偏差与方差

偏差（bias）指的是算法的期望预测与真实值之间的偏差程度，反映了模型本身的拟合能力；

方差（variance）度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。

集成学习

集成学习通过训练多个分类器，然后将其组合起来，从而达到更好的预测性能，提高分类器的泛化能力。

bagging（套袋法）

原理

bagging 是并行集成学习方法的最著名代表，其算法过程如下：

1. 从原始样本集中抽取训练集。每轮从原始样本集中使用 Bootstraping 的方法抽取 n 个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行 k 轮抽取，得到 k 个训练集。（k 个训练集之间是相互独立的）
2. 每次使用一个训练集得到一个模型，k 个训练集共得到 k 个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）
3. 对分类问题：将上步得到的 k 个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

要得到泛化性能强的集成，集成中的个体学习器应尽可能表现好且相互独立，即“好而不同”。但是“独立”的学习方法在现实任务中无法做到，因为同一个数据集，训练得到的学习器肯定不会完全独立，但可以设法使基学习器尽可能具有较大的差异。给定一个训练数据集，一种可能的做法是对训练样本进行采样，产生出若干个不同的子集，再从每个数据子集中训练出一个基学习器。这样，由于训练数据的不同，我们获得的基学习器可望具有较大的差异。然而，为了获得好的集成，我们同时还希望个体学习器不能太差，如果采样出的每个子集都完全不同，则每个学习器都只用到了一小部分的训练数据，甚至不足以进行有效学习。为解决这个问题，我们可考虑使用相互有交叠的采样子集。

bagging 对训练数据集的采样使用的是 bootstrap 自助采样法，因此这里先对这个方法进行简单介绍：

给定包含 m 个样本的数据集 $D$ ，我们对它进行采样产生数据集 $D'$ ：每次随机从 $D$ 中挑选一个样本，将其拷贝放入 $D'$ ，然后再将该样本放回初始数据集 $D$ 中，使得该样本在下次采样时仍有可能被采到；这个过程反复执行 m 次后，我们就得到了包含 m 个样本的数据集 $D'$ ，这就是自助采样法的结果。显然，$D$ 中有一部分样本会在 $D'$ 中多次出现，而另一部分样本不出现，可以做个简单的统计，样本在 m 次采样中始终不被采到的概率是 $(1-\frac{1}{m})^m$ ，取极限得到：

$\lim_{m \rightarrow \infty}(1-\frac{1}{m})^m = \frac{1}{e} \approx 0.368$

照上面的自助采样法，我们可以采样出 T 个含有 m 个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器进行结合，这便是 bagging 方法的基本流程。在对预测进行结合时，Bagging 通常对分类任务使用简单投票法，对回归任务使用简单平均法。

bagging方法之所以有效，是因为并非所有的分类器都会产生相同的误差，只要有不同的分类器产生的误差不同，就会对减小泛化误差有效。

与 Adaboost 的区别：

标准 AdaBoost 只适用于二分类任务，而 Bagging 能不经修改地用于多分类与回归任务。

Bagging 对样本重采样，对每一重采样得到的子样本集训练一个模型，最后取平均。由于子样本集的相似性以及使用的是同种模型，因此各模型有近似相等的 bias 和 variance（事实上，各模型的分布也近似相同，但不独立）。

由于 $E[\frac{\sum X_i}{n}] = E[X_i]$ ，所以 bagging 后的 bias 和单个子模型的接近，一般来说不能显著降低 bias。

另一方面，若各子模型独立，则有 $Var(\frac{\sum X_i}{n}) = \frac{Var(X_i)}{n}$ ，此时可以显著降低 variance。若各子模型完全相同，则 $Var(\frac{\sum X_i}{n}) = Var(X_i)$ ，此时不会降低 variance。bagging 方法得到的各子模型是有一定相关性的，属于上面两个极端状况的中间态，因此可以一定程度降低 variance。

为了进一步降低variance，Random forest 通过随机选取特征子集，进一步减少了模型之间的相关性，从而使得 variance 进一步降低。

Bagging 与 Dropout 的联系

dropout 思想继承自 bagging 方法。bagging 是每次训练一个基分类器的时候，都有一些样本对该基分类器不可见，而dropout是每次训练的时候，都有一些神经元对样本不可见。

我们可以把 dropout 类比成将许多大的神经网络进行集成的一种 bagging 方法。但是每一个神经元的训练是非常耗时和占用内存的，训练很多的神经网络进行集合分类就显得太不实际了，但是 dropout 可以看做是训练所有子网络的集合，这些子网络通过去除整个网络中的一些神经元来获得。

