机器学习笔记：集成学习

2020-04-25

关键词：Boosting、Bagging、Adaboost、随机森林、GBDT、XGBoost、LightGBM

集成学习

什么是集成学习（Ensemble Learning）？

面对一个机器学习问题，通常有两种策略。一种是研发人员尝试各种模型，选择其中表现最好的模型做重点调参优化。另一种策略是集各家之长，如同贤明的君主广泛地听取众多谋臣的建议，然后综合考虑，得到最终决策。后一种决策的核心，是将多个分类器的结果统一成一个最终的决策。使用这类策略的机器学习方法统称为集成学习。其中的每个单独的分类器称为基分类器（Base Learner）。

——《百面机器学习》
集成学习分为哪几种？他们有何异同？
- Boosting
  1. 基本思路：采用串行的方式训练基分类器，将基分类器层层叠加，每一层在训练的时候，对前一层的基分类器分错的样本，给予更高的权重，使得后续基学习器更加关注这些打标错误的训练样本。测试时，根据各层分类器的结果的加权得到最终的结果。
  2. 类似于人类迭代式学习：第一遍记住一部分，但也会犯一部分错误；第二遍学习，就会针对犯过错误的知识加强学习，减少类似的错误，如此不断循环往复，直到犯错误的次数减少到很低的程度
- Bagging
  1. 基本思路：在训练过程中，各基分类器之间并行训练。著名算法之一，随机森林。为了让基分类器之间互相独立，将训练集分为若干子集
  2. Bagging 方法更像是一个集体决策的过程，每个个体都进行单独学习，学习内容可以相同，也可以不同，也可以部分重叠。在最终做决策时，每个个体单独作出判断，再通过投票的方式做出最后的集体决策。
- Boosting vs Bagging
  
  Boosting 方法是通过逐步聚焦于基分类器分错的样本，减少集成分类器的偏差。Bagging 方法则是采取分而治之的策略，假设所有基分类器出错的概率是独立的，在某个测试样本上，用简单多数投票方法来集成结果，超过半数基分类器出错的概率会随着基分类器的数量增加而下降
Adaboost 算法
- Adaboost 算法是 Boosting 算法的应用
- 训练过程：
  1. 初始化训练数据的权值分布。如果有 $N$ 个样本，则每一个训练样本最开始时都被赋予相同的权值：$1/N$
  2. 训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权值就被降低；相反，如果某个样本点没有被准确地分类，那么它的权值就得到提高。然后，权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。
  3. 将各个训练得到的弱分类器组合成强分类器。加大分类误差率小的弱分类器的权重，降低分类误差率大的弱分类器的权重。
