前言
参考：
- 《统计学习》—李航（蓝皮）
- 部分来自网络的内容（主要是liaohuiqiang的博客）
提升方法
简介
提升方法（Boosting）是一种常用的统计学习方法，应用广泛且有效。在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。
基本思路：Boosting基于这样一种思想：对于一个复杂任务来说，将多个专家的判断进行适当的综合所得出的判断，要比其中任何一个专家单独的判断好。实际上就是“三个臭皮匠，顶个诸葛亮”的道理。（重要）
强可学习和弱可学习
- 强可学习：在概率近似正确（Probably Approximately Correct，PAC）学习的框架中的，对于一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么称这个概念是强可学习的。
- 弱可学习：对于一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么称为弱可学习的。
- 强可学习和弱可学习：Schapire证明了强可学习与弱可学习是等价的，也就是说，在PAC学习的框架下，一个概念是强可学习的充要条件是这个概念是弱可学习的。
从弱学习到强学习：可将“弱学习”提升为“强学习”，弱学习算法通常比强学习算法容易得多。具体如何实施提升，便称为开发提升方法时要解决的问题。有很多提升算法被提出，最具代表性的就是AdaBoost。
提升方法就是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。大多数的提升方法都是改变训练数据的概率分布（训练数据的权重分布），针对不同的训练数据分布，调用弱学习算法学习一系列弱分类器。这里就有两个问题：
- 在每一轮如何改变训练数据的权值或概率分布
- 如何将弱分类器组合成一个强分类器
AdaBoost
简介
对于前面提到的两个问题，AdaBoost的做法是：（重要）
- 提高那些被前一轮弱分类器错误分类样本的权重，降低那些被正确分类样本的权重。这样一来，那些没有得到正确分类的数据，由于权值的加大而受到后一轮的弱分类器的更大关注。
- 加权多数表决，加大分类器误差小的弱分类器的权值，使其在表决中起较大的作用，减小分类误差大的弱分类器的权值，使其在表决中起较小的作用。
与一些早期的提升方法不同，AdaBoost具有适应性，即它能适应弱分类器各自的训练误差率。这也是它名称的由来，Ada是Adaptive的简写。
算法
- 输入：训练数据集T=(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)，其中x_i\in\mathcal{X}\subseteq\mathbb{R}^n,y_i\in\{+1,-1\}，弱学习算法
- 输出：最终分类器G(x)
过程为：
（1）初始化训练数据的权值分布
::: align-center
D_1=(\omega_{11},\omega_{12},\cdots,\omega_{1N}),\omega_{1i}=\frac{1}{N},i=1,2,\cdots,N
:::
这里假设了数据具有均匀的权值分布，每个样本在基分类器的学习作用相同。
（2）对m=1,2,\cdots,M
（a）用权值分布为D_m的训练数据进行学习，得到基分类器G_m(x): \mathcal{X}\mapsto\{+1,-1\}
（b）计算G_m(x)在训练集上的分类误差率
::: align-center
e_m=\sum_{i=1}^NP(G_m(x_i)\ne y_i)=\sum_{G_m(x_i)\ne y_i}\omega_{mi}
:::
\omega_{mi}表示第m轮中第i个实例的权值，\sum_{i=1}^N\omega_{mi}=1
（c）计算G_m(x)的系数\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}，对数为自然对数，\alpha_m表示G_m(x)在最终分类器中的重要性，e_m\le0.5时\alpha_m\ge 0（该分类器比随便猜测50%-50%好），而且\alpha_m随着e_m的减小而增大，分类误差越小的基分类器在最终分类器中的作用越大。
（d）更新训练集的权值分布，为下一轮做准备
::: align-center
\begin{aligned}
&D_{m+1}=(\omega_{m+1,1},\cdots,\omega_{m+1,i},\omega_{m+1,N})\\
&\omega_{m+1,i}=\left\{ \begin{matrix}
\frac{\omega_{mi}}{Z_m}e^{-\alpha_m} & G_m(x_i)\ne y_i\\
\frac{\omega_{mi}}{Z_m}e^{\alpha_m} & G_m(x_i)= y_i
\end{matrix}(*)
\right .
\end{aligned}
:::
其中Z_m为规范化因子
::: align-center
Z_m=\sum_{i=1}^N\omega_{mi}exp(-\alpha_m y_iG_m(x_i))
:::
误分类样本权值变大，正确分类样本权值缩小，两相比较放大了\frac{1-e_m}{e_m}倍
（3）构建基分类器的线性组合
::: align-center
f(x)=\sum_{m=1}^M\alpha_mG_m(x)
:::
最终分类器为
::: align-center
G(x)=sign(f(x))
:::
注意\alpha_m之和不为1
误差分析*
AdaBoost最基本的性质是它能在学习过程中不断减少训练误差。
定理（AdaBoost的训练误差界）：AdaBoost算法最终分类器的训练误差界为
::: align-center
\frac{1}{N}\sum_{i=1}^N I(G(x_i)\ne y_i)\le\frac{1}{N}exp(-y_if(x_i))=\prod_mZ_m
:::
证明：
当G(x_i)\ne y_i时,y_if(x_i)<0，所以exp(-y_if(x_i))\ge 1,推导出前半部分
后半部分用到（*）的变形
::: align-center
\omega_{mi}exp(-\alpha_m y_iG(x_i))=Z_m\omega_{m+1,i}
:::
推导如下：
::: align-center
\begin{aligned}
&\frac{1}{N}exp(-y_if(x_i))\\
&=\frac{1}{N}exp(-\sum_{m=1}^M\alpha_iy_iG(x_i))\\
&=\sum_{i}\omega_{1i}\prod_{m=1}^M exp(\alpha_iy_iG(x_i))\\
&=Z_1\sum_{i}\omega_{2i}\prod_{m=2}^M exp(\alpha_iy_iG(x_i))\\
&=Z_1Z_2\sum_{i}\omega_{3i}\prod_{m=3}^M exp(\alpha_iy_iG(x_i))\\
&=\cdots\\
&=Z_1Z_2\cdots Z_{m-1}\sum_{i}\omega_{mi} exp(\alpha_iy_iG(x_i))\\
&=\prod_{m=1}^MZ_m
\end{aligned}
:::
这一定理说明，可以在每一轮选取恰当的G_m(x)使得Z_m最小，从而使训练误差下降最快。
定理（二分类问题AdaBoost的训练误差界）：
::: align-center
\begin{aligned}
&\prod_{m=1}^MZ_m\\
&=\prod_{m=1}^M[2\sqrt{e_m(1-e_m)}]\\
&=\prod_{m=1}^M\sqrt{1-4\gamma_m^2}\\
&\le exp(-2\sum_{m=1}^M\gamma_m^2)
\end{aligned}
:::
这里\gamma_m=\frac{1}{2}-e_m
证明：
::: align-center
\begin{aligned}
&\prod_{m=1}^MZ_m\\
&=\sum_{i=1}^N\omega_{mi}exp(-\alpha_iy_iG(x_i))\\
&=\sum_{y_i=G(x_i)}\omega_{mi}e^{-\alpha_m}+\sum_{y_i\ne G(x_i)}\omega_{mi}e^{\alpha_m}\\
&=(1-e_m)e^{-\alpha_m}+e_me^{\alpha_m}\\
&=2\sqrt{(1-e_m)e^{-\alpha_m}e_me^{\alpha_m}}(AM-GM)\\
&=2\sqrt{e_m(1-e_m)}\\
&=\sqrt{1-4\gamma_m^2}
\end{aligned}
:::
其中在倒数第三步使用到了基本不等式，取等号条件（此时可推导出最优权重\alpha_m就是\frac{1}{2}\log\frac{1-e_m}{e_m}）
至于不等式
::: align-center
\sqrt{1-4\gamma_m^2}\le exp(-2\gamma_m^2)
:::
可由(e^{-2x^2})^2在x=0时的泰勒级数得到(e^{-2x^2})^2\ge 1-4x^2，开根后得到结果
推论：若存在\gamma>0，对所有m有\gamma_m\ge\gamma，则
::: align-center
\frac{1}{N}\sum_{i=1}^NI(y_i\ne G(x_i))\le exp(-2M\gamma^2)
:::
这表明在此条件下AdaBoost的训练误差是以指数速率下降的，这一性质当然很有吸引力。
AdaBoost算法的解释*
前向分步算法
考虑加法模型
::: align-center
f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)
:::
其中b(x;\gamma_m)为基函数，\beta_m为其系数
在给定训练集和损失函数的前提下，通过经验风险极小化学习f(x)
::: align-center
\min_{\beta_m,\gamma_m}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))
:::
通常这是一个复杂的优化问题。前向分步算法求解这一优化问题的想法是：从前向后，每一步只学习一个基函数及其系数，即
::: align-center
\min_{\beta,\gamma}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta b(x_i;\gamma))
:::
逐步逼近优化上面的目标函数式，那么就可以简化优化的复杂度。
前向分步算法与AdaBoost
可认为AdaBoost是模型为加法模型，损失函数为指数函数，学习算法为前向分步算法时的二分类学习方法。
由前向分步算法可以推导出AdaBoost，用定理叙述这一关系。
定理：AdaBoost算法是前向分步加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。
证明：
AdaBoost的最终分类器为f(x)=\sum_{i=1}^M\alpha_mG_m(x)，前向分步算法逐一学习基函数，这一过程与AdaBoost算法逐一学习基分类器一致。
下面证明前向分步算法的损失函数是指数损失函数
::: align-center
L(y,f(x))=exp[-yf(x)]
:::
在第m轮迭代时得到
::: align-center
f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)
:::
目标是使前向分步算法得到的\alpha_m和G_m(x)使f_m(x)在训练数据集T上的指数损失最小，即
::: align-center
(\alpha_m,G_m(x))=\arg\min_{\alpha,G}\sum_{i=1}^Nexp[-y_i(f_{m-1}(x_i)+\alpha G(x_i)]
:::
注意：与逻辑斯蒂回归（对数损失，对数上升）和SVM（Hinge损失，线性增长），AdaBoost采用了指数损失，它的优点在于利用了指数增长爆炸的特性，使得分类器的组合对于分类错误值异常敏感。采用更为敏感的损失函数，有利于AdaBoost更好的级联弱学习的分类器
它也可以表示为
::: align-center
(\alpha_m,G_m(x))=\arg\min_{\alpha,G}\sum_{i=1}^N\overline{\omega}_{mi} exp[\alpha G(x_i)]
:::
其中\overline{w}_{mi}=exp[-y_if_{m-1}(x_i)]，它与\alpha,G的优化无关，但其依赖与f_{m-1}(x)，这意味着它会随着每一次迭代而改变
对任意\alpha>0，可以使得上式最小的G(x)可由下式得到
::: align-center
G^*_m(x)=\arg\min_G\sum_{i=1}^N\overline{\omega}_{mi}I(y_i\ne G(x_i))
:::
此分类器即为AdaBoost算法的基本分类器G_m(x)，因为它是使第m轮加权训练数据分类误差率最小的基本分类器。
至于\alpha的最优解\alpha_m^*，在之前推导误差界时已经给出了使误差不大于上界时的解，现在我们正式给出最优解的求解过程
::: align-center
\begin{aligned}
&\sum_{i=1}^N\overline{\omega}_{mi} exp[\alpha G(x_i)]\\
&=\sum_{y_i=G(x_i)}\overline{\omega}_{mi}e^{-a}+\sum_{y_i\ne G(x_i)}\overline{\omega}_{mi}e^{\alpha}\\
&=(e^{\alpha}-e^{-\alpha})\sum_{i=1}^N\overline{\omega}_{mi}I(y_i\ne G(x_i))+e^{-a}\sum_{i=1}^N\overline{\omega}_{mi}
\end{aligned}
:::
将已求得的G_{m}^*(x)代入上式，对\alpha求导并其等于0得
::: align-center
\alpha_m^*=\frac{1}{2}\log\frac{1-e_m}{e_m}
:::
其中e_m是分类误差率
::: align-center
e_m=\frac{\sum_{i=1}^N\overline{\omega}_{mi}I(y_i=G_m(x_i))}{\sum_{i=1}^N\overline{\omega}_{mi}}=\sum_{i=1}^N\overline{\omega}_{mi}I(y_i=G_m(x_i))
:::
这里的\alpha^*_m与AdaBoost算法2（c）步的\alpha_m^*完全一致，也是我们推导误差界时在（AM-GM）部分可以取等号的原因
最后再来看每一轮样本的权值更新
由f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)以及\overline{w}_{mi}=exp[-y_if_{m-1}(x_i)]可得
::: align-center
\overline{\omega}_{m,i+1}=\overline{\omega}_{mi}+exp[-y_i\alpha_mf_{m-1}(x_i)]
:::
这与AdaBoost算法第2（d）步的样本权值更新，只差规范化因子，因而等价。
提升树
简介
提升树被认为是统计学习中性能最好的方法之一。
提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树（Boosting Tree）。
提升树模型可以表示为决策树的加法模型：
::: align-center
f_M(x)=\sum_{m=1}^MT(x;\theta_m)
:::
其中T(x;\theta_m)为决策树，\theta_m为决策树的参数，M为树的个数
第m步的模型为f_m(x)=f_{m-1}(x)+T(x;\theta_m)
其中,f_m(x)为当前模型,通过经验风险极小化确定下一颗决策树的参数\theta_m
::: align-center
\hat{\theta}_m=\arg\min_{\theta_m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i,\theta_m))
:::
由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂。所以提升树是一个高功能的学习算法。
提升树的学习算法
下面讨论对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用指数损失的分类问题，用平方损失的回归问题，以及用一般损失的一般决策问题。
（1）对于二分类问题，只需将AdaBoost的基分类器限制为二分类树即可（e.g. CART分类树）。
（2）回归问题的提升树，将输入空间\mathcal{X}划分为J个互不相交的区域R_1,\cdots,R_J，并且在每个区域上确定输出的常量c_j，那么树可以表示为
::: align-center
T(x_i;\theta)=\sum_{j=1}^Jc_jI(I\in R_J)
:::
其中参数\theta=\{(R_1,c_1),(R_2,c_2),\cdots,(R_J,c_J)\}，表示树的区域划分和各区域上的常数。J是回归树的复杂度即叶结点个数。
下面我们给出一种计算上比较容易的前向分布算法
::: align-center
\begin{aligned}
&f_0(x)=0\\
&f_m(x)=f_{m-1}(x)+T(x;\theta_m),m=1,2,\cdots,M\\
&f_M(x)=\sum_{i=1}^MT(x;\theta_m)
\end{aligned}
:::
在前向分步算法的第m步，给定当前模型f_{m-1}(x)，需求解
::: align-center
\hat{\theta}_m=\arg\min_{\theta_m}L(y_i,f_{m-1}(x_i)+T(x_i;\theta_m))
:::
得到\hat{\theta}_m，即第m颗树的参数
当采用平方损失时
::: align-center
\begin{aligned}
&L(y,f_{m-1}(x)+T(x;\theta_m))\\
&=[y-f_{m-1}(x)-T(x;\theta_m)]^2\\
&=[r-T(x;\theta_m)]^2
\end{aligned}
:::
所以对于回归问题的提升树算法来说，只需简单的拟合当前模型的残差，也就是说，在学习新树T(x;\theta_m)的\theta_m（对于前面的CART回归树，\hat{c}）时，我们无需考虑原始训练数据，而只需要将上一个树f_{m-1}(x)对于训练集的残差作为训练集进行学习，之后将学习到的新树T(x;\theta_m)与前一步模型f_{m-1}(x)进行加和即可得到新的模型
梯度提升
提升树利用加法模型与前向分步算法实现学习的优化过程。当损失函数是平方损失和指数损失时，每一步优化是简单的。
但对一般损失函数而言，往往每一步优化并不容易。针对这一问题，Freidman提出了梯度提升（Gradient Boosting）算法。这是利用最速下降法的近似方法，其关键是利用损失函数的负梯度在当前模型的值
::: align-center
-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)}=f_{m-1}(x)
:::
作为回归问题提升树算法中残差的近似值，拟合一个回归树。
全部评论 (0)
暂无评论，快来抢沙发吧~