机器学习笔记3 - Boosting方法

r囧r小猫 2022-09-18 02:53 145阅读 0赞

## Table of Contents ##

*  [1 前言][1]
 *  [2 AdaBoost][]
 *  [3 Boosting Tree][]
    
     *  [3.1 加法模型和前向分步算法][3.1]
     *  [3.2 回归问题的提升树算法][3.2]
 *  [4 Gradient Boosting][]

## 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(xi≠yi))=∑i=1nwmiI(Gm(xi)≠yi)
    3.  计算Gm(x)的系数
        
        am=12ln1−emem
        
        这个地方用模型的整体误差来衡量弱分类器在最终分类器中的权重。
    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)=fm−1(x)\+T(x;Θm)

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

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

Θm=argmin∑i=1nL(yi,fm−1(xi)\+T(xi;Θm))

### 3.2 回归问题的提升树算法 ###

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

L(x,f(x))=(y−f(x))2

代入每轮迭代的优化函数中，损失函数部分为:

L(y,fm−1(x)\+T(x;Θm))==(y−fm−1(x)−T(x;Θm))2(r−T(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=yi−fm−1(xi)
    2.  拟合残差得到回归树T(x;Θm)
    3.  更新fmx=fm−1(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=argmin∑i=1nL(yi,c)
2.  对于m=1,2,…,M
    
    1.  对于i=1,2,…,N，计算
        
        rmi=−\[∂L(yi,f(xi))∂f(xi)\]f(x)=fm−1(x)
        
        这里用负梯度来表示损失函数的下降。
    2.  用rmi拟合一个回归树，得到第m棵树的叶结点区域Rmj
    3.  对于j=1,2,…,J，计算
        
        cmj=argmin∑xi∈RmjL(yi,fm−1(xi)\+c)
        
        这一步是利用线性搜索估计叶结点区域的常量输出值。
    4.  更新fm(x)=fm−1(x)\+∑Jj=1cmjI(x∈Rmj)
3.  得到回归树
    
    f(x)=fM(x)=∑m=1m∑j=1JcmjI(x∈Rmj)

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

[1]: http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html#sec-1
[2 AdaBoost]: http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html#sec-2
[3 Boosting Tree]: http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html#sec-3
[3.1]: http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html#sec-3-1
[3.2]: http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html#sec-3-2
[4 Gradient Boosting]: http://blog.crackcell.com/posts/2013/04/30/machine_learning_note_3_boosting.html#sec-4