Research of efficient MNIST feature transformations, research zkML-friendly ML models for it, implement in transpiler and examples

[kpandl]

The goal is to further improve MNIST performance (classification accuracy and constraint usage). For this, the following milestones need to be completed:

Milestone 1, feature pre-processing techniques

• Task: Research feature transformations that transform the MNIST images into lower-dimensional features with rich information
• Deliverable: Python code that performs feature pre-processing, experimental results how valuable the different techniques are for MNIST classification using common ML models
• Date: Thu, 9/28

Milestone 2, zkML-friendly ML model exploration

• Task: Research ML models that can classify these features well while being zkml-friendly
• Deliverable: Prototypical implementation of these models in Leo, estimation of constraint size
• Date: 10/4

Milestone 3, implementation of further models in the transpiler

• Task: Implement one (or more) promising models in the zkml Leo transpiler, run MNIST tests with these models
• Deliverable: Updated python code for the transpiler, Jupyter notebook running MNIST in Leo with the updated transpiler
• Date: 10/18

[kpandl]

Milestone 1 results
The experiments are conducted in the 6 Jupyter notebooks in zkml-research/MNIST_preprocessing. The last notebook (6_presentation) has the most promising results in terms of accuracy and expected computational effort for inference:

• Crop to a 20x20 window, Haar features + 2 manual features, MLP with L1 regularization + Pruning: 1028 weights, 97% accuracy

I also evaluated binary images, instead of uint8 images. Here are some promising results:

• Haar features + 2 manual features, MLP with L1 regularization + Pruning: 2738 weights, 96% accuracy
• Crop to a 20x20 window, Haar features, MLP with L1 regularization + Pruning: 1240 weights, 94% accuracy
• Haar features + 2 manual features, SVM: 7139 support vectors, 95.8% accuracy

There may be further potential upward (e.g., through iterative pruning, further pre-processing steps), but it seems reasonable to implement it in zk, see where we land constraint-wise and then see what further optimizations are promising

[kpandl]

Milestone 2 results

For milestone 2, I mainly used the mlp1 Leo program, and variations thereof (e.g., by commenting out certain sections or changing few lines of code and measuring the effect on constraints). The program explores the feasibility of MLP neural network inference in Leo, following the promising results of using MLP networks for MNIST in milestone 1. In the following, I list the experimental results and interpretation thereof.

Constraint measurements in demo Leo program:

• Leo program with 1 ReLu call: 102 constraints

• Leo program with 2 ReLu call: 171 constraints

• Leo program with 3 ReLu call: 240 constraints

• So, 69 constraints per ReLu call

• Multiplications of fields seem to add only 1 constraint, so very efficient. Additions seem to be free

Constraint extrapolation for a neural network:

• ReLu is called once for every neuron in the hidden layer. In the one example, we have 31 hidden neurons, which adds an estimated 2139 constraints
• Multiplication is called 1028 times, adding an estimated 1028 constraints

This means the core neural network logic should be very efficient (a bit more than 3k constraints), some additional overhead may come from the general Leo program structure / inputting and outputting values. There may also be hidden constraints, so we need to try it out and evaluate the proving times.

Other observations:

• Casting fixed variables seems to be free. Declaring an integer variable and then casting also seems to be free. This is especially useful for specifying (hardcoding) negative integer values in the code

Based on these results, it seems reasonable to add MLP neural networks to the supported models in the transpiler, and then evaluate the inference in Leo, for milestone 3.

[kpandl]

Milestone 3 results

For milestone 3, I implemented MLP neural networks in the transpiler, and released a new transpiler version on PyPi. I also updated the decision tree MNIST example to make use of Haar features (and other features), and added an example for MLPs. The MNIST MLP example uses Haar features (and other features), L1 regularization and iterative model pruning in training, and layer-wise fixed-point scaling factors in the inference.

With decision trees, we reach around 86.6% test accuracy @ 27k constraints, and 88.2% accuracy @ 57k constraints. With MLP neural networks, we reach around 93.9% accuracy @ 201k constraints, and higher accuracies (around 97/98% with more constraint usage). There may be further room for improvement in the MLP constraint usage by using fields instead of integers - this feature is implemented in the transpiler but not fully working yet and is part for future work.

Going forward, the focus will be on creating an MNIST web app building upon these transpiled models.