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:
- 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."
- Sparsity Constraints: To ensure model efficiency, we enforce $k$-sparsity on each prototype $w_j$, limiting the number of features the model considers.
- 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.
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.
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