Learning interpretable models has become a major focus of machine learning
research, given the increasing prominence of machine learning in socially
important decision-making. Among interpretable models, rule lists are among the
best-known and easily interpretable ones. However, finding optimal rule lists
is computationally challenging, and current approaches are impractical for
large datasets.
We present a novel and scalable approach to learn nearly optimal rule lists
from large datasets. Our algorithm uses sampling to efficiently obtain an
approximation of the optimal rule list with rigorous guarantees on the quality
of the approximation. In particular, our algorithm guarantees to find a rule
list with accuracy very close to the optimal rule list when a rule list with
high accuracy exists. Our algorithm builds on the VC-dimension of rule lists,
for which we prove novel upper and lower bounds. Our experimental evaluation on
large datasets shows that our algorithm identifies nearly optimal rule lists
with a speed-up up to two orders of magnitude over state-of-the-art exact
approaches. Moreover, our algorithm is as fast as, and sometimes faster than,
recent heuristic approaches, while reporting higher quality rule lists. In
addition, the rules reported by our algorithm are more similar to the rules in
the optimal rule list than the rules from heuristic approaches.

从大数据集中学习近乎最优的规则列表的一种新颖和可扩展的方法，使用采样以有效获得近似最优规则列表，并在质量上做出保证，速度比精确方法快两个数量级，并且与启发式方法相比更高质量的规则列表。

可扩展的采样式规则列表学习

Scalable Rule Lists Learning with Sampling

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.

本文介绍了一种基于概率规则列表和最小描述长度原则的模型选择方法，该方法可以在减小模型复杂度与保持良好拟合度之间进行折衷。同时，介绍了 Classy 算法，该算法针对多类别分类问题，选择小的概率规则列表，实现了良好的性能和可解释性。

基于 MDL 的规则列表的可解释多分类

Interpretable multiclass classification by MDL-based rule lists

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.

本文提出了一种基于离散优化的过程，用于构建基于分类特征空间的规则列表，并且通过算法边界、高效数据结构和计算复用来获得数倍的时间加速和大幅度降低的内存消耗。其结果表明，通过本方法可以在几秒钟内构建出比 Broward County，Florida 的数据上的 COMPAS 专有风险预测工具准确性近似的解释性优化规则列表，这是一种新的解释性建模决策树方法的替代方案。