Learning SMaLL Predictors

Vikas Garg, Ofer Dekel, Lin Xiao

Abstract

We present a new machine learning technique for training small resource-constrained predictors. Our algorithm, the Sparse Multiprototype Linear Learner (SMaLL), is inspired by the classic machine learning problem of learning $k$-DNF Boolean formulae. We present a formal derivation of our algorithm and demonstrate the benefits of our approach with a detailed empirical study.

Introduction: The Efficiency-Interpretability Tradeoff

Modern machine learning faces a significant "bloat" problem. While state-of-the-art models achieve high accuracy, they often require billions of operations (GFLOPs), making them unsuitable for resource-constrained "edge" devices like wearables or embedded sensors. Furthermore, these large models act as "black boxes," lacking the interpretability required for critical applications.

To address this, we revisit Boolean formulae, specifically $k$-DNFs (an "OR of ANDs" logic). While naturally intuitive to humans, $k$-DNFs have historically been difficult to train due to their discrete nature. Our work introduces SMaLL, which bridges this gap by relaxing logical rules into a continuous optimization framework.

The SMaLL Algorithm

The Sparse Multiprototype Linear Learner (SMaLL) transforms rigid Boolean logic into a trainable model through several key innovations:

  1. Continuous Relaxation: We represent a DNF as a "multiprototype" predictor: $f(x) = \text{sign}(\max_{j \in [p]} w_j \cdot x)$, where each $w_j$ represents a logical "term."
  2. Sparsity Constraints: To ensure model efficiency, we enforce $k$-sparsity on each prototype $w_j$, limiting the number of features the model considers.
  3. Optimization: We reformulate the training process—a mixed-integer nonlinear problem—into a convex-concave saddle-point relaxation. This is solved using a customized Mirror-Prox algorithm with a specialized projection step to maintain the sparsity budget.
The SMaLL decision surface demonstrates how multiple prototypes create a robust, interpretable boundary.

Experimental Evaluation

We evaluated SMaLL against standard classifiers, including SVMs, Random Forests, and Gradient Boosting, across 17 low-dimensional and several high-dimensional OpenML datasets.

Key Results

SMaLL demonstrated competitive accuracy, matching or outperforming complex ensembles like Random Forests and Gaussian Processes in 12 out of 17 low-dimensional datasets. Notably, on high-dimensional tasks like the Breast Cancer dataset, SMaLL achieved over 94% accuracy using only two prototypes with three features each.

Comparison of decision surfaces across various classification algorithms. SMaLL achieves the highest accuracy (.73) in this benchmark while maintaining a robust, clean decision boundary.

As shown in the comparison above, SMaLL produces decision surfaces that are less prone to the "overfitting noise" characteristic of k-Nearest Neighbors or Decision Trees. This robustness, combined with extreme sparsity, makes it ideal for deployment on hardware with strict power and memory budgets.

Conclusion

SMaLL offers a compelling solution for edge AI by providing a high "normalized accuracy"—predictive power per feature used. By combining the interpretability of logical formulae with the power of continuous optimization, SMaLL enables high-performance machine learning on the smallest of devices.

Summary updated

Abstract

We present a new machine learning technique for training small resource-constrained predictors. Our algorithm, the Sparse Multiprototype Linear Learner (SMaLL), is inspired by the classic machine learning problem of learning $k$-DNF Boolean formulae. We present a formal derivation of our algorithm and demonstrate the benefits of our approach with a detailed empirical study.
BibTeX
@inproceedings{garg2018learning,
  author = {Vikas Garg and Ofer Dekel and Lin Xiao},
  title = {{Learning SMaLL Predictors}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=B1VAt8W_Wr},
}
Figure