5.8 正则化与再生核希尔伯特空间 😱

本节从更广阔的正则化方法和再生核希尔伯特空间角度来理解样条函数。本节技术性较强，没有兴趣或难以接受的读者可跳过。

一般性的正则化问题可写为：

\begin{matrix} (5.42) & min_{f \in H} [\sum_{i = 1}^{N} L (y_{i}, f (x_{i})) + λ J (f)] \end{matrix}

其中 $L (y, f (x))$ 为一个损失函数， $J (f)$ 为惩罚项的范函， $H$ 为一个函数空间， $J (f)$ 在 $H$ 上有定义。Girosi et al. (1995) 介绍了一个较广义的惩罚项范函形式：

\begin{matrix} (5.43) & J (f) = \int_{R^{d}} \frac{| \tilde{f} (s) |^{2}}{\tilde{G} (s)} d s \end{matrix}

其中的 $\tilde{f}$ 为 $f$ 的傅立叶变换， $\tilde{G}$ 为某个随着 $‖ s ‖ \to \infty$ 衰减到 0 的正值函数。这样用 $1 / \tilde{G}$ 增加了这样 $f$ 中的高频成分的惩罚程度。文章中证明了在一些附加假设下，解的形式为：

\begin{matrix} (5.44) & f (X) = \sum_{k = 1}^{K} α_{k} ϕ_{k} (X) + \sum_{i = 1}^{N} θ_{i} G (X - x_{i}) \end{matrix}

其中的 $ϕ_{k}$ 可组成惩罚项范函 $J$ 的零空间（null space）， $G$ 为 $\tilde{G}$ 的逆傅里叶变换。平滑样条和薄板样条均被这个模型框架所涵盖。这个解的形式有非常值得关注的优点，即使等式 5.42 中的准测函数定义在无限维度的空间上，但其解是有限维度的。稍后会介绍几个具体的例子。

5.8.1 核函数构建的函数空间

最优化问题 5.42 的一个重要的子类，建立在一个正定核函数 $K (x, y)$ 上¹，其对应的函数空间 $H_{K}$ 被称为 再生核希尔伯特空间（reproducing kernel Hilbert space，RKHS）。惩罚项范函 $J$ 也是以核函数的方式定义的。下面会简要地介绍这类方法，内容借鉴于 Wahba (1990) 和 Girosi et al. (1995)，以及 Evgeniou et al. (2000) 很棒的概括。

假设 $x$ 和 $y$ 为 $R^{p}$ 中的两个点²。将核函数中第二个参数视为索引，那么它变成第一个参数的函数。则 ${K (\cdot, y), y \in R^{p}}$ 为一个单变量函数的集合，建立在这个函数集合上的线性生成空间 $H_{K}$ 中的元素，即为这个集合中任意元素的线性组合 $f (x) = \sum_{m} α_{m} K (x, y_{m})$ 。假设 $K$ 函数存在本征展开（eigen-expansion）：

\begin{matrix} (5.45) & K (x, y) = \sum_{i = 1}^{\infty} γ_{i} ϕ_{i} (x) ϕ_{i} (y) \end{matrix}

其中 $γ_{i} \geq 0$ ， $\sum_{i = 1}^{\infty} γ_{i}^{2} < \infty$ 。那么 $H_{K}$ 中的元素可以用这些本征函数（eigen-function）来表达：

\begin{matrix} (5.46) & f (x) = \sum_{i = 1}^{\infty} c_{i} ϕ_{i} (x) \end{matrix}

其约束条件为

\begin{matrix} (5.47) & ‖ f ‖_{H_{K}}^{2} \overset{def}{=} \sum_{i = 1}^{\infty} \frac{c_{i}^{2}}{γ_{i}} < \infty \end{matrix}

