Behrouz Ali, Lécuyer Mathias, Rudin Cynthia, Seltzer Margo
University of British Columbia Vancouver, British Columbia, Canada.
Duke University Durham, North Carolina, USA.
CEUR Workshop Proc. 2022 Oct;3318.
Sparse decision trees are one of the most common forms of interpretable models. While recent advances have produced algorithms that fully optimize sparse decision trees for , that work does not address , because the algorithms cannot handle weighted data samples. Specifically, they rely on the discreteness of the loss function, which means that real-valued weights cannot be directly used. For example, none of the existing techniques produce policies that incorporate inverse propensity weighting on individual data points. We present three algorithms for efficient sparse weighted decision tree optimization. The first approach directly optimizes the weighted loss function; however, it tends to be computationally inefficient for large datasets. Our second approach, which scales more efficiently, transforms weights to integer values and uses data duplication to transform the weighted decision tree optimization problem into an unweighted (but larger) counterpart. Our third algorithm, which scales to much larger datasets, uses a randomized procedure that samples each data point with a probability proportional to its weight. We present theoretical bounds on the error of the two fast methods and show experimentally that these methods can be two orders of magnitude faster than the direct optimization of the weighted loss, without losing significant accuracy.
稀疏决策树是可解释模型最常见的形式之一。虽然最近的进展产生了一些算法，这些算法可以针对[具体目标]对稀疏决策树进行完全优化，但这项工作并未解决[具体问题]，因为这些算法无法处理加权数据样本。具体来说，它们依赖于损失函数的离散性，这意味着不能直接使用实值权重。例如，现有的技术都没有产生能在单个数据点上纳入逆倾向加权的策略。我们提出了三种用于高效稀疏加权决策树优化的算法。第一种方法直接优化加权损失函数；然而，对于大型数据集，它在计算上往往效率低下。我们的第二种方法扩展效率更高，它将权重转换为整数值，并使用数据复制将加权决策树优化问题转化为一个无加权（但更大）的对应问题。我们的第三种算法可以扩展到更大的数据集，它使用一种随机过程，以与其权重成比例的概率对每个数据点进行采样。我们给出了两种快速方法误差的理论界限，并通过实验表明，这些方法比直接优化加权损失快两个数量级，且不会损失显著的准确性。
