Gradient Boosting —— 梯度迭代增强

2018-09-11 本文已影响2人 X猪

回归问题(Regression)

考虑一个回归问题，已知n个样本 $(x_1, y_1),(x_2, y_2), ...,(x_n, y_n)$
需要拟合一个函数 $F(x)$ ，使得误差最小。

迭代拟合残差

当然，通常很难找到一个非常准确的 F，于是我们先找到一个预测准确性比较弱的 $F_0$ ，其预测值 $F_0(x)$ 与实际 y 值之间的差异，也就是残差
$r_0(x)=y-F_0(x)$
现在问题可以变成，尽量找到一个好的 $h_0$ 来拟合 $r_0$ 。假设我们拟合了一个 $h_0$ ，现在总的拟合函数就是 $F_1(x)=F_0(x)+h_0(x)$ 。不幸的是， $F_1$ 虽然比 $F_0$ 有提升，但依然存在残差 $r_1(x)=y-F_1(x)$

于是我们再寻找一个 $h_1$ 来拟合 $r_1$ ，于是 $F_2(x)=F_1(x)+h_1(x)$ 。
这个迭代可以一直进行下去，使函数 F(x) 不断逼近目标值 y。这样迭代拟合残差来构造的模型函数可以写作
$\begin{cases} F_0= \sum_{i=1}^n y_i \\ F_{m}(x)=F_{m-1}(x)+h_{m-1}(x) \end{cases}$
即，初始模型 $F_0$ 的预测就用所有样本目标值y的均值。第m轮迭代得到的模型函数 $F_m$ ，等于上一轮函数 $F_{m-1}$ ，加上对上一轮函数残差的拟合函数 $h_{m-1}$ 。

不求一次性找到一个最优的拟合函数 F，而是采用迭代的方法构造出一系列函数，组合起来构成总的拟合函数 F，在迭代过程中不断逼近要拟合的真实函数，这是 Boosting 算法家族的共同特点。

梯度

我们现在要讨论的算法叫 Gradient Boosting，但是上面说了半天就是在拟合残差，好像跟梯度没啥关系啊！那么现在来研究一下误差函数 L 对拟合函数 F 的梯度。

对拟合函数 F，设拟合值 $\hat{y}=F(x)$
采用平方误差函数 $L(y,\hat{y})=(y-\hat{y})^2/2$
对所有样本，总的误差 $J=\sum_{i=1}^nL(y_i,\hat{y}_i)$

样本的目标值 $y_i$ 是已知的，误差J 最后算出来的结果就是一个数值标量，总共有n个样本，所以误差J 是n元变量 $(\hat{y}_1,\hat{y}_2......\hat{y}_n)$ 的函数。

计算函数J 的梯度：
$\nabla J=\Big(\frac{∂J}{∂\hat{y}_1}......\frac{∂J}{∂\hat{y}_i}......\frac{∂J}{∂\hat{y}_n}\Big)$
$\frac{∂J}{∂\hat{y}_i}=\frac{∂\sum_i^n L(y_i, \hat{y}_i)}{∂\hat{y}_i}=\frac{∂L(y_i, \hat{y}_i)}{∂\hat{y}_i}\\ =\frac{∂((y_i-\hat{y}_i)^2/2)}{∂\hat{y}_i}=-(y_i-\hat{y}_i )$
$y_i-\hat{y}_i=-\frac{∂J}{∂\hat{y}_i }\\ y-\hat{y}=-\nabla J$

即 残差 = 负梯度

说明一下，上面偏导数写法是 $\frac{∂J}{∂\hat{y}_i}$ ，不过有些文章会写作 $\frac{∂J}{∂F(x_i)}$ 。刚开始看到对 $F(x_i)$ 求偏导感觉有点疑惑，对函数求偏导怎么理解？仔细想想，其实 $F(x_i)$ 就是拟合函数的输出值，对于J来说，它也是一个变量。所以上面设 $\hat{y}=F(x)$ ，这两个偏导是一样的，引入 $\hat{y}_i$ 主要是帮助理解。

在机器学习领域，梯度下降是很常用的算法，通常应用梯度下降是误差J 对模型 F(x,w)的参数w 计算梯度，也就是说使用梯度下降的目的是寻找最优的参数 $\hat{w}$ ，使得模型 $F(x,\hat{w})$ 的预测值与目标值y 的误差J 最小。