**dropout 具体怎么去除一个神经元呢？**可以在每个神经元结点处独立采样一个二进制掩膜，采样一个掩膜值为 0 的概率是一个固定的超参数，则掩膜值为 0 的被去除，掩膜值为 1 的正常输出。

bagging与dropout训练的对比

• 在 bagging 中，所有的分类器都是独立的，而在 dropout 中，所有的模型都是共享参数的。
• 在 bagging 中，所有的分类器都是在特定的数据集下训练至收敛，而在 dropout 中没有明确的模型训练过程。网络都是在一步中训练一次（输入一个批次样本，随机训练一个子网络）。

dropout的优势

• very computationally cheap。在 dropout 训练阶段，每一个样本每一次更新只需要 O(n) ，同时要生成 n 个二进制数字与每个状态相乘。除此之外，还需要 O(n) 的额外空间存储这些二进制数字，直到反向传播阶段。
• 没有很显著的限制模型的大小和训练的过程。

boosting（提升方法）

俗话说“三个臭皮匠顶个诸葛亮”，对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。

Leslie Valiant 首先提出了“强可学习（strongly learnable）”和”弱可学习（weakly learnable）”的概念，并且指出：在概率近似正确（probably approximately correct, PAC）学习的框架中，一个概念（一个类），如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习的，如果正确率不高，仅仅比随即猜测略好，那么就称这个概念是弱可学习的。2010年的图灵奖给了L. Valiant，以表彰他的 PAC 理论。非常有趣的是 Schapire 后来证明强可学习与弱可学习是等价的，也就是说，在 PAC 学习的框架下，一个概念是强可学习的充要条件是这个概念是可学习的。

这样一来，问题便成为，在学习中，如果已经发现了“弱学习算法”，那么能否将它提升（boost）为”强学习算法”。大家知道，发现弱学习算法通常比发现强学习算法容易得多。那么如何具体实施提升，便成为开发提升方法时所要解决的问题。

对于分类问题而言，给定一个训练数据，求一个比较粗糙的分类器（即弱分类器）要比求一个精确的分类器（即强分类器）容易得多。提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据中的各个数据点的权值分布），调用弱学习算法得到一个弱分类器，再改变训练数据的概率分布，再调用弱学习算法得到一个弱分类器，如此反复，得到一系列弱分类器。

这样，对于提升方法来说，有两个问题需要回答：

1. 是在每一轮如何改变训练数据的概率分布。
2. 是如何将多个弱分类器组合成一个强分类器。

关于第一个问题，AdaBoost 的做法是，提高那些被前几轮弱分类器线性组成的分类器错误分类的的样本的权值。这样一来，那些没有得到正确分类的数据，由于权值加大而受到后一轮的弱分类器的更大关注。于是，分类问题被一系列的弱分类器”分而治之”。至于第二个问题，AdaBoost 采取加权多数表决的方法。具体地，加大分类误差率小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差率大的弱分类器的权值，使其在表决中起较小的作用。

Boosting 从优化角度来看，是用 forward-stagewise 这种贪心法去最小化 loss 函数,由于采取的是串行优化的策略，各子模型之间是强相关的，于是子模型之和并不能显著降低 variance，而每一个新的分类器都在前一个分类器的预测结果上改进，力求预测结果接近真实值，所以说 boosting 主要还是靠降低 bias 来提升预测精度。

Bagging 和 Boosting 的区别

1）样本选择上：

Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。

Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

2）样例权重：

Bagging：使用均匀取样，每个样例的权重相等

Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

3）预测函数：

Bagging：所有预测函数的权重相等。

Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

4）并行计算：

Bagging：各个预测函数可以并行生成

Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

stacking 模型融合

stacking 就是当用初始训练数据学习出若干个基学习器后，将这几个学习器的预测结果作为新的训练集，来学习一个新的学习器。stacking 在深度学习大数据比赛中经常被使用，大概流程可以看看这篇博客。

AdaBoost 算法

特点：

1. 不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用
2. 利用基本分类器的线性组合构建最终的分类器

假设给定一个二类分类的训练数据集：

$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

其中每个样本点由实例与标记组成。实例 $x_i \in \chi \subseteq R^n$ ，标记 $y_i \in \Upsilon = \{-1,1\}$ ，$\chi$ 是实例空间，$\Upsilon$ 是标记集合。Adaboost 利用以下算法，从训练数据中学习一系列弱分类器，并将这些弱分类器线性组合成为一个强分类器。

(一) 初始化训练数据的权值分布：

