基于核的岭回归（Kernel Ridge Regression）的对偶形式推导与求解过程
题目描述
岭回归（Ridge Regression）是一种经典的线性回归正则化方法，它在损失函数中加入L2正则项以防止过拟合。当我们希望模型能够捕捉非线性模式时，一种常见做法是通过“核技巧”（Kernel Trick）将数据隐式映射到高维特征空间，并在该空间中进行岭回归。这种基于核的岭回归模型称为核岭回归。本题目要求详细推导核岭回归的对偶形式，并解释其求解过程。这涉及从原始问题（Primal Problem）出发，利用表示定理（Representer Theorem）和拉格朗日对偶性，将原优化问题转化为一个完全由核函数表示的对偶问题，最终通过求解线性方程组得到模型预测函数。
解题过程
1. 原始岭回归问题的定义
给定训练集 \(\{(\mathbf{x}_i, y_i)\}_{i=1}^n\)，其中 \(\mathbf{x}_i \in \mathbb{R}^d\) 是特征向量，\(y_i \in \mathbb{R}\) 是连续标签。岭回归的优化目标为：
\[\min_{\mathbf{w} \in \mathbb{R}^d} \; \frac{1}{2} \sum_{i=1}^n (y_i - \mathbf{w}^\top \mathbf{x}_i)^2 + \frac{\lambda}{2} \|\mathbf{w}\|^2 \]
其中 \(\lambda > 0\) 是正则化系数，\(\|\cdot\|\) 表示向量的L2范数。这是一个关于权重向量 \(\mathbf{w}\) 的凸优化问题。
2. 引入特征映射与核技巧
为了处理非线性关系，我们引入一个非线性映射 \(\phi: \mathbb{R}^d \to \mathcal{H}\)，将原始特征映射到某个高维（甚至是无穷维）的再生核希尔伯特空间（RKHS）\(\mathcal{H}\)。此时模型变为：
\[f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x}) \]
优化问题变为：
\[\min_{\mathbf{w} \in \mathcal{H}} \; \frac{1}{2} \sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i))^2 + \frac{\lambda}{2} \|\mathbf{w}\|_{\mathcal{H}}^2 \]
这里 \(\|\cdot\|_{\mathcal{H}}\) 是 RKHS 中的范数。直接求解 \(\mathbf{w}\) 是困难的，因为 \(\phi(\mathbf{x}_i)\) 的维度可能极高。
3. 应用表示定理
根据表示定理（Representer Theorem），上述优化问题的最优解 \(\mathbf{w}^*\) 可以表示为训练样本映射的线性组合：
\[\mathbf{w}^* = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i) \]
其中 \(\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_n)^\top \in \mathbb{R}^n\) 是待求的组合系数。
代入模型，预测函数可写为：
\[f(\mathbf{x}) = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}) = \sum_{i=1}^n \alpha_i k(\mathbf{x}_i, \mathbf{x}) \]
这里 \(k(\mathbf{x}_i, \mathbf{x}) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}) \rangle\) 是核函数，例如高斯核 \(k(\mathbf{x}, \mathbf{z}) = \exp(-\gamma \|\mathbf{x} - \mathbf{z}\|^2)\)。我们无需显式计算 \(\phi\)，只需核函数。
4. 将对偶系数 \(\boldsymbol{\alpha}\) 的求解转化为优化问题
将 \(\mathbf{w} = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i)\) 代入原目标函数。
首先计算误差项：
\[\mathbf{w}^\top \phi(\mathbf{x}_j) = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j) = \sum_{i=1}^n \alpha_i k(\mathbf{x}_i, \mathbf{x}_j) \]
定义核矩阵 \(\mathbf{K} \in \mathbb{R}^{n \times n}\)，其中 \(K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)\)。记 \(\mathbf{y} = (y_1, \dots, y_n)^\top\)，则误差向量为：
\[\mathbf{y} - \mathbf{K} \boldsymbol{\alpha} \]
误差平方和：
\[\sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i))^2 = (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha})^\top (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha}) \]
其次计算正则项：
\[\|\mathbf{w}\|_{\mathcal{H}}^2 = \left\langle \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i), \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j) \right\rangle = \sum_{i=1}^n \sum_{j=1}^n \alpha_i \alpha_j k(\mathbf{x}_i, \mathbf{x}_j) = \boldsymbol{\alpha}^\top \mathbf{K} \boldsymbol{\alpha} \]
因此原目标函数等价为关于 \(\boldsymbol{\alpha}\) 的无约束优化问题：
\[\min_{\boldsymbol{\alpha} \in \mathbb{R}^n} \; \frac{1}{2} (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha})^\top (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha}) + \frac{\lambda}{2} \boldsymbol{\alpha}^\top \mathbf{K} \boldsymbol{\alpha} \]
5. 求解对偶系数
对目标函数关于 \(\boldsymbol{\alpha}\) 求梯度并令为零：
\[\nabla_{\boldsymbol{\alpha}} \left[ \frac{1}{2} (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha})^\top (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha}) + \frac{\lambda}{2} \boldsymbol{\alpha}^\top \mathbf{K} \boldsymbol{\alpha} \right] = 0 \]
展开：
\[-\mathbf{K}^\top (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha}) + \lambda \mathbf{K} \boldsymbol{\alpha} = 0 \]
由于 \(\mathbf{K}\) 对称（通常核函数满足对称性），即 \(\mathbf{K}^\top = \mathbf{K}\)，可得：
\[-\mathbf{K} \mathbf{y} + \mathbf{K}^2 \boldsymbol{\alpha} + \lambda \mathbf{K} \boldsymbol{\alpha} = 0 \]
提出 \(\mathbf{K}\)（注意 \(\mathbf{K}\) 可逆吗？不一定，但可整理方程）：
\[\mathbf{K} (\mathbf{K} \boldsymbol{\alpha} - \mathbf{y} + \lambda \boldsymbol{\alpha}) = 0 \]
若 \(\mathbf{K}\) 是满秩的，则可得：
\[\mathbf{K} \boldsymbol{\alpha} - \mathbf{y} + \lambda \boldsymbol{\alpha} = 0 \]
整理得到线性方程组：
\[(\mathbf{K} + \lambda \mathbf{I}_n) \boldsymbol{\alpha} = \mathbf{y} \]
其中 \(\mathbf{I}_n\) 是 \(n \times n\) 单位矩阵。
即使 \(\mathbf{K}\) 不满秩，上式也是原始优化问题的必要条件（可通过对目标函数直接求导并令为零推导出相同结果）。
6. 最终模型与预测
求解上述线性方程组得到对偶系数：
\[\boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I}_n)^{-1} \mathbf{y} \]
对于新的输入 \(\mathbf{x}_{\text{new}}\)，预测值为：
\[f(\mathbf{x}_{\text{new}}) = \sum_{i=1}^n \alpha_i k(\mathbf{x}_i, \mathbf{x}_{\text{new}}) \]
这即是核岭回归的完整模型。
关键点总结
- 核岭回归通过核技巧隐式地在高维特征空间中执行岭回归。
- 利用表示定理，将原问题的解表示为训练样本的核函数线性组合，从而将对权重向量 \(\mathbf{w}\) 的求解转化为对系数向量 \(\boldsymbol{\alpha}\) 的求解。
- 最终的求解归结为一个线性方程组，涉及核矩阵与正则化项。
- 该方法避免了显式计算高维特征映射，只需计算核函数，适用于非线性问题，但计算复杂度为 \(O(n^3)\)（因为要求解 \(n \times n\) 线性系统）。