# Interpretable multiclass classification by MDL-based rule lists

arXiv: https://arxiv.org/abs/1905.00328 · HTML: https://mlsanity.com/paper/1905.00328/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 May 2019.

## Built on by (most cited first, 16 of 16)

- [First Steps of an Approach to the ARC Challenge based on Descriptive Grid Models and the Minimum Description Length Principle](https://mlsanity.com/paper/2112.00848/) (2021)
- [Label-Descriptive Patterns and Their Application to Characterizing Classification Errors](https://mlsanity.com/paper/2110.09599/) (2021)
- [Truly Unordered Probabilistic Rule Sets for Multi-class Classification](https://mlsanity.com/paper/2206.08804/) (2022)
- [Finding Interpretable Class-Specific Patterns through Efficient Neural Search](https://mlsanity.com/paper/2312.04311/) (2023)
- [Robust subgroup discovery](https://mlsanity.com/paper/2103.13686/) (2021)
- [Rule Generation for Classification: Scalability, Interpretability, and Fairness](https://mlsanity.com/paper/2104.10751/) (2021)
- [Scalable Rule Lists Learning with Sampling](https://mlsanity.com/paper/2406.12803/) (2024)
- [Conditional Density Estimation with Histogram Trees](https://mlsanity.com/paper/2410.11449/) (2024)
- [Interpretable Models Capable of Handling Systematic Missingness in Imbalanced Classes and Heterogeneous Datasets](https://mlsanity.com/paper/2206.02056/) (2022)
- [Probabilistic Truly Unordered Rule Sets](https://mlsanity.com/paper/2401.09918/) (2024)
- [Neuro-Symbolic Rule Lists](https://mlsanity.com/paper/2411.06428/) (2024)
- [Interpretable Machine Learning Classifiers for Brain Tumour Survival Prediction](https://mlsanity.com/paper/2106.09424/) (2021)
- [Data is Moody: Discovering Data Modification Rules from Process Event Logs](https://mlsanity.com/paper/2312.14571/) (2023)
- [MISS: Multiclass Interpretable Scoring Systems](https://mlsanity.com/paper/2401.05069/) (2024)
- [TT-Sparse: Learning Sparse Rule Models with Differentiable Truth Tables](https://mlsanity.com/paper/2603.07606/) (2026)
- [Regional Explanations via Causal Sufficiency and Necessity](https://mlsanity.com/paper/2609.18049/) (2026)

## Abstract (arXiv)

Interpretable classifiers have recently witnessed an increase in attention from the data mining community because they are inherently easier to understand and explain than their more complex counterparts. Examples of interpretable classification models include decision trees, rule sets, and rule lists. Learning such models often involves optimizing hyperparameters, which typically requires substantial amounts of data and may result in relatively large models. In this paper, we consider the problem of learning compact yet accurate probabilistic rule lists for multiclass classification. Specifically, we propose a novel formalization based on probabilistic rule lists and the minimum description length (MDL) principle. This results in virtually parameter-free model selection that naturally allows to trade-off model complexity with goodness of fit, by which overfitting and the need for hyperparameter tuning are effectively avoided. Finally, we introduce the Classy algorithm, which greedily finds rule lists according to the proposed criterion. We empirically demonstrate that Classy selects small probabilistic rule lists that outperform state-of-the-art classifiers when it comes to the combination of predictive performance and interpretability. We show that Classy is insensitive to its only parameter, i.e., the candidate set, and that compression on the training set correlates with classification performance, validating our MDL-based selection criterion.