核岭回归（Kernel Ridge Regression）的数学推导与优化过程

题目描述：核岭回归是一种结合了核技巧与岭回归（L2正则化线性回归）的非线性回归方法。它通过将输入数据映射到高维特征空间，并在该空间中执行岭回归，从而处理非线性关系。本题要求详细解释其数学推导、核技巧的应用、优化问题的建立与求解过程，以及预测公式的推导。

解题过程：

1. 问题定义与岭回归基础：
   • 给定训练数据集 \(\{(x_i, y_i)\}_{i=1}^n\)，其中 \(x_i \in \mathbb{R}^d\)，\(y_i \in \mathbb{R}\)。
   • 岭回归的目标是最小化带有L2正则化的平方损失函数：

\[ \min_{w \in \mathbb{R}^d} \sum_{i=1}^n (y_i - w^T x_i)^２ + \lambda \|w\|^2 \]

 其中 $ \lambda > 0 $ 是正则化参数，防止过拟合。

2. 引入特征映射与核技巧：
   • 为处理非线性，将输入 \(x\) 映射到高维特征空间 \(\phi(x) \in \mathbb{R}^D\)（\(D\) 可能无穷大）。模型变为：

\[ f(x) = w^T \phi(x) \]

• 岭回归问题重写为：

\[ \min_{w \in \mathbb{R}^D} \sum_{i=1}^n (y_i - w^T \phi(x_i))^2 + \lambda \|w\|^2 \]

• 直接求解 \(w\) 困难（因 \(D\) 可能很大），利用核技巧避免显式计算 \(\phi(x)\)。根据表示定理，最优解 \(w^*\) 可表示为特征映射的线性组合：

\[ w^* = \sum_{i=1}^n \alpha_i \phi(x_i) \]

 其中 $ \alpha = (\alpha_1, \dots, \alpha_n)^T $ 是待求系数向量。

3. 优化问题的重构：
   • 将 \(w = \sum_{j=1}^n \alpha_j \phi(x_j)\) 代入目标函数：
     • 预测值： \(f(x_i) = \sum_{j=1}^n \alpha_j \phi(x_j)^T \phi(x_i) = \sum_{j=1}^n \alpha_j K(x_j, x_i)\)，其中 \(K(x_j, x_i)\) 是核函数（如高斯核 \(K(x, y) = \exp(-\frac{\|x-y\|^2}{2\sigma^2})\)）。
     • 损失项： \(\sum_{i=1}^n \left(y_i - \sum_{j=1}^n \alpha_j K(x_j, x_i)\right)^2 = \|Y - K\alpha\|^2\)，其中 \(K\) 是核矩阵（\(K_{ij} = K(x_i, x_j)\)），\(Y = (y_1, \dots, y_n)^T\)。
     • 正则项： \(\lambda \|w\|^2 = \lambda \alpha^T K \alpha\)（因为 \(\|w\|^2 = \sum_{i,j} \alpha_i \alpha_j K(x_i, x_j)\)）。
   • 问题转化为：

\[ \min_{\alpha \in \mathbb{R}^n} \|Y - K\alpha\|^2 + \lambda \alpha^T K \alpha \]

4. 求解系数向量：
   • 目标函数是 \(\alpha\) 的二次函数，求梯度并令其为零：

\[ \frac{\partial}{\partial \alpha} \left( (Y - K\alpha)^T (Y - K\alpha) + \lambda \alpha^T K \alpha \right) = 0 \]

 计算梯度：
 - 第一项梯度： $ -2K^T (Y - K\alpha) = -2K (Y - K\alpha) $（因 $ K $ 对称）。
 - 第二项梯度： $ 2\lambda K \alpha $。
 - 合并得： $ -2K (Y - K\alpha) + 2\lambda K \alpha = 0 $。

• 化简得线性系统：

\[ K (Y - K\alpha) + \lambda K \alpha = 0 \implies K Y = (K^2 + \lambda K) \alpha \]

 由于 $ K $ 通常可逆，两边左乘 $ K^{-1} $：

\[ Y = (K + \lambda I) \alpha \implies \alpha = (K + \lambda I)^{-1} Y \]

 其中 $ I $ 是单位矩阵。

5. 预测与新数据点：
   • 对于新输入 \(x\)，预测值为：

\[ f(x) = \sum_{i=1}^n \alpha_i K(x_i, x) = K_x^T \alpha \]

 其中 $ K_x = [K(x_1, x), \dots, K(x_n, x)]^T $。

• 代入 \(\alpha\) 得：

\[ f(x) = K_x^T (K + \lambda I)^{-1} Y \]

6. 关键点总结：
   • 核岭回归通过核函数隐式实现非线性映射，避免"维度灾难"。
   • 解 \(\alpha\) 唯一存在，因 \(K + \lambda I\) 正定可逆（只要 \(\lambda > 0\)）。
   • 计算复杂度主要来自求逆 \(O(n^3)\)，适用于中小数据集。