Ensembling Methods Chinese Version

简介

在决策树章节中,我们讨论了如何在回归和分类任务中应用决策树,以及如何构建决策树。正如决策树章节中所述,决策树模型能力有限,过拟合问题难以解决,我们很难训练一个在一般情况下表现良好的决策树。因此,该章节中提出了使用决策树的集成算法。简而言之,多个训练模型的表现比单个模型的表现会更好。

我们有n个独立同分布的随机变量$X_i$,其中$0 \leq i \leq n$,并假设所有$X_i$有$Var(X_i) = \sigma^2$。那么,我可以得到$X_i$均值的方差为:

如果我们删除$X_i$独立的假设,则随机变量间是彼此相关的。

其中p是皮尔逊相关系数 $p_{X,Y} = \frac{Cov(X,Y)}{\sigma_x\sigma_y}$。我们知道 Cov(X,X) = Var(X)。

数学: 以下证明有助于理解上述步骤。

返回主题:现在,如果我们将每个随机变量视为一个训练模型的误差,我们可以通过以下方式减少此方差:

1, 增加随机变量(即模型数量)n的数量以式子后半部分变小

2,减少每个随机变量之间的相关性,使第一项变小,使其更靠近独立同分布状态

问题是,我们如何实现这些目标呢?在此章节中,我们将介绍BaggingBoosting

Bagging

Bootstrap

简单来讲,Bootstrap是一种重新采样技术,它可以用于改进数据的estimator。在该算法中,我们从数据的经验分布中不断采样,最后得到数据的统计值。

假设我们有一个经过训练的estimator E,这个estimator可以预测数据的中位数。我们想知道这个estimator估算的置信度有多高,以及它与真实数据的差异有多大。这里我们可以使用bootstrap来进行测评。在bootstrap算法中,我们可以:

1, Bootstrap样本$\mathbb{B}_1,\dots,\mathbb{B}_B$,其中$\mathbb{B}_b$,是通过从数据为n的数据集中有放回的抽取样本而生成的。

2, 得到每个Bootstrap $\mathbb{B}_b$的estimator为:

3, 计算E的均值与方差:

这可以让我们了解estimator在估算数据中值时的表现如何。

Bagging

Bagging使用bootstrap的概念进行回归或分类,它代表着Bootstrap聚合

算法如下:

对于$b=1,\dots,B$,

1, 从训练数据集中提取大小为n的bootstrap数据$\mathbb{B}_b$

2, 对bootstrap数据$\mathbb{B}_b$训练决策树分类器或决策树回归模型$f_b$。

要预测新数据点$x_0$,我们需要计算:

对于回归问题,我们只需要计算出所有分类器的预测平均值即可。对于分类任务,我们可以使用投票机制来获得最终结果。

假设在二元分类中,有一个输入特征$x\in \mathbb{R}^5$。如下所示,我们可以使用bootstrap算法来训练多个分类器:

Bagging Examples

让我们回到等式:

正如我们所讨论的,减少误差的一种方法是使每个训练模型上的相关性变小。 Bagging可以通过对不同的数据集训练,实现这一目标。我们无法否认的是,由于每个bootstrp从原始数据集中只获取部分训练样本,这可能会使偏差加大。然而事实证明,由此带来的误差的减少将大于偏差的增加。此外,我们可以通过引入更多模型(即增加M或者在等式中的n)不断减少误差。这并不会导致过拟合,因为$p$对M不敏感,所以整体误差只会减少。

以下两点需要强调:

1, 用bagging时,每个决策树并不需要做到完美,OK就差不多了。

2, Bagging在非线性数据中表现更好。

Out-of-bag estimation

在每个bootstrap中,我们只选择原始数据集的一部分。让我们假设我们均匀分布中对其进行有放回采样。随着数据集大小为$n\rightarrow \infty$,对于某一个样本,它未被选择的概率为:

这大约是三分之一,这意味着一个bootstrap中约有三分之一的原始数据未被选中进行训练。为了测试我们的bagging训练模型,对于第i个样本,我们可以用未经过该样本训练过的那些模型(大约M / 3模型)在此样本上进行预测。通过在整个数据集中执行此操作,我们可以获得out-of-bag(词如其名,bagging外的误差)误差估计。在$M\rightarrow\infty$的极端情况下,未对第i个样本进行训练的模型,对所有其他样本进行了训练,这个效果与交叉验证的留一法相同。

随机森林

不过Bagging也是存在缺点的。从bootstrap训练的决策树是彼此相关的,因为bootstrap之间是相关的。这是我们不想见到的,我们只希望减少相关性。这样的bagging将无法获得最佳性能。因此,有人就提出了随机森林,这种方法,修改虽小但却很有效。bagging是在所有维度上生长决策树,随机森林则是在随机选择的维度子集中生长决策树,详细为:

对 $b=1,\dots,B$,

1, 从训练数据集中提取大小为n的bootstrap$\mathbb{B}_b$

2, 对于每次训练,我们从d维度中随机选择m维($m \approx \sqrt(d)$)。对于每个bootstrap,我们有不同的维度m。

Boosting

我们现在知道了bagging是为了减少使用决策树时的方差,而Boosting则是为了减少偏差。在bagging中,我们生成bootstrap样本训练每个模型。在boosting中,我们在每次训练迭代后对bootstrap中的每个样本进行重新加权。如图所示:

Bagging Boost Examples

定义上讲,Adaboost为:

1, 初始化 $w_i \leftarrow \frac{1}{N}$ 其中 $i=1,2,\dots,n$ 并且这是一个二元分类。

