基于流形正则化的半监督学习：流形假设、图拉普拉斯正则化与优化求解过程
字数 3791 2025-12-22 18:13:45

基于流形正则化的半监督学习：流形假设、图拉普拉斯正则化与优化求解过程

题目描述

在机器学习中，有标签的数据往往稀缺，而无标签数据则相对丰富。半监督学习（Semi-Supervised Learning）旨在同时利用少量有标签数据和大量无标签数据来构建更好的模型。基于流形正则化的半监督学习 是一类重要的方法，其核心思想是假设数据分布在一个低维流形上，并利用这个几何结构来约束学习函数，使得函数在流形上平滑变化。本题目将深入讲解该方法中的“流形假设”、如何通过图拉普拉斯正则化 将流形平滑性融入学习框架，以及最终的优化求解过程。

1. 流形假设（Manifold Assumption）

流形假设认为，高维观测数据实际上位于一个嵌入在高维空间中的低维流形上。例如，一组人脸图片（高维像素空间）可能实际上由少数几个连续变化的因素（如光照、姿态、表情）控制，形成一个低维流形。在半监督学习中，流形假设意味着：

  • 平滑性假设：如果两个样本在流形上是邻近的（即高维空间中的测地距离很近），那么它们的输出标签（或函数值）也应该相似。
  • 聚类假设：数据倾向于形成簇，同一簇内的样本更可能共享相同的标签。

利用无标签数据，我们可以估计这个隐含的流形结构，并将其作为正则化项约束模型，使模型在流形上保持平滑，从而提高泛化能力。

2. 构建近邻图表示流形结构

我们首先用图（Graph）来近似数据所在的流形结构：

  • 顶点：每个数据点（包括有标签和无标签）对应图中的一个节点。
  • 边：如果两个节点 \(x_i\) 和 \(x_j\) 是“近邻”，则在它们之间连一条边。常用的近邻定义包括：
    • \(k\)-最近邻（\(k\)-NN）：每个点与最近的 \(k\) 个点相连。
    • \(\epsilon\)-邻域：距离小于 \(\epsilon\) 的点相连。
  • 边权重：通常用高斯核（热核）定义权重 \(W_{ij}\)：

\[ W_{ij} = \exp\left( -\frac{\|x_i - x_j\|^2}{2\sigma^2} \right) \]

如果 \(x_i\) 和 \(x_j\) 不是近邻，则 \(W_{ij} = 0\)。

这样，我们得到一个无向加权图 \(G = (V, E, W)\)，其中 \(|V| = n = l + u\)（\(l\) 个有标签样本，\(u\) 个无标签样本）。

3. 图拉普拉斯正则化

为了度量函数在流形上的平滑程度，我们引入图拉普拉斯矩阵。定义：

  • 度矩阵 \(D\)：对角矩阵，\(D_{ii} = \sum_{j=1}^n W_{ij}\)。
  • 拉普拉斯矩阵 \(L = D - W\)（未归一化形式）。更常用的是归一化的拉普拉斯矩阵 \(L_{norm} = I - D^{-1/2} W D^{-1/2}\)。

对于一个定义在图上所有节点上的函数 \(f \in \mathbb{R}^n\)（其中 \(f_i\) 是节点 \(i\) 的函数值），其图拉普拉斯正则化项定义为：

\[f^\top L f = \frac{1}{2} \sum_{i,j=1}^n W_{ij} (f_i - f_j)^2 \]

直观解释：如果两个节点很相似（\(W_{ij}\) 大），但它们的函数值 \(f_i\) 和 \(f_j\) 差异很大，则惩罚会很大。因此，最小化 \(f^\top L f\) 会强制 \(f\) 在图上平滑，即在流形上平滑变化。

4. 流形正则化学习框架

我们将有标签数据的损失与流形正则化项结合，得到总体目标函数。假设我们有 \(l\) 个有标签样本 \(\{(x_i, y_i)\}_{i=1}^l\)，\(u\) 个无标签样本 \(\{x_j\}_{j=l+1}^{l+u}\)，总样本数 \(n = l+u\)。

目标：学习一个预测函数 \(f: \mathcal{X} \to \mathbb{R}\)。在再生核希尔伯特空间（RKHS）\(\mathcal{H}_K\) 中寻找 \(f\)，优化问题为：