$D_1 = (w_{11},...,w_{1i},...,w_{1N}),\quad w_{1i}=\frac{1}{N},\quad i=1,2,...,N$

假设训练数据集具有均匀的权值分布，即每个训练样本在基本分类器的学习中作用相同。这一假设保证第１步能够在原始数据上学习基本分类器 $G_1(x)$ 。

(二) 一共需要学习 M 个基本分类器，则在每一轮 $m = 1,2,...,M$ 顺次地执行下列操作：

1. 使用当前分布 $D_m$ 加权的训练数据集，得到基本分类器：

   $G_m(x):\chi\rightarrow \{-1,+1\}$

2. 计算 $G_m(x)$ 在训练数据集上的分类误差率：

   $e_m = \sum_{i=1}^{N}P(G_m(x_i)\not = y_i) = \sum_{G_{mi}\not = y_i}w_{mi}$

   $w_{mi}$ 表示第 m 轮中第 i 个实例的权值，$\sum_{i=1}^{N}w_{mi} = 1$ 。这表明， $G_{m}(x)$ 在加权的训练数据集上的分类误差率是被 $G_{m}(x)$ 误分类的样本的权值之和。

3. 计算 $G_{m}(x)$ 的系数：

   $\alpha_m = \frac{1}{2}ln \frac{1-e_m}{e_m}$

   $\alpha_m$ 表示 $G_{m}(x)$ 在最终分类器中的重要性。根据式子可知，$e_m \le \frac{1}{2}$ 时，$\alpha_m \ge 0$ ，并且 $\alpha_m$ 随着 $e_m$ 的减小而增大，所以分类误差率越小的基本分类器在最终分类器中的作用越大。这里注意所有 $\alpha_m$ 加起来的和并不等于 1 。 （注意 $e_m$ 是有可能比 $\frac{1}{2}$ 大的，也就是说 $\alpha_m$ 有可能小于 0，《统计学习方法》没有讨论这种情况的处理方法，但在西瓜书中的处理方法是抛弃该分类器，且终止学习过程，哪怕学习到的分类器个数远远没有达到预设的 M）

4. 更新训练数据集的权值分布：

   $D_{m+1} = (w_{m+1,1},...,w_{m+1,i},...,w_{m+1,N}) \\ w_{m+1,i} = \frac{w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)), \quad i=1,2,...,N \\ 其中 Z_m是规范因子，Z_m = \sum_{i=1}^{N}w_{mi}exp(-\alpha_my_iG_m(x_i))$

   $w_{m+1,i}$ 也可以写成分段函数的形式：

   $w_{m+1,i}= \begin {cases} \frac{w_{mi}}{Z_m}e^{-\alpha_m}, & G_m(x_i) = y_i \\ \frac{w_{mi}}{Z_m}e^{\alpha_m}, & G_m(x_i) \not = y_i \end {cases}$

   也就是说被基本分类器 $G_m(x)$ 误分类样本的权值得以增大，而被正确分类的样本的权值却变小。两者相比可知误分类样本的权值被放大 $e^{2\alpha_m} = \frac{1-e_m}{e_m}$ 倍。因此，误分类样本在下一轮学习中起更大的作用。

(三) 经过以上过程后可以得到 M 个基本分类器，构建基本分类器的线性组合：

$f(x) = \sum_{m=1}^{M}\alpha_m G_m(x)$

得到最终分类器：

$G(x) = sign(f(x)) = sign(\sum_{m=1}^{M}\alpha_m G_m(x))$

线性组合 $f(x)$ 实现 M 个基本分类器的加权表决，$f(x)$ 的符号决定了实例 $x$ 的类，$f(x)$ 的绝对值表示分类的确信度。

对无法接受带权样本的基分类器学习方法，则可通过“重采样法”来处理，即在每一轮学习中，根据样本分布对训练集重新采样，再用重采样而得的样本集对基分类器进行训练。上面也说到了，AdaBoost 模型学习过程中，当出现一个基分类器的误分类误差大于 0.5 即比随机猜测还要差时，处理方法是将该分类器丢弃，且终止学习过程，此种情形下，初始设置的学习轮次 M 也许还未达到，可能会导致最终集成中只包含很少的基分类器而性能不佳。若采用“重采样法”，则可获得“重启动”机会以避免训练过程过早停止，即在抛弃不满足条件的当前基分类器之后，可根据当前分布重新对训练样本进行采样，再基于新的采样结果重新训练出基分类器，从而使得学习过程可以持续到预设的 M 轮完成。

GBDT 算法