其中 $‖ f ‖_{H_{K}}$ 为由 $K$ 定义的范式。将空间 $H_{K}$ 上的式 5.42 惩罚项范函定义为范式的平方 $J (f) = ‖ f ‖_{H_{K}}^{2}$ 。可将 $J (f)$ 理解为广义的岭回归惩罚项，在展开式 5.45 中大本征值（eigenvalue）对应的本征函数被惩罚的程度更轻，反之亦然。

重写 5.42：

\begin{matrix} (5.48) & min_{f \in H_K} [\sum_{i = 1}^{N} L (y_{i}, f (x_{i})) + λ ‖ f ‖_{H_{K}}^{2}] \end{matrix}

或等价地：

\begin{matrix} (5.49) & min_{{c_{j}}_{1}^{\infty}} [\sum_{i = 1}^{N} L (y_{i}, \sum_{j = 1}^{\infty} c_{j} ϕ_{j} (x_{i})) + λ \sum_{j = 1}^{\infty} \frac{c_{j}^{2}}{γ_{j}}] \end{matrix}

可证明（Wahba, 1990；以及练习 5.15）式 5.48 的解为有限维度，并且可写为：

\begin{matrix} (5.50) & f (x) = \sum_{i = 1}^{N} α_{i} K (x, x_{i}) \end{matrix}

基函数 $h_{i} (x) = K (x, x_{i})$ （视为第一个参数的函数）又被称为 $H_{K}$ 空间中在 $x_{i}$ 点的 取值代表（representer of evaluation），因为对任意 $f \in H_{K}$ 都有 $⟨ K (\cdot, x_{i}), f ⟩ = f (x_{i})$ 。另外， $⟨ K (\cdot, x_{i}), K (\cdot, x_{j}) ⟩ = K (x_{i}, x_{j})$ （这就是 $H_{K}$ 的再生性质），所以对 $f (x) = \sum_{i =}^{N} α_{i} K (x, x_{i})$ ：

\begin{matrix} (5.51) & J (f) = \sum_{i = 1}^{N} \sum_{j = 1}^{N} K (x_{i}, x_{j}) α_{i} α_{j} \end{matrix}

利用式 5.50 和 5.51，可将式 5.48 简化至一个有限维度的最小化问题：

\begin{matrix} (5.52) & min_{α} L (y, K α) + λ α^{T} K α \end{matrix}

这里用向量的方式重写， $K$ 为 $N \times N$ 的矩阵，其第 i 行第 j 列的元素为 $K (x_{i}, y_{j})$ ，以此类推。式 5.52 可以使用简单的数值方法得到最优解。这种将无限维度问题，如等式 5.48 或 5.49，简化至有限维度问题的现象，在支持向量机（第十二章）领域中称为 核性质（kernel property）。

可以从贝叶斯的角度理解这类模型，可将 $f$ 视为均值为 0 的平稳高斯过程的一次实现，其先验协方差函数为 $K$ 。特征分解可得到一系列正交本征函数 $ϕ_{j} (x)$ 和对应的方差 $γ_{j}$ 。典型的场景中，“平滑”的函数 $ϕ_{j}$ 的先验方差 $γ_{j}$ 比较大，“粗糙”的 $ϕ_{j}$ 的先验方差小。式 5.48 中的惩罚项为先验概率对联合似然度的贡献，对先验方差小的函数成分惩罚程度更大（可对比式 5.43）。

简单起见，我们对 $H$ 中的所有元素都加以了惩罚，如同等式 5.48 所示。更一般地，我们可能希望对 $H$ 中的部分元素不做处理，比如第 5.4 节中的三次平滑样条的线性函数。第 5.7 节的多维薄板样条和张量积样条同样属于这个范畴。在这类场景中，可用一个更方便的表达形式 $H = H_{0} ⨁ H_{1}$ ，其中的 零空间（null space） 由诸如 $x$ 的低阶多项式等不被惩罚的成分。惩罚项则变为 $J (f) = ‖ P_{1} f ‖$ ，其中的 $P_{1}$ 为将 $f$ 正交投影到 $H_{1}$ 的转换。解的形式则为 $f (x) = \sum_{j = 1}^{M} β_{j} h_{j} (x) + \sum_{i = 1}^{N} α_{i} K (x, x_{i})$ ，其中的第一项即代表着在 $H_{0}$ 上的展开。从贝叶斯的角度， $H_{0}$ 中成分的系数有不正确的先验概率和无限的方差。

