提升方法boosting

本文是《统计学习方法》李航著学习笔记。现在的数据科学比赛中用到的算法大杀器GBDT(gradient boosting decision tree)终于要出场了！
提升方法的基本思想是将学习到的若干弱分类器组合形成强分类器，即sembling里的boosting思想。这里的弱分类器通常是同一类模型，比如都是决策树、或都是神经网络等，下面的论述中弱分类器是树形模型。有关决策树的内容参考http://blog.****.net/cymy001/article/details/78027083

不同问题的提升树学习算法主要区别在于选用的损失函数不同：
（a.）回归问题，用平方误差损失函数（eg.二差回归树提升算法）
（b.）分类问题，用指数损失函数（eg.AdaBoost）
（c.）一般决策问题，用一般损失函数（eg.GBDT）

利用boosting预测：

（1.）利用二类分类提升模型进行预测就是将训练实例点 $x_{i}$ 代入学习到的分类决策函数模型 $f(x)$ ，根据 $f(x_{i})$ 的取值正负决定点 $x_{i}$ 的类， $f(x_{i})$ 的绝对值表示分类的置信度。
（2.）利用回归树进行预测时就是判断训练实例点 $x_{i}$ 位于回归树 $\widehat{f}(x)$ 模型的哪个区间，根据对应区间找出 $\widehat{f}(x_{i})$ 的值。

boosting模型学习：

提升方法可用于分类问题和回归问题，模型学习过程大致如下：
（1.）在分类问题中，通过“改变训练样本集的权重分布”，再“对应每个训练样本集的权重分布学习一个分类器”，最后“将这些分类器根据分类误差率进行线性组合得到最终的决策模型，提高分类的性能”。
（2.）在回归问题中，以平方损失函数为目标，通过拟合“叠加的回归树与训练实例点标记值间的残差”学习回归树，最后的模型是学习到的各回归树的和。
本文下述主要是提升方法的模型学习过程。

分类问题的AdaBoost算法：

输入:二类分类训练数据集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{N},y_{N})\}$ ，其中 $x_{i}\in R^{n}，y_{i}\in\{1,-1\}$ ；某种弱学习算法(如决策树)
输出:强分类器 $G(x)$

(1)给定训练数据集 $T$ 的初始分布 $D_{1}=(w_{11},\cdots,w_{1i},\cdots,w_{1N})$ ，其中 $w_{1i}=\frac{1}{N},i=1,2,\cdots,N$
(2.)学习 $M$ 个弱分类器 $G_{m}(x),m=1,2,\cdots,M$ ：

对“具有分布 $D_{m}$ 的训练数据集”用“某种弱学习算法”学习到二类分类弱分类器 $G_{m}(x)$
$G_{m}(x)$ 在 $T$ 上的分类误差率
$e_{m}=P(G_{m}(x_{i})\neq y_{i})=\sum_{i=1}^{N}w_{mi}I(G_{m}(x_{i})\neq y_{i})$
弱分类器 $G_{m}(x)$ 的系数
$\alpha_{m}=\frac{1}{2}\ln\frac{1-e_{m}}{e_{m}}$
更新训练数据集 $T$ 的分布
$D_{m+1}=(w_{m+1,1},\cdots,w_{m+1,i},\cdots,w_{m+1,N})\\ w_{m+1,i}=\frac{w_{mi}}{Z_{m}}exp(-\alpha_{m}y_{i}G_{m}(x_{i})),i=1,2,\cdots,N$
其中，概率归一化因子 $Z_{m}=\sum\limits_{i=1}^{N}w_{mi}exp(-\alpha_{m}y_{i}G_{m}(x_{i}))$

（3.）由弱分类器 $G_{m}(x)$ 的线性组合构建强分类器 $G(x)$ :
$G(x)=sign(f(x))=sign\Big(\sum\limits_{m=1}^{M}\alpha_{m}G_{m}(x)\Big)$

