Learning a Code: Machine Learning for Approximate Non-Linear Coded Computation

1 Introduction

• Coded computation encodes k data inputs into r parity inputs, applies F to all k + r inputs, and decodes available outputs to reconstruct up to r unavailable outputs.The design goal is to choose encoding E and decoding D for reconstruction of unavailable outputs of F.Source: §1 · p. 2
• Prior coded-computation work addresses linear functions and specific iterative optimization algorithms, but the authors report no existing approach for broader nonlinear computations such as neural networks.Activations and max-pooling make neural networks nonlinear despite their linear fully connected and convolutional layers.Source: §1 · p. 2
• The approach learns E and D as neural networks, trains them together through F by backpropagation, and permits approximate rather than exact reconstruction.Approximate outputs are considered sufficient for many applications, including machine-learning algorithms.Source: §1 · p. 2
• The approach is stated to apply to any differentiable function, while experiments focus on MLP and ResNet-18 image classifiers across MNIST, Fashion-MNIST, and CIFAR-10.The reported reconstruction rates include 98.87%, 92.06%, and 80.84% for ResNet-18 on those datasets, respectively.Source: §1 · p. 3
• With 20% redundant base-model computations and 10% unavailable requests, CIFAR-10 accuracy rises from 84.12% to 90.59%, and MNIST accuracy from 89.28% to 98.75%.The scenario uses k = 5 and r = 1.Source: §1 · p. 3
• The authors present the first learning-based approach to designing erasure codes and the first coded-computation approach for resilience to nonlinear functions, to their knowledge.They describe architectures and training methods based on multilayer perceptrons and dilated convolutional neural networks.Source: §1 · p. 3

2 Related Work

• Earlier coded-computation schemes target linear functions such as matrix multiplication [DCG16] [LMAA16] [YMAA17] [WLS18] [DCG17] [RPPA17] [MCJ18].The section also describes codes for specific iterative optimization algorithms [KSDY17, KSDY18, TLDK17].Source: §2 · pp. 3–4
• For machine-learning training, prior schemes address particular optimization algorithms, including gradient descent and L-BFGS, rather than arbitrary nonlinear inference computations [KSDY17] [KSDY18] [MSM18].The cited approaches encode data, gradients, or the data matrix's second moment.Source: §2 · p. 4
• Communication research has used neural networks to learn decoding algorithms for existing block codes, whereas this work learns both encoding and decoding algorithms end to end [NML+18] [KJR+18].Source: §2 · p. 4
• Neural-network approaches to image compression and cryptography also transform data for later reconstruction, but differ in goal, architecture, and training methodology [TOH+16] [AA16].Source: §2 · p. 4

3 Learning a Code

• The encoding function E creates r parity inputs from k data inputs, and decoding function D reconstructs unavailable data outputs when at most r outputs are unavailable.The objective is to learn E and D to minimize a chosen loss.Source: §3 · p. 4
• Neural networks serve as E and D because they can perform universal function approximation.Source: §3 · p. 4
• The section presents the training methodology followed by the neural-network architectures for learning the encoding and decoding functions.Source: §3 · p. 4

3.1 Training methodology

• Training keeps F fixed and updates the neural-network parameters for E and D.Source: §3.1 · p. 4
• For machine-learning functions, training uses F's training dataset when available; otherwise, it can use generated pairs (X, F(X)).Each sample selects k inputs, and training covers unavailability scenarios except those where only parity outputs are unavailable.Source: §3.1 · pp. 4–5
• The forward pass encodes k inputs into r parities, applies F to all inputs, and feeds available outputs to D to reconstruct unavailable data outputs; backpropagation passes through D, F, and E.The parameters of E and D are updated through F.Source: §3.1 · p. 5, Figure 2 · p. 5
• Training loss can compare reconstructed and actual function outputs, or, for machine-learning functions with labels, compare predicted labels with true labels.The output-based loss applies to any given F.Source: §3.1 · p. 5

3.2 Encoding function architectures

