0.参考内容及思维导图链接

• 参考连接：AdaBoost 作者：老弓的学习日记
• 思维导图：https://github.com/QianJoe/Ensemble-Learning

1.集成学习

1.1 思想

集成学习通过构建并结合多个学习器来完成学习任务

1.1.1 类比

三个臭皮匠，顶个诸葛亮
如下图：

1.1.2 补充概念

在集成学习中，学习器相当于模型，又分为强学习器和弱学习器，弱分类器又叫基分类器。

强学习器：可以认为它是一种准确率很高但相对复杂的模型，比如一些神经网络构建出来的模型，它耗费时间精力多，对算力要求高，花费代价高；
弱学习器：可以认为它是一种比较简单的模型，预测效果不太好，如逻辑回归等简单的模型。
总结就是三个臭皮匠顶个诸葛亮

1.2 优点

集成学习通过将多个学习器进行结合，常常可以获得比单一学习器更加显著的优越性能。

1.3 需要关注的问题

1.3.1 个体学习器如何训练得到？

改变训练数据的权值或者概率分布，如何改变？
个体学习器就是弱学习器，多个弱学习器学到的东西必须是有所差异的，它们各自的强项不一样。

举例：

一个班级里有$G_1(x),\cdots ,G_n(x)$，其中$G_1(x)$语文好，$G_2(x)$英语好，$\cdots$，$G_n(x)$数学好，将他们各自好的学科组合起来，就可以抗衡学校里年级第一的学生了。

所以只需要让各学习器，学习不一样的数据就可以了，继续上面的例子

其中$G_1(x)$语文好，所以让$G_1(x)$侧重的去学习语文（花更多时间），$G_2(x)$英语好，所以让$G_2(x)$侧重的去学习英语，$\cdots$，$G_n(x)$数学好，所以让$G_n(x)$侧重的去学习数学。虽然所有学生各科目都学，但是确保发挥各个学生擅长，改变大家的侧重点，比如在固定学习时长中，增长其擅长科目所占时间。

这样相当于改变了训练数据的权值或者概率分布。

1.3.2 如何将个体学习器组合？

是通过线性相加，还是其他方法？
后面会详细说

1.4 分类

当训练和组合有不一样的办法时，就得到两种类别：

• boosting
• bagging

1.4.1 对于boosting

1.主要特点
个体学习器间存在强依赖关系、必须串行生成的序列化方法。

2.工作机制
也就是如何解决训练和组合问题：

• 1.提高那些在前一轮被弱分类器分错的样本的权值；减少那些在前一轮被弱分类器分对的样本的权值，使得误分的样本在后续受到更多的关注，体现了串行。
  举例：

如你有$3$个分身$A,B,C$，期末考试需要考语数英三门。在平时学习时，你先让$A$去学习语文，然后通过平时的测验发现$A$学习语文不错，但是学习数学和英语不行，这时，你可以派$B$去学习，减少对语文的学习的时间，增多数学和英语的时间，然后通过平时的测验发现$B$数学学的不错，这时你可以派$C$去学习，减少对数学和语文的学习的时间，增多英语的时间。

• 2.加法模型将弱分类器进行线性组合

3.四个问题

• 1.如何计算学习误差率$e_m$?
• 2.如何得到基学习器权重系数$\alpha$？
• 3.如何更新样本权重$w$?
• 4.使用何种结合策略？

1.4.2 对于bagging

1.特点
个体学习器间不存在强依赖关系，可同时生成的并行化方。

2.工作机制

• 1.从原始样本集中抽取k个训练集
  • 每轮从原始样本集中使用Boostraping法（自助法，是一种有放回的抽样方法，可能抽到重复的样本）抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中），共进行j轮抽取，得到k个训练集（k个训练集相互独立）。
  • 随机森林中，还会随机抽取一定数量的特征。
  • 举例：待补充。
• 2.k个训练集分别训练，共得到k个模型，体现了并行。
• 3.将上步得到的k个模型，通过一定方式组合起来
  • 分类问题：将上步得到的k个模型采用投票的方式得到分类结果。
  • 回归问题：计算上述模型的均值作为最后的结果。

