机器学习笔记（十一）AdaBoosting算法

MachineLearning

---

1. AdaBoost算法思想

AdaBoost算法是Adaptive Boost的简称，Boosting通过将一系列弱学习器组合起来，通过集成这些弱学习器的学习能力，得到一个强学习器。具体到AdaBoost算法，AdaBoost在之前学习器的基础上改变样本的权重，增加那些之前被分类错误的样本的比重，降低分类正确样本的比重，这样之后的学习器将重点关注那些被分类错误的样本。最后通过将这些学习器通过加权组合成一个强学习器，具体的，分类正确率高的学习器权重较高，分类正确率低的学习器权重较低。

2. AdaBoost详细算法

这里有几个地方的计算需要注意，一个是分类误差率的计算，一个是分类器系数的计算，还有就是权重向量的更新计算。
输入：
训练集$X = \{(x_1,y_1),(x_2,y_2),(x_3,y_3),..,(x_n,y_n)\}，x_i \in R^n，y_i \in\{0,1\}$
输出：最终学习器$G(x)$

1. 初始化权重向量$W_1 = (w_{11},w_{12},..,w_{1n}),w_{1i} = 1/n$;
2. 对于1,2,3...,M
3. 在权重向量$W_i$的基础上，以分类误差率最小化为目标训练弱分类器$G_m(X)$
4. 计算分类误差率 $$e_m = \sum_{i = 1}^nw_{mi}I(G_m(x_i) != y_i)$$

5. 计算分类器权重系数
   

   $$\alpha_m = \frac{1}{2}log(\frac{1}{e_m} - 1)$$ ，这是个递减函数，当分类错误率$e_m$越低，那么对应的分类器最终占得权重系数越大。

6. 更新权重向量
   

   $$w_{m+1,i} = \dfrac{1}{Z_m}(w_{m_i}*exp(-\alpha_m y_i G_m(x)))$$ ，其中$Z_n$是规范化系数，$Z_m = \sum_{i=1}^N(w_{mi}*exp(-\alpha_my_iG_m(x))$。

7. 线性组合成强学习器

   $$G(x) = sign(\sum_{i = 1}^M \alpha_mG_m(x))$$

3. AdaBoost的前向分步算法解释

前向分步算法是学习加法模型的算法。他的思路是，每一步在前一步的基础上，最小化经验风险，学习该步的基函数和系数。具体到AdaBoost算法就是：AdaBoost是模型是加法模型，学习算法是前向分步算法，损失函数是指数损失函数。
损失函数：

$$L(y,f(x)) = \sum_{i = 1}^NL(y_i,f_{m-1}(x_i)+\alpha G_m(x_i))$$
因为损失函数是指数损失函数，所以上式变成:
$$L(y,f(x)) = \sum_{i = 1}^N exp[-y_i(f_{m-1}(x_i)+\alpha G_m(x_i))]$$
因为$y_i$和$f_{m-1}(x_i)$都是已知的，设$w_{mi} = exp[-y_if_{m-1}(x_i)]$：
$$L(y,f(x)) = \sum_{i=1}^Nw_{mi}exp[-y_i\alpha G_m(x_i)]$$
将损失函数拆分为$y_i = G_m(x_i)$和$y_i != G_m(x_i)$两部分：
$$L(y,f(x)) = \sum_{y_i = G_m(x_i)}w_{m_i}e^{-\alpha} + \sum_{y_i!=G_m(x_i)}w_{mi}e^{\alpha}$$
$$= \sum_{i = 1}^{N}w_{mi}e^{-\alpha} + \sum_{y_i != G_m(x_i)}w_{mi}(e^\alpha - e^{-\alpha})$$
$$= e^{-\alpha}\sum_{i = 1}^{N}w_{mi} + (e^\alpha - e^{-\alpha})\sum_{i = 1}^Nw_{mi}I(y_i != G_m(x_i))$$
欲使损失函数L最小，L对$\alpha$求偏导并取0。可得：
$$-e^{-\alpha}\sum_{i = 1}^{N}w_{mi} + (e^\alpha + e^{-\alpha})\sum_{i = 1}^Nw_{mi}I(y_i != G_m(x_i)) = 0$$
解得：$\alpha_m = \dfrac{1}{2}ln(\dfrac{\sum_{i = 1}^Nw_{mi}}{\sum_{i = 1}^Nw_{mi}I(y_i != G_m(x_i))} - 1)$

令$\dfrac{1}{e_m} = \dfrac{\sum_{i = 1}^Nw_{mi}}{\sum_{i = 1}^Nw_{mi}I(y_i != G_m(x_i))} = \dfrac{1}{\sum_{i = 1}^N \bar {w_{mi}}I(y_i != G_m(x_i))}$

显而易见，$e_m$就是错误率，这与前面的Adaboost算法是一致的。