16.3 学习的集成

利用上一节中的深入理解，我们可以创造一个更有效而且高效的集成模型（ensemble model）。同样地，我们考虑以下形式的模型函数：

$$f(x) = \alpha_0 + \sum_{T_k\in\mathcal{T}} \alpha_k T_k(x) \tag{16.8}$$

其中的 $\mathcal{T}$ 是一个基函数的字典集，一般是树模型的集合。在梯度提升方法和随机森林中，$|\mathcal{T}|$ 会非常大，最终的模型中会非常经常地包含了几千个树模型。在上一节中，我们说明了带收缩的梯度提升方法是拟合一个在这个树模型空间上 $L_1$ 正则化的单调的路径。

Friedman and Popescu (2003) 提出了一个混合的方法，可以将这个过程分解成两个阶段：

从训练数据集中归纳出一个有限的基函数字典集 $\mathcal{T}_L=\{T_1(x),T_2(x),\dots,T_M(x)\}$。
通过在这个字典集上套索路径的拟合，构建一族模型函数 $f_\lambda(x)$： $$\alpha(\lambda) = \arg\min_\alpha \sum_{i=1}^N L[y_i, \alpha_0 + \sum_{m=1}^M \alpha_m T_m(x_i)] + \lambda \sum_{m=1}^M |\alpha_m| \tag{16.9}$$

从这个最简单的形式来看，如果将 $\mathcal{T}_L$ 看作是由梯度提升或随机森林算法中得出的树模型集合，那么这个模型可以被看作是提升方法或随机森林的一种后期处理（post-processing）方式。在这些树模型上拟合套索路径，我们通常（最终）会只使用到一个被大幅缩小的（基函数）集合，这可能会为未来的预测应用节省计算量和储存空间。下一节会介绍这个方法的一些改进，可以降低集成（字典集） $\mathcal{T}_L$ 中的相关性，从而可以改进套索后期处理模型的表现。

我们将这个方法应用在垃圾邮件数据上的随机森林集成模型上，作为一个初步的演示。

**图 16.6**：垃圾邮件数据上的套索后期处理方法（式 16.9）的应用。蓝色的水平线是在垃圾邮件数据上拟合的随机森林的测试误差，使用了 1000 个树模型并且训练至最大的深度（$m=7$；参考算法 15.1）。锯齿状的蓝色曲线是在前 500 个树模型上通过套索回归进行后期处理后的测试误差，横轴是其中参数非零的树模型的个数。橙色的曲线/水平线代表者一个修改版本的随机森林，在训练每个树模型时使用了训练集的 5% 随机抽样，而且限制了这些树模型的深度（通常是六个终结点）。后期处理对这个随机森林集成模型带来了更巨大的提升。

图 16.6 展示了一个套索后期处理可以为随机森林（蓝色曲线）带来不小的提升，并且将森林中树的个数从原来的 1000 个降低至大约 40 个。后期处理过的模型表现与梯度提升方法的表现相似。橙色曲线代表一个修改版本的随机森林，它更大地降低了树模型之间的相关性。具体来说，它在训练每个树模型时使用了训练样本 5% 的随机（无放回）子抽样，并且限制了这些树模型的深度（大约六个终结点）。这个模型的后期处理带来了更巨大的提升，并将训练计算成本降低至原来的 1/100。不过，这个后期处理过的模型的表现和蓝色曲线还有一些差距。

16.3.1 利于学习的集成

并不是所有的集成 $\mathcal{T}_L$ 都可以在后期处理中表现良好。拿基函数来说，为了让后期处理能够有效，我们希望（基函数）集合能够很好地覆盖所需要的特征空间，并且彼此之间的差异足够大。

Friedman and Popescu (2003) 从数值积分（numerical quadrature）和重要性抽样（importance sampling）中得到了启发。他们将未知函数视为一个积分：

$$f(x) = \int \beta(\gamma) b(x;\gamma) d\gamma \tag{16.10}$$

其中的 $\gamma\in\Gamma$ 是标记基函数 $b(x;\gamma)$ 的参数。例如，如果基函数是树模型，那么 $\gamma$ 指代了分割变量、分割点、以及终结点中的取值。数值积分就是寻找 $M$ 个取值点 $\gamma_m\in\Gamma$ 的集合，以及相应的权重 $\alpha_m$，使得 $f_M(x)=\alpha_0+\sum_{m=1}^M\alpha_mb(x;\gamma_m)$ 在 $x$ 的定义域上可以很好地近似 $f(x)$。重要性抽样就是对 $\gamma$ 进行随机抽样，但会在 $\Gamma$ 的空间上有相关性的（relevant）区域中赋予更高的权重。 Friedman and Popescu (2003) 提出了一个使用了损失函数来衡量（缺乏）相关程度的指标，在训练集上计算：