3.代表
随机森林

2.Adaboost

Adaboost解决的是二分类问题。

2.1 参考资料

《机器学习方法》作者：李航

2.2 思路

2.2.1 数学表达

表达式
$$\begin{array}{rl}f(x)& =\sum _{m=1}^M{\alpha }_m{G}_m(x)\\ & ={\alpha }_1{G}_1(x)+\cdots +{\alpha }_m{G}_m(x)+\cdots +{\alpha }_M{G}_M(x)\end{array}$$

其中${\alpha }_m$由$G_m(x)$的"分类误差率"决定，训练样本$G_m(x)$：提高前一轮“错误分类”的样本的权值，降低前一轮“正确分类”的样本的权值。
注意到，${\alpha }_m$不是之前说的权重值，之前说的权值是$w_m$。

2.2.2 基本思路

1.每一轮中，分别记录好那些被当前弱分类器正确分类和错误分类的样本，在下一轮训练时，提高错误分类样本的权值，同时降低正确分类样本的权重，用以训练新的弱分类器。这样一来，那些没有被正确分类的数据，由于其权值加大，会受到后一轮的更大关注。

如何理解改变样本的权值?

举例：
初始有3个样本，即其所占比例
$D_1$：

样本	$(x_1,y_1)$	$(x_2,y_2)$	$(x_3,y_3)$
所占比例	$\frac{1}{3}$	$\frac{1}{3}$	$\frac{1}{3}$

经过一轮学习后，$G_1$分类器成功将$(x_2,y_2),(x_3,y_3)$分类成功，所以我们需要将这两个样本的权重降低，提高第一个样本的权值，即下面表格：

$D_2$：

样本	$(x_1,y_1)$	$(x_2,y_2)$	$(x_3,y_3)$
所占比例	$\frac{2}{3}$	$\frac{1}{6}$	$\frac{1}{6}$

所以增大权值相当于将初始样本中的错误分类的数量变多了，变成了这样：

