Decision tree algorithms have been among the most popular algorithms for
interpretable (transparent) machine learning since the early 1980's. The
problem that has plagued decision tree algorithms since their inception is
their lack of optimality, or lack of guarantees of closeness to optimality:
decision tree algorithms are often greedy or myopic, and sometimes produce
unquestionably suboptimal models. Hardness of decision tree optimization is
both a theoretical and practical obstacle, and even careful mathematical
programming approaches have not been able to solve these problems efficiently.
This work introduces the first practical algorithm for optimal decision trees
for binary variables. The algorithm is a co-design of analytical bounds that
reduce the search space and modern systems techniques, including data
structures and a custom bit-vector library. Our experiments highlight
advantages in scalability, speed, and proof of optimality.

这篇论文介绍了第一种针对二进制变量进行最佳决策树生成的实用算法，该算法结合了分析界限和数据结构等现代技术，在可扩展性、速度和最优性方面具有明显优势。

最优稀疏决策树

Optimal Sparse Decision Trees

In many healthcare settings, intuitive decision rules for risk stratification
can help effective hospital resource allocation. This paper introduces a novel
variant of decision tree algorithms that produces a chain of decisions, not a
general tree. Our algorithm, $\alpha$-Carving Decision Chain (ACDC),
sequentially carves out "pure" subsets of the majority class examples. The
resulting chain of decision rules yields a pure subset of the minority class
examples. Our approach is particularly effective in exploring large and
class-imbalanced health datasets. Moreover, ACDC provides an interactive
interpretation in conjunction with visual performance metrics such as Receiver
Operating Characteristics curve and Lift chart.

该论文介绍了一种新型决策树算法 ACDC，该算法特别适用于探索大规模的、类别不平衡的健康数据集，并且结合 ROC 曲线和提升图等可视化性能指标进行交互式解释。

风险分层的 $α$ 切割决策链

ACDC: $α$-Carving Decision Chain for Risk Stratification

In most practical problems of classifier learning, the training data suffers
from the label noise. Hence, it is important to understand how robust is a
learning algorithm to such label noise. This paper presents some theoretical
analysis to show that many popular decision tree algorithms are robust to
symmetric label noise under large sample size. We also present some sample
complexity results which provide some bounds on the sample size for the
robustness to hold with a high probability. Through extensive simulations we
illustrate this robustness.

本文通过理论分析和大量模拟实验表明：在大样本情况下，许多流行的决策树算法对于对称标签噪声具有鲁棒性，并提供了一些样本复杂度结果来说明其鲁棒性的可靠性。