在本书第一版的第 10.12.2 节中，我们对梯度提升算法得出的一序列模型和在高维特征空间上的正则化模型拟合做了一个类比。我们可看出提升版本的线性回归和套索回归（lasso，第 3.4.2 节）之间存在着紧密的关联，这也是对上述类比的主要的启发。我们和其他研究者都对这这些关联进行了后续的研究，本节将介绍当前我们在这个领域的思考。本节将从原来的启发思路入手，这些内容（相较于第十章）更适合被留在本章集成学习的内容中。
16.2.1 惩罚回归
通过与在一个较大基扩展上的带惩罚线性回归进行类比，可以帮助我们更直观地理解梯度提升方法中的收缩策略的成功之处（第 464 页，第 10.12 节）。假设 $T=\{\mathcal{T}_k\}$ 为所有的 $J$ 个终结点的回归树的字典（函数集合），它们可以在训练集的样本处计算取值，并可作为定义在 $\mathbb{R}^p$ 上的基函数。则线性模型为：
$$f(x) = \sum_{k=1}^K \alpha_k T_k(x) \tag{16.1}$$其中的 $K=\operatorname{card}(T)$。假设用最小二乘方法来估计模型中的系数。由于这样的回归树的个数可能远远大于我们可以拿到的最大的训练数据样本数，所以必须要进行某些形式的正则化。令 $\alpha(\lambda)$ 为下式的解：
$$\min_\alpha \left\{ \sum_{i=1}^N \left(y_i - \sum_{k=1}^K \alpha_k T_k(x_i)\right)^2 + \lambda \cdot J(\alpha) \right\}\tag{16.2}$$其中的 $J(\alpha)$ 是一个关于系数的函数，它一般会对取值大的系数加以惩罚。以下为一些例子：
$$\begin{align} &J(\alpha) = \sum_{k=1}^K |\alpha_k|^2 & \text{ridge regression} \tag{16.3} \\ &J(\alpha) = \sum_{k=1}^K |\alpha_k| & \text{lasso} \tag{16.4} \end{align}$$这些在第 3.4 节介绍过。如之前所述，当 $\lambda$ 的取值适中或较大时，套索问题的解会趋于稀疏；会有很多的 $\hat{\alpha}_k(\lambda)=0$。也就是说在所有的回归树函数中只有一小部分会进入到模型（16.1）中。
这貌似也是合理的，因为在对某个任意的目标函数进行近似时，在所有备选的回归树中可能只有一小比例的函数是有相关性的。不过不同目标函数的相关（回归树）子集应该是不同的。那些非零的系数，相较于它们相应的最小二乘估计值来说1，会被套索回归收缩到更小的绝对值：$|\hat{\alpha}_k(\lambda)|<|\hat{\alpha}_k(0)|$。随着 $\lambda$ 增大，（所有的）系数会向零收缩，并且每个系数最终都会变成零。
因为有非常大量的基函数 $T_k$，所以对带有套索惩罚项（式 16.4）的式 16.2 直接求解是不太可能的。不过存在一个前向分段的可行计算策略，它可以准确地近似出套索的作用，并且与提升方法和前向分段的算法 10.2 非常相似。算法 16.1 给出了计算过程。尽管在这里的问题描述中是用的回归树基函数 $T_k$，但这个算法可被用在任意类型的基函数集合上。在起始的第一步中，所有的系数都设置为零；这对应着式 16.2 中的 $\lambda=\infty$。在后续的每步中，选择能够最好地拟合当前残差的那个树函数 $T_{k^*}$，即步骤 2.1。将它对应的系数 $\check{\alpha}_{k^*}$ 增加或减去一个无穷小的常量，即步骤 2.2，而同时保持其他系数 $\check{\alpha}_k,k\neq k^{*}$ 不变。原则上可以不断地迭代这个过程，直到或者所有的残差都等于零，或者 $\beta^*=0$。当 $K<N$ 时后者情况可能会出现，那么此时的系数值就等于最小二乘的解。这也对应着式 16.2 当 $\lambda=0$ 的情况。
算法 16.1：前向分段线性回归
- 初始化 $\check{\alpha}_k=0,k=1,\dots,K$。令 $\epsilon>0$ 为一个小的常数，$M$ 为一个较大的数。
- 从 $m=1$ 到 $m=M$：
- $(\beta^*,k^*)=\arg\min_{\beta,k}\sum_{i=1}^N(y_i-\sum_{l=1}^K\check{\alpha}_lT_l(x_i)-\beta T_k(x_i))^2$
- $\check{\alpha}_{k^*}\leftarrow\check{\alpha}_{k^*}+\epsilon\cdot\operatorname{sign}(\beta^*)$
- 得出结果 $f_M(x)=\sum_{k=1}^K\check{α}_kT_k(x)$。
在算法 16.1 经过了 $M<\infty$ 次迭代后，很多的系数取值会为零，也就是那些还从未在（2.1）中被选中过的基函数的系数。另一些系数的绝对值会倾向小于它们所对应的最小二乘解的绝对值，即 $|\check{\alpha}_k(M)|<|\hat{\alpha}_k(0)|$。所以这个 $M$ 次迭代后的解从性质上与套索回归相似，$M$ 与 $\lambda$ 逆相关。
 的结果，其中 $M=250$、$\epsilon=0.01$。](https://public.guansong.wang/eslii/ch16/eslii_fig_16_01.png)
图 16.1 用第三章中的前列腺癌症数据来做一个示例。这里没有用到回归树 $T_k(X)$ 的基函数，而是直接用了原本的特征变量 $X_k$；所以也就是一个多元线性回归模型。左图展示了套索回归中不同的边界参数 $t=\sum_k|\alpha_k|$ 时估计系数的路径曲线。右图展示了前向分段的算法 16.1 的结果，其中 $M=250$、$\epsilon=0.01$。（图 16.1 中的左图和右图分别与图 3.10 和图 3.19 的右图完全一样。）这两个图异常地相似。
在一些场景中这种相似性不仅是在性质表现上的。例如，如果所有的基函数 $T_k$ 都互不相关，那么随着 $\epsilon\downarrow0$ 并且 $M\uparrow$ 使得 $M\epsilon\to t$，算法 16.1 得出的结果与边界参数 $t=\sum_k|\alpha_k|$ 的套索回归的解完全一样。（而且与之类似，路径上所有的解都完全一样。）树基函数类型的回归元自然不会是不相关的。不过如果系数 $\hat{\alpha}_k(\lambda)$ 都是 $\lambda$ 的单调函数，那么这两个方法的解的路径也是完全一样的。当变量之间的相关性不高的时候，这个条件通常可以满足。当 $\hat{\alpha}_k(\lambda)$ 不是 $\lambda$ 的单调函数，则两者解的路径不相同。与套索回归相比，算法 16.1 的解随着正则化参数值的变动而发生的变动会更缓慢一些。
Efron et al. (2004) 在 $\epsilon$ 趋于极限的情况下给出了精确的解路径，更准确地描述了它们的关系。他们说明了套索回归和前向分段方法的系数路径都是分段线性函数。这个结论使得他们提出了一个高效的算法，可以用和单次最小二乘拟合一样的计算成本得出整个的系数路径。这就是第 3.8.1 节中详细介绍的 最小角回归（least angle regression） 算法2。
Hastie et al. (2007) 展示了这个无穷小量前向分段算法（FS₀）是在拟合一个单调版本的套索回归，它在每一步中在给定了系数路径的弧长增加量条件下最优化地降低损失函数（参考第 16.2.3 节和第 3.8.1 节）。当 $\epsilon>0$ 时它的弧长（增加量）是 $M\epsilon$，所以是与步骤数量成比例的。
带有收缩的（式 10.41）树模型提升方法（算法 10.3）与算法 16.1 非常相像，它的学习率参数 $\nu$ 与 $\epsilon$ 相对应。当使用了平方误差损失函数时，（与算法 16.1）唯一的区别是在每一次迭代中选择最优树模型的方法是通过标准的自上而下的贪婪树归纳（tree induction）算法。当使用了其他损失函数时，例如自适应提升（AdaBoost）的指数损失函数和二项偏差损失函数，Rosset et al. (2004a) 证明了和这里相似的结果。因此，可以将带有收缩的树模型提升方法视为在所有可能的（$J$ 个终结点）树函数上的某种单调的且变形了的（ill-posed）回归，并使用了套索惩罚项（式 16.4）作为正则项。第 16.2.3 节也会再对此加以讨论。
无收缩情况下的树提升方法（当式 10.41 中的 $\nu=1$ 时）与前向分段回归相似，它也与和它接近但更激进的最优子集选择方法相似，后者是对非零系数的个数进行惩罚 $J(\alpha)=\sum_k|\alpha|^0$。当特征变量中存在一小部分极显著变量时，最优子集方法通常比较有效。但当特征变量中存在中等比例的强变量时，已证明最优子集的选择可能会异常的贪婪（Copas, 1983），与例如套索回归或岭回归这种不那么激进的回归方法相比它的结果表现不佳。在提升方法中使用了收缩后通常可以得到更好的表现结果，这也从另一方面印证了上述的说明。
16.2.2 “押宝稀疏性” 原则
如上一节所见，提升方法的带收缩前向分段策略是近似地对一个（和算法 16.1）同样的损失函数做最小化，并带有了套索类型 $L_1$ 的惩罚项。这个模型是逐渐建立起来的，它在“模型空间”中进行搜寻，并将一些重要的自变量衍生出的收缩过的基函数加入到模型中。与之相反，$L_2$ 惩罚项从计算量上来说处理起来要容易得多，如第 12.3.7 节所述。在选定好匹配某个特定的正定核函数的基函数和 $L_2$ 惩罚项后，求解对应的最优化问题就不需要进行对每个基函数显式的遍历搜寻。
然而，有些时候提升方法对例如支持向量机等方法的显著优势可能很大程度来自于使用了 $L_1$ 惩罚项而不是 $L_2$ 惩罚项。使用 $L_1$ 惩罚项的收缩效果更适用于稀疏性的场景中，即（在所有的备选基函数中）只有少数基函数带有非零的系数。
我们通过一个来自 Friedman et al. (2004) 的简单例子来说明这个观点。假设有 10,000 个数据点，并且我们的模型是一百万个树模型的线性组合。如果这些树模型的总体样本（真实）系数是服从一个高斯分布的，那么我们已知从贝叶斯（最优）的角度来说最优的预测是岭回归（练习 3.6）。也就是说，在拟合系数时（最优方法）应该使用 $L_2$ 而不是 $L_1$ 的惩罚项。但从另一方面来说，如果（真实）系数中只有一小部分（例如 1000 个）非零，那么套索回归（$L_1$ 惩罚项）的表现更好。我们可将后者理解为一个稀疏的（sparse）场景，而前者（高斯分布的系数）是一个密集的（dense）场景。不过值得注意的是，密集的场景中即使 $L_2$ 惩罚项是最佳的，但其实两个方法的表现都不好；这是因为要对如此多的非零系数进行估计，这里的数据量就太少了。这也是维数灾难在后果。在一个稀疏的场景中，由于非零稀疏的个数比较小，$L_1$ 惩罚项有可能会表现良好。但 $L_2$ 惩罚项仍然表现不佳。
或者可以说，$L_1$ 惩罚项的使用遵循了高维问题中所谓的“押宝稀疏性”原则：
选择在稀疏问题中表现良好的方法即可，因为在密集问题中没有表现好的方法。
以下是一些需要注意的说明：
- 在任意某个应用中，稀疏性或密集性的程度取决于未知的真实目标函数，以及所选择的基函数字典 $\mathcal{T}$。
- 稀疏与密集的相对概念是与训练样本集的大小以及（或者）噪声信号比率（noise-to-signal ratio，NSR）相关联的。更大的训练集会让我们可以得到标准误差更小的系数估计。与之相似，在给定同样大小的样本集大小时，噪声信号比（NSR）越小，我们就可以识别出越多的非零系数。
- 基函数字典的大小也会有影响。虽然扩大字典集合的规模可能会使模型函数变成一个更稀疏的表达式，但是这也让求解的搜索过程更加困难，并导致解的方差更大。
图 16.2 通过模拟的线性模型来演示了上述的说明。我们在分类和回归问题中对比了岭回归（ridge）和套索回归（lasso）。每一次模拟中有 50 个观测样本、300 个独立的高斯分布自变量。第一行中的所有 300 个系数都是非零的，由一个高斯分布随机生成。第二行中有 10 个非零的高斯分布的系数，第三行中有 30 个非零的高斯分布的系数。在回归问题中，在线性的预测函数 $\eta(X)=X^T\beta$ 上添加了标准高斯分布的噪声，从而得到一个连续的输出变量。在分类问题中，通过对数几率（logit）逆函数将线性的预测函数转化为一个概率，并基于这个概率生成二元的输出变量。图中有五个不同的噪声信号比率，它们是通过对 $\eta(X)$ 预先做了缩放再生成输出变量而得到的。在两个问题中噪声信号比率的定义都是 $\text{NSR}=\operatorname{Var}(Y|\eta(X))/\operatorname{Var}(\eta(X))$。岭回归和套索回归的系数路径都是在对应着从 1 到 50 自由度的（细节参考第 3.4 节）50 个 $\lambda$ 取值下拟合得出的。模型的评估用到了很大的测试集（回归问题为无限大，二元分类问题为 5000）3，并且在每个场景中都选择出了使得测试集误差最小化的 $\lambda$ 取值。在图中，回归问题中展示了可解释变异（variance explained）的百分比，分类问题中展示了（相对于一个基线误差率 0.5 的）可解释误分类误差（misclassification error explained）百分比。每个场景中都进行了 20 次模拟。
需要注意的是在分类问题中我们使用了平方误差损失函数来拟合二元输出变量。同时也需要注意的是我们不是使用训练数据选择 $\lambda$，而是在不同场景中为每个方法（在测试集上）选择了最优的结果。$L_2$ 惩罚项在所有场景中都表现不佳。套索回归仅在两个它所适用的场景中（稀疏的系数）表现良好。与之前的预期一致，模型的表现随着噪声信号比率的升高而变差（分类问题中比较轻微），并随着模型的密集程度增加而变差。这个变化差异在分类问题中没有在回归问题中那么明显。
这些实证的结论也被很多理论研究的结果所证实（Donoho and Johnstone, 1994；Donoho and Elad, 2003；Donoho, 2006b；Candes and Tao, 2007），这些结论都支持了在稀疏的场景中 $L_1$ 惩罚项的估计结果更好。
16.2.3 正则化路径、过拟合、和间隔 😱
通常会看到提升方法“不会过拟合（does not overfit）”，或更精确地表述为“不轻易过拟合（slow to overfit）”。之前章节曾为随机森林对这种现象做过一部分的解释：误分类误差，相对于均方误差，对方差更不敏感，而提升方法领域中的主要研究对象是分类问题。本节将说明提升模型的正则化路径的“表现良好（well behaved）”，并且在某些特定的损失函数下可得出一个很好的极限形式。
图 16.3 展示了在一个回归问题的模拟中套索和无穷小量前向分段（FS₀）的系数路径。数据中包含 1000 个高斯分布的特征变量字典，以 20 个为一组，组内有强相关性（$\rho=0.95$），而不同组之间无相关性。生成模型中有 50 个系数非零的变量，它们从每个组中抽取一个，系数的值是从标准高斯分布中随机生成的。最后添加进去了一个高斯分布噪声，噪声信号比率为 0.72（练习 16.1）。FS₀ 是算法 16.1 的极限形式，其中的步长参数 $\epsilon$ 收缩到了零（第 3.8.1 节）。对特征变量的分组是想要模拟相邻树模型之间的相关性；而且在前向分段算法中，这样的设置是想得出一个理想化版本的带收缩的梯度提升方法。由于都是分段线性的，所以这两个算法的系数路径都可以被准确地计算出来（参考第 3.8.1 节中的最小角回归）。
两者在图中的系数路径只在前面一段是相似的。在路径的后段中，前向分段的路径趋于单调并且平滑，而套索的路径则会大范围地跳动。这是由子集中特征变量的强相关性所造成的：套索回归在某种程度上会受多重共线性问题的影响（练习 3.28）。
两个模型的表现非常相似（图 16.4），而且它们的最小值点都基本一致。在后期中前向分段方法更缓慢地出现过拟合，这可能也是其平滑的路径曲线的一个表现。
Hastie et al. (2007) 证明了 FS₀ 是求解一个使用平方误差损失函数的单调版本的套索回归问题。令 $\mathcal{T}^a=\mathcal{T}\cup\{-\mathcal{T}\}$ 为包含了 $\mathcal{T}$ 中每个基函数的负数版本而得到的扩大字典集。假设模型为 $f(x)=\sum_{T_k\in\mathcal{T}^a}\alpha_kT_k$，其中的系数非负 $\alpha_k\geq0$。在这个扩展的特征空间上，套索回归的系数路径是正的，而 FS₀ 的系数路径是单调非减的（nondecreasing）。
单调的套索回归路径可写为一个微分方程：
$$\frac{\partial\alpha}{\partial\ell} = \rho^{ml}(\alpha(\ell)) \tag{16.6}$$其中的初始化条件为 $\alpha(0)=0$，$\ell$ 为路径 $\alpha(\ell)$ 的 $L_1$ 弧长（练习 16.2）。单调套索的移动方向 $\rho^{ml}(\alpha(\ell))$（速度向量，velocity vector），是随路径的每单位 $L_1$ 弧长增加可带来的损失函数降低的二次速率（quadratic rate）的最优方向。由于 $\rho^{ml}(\alpha(\ell))\geq0,\forall k,\ell$，所以解的路径是单调的。
与之相似，套索回归也可以用一个类似式 16.6 的微分方程的解的形式来表达，不过移动方向是随路径的每单位 $L_1$ 范数（而不是弧长）增加可带来的损失函数降低的最优方向。这就导致了它们不一定必须是正的，所以套索回归的路径不一定是单调的。
在这个扩大的字典集中，系数为正的约束条件可以避免一些明显的歧义性，所以是一个比较合理的约束条件。这也与树模型提升方法有天然的联系：我们总是寻找与当前的残差正向相关的树模型。
也有一些看法认为提升方法之所以（在二元分类问题中）表现良好，是因为它们有类似于第 4.5.2 节和第十二章中的支持向量机模型中的间隔（margin）最大化的性质。Schapire et al. (1998) 将一个拟合模型 $f(x)=\sum_k\alpha_kT_k(x)$ 的标准化 $L_1$ 间隔定义为：
$$m(f) = \min_i \frac{y_i f(x_i)}{\sum_{k=1}^K|\alpha_k|} \tag{16.7}$$其中的最小化是在训练样本上取到的，并且 $y_i\in\{-1,+1\}$。与支持向量机中的 $L_2$ 间隔（式 4.40）不同，$m(f)$ 衡量的是距离最近训练样本点的 $L_\infty$ 距离（最大坐标距离）。
最大坐标距离的定义
最大坐标距离，或 $L_\infty$ 范数的定义：
$$|x|_\infty = \max {|x_1|, |x_2|, \dots, |x_n|}$$
Schapire et al. (1998) 证明了在可分的数据中，自适应提升方法（Adaboost）的每次迭代都会提高 $m(f)$ 值，最后收敛到一个间隔对称的解上。Rätsch and Warmuth (2002) 证明了带收缩的自适应提升方法会渐进地收敛到一个 $L_1$ 间隔最大化的解上。Rosset et al. (2004a) 则研究了一般损失函数的式 16.2 正则化模型。他们证明了随着 $\lambda\downarrow0$，对某个特定的损失函数的解会收敛到一个间隔最大化的结果。他们专门为自适应提升的指数损失函数以及二项偏差损失函数证明了这个结论。
总结一下本节的一些结论，我们可以对提升方法分类器概括如下：
提升方法的一系列分类器构成了走向间隔最大化解的一个 $L_1$ 正则化的单调的路径。
当然，路径尽头的间隔最大化解可能是一个表现并不好的过拟合解，如在图 16.5 中的例子所示。早停（early stopping）策略也就等价于在路径中选取一个点，这应该通过一个验证数据集来完成。
gbm，使用的收缩因子为 0.02。在 10,000 个树模型之后，$m(f)$ 不再变化。注意当间隔曲线穿过了零水平线（横轴）时，训练误差变成了零。右图展示了测试误差曲线，它在 240 个树模型时达到了最小值。在这个例子中，如果任其达到收敛的解，自适应提升会急剧地过拟合。
本节练习
练习 16.1
请详细地说明一下在第 16.2.3 节的模拟数据中，应该如何生成组内相关组间不相关的数据。
练习 16.2
Let $\alpha(t)\in\mathbb{R}^p$ be a piecewise-differentiable and continuous coefficient profile, with α(0) = 0. The L1 arc-length of α from time 0 to t is defined by
$$\Lambda(t) = \int_0^t |\dot{\alpha}(t)|_1 dt \tag{16.16}$$Show that Λ(t) ≥ |α(t)|1 , with equality iff α(t) is monotone.
练习 16.4
用程序完成图 16.2 中介绍的模拟研究。