提纲 前期调研 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）

怎样组合弱分类器 多专家组合 一种并行结构，所有的弱分类器都给出各自的预测结果，通过“组合器”把这些预测结果转换为最终结果。 eg.投票（voting）及其变种、混合专家模型 多级组合 一种串行结构，其中下一个分类器只在前一个分类器预测不够准（不够自信）的实例上进行训练或检测。 eg. 级联算法（cascading）

小结 通过前期调研我比较关注是boosting原理。 bagging在给定样本上随机抽取（有放回）训练子集，在每个训练子集上用不稳定的学习算法训练分类不同弱分类器。boosting在前一个弱分类器错分的实例在后续的弱分类器上得到更大的重视。从训练子集的获取方式上看： bagging靠“运气”，boosting有“依据”！ 所谓不稳定学习算法是指训练集很小的变化会引起所产生的分类器变化很大，即学习算法高方差。例如，决策树。

AdaBoost原理 AdaBoost的由来 ？

AdaBoost的核心思想 “关注”被错分的样本，“器重”性能好的弱分类器 怎么实现 （1）不同的训练集调整样本权重 （2）“关注”增加错分样本权重 （3）“器重”好的分类器权重大 （4）样本权重间接影响分类器权重

原始AdaBoost

1995年Freund 提出AdaBoost算法，1999年Schapire在一篇会议论文上对Freund的AdaBoost重新表述，基本原理不变但是更易理解，下面以Schapire的版本介绍AdaBoost。

Schapire AdaBoost Algorithm 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 The weight Adapts. The bigger et becomes the smaller at becomes. 3. For each example i = 1 to m Boost example if incorrectly predicted. Output Zt is a normalization factor. Linear combination of models.

AdaBoost的收敛性证明 整个证明的核心： ，不等 左边是最终强分类器的错误率 证明过程：

至此，看到AdaBoost的错误率上限，接下来的目标就是使这个上限尽可能小！

怎么使 尽量小 看到 是关于 的函数，要使 最小显然需要研 究 ！ 在原始的AdaBoost算法中采用贪婪算法，每次的 都是最小的保 证 收敛到满意的结果。 在原始AdaBoost算法中h值域是{-1，1}，问题是怎么找到最佳的

这时候

前面证明原始AdaBoost算法的收敛性，但是原始 更快的？有，Schapire提出了Real AdaBoost收 敛更快！

再次明确一下目标： 使尽量小！ 对于原始的AdaBoost，前文讨论过其h是“定死” 的，失去了“讨价还价”的余地，进而确定了 的选择方法，所以在Real AdaBoost不在“定死”

Real AdaBoost Algorithm

？ 到这里介绍完AdaBoost原理，接下来就是我学习中的一些困惑。

一些问题 AdaBoost泛化能力的证明 Adaboost中对h选择 接下来学习的方向

AdaBoost泛化能力的证明 目前对AdaBoost泛化能力的证明是各家各言，没有定论。 Freund的证明已经被实践推翻； Schapire的证明被人证明是有缺陷的； …… 我比较关注的是Freund和Schapire的证明，他们都用到一个概念叫VC维度。我查了很多文献，都没能理解这个概念，所以目前我对AdaBoost泛化能力的证明无能为力。

AdaBoost对h的选择 是h和alpha的二元函数，为什么考虑的时候都考虑alpha，没考虑h？ 在原始的AdaBoost算法中用错误率最小来确定h至少还有个说法，在Real AdaBoost中直接把h和alpha整合成一个参数h’了，那么Real AdaBoost算法中对alpha的讨论又有什么意义呢？

接下来学习的方向 不管是变种AdaBoost其功能都是把弱学习提升为强学习，直观上我的感觉是AdaBoost性能好坏取决于弱学习？ 那么我们应该怎么选择弱学习方法？我在文献中看到有决策树、神经网络、svm、k-mean。。。等，AdaBoost作者用的是C4.5决策树。Viola第一个用AdaBoost做人脸检测，他采用是单层的决策树（stump）做弱学习。

看到这么多的weak learn算法，我不知道我改用那一种，也不知道要提高AdaBoost检测速度是不是该从weak learn入手？