Adaboost & 前向分布算法
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特点
- 优点:分类精度高;灵活的弱学习器;模型简单易解释;不易过拟合
- 缺点:异常值敏感
参考
李航 - 《统计学习方法》