AdaBoost阶段小结.ppt

AdaBoost阶段小结
前期调研
PAC学习模型[2-3]
机器学习中，训练样本再大也不能代表某类事物本身，所以从训练样本中学习得到“规则”不能对某类事物完全适用，总有失效的情况出现，所以机器学习的目标是概率逼近正确学习AdaBoost阶段小结
前期调研
PAC学习模型[2-3]
机器学习中，训练样本再大也不能代表某类事物本身，所以从训练样本中学习得到“规则”不能对某类事物完全适用，总有失效的情况出现，所以机器学习的目标是概率逼近正确学习!
1984年 Valiant提出PAC（Probably Approximately Correct）学习模型文中提出强学习和弱学习两个概念。
Valiant的贡献
Valiant指出弱学习转换为强学习的可行性！
实际运用中，人们根据生产经验可以较为容易的找到弱学习方法，但是很多情况下要找到强学习方法是不容易的。有时候人们倾向于通过先找到弱学习然后把它转换为强学习的方式获取强学习方法，而Valiant证明了这种方式的可行性。
怎样实现弱学习转为强学习
核心思想：通过组合使弱学习互补。
学习是不适定问题，在有限的样本上，不同的学习方法得到不同的“规则”，并在不同的情况下失效，没有一种学习算法总是在任何领域产生最好的分类效果。
例如：学习算法A在a情况下失效，学习算法B在b情况下失效，那么在a情况下可以用B算法，在b情况下可以用A算法解决。这说明通过某种合适的方式把各种算法组合起来，可以提高准确率。
为实现弱学习互补，面临两个问题：
（1）怎样获得不同的弱分类器？
（2）怎样组合弱分类器？
怎样获得不同的弱分类器
使用不同的弱学习算法得到不同基学习器
参数估计、非参数估计…
使用相同的弱学习算法，但用不同的超参数
K-Mean不同的K，神经网络不同的隐含层…
相同输入对象的不同表示
不同的表示可以凸显事物不同的特征
使用不同的训练集
装袋（bagging）
提升（boosting）
怎样组合弱分类器
多专家组合
一种并行结构，所有的弱分类器都给出各自的预测结果，通过“组合器”把这些预测结果转换为最终结果。 （voting）及其变种、混合专家模型
多级组合
一种串行结构，其中下一个分类器只在前一个分类器预测不够准（不够自信）的实例上进行训练或检测。 eg. 级联算法（cascading）
Given: m examples (x1, y1), …, (xm, ym) where xiÎX, yiÎY={-1, +1}
Initialize D1(i) = 1/m
For t = 1 to T
1. Train learner ht with min error
2. Compute the hypothesis weight
3. For each example i = 1 to m
Output
The weight Adapts. The bigger et becomes the smaller at becomes.
Zt is a normalization factor.
Boost example if incorrectly predicted.
Linear combination of models.
Schapire AdaBoost Algorithm
AdaBoost的收敛性证明
整个证明的核心： ，不等
左边是最终强分类器的错误率
证明过程：
至此，看到AdaBoost的错误率上限，接下来的目标就是使这个上限尽可能小！
怎么使 尽量小
看到 是关于 的函数，要使 最小显然需要研
究 ！
在原始的AdaBoost算法中采用贪婪算法，每次的 都是最小的保
证 收敛到满意的结果。
在原始AdaBoost算法中h值域是{-1，1}，问题是怎么找到最佳的
这时候
前面证明原始AdaBoost算法的收敛性，但是原始
AdaBoost的收敛速度是不是就是最好的，有没有
更快的？有，Schapire提出了Real AdaBoost收
敛更快！
再次明确一下目标： 使尽量小！
对于原始的AdaBoost，前文讨论过其h是“定死”
的，失去了“讨价还价”的余地，进而确