8.9 随机搜索： Bumping¶
| 原文 | The Elements of Statistical Learning |
|---|---|
| 翻译 | szcf-weiya |
| 发布 | 2017-06-09 |
| 更新 | 2019-08-01 19:31:48 |
| 状态 | Done |
这章描述的最后一个方法不涉及平均或者结合模型，但是是寻找一个更好单模型的方法．Bumping 采用 bootstrap 采样在模型空间中随机移动．对于拟合方法经常会找到许多局部最小值的问题，bumping 可以帮助这些方法避免陷入坏的解．
像在 bagging 中一样，我们抽取自助样本并且对每个样本拟合模型．但是不是对这些预测值进行平均，我们而是选择拟合训练数据最好的自助样本的模型．具体地，我们抽取自助样本 $Z^{*1}, \ldots, Z^{*B}$ 并对每个样本拟合我们的模型，然后给出在输入点 $x$ 处的预测 $\hat f^{*b},n=1,2,\ldots,B$．我们在原始训练集上平均选择产生最小预测误差的模型．举个例子，对于平方误差，我们选择从自助样本 $\hat b$ 中得到的模型，其中
对应的模型预测为 $\hat f^{*\hat b}(x)$．按照约定，我们也把原始训练样本包含进自助样本的集合中，所以如果原始模型有更低的训练误差，这种方法也能选择原始模型．
通过打乱数据，bumping 试图将拟合过程移动到模型空间的好区域中．举个例子，如果只有少数的数据点会导致这个过程找到差的解，则任意删除掉这些数据点的自助样本应该会产生更好的解．
举另一个例子，考虑图 8.13 中的分类数据，臭名昭著的异或(exclusive or)(XOR)问题．其中有两个类别（蓝色和橘黄色）以及两个输入特征，并且特征间存在单纯的交叉．
通过先在 $x_1=0$ 处分离数据，然后在每个分层的 $x_2=0$ 处分离数据（或者反过来），一个基于树的分类器可以达到完美的判别．然而，贪婪的、见识短的 CART 算法（9.2节）试图寻找任意一个特征上的最优分割，接着再对得到的分层进行分割．由于数据的平衡特性，所有在 $x_1$ 或 $x_2$ 上的初始分割似乎无用，而且这个过程本质上在第一层产生随机的分割．对于这些数据找到的实际分割展示在图 8.13 的左图．通过对数据 bootstrap 采样，bumping 打破了类别之间的平衡，以一个合理大小的自助样本（这里是20），这至少会随机产生一个初始分割点在 $x_1=0$ 或 $x_2=0$ 附近的树．仅仅使用 20 个自助样本，bumping 找到了图 8.13 的右图中展示的接近最优的分割．如果我们添加一系列独立于类别标签的噪声特征，贪婪的生成树的算法的缺点会被加重．则生成树的算法不能区分 $x_1$ 或 $x_2$，并且将会更加迷路．
因为 bumping 在训练数据上比较了不同的模型，必须保证模型近似有相同的复杂度．在树的情形下，这意味着在每个自助样本上生成终止结点个数相同的树．bumping 在很难最优化拟合准则的问题中也有帮助，或许是因为缺少光滑性．技巧是在自助样本上优化一个不同的、但更方便的准则，接着选择在训练样本上产生原始准则达到最优的模型．