机器学习算法-boost

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

1 前言

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

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

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

2 AdaBoost

输入: 训练样例

T = {(x 1, y 1), (x 2, y 2), . . ., (x n, y n)}

输出: 由M个弱分类器构成的最终分类器G(x)
步骤:

初始化权值分布
$D 1 = (w 11, . . ., w 1 i, . . ., w 1 n), w 1 i = 1 n$
对于m=1,2,…,M:
1. 使用带权值的实例集合D_m训练模型，得到弱分类器:
  $G m (x) : x > y$
2. 计算G_m(x)在训练集上的误差率
  $e m = P (G m (x i \neq y i)) = \sum i = 1 n w m i I (G m (x i) \neq y i)$
3. 计算G_m(x)的系数
  $a m = 1 2 l n 1 e m e m$
  这个地方用模型的整体误差来衡量弱分类器在最终分类器中的权重。
4. 更新训练样例的权值分布，为下一轮迭代做准备
  $D m + 1 = (w m + 1, 1, . . ., w m + 2, i, . . ., w m + 1, n)$
  
  $w m + 1, i = w m i Z m e x p (a m y i G m (x i))$
  Z_m是规范化因子:
  $Z m = \sum i = 1 n w m i e x p (a m y i G m (x i))$
  exp(a m y i G m (x i )) 这个部分，当分类正确时，整体<1；错误时，整体>1。意义是，当样例分类错误，我们加大它的权重，以便在后面的迭代中更受重视。相应的，降低分类正确的样例的权重。
进行了M轮迭代之后，产出了M个弱分类器，将他们组合起来:
$f (x) = \sum i = 1 m a m G m (x)$

3 Boosting Tree

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

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

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

f (x) = \sum m = 1 M β m b (x; γ m)

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

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

f m (x) = f m 1 (x) + T (x; Θ m)

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

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

Θ m = a r g m i n \sum i = 1 n L (y i, f m 1 (x i) + T (x i; Θ m))

3.2 回归问题的提升树算法

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

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

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

L (y, f m 1 (x) + T (x; Θ m)) = = (y f m 1 (x) T (x; Θ m)) 2 (r T (x; Θ m)) 2

这里r就是上轮迭代的残差。所以 对于回归问题，提升树只需简单地拟合当前模型的残差 。
我们不妨对比一下Boosting Tree的回归和分类。从实现上，分别用不同的方法实现了"动态确定样本权值"这一目标。回归是用拟合残差，分类是用错误率来调整样本权值。
那么，回归问题的算法可以如下描述:

输入: 训练样例

T = {(x 1, y 1), (x 2, y 2), . . ., (x n, y n)}

输出: 提升树f _M(x)
步骤:

初始化f₀(x)=0
对m=1,2,…,M
1. 计算残差
  $r m j = y i f m 1 (x i)$
2. 拟合残差得到回归树 T(x;Θ m )
3. 更新 f m x=f m1 (x)+T(x;Θ m )
得到回归问题的boosting tree:
$f M (x) = \sum m = 1 M T (x; Θ m)$

4 Gradient Boosting

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

输入: 训练样例

T = {(x 1, y 1), (x 2, y 2), . . ., (x n, y n)}

和损失函数:

L (y, f (x))

输出: 回归树

f(x) 步骤:

初始化:
$f 0 = a r g m i n \sum i = 1 n L (y i, c)$
对于m=1,2,…,M
1. 对于i=1,2,…,N，计算
  $r m i = [L ( y i , f ( x i ) ) f ( x i )] f (x) = f m 1 (x)$
  这里用负梯度来表示损失函数的下降。
2. 用r_mi拟合一个回归树，得到第m棵树的叶结点区域R_mj
3. 对于j=1,2,…,J，计算
  $c m j = a r g m i n \sum x i \in R m j L (y i, f m 1 (x i) + c)$
  这一步是利用线性搜索估计叶结点区域的常量输出值。
4. 更新 f m (x)=f m1 (x)+∑ J j=1 c mj I(x∈R mj )
得到回归树
$f (x) = f M (x) = \sum m = 1 m \sum j = 1 J c m j I (x \in R m j)$

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