Supersparse Linear Integer Models for Optimized Medical Scoring Systems

Berk Ustun; Cynthia Rudin

Source-linked AI summary

Supersparse Linear Integer Models for Optimized Medical Scoring Systems

Berk Ustun, Cynthia Rudin

arXiv:1502.04269v3Feb 15, 2015stat.MLcs.DMcs.LGstat.APstat.ME

TL;DR

Medical scoring systems must be accurate, sparse, integer-valued, and operationally constrained, but conventional learning methods often require approximations and tuning. The paper introduces SLIM, an integer-programming approach that directly optimizes accuracy and sparsity while supporting coprime coefficients and operational constraints. SLIM produced accurate, sparse models across the reported datasets and enabled tailored medical scoring systems without parameter tuning.

Problem
Medical scoring systems are difficult to learn from data because they must be accurate, sparse, use small coprime integer coefficients, and satisfy operational constraints.
Method
SLIM uses integer programming to directly optimize 0–1 loss and sparsity while restricting coefficients to coprime integers and incorporating operational constraints.
Results
SLIM produced accurate and sparse models for all reported datasets within 10 minutes, with 0.0% MIPGAP proofs of optimality for mammo, mushroom, bankruptcy, and breastcancer.
Takeaways & Limitations
SLIM provides tailored scoring systems that can satisfy multiple operational constraints without parameter tuning and has been applied to sleep apnea screening.
Takeaways & Limitations
Interpretability remains subjective and multifaceted, so SLIM’s interpretability benefits depend on the users and model qualities considered.

Abstract

from arXiv · show

Scoring systems are linear classification models that only require users to add, subtract and multiply a few small numbers in order to make a prediction. These models are in widespread use by the medical community, but are difficult to learn from data because they need to be accurate and sparse, have coprime integer coefficients, and satisfy multiple operational constraints. We present a new method for creating data-driven scoring systems called a Supersparse Linear Integer Model (SLIM). SLIM scoring systems are built by solving an integer program that directly encodes measures of accuracy (the 0-1 loss) and sparsity (the $\ell_0$-seminorm) while restricting coefficients to coprime integers. SLIM can seamlessly incorporate a wide range of operational constraints related to accuracy and sparsity, and can produce highly tailored models without parameter tuning. We provide bounds on the testing and training accuracy of SLIM scoring systems, and present a new data reduction technique that can improve scalability by eliminating a portion of the training data beforehand. Our paper includes results from a collaboration with the Massachusetts General Hospital Sleep Laboratory, where SLIM was used to create a highly tailored scoring system for sleep apnea screening

1 Introduction

Medical scoring systems are practical but difficult to learn from data because they must combine accuracy, sparsity, small coprime integer coefficients, and operational constraints. SLIM addresses these requirements directly through integer programming rather than approximation and parameter tuning.

Medical scoring systems support quick predictions using a few small-number arithmetic operations, often without computers or extensive training.
Traditional methods struggle to produce models that are simultaneously accurate, sparse, integer-valued, coprime, and operationally constrained.
SLIM directly optimizes 0–1 loss and the ℓ0-seminorm while restricting coefficients to a small set of coprime integers.
SLIM incorporates complicated accuracy and sparsity constraints and can produce tailored scoring systems without parameter tuning.
The paper derives discretization and generalization bounds, develops data reduction for scalability, and applies SLIM to sleep apnea screening with the MGH Sleep Laboratory.
Unlike rounded real-coefficient methods, SLIM avoids approximations that can alter accuracy, sparsity, or compliance with operational constraints.

Loss Constraints for Imbalanced Data

SLIM handles imbalanced classification by weighting positive and negative errors and imposing explicit class-specific loss constraints. It also supports structured feature-selection rules and practitioner preferences, including adjustments for missing data.

SLIM uses weighted 0–1 loss with user-defined positive and negative weights to control class-specific accuracy.
Explicit loss constraints can limit negative-example errors while prioritizing sensitivity on positive examples.
Feature indicators encode logical and hierarchical constraints, including feature-count limits, either-or rules, and if-then dependencies.
Distinct coefficient trade-off parameters let practitioners favor one input variable over another according to an acceptable accuracy sacrifice.
Adjusting a feature’s trade-off parameter penalizes features with many imputed values more heavily than features with fewer missing values.