2, 对 m=0 到 M:

      根据分布$w_t(i)$对大小为n的bootstrap数据集$B_m$进行采样

      将bootstrap $B_t$与模型$F_m$进行拟合

      设 $\epsilon_m = \sum_{i=1}^n w_m(i) \mathbb{1}[y_i\neq F_m(x_i)] $ 并且 $\alpha_m = \frac{1}{2}\ln\frac{1-\epsilon_m}{\epsilon_m}$

      缩放 $\bar{w}_{m+1}(i) = w_m(i)\exp(-\alpha_m y_i F_m(x_i))$ 并且归一化 $w_{m+1}(i) = \frac{\bar{w}_{m+1}(i)}{\sum_j \bar{w}_{m+1}(j)}$

3, 分类所遵循的规则为 $f_{boost}(x_0) = sign(\sum_{m=1}^M \alpha_m)$

在每次迭代中,错误分类的样本的权重不断增加。最终预测由加权误差决定。计算求和的结构准许我们增加建模能力,但由于每个训练模型都是相关的,也会导致高方差的出现。因此,增加M也会增加方差。

Boosting分析

值得一谈的是Boosting训练的准确性。这部分是纯粹理论,如果你愿意可以跳过它。

定理: 使用AdaBoost算法,如果$\epsilon_m$是分类器$f_m$的加权误差,则最终分类为$f_{boost}(x_0)=sign(\sum_{m=1}^M \alpha_m f_m(x_0))$。那么训练误差可以被限制:

即使每个$\epsilon_m$都只比随机猜测好一些,当M较大时M模型的总和(在指数位置)将会是一个很大的负值。因此,它有一个较小的上限。

证明

为了证明这一点,我们希望借助一个中间值。如果我们知道 a < b 并且 b < c, 那么我就能确定 a < c。

回想:

我们可以定义:

那么,我们可以将其改写:

利用上面的等式进一步改写为:

由于最开始的设定,所以我们知道 $w_1(i) = \frac{1}{n}$。 我们有:

其中我们定义 $h_M(x) = \sum_{m=1}^M \alpha_m F_m(x)$。b为 $\prod_{m=1}^M Z_m$。 接下来我们可以将权重改写为:

然后,我们将训练误差带回。注意,对于任何 $z_1 <0< z_2$,$0 < \exp(z_1), 1<\exp(z_2)$。所以:

我们证明了,训练误差小于等于中间值“b”。接下来我们单独处理$Z_m$:

其中 $\epsilon_m = \sum_{i:y_i\neq F_m(x_i)} w_m(i)$。如果我们对于$\alpha_m$,使$Z_m$最小化,我们可以得到:

这正是我们在最开始时设定的。

我们可以将其带回并找出:

我们知道 $1 - x \leq \exp(-x)$,所以我们可以说:

$$Z_m = (1 - 4(\frac{1}{2} - \epsilon_m)^2)^{\frac{1}{2}} \leq (\exp(-4(\frac{1}{2} - \epsilon_m)^2))^{\frac{1}{2}} = \exp(-2(\frac{1}{2} - \epsilon_m)^2)

对于所有$Z_m$,我们可以有:

前项逐步叠加模型

在讨论新的boosting算法之前,我们值得研究一下一般的集成框架。它被称为前项逐步叠加模型。详细来讲:

输入: 提供标签的训练数据 $(x_1,y_1),\dot,(x_N,y_N)$

输出: 集成分类器 f(x)

1, 初始化 $f_0(x) = 0$

2, 对于 m=1 到 M:

       计算 $(\beta_m,\gamma_m) = \arg\min_{\beta,\gamma}\sum_{i=1}^N L(y_i,f_{m-1}(x_i) + \beta G(x_i;\gamma))$

       设 $f_m(x) = f_{m-1}(x) + \beta_m G(x;\gamma_m)$

3, 输出 $f(x) = f_m(x)$

在每次迭代中,我们修正之前步骤中所有训练模型的权重和参数。G(x)是一个弱分类器,它的参数为$\gamma$。现在证明Adaboost是一种在二分类和指数损失中的特殊情况:

此外,我们还可以证明,如果我们代入平方亏损(squared loss),那么:

这意味着在这个推导中的平方损失的效果等于在对每一个残差 $(y_i-f_{m-1}(x_i))$拟合一个分类器。这只是对逐步叠加学习的一个简短介绍,如果你想了解更多相关知识,你应该去查阅一下课本等相关书籍。

梯度提升

Boosting的应用领域很广泛,它也是逐步叠加建模的一种。其核心思想是,在每次迭代后,我们都会得到一个弱分类器。也就是说,我们只需要每个分类器的分类效果稍强于随机猜测即可。在最后,我们可以汇集所有弱分类器,形成一个能力较强的分类器。在Adaboost中,对于每次迭代,我们希望新模型专注于重新加权过的数据样本。对于梯度提升,最重要的是我们希望新模型专注于有偏差预测的梯度。

步骤为:

1, 初始化 $f_0(x) = c$

2, 在第i次迭代, 对于样本 $j=1,\dots,N$, 计算:

现在, 在第i次迭代中,我们有 $(x_1,g_{1i}),\dots,(x_N,g_{Ni})$

3, 在第i次迭代的,用$(x_1,g_{1i}),\dots,(x_N,g_{Ni})$拟合新的决策树或回归树:

4, 设

我们可以通过M次迭代来获得$f_M(X)$,这就是最终的模型了。

同样,这只是对梯度Boosting的简短介绍,更多内容请翻阅教科书。下面两个链接非常有用:

Tutorial from Northeastern University by Prof. Cheng Li

Top voted answer from Quora