GBDT (Gradient Boosting Decision Tree) 梯度提升迭代决策树。GBDT 也是 Boosting 算法的一种，我们可以从名字上对这个算法有个初步的理解：GB是 Gradient Boosting ，是一种学习策略，而 DT 就是决策树，因此 GBDT 的含义就是用 Gradient Boosting 策略训练出来的 DT 模型。

GBDT 的核心思想是 Boosting。Boosting 是一族可将弱学习器提升为强学习器的算法，属于集成学习的范畴。在 GBDT 中，每一棵决策树都是在前一棵树的残差基础上进行训练的，通过逐步减小残差，提高模型的精度。

GBDT 和 AdaBoost 的模型都可以表示为如下形式：

$f(x) = \sum_{m=1}^{M}\alpha_m G_m(x)$

只是 AdaBoost 在训练完一个 $G_m(x)$ 后会重新赋值样本的权重：分类错误的样本的权重会增大而分类正确的样本的权重则会减小。这样在训练时 $G_{m+1}(x)$ 会侧重对错误样本的训练，以达到模型性能的提升，但是 AdaBoost 模型每个基分类器的损失函数优化目标是相同的且独立的，都是最优化当前样本（样本权重）的指数损失。

GBTD 虽然也是一个加性模型，但其是通过不断迭代拟合样本真实值与当前分类器预测的残差来逼近真实值的。可以形象地理解如下：

第 m 个基分类器的预测结果为：

$f_m(x) = f_{m-1}(x)+\alpha_mG_m(x)$

而 $G_m(x)$ 的优化目标就是最小化当前预测结果 $f_{m-1}(x_i)+\alpha G(x_i)$ 与真实值 $y_i$ 之间的差距。

$(\alpha_m,G_m(x)) = arg min_{\alpha,G}\sum_{i=1}^{N}L(y_i,\quad f_{m-1}(x_i)+\alpha G(x_i))$

GBDT 无论是用于分类和回归，采用的都是回归树，分类问题最终是将拟合值转换为概率来进行分类的。

模型求解

Gradient Boosting是Friedman提出的一套框架。其思想类似于数值优化中梯度下降求参方法，参数沿着梯度的负方向以小步长前进，最终逐步逼近参数的局部最优解。在GB中模型每次拟合残差，逐步逼近最终结果。

如上所述，我们每个 stage 的优化目标是：

$G_m(x) = arg min_{G}\sum_{i=1}^{N}L(y_i,\quad f_{m-1}(x_i)+\alpha_m G(x_i))$

该函数比较难求解，类似于梯度下降方法，给定 $f_{m-1}(x_i)$ 的一个近似解，$\alpha_mG_m(x)$ 可以看作是 $f_{m-1}(x_i)$ 逼近 $f_m(x_i)$ 的步长和方向。所以：

$f_m(x)= f_{m-1}(x)-\alpha_m [\frac{\partial L(y_i,f_m(x_i))}{\partial f_m(x_i)}]_{f_m(x_i)=f_{m-1}(x_i)} \\ \alpha_m = arg min_{\alpha}\sum_{i=1}^{N}L(y_i,f_{m-1}(x)-\alpha_m [\frac{\partial L(y_i,f_m(x_i))}{\partial f_m(x_i)}]_{f_m(x_i)=f_{m-1}(x_i)} )$

上面的损失函数 L 可以根据问题的不同使用不同的损失函数，而且还可以加上模型复杂度的正则项等等来尽量避免过拟合。

XGBoost 算法

XGBoost 是 GBDT 最广为人知的一个实现。通过使用一定程度的近似，使得求解变得更高效。同时支持分布式和 GPU 优化，有着广泛的使用。

如前文所述，最终分类器可以使用这个公式表示：

$f(x) = \sum_{m=1}^{M} G_m(x)$

优化目标如下：

$Obj = \sum_{i=1}^N L(y_i,f(x_i))+\sum_{m = 1}^{M}\Omega(G_m(x))$

其中 $N$ 为样本数量，$y_i$ 表示样本真实值，$f(x)$ 是模型输出，所以前半部分代表模型的损失函数。$M$ 表示树的个数，$G_m(x)$ 表示第 $m$ 棵树，$\Omega$ 是模型复杂度函数。模型越复杂，越容易出现过拟合，所以采用这样的目标函数，为了使得最终的模型既有很好的准确度也有不错的泛化能力。

其他参考资料

超详细解析XGBoost（你想要的都有） - 知乎 (zhihu.com)

XGBoost的原理、公式推导、Python实现和应用 - 知乎 (zhihu.com)

