這篇内容為《統計學習方法》的學習筆記，也看過其他書和教育訓練班的視訊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)