3 Bounds on Training and Testing Accuracy

The paper derives training-accuracy discretization bounds and testing-accuracy generalization bounds for discrete, sparse, and coprime-integer linear classifiers. These results characterize when SLIM can match or improve upon real-valued baselines and how coefficient resolution, sparsity, and coprimality affect guarantees.

Discretization Bounds on Training Accuracy: A finite discrete coefficient set can contain a classifier whose training accuracy is no worse than that of a real-valued baseline.The result applies to classifiers such as SLIM compared with baselines such as SVM.
Discretization Bounds on Training Accuracy: Because SLIM directly minimizes 0–1 loss, its optimal discretized solution may achieve lower 0–1 loss than a baseline trained with a convex surrogate loss.The discretization result establishes that equally accurate discrete solutions exist, while direct optimization can select a better one within the coefficient set.
Discretization Bounds on Training Accuracy: The kth margin resolution bound permits a loss difference of at most k −1 while relating Λ to a worst-case training-accuracy guarantee.It obtains this guarantee by considering progressively larger margin values and excluding the corresponding k training examples.
Generalization Bounds on Testing Accuracy: Generalization bounds are successively tightened for discrete, sparse, and coprime-integer classifiers by restricting the hypothesis space.The bounds use finite coefficient sets, sparsity implied by C0, and counting arguments over coprime integer vectors; coprimality can significantly improve the bound when dimensionality is high and Λ is small.
Generalization Bounds on Testing Accuracy: Increasing C0 produces models with better generalization properties, while coprime coefficients can significantly reduce the number of candidate classifiers.The coprime-coefficient bound is expressed using P-dimensional Farey points of level Λ, and Figure 1 reports the associated relative density and bound improvement for δ = 0.01.

4 Data Reduction

Data reduction discards redundant training examples before solving a difficult optimization problem, while guaranteeing the reduced dataset preserves the original optimal classifiers under a surrogate level-set condition. Applied to SLIM, it can remove substantial portions of training data.

4 Data Reduction: Data reduction decreases training computation by discarding redundant examples before solving the original optimization problem.It is especially suited to SLIM because its underlying optimization problem can be difficult to solve on large instances.
4 Data Reduction: The procedure solves N + 1 surrogate-problem variants and removes examples that cannot change the optimal classifier.The remaining dataset DM is guaranteed to yield the same optimal classifier as the initial dataset DN.
4 Data Reduction: The surrogate ε-level set must contain all optimizers of the original problem for safe example removal.The surrogate feasible set and objective may vary, provided a suitable ε satisfies this containment condition.
4 Data Reduction: Theorem 5 states that training on the reduced dataset yields the same set of optimal classifiers as training on the initial dataset.The guarantee holds when ε satisfies the theorem’s level-set condition.
4.2 Off-The-Shelf Data Reduction for SLIM: For SLIM, data reduction can use the LP relaxation as a surrogate problem either before training or iteratively during integer-program solving.A feasible SLIM solution determines a suitable surrogate-level-set width.
4.2 Off-The-Shelf Data Reduction for SLIM: Over 40% of bankruptcy-dataset training data was discarded using the trivial λ = 0 solution, versus over 80% using a higher-quality feasible solution.Figure 3 varies the filtered proportion with ε for an SLIM instance having C0 = 0.01 and coefficients in {−10, . . . , 10}P +1.

5 Application to Sleep Apnea Screening

The authors applied SLIM to sleep-apnea screening using patient data and physician-specified constraints on false positives, model size, and coefficient signs. The resulting training setup addressed all three constraints without parameter tuning or model selection.

