Decision Tree and Bagging

本文将简要的介绍决策树这一简单的模型，主要是说明熵度量的合理性；以及集成学习中的 Bagging 方法，并引出与决策树结合的随机森林。

特别的，本人本来希望将集成学习作为专题介绍，然而由于 boosting 这一方法占用的篇幅太大，后来决定单独介绍 boosting ，因此将 bagging 划分到了决策树部分。

Decision Tree

• 决策树是一种相对简单（并且弱）的模型，以至于光靠名字就基本可以知道其本质上做了什么。具体的，不同于先前介绍的大多数模型，决策树是天然非线性的。以下我们从分类问题引入决策树。

The Case of Classification

• 给定数据集 ，其中 。我们希望利用某种树形结构对 进行层层分划，直到叶子节点为止，并利用叶子节点处的子集为该点规定某一类别。在预测时，我们将数据 输入这一树形结构，根据每一点处的分类原则向下转移，直到抵达某一叶子。此时 经过了一条从根到叶子的路径，到达了 对应的最细分的节点，该点规定的类别即为模型输出的预测 。

  现在我们关注决策树的实现细节。首先，决策树在非叶节点处的分划形如：选择特征空间 的某一维 ，并选择某一阈值 。假定当前点处的子集为 ，则按照规则： 得到 的分划 ，将其作为当前节点的左右儿子，并递归的进行操作。最后我们按照一定的规则停止分划，得到叶子节点，并将其中数据点占比最大的类别规定为这一叶子的类，这等价于在叶子内的有限信息上做 MLE 。

  因此，首要的问题是如何选择最优的 。常见的 ERM 在此处不再可行，因为这一优化问题要在离散函数空间上进行，从而无法方便的做梯度下降。¹对此，解决方式是基于树结构做贪心，这要求使用某种方式衡量单步分划的优劣。一般的框架应是，对于某一节点，该处的子集为 ，定义此处关于 的收益函数为 ，则我们希望解如下的优化问题： 来确定 的取值。在实现中，数据集大小是有限的，这意味着固定 时 的敏感位置只有 个。出于稳健性的考虑，一般会将数据点 按照 排序，选择相邻两点 值的平均作为候选的 。若给定 时 可以在 时间内计算，则考虑排序复杂度时决策树的构建复杂度一般是 的，其中 为树高，期待为 级别。

• 现在的主要问题是如何选择 。对于分类问题，常见的选择是熵度量²，即对于 ，定义熵 代表 中元素服从均匀分布时标签 的信息熵。此时我们将分划后熵的减少量视作信息的收益： 此处简单的看法是利用“信息收益”或“混乱度降低”的说辞来解释上式的含义，但我们对此并不满意。具体的，考虑如下的概率空间：使用随机变量 代表标签 ，将决策树的节点从 开始标号到 ，对于节点 处的分划 ，定义随机变量 为 。此时决策树可以看作随机变量 所刻画的随机过程 。 定义随机变量 代表落到节点 中的数据点的标签，则式 可以看作优化条件熵 ，进一步看作贪心的优化 。对于标签 ，令 代表 的最大概率对应标签， ，则容易看出： 则利用决策树的叶子做 MLE 的正确率具备条件熵的界： 这样就说明了用贪心去优化 对于我们最终关注的分类正确率来说至少是有道理的，尽管这可能是一个比较糙的界。另外此处我们讨论的是训练误差，而非泛化误差，尽管此中的分析应该是相似的。

The Case of Regression

• 在回归任务下决策树的理论框架和先前的分类任务基本是一致的，唯一的区别是最后在叶子节点处的预测采用了该点处标签的期望。此时分划时的度量自然可以采用标签的方差，合理性的分析是显然的，这里就不赘述了。

Regularization