\[\min_{f \in \mathcal{H}_K} \frac{1}{l} \sum_{i=1}^l V(y_i, f(x_i)) + \gamma_A \|f\|_K^2 + \gamma_I \cdot \frac{1}{n^2} f^\top L f \]

其中：

  • 第一项是有标签数据的经验损失，例如平方损失 \((y_i - f(x_i))^2\) 或 hinge 损失。
  • 第二项 \(\|f\|_K^2\) 是RKHS范数正则化（控制模型复杂度），\(\gamma_A > 0\) 是其权重。
  • 第三项是流形正则化项，\(\gamma_I > 0\) 控制其对流形平滑性的强调程度。因子 \(1/n^2\) 用于缩放（有时也用 \(1/(l+u)^2\)）。

5. 基于表示定理的闭式解

根据表示定理，该优化问题的最优解 \(f^*\) 具有形式：

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

其中 \(K(\cdot, \cdot)\) 是核函数，\(\alpha = (\alpha_1, \dots, \alpha_n)^\top\) 是待求系数。

将 \(f = [f(x_1), \dots, f(x_n)]^\top = K \alpha\) 代入目标函数，其中 \(K \in \mathbb{R}^{n \times n}\) 是核矩阵，\(K_{ij} = K(x_i, x_j)\)。则：

  • RKHS 正则项：\(\|f\|_K^2 = \alpha^\top K \alpha\)。
  • 流形正则项：\(f^\top L f = \alpha^\top K L K \alpha\)。
  • 有标签损失：假设用平方损失，则 \(\sum_{i=1}^l (y_i - f(x_i))^2 = \|J(Y - K\alpha)\|^2\)，其中 \(Y = (y_1, \dots, y_l, 0, \dots, 0)^\top\)（无标签部分设为0），\(J\) 是一个 \(n \times n\) 对角矩阵，前 \(l\) 个对角元为1，其余为0。

于是优化问题转化为关于 \(\alpha\) 的凸二次规划：

\[\min_{\alpha \in \mathbb{R}^n} \frac{1}{l} (Y - K\alpha)^\top J (Y - K\alpha) + \gamma_A \alpha^\top K \alpha + \gamma_I \alpha^\top K L K \alpha \]

6. 求解系数 α

对 \(\alpha\) 求导并令导数为零：

\[-\frac{2}{l} K J (Y - K\alpha) + 2\gamma_A K \alpha + 2\gamma_I K L K \alpha = 0 \]

假设 \(K\) 可逆（通常用正定核，如高斯核），两边左乘 \(K^{-1}\)，整理得：

\[\left( J K + l\gamma_A I + l\gamma_I L K \right) \alpha = J Y \]

这是一个线性方程组，可用数值方法（如共轭梯度法）求解 \(\alpha\)。解出 \(\alpha\) 后，对新样本 \(x\) 的预测为：

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

7. 算法总结与讨论

步骤总结：

  1. 用所有数据（有标签+无标签）构建近邻图，计算权重矩阵 \(W\) 和拉普拉斯矩阵 \(L\)。
  2. 选择核函数（如线性核、高斯核），计算核矩阵 \(K\)。
  3. 设置正则化参数 \(\gamma_A, \gamma_I\) 和损失函数。
  4. 求解线性方程组得到系数 \(\alpha\)。
  5. 用学得的函数 \(f\) 进行预测。

优势：

  • 利用无标签数据揭示流形结构，提升模型在低密度区域（决策边界附近）的泛化能力。
  • 可扩展至各种损失函数和核函数，灵活性强。

局限：

  • 图构造对参数（如近邻数 \(k\)、核宽 \(\sigma\)）敏感，影响最终性能。
  • 求解涉及 \(n \times n\) 矩阵，当 \(n\) 很大时计算成本高，可借助稀疏图或迭代求解。

通过以上步骤，我们完成了从流形假设出发，利用图拉普拉斯正则化约束函数平滑性，最终求解半监督学习模型的完整过程。这种方法在文本分类、图像识别等领域被广泛应用，成为经典半监督学习框架之一。