5 Application to Sleep Apnea Screening: The sleep-apnea application used 1,922 patient records and 33 binary health- and sleep-related features, with OSA present in 76.9% of patients.The positive class represented obstructive sleep apnea.
5 Application to Sleep Apnea Screening: Physicians required maximum FPR of 20%, at most 5 features, and sign constraints consistent with established risk-factor relationships.These constraints targeted diagnostic control, transparency, and clinically acceptable feature directions.
5 Application to Sleep Apnea Screening: SLIM used integer coefficients between −10 and 10 and addressed all three operational constraints without parameter tuning or model selection.Loss, feature-count, and coefficient-sign constraints were incorporated directly into the optimization setup.
5.3 Results and Observations: The study compared the best model trained by each method and summarized whether the methods satisfied the specified operational constraints.Model size was defined by the number of coefficients for linear models and by analogous structural counts for other model classes.

On the Difficulties of Handling Operational Constraints

Among nine classification methods, only SLIM, Lasso, and Elastic Net produced models satisfying all physician-specified operational constraints. Other methods lacked suitable controls, failed constraints, or could not reliably preserve them through tuning.

Only SLIM, Lasso, and Elastic Net produced models satisfying all operational constraints.Tree and rule-based methods failed the maximum FPR constraint, while ℓ2-regularized methods failed the required sparsity level.
Tree and rule-based methods could not produce models with maximum FPR ≤20%.This included CART, C5.0 Tree, and C5.0 Rule.
ℓ2-regularized methods could not produce models with the required sparsity.The reported examples were Ridge, SVM Lin., and SVM RBF.
Popular classification methods often lack mechanisms for jointly controlling operational quantities such as sparsity, sign constraints, and false-positive rate.Available controls may also require high-dimensional parameter tuning and still fail to find a feasible model.
Tuned parameter values are not guaranteed to preserve all operational constraints when the training set changes.The paper describes this as a portability problem for standard model-selection procedures.

On the Sensitivity of Acceptable Models

SLIM achieved higher sensitivity than acceptable Lasso and Elastic Net models while using a much smaller, constrained hypothesis space. In the sleep-apnea application, it produced a deployable scoring system with 61.4% test sensitivity and 20.9% test FPR while satisfying all operational constraints.

Sensitivity and sparsity: At least 8 coefficients were required by Lasso and Elastic Net to match SLIM’s sensitivity under sign and FPR constraints.Figure 5 compares the highest-sensitivity models at model sizes from 0 through 8.
ROC performance: SLIM scoring systems dominated Lasso and Elastic Net across the entire ROC curve.The comparison used models satisfying sign and model-size constraints and evaluated 10-CV mean test TPR across FPR values from 5% to 95%.
Sleep-apnea application: Lasso and Elastic Net had poor sensitivity for deployment as screening tools: 29.3% for Lasso and 44.2% for Elastic Net.The corresponding SLIM model had 61.4% sensitivity.
Interpretability: All three best acceptable models aligned with domain knowledge by obeying sign constraints and assigning large coefficients to established risk factors.Examples included BMI, female sex, age, snoring, and hypertension.
Interpretability: SLIM’s small integer coefficients and high sparsity support qualitative understanding of how input variables influence predictions jointly.The paper connects this interpretability benefit to users’ limited ability to handle many cognitive entities and estimate associations among multiple variables.
Sleep-apnea application: 61.4% test TPR and 20.9% test FPR were achieved by the SLIM sleep-apnea scoring system while satisfying all operational constraints.The model was trained without parameter tuning; its training TPR/FPR were 62.0/19.6%.

6 Numerical Experiments

The experiments compare SLIM with popular classification methods across eight datasets, emphasizing accuracy, sparsity, computation, and interpretability. SLIM generally achieves favorable accuracy–sparsity trade-offs and produces interpretable scoring systems, while discrete coefficient restrictions can affect accuracy at larger model sizes.