5.8.2 再生核希尔伯特空间的例子

上述的模型框架由核函数 $K$ 和损失函数 $L$ 的选择所控制。首先考虑使用平方误差损失函数的回归。这时的式 5.48 成为加惩罚的最小二乘，其解可用类似于等式 5.49 的形式表述为一个无限维度的广义岭回归问题：

\begin{matrix} (5.53) & min_{{c_{j}}_{1}^{\infty}} \sum_{i = 1}^{N} {(y_{i} - \sum_{j = 1}^{\infty} c_{j} ϕ_{j} (x_{i}))}^{2} + λ \sum_{j = 1}^{\infty} \frac{c_{j}^{2}}{γ_{j}} \end{matrix}

或也可等价地写为类似式 5.52 的形式：

\begin{matrix} (5.54) & min_{α} (y - K α)^{T} (y - K α) + λ α^{T} K α \end{matrix}

可以轻松地得到 $α$ 的解：

\begin{matrix} (5.55) & \hat{α} = (K + λ I)^{- 1} y \end{matrix}

并有：

\begin{matrix} (5.56) & \hat{f} (x) = \sum_{j = 1}^{N} {\hat{α}}_{j} K (x, x_{j}) \end{matrix}

拟合值的长度为 $N$ 的向量为：

\begin{aligned} \hat{f} & = K \hat{α} \\ (5.57) & = K (K + λ I)^{- 1} y \\ (5.58) & = (I + λ K^{- 1})^{- 1} y \end{aligned}

估计式 5.57 在空间统计学（spatial statistics）中也被称为高斯随机场（field）的 克里金（kriging） 估计（Cressie, 1993）。同时等式 5.58 可类比平滑样条拟合的等式 5.17（第 5.4 节，第 154 页）。

惩罚多项式回归（Penalized Polynomial Regression）

考虑核函数 $K (x, y) = (⟨ x, y ⟩ + 1)^{d}$ ， $x, y \in R^{p}$ ，共有 $M = (\binom{p + d}{d})$ 个本征函数，它们生成了 $R^{d}$ 上级数为 $d$ 的多项式空间。例如，当 $p = 2$ 、 $d = 2$ 、 $M = 6$ ：

\begin{aligned} (5.59) & K (x, y) & = 1 + 2 x_{1} y_{1} + 2 x_{2} y_{2} + x_{1}^{2} y_{1}^{2} + x_{2}^{2} y_{2}^{2} + 2 x_{1} x_{2} y_{1} y_{2} \\ (5.60) & = \sum_{m = 1}^{M} h_{m} (x) h_{m} (y) \end{aligned}

其中

\begin{matrix} (5.61) & h (x)^{T} = (1, \sqrt{2} x_{1}, \sqrt{2} x_{2}, x_{1}^{2}, x_{2}^{2}, \sqrt{2} x_{1} x_{2}) \end{matrix}

可将 $h$ 用 $K$ 的 $M$ 个正交本征函数和本征值来表述为：

\begin{matrix} (5.62) & h (x) = V D_{γ}^{\frac{1}{2}} ϕ (x) \end{matrix}

其中 $D_{γ} = diag (γ_{1}, γ_{2}, \dots, γ_{M})$ ， $V$ 为 $M \times M$ 的正交矩阵。

若要求惩罚多项式回归问题的解：

