The DOI matches its DataCite record; 36 of the 38 references it cites were found in a registry or an index.
Learning Certifiably Optimal Rule Lists for Categorical Data
Open accessAbstract
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.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“In fact, quite a lot of effort has been made by scientists to understand how COMPAS depends on important variables like race and age, without a lot of success (59, 60).”
From Interpretable algorithmic forensics (2023) · cites this paper as [60]
In the citing paper
“For example, researchers found that a simple model relying on age, gender, and prior criminal record was just as predictable as the COMPAS algorithm, which is proprietary and could rely on up to 137 inputs (32).”
From Interpretable algorithmic forensics (2023) · cites this paper as [32]
Citations
Cites
Classification and Regression Trees.
Ryzin, J. V., Breiman, L., Friedman, J. H., Olshen, R. A., & Stone, C. J. (1986) · Journal of the American Statistical Association · doi:10.2307/2288003 · Cited by 21,030
Cohen, W. W. (1995) · Elsevier eBooks · doi:10.1016/b978-1-55860-377-6.50023-2 · Cited by 3,890
Clark, P. A., & Niblett, T. (1989) · Machine Learning · doi:10.1023/a:1022641700528 · Cited by 2,267
European Union Regulations on Algorithmic Decision Making and a “Right to Explanation”
Goodman, B., & Flaxman, S. (2017) · AI Magazine · doi:10.1609/aimag.v38i3.2741 · Cited by 2,131 · cited 2×
“There are now regulations on algorithmic decision-making in the European Union on the “right to an explanation” [19] that would legally require interpretability of predictions.”
BackgroundThe robust beauty of improper linear models in decision making.
Dawes, R. M. (1979) · American Psychologist · doi:10.1037/0003-066x.34.7.571 · Cited by 2,046
Very Simple Classification Rules Perform Well on Most Commonly Used Datasets
Holte, R. C. (1993) · Machine Learning · doi:10.1023/a:1022631118932 · Cited by 1,800
Generating Accurate Rule Sets Without Global Optimization
Frank, E., & Witten, I. H. (1998) · Research Commons (University of Waikato) · doi:10.5555/645527.657305 · Cited by 1,297
The accuracy, fairness, and limits of predicting recidivism
Dressel, J., & Farid, H. (2018) · Science Advances · doi:10.1126/sciadv.aao5580 · Cited by 1,071
Rivest, R. L. (1987) · Machine Learning · doi:10.1023/a:1022607331053 · Cited by 894
BART: Bayesian Additive Regression Trees
Chipman, H., George, E. I., & McCulloch, R. E. (2006) · ScholarlyCommons (University of Pennsylvania) · Cited by 889
CPAR: Classification based on Predictive Association Rules
Yin, X., & Han, J. (2003) · Proceedings of the 2003 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972733.40 · Cited by 833
Letham, B., Rudin, C., McCormick, T. H., & Madigan, D. (2015) · The Annals of Applied Statistics · doi:10.1214/15-aoas848 · Cited by 766
Self-citationChipman, H., George, E. I., & McCulloch, R. E. (1998) · Journal of the American Statistical Association · doi:10.1080/01621459.1998.10473750 · Cited by 750
Comprehensible classification models
Freitas, A. A. (2014) · ACM SIGKDD Explorations Newsletter · doi:10.1145/2594473.2594475 · Cited by 575
Li, O., Liu, H., Chen, C., & Rudin, C. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11771 · Cited by 541
Self-citationHuysmans, J., Dejaeger, K., Mues, C., Vanthienen, J., & Baesens, B. (2011) · Decision Support Systems · doi:10.1016/j.dss.2010.12.003 · Cited by 425
Supersparse linear integer models for optimized medical scoring systems
Ustun, B., & Rudin, C. D. (2015) · Machine Learning · doi:10.1007/s10994-015-5528-6 · Cited by 316
Self-citationPrecinct or prejudice? Understanding racial disparities in New York City’s stop-and-frisk policy
Goel, S., Rao, J. M., & Shroff, R. (2016) · The Annals of Applied Statistics · doi:10.1214/15-aoas897 · Cited by 285
(2012) · Cited by 253
Interpretable classification models for recidivism prediction
Zeng, J., Ustun, B., & Rudin, C. (2017) · Journal of the Royal Statistical Society Series A: Statistics in Society · doi:10.1111/rssa.12227 · Cited by 220
Self-citationChipman, H., George, E. I., & McCulloch, R. E. (2002) · Machine Learning · doi:10.1023/a:1013916107446 · Cited by 177
(2015) · International Conference on Artificial Intelligence and Statistics · Cited by 162
Self-citationScalable Bayesian Rule ListsPreprint
Yang, H., Rudin, C. D., & Seltzer, M. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1602.08610 · Cited by 138
Self-citationTollenaar, N., & van der Heijden, P. G. M. (2012) · Journal of the Royal Statistical Society Series A (Statistics in Society) · doi:10.1111/j.1467-985x.2012.01056.x · Cited by 133
Stefan Rüping, A. (2006) · Technische Universität Dortmund Eldorado (Technische Universität Dortmund) · doi:10.17877/de290r-8863 · Cited by 70
Ustun, B., & Rudin, C. D. (2017) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3097983.3098161 · Cited by 47
Self-citationWang, T., Rudin, C., Doshi-Velez, F., Liu, Y.-M., Klampfl, E., & MacNeille, P. (2015) · arXiv.org · doi:10.48550/arxiv.1504.07614 · Cited by 41
Self-citationBox drawings for learning with imbalanced data
Goh, S. T., & Rudin, C. D. (2014) · ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/2623330.2623648 · Cited by 37
Self-citationEfficient algorithms for constructing decision trees with constraints
Garofalakis, M., Hyun, D.-J., Rastogi, R. R., & Shim, K. (2000) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/347090.347163 · Cited by 37
An Optimization Approach to Learning Falling Rule ListsPreprint
Chen, C., & Rudin, C. D. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.02572 · Cited by 26
Self-citationIs There Any Logic to Using Logit
Bushway, S. D. (2013) · Criminology & Public Policy · doi:10.1111/1745-9133.12059 · Cited by 20
Structure of association rule classifiers: a review
Vanhoof, K., & Depaire, B. (2010) · IEEE International Conference on Intelligent Systems and Knowledge Engineering · doi:10.1109/iske.2010.5680784 · Cited by 16
Causal Falling Rule ListsPreprint
Wang, F., & Rudin, C. D. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1510.05189 · Cited by 15
Self-citationA Fast Way to Produce Optimal Fixed-Depth Decision Trees.
Farhangfar, A., Greiner, R., & Zinkevich, M. (2008) · Cited by 7
Hybrid Decision Making: When Interpretable Models Collaborate With Black-Box Models.Preprint
Wang, T. (2018) · arXiv (Cornell University) · Cited by 6
A Minimax Surrogate Loss Approach to Conditional Difference EstimationPreprint
Goh, S. T., & Rudin, C. D. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1803.03769 · Cited by 2
Self-citation
Cited by
Sorted by citations
Ali, S., Abuhmed, T., El-Sappagh, S., Muhammad, K., Alonso-Moral, J. M., Confalonieri, R., Guidotti, R., Del Ser, J., Díaz-Rodríguez, N., & Herrera, F. (2023) · Information Fusion · doi:10.1016/j.inffus.2023.101805 · Cited by 1,762
The accuracy, fairness, and limits of predicting recidivism
Dressel, J., & Farid, H. (2018) · Science Advances · doi:10.1126/sciadv.aao5580 · Cited by 1,071
Interpretable machine learning: Fundamental principles and 10 grand challenges
Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L., & Zhong, C. (2022) · Statistics Surveys · doi:10.1214/21-ss133 · Cited by 958
Self-citationOpening the black box: the promise and limitations of explainable machine learning in cardiology
Petch, J., Di, S., & Nelson, W. (2022) · Canadian Journal of Cardiology · doi:10.1016/j.cjca.2021.09.004 · Cited by 552
Rudin, C., & Radin, J. (2019) · Harvard Data Science Review · doi:10.1162/99608f92.5a8a3a3d · Cited by 432
Self-citation
Metadata
- Authors
- Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., & Rudin, C.
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2017
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 1704.01701
- OpenAlex
- W2606882704
- Cited by
- 108
- References
- 38
- Citations by year
- 2026: 1 · 2025: 7 · 2024: 9 · 2023: 26 · 2022: 23 · 2021: 18 · 2020: 11 · 2019: 8 · 2018: 3 · 2017: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Explainable Artificial Intelligence (XAI)
- Physical Sciences › Computer Science › Information Systems › Data Mining Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
- Keywords
- categorical data, discrete optimization, optimality certificates, model interpretability, decision tree, Broward County
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
