This paper proposes a new algorithm for learning accurate tree-based models
while ensuring the existence of recourse actions. Algorithmic Recourse (AR)
aims to provide a recourse action for altering the undesired prediction result
given by a model. Typical AR methods provide a reasonable action by solving an
optimization task of minimizing the required effort among executable actions.
In practice, however, such actions do not always exist for models optimized
only for predictive performance. To alleviate this issue, we formulate the task
of learning an accurate classification tree under the constraint of ensuring
the existence of reasonable actions for as many instances as possible. Then, we
propose an efficient top-down greedy algorithm by leveraging the adversarial
training techniques. We also show that our proposed algorithm can be applied to
the random forest, which is known as a popular framework for learning tree
ensembles. Experimental results demonstrated that our method successfully
provided reasonable actions to more instances than the baselines without
significantly degrading accuracy and computational efficiency.

该论文提出了一种新算法，用于学习准确的基于树的模型，同时确保存在补救措施行动。

使用算法回溯学习决策树和随机森林

Learning Decision Trees and Forests with Algorithmic Recourse

The Classification Tree (CT) is one of the most common models in
interpretable machine learning. Although such models are usually built with
greedy strategies, in recent years, thanks to remarkable advances in
Mixer-Integer Programming (MIP) solvers, several exact formulations of the
learning problem have been developed. In this paper, we argue that some of the
most relevant ones among these training models can be encapsulated within a
general framework, whose instances are shaped by the specification of loss
functions and regularizers. Next, we introduce a novel realization of this
framework: specifically, we consider the logistic loss, handled in the MIP
setting by a linear piece-wise approximation, and couple it with
$\ell_1$-regularization terms. The resulting Optimal Logistic Tree model
numerically proves to be able to induce trees with enhanced interpretability
features and competitive generalization capabilities, compared to the
state-of-the-art MIP-based approaches.

本研究提出了一个通用框架并构建了一种新型的最优逻辑树模型，该模型采用线性分段逼近法处理逻辑损失，并与 L1 正则项耦合，证明其能够诱导出具有更好可解释性和竞争性推广能力的树状模型，相对于现有的 MIP-based 方法。

损失最优分类树：一个广义框架和逻辑回归情形

Loss-Optimal Classification Trees: A Generalized Framework and the  Logistic Case

We consider the problem of \emph{pruning} a classification tree, that is,
selecting a suitable subtree that balances bias and variance, in common
situations with inhomogeneous training data. Namely, assuming access to mostly
data from a distribution $P_{X, Y}$, but little data from a desired
distribution $Q_{X, Y}$ with different $X$-marginals, we present the first
efficient procedure for optimal pruning in such situations, when
cross-validation and other penalized variants are grossly inadequate.
Optimality is derived with respect to a notion of \emph{average discrepancy}
$P_{X} \to Q_{X}$ (averaged over $X$ space) which significantly relaxes a
recent notion -- termed \emph{transfer-exponent} -- shown to tightly capture
the limits of classification under such a distribution shift. Our relaxed
notion can be viewed as a measure of \emph{relative dimension} between
distributions, as it relates to existing notions of information such as the
Minkowski and Renyi dimensions.

本研究讨论了在不同分布的训练数据中，选择一个平衡偏差和方差的适当子树的剪枝问题，并提出了首个在这种情况下进行最优剪枝的高效程序。

协变量转移下的分类树剪枝

Classification Tree Pruning Under Covariate Shift

Despite the previous success of object analysis, detecting and segmenting a
large number of object categories with a long-tailed data distribution remains
a challenging problem and is less investigated. For a large-vocabulary
classifier, the chance of obtaining noisy logits is much higher, which can
easily lead to a wrong recognition. In this paper, we exploit prior knowledge
of the relations among object categories to cluster fine-grained classes into
coarser parent classes, and construct a classification tree that is responsible
for parsing an object instance into a fine-grained category via its parent
class. In the classification tree, as the number of parent class nodes are
significantly less, their logits are less noisy and can be utilized to suppress
the wrong/noisy logits existed in the fine-grained class nodes. As the way to
construct the parent class is not unique, we further build multiple trees to
form a classification forest where each tree contributes its vote to the
fine-grained classification. To alleviate the imbalanced learning caused by the
long-tail phenomena, we propose a simple yet effective resampling method, NMS
Resampling, to re-balance the data distribution. Our method, termed as Forest
R-CNN, can serve as a plug-and-play module being applied to most object
recognition models for recognizing more than 1000 categories. Extensive
experiments are performed on the large vocabulary dataset LVIS. Compared with
the Mask R-CNN baseline, the Forest R-CNN significantly boosts the performance
with 11.5% and 3.9% AP improvements on the rare categories and overall
categories, respectively. Moreover, we achieve state-of-the-art results on the
LVIS dataset. Code is available at this https URL

本研究提出了一种基于分类树和分类森林的方法 Forest R-CNN，通过利用对象类别之间的关系来构建分类树，re-balance 数据分布，以提高在大词汇量数据集 LVIS 上识别 1000 多个类别的目标识别模型的性能。实验表明，此方法在稀有类别和整体类别方面明显提高了性能，并在 LVIS 数据集上实现了最先进的结果。