核岭回归（Kernel Ridge Regression）算法的原理与计算过程
题目描述
核岭回归（Kernel Ridge Regression, KRR）是一种结合了岭回归（L2正则化线性回归）和核技巧（Kernel Trick）的回归算法。它能够有效地处理非线性关系，同时通过正则化避免过拟合。我们的任务是理解KRR如何将线性模型扩展到非线性场景，并掌握其从模型构建到求解的完整计算过程。
解题过程
- 问题回顾：岭回归
岭回归是线性回归的L2正则化形式。对于一个线性模型 \(f(\mathbf{x}) = \mathbf{w}^T \mathbf{x} + b\)，其目标是最小化带有L2惩罚项的损失函数：
\[ \min_{\mathbf{w}, b} \sum_{i=1}^{n} (y_i - \mathbf{w}^T \mathbf{x}_i - b)^2 + \alpha \|\mathbf{w}\|_2^2 \]
其中，\(\alpha\) 是控制正则化强度的超参数。其解析解可以通过求解正规方程得到。然而，标准的岭回归只能学习输入特征 \(\mathbf{x}\) 的线性组合。
- 引入核技巧处理非线性
当数据中存在非线性关系时，我们希望将原始特征 \(\mathbf{x} \in \mathbb{R}^d\) 映射到一个更高维（甚至无限维）的特征空间 \(\mathcal{H}\) 中，即 \(\phi(\mathbf{x})\)。在这个高维空间中，数据可能变得线性可分或线性关系更明显。模型变为：
\[ f(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b \]
直接计算 \(\phi(\mathbf{x})\) 可能非常困难（维度灾难）。核技巧的核心思想是，我们不需要显式地知道映射 \(\phi\) 是什么，也不需要直接计算高维向量 \(\mathbf{w}\) 和 \(\phi(\mathbf{x})\)，而是通过一个核函数 \(K(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle\) 来隐式地计算高维空间中的内积。常用的核函数包括多项式核、高斯径向基（RBF）核等。
- 核岭回归的优化问题
将岭回归的模型应用到特征映射后的空间，优化问题变为：
\[ \min_{\mathbf{w}, b} \sum_{i=1}^{n} (y_i - \mathbf{w}^T \phi(\mathbf{x}_i) - b)^2 + \alpha \|\mathbf{w}\|_2^2 \]
为了简化，通常假设数据已经中心化，即 \(b = 0\)（可以通过预处理数据减去均值来实现）。因此，问题简化为：
\[ \min_{\mathbf{w}} \|\mathbf{y} - \Phi \mathbf{w}\|_2^2 + \alpha \|\mathbf{w}\|_2^2 \]
其中，\(\mathbf{y} = [y_1, y_2, ..., y_n]^T\) 是目标值向量，\(\Phi\) 是设计矩阵，其第 \(i\) 行为 \(\phi(\mathbf{x}_i)^T\)。
- 求解核岭回归：表示定理
根据表示定理（Representer Theorem），上述优化问题的最优解 \(\mathbf{w}^*\) 可以表示为训练样本在特征空间中映射的线性组合：
\[ \mathbf{w}^* = \sum_{i=1}^{n} \beta_i \phi(\mathbf{x}_i) = \Phi^T \boldsymbol{\beta} \]
这里，\(\boldsymbol{\beta} = (\beta_1, \beta_2, ..., \beta_n)^T\) 是一个新的权重系数向量。这个定理的意义在于，它将优化变量从高维（可能无限维）的 \(\mathbf{w}\) 转换为了 \(n\) 维的 \(\boldsymbol{\beta}\)。
- 推导核岭回归的解析解
将 \(\mathbf{w} = \Phi^T \boldsymbol{\beta}\) 代入简化后的优化目标函数中：
\[ \|\mathbf{y} - \Phi (\Phi^T \boldsymbol{\beta}) \|_2^2 + \alpha \| \Phi^T \boldsymbol{\beta} \|_2^2 \]
计算L2范数：
\[ = (\mathbf{y} - \Phi \Phi^T \boldsymbol{\beta})^T (\mathbf{y} - \Phi \Phi^T \boldsymbol{\beta}) + \alpha (\Phi^T \boldsymbol{\beta})^T (\Phi^T \boldsymbol{\beta}) \]
\[ = \mathbf{y}^T \mathbf{y} - 2 \mathbf{y}^T \Phi \Phi^T \boldsymbol{\beta} + \boldsymbol{\beta}^T \Phi \Phi^T \Phi \Phi^T \boldsymbol{\beta} + \alpha \boldsymbol{\beta}^T \Phi \Phi^T \boldsymbol{\beta} \]
我们引入格拉姆矩阵（Gram Matrix）\(\mathbf{K}\)，其中 \(K_{ij} = K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\)。因此，\(\Phi \Phi^T = \mathbf{K}\)。
目标函数简化为：
\[ = \mathbf{y}^T \mathbf{y} - 2 \mathbf{y}^T \mathbf{K} \boldsymbol{\beta} + \boldsymbol{\beta}^T \mathbf{K} \mathbf{K} \boldsymbol{\beta} + \alpha \boldsymbol{\beta}^T \mathbf{K} \boldsymbol{\beta} \]
为了最小化这个关于 \(\boldsymbol{\beta}\) 的函数，我们对其求梯度并令其为零：
\[ \nabla_{\boldsymbol{\beta}} = -2 \mathbf{K} \mathbf{y} + 2 \mathbf{K} \mathbf{K} \boldsymbol{\beta} + 2 \alpha \mathbf{K} \boldsymbol{\beta} = 0 \]
假设 \(\mathbf{K}\) 是满秩的（通常通过选择适当的核函数和 \(\alpha > 0\) 来保证），我们可以两边同时左乘 \(\mathbf{K}^{-1}\) 并除以2：
\[ -\mathbf{y} + \mathbf{K} \boldsymbol{\beta} + \alpha \boldsymbol{\beta} = 0 \]
整理得到：
\[ (\mathbf{K} + \alpha \mathbf{I}) \boldsymbol{\beta} = \mathbf{y} \]
其中，\(\mathbf{I}\) 是 \(n \times n\) 的单位矩阵。最终，我们得到核岭回归的解析解：
\[ \boldsymbol{\beta} = (\mathbf{K} + \alpha \mathbf{I})^{-1} \mathbf{y} \]
- 预测新样本
对于一个新的样本 \(\mathbf{x}_{\text{new}}\)，其预测值 \(f(\mathbf{x}_{\text{new}})\) 为：
\[ f(\mathbf{x}_{\text{new}}) = \mathbf{w}^{*T} \phi(\mathbf{x}_{\text{new}}) = (\Phi^T \boldsymbol{\beta})^T \phi(\mathbf{x}_{\text{new}}) = \boldsymbol{\beta}^T \Phi \phi(\mathbf{x}_{\text{new}}) \]
再次利用核函数，\(\Phi \phi(\mathbf{x}_{\text{new}})\) 是一个向量，其第 \(i\) 个元素是 \(K(\mathbf{x}_i, \mathbf{x}_{\text{new}})\)。我们记这个向量为 \(\mathbf{k}_{\text{new}} = [K(\mathbf{x}_1, \mathbf{x}_{\text{new}}), ..., K(\mathbf{x}_n, \mathbf{x}_{\text{new}})]^T\)。
因此，预测公式非常简洁：
\[ f(\mathbf{x}_{\text{new}}) = \boldsymbol{\beta}^T \mathbf{k}_{\text{new}} = \sum_{i=1}^{n} \beta_i K(\mathbf{x}_i, \mathbf{x}_{\text{new}}) \]
总结
核岭回归的关键步骤是：1) 通过核函数隐式地将数据映射到高维特征空间以捕捉非线性；2) 利用表示定理将优化变量转换为样本空间的系数向量；3) 通过求解线性方程组 \((\mathbf{K} + \alpha \mathbf{I}) \boldsymbol{\beta} = \mathbf{y}\) 得到模型参数 \(\boldsymbol{\beta}\)；4) 对新样本的预测是训练样本目标值的加权和，权重由 \(\boldsymbol{\beta}\) 和核函数决定。KRR的优点在于能够处理非线性且具有解析解，缺点是当样本量 \(n\) 很大时，求逆一个 \(n \times n\) 的矩阵计算成本较高。