• The encoding function maps k data inputs to r parity inputs; for image classification, each input is an n × n image and F returns an m-length vector.Source: §3.2 · p. 6

3.2.1 MLPEncoder

• MLPEncoder flattens and concatenates the k images, then uses two fully connected layers to produce the parity vectors [Hor91].Its fully connected layers can combine arbitrary input values, but their high parameter count can lead to overfitting.Source: §3.2.1 · pp. 6–7

3.2.2 ConvEncoder

• ConvEncoder processes the k inputs as channels in their original n × n form and uses dilated convolutions to expand receptive field without downsampling and upsampling.It uses fewer parameters than MLPEncoder but requires more layers to combine all input pixels; the lower parameter count helps avoid overfitting.Source: §3.2.2 · p. 7

3.2.3 Multi-channel input

• For multi-channel images, the encoder operates independently across corresponding channels, then combines the resulting parity channels into parity images.Source: §3.2.3 · p. 7

3.3 Decoding function architecture

• The decoder D uses available base-model outputs to reconstruct approximations of up to r unavailable outputs among the k data inputs.The description applies to a neural-network classifier over m classes but says the architecture can be repurposed for any differentiable F.Source: §3.3 · p. 7

3.3.1 Representing unavailability

• Unavailable outputs are represented by zero vectors in their original input positions, preserving positional information for the decoder.The decoder outputs k approximate reconstructions in corresponding positions; parity inputs are shaded in Figure 5.Source: §3.3.1 · p. 8, Figure 5 · p. 8

3.3.2 Decoding function architecture

• The decoding function is a 3-layer MLP that uses raw base-model outputs without converting them to probabilities with softmax.Table 2 describes a fully connected decoder with ReLU activations after all but the final layer.Source: §3.3.2 · p. 8, Table 2 · p. 8

4 Evaluation

• The evaluation uses MLP and ResNet-18 image classifiers on MNIST, Fashion-MNIST, and CIFAR-10, with test accuracies reported for the base models.The evaluation also analyzes accuracy and prediction quality for reconstructed outputs.Source: §4 · p. 8, Table 3 · p. 9

4.1 Experimental setup

• The experimental setup considers multiple loss functions, architectures, and accuracy metrics for training learned encoding and decoding functions.The authors describe this as the first training methodology for learning codes for coded computation.Source: §4.1 · p. 9

4.1.1 Loss functions used in training

• Training loss is calculated against either the base-model output using MSE or KL-divergence, or the true label using cross-entropy.The configurations are denoted MSE-Base, KL-Base, and XENT-Label.Source: §4.1.1 · p. 9

4.1.2 Base models

• Base-MLP is a 3-layer model for MNIST and Fashion-MNIST, while ResNet-18 is used for Fashion-MNIST and CIFAR-10.Base-MLP is not used for CIFAR-10 because similar architectures have been shown to achieve low accuracy.Source: §4.1.2 · p. 9

4.1.3 Encoding and decoding function architectures

• Experiments use both proposed encoding architectures, MLPEncoder and ConvEncoder, together with the MLP-based decoding architecture.Results are presented for all proposed architecture combinations.Source: §4.1.3 · p. 9

4.1.4 Parameters and training details

• Experiments use k = 2 or 5 with r = 1, corresponding to 50% or 20% redundant computation, respectively.Training uses minibatches of 64 samples for k = 2 and 32 for k = 5, with Adam at learning rate 0.001 and L2 regularization of 1 × 10^-5.Source: §4.1.4 · pp. 9–10

4.1.5 Accuracy metrics

• Recovery-accuracy measures agreement with the base model's predicted label, while overall-accuracy measures agreement with the true label.Reported aggregate accuracy averages across unavailability scenarios; known scenario statistics can instead be used as weights.Source: §4.1.5 · p. 10

4.2.1 Main results

