mlsanityData to 7 Oct 2026

Learning Certifiably Optimal Rule Lists for Categorical Data

arXiv 1704.01701 ↗First posted 6 Apr 2017stat.ML cs.LGcited by 50

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 50 papers in the map (data through 7 Oct 2026). First posted on arXiv 6 Apr 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 18; 2023: 9; 2024: 2; 2025: 2; 2026: 2.

50 papers.

Sort:

By area:

  1. 2021Interpretable Machine Learning: Fundamental Principles and 10 Grand Challengescited by 364
  2. 2022TalkToModel: Explaining Machine Learning Models with Interactive Natural Language Conversationscited by 65
  3. 2022Leveraging Explanations in Interactive Machine Learning: An Overviewcited by 52
  4. 2021Entropy-based Logic Explanations of Neural Networkscited by 51
  5. 2021GLocalX -- From Local to Global Explanations of Black Box AI Modelscited by 48
  6. 2022Logic-Based Explainability in Machine Learningcited by 47
  7. 2021SAT-Based Rigorous Explanations for Decision Listscited by 40
  8. 2022Augmenting Interpretable Models with LLMs during Trainingcited by 36
  9. 2023A Path to Simpler Models Starts With Noisecited by 33
  10. 2021Characterizing the risk of fairwashingcited by 21
  11. 2022Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Featurescited by 19
  12. 2021FADE: FAir Double Ensemble Learning for Observable and Counterfactual Outcomescited by 13
38 more
  1. 2021The Impact of Algorithmic Risk Assessments on Human Predictions and its Analysis via Crowdsourcing Studiescited by 13
  2. 2022Learning Interpretable Decision Rule Sets: A Submodular Optimization Approachcited by 13
  3. 2022Self-explaining deep models with logic rule reasoningcited by 13
  4. 2022Fast Interpretable Greedy-Tree Sumscited by 12
  5. 2022Computing the Collection of Good Models for Rule Listscited by 12
  6. 2022Learning Interpretable, High-Performing Policies for Autonomous Drivingcited by 11
  7. 2021Interpretable and Fair Boolean Rule Sets via Column Generationcited by 10
  8. 2024Efficient Exploration of the Rashomon Set of Rule Set Modelscited by 10
  9. 2022Differentiable Rule Induction with Learned Relational Featurescited by 8
  10. 2021Explainable AI and Adoption of Financial Algorithmic Advisors: an Experimental Studycited by 7
  11. 2021A Scalable Two Stage Approach to Computing Optimal Decision Setscited by 7
  12. 2023Probabilistic Dataset Reconstruction from Interpretable Modelscited by 7
  13. 2021Better Short than Greedy: Interpretable Models through Optimal Rule Boostingcited by 6
  14. 2022Explainable Global Fairness Verification of Tree-Based Classifierscited by 5
  15. 2021Robust subgroup discoverycited by 4
  16. 2021Fair Decision Rules for Binary Classificationcited by 4
  17. 2022Mixed integer linear optimization formulations for learning optimal binary classification treescited by 4
  18. 2022A Scalable, Interpretable, Verifiable & Differentiable Logic Gate Convolutional Neural Network Architecture From Truth Tablescited by 4
  19. 2021Quantifying Explainability in NLP and Analyzing Algorithms for Performance-Explainability Tradeoffcited by 3
  20. 2022bsnsing: A decision tree induction method based on recursive optimal boolean rule compositioncited by 3
  21. 2023Explainable AI using expressive Boolean formulascited by 2
  22. 2023Feature Importance Measurement based on Decision Tree Samplingcited by 2
  23. 2026Neuron-Anchored Rule Extraction for Large Language Models via Contrastive Hierarchical Ablationcited by 2
  24. 2021Human strategic decision making in parametrized gamescited by 1
  25. 2022Fast Optimization of Weighted Sparse Decision Trees for use in Optimal Treatment Regimes and Optimal Policy Designcited by 1
  26. 2022Learning to Advise Humans in High-Stakes Settingscited by 1
  27. 2022A Seven-Layer Model for Standardising AI Fairness Assessmentcited by 1
  28. 2023Neural Network-Based Rule Models With Truth Tablescited by 1
  29. 2021Distilling Interpretable Models into Human-Readable Codecited by 0
  30. 2021Information-theoretic Evolution of Model Agnostic Global Explanationscited by 0
  31. 2023Practical Policy Optimization with Personalized Experimentationcited by 0
  32. 2023Learning Locally Interpretable Rule Ensemblecited by 0
  33. 2023CONFIDERAI: a novel CONFormal Interpretable-by-Design score function for Explainable and Reliable Artificial Intelligencecited by 0
  34. 2023Is Machine Learning Unsafe and Irresponsible in Social Sciences? Paradoxes and Reconsidering from Recidivism Prediction Taskscited by 0
  35. 2024Smooth Sensitivity for Learning Differentially-Private yet Accurate Rule Listscited by 0
  36. 2025It's 2025 -- Narrative Learning is the new baseline to beat for explainable machine learningcited by 0
  37. 2025Additive Large Language Models for Semi-Structured Textcited by 0
  38. 2026Rules or Weights? Comparing User Understanding of Explainable AI Techniques with the Cognitive XAI-Adaptive Modelcited by 0