基于流形正则化的最小二乘回归（Manifold Regularized Least Squares Regression, LapRLS）的推导与优化过程
题目描述
在传统的监督学习中，我们通常假设训练数据是从某个独立同分布中采样得到的。但在许多实际问题（如图像分类、文本分类、半监督学习等）中，未标记的数据往往更容易获取，且数据通常存在于一个低维流形结构中。基于流形正则化的最小二乘回归（LapRLS） 是一种将流形假设引入正则化框架的半监督/监督学习算法。其核心思想是：除了最小化预测误差和模型复杂度（如岭回归中的L2正则化）外，还通过流形正则化项来约束学习到的函数在数据流形上平滑变化，即相似的数据点应有相似的预测值。本题目将详细讲解LapRLS的模型构建、目标函数推导、优化求解以及算法实现步骤。
解题过程
步骤1：问题形式化与符号定义
假设我们有一个包含标记数据和未标记数据的训练集：
- 标记数据：\(\{ (x_i, y_i) \}_{i=1}^l\)，其中 \(x_i \in \mathbb{R}^d\)，\(y_i \in \mathbb{R}\)（回归问题）或 \(y_i \in \{-1, 1\}\)（分类问题，可视为回归的离散形式）。
- 未标记数据：\(\{ x_i \}_{i=l+1}^{l+u}\)，总数据点数为 \(n = l + u\)。
目标：学习一个函数 \(f: \mathbb{R}^d \to \mathbb{R}\)，使得 \(f\) 在标记数据上预测误差小，同时在整个数据流形上平滑变化。
步骤2：构建目标函数
LapRLS的目标函数由三部分组成：
- 经验损失项：衡量标记数据上的预测误差，通常采用平方损失：
\[ \frac{1}{l} \sum_{i=1}^l (y_i - f(x_i))^2 \]
- 模型复杂度正则项：防止过拟合，采用L2范数正则化（岭回归）：
\[ \lambda \|f\|_K^2 \]
其中 \(\|\cdot\|_K\) 是再生核希尔伯特空间（RKHS）中的范数，\(\lambda > 0\) 是正则化参数。
- 流形正则化项：强制函数 \(f\) 在数据流形上平滑。定义数据点的相似性图（如k近邻图），其边权重 \(W_{ij}\) 通常用高斯核计算：
\[ W_{ij} = \exp\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right) \]
图拉普拉斯矩阵为 \(L = D - W\)，其中 \(D\) 是对角度矩阵，\(D_{ii} = \sum_{j=1}^n W_{ij}\)。流形正则化项定义为：
\[ \frac{\gamma}{n^2} \sum_{i,j=1}^n W_{ij} (f(x_i) - f(x_j))^2 = \frac{\gamma}{n^2} f^\top L f \]
其中 \(f = [f(x_1), f(x_2), \dots, f(x_n)]^\top\)，\(\gamma > 0\) 是流形正则化系数。该项惩罚图中相连节点（相似点）的预测值差异，促使 \(f\) 在流形上平滑。
综合以上三项，得到LapRLS的目标函数：
\[J(f) = \frac{1}{l} \sum_{i=1}^l (y_i - f(x_i))^2 + \lambda \|f\|_K^2 + \frac{\gamma}{n^2} f^\top L f \]
步骤3：基于核函数的表示定理
根据表示定理，目标函数的最优解可表示为核函数的线性组合：
\[f(x) = \sum_{i=1}^n \alpha_i k(x, x_i) \]
其中 \(k(\cdot, \cdot)\) 是正定核函数（如RBF核），\(\alpha = [\alpha_1, \dots, \alpha_n]^\top\) 是待求系数向量。定义核矩阵 \(K \in \mathbb{R}^{n \times n}\)，其中 \(K_{ij} = k(x_i, x_j)\)。则所有数据点的预测向量为：
\[f = K\alpha \]
步骤4：目标函数的矩阵形式
将 \(f = K\alpha\) 代入目标函数 \(J(f)\)：
- 经验损失项：令 \(Y = [y_1, \dots, y_l, 0, \dots, 0]^\top \in \mathbb{R}^n\)（未标记数据对应标签为0），定义选择矩阵 \(J = \text{diag}(1, \dots, 1, 0, \dots, 0)\)，前 \(l\) 个对角线元素为1，其余为0。则经验损失项可写为：
\[ \frac{1}{l} (Y - JK\alpha)^\top (Y - JK\alpha) \]
- 模型复杂度项：在RKHS中，有 \(\|f\|_K^2 = \alpha^\top K\alpha\)。
- 流形正则化项：\(f^\top L f = \alpha^\top K L K \alpha\)。
因此，目标函数化为关于 \(\alpha\) 的凸二次函数：
\[J(\alpha) = \frac{1}{l} (Y - JK\alpha)^\top (Y - JK\alpha) + \lambda \alpha^\top K\alpha + \frac{\gamma}{n^2} \alpha^\top K L K \alpha \]
步骤5：优化求解
对 \(J(\alpha)\) 关于 \(\alpha\) 求导并令导数为零：
\[\frac{\partial J}{\partial \alpha} = -\frac{2}{l} K J^\top (Y - JK\alpha) + 2\lambda K\alpha + \frac{2\gamma}{n^2} K L K \alpha = 0 \]
两边左乘 \(K^{-1}\)（假设 \(K\) 可逆，实际中常为正定）并整理：
\[\left( JK + \lambda l I + \frac{\gamma l}{n^2} L K \right) \alpha = J^\top Y \]
这里 \(I\) 是单位矩阵。求解该线性方程组即可得到 \(\alpha\)：
\[\alpha = \left( JK + \lambda l I + \frac{\gamma l}{n^2} L K \right)^{-1} J^\top Y \]
步骤6：预测与新样本处理
对于新样本 \(x_{\text{new}}\)，预测值为：
\[f(x_{\text{new}}) = \sum_{i=1}^n \alpha_i k(x_{\text{new}}, x_i) = k_{\text{new}}^\top \alpha \]
其中 \(k_{\text{new}} = [k(x_{\text{new}}, x_1), \dots, k(x_{\text{new}}, x_n)]^\top\)。
步骤7：算法总结与实现要点
- 输入：标记数据 \((X_l, Y_l)\)，未标记数据 \(X_u\)，超参数 \(\lambda, \gamma, \sigma\)（核带宽）。
- 构建相似图：计算全数据集 \(X = [X_l; X_u]\) 的k近邻图及权重矩阵 \(W\)，进而得到拉普拉斯矩阵 \(L = D - W\)。
- 计算核矩阵：例如用RBF核 \(k(x_i, x_j) = \exp(-\|x_i - x_j\|^2 / (2\sigma^2))\) 计算 \(K\)。
- 构造选择矩阵：\(J = \text{diag}(1_{l}, 0_{u})\)。
- 求解系数：解线性方程组得 \(\alpha\)。
- 预测：对新样本计算核向量并输出 \(f(x_{\text{new}}) = k_{\text{new}}^\top \alpha\)。
关键点：流形正则化项 \(\gamma\) 控制函数在流形上的平滑程度；当 \(\gamma = 0\) 时，LapRLS退化为标准核岭回归。该算法巧妙地将几何结构信息融入正则化框架，提升了在半监督场景下的泛化能力。