$$Q(\gamma) = \min_{c_0,c_1} \sum_{i=1}^N L(y_i, c_0+c_1 b(x_i;\gamma)) \tag{16.11}$$

如果只能选出一个基函数来（例如，单个的树模型），那么它会是全局最小的点 $\gamma^*=\arg\min_{\gamma\in\Gamma}Q(\gamma)$。在选择 $\gamma$ 的过程中引入随机性，会必然地引入非最优的参数值，即有 $Q(\gamma)\geq Q(\gamma^*)$。作者提出了一个衡量当前样本 $\mathcal{S}$ 的特征宽度 $\sigma$ 的一个自然的指标：

$$\sigma = \operatorname{E}_\mathcal{S}[Q(\gamma)-Q(\gamma^*)] \tag{16.12}$$

如果 $\sigma$ 太小（窄），则意味着存在过多相似的 $b(x;\gamma_m)$，并且他们与 $b(x;\gamma^*)$ 都比较相似。
如果 $\sigma$ 太大（宽），则意味着 $b(x;\gamma_m)$ 之间有很大的差异性，不过可能会包含了很多不相关的函数 $b$。

Friedman and Popescu (2003) 用子抽样作为一个引入随机性的机制，从而得出了他们的集成生成（ensemble-generation）算法 16.2。

算法 16.2 ISLE 集成生成.

$f_0(x)=\arg\min_c\sum_{i=1}^NL(y_i;c)$
从 $m=$ 到 $m=M$，迭代进行：
1. $\gamma_m=\arg\min_\gamma\sum_{i\in S_m(\eta)}L(y_i,f_{m-1}(x_i)+b(x_i;\gamma))$
2. $f_m(x)=f_{m-1}(x)+\nu b(x;\gamma_m)$
$\mathcal{T}_\text{ISLE}=\{b(x;\gamma_1),b(x;\gamma_2),\dots,b(x;\gamma_M)\}$

$S_m(\eta)$ 指的是在训练观测样本上，通常无放回的，大小为 $N\cdot\eta$（$\eta\in(0,1]$）的子抽样。他们的模拟实验结果建议选择 $\eta\leq\frac{1}{2}$，并且当 $N$ 比较大时选择 $\eta\sim1/\sqrt{N}$。$\eta$ 的降低意味着随机性的提升，因而宽度 $\sigma$ 的提升。参数 $\nu\in[0,1]$ 为随机化过程引入了记忆：$nu$ 越大，这个过程越会避开与之前曾加入的函数相似的 $b(x;\gamma)$。一些熟知的随机化策略都可看作是算法 16.2 的特殊情况：

自助聚合（bagging）中 $\eta=1$，但是有放回的抽样，并且 $\nu=0$。Friedman and Hall (2007) 说明了 $\eta=1/2$ 的无放回抽样等价于 $\eta=1$ 的有放回抽样，而前者是更高效的方法。
随机森林（random forest）的抽样是相似的，而由对分割变量的选择引入了更多的随机性。算法 16.1 中降低 $\eta<1/2$ 和在随机森林中降低 $m$ 有相似的效果，但不会导致第 15.4.2 节中提到的潜在偏差。
带收缩的梯度提升（gradient boosting with shrinkage），式 10.41，使用了 $\eta=1$，但一般不会产生足够的宽度 $\sigma$。
随机梯度提升（stochastic gradient boosting，Friedman, 1999）则与上述算法完全一致。

作者建议的取值是 $\nu=01$ 和 $\eta\leq\frac{1}{2}$，并且将这个组合过程（集成的生成和后期处理）称为 重要性抽样学习集成（importance sampled learning ensemble，ISLE）。

**图 16.7**：在垃圾邮件数据集上的重要性抽样学习集成（ISLE）拟合。这里使用了 $\eta=1/2$，$\nu=0.05$，五个终结点的树模型。在这个例子中，套索后期处理过的集成模型并没有提升预测误差，但它将树模型的个数降低至原来的 $1/5$。

图 16.7 在垃圾邮件数据上展示了一个 ISLE 的表现。它并没有提升预测结果的表现，不过能够得到一个更简约的模型。需要注意的是在实践中，后期处理包括了对式 16.9 中正则参数 $\lambda$ 的选择，这可以通过交叉验证来完成。这里展示了在测试数据上的整体路径曲线，只是为了简单地演示后期处理的作用。

