AdaBoost

1. 什么是AdaBoost

   标准AdaBoost关注二分类问题，AdaBoost通过训练一系列的弱分类器来组成一个强分类器，每一轮训练时会提高前一轮弱分类器错误分类样本的权值，而降低那些被正确分类的样本的权值。模型最后的预测结果为各弱分类器预测结果的加权多数表决结果。

   AdaBoost算法具体流程：

   • 输入：训练数据集\(T={(x_1,y_1),(x_2,y_2),..,(x_N,y_N)}\)，其中\(x_i\in \mathbb{R}^n\)，\(Y_i\in \{-1,1\}\)；弱分类器算法（一般为树桩）；

   • 输出：最终分类器\(G(x)\).

   • 1. 初始化训练数据的权值分布为

        \(D_1=(w_{11},w_{12},...,w_{1N}),w_{1i}=\frac{1}{N}\)

     2. 对m=1,2,...,M（M为弱分类器数量）

        • 使用具有权值分布\(D_m\)的训练数据学习，得到第m个基分类器\(G_m(x)\)

        • 计算\(G_m(x)\)的分类误差率：

          \[e_m=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\ne y_i) \]

        • 计算\(G_m(x)\)的系数（权重）

          \[\alpha_m=\frac{1}{2}\ln \frac{1-e_m}{e_m} \]

        • 更新训练集数据权值分布

          \[D_{m+1}=(w_{m1},w_{m2},...,w_{mN}) \\ w_{mi}=\frac{w_{mi}e^{-\alpha_m y_iG(x_i)}}{Z_m} \\ Z_m=\sum_{i=1}^Nw_{mi}e^{-\alpha_m y_iG(x_i)} \]

        • 最终分类器

          \[G(x)=sign(\sum_{m=1}^M\alpha_mG_m(x)) \]