- 算法流程：
  
  $N$：样本数量，$T$：基分类器数量
  - 初始化采样分布 $D_1(i) = 1 / N$ （初始化每个样本的权重）
  - 令 $t = 1, 2, \dots, T$ 循环：
    - 从训练集中，按照 $D_t$ 分布，采样出子集 $S_t = {x_i, y_i}, \ i = 1, \dots, N_t$
    - 用 $S_t$ 训练出基分类器 $h_t$
    - 计算 $h_t$ 的错误率
      $$
      \epsilon_t = \frac{\sum^{N_t}_{i = 1}I[h_t(x_i) \neq y_i]D_t(x_i)}{N_t}
      $$
      其中 $I[]$ 为判别函数
      
      为什么这里的分母是 $N_t$ 而不是 $\sum^{N_t}_{i = 1}D_t(x_i)$
    - 计算基分类器 $h_t$ 权重 $a_t = log\frac{(1 - \epsilon_t)}{\epsilon_t}$
    - 设置下一次采样（更新每个样本的权重）
      $$
      D_{t + 1} = \left{
      \begin{aligned}
      D_t(i) 或者 \frac{D_t(i)(1 - \epsilon_t)}{\epsilon_t}, \quad h_t(x_i) \neq y_i \
      \frac{D_t(i)\epsilon_t}{(1 - \epsilon_t)}, \quad h_t(x_i) = y_i \
      \end{aligned}
      \right.
      $$
      并将它归一化为一个概率分布函数
  - 合并基分类器：给定一个未知样本 $z$，输出分类结果为加权投票的结果 $Sign(\sum^T_{t = 1}h_t(z)a_t)$
Bagging 算法
- Bagging使用“有放回”采样的方式选取训练集，对于包含m个样本的训练集，进行m次有放回的随机采样操作，从而得到m个样本的采样集，这样训练集中有接近36.8%的样本没有被采到。
- 按照这种方式重复，采样得到 $T$ 个包含 $m$ 个样本的数据集，从而训练出 $T$ 个基分类器
- 给定一个未知样本 $z$，由这 $T$ 个基分类器投票做出最后的决策
- Bagging主要通过样本的扰动来增加基学习器之间的多样性，因此Bagging的基学习器应为那些对训练集十分敏感的不稳定学习算法，例如：神经网络与决策树等。
如何从减小方差和偏差的角度解释 Boosting 和 Bagging 的原理
- 偏差形容的是预测值和真实值间的偏差，偏差越小，则预测值越接近真实值；方差形容的是所有预测值的聚合程度，如果预测值越离散，则方差越高。
- 在 Bagging 算法中，对 $n$ 个独立不相关的模型的预测结果取平均，方差变为原来单个模型的 $1 / n$。因此，诸多 Bagging 算法均追求模型的独立性。
- 在Boosting 算法中，需要计算弱分类器的错误或者残差，作为下一个分类器的输入，这个过程本身就是在不断减少偏差的。但是 Boosting 的过程并不会显著降低方差，这是因为 Boosting 的训练过程是的各弱分类器之间是强相关的，缺乏独立性，所以并不会降低方差。
最常用的基分类器是什么？为什么？

最常用的基分类器是决策树，有以下 3 个方面的原因。
- 决策树可以较为方便地将样本的权重整合到训练过程中，而不需要使用过采样的方法来调整样本的权重
- 决策树的表达能力和泛化能力，可以通过调节树的层数来做折中
- 数据样本的扰动对于决策树的影响较大，因此不同子样本集合生成的决策树基分类器随机性较大。
除了决策树外，神经网络模型也适合作为基分类器，主要由于神经网络模型也比较“不稳定”，而且还可以通过调整神经元数量、连接方式、网络层数、初始权重等方式引入随机性。
随机森林是什么？

随机森林是一种基于树模型的 Bagging 的优化版本。随机森林中的基分类器具有多样性，这种基多样性不仅来自样本扰动，还来自属性扰动。
- 样本扰动：有放回的取样
- 属性扰动：在基决策树的训练过程中，在选择划分属性时，随机森林先从候选属性集中随机挑选出一个包含 $K$ 个属性的子集，再从这个子集中选择最优划分属性，一般推荐 $K = log_2(|D|)$
- 建立过程
  - 如果训练集大小为N，对于每棵树而言，随机且有放回地从训练集中的抽取N个训练样本，作为该树的训练集
  - 如果每个样本的特征维度为M，指定一个常数 $m$，随机地从 $M$ 个特征中选取 $m$ 个特征子集，每次树进行分裂时，从特征子集中选择最优属性
  - 每棵树都尽最大程度的生长，并且没有剪枝过程
- 优点
  1. 能够处理很高维度（feature很多）的数据，并且不用做特征选择（因为特征子集是随机选择的）
  2. 容易做成并行化方法（训练时树与树之间是相互独立的）
  3. 相比决策树的 Bagging 集成，训练速度更快，因为基决策树只在属性集的一个子集中选择划分属性
  4. 对于不平衡的数据集来说，它可以平衡误差
- 缺点
  - 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合
  - 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的
什么是 OOB？随机森林中的OOB是如何计算的？它有什么优缺点？
- OOB：袋外错误率（Out-Of-Bag Error）
- bagging方法中Bootstrap每次约有1/3的样本不会出现在Bootstrap所采集的样本集合中，当然也就没有参加决策树的建立，把这1/3的数据称为袋外数据，它可以用于取代测试集误差估计方法。
- 可以通过计算袋外数据的误差来衡量模型的优劣，由于袋外数据是无偏估计的,所以在随机森林算法中不需要再进行交叉验证或者单独的测试集来获取测试集误差的无偏估计
什么是梯度提升决策树（GBDT）？
- 核心思想：基于树模型的Boosting思想，所有弱分类器的结果相加等于预测值。下一个弱分类器需要拟合之前所有弱分类器结论和的残差（这个残差就是预测值与真实值之间的误差）。这里的残差相当于当前模型的负梯度值。
  
  例如，用户 $A$ 的真实年龄是25岁，但第一棵决策树的预测年龄是 22 岁，差了 3 岁。那么在第二棵树里我们把 $A$ 的年龄设为 3 岁去学习；如果第二棵树的结论是 5 岁，则 $A$ 仍然存在 -2 岁的误差，第三棵树的年龄变为 -2 岁，继续学。
- GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树
- 训练过程
  
  假定训练集只有4个人：A, B, C, D，他们的年龄分别是14, 16, 24, 26。其中A、B分别是高一和高三学生；C, D分别是应届毕业生和工作两年的员工。如果是用一棵传统的回归决策树来训练，会得到如下图所示结果：
  
  现在我们使用GBDT来做这件事，由于数据太少，我们限定叶子节点做多有两个，即每棵树都只有一个分枝，并且限定只学两棵树。我们会得到如下图所示结果：
  
  第一棵树如上图左侧所示，每个节点使用平均年龄作为预测值。此时计算的残差如图所示，利用残差替代原值，在第二棵树（上图右侧）中学习。经过第二棵树，所有人的残差都为0，即每个人的预测值都等于真实值，预测值为所有树结论的累加。
GBDT的优点和局限性有哪些？
- 优点：
  1. 预测阶段的计算速度快，树与树之间可并行化计算
  2. 在分布稠密的数据集上，泛化能力和表达能力都很好，这使得GBDT在Kaggle的众多竞赛中，经常名列榜首
  3. 采用决策树作为弱分类器使得GBDT模型具有较好的解释性和鲁棒性，能够自动发现特征间的高阶关系
- 局限性
  1. GBDT在高维稀疏的数据集上，表现不如支持向量机或者神经网络
  2. GBDT在处理文本分类特征问题上，相对其他模型的优势不如它在处理数值特征时明显
  3. 训练过程需要串行训练，只能在决策树内部采用一些局部并行的手段提高训练速度
因为 GBDT 对异常值明显，因此 GBDT 需要进行特征归一化（GBDT的学习过程有点类似于梯度下降）
什么是 XGBoost？

XGBoost 是 GBDT的优化版本，XGBoost 和 GBDT 比较大的不同就是目标函数的定义。XGBoost 的目标函数如下所示：
$$
Obj^{(t)} = \sum^n_{i = 1}l(y_i, \hat{y_i}^{(t - 1)} + f_t(x_i)) + \Omega(f_t) + constant
$$
其中，$l$ 表示损失函数（XGBoost 没有给出具体的损失函数定义），$\hat{y_i}^{(t - 1)}$ 是前一轮模型的预测值，即 $\hat{y_i}^{(t - 1)} = \sum^{t - 1}_{k = 1} f_k(x_i)$，$f_t(x_i)$ 是本轮模型的预测值，$\Omega(f_t)$ 是正则化项，是对模型复杂度的惩罚。

接下来，就是利用泰勒二阶展开去做目标函数的近似。

泰勒定理：

如果 $n$ 是一个正整数，函数 $f$ 在 $a$ 点处 $n + 1$ 可导，那么对于这个区间上的任意 $x$，都有：
$$
f(x) = f(a) + \frac{f’(a)}{1!}(x - a) + \frac{f^{(2)}(a)}{2!}(x - a)^2 + \cdots + \frac{f^{(n)}(a)}{n!}(x - a)^n + R_n(x)
$$
其中，$R_n(x)$ 是泰勒公式的余项，是 $(x - a)^n$ 的高阶无穷小

泰勒二阶展开为：
$$
f(x + \Delta x) \simeq f(x) + f’(x)\Delta x + \frac{1}{2}f’’(x)\Delta x^2
$$
将目标函数 $Obj^{(t)}$ 和泰勒二阶展开一一对应起来：
- $Obj^{(t)} \rightarrow f$
- $x \rightarrow \hat{y_i}^{(t - 1)}$
- $\Delta x \rightarrow f_t(x_i)$
因此目标函数 $Obj^{(t)}$ 经过泰勒二阶展开后得到：
$$
Obj^{(t)} \simeq \sum^{n}{i = 1}[l(y_i, \hat{y_i}^{(t- 1)}) + g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t) + constant
$$
其中，$g_i = \partial{\hat{y}^{(t - 1)}}l(y_i, \hat{y}^{(t - 1)}), \quad h_i = \partial^2_{\hat{y}^{(t - 1)}}l(y_i, \hat{y}^{(t -1)})$

因为 $\hat{y}^{(t -1)}$ 由前一轮的模型确定$\longrightarrow l(y_i, \hat{y}^{(t -1)}$) 确定，不影响目标函数优化，$l(y_i, \hat{y}^{(t -1)})$ 和常数项都可以从目标函数中移除，由此得到推导后的目标函数。
$$
Obj^{(t)} \simeq \sum^{n}_{i = 1}[g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t)
$$
此时，目标函数仅依赖损失函数的一阶导数 $g_i$ 和二阶导数 $h_i$，而不依赖于损失函数。

接下来，我们来看看 XGBoosting 中树的复杂度，树遵循以下几个规则：
- 每个样本都落在叶子节点上
- $q(x)$ 表示样本 $x$ 落在的叶子节点，每个样本 $x$ 都能通过函数 $q(x)$ 映射到树中的某一个叶子节点
- $w_{q(x)}$ 表示样本 $x$ 在叶子节点 $q(x)$ 的预测值
目标函数 $Obj^{(t)}$ 中的正则化项 $\Omega(f_t)$ 包含两个部分：
$$
\Omega(f_t) = \gamma T + \frac{1}{2} \lambda \sum^T_{j = 1} w^2_j
$$
其中，$T$ 表示叶子节点的个数，$w_j$ 表示叶子节点的预测值，$\frac{1}{2} \lambda \sum^T_{j = 1} w^2_j$ 的惩罚是为了避免某一个叶子节点的预测值过大。

上述目标函数中的 $f_t(x_i)$，其实就是 $w_j$，因此目标函数可以进一步合并为：
$$
\begin{align}
Obj^{(t)} &\simeq \sum^{n}{i = 1}[g_if_t(x_i) + \frac{1}{2}h_if^2_t(x_i)] + \Omega(f_t) \
&= \sum^{n}{i = 1}[g_iw_q(x_i) + \frac{1}{2}h_iw^2_q(x_i)] + \gamma T + \frac{1}{2} \lambda \sum^T_{j = 1} w^2_j \
&= \sum^T_{j = 1}[(\sum_{i \in I_j} g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i + \lambda)w^2_j] + \gamma T
\end{align}
$$
其中，$I_j$ 为每个叶节点中的下标集合，$I_i = {i | q(x_i) = j }$

令 $G_j = \sum_{i \in I_j} g_i, \quad H_j = \sum_{i \in I_j} h_i$

最终，目标函数化简为：
$$
Obj^{(t)} = \sum^T_{j = 1}[(G_jw_j + \frac{1}{2}(H_j + \lambda)w^2_j] + \gamma T
$$
计算目标函数的极小值点：
$$
\partial w_j Obj^{(t)} = G_j + (H_j + \lambda)w_j
$$
令 $\partial w_j Obj^{(t)} = 0$，得到：
$$
w_j = -\frac{G_j}{H_j + \lambda} \
$$
带入到目标函数中得到：
$$
Obj^{(t)} = -\frac{1}{2} \sum^T_{j = 1} \frac{G^2_j}{H_j + \lambda} + \gamma T
$$
目标函数可以直观理解为当我们指定一个树结构时，最多在目标函数减少多少。上面推导的目标函数为所有叶节点的求和，正如前面的 ID3树、C4.5树和 CART树，我们在确定某一个节点是否还要往下继续分裂时，需要比较节点分裂前后的增益 Gain，并根据增益 Gain 选择最优特征。增益Gain的表达式如下所示：

XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用的目标函数不一样。
XGBoost 中树停止生长的条件？
- 当引入的分裂带来的增益小于设定阀值
- 当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，避免树太深导致学习局部样本，从而防止过拟合
- 样本权重和小于设定阈值时则停止建树。什么意思呢，即涉及到一个超参数-最小的样本权重和min_child_weight，和GBM的 min_child_leaf 参数类似，但不完全一样。大意就是一个叶子节点样本太少了，也终止同样是防止过拟合
XGBoost 和 GBDT 的区别是什么？

XGBoost 可以理解为 GBDT 的优化版本，与 GBDT 相比，无论是精度还是效率上都有了提升。和 GBDT 相比，具体的优点有：
- 损失函数使用了泰勒展开二项逼近，而不是像 GBDT 里是一阶导数
- 对树的结构进行了正则化约束，防止模型过度复杂，降低了过拟合的可能性
- 节点分裂的方式不同，GBDT 使用的是基尼系数（GBDT的每一棵树都是 CART 回归树），而 XGBoost 使用的是经过优化推导后得出的增益评分
XGBoost 为什么使用泰勒展开？优势在哪里？

XGBoost 使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准。使用泰勒展开取得函数做自变量的二阶导数形式，可以在不选定损失函数具体形式的情况下，仅仅依靠输入数据的值就可以进行叶子分裂优化计算，本质上也就把损失函数的选取和模型算法优化/参数选择分开了（因为没有确定的损失函数）。这种去耦合增加了XGBoost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。
什么是 LightGBM