核岭回归（Kernel Ridge Regression, KRR）的数学推导与对偶优化求解过程

字数 2402 2025-12-17 19:59:45

核岭回归（Kernel Ridge Regression, KRR）的数学推导与对偶优化求解过程

题目描述
核岭回归是岭回归（线性回归的L2正则化版本）在特征空间通过核技巧的扩展，用于解决非线性回归问题。其核心思想是：将原始特征空间的数据通过一个非线性映射Φ映射到高维（甚至无限维）特征空间，然后在特征空间中进行线性岭回归，并利用核函数避免显式计算映射Φ。本题将详细讲解核岭回归的目标函数构建、对偶问题的推导，以及如何通过求解对偶问题得到最终预测模型。整个过程从原始问题到对偶问题的转换是关键。

解题过程
假设我们有一个数据集 { (x_i, y_i) }，i=1,...,n，其中 x_i ∈ R^d 是输入特征，y_i ∈ R 是连续目标值。我们的目标是学习一个从输入到输出的非线性映射。

原始空间的目标函数
首先回顾线性岭回归。在原始特征空间中，岭回归模型为 f(x) = w^T x，其优化目标是最小化平方误差损失加上L2正则项：
min_w Σ_{i=1}^{n} (y_i - w^T x_i)^2 + λ ||w||^2
其中 λ > 0 是正则化系数，控制模型复杂度。
引入特征映射与对偶问题
对于非线性问题，我们引入一个非线性映射 Φ: R^d → H，将数据映射到高维特征空间 H。在这个空间中的线性模型为 f(x) = w^T Φ(x)。则目标函数变为：
min_w Σ_{i=1}^{n} (y_i - w^T Φ(x_i))^2 + λ ||w||^2
这里 w 是特征空间 H 中的权重向量，可能维度很高甚至无限维，因此直接求解 w 通常不可行。
表示定理的应用
根据表示定理（Representer Theorem），对于这种带有L2正则化的损失最小化问题，最优解 w* 可以表示为训练样本在特征空间中映射的线性组合：
w* = Σ_{j=1}^{n} α_j Φ(x_j)
其中 α = [α_1, ..., α_n]^T 是待求的系数向量。这个定理是关键，因为它将优化变量从高维的 w 转换为了 n 维的 α。
代入目标函数，转化为关于 α 的问题
将 w = Σ_j α_j Φ(x_j) 代入目标函数。首先计算模型预测：
f(x_i) = w^T Φ(x_i) = [Σ_j α_j Φ(x_j)]^T Φ(x_i) = Σ_j α_j Φ(x_j)^T Φ(x_i) = Σ_j α_j K(x_j, x_i)
其中 K(x_j, x_i) = Φ(x_j)^T Φ(x_i) 是核函数，它计算了两个样本在特征空间的内积，无需知道 Φ 的具体形式。常用核函数如高斯核 K(x, z) = exp(-γ ||x - z||^2)。

将 f(x_i) 的表达式代入平方误差项：
Σ_i (y_i - Σ_j α_j K(x_j, x_i))^2
定义核矩阵 K ∈ R^{n×n}，其中 K_{ij} = K(x_i, x_j)。定义向量 y = [y_1, ..., y_n]^T。则平方误差项可写为：
(y - Kα)^T (y - Kα)

接下来计算正则项 ||w||^2：
||w||^2 = w^T w = [Σ_i α_i Φ(x_i)]^T [Σ_j α_j Φ(x_j)] = Σ_i Σ_j α_i α_j Φ(x_i)^T Φ(x_j) = Σ_i Σ_j α_i α_j K(x_i, x_j) = α^T K α

因此，目标函数转化为关于 α 的问题：
min_α (y - Kα)^T (y - Kα) + λ α^T K α
求解对偶问题
这是一个关于 α 的无约束凸优化问题。我们对 α 求梯度并令其为零。展开目标函数：
J(α) = (y - Kα)^T (y - Kα) + λ α^T K α = y^T y - 2 y^T Kα + α^T K^T K α + λ α^T K α
由于 K 对称（核矩阵），K^T = K，所以：
J(α) = y^T y - 2 y^T Kα + α^T K^2 α + λ α^T K α = y^T y - 2 y^T Kα + α^T K (K + λI) α

对 α 求梯度：
∇_α J = -2 K y + 2 K (K + λI) α
令梯度为零：
-K y + K (K + λI) α = 0
由于 K 通常是满秩的（如果使用高斯核且数据点不同，K 正定），我们可以两边左乘 K^{-1}，得到：
-y + (K + λI) α = 0
因此，最优系数 α* 满足线性系统：
(K + λI) α = y

解这个线性系统即可得到 α* = (K + λI)^{-1} y。这里 I 是 n×n 单位矩阵。注意，由于 K 对称半正定，加上 λI 后矩阵正定，可逆。
预测新样本
对于一个新的输入 x，预测输出为：
f(x) = Σ_{j=1}^{n} α_j^* K(x_j, x)
即用学习到的 α* 与所有训练样本的核函数值加权求和。这体现了核方法的“记忆”特性：预测需要用到所有训练数据。
算法总结与复杂度
核岭回归的训练就是求解线性系统 (K + λI) α = y，时间复杂度为 O(n^3)（由于需要矩阵求逆或求解线性系统），空间复杂度为 O(n^2)（存储核矩阵）。因此，它不适合大规模数据，但非常适合中小规模非线性回归问题。

通过上述过程，我们将原始高维特征空间中的岭回归，通过表示定理和核技巧，转化为对偶空间中关于有限维 α 的优化问题，从而高效地求解非线性回归模型。

