核岭回归（Kernel Ridge Regression）的数学推导与对偶优化求解过程
题目描述
核岭回归（Kernel Ridge Regression, KRR）是一种结合了核方法（Kernel Method）与岭回归（Ridge Regression）的非线性回归算法。其核心思想是通过核技巧（Kernel Trick）将原始输入空间的数据映射到高维特征空间，并在该特征空间中执行岭回归（即带L2正则化的线性回归），从而实现对非线性关系的建模。题目要求推导核岭回归的对偶优化问题，解释其如何避免显式计算高维特征映射，并展示预测公式的导出过程。
解题过程
- 岭回归的原问题回顾
给定训练集 \(\{ (\mathbf{x}_i, y_i) \}_{i=1}^n\)，其中 \(\mathbf{x}_i \in \mathbb{R}^d\)，\(y_i \in \mathbb{R}\)。岭回归的目标是学习一个线性模型 \(f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b\)，通过最小化带有L2正则化的平方损失：
\[ \min_{\mathbf{w}, b} \ \frac{1}{2} \sum_{i=1}^n (y_i - \mathbf{w}^\top \mathbf{x}_i - b)^2 + \frac{\lambda}{2} \|\mathbf{w}\|^2 \]
其中 \(\lambda > 0\) 是正则化系数。
- 引入特征映射与核技巧
为处理非线性关系，引入一个非线性特征映射 \(\phi: \mathbb{R}^d \to \mathcal{H}\)，将输入映射到高维（甚至无限维）的特征空间 \(\mathcal{H}\)。模型变为：
\[ f(\mathbf{x}) = \mathbf{w}^\top \phi(\mathbf{x}) + b \]
其中 \(\mathbf{w} \in \mathcal{H}\)。对应的岭回归问题为：
\[ \min_{\mathbf{w}, b} \ \frac{1}{2} \sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i) - b)^2 + \frac{\lambda}{2} \|\mathbf{w}\|^2 \]
直接求解需要显式计算 \(\phi(\mathbf{x})\)，但 \(\mathcal{H}\) 可能维数极高。核技巧通过核函数 \(k(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)\) 隐式计算内积，避免显式映射。
- 对偶问题的推导
构建拉格朗日函数，将原问题转化为对偶形式。首先将目标函数写为：
\[ L(\mathbf{w}, b) = \frac{1}{2} \sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i) - b)^2 + \frac{\lambda}{2} \|\mathbf{w}\|^2 \]
对 \(b\) 求偏导并令为零：
\[ \frac{\partial L}{\partial b} = -\sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i) - b) = 0 \]
解得：
\[ b = \frac{1}{n} \sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i)) \]
代入原问题，可先集中求解 \(\mathbf{w}\)。对 \(\mathbf{w}\) 求偏导：
\[ \frac{\partial L}{\partial \mathbf{w}} = -\sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i) - b) \phi(\mathbf{x}_i) + \lambda \mathbf{w} = 0 \]
解得：
\[ \mathbf{w} = \frac{1}{\lambda} \sum_{i=1}^n (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i) - b) \phi(\mathbf{x}_i) \]
令 \(\alpha_i = \frac{1}{\lambda} (y_i - \mathbf{w}^\top \phi(\mathbf{x}_i) - b)\)，则：
\[ \mathbf{w} = \sum_{i=1}^n \alpha_i \phi(\mathbf{x}_i) \]
这表明最优权重 \(\mathbf{w}\) 是训练样本特征映射的线性组合，这是代表定理（Representer Theorem）的一个实例。
- 将对偶变量代入原问题
将 \(\mathbf{w} = \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j)\) 代入原模型：
\[ f(\mathbf{x}) = \sum_{j=1}^n \alpha_j \phi(\mathbf{x}_j)^\top \phi(\mathbf{x}) + b = \sum_{j=1}^n \alpha_j k(\mathbf{x}_j, \mathbf{x}) + b \]
将 \(\mathbf{w}\) 和 \(b\) 的表达式代入岭回归的平方损失项和正则项。定义核矩阵 \(\mathbf{K} \in \mathbb{R}^{n \times n}\)，其中 \(K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)\)，向量 \(\boldsymbol{\alpha} = [\alpha_1, \dots, \alpha_n]^\top\)，\(\mathbf{y} = [y_1, \dots, y_n]^\top\)，以及全1向量 \(\mathbf{1} = [1, \dots, 1]^\top\)。经过代数运算（推导略），原问题转化为关于 \(\boldsymbol{\alpha}\) 和 \(b\) 的优化问题：
\[ \min_{\boldsymbol{\alpha}, b} \ \frac{1}{2} (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha} - b \mathbf{1})^\top (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha} - b \mathbf{1}) + \frac{\lambda}{2} \boldsymbol{\alpha}^\top \mathbf{K} \boldsymbol{\alpha} \]
注意正则项 \(\|\mathbf{w}\|^2 = \boldsymbol{\alpha}^\top \mathbf{K} \boldsymbol{\alpha}\)，因为 \(\|\mathbf{w}\|^2 = \sum_{i,j} \alpha_i \alpha_j \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j) = \boldsymbol{\alpha}^\top \mathbf{K} \boldsymbol{\alpha}\)。
- 求解对偶问题
将对偶问题写为矩阵形式并求导。令目标函数为 \(J(\boldsymbol{\alpha}, b)\)。对 \(b\) 求偏导并令为零，得到：
\[ b = \frac{1}{n} \mathbf{1}^\top (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha}) \]
对 \(\boldsymbol{\alpha}\) 求偏导并令为零：
\[ \frac{\partial J}{\partial \boldsymbol{\alpha}} = -\mathbf{K} (\mathbf{y} - \mathbf{K} \boldsymbol{\alpha} - b \mathbf{1}) + \lambda \mathbf{K} \boldsymbol{\alpha} = 0 \]
代入 \(b\) 的表达式，整理后得到线性系统：
\[ (\mathbf{K} + \lambda \mathbf{I}) \boldsymbol{\alpha} = \mathbf{y} - b \mathbf{1} \]
结合 \(b\) 的方程，可联立求解。更常见的做法是考虑中心化后的形式：若先对数据去均值（即令 \(\sum_i \phi(\mathbf{x}_i) = 0\)），则 \(b=0\)，此时解简化为：
\[ \boldsymbol{\alpha} = (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{y} \]
实践中，通常使用中心化核矩阵 \(\tilde{\mathbf{K}} = \mathbf{H} \mathbf{K} \mathbf{H}\)，其中 \(\mathbf{H} = \mathbf{I} - \frac{1}{n} \mathbf{1} \mathbf{1}^\top\) 是中心化矩阵，此时 \(b\) 被吸收进中心化处理中。
- 预测公式
对于新样本 \(\mathbf{x}_*\)，预测值为：
\[ f(\mathbf{x}_*) = \sum_{i=1}^n \alpha_i k(\mathbf{x}_i, \mathbf{x}_*) + b \]
其中 \(\boldsymbol{\alpha}\) 和 \(b\) 由上述线性系统解得。整个预测过程仅依赖核函数计算，无需显式使用 \(\phi(\cdot)\)。
- 算法总结
- 输入：训练数据 \(\{ (\mathbf{x}_i, y_i) \}_{i=1}^n\)，核函数 \(k(\cdot, \cdot)\)，正则化参数 \(\lambda\)。
- 步骤：
- 计算核矩阵 \(\mathbf{K}\)，其中 \(K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)\)。
- 中心化 \(\mathbf{K}\) 和 \(\mathbf{y}\)（可选，以消除偏置项 \(b\) 或显式求解）。
- 解线性系统 \((\mathbf{K} + \lambda \mathbf{I}) \boldsymbol{\alpha} = \mathbf{y}\) 得到 \(\boldsymbol{\alpha}\)。
- 若未中心化，通过 \(b = \frac{1}{n} \sum_i (y_i - \sum_j \alpha_j K_{ij})\) 计算 \(b\)。
- 预测：对新样本 \(\mathbf{x}_*\)，计算 \(f(\mathbf{x}_*) = \sum_i \alpha_i k(\mathbf{x}_i, \mathbf{x}_*) + b\)。
关键点：核岭回归通过核技巧将非线性回归转化为高维空间中的线性问题，其解可表示为核函数的线性组合，避免了显式特征映射，同时岭正则化控制了模型复杂度防止过拟合。