基于流形正则化的半监督学习：流形假设、图拉普拉斯正则化与优化求解过程 题目描述 在机器学习中，有标签的数据往往稀缺，而无标签数据则相对丰富。半监督学习（Semi-Supervised Learning）旨在同时利用少量有标签数据和大量无标签数据来构建更好的模型。 基于流形正则化的半监督学习 是一类重要的方法，其核心思想是假设数据分布在一个低维流形上，并利用这个几何结构来约束学习函数，使得函数在流形上平滑变化。本题目将深入讲解该方法中的“流形假设”、如何通过 图拉普拉斯正则化 将流形平滑性融入学习框架，以及最终的优化求解过程。 1. 流形假设（Manifold Assumption） 流形假设认为，高维观测数据实际上位于一个嵌入在高维空间中的低维流形上。例如，一组人脸图片（高维像素空间）可能实际上由少数几个连续变化的因素（如光照、姿态、表情）控制，形成一个低维流形。在半监督学习中，流形假设意味着： 平滑性假设 ：如果两个样本在流形上是邻近的（即高维空间中的测地距离很近），那么它们的输出标签（或函数值）也应该相似。 聚类假设 ：数据倾向于形成簇，同一簇内的样本更可能共享相同的标签。 利用无标签数据，我们可以估计这个隐含的流形结构，并将其作为正则化项约束模型，使模型在流形上保持平滑，从而提高泛化能力。 2. 构建近邻图表示流形结构 我们首先用图（Graph）来近似数据所在的流形结构： 顶点 ：每个数据点（包括有标签和无标签）对应图中的一个节点。 边 ：如果两个节点 \( x_ i \) 和 \( x_ j \) 是“近邻”，则在它们之间连一条边。常用的近邻定义包括： \( k \)-最近邻（\( k \)-NN）：每个点与最近的 \( k \) 个点相连。 \( \epsilon \)-邻域：距离小于 \( \epsilon \) 的点相连。 边权重 ：通常用高斯核（热核）定义权重 \( W_ {ij} \)： \[ W_ {ij} = \exp\left( -\frac{\|x_ i - x_ j\|^2}{2\sigma^2} \right) \] 如果 \( x_ i \) 和 \( x_ j \) 不是近邻，则 \( W_ {ij} = 0 \)。 这样，我们得到一个无向加权图 \( G = (V, E, W) \)，其中 \( |V| = n = l + u \)（\( l \) 个有标签样本，\( u \) 个无标签样本）。 3. 图拉普拉斯正则化 为了度量函数在流形上的平滑程度，我们引入 图拉普拉斯矩阵 。定义： 度矩阵 \( D \)：对角矩阵，\( D_ {ii} = \sum_ {j=1}^n W_ {ij} \)。 拉普拉斯矩阵 \( L = D - W \)（未归一化形式）。更常用的是归一化的拉普拉斯矩阵 \( L_ {norm} = I - D^{-1/2} W D^{-1/2} \)。 对于一个定义在图上所有节点上的函数 \( f \in \mathbb{R}^n \)（其中 \( f_ i \) 是节点 \( i \) 的函数值），其 图拉普拉斯正则化项 定义为： \[ f^\top L f = \frac{1}{2} \sum_ {i,j=1}^n W_ {ij} (f_ i - f_ j)^2 \] 直观解释 ：如果两个节点很相似（\( W_ {ij} \) 大），但它们的函数值 \( f_ i \) 和 \( f_ j \) 差异很大，则惩罚会很大。因此，最小化 \( f^\top L f \) 会强制 \( f \) 在图上平滑，即在流形上平滑变化。 4. 流形正则化学习框架 我们将有标签数据的损失与流形正则化项结合，得到总体目标函数。假设我们有 \( l \) 个有标签样本 \( \{(x_ i, y_ i)\} {i=1}^l \)，\( u \) 个无标签样本 \( \{x_ j\} {j=l+1}^{l+u} \)，总样本数 \( n = l+u \)。 目标：学习一个预测函数 \( f: \mathcal{X} \to \mathbb{R} \)。在再生核希尔伯特空间（RKHS）\( \mathcal{H} K \) 中寻找 \( f \)，优化问题为： \[ \min {f \in \mathcal{H} K} \frac{1}{l} \sum {i=1}^l V(y_ i, f(x_ i)) + \gamma_ A \|f\|_ K^2 + \gamma_ I \cdot \frac{1}{n^2} f^\top L f \] 其中： 第一项是 有标签数据的经验损失 ，例如平方损失 \( (y_ i - f(x_ i))^2 \) 或 hinge 损失。 第二项 \( \|f\|_ K^2 \) 是 RKHS范数正则化 （控制模型复杂度），\( \gamma_ A > 0 \) 是其权重。 第三项是 流形正则化项 ，\( \gamma_ I > 0 \) 控制其对流形平滑性的强调程度。因子 \( 1/n^2 \) 用于缩放（有时也用 \( 1/(l+u)^2 \)）。 5. 基于表示定理的闭式解 根据表示定理，该优化问题的最优解 \( f^* \) 具有形式： \[ f^* (x) = \sum_ {i=1}^n \alpha_ i K(x, x_ i) \] 其中 \( K(\cdot, \cdot) \) 是核函数，\( \alpha = (\alpha_ 1, \dots, \alpha_ n)^\top \) 是待求系数。 将 \( f = [ f(x_ 1), \dots, f(x_ n)]^\top = K \alpha \) 代入目标函数，其中 \( K \in \mathbb{R}^{n \times n} \) 是核矩阵，\( K_ {ij} = K(x_ i, x_ j) \)。则： RKHS 正则项：\( \|f\|_ K^2 = \alpha^\top K \alpha \)。 流形正则项：\( f^\top L f = \alpha^\top K L K \alpha \)。 有标签损失：假设用平方损失，则 \( \sum_ {i=1}^l (y_ i - f(x_ i))^2 = \|J(Y - K\alpha)\|^2 \)，其中 \( Y = (y_ 1, \dots, y_ l, 0, \dots, 0)^\top \)（无标签部分设为0），\( J \) 是一个 \( n \times n \) 对角矩阵，前 \( l \) 个对角元为1，其余为0。 于是优化问题转化为关于 \( \alpha \) 的凸二次规划： \[ \min_ {\alpha \in \mathbb{R}^n} \frac{1}{l} (Y - K\alpha)^\top J (Y - K\alpha) + \gamma_ A \alpha^\top K \alpha + \gamma_ I \alpha^\top K L K \alpha \] 6. 求解系数 α 对 \( \alpha \) 求导并令导数为零： \[ -\frac{2}{l} K J (Y - K\alpha) + 2\gamma_ A K \alpha + 2\gamma_ I K L K \alpha = 0 \] 假设 \( K \) 可逆（通常用正定核，如高斯核），两边左乘 \( K^{-1} \)，整理得： \[ \left( J K + l\gamma_ A I + l\gamma_ I L K \right) \alpha = J Y \] 这是一个线性方程组，可用数值方法（如共轭梯度法）求解 \( \alpha \)。解出 \( \alpha \) 后，对新样本 \( x \) 的预测为： \[ f(x) = \sum_ {i=1}^n \alpha_ i K(x, x_ i) \] 7. 算法总结与讨论 步骤总结 ： 用所有数据（有标签+无标签）构建近邻图，计算权重矩阵 \( W \) 和拉普拉斯矩阵 \( L \)。 选择核函数（如线性核、高斯核），计算核矩阵 \( K \)。 设置正则化参数 \( \gamma_ A, \gamma_ I \) 和损失函数。 求解线性方程组得到系数 \( \alpha \)。 用学得的函数 \( f \) 进行预测。 优势 ： 利用无标签数据揭示流形结构，提升模型在低密度区域（决策边界附近）的泛化能力。 可扩展至各种损失函数和核函数，灵活性强。 局限 ： 图构造对参数（如近邻数 \( k \)、核宽 \( \sigma \)）敏感，影响最终性能。 求解涉及 \( n \times n \) 矩阵，当 \( n \) 很大时计算成本高，可借助稀疏图或迭代求解。 通过以上步骤，我们完成了从 流形假设 出发，利用 图拉普拉斯正则化 约束函数平滑性，最终求解半监督学习模型的完整过程。这种方法在文本分类、图像识别等领域被广泛应用，成为经典半监督学习框架之一。