Source-linked AI summary
Learning Certifiably Optimal Rule Lists for Categorical Data
Elaine Angelino, Nicholas Larus-Stone, Daniel Alabi, Margo Seltzer, Cynthia Rudin
TL;DR
Interpretable predictive models remain important for socially consequential decisions, but finding optimal rule lists over categorical data is computationally difficult. CORELS uses specialized discrete optimization, bounds, and data structures to find certifiably optimal rule lists; on practical datasets, these lists match approaches such as random forests in accuracy while remaining interpretable.
Problem
Interpretable, sufficiently predictive models are needed for socially important decisions, while optimizing regularized risk over rule lists is computationally difficult because the search space is exponential.
Method
CORELS is a branch-and-bound algorithm that searches rule lists assembled from frequent itemsets and returns an optimal training-objective solution with a certificate of optimality.
Results
CORELS produces certifiably optimal, interpretable rule lists with the same accuracy as approaches such as random forests on COMPAS and stop-and-frisk datasets; equivalent support and equivalent points bounds sometimes proved critical for finding solutions and proving optimality.
Takeaways & Limitations
The results indicate that optimal sparse rule lists can provide an interpretable alternative to proprietary black-box recidivism prediction tools.
Takeaways & Limitations
CORELS is predictive rather than causal and may have difficulty proving optimality when many highly correlated features make large search-space regions difficult to exclude.
Abstract
from arXiv · showhide
We present the design and implementation of a custom discrete optimization technique for building rule lists over a categorical feature space. Our algorithm produces rule lists with optimal training performance, according to the regularized empirical risk, with a certificate of optimality. By leveraging algorithmic bounds, efficient data structures, and computational reuse, we achieve several orders of magnitude speedup in time and a massive reduction of memory consumption. We demonstrate that our approach produces optimal rule lists on practical problems in seconds. Our results indicate that it is possible to construct optimal sparse rule lists that are approximately as accurate as the COMPAS proprietary risk prediction tool on data from Broward County, Florida, but that are completely interpretable. This framework is a novel alternative to CART and other decision tree methods for interpretable modeling.
1. Introduction
The paper develops CORELS, a certifiably optimal method for learning interpretable rule lists under a regularized risk objective. Bounds, data structures, and search strategies make optimal solutions practical on public datasets, with accuracy comparable to greedy tree methods and random forests.
- Rule lists provide transparent if-then predictions, giving a reason for each prediction while targeting highly predictive models.
- Existing rule-list algorithms can be accurate and fast, but do not establish optimality or distance from the regularized-loss optimum.
- CORELS searches pre-mined frequent-itemset rules for a rule list minimizing regularized risk and returns a certificate of optimality.
- CORELS prunes incomplete lists using lower bounds, incumbent comparisons, and symmetry-aware accuracy reuse across permutations.
- A modified prefix tree organizes rule-list generation and evaluation while supporting multiple search policies and tunable space-time tradeoffs.
- CORELS generally finds optimal rule lists in seconds, certifies optimality within about 10 minutes, and achieves better or similar out-of-sample accuracy to CART and C4.5.
- On COMPAS and stop-and-frisk data, CORELS produces certifiably optimal interpretable lists with the same accuracy as approaches such as random forests.
2. Related Work
The paper places CORELS within work on optimal trees, rule learning, DNF models, and interpretable prediction. It also identifies scope boundaries: CORELS relies on pre-mined rules, supports predictive rather than causal modeling, and differs from constrained interpretability variants.
- CORELS solves a regularized version of the optimal decision-tree problem, using bounds and data structures not used by earlier cited methods.
- Greedy methods such as CART, C4.5, and several decision-list algorithms avoid broad search, while Bayesian tree methods explore it differently.
- Because DNF models are a proper subset of decision lists for fixed size, the framework can be restricted to learn optimal DNF models.
- Some CORELS bounds derive from prior mixed-integer programming work, but the cited MIP solvers do not match CORELS speed.
- CORELS depends on pre-mined rules, although other rule-mining methods could reasonably replace its enumeration procedure.
- Interpretability can involve additional constraints, such as decreasing probabilities in Falling Rule Lists, whose support bounds are more complicated.
- CORELS models are predictive only and omit causal structure and costs for classification errors or information gathering, so they cannot be used directly for policy-making.
3. Learning Optimal Rule Lists
This section formulates learning rule lists as a regularized empirical-risk minimization problem and develops bounds that enable certifiable global optimization. CORELS uses these bounds to prune impossible or redundant prefixes while preserving optimality.
- Problem formulation: Rule-list prefixes define search subspaces containing all lists that begin with those antecedents.A prefix captures data according to first-match semantics, and its extensions form the corresponding search space.
- Problem formulation: CORELS learns binary rule lists from pre-mined antecedents by minimizing misclassification error plus a length penalty.Each rule predicts the majority label among data it captures, while the default rule predicts the majority label among uncaptured data.
- Optimization bounds: Lower bounds on prefixes also apply to every extension, allowing branch-and-bound to eliminate entire subtrees without evaluating them.The framework combines hierarchical bounds with bounds on length, support, rule accuracy, and unavoidable mistakes from conflicting labels.
- Optimization bounds: Each rule in an optimal list must have sufficient support and predictive accuracy, enabling pruning during both rule mining and list construction.The support condition restricts mining to frequent itemsets, while the accuracy condition bounds how many observations each rule must classify correctly.
- Optimization bounds: Symmetry-aware pruning removes permutations of the same antecedents when another ordering has a no-worse objective lower bound.Equivalent points with identical features and opposite labels also yield unavoidable-error lower bounds that can be combined with other bounds.
4. Incremental Computation
This section reduces CORELS computation by reusing information between parent and child prefixes. Incremental updates, caching, and grouped child processing lower both execution overhead and memory demands.
- Caching and search: A prefix-tree cache stores evaluated prefixes and their lower bounds, while Algorithm 2 groups all children of a parent to consolidate cache queries.The implementation stores lower bounds rather than both lower bounds and objectives when that avoids additional storage overhead.
- Incremental updates: CORELS incrementally computes each child prefix’s objective lower bound from the stored bound of its parent.The hierarchical search structure guarantees that a parent has already been evaluated before its child.
- Incremental updates: The child rule list’s objective is likewise updated incrementally using quantities computed for the parent and newly captured data.This avoids recomputing the full regularized empirical risk from scratch.
- Algorithm: The incremental branch-and-bound algorithm initializes an empty prefix, expands queued prefixes, applies bounds, updates the incumbent, and returns a provably optimal list when the queue empties.Its recorded output is the rule list with minimum objective and the corresponding optimal objective value.
- Efficiency: With 1000 antecedents, the incremental algorithm’s maximum queue size is nearly 1000 times smaller than Algorithm 1’s.The reduction follows from reorganizing computations around all children of a particular prefix.
5. Implementation
CORELS combines optimized data structures with configurable search policies and symmetry-aware pruning. These implementation choices reduce memory use and can substantially accelerate exploration, while some promising strategies remain future work.
- Data structures: A prefix tree stores shared structure among related prefixes, with nodes representing rules and paths representing prefixes.Node metadata includes bounds, objective values, captured-sample counts, viable extensions, and deletion indicators.
- Search policies: A queue orders unexplored leaves and supports breadth-first, best-first, and other search policies.FIFO implements breadth-first search, while priority queues can order prefixes by lower bound, objective, or custom functions.
- Symmetry-aware pruning: A symmetry-aware map canonicalizes antecedent sets and retains only the ordering with the better lower bound, deleting dominated subtrees.This implements permutation-based pruning while preserving the best known representative of each antecedent set.
- Memory management: Garbage collection removes subtrees whose bounds exceed the incumbent and prunes childless nodes upward to constrain trie memory consumption.Leaves are marked for deletion because the priority queue does not expose direct access for immediate removal.
- Search policies: Ordering prefixes by lower bound usually runs faster than breadth-first search in CORELS experiments.The paper also reports that curiosity-based ordering can dramatically reduce runtime on some small problems.
- Future work: Developing curiosity functions effective across more general settings remains an open direction for future work.The reported benefits of curiosity-based ordering are currently tied to specific small problems and solution structures.
6. Experiments
CORELS produces short, transparent rule lists with predictive performance comparable to COMPAS and other algorithms across the evaluated socially important prediction tasks. Its ProPublica models show similar race-specific performance patterns to COMPAS, while the authors emphasize that transparency makes fairness easier to debate.
- Interpretability and limitations: CORELS uses transparent models with performance comparable to COMPAS, but the authors do not advocate using these specific models or claim that they are fair.They characterize the examples as illustrative and note that additional fairness or transparency constraints can be imposed.
- Comparison with COMPAS: 0.665 mean test accuracy was achieved by CORELS on ProPublica recidivism prediction, with standard deviation 0.018 across 10 folds.This result uses the Feature Set A rule lists with λ = 0.005 and is reported as competitive with COMPAS.
- Comparison with COMPAS: CORELS and COMPAS show similar race-specific performance patterns, including higher TPRs and FPRs for black individuals and higher TNRs and FNRs for white individuals.The authors state that CORELS uses only counts of past crimes, age, and gender in these simple models, and caution that fairness is not established.
- Predictive performance and model size: CORELS models are approximately as small as the heuristic models in the weapon-prediction comparison, using either 3 or approximately 5 rules versus 4 parameters.The comparison defines model size as rules for CORELS and parameters for the heuristic models.
- Predictive performance and model size: CORELS learns short, interpretable rule lists whose predictive performance is comparable to COMPAS and other evaluated algorithms.The models use a small number of rules or features while matching the reported performance of black-box and conventional alternatives.
7. Summary and Future Work on Bounds
The section identifies bounds and data structures that improve CORELS’s search efficiency, while outlining future work on additional bounds and search policies. CORELS can also provide optimality certificates and quality guarantees before complete execution.
- Empirical impact: Equivalent support and equivalent points bounds yielded the most significant empirical improvements, sometimes proving optimality even on small problems.These bounds were reported as critical for finding solutions and proving optimality.
- Future work: Future work includes efficient support for similar-support and antecedent-rejection bounds, which may enable principled approximate variants.The similar-support bound is not yet efficiently exploited in practice, while antecedent-rejection data structures remain unfinished.
- Incomplete execution: Incomplete executions can still identify the optimal rule list quickly and use lower bounds to guarantee solution quality and bound the remaining search space.Finding the optimum may take substantially less time than proving optimality.
- Future work: Search-policy choices affect pruning rates and total runtime, motivating future policies that could improve performance.The order in which prefixes are evaluated determines how quickly search-space pruning occurs.
8. Conclusion and More Possible Directions for Future Work
The conclusion defines CORELS’s practical scope and identifies settings requiring extensions, including correlated features, raw images, continuous variables, causal inference, and generic decision trees. Several proposed directions adapt or combine the rule-list framework for these settings.
- Scope and limitations: CORELS may have difficulty proving optimality when many highly correlated features create large search-space regions that are hard to exclude.The algorithm scales well to many observations, but feature correlation can hinder optimality proofs.
- Scope and limitations: CORELS is designed for interpretable structured features rather than raw images, though it could combine precomputed image features into a final classifier.The paper distinguishes interpretability for image classification from interpretability for structured data.
- Future directions: Future directions include cost-sensitive learning, weighted regularization, hybrid interpretable–black-box models, optimal DNF formulas, and generic decision trees.Generalizing the theorems or handling additional symmetries would be required for several extensions.
- Scope and limitations: CORELS does not automatically rank subgroups by positive-outcome likelihood or estimate treatment effects for causal inference.Conditional outcome proportions can be computed, but causal treatment effects require different methods.
- Scope and limitations: CORELS does not directly handle continuous variables, although interpretable rules can be constructed for use within the framework.The authors suggest techniques such as Fast Boxes for discovering useful rules over continuous data.
Appendix A. Excessive Antecedent Support
The appendix proves that antecedents with support too similar to the uncovered data cannot appear in an optimal rule list. This yields pruning rules during construction and propagates to equivalent prefixes and extensions.
- Theorem 21: An antecedent capturing nearly all data left uncovered by a prefix cannot improve error enough to offset the regularization penalty for adding a rule.The potential error reduction is bounded by ϵ, while the additional rule incurs λ; when ϵ < λ, the extension is not optimal.
- Theorem 21: If the support discrepancy equals λ, the extended rule list can be optimal; otherwise, when ϵ < λ, it is strictly worse than the shorter list.The objective comparison establishes strict suboptimality for the non-equality case.
- Pruning consequence: The bound allows branch-and-bound to prune a prefix when a new antecedent has support too similar to the data remaining after preceding antecedents.The same reasoning applies during rule-list construction and rule mining.
- Proposition 22: The excessive-support condition propagates to longer rule lists, so extensions containing such an antecedent cannot be optimal.The appendix applies Theorem 21 to any rule list whose prefix contains the excessive-support antecedent.
Appendix B. Proof of Theorem 15 (Equivalent Support Bound)
The proof establishes that equivalent-support prefixes can be compared through corresponding rule lists that preserve captured data, objective differences, and optimality relationships. This supports the equivalent support bound used for pruning.
- Prefix equivalence: Rule lists with prefixes that capture the same data share the same default rule and default-rule misclassification error.The proof formalizes equality of the uncaptured-data sets before relating corresponding objectives.
- Objective comparison: Corresponding extensions preserve the difference in regularized objectives between the extended and original rule lists.The proof states R(d′, x, y) − R(d, x, y) = R(D′, x, y) − R(D, x, y).
- Prefix correspondence: The correspondence remains valid when prefixes differ in antecedents, because extensions containing unmatched antecedents can be excluded using the insufficient-support bound.The proof handles both equivalent prefixes up to permutation and prefixes with different antecedent sets.
- Final bound: Combining objective-difference equality with the prefix correspondence yields the equivalent-support inequality between the best extensions of the two prefixes.The final relation compares the minimum objective over extensions of each prefix.
Appendix C. Proof of Theorem 18 (Similar Support Bound)
The proof compares an arbitrary rule list extending a prefix with an analogous list under a similar-support constraint. It derives an objective lower bound showing how prefix bounds and discrepancy terms constrain the analogous list.
- The proof defines rule lists d and D with prefixes dp and Dp, requiring their support-related quantities ω and Ω to be at most λ.
- For any extension d′ of dp, the analogous list D′ shares its added antecedents and satisfies R(D′, x, y) ≥ R(d′, x, y) + b(Dp, x, y) − b(dp, x, y) − ω − Ω.
- The comparison accounts for the largest possible objective discrepancy when d′ misclassifies data associated with ω and Ω while D′ classifies it correctly.
- Applying the inequality to an optimal rule list D* and its analogous list d* yields the desired inequality in Theorem 18.
Appendix D. Proof of Theorem 20 (Equivalent Points Bound)
The proof derives a lower bound for rule-list objectives by separating prefix performance from default-rule errors. It uses equivalent observations with conflicting labels to bound unavoidable mistakes.
- For identical-feature observations with opposite labels, unavoidable mistakes are bounded below by the number carrying the minority label.
- The default-rule lower bound counts label differences from the minority class across equivalent-point sets rather than directly counting default-rule mistakes.
- The objective decomposes as prefix error plus default-rule error plus λK, and the proof identifies the prefix lower bound b(dp, x, y) within this decomposition.
- Combining the bounds yields the desired inequality for Theorem 20, with extending the prefix contributing a nonnegative regularization term λ(K′ − K).
E.1 ProPublica Recidivism Data Set
The ProPublica data preparation uses categorical attributes to generate filtered antecedents for rule-list experiments. The dataset also excludes a charge attribute judged inconsistently representative for multi-charge records.
- The current-charge attribute is excluded because, for multiply booked individuals, it does not consistently reflect the most serious charge.
- Table 7 contains 6 attributes and 17 categorical values, including a constructed juvenile-crimes feature formed by summing three juvenile-crime categories.
E.3 NYCLU Stop-and-frisk Data Set
The NYCLU stop-and-frisk dataset records searches, frisks, and weapon findings, then supplies categorical antecedents for rule-list experiments. CORELS rule-list listings vary with the regularization parameter.
- The original NYCLU dataset contains 45,787 incident records, with frisks in 66.3%, searches in 15.9%, and weapons identified in 4.7% of frisk-or-search records.
- After removing records with missing data and extreme ages, the experiments use 5 categorical attributes representing 28 values.
- The antecedent set contains the base antecedents and negations for stop reason and additional circumstances, totaling 46 antecedents.
- As λ decreases, the optimal CORELS rule lists reported across 10 cross-validation folds tend to grow longer.
F.1 ProPublica Recidivism Data Set
Across regularization settings, ProPublica’s optimal rule lists share stable prefix rules, while smaller λ values yield longer and more varied lists.
- At λ = 0.02, all folds identify the same length-1 optimal rule list: priors > 3 predicts yes, otherwise no.
- At λ = 0.01, folds identify optimal 2-rule or 3-rule lists with nearly identical prefix rules, up to permutations.
- At λ = 0.005, folds identify optimal 3-rule or 4-rule lists that retain nearly identical prefix rules, up to permutations.
- The recurring ProPublica rules use age, sex, and prior offenses to predict two-year recidivism.
F.2 NYPD Stop-and-frisk Data Set
On the NYPD data set, CORELS produces optimal weapon-prediction rule lists whose structure varies with regularization, while commonly retaining suspicious-object and location rules.
- CORELS learns NYPD weapon-prediction lists centered on stop reason = suspicious object, with additional rules involving transit-authority location and other stop reasons.
- The examples include compact lists using suspicious-object status alone or paired with transit-authority location.
- At λ = 0.005, seven shown folds share the same first prefix rule, while three remaining folds are equivalent up to prefix-rule permutation.
F.3 NYCLU Stop-and-frisk Data Set
On the NYCLU data set, larger regularization values produce structurally consistent optimal lists across folds, whereas λ = 0.0025 produces more diverse and longer lists.
- For λ = 0.04 and λ = 0.01, all folds contain the same or equivalent optimal rules, up to permutation.
- At λ = 0.0025, optimal rule lists become more diverse and longer but retain similar structure.
- NYCLU lists predict weapon recovery using stop reasons such as suspicious object, casing, suspicious bulge, and fits description.
- Several examples also incorporate housing-authority or transit-authority location and Manhattan or Bronx city indicators.
Appendix G. Additional Results on Predictive Performance and Model Size for CORELS and Other Algorithms
Appendix G compares CORELS with three other algorithms on NYPD weapon prediction, plotting test-set TPR and FPR against model size across methods.
- Figure 25 plots test-set TPR and FPR as functions of model size for NYPD Feature Set D.
- Legend markers and error bars represent means and standard deviations across cross-validation folds.
- C4.5 finds large models for all tested parameter settings.