【李航统计学习笔记】第八章：adaboost

8.1 Adaboost

Boosting提升方法

基本思路

• 将弱可学习算法是升为强可学习算法。
• 其中提升方法是集成学习的一种
• 集成学习两个主要类别:
  • 序列方法
  • 并行方法

Adaboost算法

解分类问题 $y\in [-1,+1]$
在训练数据上训练得到模型，查看模型在整体数据和单个数据的分类 效果
在整体数据上分类效果较好，则该模型在最后的模型中占较大比例， 反之。
在单个数据上分类效果较好，那么在训练下一个模型时调小孩单个数
在上面过程迭代N次之后，直到最后的分类结果达到预期目标。将所有的模型组合，得到强可学习模型。

输入: 训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } 1 T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}_{1} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}1​ 其中 $x_i\in$ X ⊆ R n , y i ∈ Y = { − 1 , + 1 } X \subseteq R^{n}, y_{i} \in Y=\{-1,+1\} X⊆Rn,yi​∈Y={−1,+1}; 弱学习算法;

输出: 最终分类器 $G_{(x)}$
(1) 初始化训练数据的权值分布
$$D_1=\left({\omega }_{11},\cdots ,{\omega }_{1i},\cdots {\omega }_{1N}\right),{\omega }_{1i}=\frac{1}{N},i=1,2,\cdots ,N$$
(2) 对 $m=1,2\cdots ,M$
(2.1)使用具有权值分布 ${\mathrm{D}}_m$ 的训练数据集学习，得到基本分类器
G m ( x ) : X → { − 1 , + 1 } G_{m}(x): X \rightarrow\{-1,+1\} Gm​(x):X→{−1,+1}
(2.2)计算 $G_m(x)$ 在训㤽数据集上的分类误差率$e_m$
$$e_m=\sum _{i=1}^{N}P\left(G_m\left(x_i\right)\ne y_i\right)=\sum _{i=1}^N{\omega }_{mi}I\left(G_m\left(x_i\right)\ne y_i\right)$$
(2.3) 计算 ${\mathrm{G}}_m(x)$ 在训练数据集上的分类误差
$${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$$
这里的对数是自然对数
(2.4) 更新训练数据集的权值分布
D m + 1 = ( ω m + 1 , 1 , ⋯   , ω m + 1 , i , ⋯   , ω m + 1 , N ) ω m + 1 , i = ω m i Z m exp ⁡ ( − α m y i G m ( x i ) ) , i = 1 , 2 , ⋯   , N

Dm+1​=(ωm+1,1​,⋯,ωm+1,i​,⋯,ωm+1,N​)ωm+1,i​=Zm​ωmi​​exp(−αm​yi​Gm​(xi​)),i=1,2,⋯,N​
这里， $Z_m$ 是规范化因子
$$Z_m=\sum _{i=1}^N{\omega }_{mi}\exp \left(-{\alpha }_m{y}_i{G}_m\left(x_i\right)\right)$$
它使 $D_{m+1}$ 成为一个概率分布
(3)构建基本分类器的先行组合
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$
得到最终分类器
G ( x ) = sign ⁡ ( f ( x ) ) = sign ⁡ ( ∑ m = 1 M α m G m ( x ) )

G(x)=sign⁡(f(x))=sign⁡(∑m=1MαmGm(x))" role="presentation" style="position: relative;">G(x)=sign(f(x))=sign(∑m=1MαmGm(x))$$\begin{array}{c}G(x)=\mathrm{sign}(f(x))\\ =\mathrm{sign}\left(\sum _{m=1}^M{\alpha }_m{G}_m(x)\right)\end{array}$$

G(x)=sign(f(x))=sign(m=1∑M​αm​Gm​(x))​

提升树boosting tree

基本分类器：分类树或回归树

提左树模型：
$$f_M(x)=\sum _{m=1}^{M}T\left(x;{\Theta }_m\right)$$
前向分步算法:
f m ( x ) = f m − 1 ( x ) + T ( x ; Θ m ) Θ ^ m = arg ⁡ min ⁡ ∑ i = 1 N L ( y i , f m − 1 ( x i ) + T ( x i ; Θ m ) ) f 0 ( x ) = 0 f 1 ( x ) = f 0 ( x ) + T ( x ; Θ 1 ) 1 N ∑ i = 1 N L ( y i , f 1 ( x i ) )

​fm​(x)=fm−1​(x)+T(x;Θm​)Θ m​=argmini=1∑N​L(yi​,fm−1​(xi​)+T(xi​;Θm​))f0​(x)=0f1​(x)=f0​(x)+T(x;Θ1​)N1​i=1∑N​L(yi​,f1​(xi​))​
其中对于回归问题，一般为
$$L\left(y_i,f_1\left(x_i\right)\right)=\frac{1}{2}(y-f(x){)}^2$$

回归问题（平方误差损失）

算法8.3 (回忉问题的提升树方法)
输入: 训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)} ， 其中 $x_i\in X\subseteq R^n,y_i\in Y\subseteq {\mathrm{R}}_i$