\begin{matrix} (5.63) & min_{{β_{m}}_{1}^{M}} \sum_{i = 1}^{N} {(y_{i} - \sum_{m = 1}^{M} β_{m} h_{m} (x_{i}))}^{2} + λ \sum_{m = 1}^{M} β_{m}^{2} \end{matrix}

将式 5.62 代入式 5.63，可得到一个类似于式 5.53 的待最优化表达式。

基函数的个数 $M = (\binom{p + d}{d})$ 可能会非常大，通常会大于 $N$ 。从式 5.55 可见，若将解函数以核函数的方式表达，只需要计算 $N^{2}$ 次核函数，计算解则需要 $O (N^{3})$ 的计算量。

This simplicity is not without implications. 式 5.61 中每一个多项式 $h_{m}$ 中均包含一个来自于 $K$ 的具体形式的尺度因子，这对等式 5.63 中的惩罚项会产生影响。在下一节中会详述。

高斯径向基函数（Gaussian Radial Basis Functions）

在上例中所选择的核函数，可使得模型为多项式的形式，并且在高维度下易于内积的计算。本例中选择的核函数，使模型为式 5.50 的形式。

例如，高斯核函数 $K (x, y) = e^{- ν ‖ x - y ‖^{2}}$ 与平方误差损失函数组合，可得到高斯径向基函数展开形式的回归模型：

\begin{matrix} (5.64) & k_{m} (x) = e^{- ν ‖ x - x_{m} ‖^{2}}, m = 1, \dots, N \end{matrix}

每个基函数的以某个训练样本的输入特征向量 $x_{m}$ 为均值点。其系数通过式 5.54 来估计。

**图 5.13**：混合分布样本的径向基函数 $k_k(x)$，其尺度参数 $\nu=1$。基函数的中心点 $x_m$ 为从 200 个样本中随机选取的 5 个点。 — **图 5.13**：混合分布样本的径向基函数 $k_{k} (x)$ ，其尺度参数 $ν = 1$ 。基函数的中心点 $x_{m}$ 为从 200 个样本中随机选取的 5 个点。

图 5.13 展示了第二章中混合分布例子中第一个坐标（输入变量）在 $R^{1}$ 上的径向基函数。图中给出了 200 个基函数 $k_{m} (x) = K (x, x_{m})$ 中的 5 个。

**图 5.14**：左图为混合分布样本中第一个变量的 $200\times200$ 矩阵 $\mathbf{K}$ 的前 16 个标准化的特征向量。这可视为等式 5.45 中本征函数的一个估计 $\hat{\phi}\_l$，表达为 $\mathbb{R}^1$ 上的函数，图中以颜色来标记实际观测值。它们从左上开始按行的方向排列。右图为将左图中的函数重调节尺度后的版本 $h_l=\sqrt{\hat{\gamma}\_l}\hat{\phi}\_l$，for which the kernel computes the “inner product.” — **图 5.14**：左图为混合分布样本中第一个变量的 $200 \times 200$ 矩阵 $K$ 的前 16 个标准化的特征向量。这可视为等式 5.45 中本征函数的一个估计 ${\hat{ϕ}}_{l}$ ，表达为 $R^{1}$ 上的函数，图中以颜色来标记实际观测值。它们从左上开始按行的方向排列。右图为将左图中的函数重调节尺度后的版本 $h_{l} = \sqrt{{\hat{γ}}_{l}} {\hat{ϕ}}_{l}$ ，for which the kernel computes the “inner product.”

图 5.14 展示了 $x \in R^{1}$ 上的径向核函数的隐含特征空间。这里计算了 $200 \times 200$ 的核函数矩阵 $K$ ，以及其特征分解 $Φ D_{γ} Φ^{T}$ 。可将 $Φ$ 的列向量及其对应的 $D_{γ}$ 中的特征值作为式 5.45 的本征展开的经验估计（empirical estimate）³。尽管特征向量是离散的，但可将它们表示为 $R^{1}$ 上的函数（练习 5.17）。

