AdaBoost

PAC学习模型（Probably Approximately Correct）

在机器学习中，训练样本再大也不能代表某类事物本身，所以从训练样本中学习得到”规则“不能对某类事物完全适用，总有失效的情况出现，所以机器学习的目标是概率逼近正确学习

强学习 VS 弱学习

强学习

令S为包含N个数据点 $(x_1, y_1), ..., (x_N, y_N)$ 的样本集，其中 $x_n$ 是按照某种固定但未知的分布 $D(x)$ 随机独立抽取的。 $y_n = f(x_n)$ ， $f$ 属于某个已知的布尔函数集 $F$ 。如果对于任意的 $D$ ，任意的 $f \in F$ ，任意的 $0 \leq \epsilon , \delta \leq 1/ 2$ ，学习算法生成一个满足$Pr[h(x) \neq f(x)] \leq \epsilon $的估计$ h$的概率大于 $1 - \delta$ ，并且学习算法的运行时间与 $1/ \epsilon ， 1 / \delta$ 成多项式关系，则这种学习算法为强学习算法

弱学习

其定义与强学习类似，只是弱学习算法中只需存在某对 $\epsilon, \delta$ 满足上述条件即可。

能否将弱学习算法转化为强学习算法？

已经证明了只要有足够的数据，弱学习算法就能听过集成的方式生成任意高精度的估计

怎样实现弱学习转为强学习？

核心思想：通过组合使弱学习互补

学习是不适定问题，在有限的样本上，不同的学习方法法得到不同的“规则”，并在不同的情况下失效，没有一种学习算法总是在任何领域产生最好的分类效果。

例：学习算法A在a情况下失效，学习算法B在b情况下失效，那么在a情况下可以可以用B算法，在b情况下可以用A算法。这说明通过某种合适的方法把各种算法组合起来，可以提高准确率

如何获得不同的弱分类器？

使用不同的弱学习算法得到不同基学习器参数估计，非参数估计…
使用相同的弱学习算法，但用不同的超参数K-mean的不同K，神经网络不同的隐含层…
相同输入对象的不同表示，不同的表示可以凸显事物不同的特征
使用不同的训练集

装袋（bagging）

提升（boosting）

如何组合弱分类器？

多专家组合

一种并行结构，所有的弱分类器都给出个字的预测结果，通过“组合器”吧这些预测结果转换为最终结果，eg. 投票（voting）机器变种、混合专家模型

多级组合

一种串行结构，其中下一个分类器只在前一个分类器预测不够准确（不够自信）的实力上进行训练或预测。 eg. 级联算法（cascading）

Bagging & Boosting

bagging在给定样本上随机抽取（有放回）训练自己，在每个训练集上用不稳定的学习算法那训练分类不同弱分类器

boosting在前一个弱分类器错分的实例后在后续的弱分类器上得到更大的重视

从训练集的获取方式上看，bagging靠“运气”，boosting有“依据”

所谓不稳定学习算法是指训练集很小的变化会引起所产生的分类器变化很大，即学习算法高方差。例如，决策树

AdaBoosting （Adaptive Boosting）的先验知识

原理

AdaBoost的核心思想：”关注“被错分的样本，“器重”性能好的弱分类器

如何实现？

不同的训练集 -> 调整样本权重
“关注” -> 增加错分样本权重
“器重” -> 好的分类器的样本权重大
样本权重间接影响分类器权重

AdaBoost Concept

$\left.\begin{array}{rl}{h_{1}(x)} & {\in\{-1,+1\}} \\ {h_{2}(x)} & {\in\{-1,+1\}} \\ {} & {\vdots} \\ {h_{T}(x)} & {\in\{-1,+1\}}\end{array}\right\} \quad H_{T}(x)=\operatorname{sign}\left(\sum_{i=1}^{T} \alpha_{i} h_{t}(x)\right)$

weak classifier strong classifier

slightly better than random

Schapire AdaBoost Algorithm

Given: m examples(x1, y1), ..., (xm, ym) where xi ∈ X, yi ∈ {-1, +1}

Initialize D1(i) = 1/m

for t = 1 to T

Train learner $h_t$ with min error $\epsilon_t = Pr_{i-D_t}[h_t(x_i) \neq y_y]$
Compute the hypothesis weight $\alpha = \frac{1}{2} ln(\frac{1 - \epsilon_t}{\epsilon_t})$
For each example i = 10 to m

$D_{t+1}(i)=\frac{D_{t}(i)}{Z_{t}} \times\left\{\begin{array}{ll} {e^{-\alpha_{t}}} & {\text { if } h_{t}\left(x_{i}\right)=y_{i}} \\ {e^{\alpha_{t}}} & {\text { if } h_{t}\left(x_{i}\right) \neq y_{i}} \end{array}\right.$

Output:

$H(x) = sign (\sum_{t = 1}^{T} \alpha_t h_t(x))$