GBDT的原理和应用 - 知乎 (zhihu.com)

随机森林

随机森林 (RF) 是 Bagging 的一个变体。RF 在以决策树为基学习器构建 Bagging 集成的基础上，进一步在决策树的训练过程中引入随机性：

传统决策树在选择划分属性时，是在当前结点的属性集合（假定有 d 个属性）中选择一个最优属性；而在 RF 中，对基决策树的每一个结点，先从结点的属性集合中随机选择一个包含 k 个属性的子集，然后再从这个子集当中选择一个最优属性用于划分。

这里的参数 k 控制了随机性的引入程度。若令 $k=d$ ，则基决策树的构建与传统决策树相同，一般情况下，推荐值为 $k=log_2 d$ 。

为什么不容易过拟合

因为随机森林中每棵树的训练样本是随机的，每棵树中的每个结点的分裂属性也是随机选择的。这两个随机性的引入，使得随机森林不容易陷入过拟合。且树的数量越多，随机森林通常会收敛到更低的泛化误差。理论上当树的数目趋于无穷时，随机森林便不会出现过拟合，但是现实当做做不到训练无穷多棵树。

如何评估特征的重要性

这个问题是决策树的核心问题，而随机森林是以决策树为基学习器的，所以这里大概提提，详细的可以去看看决策树模型。

决策树中，根节点包含样本全集，其他非叶子结点包含的样本集合根据选择的属性被划分到子节点中，叶节点对应于分类结果。决策树的关键是在非叶子结点中怎么选择最优的属性特征以对该结点中的样本进行划分，方法主要有信息增益、增益率以及基尼系数３种，下面分别叙述。

信息增益 (ID3决策树中采用)

“信息熵”是度量样本集合纯度最常用的一种指标，假定当前样本结合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k = 1, 2, ..., c)$ ，则 $D$ 的信息熵定义为：

$Ent(D)= -\sum_{k=1}^{c}p_klog_2 p_k$

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。注意因为 $p_k \le 1$ ，因此 $Ent(D)$ 也是一个大于等于０小于１的值。

假定离散属性 $a$ 有 V 个可能的取值 $\{a^1,a^2,...,a^V\}$ ，若使用 $a$ 来对样本集合 $D$ 进行划分的话，则会产生 V 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有在属性 $a$ 上取值为 $a^v$ 的样本，记为 $D^v$ 。同样可以根据上式计算出 $D^v$ 的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $\frac{|D^v|}{|D|}$ ，即样本数越多的分支结点的影响越大，于是可以计算出使用属性 $a$ 对样本集 $D$ 进行划分时所获得的“信息增益”：

$Gain(D,a) = Ent(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)$

一般而言，信息增益越大越好，因为其代表着选择该属性进行划分所带来的纯度提升，因此全部计算当前样本集合 $D$ 中存在不同取值的那些属性的信息增益后，取信息增益最大的那个所对应的属性作为划分属性即可。

缺点：对可取值数目多的属性有所偏好

增益率 (C4.5决策树中采用)

从信息增益的表达式很容易看出，信息增益准则对可取值数目多的属性有所偏好，为减少这种偏好带来的影响，大佬们提出了增益率准则，定义如下：

$Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)} \\ IV(a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}log_2 \frac{|D^v|}{|D|}$

$IV(a)$ 称为属性 a 的“固有值”。属性 a 的可能取值数目越多，则 $IV(a)$ 的值通常会越大，因此一定程度上抵消了信息增益对可取值数目多的属性的偏好。

缺点：增益率对可取值数目少的属性有所偏好

因为增益率存在以上缺点，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数 (CART决策树中采用)

这里改用基尼值来度量数据集 $D$ 的纯度，而不是上面的信息熵。基尼值定义如下：

$Gini(D) = \sum_{k=1}^{c} \sum_{k^, \not =k}p_kp_{k^,} = 1- \sum_{k=1}^{c}p_k^2 = 1-\sum_{k=1}^{c}(\frac{D^k}{D})^2$

直观来看，$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，因此$Gini(D)$ 越小，则数据集 $D$ 的纯度越高。

对于样本D，个数为|D|，根据特征A的某个值a，把D分成|D1|和|D2|，则在特征A的条件下，样本D的基尼系数表达式为：

$Gini\_index(D,A) = \frac{|D^1|}{|D|}Gini(D^1)+ \frac{|D^2|}{|D|}Gini(D^2)$

于是，我们在候选属性集合A中，选择那个使得划分后基尼系数最小的属性作为最优划分属性即可。