**图 16.8**：在一个回归模拟例子上的集成方法演示。$\text{GBM}(0.1,0.01)$ 指的是一个参数为 $(\eta,\nu)$ 的梯度提升模型（GBM）。图中根据（已知的）真实输出变量函数计算出了均方误差。值得注意的是子抽样的梯度提升模型（绿色）比完整的梯度提升模型（橙色）表现更好。套索后期处理过的模型得到的误差与它们相似。随机森林的在后期处理过后表现得到提升，但两者的表现都没有其他模型好。

图 16.8 在一个回归例子中展示了不同 ISLE 的结果。模型的生成函数为：

$$f(X) = 10 \cdot \prod_{j=1}^5 e^{-2X_j^2}+\sum_{j=6}^{35}X_j \tag{16.13}$$

其中的 $X\sim U[0,1]^{100}$（后 65 个变量是噪声变量）。输出变量 $Y=f(X)+\epsilon$，$\epsilon\sim\mathcal{N}(0,\sigma^2)$；令 $\sigma=1.3$，则噪声信号比率大致为 2。训练集的大小为 1000，均方误差 $\operatorname{E}(\hat{f}(X)-f(x))^2$ 的估计是在 500 个样本的测试集上的平均。子抽样的梯度提升模型曲线（GBM，浅蓝色）是第 10.12 节中介绍的随机梯度提升（Friedman, 1999）的一个应用，在这个例子中它的表现好于梯度提升。

16.3.2 规则的集成

本节介绍树模型集成方法的一个变体，它聚焦于单个的规则（Friedman and Popescu, 2003）。在第 9.3 节讨论 PRIM 方法时也曾用到过规则（rule）。它的想法是通过由集合中的每个树模型构建出一组规则，来扩大树模型的集成。

图 16.9 展示了一个小型的树模型，它的节点用数字做了编号。从这个树模型可以推导出以下的规则：

$$\begin{align} R_1(x) &= I(X_1 < 2.1) \\ R_2(x) &= I(X_1 \geq 2.1) \\ R_3(x) &= I(X_1 \geq 2.1) \cdot I(X_3 \in \{S\}) \\ R_4(x) &= I(X_1 \geq 2.1) \cdot I(X_3 \in \{M,L\}) \\ R_5(x) &= I(X_1 \geq 2.1) \cdot I(X_3 \in \{S\}) \cdot I(X_7 < 4.5) \\ R_6(x) &= I(X_1 \geq 2.1) \cdot I(X_3 \in \{S\}) \cdot I(X_7 \geq 4.5) \end{align}\tag{16.14}$$

规则 1、4、5、和 6 的一个线性扩展可以与这个树模型本身等价（练习 16.3）；因此，式 16.14 是这个树模型的一个过完备（over-complete）基。

为一个集成 $\mathcal{T}$ 中的每个树模型 $T_m$，都可以构建它的小型规则集成 $\mathcal{T}_\text{RULE}^m$，然后再将所有这些规则集成结合成一个更大的集成：

$$\mathcal{T}_\text{RULE} = \bigcup_{m=1}^M \mathcal{T}_\text{RULE}^m \tag{16.15}$$

然后就和其他对集成的处理方式一样，可以通过套索或类似的正则化过程进行后期处理。

这个从更复杂的树模型中推导规则的方法有以下几点好处：

模型空间被扩大了，可能会提升模型的表现。
规则比树模型更容易理解，所以可能会得出一个更简洁的模型。
通常也会自然地在 $\mathcal{T}_\text{RULE}$ 中添加每个特征变量 $X_j$ 本身，因此可以使这个集成也有构建线性函数模型的能力。

**图 16.10**：模拟例子（式 16.13）的 20 次实现上的规则集成的均方误差。

Friedman and Popescu (2008) 在很多例子中演示了这个方法的能力，这也包括了式 16.13 的模拟例子。图 16.10 展示了这个模拟例子的二十次模拟样本得出的（从真实模型函数计算的）均方误差的箱线图。模型的拟合用的都是在自动模式下的 Rulefit 软件，可从本书的网页¹下载。

在和图 16.8 中所用的同样的训练集上，基于规则的模型达到了 1.06 的均方误差。尽管这比那个图中的最优结果要差一些，但由于这里是通过交叉验证来选择最终的模型的，所以两者并不具备可比性。

本节练习

练习 16.3

证明使用式 16.14 中的规则 1、4、5、和 6 拟合的线性模型与这个树模型相应的回归树拟合完全一样。证明如果使用了一个对数几率回归模型拟合，那么在分类问题中这个结论也成立。

原文脚注3：本书首页为 www-stat.stanford.edu/ElemStatLearn ↩︎