Learning SMaLL Predictors

Vikas K. Garg, Ofer Dekel, Lin Xiao

TL;DR

The Sparse Multiprototype Linear Learner (SMaLL) is a new algorithm designed to train highly accurate, interpretable, and resource-constrained models. By relaxing the classic (but computationally hard) problem of learning Boolean $k$-DNF formulae into a continuous optimization task, SMaLL produces predictors that excel on mobile and embedded devices where memory and power are at a premium.

What Problem Does This Paper Address?

Modern machine learning has a "bloat" problem. State-of-the-art models like deep neural networks or large ensembles achieve incredible accuracy but require billions of operations (GFLOPs) to make a single prediction. This makes them unsuitable for resource-constrained environments like wearables, IoT sensors, or smartphones.

Furthermore, these "black box" models are notoriously difficult to interpret. In high-stakes fields like finance or medicine, an engineer needs to know why a model made a specific decision. The authors look back to classical learning theory—specifically Disjunctive Normal Forms (DNFs)—to find a solution. A DNF is essentially an "OR of ANDs" (e.g., "Approve loan if [Credit > 700 AND Income > 50k] OR [Downpayment > 20% AND Employed]"). While DNFs are inherently interpretable and compact, learning them from data is a notoriously difficult (NP-hard) problem.

Methods

The authors introduce SMaLL, which bridges the gap between the interpretability of Boolean logic and the efficiency of continuous optimization.

  1. Continuous Relaxation: They represent a $p$-term $k$-DNF as a "max of dot products." Instead of discrete Boolean variables, they use a function $f(x) = \text{sign}(\max_{j \in [p]} w_j \cdot x)$, where each $w_j$ is a "prototype" vector representing one "AND" term.
  2. Sparsity Constraints: To keep the model small, they enforce that each prototype vector $w_j$ is $k$-sparse (meaning it only uses $k$ features).
  3. Optimization via Mirror-Prox: The resulting training problem is a difficult mixed-integer nonlinear program. The authors use a clever mathematical trick—a saddle-point relaxation—to turn it into a convex-concave problem. They then solve this efficiently using a customized Mirror-Prox algorithm, which provides a principled way to handle the sparsity constraints without falling into the traps of simpler heuristic methods.

Datasets

The researchers evaluated SMaLL across a wide variety of benchmarks from the OpenML repository:

  • Low-dimensional datasets ($n < 20$): 17 datasets including bankruptcy, vineyard, and human_dev to test general classification performance.
  • High-dimensional datasets ($n \ge 50$): Datasets like fri_c0_1000_50 to test how well the algorithm handles feature selection and sparsity.
  • Interpretability Case Study: The Breast Cancer dataset was used to visualize how the model selects specific biological markers to reach a diagnosis.

Key Insights and Ideas

  • Improper Learning as a Shortcut: The paper doesn't try to solve the fundamental theoretical hardness of learning $k$-DNFs. Instead, it uses "improper learning"—learning a slightly more powerful class of models (continuous prototypes) that is easier to optimize but still captures the essence of the original logic.
  • The "Max" Operator is Key: By using a max over multiple linear prototypes, the model can create non-linear, complex decision boundaries that a single linear classifier (like a standard SVM) simply cannot.
  • Efficiency vs. Accuracy: The authors demonstrate that you don't always need a massive model for high accuracy. In many cases, a 2-prototype model using only 3 features per prototype can match the performance of much larger ensembles.
Figure 1: Decision surfaces on toy data. Notice how SMaLL (bottom right) creates a non-linear boundary that captures the data better than linear methods like Logistic Regression.

Key Results

  • Superior Sparsity: In high-dimensional tests, SMaLL achieved a "normalized accuracy" (accuracy per feature used) that was often an order of magnitude higher than standard sparsity-inducing methods like $L_1$ regularization (Lasso) or Elastic Net.
  • Competitive Accuracy: On low-dimensional data, SMaLL outperformed or matched established algorithms like Random Forests, AdaBoost, and SVMs in 14 out of 17 datasets.
  • Interpretability in Action: On the Breast Cancer dataset, SMaLL achieved >94% accuracy using just two prototypes with three features each. As shown in Figure 2, it's easy to see exactly which features (like perimeter_worst) the model relies on.
Figure 2: SMaLL applied to Breast Cancer data. The model is transparent, showing the distribution of the few key features it uses to make a prediction.
Figure 4: The "Big Picture" comparison. SMaLL (dark blue bar) shows a massive lead in the ratio of accuracy to the number of features used.

Limitations and Future Work

While SMaLL is powerful, the authors note a few areas for improvement:

  • Initialization: The algorithm currently benefits from pre-clustering positive examples to initialize prototypes. A more automated initialization strategy could make it even more robust.
  • Hyperparameter Tuning: Like many sparse methods, the user must still choose the number of prototypes ($p$) and the sparsity level ($k$).
  • Scaling to "Big Data": While efficient on the tested datasets, further work is needed to see how the Mirror-Prox approach scales to truly massive datasets with millions of features.

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 K. 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