这篇内容为《统计学习方法》的学习笔记，也看过其他书和培训班的视频ppt等，但是感觉都是离不开《统计学习方法》这本书，还是这本书读起来干净利落（虽然有很少的地方有点晕）。
接下来首先介绍加法模型和前向分步算法，接着介绍提升树，最后补充梯度提升方法。
1、加法模型和前向分步算法
考虑以下线性组合的模型
f ( x ) = ∑ m = 1 M β m b ( x ; θ m ) f(x)=\sum\limits_{m=1}^{M}\beta_mb(x;\theta_m) f(x)=m=1∑Mβmb(x;θm)
其中 β m \beta_m βm为系数， θ m \theta_m θm为模型参数，上面的模型显然就是加法模型。
当给定训练集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\} T={(x1,y1),(x2,y2),...,(xn,yn)}，以及损失函数 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x))， y = { − 1 , + 1 } y=\{-1,+1\} y={−1,+1},学习算法通常就是求经验风险极小化（或者说损失函数极小化）：
min β m , θ m ∑ i = 1 n L ( y i , f ( x i ) ) = min ∑ i = 1 n L [ y i , ∑ m = 1 M β m b ( x i ; θ m ) ] \min\limits_{\beta_m,\theta_m} \sum\limits_{i=1}^{n}L(y_i,f(x_i))=\min \sum\limits_{i=1}^{n}L[y_i,\sum\limits_{m=1}^{M}\beta_mb(x_i;\theta_m)] βm,θmmini=1∑nL(yi,f(xi))=mini=1∑nL[yi,m=1∑Mβmb(xi;θm)]
该优化问题存在两个求和，求解比较困难，由于是加法模型，所以可以使用前向分步算法：每次只学习一个基函数及其系数（ b ( x ; θ m ) , β m b(x;\theta_m),\beta_m b(x;θm),βm），逐步逼近优化目标函数。具体地，每步只需优化如下损失函数
min β , θ ∑ i = 1 n L [ y i , β b ( x i ; θ ) ] \min\limits_{\beta,\theta}\sum\limits_{i=1}^{n}L[y_i,\beta b(x_i;\theta)] β,θmini=1∑nL[yi,βb(xi;θ)]
具体的前向分步算法如下
前向分步算法
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\} T={(x1,y1),(x2,y2),...,(xn,yn)}，损失函数 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x))，基函数集 { b ( x ; θ ) } \{b(x;\theta)\} {b(x;θ)}
输出：加法模型 f ( x ) f(x) f(x)
（1）、初始化 f 0 ( x ) = 0 f_0(x)=0 f0(x)=0；
（2）、对 m = 1 , 2 , … , M m=1,2,\dots,M m=1,2,…,M
（a）、极小化损失函数，获得参数 β m , θ m \beta_m,\theta_m βm,θm
( β m , θ m ) = a r g min β , θ ∑ i = 1 n L [ y i , f m − 1 ( x ) + β b ( x i ; θ ) ] (\beta_m,\theta_m)=arg\min\limits_{\beta,\theta}\sum\limits_{i=1}^{n}L[y_i,f_{m-1}(x)+\beta b(x_i;\theta)] (βm,θm)=argβ,θmini=1∑nL[yi,fm−1(x)+βb(xi;θ)]
（b）、更新加法模型
f m ( x ) = f m − 1 ( x ) + β m b ( x i ; θ m ) f_m(x)=f_{m-1}(x)+\beta_m b(x_i;\theta_m) fm(x)=fm−1(x)+βmb(xi;θm)
（3）、得到加法模型
f ( x ) = ∑ m = 1 M β m b ( x i ; θ m ) f(x)=\sum\limits_{m=1}^{M}\beta_m b(x_i;\theta_m) f(x)=m=1∑Mβmb(xi;θm)
2、提升树
提升树：是以分类树或回归树为基本分类器的提升方法。采用的加法模型（基函数的线性组合）与前向分步算法，以决策树（二叉分类树或者二叉回归树）为基函数的提升方法，三点：
- 基函数为决策树
- 模型为加法模型
- 学习方法为前向分步算法
2.1、提升树模型
具体地，提升树模型可以表示为下面的加法模型
f M ( x ) = ∑ m = 1 M T ( x ; θ m ) f_M(x)=\sum\limits_{m=1}^{M}T(x;\theta_m) fM(x)=m=1∑MT(x;θm)
T ( x ; θ m ) T(x;\theta_m) T(x;θm)表示决策树， θ m \theta_m θm为模型参数
2.2、提升树学习
提升树的学习算法是前面介绍的前向分步算法，下面来分析一下
第 m m m步的模型可以表示为:
f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m) fm(x)=fm−1(x)+T(x;θm)
通过损失函数最小化来求解每步的 θ m \theta_m θm
a r g min θ m ∑ i = 1 n L [ y i , f m − 1 ( x i ) + T ( x i ; θ m ) ] arg\min\limits_{\theta_m}\sum\limits_{i=1}^{n}L[y_i,f_{m-1}(x_i)+T(x_i;\theta_m)] argθmmini=1∑nL[yi,fm−1(xi)+T(xi;θm)]
关于分类树的提升算法使用Adaboost算法，将其中的基本分类器限制为二类分类树即可，下面介绍回归树学习算法。
假设输入空间被划分成了 R 1 , R 2 , … , R J R_1,R_2,\dots,R_J R1,R2,…,RJ区域（表示 J J J个叶节点），那么回归树模型可以表示为（具体的参考决策树）
T ( x ; θ ) = ∑ m = 1 J c m I ( x ∈ R m ) T(x;\theta)=\sum\limits_{m=1}^{J}c_mI(x\in R_m) T(x;θ)=m=1∑JcmI(x∈Rm)
参数 θ = { ( R 1 , c 1 ) , ( R 2 , c 2 ) , … , ( R J , c J ) } \theta=\{(R_1,c_1),(R_2,c_2),\dots,(R_J,c_J)\} θ={(R1,c1),(R2,c2),…,(RJ,cJ)}，表示划分的区域以及区域上的值 c c c。
使用前向分步算法有：
f 0 ( x ) = 0 f_0(x)=0 f0(x)=0
f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m) fm(x)=fm−1(x)+T(x;θm)
f M ( x ) = ∑ m = 1 M T ( x ; θ m ) f_M(x)=\sum\limits_{m=1}^{M}T(x;\theta_m) fM(x)=m=1∑MT(x;θm)
在第 m − 1 m-1 m−1步，通过极小化损失函数即得到参数 θ m \theta_m θm，从而得到第 m m m棵树的参数
a r g min θ m ∑ i = 1 n L [ y i , f m − 1 ( x i ) + T ( x i ; θ m ) ] arg\min\limits_{\theta_m}\sum\limits_{i=1}^{n}L[y_i,f_{m-1}(x_i)+T(x_i;\theta_m)] argθmmini=1∑nL[yi,fm−1(xi)+T(xi;θm)]
考虑损失函数为平方误差损失函数和一般损失函数情况，先讨论平方误差损失函数的情况。
L [ y , f m − 1 ( x ) + T ( x ; θ m ) ] = [ r m − T ( x ; θ m ) ] 2 L[y,f_{m-1}(x)+T(x;\theta_m)]=[r_m-T(x;\theta_m)]^2 L[y,fm−1(x)+T(x;θm)]=[rm−T(x;θm)]2
其中 r m = y − f m − 1 ( x ) r_m=y-f_{m-1}(x) rm=y−fm−1(x)，称为当前模型数据的残差。所以要求最小值对应的树模型 T ( x ; θ m ) T(x;\theta_m) T(x;θm)，只需要拟合参数即可。
下面给出具体的算法（使用平方误差损失函数）：
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\} T={(x1,y1),(x2,y2),...,(xn,yn)}
输出：提升树模型 f ( x ) f(x) f(x)
（1）、初始化 f 0 ( x ) = 0 f_0(x)=0 f0(x)=0；
（2）、对 m = 1 , 2 , … , M m=1,2,\dots,M m=1,2,…,M
（a）、针对每个 i = 1 , 2 , … , n i=1,2,\dots,n i=1,2,…,n 计算当前模型的残差（最初的时候参数就是当前数据）
r m i = y i − f m − 1 ( x i ) r_{mi}=y_i-f_{m-1}(x_i) rmi=yi−fm−1(xi)
（b）、拟合残差 r m i r_{mi} rmi学习到一棵回归树 T ( x ; θ m ) T(x;\theta_m) T(x;θm)
（c）、更新模型
f m ( x ) = f m − 1 ( x ) + T ( x ; θ m ) f_m(x)=f_{m-1}(x)+T(x;\theta_m) fm(x)=fm−1(x)+T(x;θm)
（3）、得到回归问题的提升树
f ( x ) = ∑ m = 1 M T ( x ; θ m ) f(x)=\sum\limits_{m=1}^{M}T(x;\theta_m) f(x)=m=1∑MT(x;θm)
为了便于理解，粘贴上《统计学习方法》中的例子。
3、梯度提升
前面介绍的是假设损失函数是平方误差损失函数的情况，如果损失函数是一般情况那么怎么学习呢？这里介绍一种梯度提升算法，该算法的关键是利用损失函数在负梯度在当前模型的值。
− [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) -[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} −[∂f(xi)∂L(yi,f(xi))]f(x)=fm−1(x)
将上式值作为回归问题提升树算法中残差的近似值，到时候去拟合它即可（相当于前面拟合 r m r_{m} rm）
梯度提升算法：
输入：训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) } T=\{(x_1,y_1),(x_2,y_2),...,(x_n,y_n)\} T={(x1,y1),(x2,y2),...,(xn,yn)}，损失函数 L ( y , f ( x ) ) L(y,f(x)) L(y,f(x))
输出：提升树模型 f ( x ) f(x) f(x)
（1）、初始化,用来估计使得损失函数极小化的常数值
f 0 ( x ) = arg min c ∑ i = 1 n L ( y i , c ) f_0(x)=\arg\min\limits_{c}\sum\limits_{i=1}^{n}L(y_i,c) f0(x)=argcmini=1∑nL(yi,c)；
（2）、对 m = 1 , 2 , … , M m=1,2,\dots,M m=1,2,…,M
（a）、对每个 i = 1 , 2 , … , n i=1,2,\dots,n i=1,2,…,n，计算近似残差
r m i = − [ ∂ L ( y i , f ( x i ) ) ∂ f ( x i ) ] f ( x ) = f m − 1 ( x ) r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)} rmi=−[∂f(xi)∂L(yi,f(xi))]f(x)=fm−1(x)
（b）、对 r m i , i = 1 , 2 , . . . , n r_{mi},i=1,2,...,n rmi,i=1,2,...,n（注意是n个 r r r值）进行拟合，得到回归树，得到第 m m m棵树的叶节点区域 R m j , j = 1 , 2 , . . . , J R_{mj},j=1,2,...,J Rmj,j=1,2,...,J，即 J J J个叶节点（这一步跟前面的提升树算法是一样的，只是前面省略掉了）
（c）、对 j = 1 , 2 , . . . , J j=1,2,...,J j=1,2,...,J，计算每个区域的常数值
c m j = arg min c ∑ x i ∈ R m j L ( y i , f m − 1 ( x i ) + c ) c_{mj}=\arg\min\limits_{c}\sum\limits_{x_i\in R_{mj}}L(y_i,f_{m-1}(x_i)+c) cmj=argcminxi∈Rmj∑L(yi,fm−1(xi)+c)
（d）、更新 f m ( x ) = f m − 1 ( x ) + ∑ j = 1 J c m j I ( x i ∈ R m j ) f_m(x)=f_{m-1}(x)+\sum\limits_{j=1}^{J}c_{mj}I(x_i\in R_{mj}) fm(x)=fm−1(x)+j=1∑JcmjI(xi∈Rmj)
（3）、得到回归树
f ( x ) = ∑ m = 1 M c m j I ( x i ∈ R m j ) f(x)=\sum\limits_{m=1}^{M}c_{mj}I(x_i\in R_{mj}) f(x)=m=1∑McmjI(xi∈Rmj)