机器学习算法-boost

时间:2022-09-09 07:36:03

本文转自http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html

1 前言

Boosting的基本思想很简单,就是"三个臭皮匠顶个诸葛亮"。将若干个弱分类器(base learner)组合起来,变成一个强分类器。大多数boosting方法都是通过不断改变训练数据的概率(权值)分布,来迭代训练弱学习器的。所以总结而言,boosting需要回答2个问题:。

  1. 如何改变训练数据的概率(权值)分布
  2. 如何将弱分类器组合起来

下面先用Adaboost入手,聊一下boosting。

2 AdaBoost

输入: 训练样例

T={(x1,y1),(x2,y2),...,(xn,yn)}
输出: 由M个弱分类器构成的最终分类器G(x)
步骤:

  1. 初始化权值分布
    D1=(w11,...,w1i,...,w1n),w1i=1n
  2. 对于m=1,2,…,M:
    1. 使用带权值的实例集合Dm训练模型,得到弱分类器:
      Gm(x):x>y
    2. 计算Gm(x)在训练集上的误差率
      em=P(Gm(xiyi))=i=1nwmiI(Gm(xi)yi)
    3. 计算Gm(x)的系数
      am=12ln1emem
      这个地方用模型的整体误差来衡量弱分类器在最终分类器中的权重。
    4. 更新训练样例的权值分布,为下一轮迭代做准备
      Dm+1=(wm+1,1,...,wm+2,i,...,wm+1,n)
      wm+1,i=wmiZmexp(amyiGm(xi))
      Zm是规范化因子:
      Zm=i=1nwmiexp(amyiGm(xi))
      exp(amyiGm(xi)) 这个部分,当分类正确时,整体<1;错误时,整体>1。意义是,当样例分类错误,我们加大它的权重,以便在后面的迭代中更受重视。相应的,降低分类正确的样例的权重。
  3. 进行了M轮迭代之后,产出了M个弱分类器,将他们组合起来:
    f(x)=i=1mamGm(x)

3 Boosting Tree

提升树被认为是统计学习中性能最好的方法之一,可以用来分类或者回归。对于分类问题,算法类似在AdaBoost中,使用决策树作为弱分类器。但对于回归问题,稍微有点不同。回归和分类最大的区别在于模型产出的数值之间的可比性。比如,对于分类,我们把本来应该是分类1的样本预测成了2或者3,他们2者的错误程度是一样的。但若这是一个回归问题,回归成3显然比2"错"得更多。

3.1 加法模型和前向分步算法

在聊Boosting Tree的回归之前,需要先了解2个概念:加法模型(additive model)和前向分步算法。
加法模型 就是将若干基函数线性组合的模型,函数表示为:

f(x)=m=1Mβmb(x;γm)

  • b(x;γm) 为基函数
  • γm 为基函数的参数
  • βm 为基函数的系数

直接解加法模型的最优化问题很麻烦,所以使用 前向分步算法 来分步迭代的求解,每次只算一个基函数的参数。
对于提升树,第m次迭代可以表示为:

fm(x)=fm1(x)+T(x;Θm)

  • T(x;Θm) 为一个树
  • Θm 为树的参数

每轮的最优化问题可以表示为:

Θm=argmini=1nL(yi,fm1(xi)+T(xi;Θm))

3.2 回归问题的提升树算法

接上节,那么对于回归问题,可以用平方误差损失函数:

L(x,f(x))=(yf(x))2
代入每轮迭代的优化函数中,损失函数部分为:
L(y,fm1(x)+T(x;Θm))==(yfm1(x)T(x;Θm))2(rT(x;Θm))2
这里r就是上轮迭代的残差。所以 对于回归问题,提升树只需简单地拟合当前模型的残差
我们不妨对比一下Boosting Tree的回归和分类。从实现上,分别用不同的方法实现了"动态确定样本权值"这一目标。回归是用拟合残差,分类是用错误率来调整样本权值。
那么,回归问题的算法可以如下描述:

输入: 训练样例
T={(x1,y1),(x2,y2),...,(xn,yn)}
输出: 提升树f M(x)
步骤:

  1. 初始化f0(x)=0
  2. 对m=1,2,…,M
    1. 计算残差
      rmj=yifm1(xi)
    2. 拟合残差得到回归树 T(x;Θm)
    3. 更新 fmx=fm1(x)+T(x;Θm)
  3. 得到回归问题的boosting tree:
    fM(x)=m=1MT(x;Θm)

4 Gradient Boosting

上面聊到的算法中存在最优化的操作。如果损失函数是平方损失(对于回归问题)和指数损失(对于分类问题),解最优化很简单。但如果是一般的损失函数,最优化可能很困难。Gradient Boosting就是为了解决这个问题。它将问题转变成在损失函数梯度上寻找下降最快的方向,近似地求解。

输入: 训练样例

T={(x1,y1),(x2,y2),...,(xn,yn)}
和损失函数:
L(y,f(x))
输出: 回归树 f(x) 步骤:

  1. 初始化:
    f0=argmini=1nL(yi,c)
  2. 对于m=1,2,…,M
    1. 对于i=1,2,…,N,计算
      rmi=[L(yi,f(xi))f(xi)]f(x)=fm1(x)
      这里用负梯度来表示损失函数的下降。
    2. 用rmi拟合一个回归树,得到第m棵树的叶结点区域Rmj
    3. 对于j=1,2,…,J,计算
      cmj=argminxiRmjL(yi,fm1(xi)+c)
      这一步是利用线性搜索估计叶结点区域的常量输出值。
    4. 更新 fm(x)=fm1(x)+Jj=1cmjI(xRmj)
  3. 得到回归树
    f(x)=fM(x)=m=1mj=1JcmjI(xRmj)

我们可以和3.2节中的算法比较一下,一目了然,主要差别在于这里每轮拟合模型的是损失函数的负梯度而不是残差。