PreprintCited by 109Explainable Artificial Intelligence (XAI)Data Mining Algorithms and ApplicationsMachine Learning and Data Classification

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 access

Abstract

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

DataCite · 10.48550/arxiv.1704.01701

Cites

36 of 36 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

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?

Citations

Cites

Show all 38 references

Cited by

Sorted by citations

Metadata

Authors
Angelino, E., Larus-Stone, N., Alabi, D., Seltzer, M., & Rudin, C.
Venue
arXiv
Publisher
arXiv
Published
2017
ISSN
2331-8422 (ISSN-L)
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
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