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

Learning Certifiably Optimal Rule Lists for Categorical Data

Open access
Angelino, Elaine, Larus-Stone, Nicholas, Alabi, Daniel, Seltzer, Margo, Rudin, Cynthia·2017·arXiv

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.

Integrity signals

Registry

DataCite · 10.48550/arxiv.1704.01701

Cites

37 of 37 references verified0 citation errors · 0 not checkable

Statistics

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

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?

  • A simple model relying on age, gender, and prior criminal record was just as predictable as the COMPAS algorithm.

    “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]

Cites

Flagged first, then by citations

1 of the 38 references couldn’t be matched to a known paper.

Cited by

Sorted by citations

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