Adaboost & 前向分布算法

Adaboost
前向分布算法
前向分布算法推导Adaboost
Adaboost特点

1. Adaboost

Adaboost提高那些被前一轮弱学习器错误分类样本的权值，而降低那些被正确分类样本的权值。这样没有正确分类的样本在下一轮学习中将获得更大的关注；之后Adaboost采用加权多数表决的方法，加大错误率低的弱学习器的权值，减小错误率高的弱学习器的权值。

1.1 Adaboost算法

输入：训练数据集\(T =\lbrace (x_1,y_1),(x_2,y_2),…,(x_n,y_n) \rbrace \)，其中\( x_i \in \chi \subseteq R^n, y_i \in \mathcal{y} = \lbrace -1, +1 \rbrace \)；弱学习器学习算法；

输出：最终的强学习器\(G(x)\)

（1）初始化训练数据的权值分布 \[ D_1 = (w_{11}, w_{12}, …, w_{1n}), \quad w_{1i}=\frac{1}{n}, \quad i=1,2,…,n \] 假设训练数据集具有均匀分布的权值分布，保证第1步能在原始数据集上学习弱学习器\(G_1(x)\)。

（2）对\(m=1,2,…,M\)

（2.1）使用具有权值分布\(D_m\)的训练数据集学习，得到基本分类器 \[ G_m(x):\chi \longrightarrow \lbrace -1,+1 \rbrace \]

（2.2）计算\(G_m(x)\)在训练数据集上的误差率 \[ e_m = \sum_{i=1}^n P(G_m(x_i) \not= y_i) = \sum_{i=1}^n w_{mi}I(G_m(x_i) \not= y_i) \]

（2.3）计算\(G_m(x_i)\)的系数 \[ \alpha_m = \frac{1}{2} ln \frac{1-e_m}{e_m} \] 这里可知，当\(e_m \leq \frac{1}{2}时，\alpha_m \geq 0\)，并且\(\alpha_m\)随着\(e_m\)的减小而增大，所以误差率小的弱学习器在最终的强学习器中具有更大的作用。当\( e_m > \frac{1}{2} \)算法停止。

（2.4）更新训练数据集的权值分布 \[ D_{m+1} = (w_{m+1,1}, w_{m+1,2}, …, w_{m+1,n}) \\ w_{m+1,i} = \frac{w_{mi}}{Z_m} exp(-\alpha_m y_i G_m(x_i)), \quad i=1,2,…,n \] 这里的\(Z_m\)是规范化因子，它使\(D_{m+1}\)成为一个概率分布。 \[ Z_m = \sum_{i=1}^n w_{mi} exp(-\alpha_m y_i G_m(x_i)) \]

（3）构建弱学习器的线性组合 \[ f(x) = \sum_{m=1}^M \alpha_m G_m(x) \] 得到最终强学习器 \[ G(x) = sign(f(x)) = sign( \sum_{m=1}^M \alpha_m G_m(x)) \]

Adaboost的例子见《统计学习方法》page,140.

Adaboost的另外一个解释：认为Adaboost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二类分类学习方法。

2. 前向分布算法

输入：训练数据集\(T=\lbrace (x_1,y_1),(x_2,y_2),…,(x_n,y_n) \rbrace\)；损失函数\(L(y,f(x))\)；基函数集\( \lbrace b(x;\gamma) \rbrace \)；

输出：加法模型\(f(x)\)。

（1）初始化\(f_0(x)=0\)

（2）对\(m=1,2,…,M\)

（2.1）极小化损失函数 \[ (\beta_m, \gamma_m) = \mathop{\arg\min_{\beta,\gamma}} \sum_{i=1}^n L(y_i, f_{m-1}(x_i)+\beta b(x_i;\gamma)) \] 得到参数\(\beta_m, \gamma_m\)。

（2.2）更新 \[ f_m(x) = f_{m-1}(x) + \beta_m b(x;\gamma_m) \]

（3）得到加法模型 \[ f(x) = f_M(x) = \sum_{i=1}^M \beta_m b(x;\gamma_m) \]

这样，前向分布算法将同时求解\(m=1\)到\(M\)所有参数\(\beta_m, \gamma_m\)的优化问题简化为逐次求解各个\(\beta_m, \gamma_m\)的优化问题。

3. 前向分布算法推导Adaboost

前向分布算法学习的是加法模型，所以该加法模型等价于Adaboost的最终的强学习器 \[ f(x) = \sum_{m=1}^M \alpha_m G_m(x) \] 前向分步算法逐一学习基函数与Adaboost逐一学习弱分类器的过程一致。