核岭回归（Kernel Ridge Regression, KRR）的数学推导与对偶优化求解过程题目描述核岭回归是岭回归（线性回归的L2正则化版本）在特征空间通过核技巧的扩展，用于解决非线性回归问题。其核心思想是：将原始特征空间的数据通过一个非线性映射Φ映射到高维（甚至无限维）特征空间，然后在特征空间中进行线性岭回归，并利用核函数避免显式计算映射Φ。本题将详细讲解核岭回归的目标函数构建、对偶问题的推导，以及如何通过求解对偶问题得到最终预测模型。整个过程从原始问题到对偶问题的转换是关键。解题过程假设我们有一个数据集 { (x_ i, y_ i) }，i=1,...,n，其中 x_ i ∈ R^d 是输入特征，y_ i ∈ R 是连续目标值。我们的目标是学习一个从输入到输出的非线性映射。原始空间的目标函数首先回顾线性岭回归。在原始特征空间中，岭回归模型为 f(x) = w^T x，其优化目标是最小化平方误差损失加上L2正则项： min_ w Σ_ {i=1}^{n} (y_ i - w^T x_ i)^2 + λ ||w||^2 其中 λ > 0 是正则化系数，控制模型复杂度。引入特征映射与对偶问题对于非线性问题，我们引入一个非线性映射 Φ: R^d → H，将数据映射到高维特征空间 H。在这个空间中的线性模型为 f(x) = w^T Φ(x)。则目标函数变为： min_ w Σ_ {i=1}^{n} (y_ i - w^T Φ(x_ i))^2 + λ ||w||^2 这里 w 是特征空间 H 中的权重向量，可能维度很高甚至无限维，因此直接求解 w 通常不可行。表示定理的应用根据表示定理（Representer Theorem），对于这种带有L2正则化的损失最小化问题，最优解 w* 可以表示为训练样本在特征空间中映射的线性组合： w* = Σ_ {j=1}^{n} α_ j Φ(x_ j) 其中 α = [ α_ 1, ..., α_ n ]^T 是待求的系数向量。这个定理是关键，因为它将优化变量从高维的 w 转换为了 n 维的 α。代入目标函数，转化为关于 α 的问题将 w = Σ_ j α_ j Φ(x_ j) 代入目标函数。首先计算模型预测： f(x_ i) = w^T Φ(x_ i) = [ Σ_ j α_ j Φ(x_ j)]^T Φ(x_ i) = Σ_ j α_ j Φ(x_ j)^T Φ(x_ i) = Σ_ j α_ j K(x_ j, x_ i) 其中 K(x_ j, x_ i) = Φ(x_ j)^T Φ(x_ i) 是核函数，它计算了两个样本在特征空间的内积，无需知道 Φ 的具体形式。常用核函数如高斯核 K(x, z) = exp(-γ ||x - z||^2)。将 f(x_ i) 的表达式代入平方误差项： Σ_ i (y_ i - Σ_ j α_ j K(x_ j, x_ i))^2 定义核矩阵 K ∈ R^{n×n}，其中 K_ {ij} = K(x_ i, x_ j)。定义向量 y = [ y_ 1, ..., y_ n ]^T。则平方误差项可写为： (y - Kα)^T (y - Kα) 接下来计算正则项 ||w||^2： ||w||^2 = w^T w = [ Σ_ i α_ i Φ(x_ i)]^T [ Σ_ j α_ j Φ(x_ j)] = Σ_ i Σ_ j α_ i α_ j Φ(x_ i)^T Φ(x_ j) = Σ_ i Σ_ j α_ i α_ j K(x_ i, x_ j) = α^T K α 因此，目标函数转化为关于 α 的问题： min_ α (y - Kα)^T (y - Kα) + λ α^T K α 求解对偶问题这是一个关于 α 的无约束凸优化问题。我们对 α 求梯度并令其为零。展开目标函数： J(α) = (y - Kα)^T (y - Kα) + λ α^T K α = y^T y - 2 y^T Kα + α^T K^T K α + λ α^T K α 由于 K 对称（核矩阵），K^T = K，所以： J(α) = y^T y - 2 y^T Kα + α^T K^2 α + λ α^T K α = y^T y - 2 y^T Kα + α^T K (K + λI) α 对 α 求梯度： ∇_ α J = -2 K y + 2 K (K + λI) α 令梯度为零： -K y + K (K + λI) α = 0 由于 K 通常是满秩的（如果使用高斯核且数据点不同，K 正定），我们可以两边左乘 K^{-1}，得到： -y + (K + λI) α = 0 因此，最优系数 α* 满足线性系统： (K + λI) α = y 解这个线性系统即可得到 α* = (K + λI)^{-1} y。这里 I 是 n×n 单位矩阵。注意，由于 K 对称半正定，加上 λI 后矩阵正定，可逆。预测新样本对于一个新的输入 x，预测输出为： f(x) = Σ_ {j=1}^{n} α_ j^* K(x_ j, x) 即用学习到的 α* 与所有训练样本的核函数值加权求和。这体现了核方法的“记忆”特性：预测需要用到所有训练数据。算法总结与复杂度核岭回归的训练就是求解线性系统 (K + λI) α = y，时间复杂度为 O(n^3)（由于需要矩阵求逆或求解线性系统），空间复杂度为 O(n^2)（存储核矩阵）。因此，它不适合大规模数据，但非常适合中小规模非线性回归问题。通过上述过程，我们将原始高维特征空间中的岭回归，通过表示定理和核技巧，转化为对偶空间中关于有限维 α 的优化问题，从而高效地求解非线性回归模型。