Decision Tree Learning on Product Spaces

技术摘要：产品空间上的决策树学习

问题陈述
决策树学习是机器学习的基石，因其可解释性和实证成功而备受推崇。标准的实践方法是自顶向下的贪婪启发式算法，该算法递归地根据最“有影响力”的变量（通常通过熵或基尼指数等不纯度减少量来衡量）对节点进行分割。尽管该方法在实证上有效，但对其启发式方法的理论理解一直有限。此前严格的保证（如 Blanc 等人于 ITCS 2020 年提出的成果）仅限于布尔超立方体上的均匀分布。这一假设无法捕捉现实世界数据，因为其中的特征通常遵循异质的、非均匀的产品分布。此外，许多理论工作提出了复杂的非贪婪算法（例如自底向上或暴力搜索），这些算法与实践实现相去甚远，导致理论与实践之间存在差距。

方法论
作者将自顶向下贪婪启发式算法的理论分析扩展到了任意产品分布。该设定涉及在产品分布 $\mu = \mu_1 \times \dots \times \mu_n$ 下学习布尔函数 $f: \{0, 1\}^n \to \{\pm 1\}$，其中每一位为 1 的概率为 $p_i$。

所分析的核心算法是BuildTopDownDT，这是对标准贪婪方法的正式化：

1. 初始化：从一个叶子节点开始。
2. 评分：在每一步，对当前树中的每个叶子节点 $l$ 进行评分。评分定义为到达该叶子的概率质量（$p_l$）乘以该叶子处子函数上任意变量的最大影响力（$\max_i \text{Inf}_i(f_l)$）。
3. 分割：选择得分最高的叶子节点，并在其最具影响力的变量上进行分割。
4. 终止：重复上述过程，直到树的 $f$-完成（即给叶子节点分配多数标签）成为 $f$ 的 $\epsilon$-近似。

为了分析该算法，作者引入了一个称为裸树（无标签树）成本的势函数，定义为每个叶子处子函数的总影响力之和，并以到达该叶子的概率作为权重。他们建立了该成本、近似误差以及最优树的结构属性（最大深度 $D_{\text{opt}}$ 和平均深度 $\Delta_{\text{opt}}$）之间的关系。

主要贡献

1. 推广至产品分布：本文首次为任意产品分布下的自顶向下贪婪启发式算法提供了严格的性能保证，消除了先前工作中对均匀分布假设的限制。
2. 改进的规模界限：主要理论结果（定理 1.1）指出，对于任何可由大小为 $s$、最大深度为 $D_{\text{opt}}$、平均深度为 $\Delta_{\text{opt}}$ 的最优树计算的函数，贪婪启发式算法构建的 $\epsilon$-近似树的大小至多为：
   $$\max \left( \left( \frac{e \cdot \Delta_{\text{opt}}}{\epsilon D_{\text{opt}}} \right)^{\Delta_{\text{opt}} D_{\text{opt}}}, e^{\Delta_{\text{opt}} D_{\text{opt}}} \right)$$
   • 平衡情形：对于 $D_{\text{opt}} = \Delta_{\text{opt}} = \log s$ 的满二叉树，该界限简化为 $s^{O(\log s \cdot \log(e/\epsilon))}$。这是一个拟多项式界限，优于 Blanc 等人（2020）建立的界限，并且适用于更广泛的分布类。
   • 路径状情形：对于高度不平衡的树（例如路径树），$D_{\text{opt}}$ 可能为 $O(n)$，而 $\Delta_{\text{opt}}$ 仍保持为一个小常数。对 $\Delta_{\text{opt}}$ 和 $D_{\text{opt}}$ 的混合依赖产生的界限比仅依赖于 $D_{\text{opt}}$ 的界限指数级更紧（前者为 $e^{O(n)}$，而后者为 $e^{O(n^2)}$）。
3. 无参数的实践实现：作者提出了算法 2，这是该启发式算法的一种完全无参数的实践实现。与先前假设已知最优树大小（$s$）或深度的理论分析不同，该算法依赖于基于样本的评分和误差估计。它自适应地增加样本量以维持统计置信度，而无需预先了解目标函数的复杂度。
4. 对估计的鲁棒性：理论保证表明，即使算法选择的叶子节点的得分仅为最大可能得分的一个常数分数（例如 $1/4$），保证依然成立，从而适应了基于样本估计中固有的噪声。

结果

• 理论方面：本文证明了贪婪启发式算法在平衡情形下实现了拟多项式规模界限，并且在非平衡情形下，相较于仅依赖于最大深度的界限，实现了显著更优的界限。该分析依赖于新的引理，将树的成本与其误差联系起来，并建立了所选叶子节点得分相对于当前误差和树深度的下界。
• 实证方面：作者在均匀、中等偏差和重偏差等不同产品分布下，对平衡和非平衡决策树目标上的无参数算法（算法 2）进行了实证评估。结果证实，恢复的树大小与真实目标非常接近，且远优于理论界限，样本复杂度随维度和 $1/\epsilon$ 呈多项式增长。

意义与主张
本文声称弥合了决策树学习的理论分析与其实际应用之间的差距。通过分析经典的、简单的贪婪启发式算法（用于 ID3、C4.5、CART），而非复杂的非贪婪变体，作者为这些广泛使用的算法的强大实证性能提供了严格的理论依据。

其意义在于：

• 现实性：从均匀分布转向任意产品分布，后者能更好地模拟现实世界数据。
• 实用性：提供了一种无需预先知道最优树大小或深度的无参数算法，使理论保证可直接应用于现实场景。
• 紧密性：证明了平均深度和最大深度的混合依赖关系能为不平衡树（决策树中的常见结构）产生严格更紧的界限。

作者承认了局限性，指出其分析侧重于未剪枝的树（因为关于严格剪枝的分析很少），且当前证明依赖于离散产品空间。他们指出，将分析扩展到连续特征和基于阈值的分割是未来的方向。此外，他们指出，尽管其界限是拟多项式的，但决策树学习存在超多项式下界，这表明对最优大小 $s$ 的某种依赖是不可避免的。