提出高效算法，精准排序决策树特征重要性，解决传统方法误差大问题。
TreeGrad-Ranker: Feature Ranking via $O(L)$-Time Gradients for Decision Trees
- 基于联合优化目标直接计算梯度，实现每叶O(L)时间复杂度
- 实验显示新方法在插入/删除指标上显著优于现有方法
- 适合需要高精度特征解释的机器学习应用，尤其决策树模型
我们重新审视使用概率值（如Shapley和Banzhaf值）对决策树局部预测值进行特征排序。特征排序质量通常通过插入与删除指标评估。经验发现，同时优化这两个指标等价于选择一个子集特征，以最大化局部预测值而最小化其补集。然而，理论上证明概率值一般无法可靠解决该联合优化问题。因此，我们探索直接优化联合目标来生成特征排序。核心是提出TreeGrad，可在含L个叶子的决策树上以O(L)时间计算联合目标多元线性扩展的梯度，这些梯度包含加权Banzhaf值。在此基础上，提出TreeGrad-Ranker，通过聚合梯度并优化联合目标生成排序；以及TreeGrad-Shap，一种数值稳定的Beta Shapley值计算算法（积分参数）。特别地，TreeGrad-Ranker的特征得分满足所有唯一表征概率值的公理，仅不满足线性——而正是线性导致了传统方法的不可靠性。实验表明，计算Shapley值时，Linear TreeShap的数值误差可达TreeGrad-Shap的10^15倍。作为副产品，还开发了TreeProb，将Linear TreeShap推广至支持所有概率值。实验显示，TreeGrad-Ranker在插入与删除指标上均表现显著更优。代码开源：https://github.com/watml/TreeGrad。
原文摘要 · Abstract (English)
We revisit the use of probabilistic values, which include the well-known Shapley and Banzhaf values, to rank features for explaining the local predicted values of decision trees. The quality of feature rankings is typically assessed with the insertion and deletion metrics. Empirically, we observe that co-optimizing these two metrics is closely related to a joint optimization that selects a subset of features to maximize the local predicted value while minimizing it for the complement. However, we theoretically show that probabilistic values are generally unreliable for solving this joint optimization. Therefore, we explore deriving feature rankings by directly optimizing the joint objective. As the backbone, we propose TreeGrad, which computes the gradients of the multilinear extension of the joint objective in $O(L)$ time for decision trees with $L$ leaves; these gradients include weighted Banzhaf values. Building upon TreeGrad, we introduce TreeGrad-Ranker, which aggregates the gradients while optimizing the joint objective to produce feature rankings, and TreeGrad-Shap, a numerically stable algorithm for computing Beta Shapley values with integral parameters. In particular, the feature scores computed by TreeGrad-Ranker satisfy all the axioms uniquely characterizing probabilistic values, except for linearity, which itself leads to the established unreliability. Empirically, we demonstrate that the numerical error of Linear TreeShap can be up to $10^{15}$ times larger than that of TreeGrad-Shap when computing the Shapley value. As a by-product, we also develop TreeProb, which generalizes Linear TreeShap to support all probabilistic values. In our experiments, TreeGrad-Ranker performs significantly better on both insertion and deletion metrics. Our code is available at https://github.com/watml/TreeGrad.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。