输出: 提升树 $f_M(x)$
(1) 初始化 $f_0(x)=0$
(2) 对 $m=1,2，\cdots ,M$
(2.1)计算残差:
$$r_{mi}=y_i-f_{m-1}\left(x_i\right),i=1,2,\cdots ,N$$
(2.2)拟合残差 $r_{mi}$ 学习―个回归树，得到 $T\left(x;{\Theta }_m\right)$
(2.3) 更新 $f_m(x)=f_{m-1}(x)+T\left(x;{\Theta }_m\right)$

(3) 得到回归问题是升树
$$f_M(x)=\sum _{m=1}^{M}T\left(x;{\Theta }_m\right)$$
至于拟合残差的原因:
对于任意的样本点y和拟合值 $f(x)$ 的损失
L [ y , f ( x ) ] = [ y − f ( x ) ] 2

=​L[y,f(x)][y−f(x)]2​
在前项分布算法中
f m ( x ) = [ y − f m − 1 ( x ) − T ( x ; Θ m ) ] 2 = [ γ m − 1 − T ( x ; Θ m ) ] 2 = L ( γ m − 1 , T ( x ; Θ m ) )

fm(x)=[y−fm−1(x)−T(x;Θm)]2=[γm−1−T(x;Θm)]2=L(γm−1,T(x;Θm))" role="presentation" style="position: relative;">fm(x)===[y−fm−1(x)−T(x;Θm)]2[γm−1−T(x;Θm)]2L(γm−1,T(x;Θm))$$\begin{array}{rl}{f}_m(x)=& {\left[y-f_{m-1}(x)-T\left(x;{\mathrm{\Theta }}_m\right)\right]}^2\\ =& {\left[{\gamma }_{m-1}-T\left(x;{\mathrm{\Theta }}_m\right)\right]}^2\\ =& L\left({\gamma }_{m-1},T\left(x;{\mathrm{\Theta }}_m\right)\right)\end{array}$$

fm​(x)===​[y−fm−1​(x)−T(x;Θm​)]2[γm−1​−T(x;Θm​)]2L(γm−1​,T(x;Θm​))​

回归问题梯度提升：

算法8.4 (梯度提升算法)

输入: 训练数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ⋯   , ( x N , y N ) } 1 T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}_{1} T={(x1​,y1​),(x2​,y2​),⋯,(xN​,yN​)}1​, 其 中 $x_i\in X\subseteq R^n,y_i\in Y\subseteq {\mathrm{R}}_i$;损失函数$L(y,f(x))$

输出：回归树 $\hat{f}(x)$