将Adaboost算法看作前向分布算法，即每步学习一个基函数 $b(x;\gamma_{m})$ 及相应的系数 $\beta_{m}$ ，最终的强学习器是叠加 $m$ 次的加法模型 $\sum\limits_{m=1}^{M}\beta_{m}b(x;\gamma_{m})$ 。
损失函数为指数损失函数 $L(y,f(x))=exp[-y\sum\limits_{m=1}^{M}\beta_{m}b(x;\gamma_{m})]$ 。

以决策树为弱分类器的提升方法称为提升树：对分类问题，只需要在Adaboost算法中的第（2）步中对“具有分布 $D_{m}$ 的训练数据集”用“决策树”学习二类分类弱分类器 $G_{m}(x)$ ；对回归问题，根据加法原理和平方损失最小的目标构建残差拟合模型
$L\big(y,f_{m-1}(x)+T(x;\Theta_{m})\big)=\Big[y-f_{m-1}(x)-T(x;\Theta_{m})\Big]^2$
其中 $f_{m-1}(x)=\sum\limits_{j=1}^{m-1}T(x;\Theta_{j})$ ，残差项为 $r=y-f_{m-1}(x)$ ，每一步拟合残差利用的是回归树模型 $T(x;\Theta_{m})=\sum\limits_{j=1}^{J}c_{j}I(x\in R_{j})$ 。

回归问题的提升树算法：

输入:训练数据集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{N},y_{N})\}$ ，其中 $x_{i}\in R^{n}，y_{i}\in R$
输出:提升树 $f_{M}(x)$

（1.）初始化 $f_{0}(x)=0$
（2.）学习 $M$ 个弱回归树 $f_{m}(x),m=1,2,\cdots,M$ ：

分别计算 $i=1,2,\cdots,N$ 个训练实例点的残差
$r_{mi}=y_{i}-f_{m-1}(x_{i})$
拟合残差 $r_{mi}$ ，学习一个回归树 $T(x;\Theta_{m})$
更新组合树模型 $f_{m}(x)=f_{m-1}(x)+T(x;\Theta_{m})$

（3.）最终的回归提升树 $f_{M}(x)=\sum\limits_{m=1}^{M}T(x;\Theta_{m})$

注：这里没有改变数据集的分布，每次学习新的树模型时，拟合的是训练数据集对应的残差项。

GBDT：

针对一般损失函数，类似回归树的拟合残差，这里用损失函数的负梯度作为残差项。
输入:训练数据集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{N},y_{N})\}$ ，其中 $x_{i}\in R^{n}，y_{i}\in R$ ；损失函数 $L(y,f(x))$
输出:回归树 $f(x)$

（1.）初始化 $f_{0}(x)=arg\min\limits_{c}\sum\limits_{i=1}^{N}L(y_{i},c)$
（2.）学习 $M$ 个弱回归树 $f_{m}(x),m=1,2,\cdots,M$ ：

分别计算 $i=1,2,\cdots,N$ 个训练实例点的残差
$r_{mi}=-\Big[\frac{\partial L(y_{i},f_{m-1}(x_{i}))}{\partial f_{m-1}(x_{i})}\Big]$
拟合残差 $r_{mi}$ ，学习一个回归树 $\sum\limits_{j=1}^{J}c_{mj}I(x\in R_{mj})$ ：先生成树，即确定 $J$ 个叶结点数目，再对每个叶结点根据最小化损失函数选取 $c_{mj}$
更新组合树模型 $f_{m}(x)=f_{m-1}(x)+\sum\limits_{j=1}^{J}c_{mj}I(x\in R_{mj})$

（3.）最终的回归提升树 $f(x)=\sum\limits_{m=1}^{M}\sum\limits_{j=1}^{J}c_{mj}I(x\in R_{mj})$

注：GBDT算法中拟合残差生成回归树步里，生成树遍历选择切分点时，只需要一层遍历(因为拟合残差值是一维向量运算，维度上不需要遍历选取)，但是当构建的回归树不是二叉树时，切分点的选取组合遍历比二叉树时要复杂。有了切分点后，利用平方损失最小，在每个区间内的 $c_{mj}$ 通过求导易求得。