• 95.71% and 82.77% of unavailable ResNet-18 outputs are recovered on MNIST and Fashion-MNIST, respectively, with 20% redundant computation; CIFAR-10 recovery is 80.74% with k = 2.Table 4 reports recovery-accuracy on test data for configurations selected by highest training recovery-accuracy.Source: §4.2.1 · p. 10, Table 4 · p. 11
• Overall-accuracy differs only marginally from recovery-accuracy in the experiments.The overall-accuracy results are relegated to Appendix A.Source: §4.2.1 · p. 10

4.2.2 Effect of configuration settings and parameters

• Test accuracy is significantly higher at k = 2 than k = 5 across datasets, base models, and encoding architectures, trading 50% redundancy for 20%.The authors suggest that each parity must pack information about fewer images at k = 2.Source: §4.2.2 · p. 11
• Despite its greater complexity, ResNet-18 achieves similar learned-code accuracies to Base-MLP on MNIST and Fashion-MNIST.The authors report that base-model complexity does not adversely affect learned-code accuracy in these experiments.Source: §4.2.2 · p. 11
• On MNIST and Fashion-MNIST, MLPEncoder and ConvEncoder differ little in accuracy, while ConvEncoder greatly outperforms MLPEncoder on CIFAR-10.The authors attribute MLPEncoder's lower CIFAR-10 accuracy to overfitting from its high parameter count; they report only marginal differences between training losses.Source: §4.2.2 · p. 11

4.2.3 Detailed analysis of accuracy and quality of predictions

• 2.19 times higher recovery-accuracy is attained, on average, for samples the base model classifies correctly than for samples it classifies incorrectly.Figure 6 compares the two sample groups across the configurations listed in Table 4.Source: §4.2.3 · p. 12, Figure 6 · p. 12
• 61.29% of inaccurate reconstructions predict the base model's second-ranked class, and 79.12% predict a class among its top three.Figure 7 reports the fractions of inaccurate reconstructions at ranks 2 and 3 for the configurations considered.Source: §4.2.3 · p. 12, Figure 7 · p. 12

• The learned codes reconstruct up to 98.85%, 92.15%, and 80.74% of unavailable class predictions on MNIST, Fashion-MNIST, and CIFAR-10, respectively.The evaluations use image classifiers.Source: §5 · p. 13
• Neural-network architectures and a training methodology learn encoding and decoding functions that approximate unavailable outputs for differentiable nonlinear functions.Source: §5 · p. 13
• The approach addresses the limited applicability of existing coded-computation techniques to general computation, including machine-learning algorithms.Source: §5 · p. 13

• Table 5 reports recovery-accuracy and overall-accuracy for r = 1 across all configuration settings, with little difference between the metrics when other settings are held constant.Source: Table 5 · p. 16, Appendix A · p. 16
• The authors suggest that similar recovery-accuracy on correctly classified samples and overall accuracy may partly explain the similarity between the two metrics.Source: Appendix A · p. 16
• Recovery-accuracy and overall-accuracy are very similar across XENT-Label, KL-Base, and MSE-Base configurations, except for two reported settings.For Fashion-MNIST with Base-MLP and MLPEncoder, MSE-Base decreases both test accuracies versus KL-Base and XENT-Label; for CIFAR-10 with ResNet-18, ConvEncoder, and k = 5, MSE-Base increases both by roughly 0.10.Source: Appendix A · p. 17

• For MNIST logistic regression, the decoder receives raw outputs AX + b before softmax, and softmax is applied to the reconstructed outputs.Each 28 × 28 image is flattened into a 784-length vector, and the model has 10 classes.Source: Appendix B · p. 17
• With r = 1 and KL-divergence loss, the proposed codes achieve high test recovery-accuracy across the evaluated encoding architectures and k = 2 and 5.The base model achieves 0.9283 accuracy on the MNIST test set.Source: Appendix B · p. 17
• Because AX + b can be transformed into a linear function, existing linear-function approaches may be more suitable here by guaranteeing exact reconstruction.The paper's broader goal is to handle nonlinear functions, to which those approaches do not apply.Source: Appendix B · p. 17