(1)初始化
$$f_0(x)=\arg \underset{c}{\min }\sum _{i=1}^{N}L\left(y_i,c\right)$$
(2)对于 $m=1,2,\cdots ,M$
(2.1) 对i $i=1,2,\cdots ,N$,计算
$$r_{mi}=-{\left[\frac{\partial L\left(y_i,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]}_{f(x)=f_{m-1}(x)}$$
(2.2) 对 $r_{mi}$ 拟合拟合一个回归树，得到 第棵树的叶节点区域 ${\mathrm{R}}_{mj},j=1,2,\cdots ,J$
(2.3) 对j $=1,2,\cdots ,J$, 计箿
$$c_{mj}=\arg \underset{c}{\min }\sum _{x_i\in R_{mj}}L\left(y_i,f_{m-1}\left(x_i\right)+c\right)$$
(2.4) 更新
$$f_m(x)=f_{m-1}(x)+\sum _{j=1}^J{c}_{mj}I\left(x\in R_{mj}\right)$$
(3) 得到回归树
$$\hat{f}(x)=f_M(x)=\sum _{m=1}^M\sum _{j=1}^J{c}_{mj}I\left(x\in R_{mj}\right)$$

总结

1. 提升算法采用了多个弱模型结合达到一个强模型的效果
2. AdaBoost每次训练的分类器将重点关注于之前仍然被错分的样本。
3. 以决策树为基函数的提升方法被称为提升树

8.2 前向分步部算法

前向分步算法

前向分步算去求解诣数函数为损佚函数的氻法模型与Adabost的关系 结论: 两者是等价的
$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x),G_m(x)\in [-1,+1]$$
损失函数
$$L(y,f(x))=\exp (-yf(x))$$
假没经过m-1轮迭代，前向分步算刧已经得到
$$f_{m-1}(x)=\sum _{j=1}^{m-1}{\alpha }_j{G}_j(x)$$
那么
f m ( x ) = f m − 1 ( x ) + α m G m ( x ) α m , G m ( x ) = arg ⁡ min ⁡ α , G ∑ i = 1 N exp ⁡ [ − y i ( f m − 1 ( x i ) + α G ( x i ) ) ] = arg ⁡ min ⁡ α , G ∑ i = 1 N ω m i ‾ exp ⁡ [ − y i α G ( x i ) ] = arg ⁡ min ⁡ α , G ∑ i ∈ M 1 ω m i ‾ exp ⁡ ( − α ) + arg ⁡ min ⁡ α , G ∑ i ∈ M 2 ω m i ‾ exp ⁡ ( α )

fm​(x)αm​,Gm​(x)​=fm−1​(x)+αm​Gm​(x)=argα,Gmin​i=1∑N​exp[−yi​(fm−1​(xi​)+αG(xi​))]=argα,Gmin​i=1∑N​ωmi​​exp[−yi​αG(xi​)]=argα,Gmin​i∈M1​∑​ωmi​​exp(−α)+argα,Gmin​i∈M2​∑​ωmi​​exp(α)​
其中 $M_1$ 是止确分类， $M_2$ 是错误分类
arg ⁡ min ⁡ α , G ∑ i ∈ M 1 ω m i ‾ exp ⁡ ( − α ) + arg ⁡ min ⁡ α , G ∑ i ∈ M 2 ω m i ‾ exp ⁡ ( − α ) + arg ⁡ min ⁡ α , G ∑ i ∈ M 2 ω m i ‾ ( exp ⁡ ( α ) − exp ⁡ ( − α ) ) = exp ⁡ ( − α ) ∑ i ω m i ‾ + [ exp ⁡ ( α ) − exp ⁡ ( − α ) ] ∑ ω m i ‾ I ( y i ≠ G ( x i ) )

arg⁡minα,G∑i∈M1ωmi¯exp⁡(−α)+arg⁡minα,G∑i∈M2ωmi¯exp⁡(−α)+arg⁡minα,G∑i∈M2ωmi¯(exp⁡(α)−exp⁡(−α))=exp⁡(−α)∑iωmi¯+[exp⁡(α)−exp⁡(−α)]∑ωmi¯I(yi≠G(xi))" role="presentation" style="position: relative;">argminα,G=∑i∈M1ωmi¯¯¯¯¯¯¯¯exp(−α)+argminα,G∑i∈M2ωmi¯¯¯¯¯¯¯¯exp(−α)+argminα,G∑i∈M2ωmi¯¯¯¯¯¯¯¯(exp(α)−exp(−α))exp(−α)∑iωmi¯¯¯¯¯¯¯¯+[exp(α)−exp(−α)]∑ωmi¯¯¯¯¯¯¯¯I(yi≠G(xi))$$\begin{array}{rl}\arg \underset{\alpha ,G}{min}& \sum _{i\in M_1}\overline{{\omega }_{mi}}\exp (-\alpha )+\arg \underset{\alpha ,G}{min}\sum _{i\in M_2}\overline{{\omega }_{mi}}\exp (-\alpha )+\\ & \arg \underset{\alpha ,G}{min}\sum _{i\in M_2}\overline{{\omega }_{mi}}(\exp (\alpha )-\exp (-\alpha ))\\ =& \exp (-\alpha )\sum _i\overline{{\omega }_{mi}}+[\exp (\alpha )-\exp (-\alpha )]\sum \overline{{\omega }_{mi}}I\left(y_i\ne G\left(x_i\right)\right)\end{array}$$

argα,Gmin​=​i∈M1​∑​ωmi​​exp(−α)+argα,Gmin​i∈M2​∑​ωmi​​exp(−α)+argα,Gmin​i∈M2​∑​ωmi​​(exp(α)−exp(−α))exp(−α)i∑​ωmi​​+[exp(α)−exp(−α)]∑ωmi​​I(yi​=G(xi​))​
得到G的最优解
$$G_m^{\ast }=\mathrm{argmin}\sum _i\overline{{\omega }_{mi}}I\left(y_i\ne G\left(x_i\right)\right)$$
接下来求$\alpha$的最优解
α m = arg ⁡ min ⁡ α ∑ i ω m i ‾ exp ⁡ ( − α y i G ∗ ( x i ) ) = ∑ i ∈ M 1 ω m i ‾ exp ⁡ ( − α ) + ∑ i ∈ M 2 ω m i ‾ exp ⁡ ( α ) = ( e α − e − α ) ∑ ω m i ‾ I ( y i ≠ G ( x i ) ) + e − α ∑ ω m i ‾

αm=arg⁡minα∑iωmi¯exp⁡(−αyiG∗(xi))=∑i∈M1ωmi¯exp⁡(−α)+∑i∈M2ωmi¯exp⁡(α)=(eα−e−α)∑ωmi¯I(yi≠G(xi))+e−α∑ωmi¯" role="presentation" style="position: relative;">αm=argminα∑iωmi¯¯¯¯¯¯¯¯¯exp(−αyiG∗(xi))=∑i∈M1ωmi¯¯¯¯¯¯¯¯exp(−α)+∑i∈M2ωmi¯¯¯¯¯¯¯¯exp(α)=(eα−e−α)∑ωmi¯¯¯¯¯¯¯¯I(yi≠G(xi))+e−α∑ωmi¯¯¯¯¯¯¯¯$$\begin{array}{c}{\alpha }_m=\arg \underset{\alpha }{min}\sum _i\overline{\omega m_i}\exp \left(-\alpha y_i{G}^{\ast }\left(x_i\right)\right)\\ =\sum _{i\in M_1}\overline{{\omega }_{mi}}\exp (-\alpha )+\sum _{i\in M_2}\overline{{\omega }_{mi}}\exp (\alpha )\\ =\left(e^{\alpha }-e^{-\alpha }\right)\sum \overline{{\omega }_{mi}}I\left(y_i\ne G\left(x_i\right)\right)+e^{-\alpha }\sum \overline{{\omega }_{mi}}\end{array}$$

αm​=argαmin​i∑​ωmi​​exp(−αyi​G∗(xi​))=i∈M1​∑​ωmi​​exp(−α)+i∈M2​∑​ωmi​​exp(α)=(eα−e−α)∑ωmi​​I(yi​=G(xi​))+e−α∑ωmi​​​
将得到的式子对 $\alpha$ 求导并使导数为 0 。即
$\left(e^{\alpha }+e^{-\alpha }\right)\sum \bar{\omega }I\left(y_i\ne G\left(x_i\right)\right)-e^{-\alpha }\bar{\omega }=0$
e 2 α = ∑ ω i ‾ ∑ ω i ‾ I ( y i ≠ G ( x i ) ) − 1 α = 1 2 ln ⁡ ∑ ω i ‾ − ∑ ω ˉ I ( y i ≠ G ( x i ) ) ∑ ω ˉ I ( y i ≠ G ( x i ) ) = 1 2 ln ⁡ 1 − ∑ ω ˉ I ( y i ≠ G ( x i ) ) ∑ ω i ‾ ∑ ω ˉ I ( y i ≠ G ( x i ) ) ∑ ω i ‾ = 1 2 ln ⁡ 1 − e m e m

e2α=∑ωi¯∑ωi¯I(yi≠G(xi))−1α=12ln⁡∑ωi¯−∑ω¯I(yi≠G(xi))∑ω¯I(yi≠G(xi))=12ln⁡1−∑ω¯I(yi≠G(xi))∑ωi¯∑ω¯I(yi≠G(xi))∑ωi¯=12ln⁡1−emem" role="presentation" style="position: relative;">e2α=∑ωi¯¯¯¯¯∑ωi¯¯¯¯¯I(yi≠G(xi))−1α=12ln∑ωi¯¯¯¯¯−∑ω¯I(yi≠G(xi))∑ω¯I(yi≠G(xi))=12ln1−∑ω¯I(yi≠G(xi))∑ωi¯¯¯¯¯∑ω¯I(yi≠G(xi))∑ωi¯¯¯¯¯=12ln1−emem$$\begin{array}{c}{e}^{2\alpha }=\frac{\sum \overline{{\omega }_i}}{\sum \overline{{\omega }_i}I\left(y_i\ne G\left(x_i\right)\right)}-1\\ \alpha =\frac{1}{2}\ln \frac{\sum \overline{{\omega }_i}-\sum \overline{\omega }I\left(y_i\ne G\left(x_i\right)\right)}{\sum \overline{\omega }I\left(y_i\ne G\left(x_i\right)\right)}\\ =\frac{1}{2}\ln \frac{1-\frac{\sum \overline{\omega }I\left(y_i\ne G\left(x_i\right)\right)}{\sum \overline{{\omega }_i}}}{\frac{\sum \overline{\omega }I\left(y_i\ne G\left(x_i\right)\right)}{\sum \overline{{\omega }_i}}}\\ =\frac{1}{2}\ln \frac{1-e_m}{e_m}\end{array}$$

e2α=∑ωi​​I(yi​=G(xi​))∑ωi​​​−1α=21​ln∑ωˉI(yi​=G(xi​))∑ωi​​−∑ωˉI(yi​=G(xi​))​=21​ln∑ωi​​∑ωˉI(yi​=G(xi​))​1−∑ωi​​∑ωˉI(yi​=G(xi​))​​=21​lnem​1−em​​​

ω m i ‾ = exp ⁡ ( − y i f m − 1 ( x i ) ) = exp ⁡ ( − y i ∑ j = 1 m − 1 α j G j ( x ) ) = ∏ j exp ⁡ ( − y i α j G j ( x i ) )

​ωmi​​=exp(−yi​fm−1​(xi​))=exp(−yi​j=1∑m−1​αj​Gj​(x))=j∏​exp(−yi​αj​Gj​(xi​))​

总结

1. AdaBoost算法的一个解释是该算法实际是前向分步算法的一个实现。
2. 对于AdaBoost而言，模型是加法模型，损失函数是指数损失，算法是前向分步算法。