$\{\begin{array}{l}(x_1,y_1)\\ (x_2,y_2)\\ (x_3,y_3)\end{array}$ $\to$ $\{\begin{array}{l}(x_1,y_1),(x_1,y_1),(x_1,y_1),(x_1,y_1)\\ (x_2,y_2)\\ (x_3,y_3)\end{array}$

2.加权多数表决

• 1.加大分类误差率小的弱分类器的权值${\alpha }_m$，使其在表决中起较大作用；
• 2.减少分类误差率大的弱分类器的权值${\alpha }_m$，使其在表决中起较小作用。

2.3 算法流程

2.3.1 基本流程

1.二分类训练数据集
$T=\{(x_1,y_1),\cdots ,(x_N,y_N)\}$，其中，每个样本点由实例与标记组成。实例$x_i\in \mathcal{X}\subseteq R^n$，标记 y i ∈ Y = { − 1 , + 1 } y_i\in \mathcal{Y}=\{-1,+1\} yi​∈Y={−1,+1}，$\mathcal{X}$是实例空间，$\mathcal{Y}$是标记集合。
2.定义基分类器（弱分类器）$G(x)$
大部分情况下，$G1\sim Gm$都是同一类型的分类器。
比如：$G_1(x)=\{\begin{array}{ll}1,& x<k\\ -1,& x>k\end{array}$，其中$k$为阈值
3.具体算法流程

1.初始化/更新当前训练数据的权值分布

• 如果是初始化： $D_1=(w_{11},w_{12},\cdots ,w_{1N}),w_{1i}=\frac{1}{N},i=1,2,\cdots ,N)$，初始化权值（这个是训练数据的权值，不是基分类器的）使用数量的平均值$\frac{1}{N}$。

• 如果是更新（不是第一次）：
  ，其中$w_{m,i}=\{\begin{array}{l}\frac{w_{m-1,i}}{Z_{m-1}}{e}^{-{\alpha }_{m-1}},G_{m-1}(x_i)=y_i\\ \frac{w_{m-1,i}}{Z_{m-1}}{e}^{{\alpha }_{m-1}},G_{m-1}(x_i)\ne y_i\end{array}$，由此可知，被基本分类器$G_m(x)$误分类样本的权值得以扩大（$e^{{\alpha }_{m-1}}>1$），而被正确分类样本的权值却在缩小（$e^{-{\alpha }_{m-1}}<1$）。规范化因子$Z_{m-1}$通俗地讲，是将更新后的权重之和归为 1，保证权重序列以一个离散的概率分布出现。

2.训练当前基分类器$G_m(x)$

使用具有权值分布$D_m$的训练数据集学习，得到基分类器$G_m(x)$。比如，你选择的是逻辑回归模型，就要交叉熵作为损失函数，用梯度下降作为优化方法来训练。

3.计算当前基分类器的权值${\alpha }_m$

• 1.先要计算当前$G_m(x)$在训练集上的分类误差率
  $e_m={\sum }_{i=1}^{N}P(G_m(x_i)\ne y_i)={\sum }_{i=1}^N{w}_{mi}I(G_m(x_i)\ne y_i)={\sum }_{G_m(x_i)\ne y_i}{w}_{mi}$，其中$I$为指示函数，$I=\{\begin{array}{ll}1,& G_m(x_i)\ne y_i\\ 0,& G_m(x_i)=y_i\end{array}$
  其中$e_m$一定满足$0\le e_m\le 0.5$，下面是简单的解释：

基分类器的权重${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$，$e_m$越大，${\alpha }_m$越小，也就是说，误差率小的基分类器权重越大，当$e_m<0.5$，${\alpha }_m>0$；当$e_m>0.5$，${\alpha }_m<0$，但是必有${\alpha }_m>0$，所以分类误差率$e_m<0.5$，如果$e_m>0.5$，那就把该分类器的结果都取一个相反的结果，这样一来取反后的分类器误差率还是小于$0.5$。

举例：

4.将${\alpha }_m\cdot G_m(x)$更新到加法模型$f(x)$中

$f(x)={\alpha }_1{G}_1(x)+\cdots +{\alpha }_m{G}_m(x)$

5.判断是否满足循环退出条件，如定义的M次或者模型精度

• 分类器个数是否达到M
• 总分类器误差率是否低于设定的精度（$sign(f(x))$）

2.3.2 例题

1.二分类训练数据集

2.定义基分类器（弱分类器）
1.基分类器定义如下：
$$G_1(x)=\{\begin{array}{ll}1,& x<k\\ -1,& x>k\end{array}$$，其中$k$为阈值
2.训练方法

在x中划分出候选阈值（如图中红色箭头指向的所示），
从中选出使得误差率$e_m$最小的，作为我们最终阈值构建好$G(x)$：

根据上图选择阈值为$2.5$，这时分错3个，误差率$e_m=\frac{3}{10}$

3.循环M次

M=1时：
1.初始化/更新当前训练数据的权值分布

• 初始化:$D_1=(w_{11},w_{12},\cdots ,w_{1N}),w_{1i}=\frac{1}{N},i=1,2,\cdots ,N)$

2.训练当前基分类器

• 使用具有权值分布$D_m$的训练数据集学习，得到基分类器$G_m(x)$
• 训练方法：1.在$x$中划分出各候选阈值，构建好候选$G_m(x)$；2.找到使误差$e_m$最小的$G_m(x)$，作为本轮的基分类器。
  在权值分布为$D_1$的训练数据上，阈值$k$取2.5时分类误差最低，故基本分类器为$$G_1(x)=\{\begin{array}{ll}1,& x>2.5\\ -1,& x<2.5\end{array}$$

3.计算当前基分类器的权值

• 1.计算当前$G_m(x)$在训练集上的分类误差率
  $e_m={\sum }_{i=1}^{N}P(G_m(x_i)\ne y_i)={\sum }_{i=1}^N{w}_{mi}I(G_m(x_i)\ne y_i)={\sum }_{G_m(x_i)\ne y_i}{w}_{mi}$，其中$I$为指示函数，$I=\{\begin{array}{ll}1,& G_m(x_i)\ne y_i\\ 0,& G_m(x_i)=y_i\end{array}$

• 2.根据分类误差率$e_m$，计算基分类器$G_m(x)$的权重系数

• 3.计算$G_1(x)$的系数：${\alpha }_1=\frac{1}{2}\log \frac{1-e_1}{e_1}=0.4236$

4.将${\alpha }_m\cdot G_m(x)$更新到加法模型$f(x)$中
得$f_1(x)=0.4236G_1(x)$

5.判断是否满足循环退出条件

• 分类器个数是否达到M
• 总分类器误差是否低于设定的精度
  

M=2时：
1.初始化/更新当前训练数据的权值分布

• 更新:
  

2.训练当前基分类器

• 使用具有权值分布$D_m$的训练数据集学习，得到基分类器$G_m(x)$
• 训练方法：1.在$x$中划分出各候选阈值，构建好候选$G_m(x)$；2.找到使误差$e_m$最小的$G_m(x)$，作为本轮的基分类器。
  

3.计算当前基分类器的权值

• 1.计算当前$G_m(x)$在训练集上的分类误差率
  $e_m={\sum }_{i=1}^{N}P(G_m(x_i)\ne y_i)={\sum }_{i=1}^N{w}_{mi}I(G_m(x_i)\ne y_i)={\sum }_{G_m(x_i)\ne y_i}{w}_{mi}$，其中$I$为指示函数，$I=\{\begin{array}{ll}1,& G_m(x_i)\ne y_i\\ 0,& G_m(x_i)=y_i\end{array}$
  

• 2.根据分类误差率$e_m$，计算基分类器$G_m(x)$的权重系数$${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$$

• 3.计算$G_2(x)$的系数：${\alpha }_2=\frac{1}{2}\log \frac{1-e_1}{e_1}=0.6496$

4.将${\alpha }_m\cdot G_m(x)$更新到加法模型$f(x)$中
得$$f_1(x)=0.4236G_1(x)+0.6496G_2(x)$$

5.判断是否满足循环退出条件

• 分类器个数是否达到M
• 总分类器误差是否低于设定的精度
  

M=3时：
$$f_3(x)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)$$

2.4 加法模型

2.4.1 预测函数

$$f(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$$

其中
类比Adaboost的预测函数：可知Adaboost就是一个加法模型：
$$f(x)=\sum _{m=1}^M{\beta }_{m}b(x;{\gamma }_m)$$

$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$

2.4.2 损失函数的设计

1.自定义损失函数$L(y,f(x))$

2.回归问题
MSE均方误差

3.分类问题

• 指数函数
• 交叉熵损失

4.优化方法

• 为什么不用梯度？
  • 梯度下降的缺点：整体损失极小化：$$\underset{{\beta }_m,{\gamma }_m}{\min }\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))$$
• 缺点：复杂度高；举例：假设$M=2$，假设L为MSE，$$\sum _{i=1}^{N}L(y_i,\sum _{m=1}^M{\beta }_{m}b(x_i;{\gamma }_m))=\sum _{i=1}^N\left(y_i-({\beta }_{1}b(x_i;{\gamma }_1+{\beta }_{2}b(x_i;{\gamma }_2)\right)$$

如：假设你用梯度下降优化，单词迭代过程，就需要同时优化4个参数${\beta }_1,{\beta }_2,{\gamma }_1,{\gamma }_2$（而且$\gamma$是向量），如果$M$再大些，单词迭代需要同时更新$2\cdot M$个参数，复杂度高。

• 使用的方法：前向分步算法
  • 具体步骤：

2.5 算法原理

2.5.1 需要优化的问题：二分类

1.二分类训练数据集
2.
$$T=\{(x_1,y_1),\cdots ,(x_N,y_N)\}$$，其中，每个样本点由实例与标记组成。实例$x_i\in \mathcal{X}\subseteq R^n$，标记 y i ∈ Y = { − 1 , + 1 } y_i\in \mathcal{Y}=\{-1,+1\} yi​∈Y={−1,+1}，$\mathcal{X}$是实例空间，$\mathcal{Y}$是标记集合。

2.5.2 模型：加法模型

$$f(x)=\sum _{m=1}^M{\alpha }_m{G}_m(x)$$

2.5.3 最终分类器

$$G(x)=sign[f(x)]$$

2.5.4 损失函数：指数损失函数

1.二分类问题，使用指数损失函数
$$L(y,f(x))=\exp [-yf(x)]$$

• 当$f(x)$分类正确时，与$y$同号，$L(y,f(x))<=1$。
• 当$f(x)$分类错误时，与$y$异号，$L(y,f(x))>1$。

2.将损失函数视为训练数据的权值
$${\bar{w}}_{mi}=\exp [-y_i{f}_{m-1}(x_i)]$$
非常符合训练样本中：提高前一轮“错误分类”的样本权值；降低前一轮“正确分类”的样本的权值。（就是因为$e^{-y\cdot f_{m-1}(x)}$）

3.单个样本损失函数
$$\begin{array}{rl}L(y,f(x))& =\exp [-y{f}_m(x)]\\ & =\exp [-y\sum _{m=1}^M{\alpha }_m{G}_m(x)]\\ & =\exp [-y(f_{m-1}(x)+{\alpha }_m{G}_m(x))]\end{array}$$
4.总体损失函数（把所有样本放进去）
$$\sum _{i=1}^N\exp [-y_i(f_{m-1}(x_i)+{\alpha }_m{G}_m(x_i))]$$

2.5.5 优化方法：前向分步算法

1.算法流程

2.第m轮

• 1.极小化损失函数：$({\alpha }_m,G_m(x))=arg{\min }_{\alpha ,G}{\sum }_{i=1}^N\exp [-y_i(f_{m-1}(x_i)+\alpha G_m(x_i))]$

• 2.式子变换：
  $({\alpha }_m,G_m(x))=arg{\min }_{\alpha ,G}(e^{-\alpha }\cdot {\sum }_{y_i=G(x)}{\bar{w}}_{mi}+e^{\alpha }\cdot {\sum }_{y_i\ne G(x)}{\bar{w}}_{mi})$，其中${\bar{w}}_{mi}=\exp [-y_i{f}_{m-1}(x_i)]$
  推导过程：
  $$\begin{array}{rl}({\alpha }_m,G_m(x))& =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N\exp [-y_i{f}_m(x_i)]\\ & =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N\exp [-y_i\sum _{m=1}^M{\alpha }_m{G}_m(x_i)]\\ & =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N\exp [-y_i(f_{m-1}(x_i)+{\alpha }_m{G}_m(x_i))]\\ & =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N\exp [-y_i{f}_{m-1}(x_i)]\cdot \exp [-y_i{\alpha }_m{G}_m(x_i)]\\ & =arg\underset{\alpha ,G}{\min }\sum _{i=1}^N{\bar{w}}_{mi}\cdot \exp [{\alpha }_m{G}_m(x_i)],其中{\bar{w}}_{mi}=\exp [-y_i(f_{m-1}(x_i)],而G(x)有两种取值可能\{\begin{array}{l}G(x_i)=y_i\\ G(x_i)\ne y_i\end{array}\\ & =arg\underset{\alpha ,G}{\min }\left(\sum _{y_i=G(x_i)}{\bar{w}}_{mi}\cdot \exp [-y_i{\alpha }_m{G}_m(x_i)]+\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}\cdot \exp [-y_i{\alpha }_m{G}_m(x_i)]\right)\\ & =arg\underset{\alpha ,G}{\min }\left(\sum _{y_i=G(x_i)}{\bar{w}}_{mi}\cdot \exp [-{\alpha }_m]+\sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}\cdot \exp [{\alpha }_m]\right),这一步是因为，y_i\cdot G_m(x_i)=-1or1\\ & =arg\underset{\alpha ,G}{\min }\left(e^{-{\alpha }_m}\cdot \sum _{y_i=G(x_i)}{\bar{w}}_{mi}+e^{{\alpha }_m}\cdot \sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}\right)\end{array}$$
  3.求解

• 1.优化$G_m(x)$

  • 从$G_m(x)$本身的意义上来讲，最优的$G_m(x)$要使得误差最小
  • $G_m^{\ast }(x)=arg{\min }_G{\sum }_{i=1}^N{\bar{w}}_{mi}I(y_i\ne G(x))$

• 2.优化${\alpha }_m$

  • ${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$
  • 推导过程:

  式子变换：$$\begin{array}{rl}& arg\underset{{\alpha }_m}{\min }\left(e^{-{\alpha }_m}\cdot \sum _{y_i=G(x)}{\bar{w}}_{mi}+e^{{\alpha }_m}\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}\right)\\ & \to arg\underset{{\alpha }_m}{\min }\left(\underbrace{e^{-{\alpha }_m}\cdot \sum _{y_i=G(x)}{\bar{w}}_{mi}+e^{-{\alpha }_m}\cdot \sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}}-\underbrace{e^{-{\alpha }_m}\cdot \sum _{y_i\ne G(x_i)}{\bar{w}}_{mi}+e^{{\alpha }_m}\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}}\right)\\ & \to arg\underset{{\alpha }_m}{\min }\left(e^{-{\alpha }_m}\cdot \sum _{i=1}^N{\bar{w}}_{mi}+(e^{{\alpha }_m}-e^{-{\alpha }_m})\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}\right)\end{array}$$
  凸优化:
  求导：$$\begin{array}{rl}& \frac{\partial \left(e^{-{\alpha }_m}\cdot {\sum }_{i=1}^N{\bar{w}}_{mi}+(e^{{\alpha }_m}-e^{-{\alpha }_m})\cdot {\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}\right)}{\partial {\alpha }_m}\\ & =-e^{-{\alpha }_m}\cdot \sum _{i=1}^N{\bar{w}}_{mi}+(e^{{\alpha }_m}+e^{-{\alpha }_m})\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}\\ & =-e^{-{\alpha }_m}\cdot \left(\sum _{i=1}^N{\bar{w}}_{mi}-\sum _{y_i\ne G(x)}{\bar{w}}_{mi}\right)+e^{{\alpha }_m}\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}\\ & =-e^{-{\alpha }_m}\cdot \sum _{y_i=G(x)}{\bar{w}}_{mi}+e^{{\alpha }_m}\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}\triangleq \psi \end{array}$$
  导数为0：令$\psi =0$，即：
  $$\begin{array}{rl}& e^{{\alpha }_m}\cdot \sum _{y_i\ne G(x)}{\bar{w}}_{mi}=e^{-{\alpha }_m}\cdot \sum _{y_i=G(x)}{\bar{w}}_{mi},两边取对数\\ & \to {\alpha }_m+\ln (\sum _{y_i\ne G(x)}{\bar{w}}_{mi})=-{\alpha }_m\ln (\sum _{y_i=G(x)}{\bar{w}}_{mi})\\ & \to 2{\alpha }_m=\ln \left(\frac{{\sum }_{y_i=G(x)}{\bar{w}}_{mi}}{{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}\right)\\ & \to {\alpha }_m=\frac{1}{2}\ln \left(\frac{{\sum }_{i=1}^N{\bar{w}}_{mi}-{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}{{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}\right)\end{array}$$
  公式转换：$$\begin{array}{rl}{\alpha }_m& =\frac{1}{2}\ln \left(\frac{{\sum }_{i=1}^N{\bar{w}}_{mi}-{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}{{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}\right)\\ & =\frac{1}{2}\ln \left(\frac{\frac{{\sum }_{i=1}^N{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}-\frac{{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}}{\frac{{\sum }_{y_i\ne G(x)}{\bar{w}}_{mi}}{{\sum }_{i=1}^N{\bar{w}}_{mi}}}\right)\\ & =\frac{1}{2}\ln \frac{1-e_m}{e_m}\end{array}$$
  其中$\bar{w}$是损失并不是$[0-1]$限定空间里面的，而之前算法流程中的w是加了规范化因子进行归一化操作，保证了系数和为$1$。

• 3.前向更新$f_m(x)$：
  $$f_m(x)=f_{m-1}+{\alpha }_m{G}_m(x)$$

• 4.更新训练数据权值${\bar{w}}_{m+1,i}$：
  ${\bar{w}}_{mi}\{\begin{array}{ll}\frac{1}{N}& ,m=1\\ {\bar{w}}_{m-1,i}\cdot \exp [-y_i\cdot {\alpha }_{m-1}{G}_{m-1}(x_i)]& ,m>1\end{array}$

  • 推导：
    更新${\bar{w}}_{m+1,i}$:
    根据公式：${\bar{w}}_{mi}=\exp [-y_i\cdot f_{m-1}(x_i)]$
    有：$$\begin{array}{rl}\exp [-y_i\cdot f_m(x_i)]& =\exp [-y_i\cdot (f_{m-1}(x_i)+{\alpha }_m{G}_m(x_i))]\\ & =\exp [-y_i\cdot f_{m-1}(x_i)]\cdot \exp [-y_i\cdot {\alpha }_m{G}_m(x_i)]\\ & ={\bar{w}}_{mi}\cdot \exp [-y_i\cdot {\alpha }_m{G}_m(x_i)]\end{array}$$

3.四个问题

3.1 如何计算学习误差率$e_m$?

根据分类误差率$e_m$，计算基分类器$G_m(x)$的权重系数：
$${\alpha }_m=\frac{1}{2}\log \frac{1-e_m}{e_m}$$
为什么这样计算基学习器权重系数？

$0\le e_m\le \frac{1}{2}\to \frac{1-e_m}{e_m}\ge 1\to {\alpha }_m\ge 0$，$e_m$ 下降时，$\frac{1-e_m}{e_m}$单调增，${\alpha }_m$单调增。

推导过程：
看2.5 算法原理

3.2 如何得到基学习器权重系数$\alpha$？

3.3 如何更新样本权重$w$?

$${\bar{w}}_{mi}\{\begin{array}{ll}\frac{1}{N}& ,m=1\\ {\bar{w}}_{m-1,i}\cdot \exp [-y_i\cdot {\alpha }_{m-1}{G}_{m-1}(x_i)]& ,m>1\end{array}$$

更新${\bar{w}}_{m+1,i}$:

根据公式：${\bar{w}}_{mi}=\exp [-y_i\cdot f_{m-1}(x_i)]$
有：
$$\begin{array}{rl}\exp [-y_i\cdot f_m(x_i)]& =\exp [-y_i\cdot (f_{m-1}(x_i)+{\alpha }_m{G}_m(x_i))]\\ & =\exp [-y_i\cdot f_{m-1}(x_i)]\cdot \exp [-y_i\cdot {\alpha }_m{G}_m(x_i)]\\ & ={\bar{w}}_{mi}\cdot \exp [-y_i\cdot {\alpha }_m{G}_m(x_i)]\end{array}$$

这里$\bar{w}$ 是除以过规范化因子$Z$的，从公式${\bar{w}}_{mi}$可以看出，如果有第$i$个样本分类错误，则$y_i\cdot G_{m-1}(x_i)<0$，导致样本的权重在第$m$个基分类器中增大，如果分类正确，则权重在第$m$个基分类器中减少。

3.4 使用何种结合策略？

$f(x)=sign({\sum }_{m=1}^M{\alpha }_m{G}_m(x))$

4.小结

Adaboost的主要优点有：

• 1.Adaboost作为分类器时，分类精度很高
• 2.在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
• 3.作为简单的二元分类器时，构造简单，结果可理解。
• 4.不容易发生过拟合

Adaboost的主要缺点有：

• 1.对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。