8.9 随机搜索:Bumping

本章介绍的最后一个方法不涉及对模型的平均或结合,而是一种寻找更佳单一模型的方法。bumping1 利用自助抽样在模型空间中随机地移动。在拟合方法会遇到很多局部最小值的问题中,bumping 可以避免陷于非最优解从而改善拟合方法。

与自助聚合一样,先抽取自助样本然后在对每个样本拟合。但接下来不对预测结果进行平均,而是选择在训练集拟合最好的从自助样本估计的模型。具体来说,先抽取自主样本 $\mathbf{Z}^{*1}$,……,$\mathbf{Z}^{*B}$,在每个样本上拟合模型,得到每个输入点 $x$ 处的预测 $\hat{f}^{*b}(x)$,$b=1,2,\dots,B$。然后选择在原来的训练集中的平均预测误差最小的模型,例如,选择从自助样本 $\hat{b}$ 得出的模型,使得:

$$\hat{b} = \underset{b}{\arg\min} \sum_{i=1}^N [y_i - \hat{f}^{*b}(x_i)]^2 \tag{8.60}$$

对应模型的预测为 $\hat{f}^{*\hat{b}}(x)$。按惯例也会将原始的训练集作为候选自助抽样的其中一个,因此如果它的训练误差最低此方法也可以选择原始训练集估计出的模型。

bumping 通过在数据中加入绕动,设法将拟合过程移至模型空间上更优的区域。例如,如果有几个数据点导致了拟合过程被引入次优解上,任一排除了这些数据点的自助样本可能会得到更好的解。

**图 8.13**:两个特征和两个类别(蓝色和橙色)的数据,输入和输出变量有简单确定的关系。左图展示了由标准的贪心树生长算法得出的三个分割。靠近左边的垂直灰色线为第一次分割,虚线为两个接下来的分割。算法无法判断第一次分割应该在何处,得到了较差的分割。右图展示了 bumping 树生长算法 20 次得出的近乎最优的分割。
图 8.13:两个特征和两个类别(蓝色和橙色)的数据,输入和输出变量有简单确定的关系。左图展示了由标准的贪心树生长算法得出的三个分割。靠近左边的垂直灰色线为第一次分割,虚线为两个接下来的分割。算法无法判断第一次分割应该在何处,得到了较差的分割。右图展示了 bumping 树生长算法 20 次得出的近乎最优的分割。

作为另一个例子,考虑图 8.13 中的分类数据,这是著名的难以分类的 异或(exclusive or,XOR)问题。其中有两个类别(蓝色和橙色)和两个输入特征,特征对类别有简单确定的关系。先将数据按照 $x_1=0$ 分割再将得到的两个分组再按照 $x_2=0$ 分割(或调换顺序),如此的一个树类型的分类器可以完美地判定类别。然而,贪心而短视的 CART 算法(第 9.2 节)会先在两个特征中寻找最优的分割,然后再对得到的分组再进行分割。由于数据均衡分布的性质,基于 $x_1$ 或 $x_2$ 的所有第一步分割都是无用的,模型基本上会产生一个总体上随机的分割。图 8.13 的左图展示了从这组数据得出的实际的分割。bumping 通过对数据的自助抽样打破了类别分布的均衡,并且在经过合理的自助抽样次数后(这里为 20),它会随机地产生至少一个第一步分割在 $x_1=0$ 或 $x_2=0$ 的树模型。bumping 只用了 20 个自助样本便找到了图 8.13 的右图所示的近乎最优的分割。如果在数据中添加一些与类别标签独立的噪声特征变量,会进一步放大这种贪心的树生长(tree-growing)算法的缺点。那样会使树生长算法无法从其他特征中识别出 $x_1$ 和 $x_2$,更加不知所措。

由于 bumping 在训练集上比较不同的模型,所以必须要保证这些模型有大致相同的复杂度。对树模型而言,这意味着在每个自助样本上训练的树模型要有一样数量的终结点。bumping 也适用于涉及到可能由于不够平滑而难以最优化的拟合准则的问题中。其技巧在于在自助样本上对一个不同且更方便的准则进行最优化,然后再选择在训练集上得出最优期待准则的模型。


  1. 根据提出该方法的论文,“bumping” 是 “Bootstrap Umbrella of Model Parameters” 的首字母缩写。网上相关的内容很少,译者也不确定应该如何汉化这个词。 ↩︎

上一页