**图 5.15**：$\mathbf{K}$ 的 50 个最大的特征值；第 30 个之后的值可视为 0。 — **图 5.15**： $K$ 的 50 个最大的特征值；第 30 个之后的值可视为 0。

图 5.15 展示了 $K$ 的 50 个最大的特征值。头几个对应的本征函数比较平滑，随着特征值的依次减小，本征函数也越来越不平滑。这呼应了等式 5.49 中的惩罚项，即高阶函数的系数的惩罚程度要大于低阶函数的系数。图 5.14 的右图展示了对应的特征空间上本征函数的形式。

\begin{matrix} (5.65) & h_{ℓ} (x) = \sqrt{{\hat{γ}}_{ℓ}} {\hat{ϕ}}_{ℓ} (x), ℓ = 1, \dots, N \end{matrix}

注意 $⟨ h (x_{i}), h (x_{i^{'}}) ⟩ = K (x_{i}, x_{i^{'}})$ 。利用特征值的尺度调节将大部分函数快速地收缩至 0，在这个例子中只留下了 12 个有效的维度。之后的最优化问题成为了一个岭回归，如等式 5.63 所示。因此尽管隐含的特征空间理论上是无限维度的，但对基函数的不同收缩程度使得有效维度大幅降低。核函数尺度参数 $ν$ 在这里也有影响；较大的 $ν$ 意味着更多局部的函数 $k_{m}$ ，并会增加特征空间的有效维度。更多细节参考 Hastie and Zhu (2006)。

另外，薄板样条（第 5.7 节）可通过以下核函数的径向基函数展开生成 (Girosi et al., 1995)：

\begin{matrix} (5.66) & K (x, y) = ‖ x - y ‖^{2} \log (‖ x - y ‖) \end{matrix}

第 6.7 节会更详尽地讨论径向基函数。

支持向量分类器（Support Vector Classifiers）

第十二章的支持向量机在二分类模型中的形式为 $f (x) = α_{0} + \sum_{i = 1}^{N} α_{i} K (x, x_{i})$ ，其系数通过最小化得出：

\begin{matrix} (5.67) & min_{α_{0}, α} {\sum_{i = 1}^{N} [1 - y_{i} f (x_{i})]_{+} + \frac{λ}{2} α^{T} K α} \end{matrix}

其中 $y_{i} \in {- 1, 1}$ ， $[z]_{+}$ 表示 $z$ 的正部。可将其视为含有线性约束条件的二次优化问题，需要通过二次规划算法求解。其名称中的“支持向量”，是因为通常有很多的 ${\hat{α}}_{i} = 0$ （由于等式 5.67 中损失函数分段为 0 的性质），因此 $\hat{f}$ 是在 $K (\cdot, x_{i})$ 子集上的展开。更多细节见第 12.3.3 节。

本节练习

练习 5.15

定义在集合 $X$ 上的对称函数 $K : X \times X \to R$ 为正定核函数，如果对任意的 $n \in N$ ， $x_{1}, \dots, x_{n} \in X$ ， $c_{1}, \dots, c_{n} \in R$ ，都满足 $\sum_{i = 1}^{n} \sum_{j = 1}^{n} c_{i} c_{j} K (x_{i}, x_{j}) \geq 0$ 。（Wikipedia） ↩︎
注意这里的 $x$ 和 $y$ 是同一个空间上的两个点，而不是通常的输入变量和输出变量。本段的原文直译较难理解，所以译者进行了转述，所以行文逻辑与原文改动较大。 ↩︎
原文脚注2： $Φ$ 的第 l 行为 $ϕ_{l}$ 在 $N$ 个样本每一个点上的估计。或者说， $Φ$ 的第 i 行为在点 $x_{i}$ 上对基函数 $ϕ (x_{i})$ 的估计向量。虽然在理论上 $ϕ$ 有无穷多个元素，但这里的估计值最多只有 $N$ 个维度。 ↩︎