AdaBoost阶段小结.ppt

提纲 前期调研AdaBoost原理一些问题 前期调研 PAC学习模型 2 3 机器学习中 训练样本再大也不能代表某类事物本身 所以从训练样本中学习得到 规则 不能对某类事物完全适用 总有失效的情况出现 所以机器学习的目标是概率逼近正确学习 1984年Valiant提出PAC ProbablyApproximatelyCorrect 学习模型文中提出强学习和弱学习两个概念 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 Given mexamples x1 y1 xm ym wherexi X yi Y 1 1 InitializeD1 i 1 m Fort 1toT 1 Trainlearnerhtwithminerror 2 Computethehypothesisweight 3 Foreachexamplei 1tom Output TheweightAdapts Thebiggeretbecomesthesmalleratbecomes Ztisanormalizationfactor Boostexampleifincorrectlypredicted Linearcombinationofmodels SchapireAdaBoostAlgorithm AdaBoost的收敛性证明整个证明的核心 不等左边是最终强分类器的错误率证明过程 至此 看到AdaBoost的错误率上限 接下来的目标就是使这个上限尽可能小 怎么使尽量小看到是关于的函数 要使最小显然需要研究 在原始的AdaBoost算法中采用贪婪算法 每次的都是最小的保证收敛到满意的结果 在原始AdaBoost算法中h值域是 1 1 问题是怎么找到最佳的 这时候 前面证明原始AdaBoost算法的收敛性 但是原始AdaBoost的收敛速度是不是就是最好的 有没有更快的 有 Schapire提出了RealAdaBoost收敛更快 再次明确一下目标 使尽量小 对于原始的AdaBoost 前文讨论过其h是 定死 的 失去了 讨价还价 的余地 进而确定了的选择方法 所以在RealAdaBoost不在 定死 RealAdaBoostAlgorithm h不再 定死 到这里介绍完AdaBoost原理 接下来就是我学习中的一些困惑 一些问题 AdaBoost泛化能力的证明Adaboost中对h选择接下来学习的方向 AdaBoost泛化能力的证明目前对AdaBoost泛化能力的证明是各家各言 没有定论 Freund的证明已经被实践推翻 Schapire的证明被人证明是有缺陷的 我比较关注的是Freund和Schapire的证明 他们都用到一个概念叫VC维度 我查了很多文献 都没能理解这个概念 所以目前我对AdaBoost泛化能力的证明无能为力 AdaBoost对h的选择是h和alpha的二元函数 为什么考虑的时候都考虑alpha 没考虑h 在原始的AdaBoost算法中用错误率最小来确定h至少还有个说法 在RealAdaBoost中直接把h和alpha整合成一个参数h 了 那么RealAdaBoost算法中对alpha的讨论又有什么意义呢 接下来学习的方向不管是变种AdaBoost其功能都是把弱学习提升为强学习 直观上我的感觉是AdaBoost性能好坏取决于弱学习 那么我们应该怎么选择弱学习方法 我在文献中看到有决策树 神经网络 svm k mean 等 AdaBoost作者用的是C4 5决策树 Viola第一个用AdaBoost做人脸检测 他采用是单层的决策树 stump 做弱学习 看到这么多的weaklearn算法 我不知道我改用那一种 也不知道要提高AdaBoost检测速度是不是该从weaklearn入手 目前我对AdaBoost的认识停留在数学层面 感觉还是很抽象 特别是人脸特征的知识表示是怎么进行的 我是不是应该先把黄金凤的程序拿来对照学习