Boosting原理及在分类上的应用 电子工程系 刘辉 2002 年 12 月 9 日

Outline 背景 Boosting原理 Boosting算法 Boosting应用 总结

背景 游戏理论（Game theory） R P S 锤子 布 剪子 锤子 ½ 1 0 布 0 ½ 1 剪子 1 0 ½ 锤子 布 剪子 锤子 ½ 1 0 布 0 ½ 1 剪子 1 0 ½ 游戏者1（row player)： RSPPSRS… （损失最小化） 游戏者2（column player）： SRRPSRP… （损失最大化）

背景 在线学习（On-line learning) 以上种种因素，如何综合考虑？ 马以往的表现 马当前的状态 马的主人 场地安排 …….. 选哪个呢？

三个臭皮匠，胜过诸葛亮 背景 Boosting思想源于 Finding many rough rules of thumb can be a lot easier and more effective than finding a single, highly prediction rule.

原理引入 天气预报 预测明天是晴是雨？ 传统观念：依赖于专家系统（A perfect Expert)

原理引入 A perfect expert Reality CNN (Perfect!) ABC CBS X X X

X 原理引入 CNN ABC CBS Reality Boosting：based on “Nobody is perfect”，combine common reporter to obtain perfect expert 更加符合自然界的现实 CNN ABC CBS Reality X

原理引入 X X X X X X 3 2 7/4 1 1 1/4 1/2 1 1/2 1 1/4 1/2 1/8 1 MON TUE WED THU REALITY MAJORITY CNN ABC CBS FOX TOTAL 32/8 28/8 26/8 15/8 3 2 7/4 X 1 X 1 1/4 1/2 X 1 1/2 1 1/4 1/2 1/8 1 X X X

Boosting—concepts(1) 机器学习（Machine Learning)：将一些已知的并已被成功解决的问题作为范例输入计算机,机器通过学习这些范例总结并生成相应的规则,这些规则具有通用性,使用它们可以解决某一类的问题 。 人脸识别 文本分类 网络安全 生物信息工程 学习机（learner)：机器学习得到的规则或者模型。 样本：所研究问题的实例，一般在训练集中包括正样本和负样本。 一张人脸图像，一篇文章，一个病毒代码，一个生物的遗传编码 训练：采用某种方法，用已知属性的样本作为输入，得到相应规则的过程。 训练集：由已知属性的样本组成的集合，作为训练过程的输入数据。 测试集：由已知属性的样本组成的集合，作为测试过程的输入数据。 假设：学习机对样本做出的判断，即是否符合需要判定的事实。 某张脸是否是张三的，某篇文章是否属于新闻类别

Boosting—concepts(2) 特征选取：从实际数据中抽取反映其本质规律的属性。 人脸图像向量做PCA变换得到特征向量的投影系数 对文本进行语法分析后表示成关于词的特征向量 机器学习系统结构表示

Boosting—concepts(3) 弱学习机（weak learner): 对一定分布的训练样本给出假设（仅仅强于随机猜测） 根据有云猜测可能会下雨 强学习机（strong learner): 根据得到的弱学习机和相应的权重给出假设（最大程度上符合实际情况：almost perfect expert) 根据CNN,ABC,CBS以往的预测表现及实际天气情况作出综合准确的天气预测 弱学习机 强学习机 Boosting

Boosting流程(loop1) 加权后的训练集 原始训练集 强学习机 弱学习机 弱假设 X>1?1:-1 加权后的假设

Boosting流程(loop2) 加权后的训练集 原始训练集 强学习机 弱学习机 弱假设 Y>3?1:-1 加权后的假设

Boosting流程(loop3) 加权后的训练集 原始训练集 强学习机 弱学习机 弱假设 Z>7?1:-1 加权后的假设

流程描述 Step1: 原始训练集输入，带有原始分布 Step2: 给出训练集中各样本的权重

核心思想 样本的权重 弱学习机的权重 循环控制：损失函数达到最小 没有先验知识的情况下，初始的分布应为等概分布，也就是训练集如果有N个样本，每个样本的分布概率为1/N 每次循环一后提高错误样本的分布概率，分错样本在训练集中所占权重增大， 使得下一次循环的弱学习机能够集中力量对这些错误样本进行判断。 弱学习机的权重 准确率越高的弱学习机权重越高 循环控制：损失函数达到最小 在强学习机的组合中增加一个加权的弱学习机，使准确率提高，损失函数值减小。

简单问题演示（Boosting训练过程）

算法—问题描述 训练集 { (x1,y1), (x2,y2),…, (xN,yN) } xi Rm, yi {-1,+1} Dt 为第t次循环时的训练样本分布（每个样本在训练集中所占的概率， Dt总和应该为1） ht:X{-1,+1} 为第t次循环时的Weak learner，对每个样本给出相应的假设，应该满足强于随机猜测： wt为ht的权重 为t次循环得到的Strong learner

算法—样本权重 思想：提高分错样本的权重 反映了strong learner对样本的假设是否正确 采用什么样的函数形式？

算法—弱学习机权重 思想：错误率越低，该学习机的权重应该越大 为学习机的错误概率 采用什么样的函数形式？ 和指数函数遥相呼应：

算法--Adaboost

理论分析--最优化 如何求弱学习机的权重？ 最基本的损失函数表达形式 为了便于计算，采用以下的目标函数 Boosting的循环过程就是沿着损失函数的负梯度方向进行最优化的过程。通过调整样本的分布Dt和选择弱学习机的权重wt来达到这个目的。每循环一次，增加一项 ，使损失函数以最快速度下降。

理论分析—熵映射 给定当前分布和选定的弱学习机，如何求下一次的分布？ Boosting的设计思想： 改变分布，提高错误样本概率，使下一次的弱学习机能够集中精力针对那些困难样本。 调整分布后的训练集对当前学习机具有最大的随机性，正确率50%（恰好为随机猜测）

理论分析—熵映射 相对熵原理（最小鉴别信息原理） 已知随机变量X（样本集）的先验分布（Dt），并且已知所求未知分布Dt+1满足条件 ( Dt+1*Ut = 0 )，那么所求得的未知分布估计值具有如下形式： 物理意义：在只掌握部分信息的情况下要对分布作出判断时，应该选取符合约束条件但熵值取得最大的概率分布。从先验分布到未知分布的计算应该取满足已知条件，不确定度（熵）变化最小的解。

应用—人脸识别

应用—人脸识别

应用—文本分类

应用—文本分类

总结 Boosting的思想源泉： Boosting的数学实质： Boosting的理论联系： Boosting的应用 三个臭皮匠，胜过诸葛亮 将一系列粗略的规则加权组合起来得到高度精确的规则。 Boosting的数学实质： 对目标函数（损失函数）的最优化问题。 Boosting的理论联系： 最优化 熵映射 Boosting的应用 人脸识别 文本分类

参考资料 Internet站点 推荐论文 www.boosting.org http://mathworld.wolfram.com A Brief Introduction to Boosting Experiments with a New Boosting Algorithm Additive Logistic Regression: a Statistical View of Boosting The Boosting Approach to Machine Learning: an overview Game Theory, On-line Prediction and Boosting Boosting as Entropy Projection Logistic Regression, AdaBoost and Bregman Distances 以上论文均可在www.boosting.org下载

Thank you! Have a good supper! End  Thank you! Have a good supper!