2. AdaBoost算法的解释

   AdaBoost算法可解释为模型是加法模型、损失函数为指数函数、学习算法为前向分步算法时的二分类学习算法。

   • 前向分步算法

     加法模型：

     \[f(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m) \]

     其中，\(b(x;\gamma_m)\)为基函数，\(\gamma_m\)为基函数参数，\(beta_m\)为基函数的系数，M为基函数的个数。

     学习加法模型\(f(x)\)即对经验风险极小化：

     \[\min_{\beta_m,\gamma_m}\sum_{i=1}^NL(y_i,\sum_{m=1}^M\beta_mb(x;\gamma_m)) \]

     通常这是一个复杂的优化问题，前向分布算法求解这一优化问题的想法是：从前往后每一步只学习一个基函数及其系数，逐步逼近最优解。具体地，每一步需要优化如下损失函数：

     \[\min_{\beta,\gamma}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+\beta b(x;\gamma)) \]

   • 前向分布算法与AdaBoost

     前向分步算法逐一学习基函数，这与AdaBoost算法逐一学习基本分类器的过程一致。

     当前向分步算法的损失函数为指数损失函数，即：

     \[L(y,f(x))=e^{-yf(x)} \]

     时，其学习的具体操作等价于AdaBoost算法学习的具体操作。

     假设经过m-1轮迭代前向分步算法已经得到：

     \[f_{m-1}(x)=\alpha_1G_1(x)+\alpha_2G_2(x)+...+\alpha_{m-1}G_{m-1}(x) \]

     在第m轮迭代得到\(\alpha_m,G_m(x)和f_m(x)=f_{m-1}(x)+\alpha_mG_m(x)\)，目标是希望得到：

     \[(\alpha_m,G_m(x))=\arg\min_{\alpha_m,G_m(x)}\sum_{i=1}^Ne^{-y_i(f_{m-1}(x_i)+\alpha_mG_m(x_i))} \]

     令\(\overline w_{mi}=e^{-y_if_{m-1}(x_i)}\)，则上式子可以化为：

     \[(\alpha_m,G_m)=\arg\min_{\alpha_m,G_m(x)}\sum_{i=1}^N\overline w_{mi}e^{-\alpha_my_iG_m(x_i)} \\ =\arg\min_{\alpha_m,G_m}e^{-\alpha_m}\sum_{y_i=G_m(x_i)}\overline w_{mi}+e^{\alpha_m}\sum_{y_i\ne G_m(x_i)}\overline w_{mi} \\ =\arg\min_{\alpha_m,G_m}e^{-\alpha_m}(\sum_{i=1}^N\overline w_{mi}-\sum_{y_i\ne G_m(x_i)}\overline w_{mi})+e^{\alpha_m}\sum_{y_i\ne G_m(x_i)}\overline w_{mi} \\ =\arg\min_{\alpha_m,G_m}e^{-\alpha_m}\sum_{i=1}^N\overline w_{mi}+(e^{\alpha_m}-e^{-\alpha_m})\sum_{y_i\ne G_m(x_i)}\overline w_{mi} \\ =\arg\min_{\alpha_m,G_m}e^{-\alpha_m}\sum_{i=1}^N\overline w_{mi}+(e^{\alpha_m}-e^{-\alpha_m})\sum_{i=1}^N\overline w_{mi}I(y_i\ne G_m(x_i)) \]

     对于固定的\(\alpha_m\)，上式中\(e^{-\alpha_m}\sum_{i=1}^N\overline w_{mi}\)和\(e^{\alpha_m}-e^{-\alpha_m}\)都是定值，则上式等价于：

     \[G_m^*=\arg\min_{G_m}\sum_{i=1}^N\overline w_{mi}I(y_i\ne G_m(x_i)) \]

     这与AdaBoost中要寻找的基本分类器一致。

     然后对\(\alpha_m\)求导并使其等于0，得：

     \[\alpha_m^*=\frac{1}{2}\ln \frac{1-e_m}{e_m} \\ e_m=\frac{\sum_{i=1}^N\overline w_{mi}I(y_i\ne G_m(x_i))}{\sum_{i=1}^N\overline w_{mi}} \]

     令\(w_{mi}=\frac{\overline w_{mi}}{\sum_{i=1}^N\overline w_{mi}}\)，得\(e_m=\sum_{i=1}^Nw_{mi}I(y_i\ne G_m(x_i))\)，这与AdaBoost一致。特别地，当\(m=0\)时，\(\overline w_{mi}=e^{-y_i*0}=1,w_{mi}=\frac{1}{N}=\frac{\overline w_{mi}}{\sum_{i=1}^N\overline w_{mi}}\)。

     由\(\overline w_{mi}=e^{-y_if_{m-1}(x_i)}\)以及\(f_m(x_i)==f_{m-1}(x)+\alpha_mG_m(x_i)\)得：

     \[\overline w_{m+1,i}=\overline w_{mi}e^{-y_i\alpha_mG_m(x_i)} \]

     由\(w_{m+1,i}=\frac{\overline w_{m+1,i}}{\sum_{i=1}^N\overline w_{m+1,i}}\)以及上式得：

     \[w_{m+1,i}=\frac{\overline w_{mi}e^{-y_i\alpha_mG_m(x_i)}}{\sum_{i=1}^N\overline w_{mi}e^{-y_i\alpha_mG_m(x_i)}} \\ =\frac{\frac{\overline w_{mi}}{\sum_{i=1}^N\overline w_{mi}}e^{-y_i\alpha_mG_m(x_i)}}{\sum_{i=1}^N\frac{\overline w_{mi}}{\sum_{i=1}^N\overline w_{mi}}e^{-y_i\alpha_mG_m(x_i)}} \\ =\frac{w_{mi}e^{-y_i\alpha_mG_m(x_i)}}{\sum_{i=1}^Nw_{mi}e^{-y_i\alpha_mG_m(x_i)}} \]

     与AdaBoost一致。

     综上，模型是加法模型、损失函数为指数函数、学习算法为前向分步算法时可以推导出AdaBoost。

   ?

AdaBoost

原文：https://www.cnblogs.com/lyq2021/p/14253860.html