而这里 Gradient Boosting 是误差J 对 F的值 计算梯度，即对 $F(x_i)$ 计算梯度，而不关心F的参数w。实际上也没法关心，因为在迭代过程中，F的参数在上一轮迭代已经确定好了，F已经是确定的（记得第一个 $F_0$ 是先给出的，然后再开始迭代），现在的关注点是残差。

其它误差函数

上面推导出残差=负梯度，但两者既然一样，好像也没有引出什么新的东西。不过，上面的结论是采用平方误差函数的情况。如果考虑其它误差函数，用梯度计算时我们可以得到一些不同的特性。我们对比看几个例子：

1. 残差
$r_i = y_i - F(x_i)$

2. 平方误差
$L(y,F) = (y-F)^2$
负梯度
$-\frac{∂J}{∂F(x_i)}=-\frac{∂\sum_i^n L(y_i, F(x_i))}{∂F(x_i)}= y_i-F(x_i)$

3. 绝对误差
$L(y,F) = |y-F|$

负梯度
$-\frac{∂J}{∂F(x_i)}=-\frac{∂\sum_i^n L(y_i, F(x_i))}{∂F(x_i)}= sign(y_i-F(x_i)) \qquad\qquad (1)$

4. Huber 误差
$L(y,F) = \begin{cases}(y-F)^2/2, \qquad \qquad |y-F|\leq \delta \\ \delta(|y-F|-\delta/2, \qquad |y-F|>\delta\end{cases}$

负梯度
$-\frac{∂J}{∂F(x_i)}=-\frac{∂\sum_i^n L(y_i, F(x_i))}{∂F(x_i)}= \begin{cases} y-F(x_i), \qquad \qquad |y_i-F(x_i)|\leq \delta \\ \delta sign(y_i-F(x_i)), \quad |y_i-F(x_i)| > \delta \end{cases} \qquad (2)$

可见，平方误差的负梯度=残差，而绝对误差和Huber误差的负梯度 $\neq$ 残差。
这些差异会带来什么不同的特性呢？

公式(1)表明，绝对误差的负梯度是 {-1,1}，每个样本的残差都映射到 {-1,1}，差别大小被忽略了。
公式(2)表明，Huber误差的负梯度，在误差绝对值 $\leq \delta$ 时等于残差，但误差绝对值 $> \delta$ 时被限制为 $\delta$ ，即“残差”上限是 $\delta$ 。
所以，相对原始的残差 $y_i - F(x_i)$ ，这两种负梯度都弱化了异常值的影响。如果我们拟合这三种负梯度，会发现平方误差对异常值（outliers）的敏感度较高，Huber 误差、绝对误差对异常值的敏感度较低。

负梯度 / 伪残差
虽然绝对误差和Huber误差的负梯度 $\neq$ 残差，但负梯度也是根据误差 L 计算出来的，从上面的分析也可以看出，不同误差函数得到的负梯度主要是对残差进行了一些限制或调整，所以，我们可以把负梯度理解为一种“伪残差”，或者说，经过调整的残差。

Gradient Boosting 算法步骤

对于回归问题，已知n个样本 $(x_1, y_1),(x_2, y_2), ...,(x_n, y_n)$ ，求拟合函数 $F(x)$ ，使得误差最小。
首先选取一个可微分的误差函数L。

产生一个初始模型，比如 $F= \sum_{i=1}^n y_i$
进行M次迭代
2.1 计算L对F的负梯度 $-g(x_i)=-\frac{∂ L(y_i, F(x_i)}{∂F(x_i)}$
2.2 构建函数 h 拟合负梯度 $-g(x_i)$
2.3 计算h的权重系数 $γ$ ，使得F增加h后的总误差 $\sum_{i+1}^n L(y_i, F+\gamma h)$ 最小。
这里 y、F、h 都已知，可以用一维优化方法计算出 $γ$ 。（参考维基百科 - Line search）。
2.3 F 更新为 F+ $γ$ h（ $γ$ 为h的权重系数）

Gradient Boosting vs AdaBoost

同属 Boosting 家族，Gradient Boosting vs AdaBoost 在大方向上是一致的，都是通过迭代构建弱模型，逐步增强（Boosting）并组合为强模型。
主要的差别集中在，Gradient Boosting 迭代拟合负梯度（“伪残差”），AdaBoost 迭代调整样本的权重。
关于 AdaBoost 可以参考上一篇文章 Boosting/AdaBoost —— 多级火箭助推。

另外，Gradient Boosting 并不只用于回归问题，也可以用在分类和排名问题，本文不再详述。

参考

A Gentle Introduction to Gradient Boosting
维基百科 - Gradient boosting