当前课程知识点：大数据机器学习 > 第十二章 提升方法 > 1. 提升方法Adaboost算法 > 1. 提升方法adaboost算法
同学们好
欢迎来到大数据机器学习的课堂
我们这一讲的题目是提升方法
我们之前介绍的机器学习方法
对训练样本进行训练的时候
每个训练样本的重要性是相同的
这一讲呢
我们将介绍的提升方法
也就是Boosting方法
它呢不仅仅是一个方法
而且还是一类学习方法
该类方法通过改变训练样本的权值
学习多个子模型或子分类器
然后再将它们进行线性组合
得到一个组合的模型
从而提高模型的性能
这一讲首先会介绍提升方法的思路
和代表性的提升算法Adaboost
然后呢会通过训练误差分析
探讨Adaboost为什么能够提高学习精度
然后呢
从前向分布加法模型的角度去解释Adaboost
然后再介绍
提升方法的另一个经典算法提升树
最后呢
我们给出一个具体的Python的实例
供大家对提升方法进行编程学习
好
下面我们介绍提升方法及AdaBoost算法
我们将介绍一下这些内容
AdaBoost算法的起源
怎样实现弱学习转为强学习
还包括Bagging方法
然后是怎样组合弱分类器
接着介绍
AdaBoost提出动机和基本概念
AdaBoost算法的动机
在机器学习方法中
有一个最基本的思路
就是多个方法的组合
多个模型共同决策
尤其是对那些复杂的任务来说
我们将多个模型或专家的结果
进行适当的综合
这样呢
就比任何其中一个单独的判断要好
中国有句古话
三个臭皮匠顶一个诸葛亮也是这个道理
在1984年的时候
有两位学者Kearns和Valiant
首先提出了叫强可学习和弱可学习的概念
那么他们同时也指出
在概率近似正确的条件下
那么 概率近似正确
probably approximately correct 简称PAC
是一个这样的概念
它包括一个叫概念或者是概念类
如果存在一个多项式的学习算法能够学习它
并且正确率很高
我们就称这个概念是强可学习的
如果一个概念或概念类
是存在一个多项式的学习算法能够学习它
学习的正确率
仅比随机的猜测略好那么一点
我们就称这个概念是弱可学习的
到了1989年
Schapire就证明了
在PAC学习的框架下
一个概念是强可学习的充分必要条件
是这个概念是弱可学习的
有了这个理论
大家都在思考
如果已经发现了弱学习算法
那么能否将它提升为强可学习算法
这样就有很多算法被提出
adaboost就是其中的一个有代表性的算法
adaboost的算法提出的时候
是在1990年
当时Schapire首先构造出了一种多项式级的算法
也就是最初的Boost提升算法
1993年的时候
Drunker和Schapire第一次将
神经网络作为弱学习器
应用提升的算法
解决了OCR的问题
到1995年的时候
Freund和Schapire又提出了Adaboost
那么Adaboost算法提出以后
它的效率和原来Boosting算法是一样的
但是呢
它不需要任何关于弱学习器性能的先验知识
可以非常容易地应用到实际的问题当中去
那么 到了2000年的时候
Friedman提出了提升树的算法
下面我们介绍提升方法的基本思路
对于一个分类问题
我们给定一个训练样本
及我们先找出一个粗略的分类方法
或者叫弱分类器
因为找一个弱分类器
比找一个精确的强分类器要容易很多
那么
提升方法就是从弱学习算法出发
多次学习
得到一系列的弱分类器
然后呢 组合他们构成一个强分类器
大多数的提升方法
都会在每个弱分类器学习以后呢
会更改训练数据的权值分布
或者是概率分布
再进行下一个弱分类器的学习
那么 怎样去实现弱学习转为强学习
我们打一个比方
学习算法A在A情况下是失效的
学习算法B在B情况下失效
那么
我们可以在A情况下使用B算法
在B情况下用A算法来解决这个问题
这就说明 通过某种合适的方法
把各种算法组合起来可以提高准确率
但是呢
实现弱学习器的组合和互补也面临两个问题
第一个
怎样选取不同的弱分类器
第二个呢 怎样组合弱分类器
首先
怎样选择弱分类器
一般我们有以下几种方法
首先我们会使用不同的弱学习算法
得到不同的基本学习器
比方说
有的弱分类器采用参数的估计方法
有的呢就可以采用非参数的估计方法
其次呢 我们会使用相同的弱学习算法
但使用的参数是不同的
例如
我们在使用前面介绍过的K均值方法的时候
就可以取不同的K参数
神经网络方法呢
也可以取不同层数的隐含层等
这些都是使用超参不同的方式
去构建不同的弱分类器
我们还可以对相同的输入对象的不同表示
来凸显事物不同的特征
也可以使用不同的变异或增强以后的训练数据集
Bagging方法就是一种组合的方法
也称为自举汇聚法
它的步骤是这样的
先从原始的数据集去选择S次
这样呢就得到了S个新的数据集
这新的数据集和原数据集
它的大小是相同的
每个数据集都是通过在原始的数据集上
随机选择样本来进行替换而得到的
这S个数据集建好以后
我们就可以将某个学习算法
分别作用于每个数据集当中
这样我们就得到了S个分类器
选择分类器投票结果中
最多的类别作为最后的分类结果
我们之前提到过的随机森林方法
就是一种改进的Bagging算法
刚才我们已经介绍了
如何去选择不同的弱分类器
那么 如何去组合弱分类器呢
首先是多专家组合方法
这是一种并行的结构
所有的弱分类器呢都给出自己的预测结果
我们通过组合器
把这些预测的结果转换为最终的结果
可以采用投票以及投票的变种
还可以采用混合专家模型等方式进行组合
也可以采用多级的组合方式
也就是一种串联的结构
也就是说下一个分类器
只在前一个分类器预测不够准确的情况下
进行训练或检测
例如 级联算法就是一种
串行的结构的多级组合方式
Adaboost算法是adaptive boosting 的缩写
意思是通过一系列的弱分类器
构建一个强分类器
Adaboost要解决两个主要的问题
AdaBoost的算法过程中
有两个需要重点解决的问题
第一个问题是
每一轮如何改变训练数据的权值或概率分布
那么AdaBoost的方法是
提高那些被前一轮的弱分类器
错误分类的样本的权值
降低那些被正确分类的样本的权值
第二个需要重点关注的就是
如何将弱分类器进行组合成一个强的分类器
那么 AdaBoost用了一种叫加权多数表决
加大分类误差率小的弱分类器的权值
这样呢就使他在表决中起到较大的作用
减小分类错误率大的弱分类器的权值
使其在表决中起较小的作用
AdaBoost算法如图所示
每个训练数据首先都赋予一个权值Wi
在得到每个弱分类器以后呢
会根据更新后的分类结果得到误差率
然后通过这个误差率
再去更新每个训练样本的权值
给下一轮的弱分类器进行学习
直到最后的弱分类器
达到要求的错误率从而停止操作
下面给出AdaBoost算法的具体步骤
输入是二分类的训练数据集
T=x1 y1 x2 y2到xn yn
xi属于Rn yi属于-1或+1
输出是最终的分类器Gx
步骤一
先初始化训练数据的起始权值分布
D1=w11 w1i一直到w1N w1i=1/N
也就是说 第一轮我们都对每一个
训练数据进行均匀化的赋予权值
第二步
对M个弱分类器就是m=1 2一直到M
进行如下的子程序操作
子程序的第一步
在权值Dm下
训练数据得到弱分类器Gmx
第二步
计算Gm的训练误差
（见上图）
第三步 计算GM的系数
（见上图）
第四步
更新训练数据集的权值分布
（见上图）
更新以后的权值是根据下式计算
（见上图）
Z是规范化因子
（见上图）
我们后面会详细的分析
这四个子步骤中
两个重要的参数更新的具体含义
一个呢
就是每个弱分类器的GM的系数αm
另一个是样本的权值Wm+1i
第二步的四个子步骤完成以后
就可以进入第三个步骤
构建弱分类器的线性组合
得到一个强分类器
（见上图）
然后再得到最终的分类器
（见上图）
下面呢
我们具体分析一下
在四个子步骤中的参数
他们进行更新的具体的含义
每一轮的训练误差EM
它就等于弱分类的样本的权值的累加
错误分类的样本越多
误分类样本的权值越大
则误差越大
子步骤三中的阿尔法M的含义
是当这一轮的弱分类器错误率
小于等于阿尔法1的时候
那么这个阿尔法M会大于等于0
就是说弱分类器对总体的分类器是有贡献的
如果错误率大于1/2
那么 阿尔法m就会小于零
该弱分类器的贡献就会为负
阿尔法M是分类器的总体性能的参数
接下来是每个样本权值的更新
WM加1i 它等于当这一轮
对XI样本分类正确的时候
（见上图）
这样呢这个样本的权重就变小了
而当这一轮对Xi分类错误的时候呢
取值就变为WMA除以ZM乘以Pxpfm
这样呢这个样本的权重就变大了
这就符合了刚才我们所说的
当这个样本分类正确的时候呢
我们就会减小他在下一轮的权值
而如果分类错误的话
我们会增加他在下一轮的权值
下面我们给出一个实际的例子
来更加清晰的说明AdaBoost的学习过程
我们有十个训练样本是一维数据
初始化的权值呢为均匀化的1/10
也就是
第一轮对一维数据进行弱分类
选取最小误差的弱分类器分割点
我们通过计算是在X等于2.5
这样呢 大于2.5就取为-1
小于2.5就取为正1
得到第一个弱分类器G1
G1的误差率就是分类错误的样本数
除以总的样本数为0.3
阿尔法1就等于0.4236
有了第一轮的分类错误率
我们就给每个数据集的样本
重新计算权值
这样分类正确的点权值降低
分类错误的点权值增加
第一个分类器为F1X
有三个误分类点
根据更新以后的样本权重
我们得到了第二个弱分类器
第二个弱分类器的分类阈值为8.5
这样呢得到的分类误差为0.2143
阿尔法二等于0.6496
得到的分类器F2x
为前面两个弱分类器的加权和
这时呢
依然还有三个误分类点
在第二个训练数据集的权值基础上
得到第三个弱分类器
并更新误差率和阿尔法
得到更新的样本权值分布
这时候得到的分类器
Sign f3的误分类点就为零了
这样满足了我们的误差要求
所以学习结束
得到最终的组合的分类器
下面我们用图示的方法
形象地说明adaboost的方法
首先我们用弱分类器分割数据集
得到三个误分点
我们增加三个误分点的权值
在更新权值以后
进行下一次的线性分类
虚线部分为分类器二
这时还有两个误分点
继续增加误分点的权值得到弱分类器三
也就是虚线的误分类器
最后我们组合这几个弱分类器
得到性能更优的强分类器
-1.机器学习定义和典型应用
-2.机器学习和人工智能的关系
-3.深度学习方法和其它人工智能方法的共性和差异
-4.机器学习和数据挖掘的关系
-5.机器学习和统计学习的关系
-6.机器学习的发展历程
-7.大数据机器学习的主要特点
-第一章 概述--7.大数据机器学习的主要特点
-1机器学习的基本术语
-2.监督学习
--2.监督学习
-3.假设空间
--3.假设空间
-4.学习方法三要素
-第二章 机器学习基本概念--4.学习方法三要素
-5.奥卡姆剃刀定理
-6.没有免费的午餐定理
-7.训练误差和测试误差
-8.过拟合与模型选择
-第二章 机器学习基本概念--8.过拟合与模型选择
-9.泛化能力
--9.泛化能力
-10.生成模型和判别模型
-1.留出法
--1.留出法
-2.交叉验证法
--2.交叉验证法
-3.自助法
--3.自助法
-4.性能度量
--4.性能度量
-5.PR曲线
--5.PR曲线
-6.ROC和AUC曲线
-第三章 模型性能评估--6.ROC和AUC曲线
-7.代价敏感错误率
-8.假设检验
--8.假设检验
-9.T检验
--9.T检验
-10.偏差和方差
--10.偏差和方差
-1.感知机模型
--1.感知机模型
-第四章 感知机--1.感知机模型
-2.感知机学习策略
-3.感知机学习算法
-第四章 感知机--3.感知机学习算法
-1.原型聚类描述
--1.原型聚类描述
-第五章 聚类--1.原型聚类描述
-2.性能度量
--2.性能度量
-第五章 聚类--2.性能度量
-3.1原型聚类 k均值算法
-3.2 原型聚类 学习向量算法
-3.3 原型聚类 密度聚类
-第五章 聚类--3.3 原型聚类 密度聚类
-3.4原型聚类 层次聚类
-1.综述
--1.综述
-2.概率图模型
--2.概率图模型
-第六章 贝叶斯分类器及图模型--2.概率图模型
-3.贝叶斯网络
--3.贝叶斯网络
-第六章 贝叶斯分类器及图模型--3.贝叶斯网络
-4.朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--4.朴素贝叶斯分类器
-5.半朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--5.半朴素贝叶斯分类器
-6.贝叶斯网络结构学习推断
-7.吉布斯采样
--7.吉布斯采样
-第六章 贝叶斯分类器及图模型--7.吉布斯采样
-开头
--开头
-1.决策树模型与学习基本概念
-2.信息量和熵
--2.信息量和熵
-第七章 决策树和随机森林--2.信息量和熵
-3.决策树的生成
--3.决策树的生成
-4.决策树的减枝
--4.决策树的减枝
-5.CART算法
--5.CART算法
-6.随机森林
--6.随机森林
-简介
--简介
-1.逻辑斯谛回归模型
-第八章 逻辑斯谛回归与最大熵模型--1.逻辑斯谛回归模型
-2.最大熵模型
--2.最大熵模型
-3.模型学习的最优化方法
-第八章 逻辑斯谛回归与最大熵模型--3.模型学习的最优化方法
-1.开头
--1.开头
-2.SVM简介
--2.SVM简介
-3.线性可分支持向量机
-第九章 SVM--3.线性可分支持向量机
-4. 凸优化问题的基本概念
-第九章 SVM--4. 凸优化问题的基本概念
-5.支持向量的确切定义
-6.线性支持向量机
-第九章 SVM--6.线性支持向量机
-svm相关拓展资料
-开头
--开头
-第十章 核方法与非线性SVM--开头
-1.泛函基础知识
--1.泛函基础知识
-第十章 核方法与非线性SVM--1.泛函基础知识
-2. 核函数和非线性支持向量机
-第十章 核方法与非线性SVM--2. 核函数和非线性支持向量机
-3. 序列最小最优化算法
-第十章 核方法与非线性SVM--3. 序列最小最优化算法
-开头
--开头
-1. k近邻学习
--1. k近邻学习
-第十一章 降维与度量学习--1. k近邻学习
-2. 降维嵌入
--2.降维嵌入
-第十一章 降维与度量学习--2. 降维嵌入
-3. 主成分分析
--3.主要成分分析
-第十一章 降维与度量学习--3. 主成分分析
-4. 核化线性降维
--4.核化线性降维
-5. 流型学习和度量学习
-1. 提升方法Adaboost算法
-第十二章 提升方法--1. 提升方法Adaboost算法
-2. Adaboost算法的训练误差分析
-3. Adaboost算法的解释
-4. Adaboost的实现
-第十二章 提升方法--4. Adaboost的实现
-adaboost拓展资料
-开头
--开头
-1. 问题提出
--1. 问题提出
-2. EM算法的引入
-3. EM算法的收敛性
-4. EM算法在高斯混合模型学习中的应用
-5. EM算法的推广
-第十三章 EM算法及混合高斯模型--3. EM算法的收敛性
-开头
--开头
-1. 计算学习理论的基础知识
-第十四章 计算学习理论--1. 计算学习理论的基础知识
-2. 概率近似正确学习理论
-3. 有限假设空间
--3.有限假设空间
-4. VC维
--4. VC维
-第十四章 计算学习理论--4. VC维
-5. 学习稳定性
--5. 学习稳定性
-开头
--开头
-1. 隐马尔科夫模型的基本概念
-第十五章 隐马尔可夫模型--1. 隐马尔科夫模型的基本概念
-2. 概率计算算法
-3. 学习算法
--3.学习算法
-第十五章 隐马尔可夫模型--3. 学习算法
-4预测算法
--4. 预测算法
-第十五章 隐马尔可夫模型--4预测算法
-开头
--开头
-1.概率无向图模型
-第十六章 条件随机场--1.概率无向图模型
-2.条件随机场的定义与形式
-第十六章 条件随机场--2.条件随机场的定义与形式
-3.条件随机场的计算问题
-4.条件随机场的学习算法
-5.条件随机场的预测算法
-第十六章 条件随机场--5.条件随机场的预测算法
-开头
--开头
-1.精确推断法：变量消去法和信念传播法
-第十七章 概率图模型的学习与推断--1.精确推断法：变量消去法和信念传播法
-2.近似推断法：MCMC和变分推断
-第十七章 概率图模型的学习与推断--2.近似推断法：MCMC和变分推断
-1.神经网络的发展历程
-2.神经网络的基本概念以及常见的神经网络(一）
-第十八章 神经网络和深度学习--2.神经网络的基本概念以及常见的神经网络(一）
-3.神经网络的基本概念以及常见的神经网络(二）
-4.玻尔兹曼机
--4.玻尔兹曼机
-5.深度学习
--5.深度学习
-第十八章 神经网络和深度学习--5.深度学习
-1. 深度学习简介和架构设计
-2. 计算图形式的反向传播算法
-3.深度学习的正则化方法（一）
-4.深度学习的正则化方法（二）
-1.深度学习的优化问题
-第二十章 深度学习优化方法--1.深度学习的优化问题
-2.神经网络优化的挑战
-3.神经网络的优化算法
-第二十章 深度学习优化方法--3.神经网络的优化算法
-4.相关策略
--4.相关策略
-第二十章 深度学习优化方法--4.相关策略