Accuracy, Sparsity and Computation: SLIM produced accurate and sparse models for all datasets within 10 minutes, with zero optimality gaps on four datasets.The solver proved optimality for mammo, mushroom, bankruptcy, and breastcancer.
Accuracy, Sparsity and Computation: SLIM was more accurate than Lasso at some sparsity level on every dataset and sometimes at all sparsity levels.The latter pattern occurred for spambase, haberman, mushroom, and breastcancer.
Accuracy, Sparsity and Computation: The finite coefficient set L can make Lasso more accurate mainly at larger model sizes.This comparison identifies the regularization effect associated with restricting SLIM to discrete coefficients.
Accuracy, Sparsity and Computation: In bankruptcy, the highest-training-accuracy SLIM model used 3 of 6 features because of the finite coefficient-set restriction.Without that restriction, the paper states that all features would be used to improve training accuracy.
Interpretability: Interpretability benefits are baseline and subjective, but operational constraints allow practitioners to encode audience-specific interpretability requirements.The paper contrasts SLIM’s linear form with the hierarchical structure of C5.0 models.
Interpretability: On mushroom, SLIM achieved 0.0 ± 0.0% 10-CV mean test error using 7 integer coefficients, simplified to a 5-line scoring system.The simplified form groups three mutually exclusive odor variables with the same coefficient.

7 Specialized Models

The paper extends SLIM to specialized integer models that control coefficient interpretability, operate on binary rules, or optimize thresholded features. These models preserve integer-programming optimization while tailoring penalties and constraints to particular model structures.

Personalized Integer Linear Models (PILM): PILM generalizes SLIM by assigning coefficients to interpretability sets with progressively larger penalties.The sets must be mutually exclusive and ordered by interpretability, with monotonically increasing trade-off parameters.
Rule-Based Models: SLIM can produce rule-based models by thresholding real-valued features or encoding categorical values as binary rules.Thresholds may be selected using domain expertise, rule mining, or discretization.
M-of-N Rule Tables: M-of-N rule tables predict positive when at least M of N rules are true and require users only to count satisfied rules.They can be trained as stand-alone discrete linear classifiers.
M-of-N Rule Tables: An optimized M-of-N table sets M = λ0 + 1 and determines N from the selected binary rules.The optimization uses binary rule coefficients and a sparsity penalty tied to rule inclusion.
Threshold-Rule Integer Linear Models (TILM): TILM uses thresholded features and penalizes both the number of selected features and the number of rules per feature.It also limits rules per feature, enforces common coefficient signs, and uses a small ℓ1 penalty for coprime coefficients.

8 Conclusion

The paper concludes that SLIM creates data-driven medical scoring systems by directly optimizing accuracy and sparsity under operational constraints. Its main advantage is avoiding surrogate approximations, while current integer-programming software makes such optimization practical for many real-world datasets.

Conclusion: SLIM fully optimizes accuracy and sparsity, accommodates multiple operational constraints, and requires no parameter tuning.These properties are presented as the paper’s central demonstrated capabilities.
Conclusion: Avoiding surrogate loss functions and ℓ1-regularization preserves direct control over model accuracy and sparsity.The paper identifies this avoidance of computation-oriented approximations as the main benefit over existing methods.
Conclusion: Integer-programming software can also support feasible-model mining and improvements in solver performance without code revisions.These are additional practical benefits attributed to the optimization framework.

A Proofs of Theorems

The proofs establish margin-preserving discretization properties and theoretical results for discrete sparse linear classifiers and reduced training data. They formalize when coefficient rounding preserves classifications and when data reduction is valid.

Discretization and Margin Bounds: Rounding normalized coefficients to a sufficiently fine grid preserves the classification sign whenever the original classifier has a nonzero margin.The proof treats positive, negative, and zero-margin cases separately.
Discretization and Margin Bounds: The proof handles negative margins analogously, showing λ^T x_i < 0 whenever ρ^T x_i < 0.Together with the positive-margin case, this establishes sign agreement across training examples.
Discrete Classifier Generalization: Because the zero classifier is feasible and has objective value 1, every optimal solution has objective value at most 1.This bounds the relevant minimizers for the discrete optimization problem.
Reduced Data: The data-reduction proof relies on removing examples only when their classification sign is fixed across the relevant classifier set.The removed set is represented as S = D_N \ D_M.
Surrogate Conditions: Under the stated surrogate-function conditions and Cψ > 2ε, the level-set condition holds with ε = L Cλ.The result follows by combining the proof’s inequalities and Lipschitz condition.