• 决策树实际上是一类相对弱的模型，其是非参数化的，且在深度大时很容易过拟合。因此，我们很少使用单一的决策树，并且在使用时往往要做强正则化。可选的方案包括：限制树深度、限制节点总数、限制数据点过少的分划、在收益较小时不做分划、建树后自底向上剪枝、等等。此处并无兴趣逐一介绍每种正则化方案，尽管其中的一部分确实是不理想的。（例如限制增益最小值往往不是一个好的策略。）
• 特别的，决策树本身的结构决定其不需要特征映射也可以方便的处理标签类数据（对标签类做分划），这使得决策树非常适用于处理表格类数据。然而当标签种类过多时，决策树的效率可能过低（此时需枚举指数种可能的分划），因此可能需要其它启发性的划分方式。

Ensemble Learning

• 集成学习的思想是通过综合一系列相对弱但易于训练的模型来提高模型的整体能力。由于决策树恰好符合这种要求，因此我们往往选择其作为集成学习的基模型。从模型误差的偏差-方差分解视角来看，我们希望从偏差和方差两个维度来控制误差，从这两个方面入手可以得到两类集成方式，这便是 boosting 和 bagging ，我们从后者讲起。

Bagging

• Bagging 是一类直观的思路。假设我们有了一个偏差好但方差大的模型，这说明该模型拟合能力强但对训练集敏感。一个简单的思路是通过对独立同分布的随机试验做平均来减小方差。在 PAC 假设和 MSE 度量下，假设对于同一模型做 次独立试验，也就是从数据的真实分布 中独立取样 个大小为 的数据集 做平均，得到假设 ，记期望预测 （此处的期望是对数据集做的），从而平均后的结果为： 显然这是对 的无偏估计，且其方差满足： 因此理想情况下随着平均次数的增加，我们可以严格的控制方差而不改变偏差。然而实践中我们很难从 中直接采样，而只有手头的训练集 。一个折衷的办法是，每次采样数据集 时，在 上做 次独立均匀随机的数据点采样，称作自助采样（bootstrap sample）。

• 现在我们希望考察这一方式的优劣，对此，有两种看法：

  1. 直接考察 bagging 得到模型的偏差与方差。即固定概率空间 使得 的每个数据点独立同分布且服从 ，再从 中做 次自助采样得到 。
  2. 考察固定 时 bagging 得到模型相比原先单一模型的偏差与方差。即固定概率空间 使得对于给定的 直接从中做 次自助采样得到 。

  这里我们关注第一种方式。先考察 的分布，显然 中的单一数据点仍然服从分布 ，然而容易验证 的数据点之间并不独立（用熵方法即可），这说明 并不与 同分布。记 ，从而 bagging 模型： 是对 而非 的无偏估计。由于理论上没有什么对于 的保障，我们倾向于认为（在实践中） 会导致偏差略大。

  现在考察方差，有： 注意到任意两个不同假设之间的相关性显然是相同的，记其平均成对相关系数为 ，则协方差为 。这样： 由于自助采样的数据有重叠，假设 ；考虑到假设之间不会完全相同，应有 。从而给定 时，便有系数 ，这便说明了 bagging 确实可以优化单一模型自助采样的方差。然而一个重要的问题是原模型的方差 是不做自助采样的，我们并不能平凡的断言在某种尺度上自助采样不改变模型方差。实际上我也不知道此中的数学原理如何严格说明，而只好认为其是经验上的假设了。那么在假设自助采样方差和原先的方差相差不远时，便可以说明 bagging 的确优化了方差。

• 最后，一个有趣的观点是每一次自助采样并不会利用 中的全部数据。更确切的说，对于单个数据点，其在 次抽选中被抽中至少一次的概率是： 这说明单次自助采样中大概只有 63.2% 的数据被抽中，这看起来使得有效数据更少，但也可以避免模型假设依赖于一小部分数据。

Random Forest

• 随机森林是 bagging 在选择决策树作为基模型时的进一步优化。更确切的说，深度较大的决策树恰为偏差小而方差大的模型，因而适于 bagging 。而随机森林则在此的基础上，要求决策树在每一次分划时只能在一部分特征维上考虑，例如固定超参数 ，每一次分划时在均匀随机选出的 个特征维上优化。这样做的好处是进一步减小了模型之间的相关性，也可以看作某种正则化方式。

---

1. 更确切的说，决策树的 ERM 似乎是 NPC 。↩︎

2. 也可以直接度量分类错误率，但是熵度量更敏感一些。↩︎