核岭回归（Kernel Ridge Regression）算法的原理与计算过程
题目描述
核岭回归（Kernel Ridge Regression, KRR）是一种结合核技巧与岭回归（L2正则化线性回归）的非线性回归算法。给定数据集 \(\{(x_i, y_i)\}_{i=1}^n\)（\(x_i \in \mathbb{R}^d\), \(y_i \in \mathbb{R}\)），KRR的目标是学习一个非线性映射函数 \(f(x)\)，使其能对未知样本进行准确预测。该算法通过核函数隐式地将输入数据映射到高维特征空间，并在高维空间中求解带正则化的线性回归问题，从而避免复杂的高维计算。
解题过程
- 问题形式化
- 岭回归的优化目标为最小化损失函数：
\[ J(w) = \|y - Xw\|^2 + \alpha \|w\|^2 \]
其中 $ X $ 为设计矩阵（每行一个样本），$ y $ 为标签向量，$ \alpha $ 为正则化系数。
- 通过核技巧，假设 \(w = \sum_{i=1}^n \beta_i \phi(x_i)\)（表示定理），其中 \(\phi(\cdot)\) 为高维特征映射。此时模型可写为 \(f(x) = \sum_{i=1}^n \beta_i K(x, x_i)\)，\(K(x_i, x_j) = \langle \phi(x_i), \phi(x_j) \rangle\) 为核函数。
- 核化岭回归的推导
- 将 \(w\) 的表达式代入岭回归目标函数，并定义核矩阵 \(K\)（满足 \(K_{ij} = K(x_i, x_j)\)）和系数向量 \(\beta = [\beta_1, \dots, \beta_n]^T\)。
- 重构损失函数：
\[ J(\beta) = \|y - K\beta\|^2 + \alpha \beta^T K \beta \]
其中 $ K\beta $ 对应预测值（因 $ f(X) = K\beta $），第二项中 $ \|w\|^2 = \beta^T K \beta $ 来自内积运算。
- 求解闭式解
- 对 \(J(\beta)\) 求导并令导数为零：
\[ \frac{\partial J}{\partial \beta} = -2K^T (y - K\beta) + 2\alpha K \beta = 0 \]
由于 $ K $ 对称（$ K^T = K $），化简得：
\[ (K + \alpha I) \beta = y \]
- 解得系数向量：
\[ \beta = (K + \alpha I)^{-1} y \]
需保证 $ K + \alpha I $ 可逆（$ \alpha > 0 $ 时正定）。
- 预测新样本
- 对于新样本 \(x_{\text{new}}\)，预测值为：
\[ f(x_{\text{new}}) = \sum_{i=1}^n \beta_i K(x_{\text{new}}, x_i) = k_{\text{new}}^T \beta \]
其中 $ k_{\text{new}} = [K(x_{\text{new}}, x_1), \dots, K(x_{\text{new}}, x_n)]^T $.
- 算法特点与复杂度
- 优点：通过核函数处理非线性关系，闭式解无需迭代优化。
- 缺点：需存储核矩阵（空间复杂度 \(O(n^2)\)），求逆时间复杂度 \(O(n^3)\)，故适用于中小规模数据。
- 常用核函数：高斯核 \(K(x, y) = \exp(-\frac{\|x-y\|^2}{2\sigma^2})\)、多项式核等。
总结
核岭回归通过核技巧将线性岭回归扩展为非线性模型，其核心步骤包括核化目标函数、推导闭式解及核矩阵计算。算法在保持岭回归抗过拟合能力的同时，灵活拟合复杂数据分布。