经典机器学习算法回顾 之 Boost 框架

在本期文章里，包子君将带大家来快速回顾一下经典 Boost 机器学习算法。

Boost 框架是一种通过累加弱模型来产生一个强模型的方法。它和一般的 Bagging 投票方法相比较，它们的相同点都是累加弱模型，但区别是在投票模型中， 每一个弱模型都是预测最终结果的（通过不同Groups的features），而 Boost 框架中的第 k 个弱模型是预测前面 1...k-1 个累加模型与正确答案之间的残差 (residual)， 也就是说 Boost 框架通过不断消除残差来提高模型精度。

Boost 框架的一般形式为：


f(x) = \sum_{m=1}^M \beta_m g_m(x)

M 是总共弱模型个数， \beta_m 是每个弱模型的权重， g_m是每个弱模型。 我们也可把它写成递归的形式：


f_m(x) = f_{m-1}(x) + \beta_m g_m(x)

Boost 框架训练的目标为：


argmin_{\beta_m,g_m} \sum_{n=1}^{N} L(y_n, f_{m-1}(x_n) + \beta_m g_m(x_n))

N 是总共训练样例的数目， L 是 Loss 函数。在优化时，我们采取迭代增加弱模型的方法, 用第 m 个模型去拟合每次前面 m-1 模型和的残差。

对于 Boost 框架，我们有两种常见的应用，分别是 Ada-Boost 自适应增强分类器 和 GDBT 增强回归树。

Ada-Boost 自适应增强分类器

对于输入 x_n \in \mathbf{R}^d, y_n \in \{-1, +1\} 以及弱分类器集合 \mathbf{G} = \{g_1, g_2 \dots g_k\} ， Ada-Boost 会通过Boost 框架从 K 个弱分类器中找到 M 个最佳弱分类器并分配其权重来优化一个指数型损失函数。

为了选择第 m 个弱分类器及其权重，我们先假设已经得到了前面 m - 1 个，于是损失函数成为：


\sum_{n=1}^{N} e^{-y_n (\beta_1 g_1(x_n) + \beta_2 g_2(x_n) + \dots + \beta_m g_m(x_n))} = \sum_{n=1}^{N} F_{m-1}(x_n) e^{-y_n \beta_m f_m(x_n)}

我们通过尝试 M 个不同的弱分类器（假设 \beta_m > 0 ），可以找到，损失函数最小的那个，并且通过对 \beta_m 求导等于零来得到其系数的值：


\beta_m = \frac{1}{2}log(\frac{1 - \epsilon_m}{\epsilon_m})

其中：


\epsilon_m = \frac {\sum_{y_n \neq g_m(x_n)}}{\sum_{n=1}^{N}g_m(x_n)}

迭代以上步骤 M 次即可得到由 M 个弱分类器组成的强分类器。

GDBT 增强回归树

增强回归树是通过之前提到的 Boost 方法，不断累加弱回归树来得到一个强的回归模型。 唯一的区别是，我们用导函数去近似残差，把 m 棵回归树拟合成前面 m-1 棵树和的负导数，于是我们有：


\frac{\partial L(F_{m-1}(x_n))}{\partial F_{m - 1}(x_n)} = - \beta_m g_m(x_n)

对于回归问题，我们可以用 Least Square 来作为作为损失函数：


L = \sum_{i=1}^{n} (F_m(x_i) - y_i)^2

同样我们用最小二乘回归树来拟合 g_m 函数，在这里我们不详细展开讨论回归树是如何构建的。简单地说，最小二乘回归树通过不断地 branch， 把输入空间中的 N 个点 \{x_n \mid n \in 1 \dots N \} 映射到 T 个空间 \{R_t \mid n \in 1 \dots T\} 里， 并给每个空间 assign 一个值 R_t，使得下面的回归树损失函数最小化：


\sum_n L(g_m(x_n), \sum_t R_t I_t(x_n))

其中 I_t(x_n) 是一个指标函数，当 x_n 被划分为第 t 个 Region 的时候 I_t(x_n) 为 1，其余情况全为 0 。

每一轮迭代我们就用产生一棵新的回归树 g_m 与之前所训练的 m - 1 棵树相加，一直到迭代结束。

Boost 框架的问题及改进

在使用中，我们发现 Boost 方法能够很灵活地拟合各种复杂的训练样本，但在泛化方面却有一定的问题。 Boost 框架和 以随机森林 (Random Forest) 为代表的 Bagging 方法同为 模型 Ensemble 的思路，却着重优化了两个不同的方面：偏差 (Bias) 和 方差 (Variance)。

对于 Boost 方法来说， 由于每一个弱分类器都为了是减少上一个弱分类器在训练样本里的偏差，所以最终 Ensemble 的 偏差 会较小，也就是模型比较灵活 (flexible)； 而对于 Bagging 的方法来说恰恰相反，每一弱分类器都独立预测了最终的结果，通过平均结果的方法，我们把预测结果的方差也减少到了原来每个弱分类器的 \frac{1}{\sqrt{M}} 。 为了提高 Boost 方法的泛化性能, 我们常常会在训练时，对其加入多个 Regularization 约束，并通过 Early Stopping 的方式来防止 Over-Fitting 。

好了，这次的 Boost 框架包子君就先带大家回顾到这里，如有还有什么不明白的，欢迎在留言中提问哦。