下面证明前向分布算法的损失函数是指数损失函数时，其学习的具体操作等价于Adaboost算法学习的具体操作。 \[ L(y, f(x)) = exp[-y f(x)] \] 假设经过\(m-1\)轮迭代，前向分布算法得到\(f_{m-1}(x)\)： \[ \begin{equation} \begin{aligned} f_{m-1}(x) = & = f_{m-2}(x) + \alpha_{m-1}G_{m-1}(x) \\ & = \alpha_1 G_1(x) + … + \alpha_{m-1} G_{m-1}(x) \end{aligned} \end{equation} \]

在第\(m\)次迭代得到\(\alpha_m, G_m(x)和f_m(x)\)。 \[ f_m(x) = f_{m-1}(x) + \alpha_m G_m(x) \]

我们的目标是使用前向分步算法，得到\(\alpha_m, G_m(x)\)使\(f(x)\)在训练数据集上的指数损失最小，即 \[ (\alpha_m, G_m(x)) = \mathop{\arg\min_{\alpha, G}} \sum_{i=1}^n exp[-y_i (f_{m-1}(x_i) + \alpha G(x_i))] \] 重新整理\(式(16)\)得： \[ (\alpha_m, G_m(x)) = \mathop{\arg\min_{\alpha, G}} \sum_{i=1}^n \bar{w}_{mi} exp[-y_i \alpha G(x_i)] \] 其中\(\bar{w}_{mi} = exp[-y_i f_{m-1}(x_i)]\)，由于\(\bar{w}_{mi}\)既不依赖\(\alpha\)也不依赖于\(G\)，所以与最小化无关。

首先求\( G_m^{\ast} \)，对任意\(\alpha > 0\)，使\( 式(8.21) \)最小的\(G(x)\)由下式得到： \[ G_m^{\ast} = \mathop{\arg\min_G} \sum_{i=1}^n \bar{w}_{mi} I(y_i \not= G(x_i)) \] 之后求\(\alpha_m^{\ast}\)，令： \[ \begin{equation} \begin{aligned} W & = \sum_{i=1}^n \bar{w}_{mi} exp[ - y_i \alpha G(x_i)] \\ & = \sum_{y_i = G_m(x_i)} \bar{w}_{mi} e^{-\alpha} + \sum_{y_i \not= G_m(x_i)} \bar{w}_{mi} e^{\alpha} \\ & = e^{-\alpha} \sum_{y_i = G_m(x_i)} \bar{w}_{mi} + e^{\alpha} \sum_{y_i \not= G_m(x_i)} \bar{w}_{mi} \\ & = e^{-\alpha} \lbrace \sum_{i=1}^n \bar{w}_{mi} - \sum_{y_i \not= G_m(x_i)} \bar{w}_{mi} \rbrace + e^{\alpha} \sum_{y_i \not= G_m(x_i)} \bar{w}_{mi} \\ & = e^{-\alpha} \sum_{i=1}^n \bar{w}_{mi} + (e^{\alpha} - e^{-\alpha}) \sum_{i=1}^n \bar{w}_{mi} I(y_i \not= G_m(x_i)) \end{aligned} \end{equation} \] 将式\((18)\)求得的\( G_m^{\ast}(x) \)代入上式，对\(\alpha\)求导并令导数为零，即得： \[ \frac{\partial W}{\partial \alpha} = - e^{-\alpha} \sum_{i=1}^n \bar{w}_{mi} + (e^{\alpha} + e^{- \alpha}) \sum_{i=1}^n \bar{w}_{mi} I(y_i \not= G_m^{\ast}(x_i)) = 0 \\ \Downarrow \\ e^{-\alpha} \sum_{i=1}^n \bar{w}_{mi} = (e^{\alpha} + e^{- \alpha}) \sum_{i=1}^n \bar{w}_{mi} I(y_i \not= G_m^{\ast}(x_i)) \\ \Downarrow \\ \alpha_m^{\ast} = \frac{1}{2} log \frac{1-e_m}{e_m} \\ where, \quad e_m = \frac{\sum_{i=1}^n \bar{w}_{mi} I(y_i \not= G_m(x_i))}{\sum_{i=1}^n \bar{w}_{mi}} \] 这里的\(\alpha_m^{\ast}\)与Adaboost算法第(2.3)步的\(\alpha_m\)完全一致。

接下来求权值更新公式： \[ \begin{cases} f_m(x) = f_{m-1}(x) + \alpha_m G_m(x) \\ \bar{w}_{mi} = exp[-y_i f_{m-1}(x_i)] \end{cases} \quad \Longrightarrow \quad \bar{w}_{m+1,i} = \bar{w}_{m,i}exp[-y_i \alpha_m G_m(x)] \] 这与Adaboost算法的第(2.4)步的样本均值的更新，只相差规范化因子，因而等价。

4. Adaboost特点

优点：分类精度高；灵活的弱学习器；模型简单易解释；不易过拟合
缺点：异常值敏感

参考

李航 - 《统计学习方法》