基于流形正则化的半监督学习：流形假设、图拉普拉斯正则化与优化求解过程
字数 4560 2025-12-20 11:00:25

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

我将为你讲解“基于流形正则化的半监督学习”这个算法题目。这是一种经典的学习范式，旨在利用大量无标签数据来提升模型在少量有标签数据上的泛化能力。

1. 问题背景与核心思想

  • 场景设定：在现实问题中，获取大量“有标签”数据（如已标注的图片、文本）通常成本高昂，而获取“无标签”数据则相对容易。我们希望利用这大量无标签数据和少量有标签数据，共同训练一个更好的模型。这就是半监督学习。
  • 流形假设：这是流形正则化方法的基石。假设高维空间中的数据点（例如图片像素构成的向量）实际上分布在一个低维流形上。流形可以理解为嵌入在高维空间中的低维曲面或结构。例如，不同光照、角度下的人脸图片虽然像素维度很高，但本质上由少数几个因素（姿态、光照）控制，形成低维结构。
  • 平滑性假设：在流形上，距离相近的数据点（相似样本）应该具有相似的性质（例如类别标签或函数值）。换句话说，我们希望学习到的模型在流形上是平滑变化的。

2. 问题的数学建模

目标是学习一个预测函数 \(f: \mathbb{R}^d \rightarrow \mathbb{R}\)。假设我们有：

  • 有标签数据： \(L = \{ (\mathbf{x}_i, y_i) \}_{i=1}^l\)， 共 \(l\) 个样本。
  • 无标签数据： \(U = \{ \mathbf{x}_i \}_{i=l+1}^{l+u}\)， 共 \(u\) 个样本。总样本数 \(n = l + u\)。

目标函数（正则化框架）通常构建如下：

\[\min_{f \in \mathcal{H}_K} \frac{1}{l} \sum_{i=1}^{l} V(y_i, f(\mathbf{x}_i)) + \gamma_A ||f||_K^2 + \gamma_I ||f||_I^2 \]

让我详细分解这三项：

  1. 经验损失项：\(\frac{1}{l} \sum_{i=1}^{l} V(y_i, f(\mathbf{x}_i))\)

    • 这是模型在有标签数据上的表现。\(V(\cdot)\) 是损失函数，例如均方误差（回归）或合页损失/交叉熵（分类）。它确保模型能正确拟合已知的标签。

  2. 模型复杂度正则项：\(\gamma_A ||f||_K^2\)

    • 这是经典的正则化项，防止模型在给定的假设空间 \(\mathcal{H}_K\) 中“过拟合”。
    • \(||f||_K\) 是函数 \(f\) 在再生核希尔伯特空间 中的范数，它衡量了函数的复杂性。\(\gamma_A > 0\) 是控制其权重的参数。
    • 作用：即使没有无标签数据，这一项也能保证模型的泛化性。

  3. 流形正则项：\(\gamma_I ||f||_I^2\)

    • 这是流形正则化的核心创新点，它引入了无标签数据的影响。
    • \(||f||_I\) 是函数 \(f\) 在数据分布的几何结构（即流形）上的光滑性度量。\(\gamma_I > 0\) 是其权重参数。
    • 直观解释：如果 \(f\) 在流形上变化剧烈，即相邻样本的预测值差异很大，那么这个值就大，会被惩罚。因此，最小化这一项强制 \(f\) 在流形结构上保持平滑，从而将标签信息从有标签样本“传播”到邻近的无标签样本。

3. 关键步骤：如何计算流形正则项 \(||f||_I^2\)

这是整个算法的核心。由于我们不知道真实的流形，需要用图来近似它。

步骤一：构建近邻图
将所有有标签和无标签样本看作图的节点。常用的建图方法有：

  • \(\epsilon\)-邻近图：两点距离小于 \(\epsilon\) 则连边。
  • k-最近邻图：每个点只与其k个最近邻相连。
  • 全连接图：所有点之间都连边，用权重表示亲疏。

步骤二：定义边的权重（相似度）
如果节点 \(i\) 和 \(j\) 之间有边，通常用高斯（热）核定义权重 \(W_{ij}\)：

\[W_{ij} = \exp\left( -\frac{||\mathbf{x}_i - \mathbf{x}_j||^2}{2\sigma^2} \right) \]

如果无边，则 \(W_{ij} = 0\)。权重 \(W_{ij}\) 越大，表示两个点在原始空间（以及推测的流形上）越接近、越相似。

步骤三：构建图拉普拉斯矩阵（Graph Laplacian）
图的拉普拉斯矩阵 \(L\) 是刻画图结构的关键工具。常用的有两种：

  1. 非规范化图拉普拉斯： \(L = D - W\)
  2. 规范化图拉普拉斯： \(L = I - D^{-1/2} W D^{-1/2}\) 或 \(L = D^{-1/2} L D^{-1/2}\)
    其中，\(D\) 是度矩阵，一个对角矩阵，其对角线元素 \(D_{ii} = \sum_{j=1}^{n} W_{ij}\)，表示第 \(i\) 个节点的“连接强度”。

步骤四：定义流形正则项 \(||f||_I^2\)
将函数 \(f\) 在所有样本点上的取值写成一个向量：\(\mathbf{f} = [f(\mathbf{x}_1), f(\mathbf{x}_2), ..., f(\mathbf{x}_n)]^T\)。
流形正则项定义为：

\[||f||_I^2 = \mathbf{f}^T L \mathbf{f} = \frac{1}{2} \sum_{i,j=1}^{n} W_{ij} (f(\mathbf{x}_i) - f(\mathbf{x}_j))^2 \]

  • 矩阵形式：\(||f||_I^2 = \mathbf{f}^T L \mathbf{f}\)。这可以看作是函数在图上的一种能量。
  • 和形式推导：由 \(L = D-W\)，有 \(\mathbf{f}^T L \mathbf{f} = \mathbf{f}^T D \mathbf{f} - \mathbf{f}^T W \mathbf{f} = \sum_i D_{ii} f_i^2 - \sum_{i,j} W_{ij} f_i f_j = \frac{1}{2} \sum_{i,j} W_{ij}(f_i^2 + f_j^2 - 2f_i f_j) = \frac{1}{2} \sum_{i,j} W_{ij}(f_i - f_j)^2\)。
  • 直观解释：这个和式遍历所有节点对。如果两个节点相似度高（\(W_{ij}\) 大），而它们的预测值 \(f_i\) 和 \(f_j\) 差异大，那么惩罚 \((f_i - f_j)^2\) 的权重就大。最小化这一项，会迫使相似样本的预测值变得相近，这完美地体现了“平滑性假设”。

4. 优化求解过程

将流形正则项代入总目标函数。以最常见的最小二乘损失为例，目标函数变为：

\[\min_{\mathbf{f} \in \mathbb{R}^n} \frac{1}{l} \sum_{i=1}^{l} (y_i - f_i)^2 + \gamma_A \mathbf{f}^T K^{-1} \mathbf{f} + \gamma_I \mathbf{f}^T L \mathbf{f} \]

这里为了简化，假设函数空间是有限维的，并用核矩阵 \(K\) 来实现 \(||f||_K^2 = \boldsymbol{\alpha}^T K \boldsymbol{\alpha} = \mathbf{f}^T K^{-1} \mathbf{f}\)，其中 \(\mathbf{f} = K \boldsymbol{\alpha}\)。

由于目标函数是关于 \(\mathbf{f}\) 的二次函数，我们可以直接求导得到闭合解。对 \(\mathbf{f}\) 求导并令导数为零：

\[\frac{\partial}{\partial \mathbf{f}} \left[ \frac{1}{l} (\mathbf{y}_l - J\mathbf{f})^T (\mathbf{y}_l - J\mathbf{f}) + \gamma_A \mathbf{f}^T K^{-1} \mathbf{f} + \gamma_I \mathbf{f}^T L \mathbf{f} \right] = 0 \]

其中，\(J\) 是一个 \(n \times n\) 的对角选择矩阵，其前 \(l\) 个对角线元素为1（对应有标签点），其余为0。\(\mathbf{y}_l\) 是扩展的标签向量，其前 \(l\) 个元素为 \(y_i\)，其余为0。

推导后得到线性系统：

\[( J^T J + l\gamma_A K^{-1} + l\gamma_I L ) \mathbf{f} = J^T \mathbf{y} \]

更具体地，因为 \(J^T J\) 是一个对角矩阵，其前 \(l\) 个对角元为1，其余为0。因此，这个方程可以写成：

\[\mathbf{f} = ( J + l\gamma_A K^{-1} + l\gamma_I L )^{-1} \mathbf{y} \]

其中 \(J\) 是上述对角矩阵。这个方程可以通过求解线性系统来得到所有点（包括无标签点）的预测值 \(\mathbf{f}\)。

5. 算法总结与意义

  1. 输入：有标签集 \(L\)， 无标签集 \(U\)， 正则化参数 \(\gamma_A, \gamma_I\)， 图参数（k, \(\sigma\)）。
  2. 建图：将所有样本点构建成一个近邻图，计算权重矩阵 \(W\) 和度矩阵 \(D\)。
  3. 构造正则化矩阵：计算图拉普拉斯矩阵 \(L = D - W\)。
  4. 构造核矩阵：根据选定的核函数（如高斯核），计算所有样本对（有标签+无标签）的核矩阵 \(K\)。
  5. 构造标签向量：构建长度为 \(n\) 的初始标签向量，有标签位置为 \(y_i\)， 无标签位置为0。构造选择矩阵 \(J\)。
  6. 求解：求解线性系统 \((J + l\gamma_A K^{-1} + l\gamma_I L) \mathbf{f} = \mathbf{y}\)， 得到对所有 \(n\) 个点的预测向量 \(\mathbf{f}\)。
  7. 输出：对于新样本 \(\mathbf{x}\)， 其预测值可通过已学得的表示（或通过核技巧）计算得到。

核心意义：该方法巧妙地将无标签数据蕴含的几何结构信息（通过图拉普拉斯矩阵 \(L\) 编码）作为一种正则化约束，引入到标准的有监督学习框架中。模型在拟合有标签数据的同时，被强制要求在推测的数据流形上保持平滑，从而利用无标签数据极大地提升了泛化性能，成为半监督学习领域一个里程碑式的方法。

基于流形正则化的半监督学习：流形假设、图拉普拉斯正则化与优化求解过程 我将为你讲解“基于流形正则化的半监督学习”这个算法题目。这是一种经典的学习范式，旨在利用大量无标签数据来提升模型在少量有标签数据上的泛化能力。 1. 问题背景与核心思想 场景设定 ：在现实问题中，获取大量“有标签”数据（如已标注的图片、文本）通常成本高昂，而获取“无标签”数据则相对容易。我们希望利用这 大量无标签 数据和 少量有标签 数据，共同训练一个更好的模型。这就是 半监督学习 。 流形假设 ：这是流形正则化方法的基石。假设高维空间中的数据点（例如图片像素构成的向量）实际上分布在一个 低维流形 上。流形可以理解为嵌入在高维空间中的低维曲面或结构。例如，不同光照、角度下的人脸图片虽然像素维度很高，但本质上由少数几个因素（姿态、光照）控制，形成低维结构。 平滑性假设 ：在流形上， 距离相近 的数据点（相似样本）应该具有 相似的性质 （例如类别标签或函数值）。换句话说，我们希望学习到的模型在流形上是平滑变化的。 2. 问题的数学建模 目标是学习一个预测函数 \( f: \mathbb{R}^d \rightarrow \mathbb{R} \)。假设我们有： 有标签数据： \( L = \{ (\mathbf{x} i, y_ i) \} {i=1}^l \)， 共 \(l\) 个样本。 无标签数据： \( U = \{ \mathbf{x} i \} {i=l+1}^{l+u} \)， 共 \(u\) 个样本。总样本数 \(n = l + u\)。 目标函数 （正则化框架）通常构建如下： \[ \min_ {f \in \mathcal{H} K} \frac{1}{l} \sum {i=1}^{l} V(y_ i, f(\mathbf{x}_ i)) + \gamma_ A ||f||_ K^2 + \gamma_ I ||f||_ I^2 \] 让我详细分解这三项： 经验损失项 ：\(\frac{1}{l} \sum_ {i=1}^{l} V(y_ i, f(\mathbf{x}_ i))\) 这是模型在有标签数据上的表现。\(V(\cdot)\) 是损失函数，例如均方误差（回归）或合页损失/交叉熵（分类）。它确保模型能正确拟合已知的标签。 模型复杂度正则项 ：\(\gamma_ A ||f||_ K^2\) 这是经典的正则化项，防止模型在给定的 假设空间 \(\mathcal{H}_ K\) 中“过拟合”。 \(||f||_ K\) 是函数 \(f\) 在 再生核希尔伯特空间 中的范数，它衡量了函数的复杂性。\(\gamma_ A > 0\) 是控制其权重的参数。 作用 ：即使没有无标签数据，这一项也能保证模型的泛化性。 流形正则项 ：\(\gamma_ I ||f||_ I^2\) 这是 流形正则化 的核心创新点，它引入了 无标签数据 的影响。 \(||f||_ I\) 是函数 \(f\) 在 数据分布的几何结构 （即流形）上的光滑性度量。\(\gamma_ I > 0\) 是其权重参数。 直观解释 ：如果 \(f\) 在流形上变化剧烈，即相邻样本的预测值差异很大，那么这个值就大，会被惩罚。因此，最小化这一项 强制 \(f\) 在流形结构上保持平滑，从而将标签信息从有标签样本“传播”到邻近的无标签样本。 3. 关键步骤：如何计算流形正则项 \(||f||_ I^2\) 这是整个算法的核心。由于我们不知道真实的流形，需要用 图 来近似它。 步骤一：构建近邻图 将所有有标签和无标签样本看作图的节点。常用的建图方法有： \(\epsilon\)-邻近图 ：两点距离小于 \(\epsilon\) 则连边。 k-最近邻图 ：每个点只与其k个最近邻相连。 全连接图 ：所有点之间都连边，用权重表示亲疏。 步骤二：定义边的权重（相似度） 如果节点 \(i\) 和 \(j\) 之间有边，通常用 高斯（热）核 定义权重 \(W_ {ij}\)： \[ W_ {ij} = \exp\left( -\frac{||\mathbf{x} i - \mathbf{x} j||^2}{2\sigma^2} \right) \] 如果无边，则 \(W {ij} = 0\)。权重 \(W {ij}\) 越大，表示两个点在原始空间（以及推测的流形上）越接近、越相似。 步骤三：构建图拉普拉斯矩阵（Graph Laplacian） 图的拉普拉斯矩阵 \(L\) 是刻画图结构的关键工具。常用的有两种： 非规范化图拉普拉斯 ： \(L = D - W\) 规范化图拉普拉斯 ： \(L = I - D^{-1/2} W D^{-1/2}\) 或 \(L = D^{-1/2} L D^{-1/2}\) 其中，\(D\) 是 度矩阵 ，一个对角矩阵，其对角线元素 \(D_ {ii} = \sum_ {j=1}^{n} W_ {ij}\)，表示第 \(i\) 个节点的“连接强度”。 步骤四：定义流形正则项 \(||f||_ I^2\) 将函数 \(f\) 在所有样本点上的取值写成一个向量：\(\mathbf{f} = [ f(\mathbf{x}_ 1), f(\mathbf{x}_ 2), ..., f(\mathbf{x} n) ]^T\)。 流形正则项定义为： \[ ||f|| I^2 = \mathbf{f}^T L \mathbf{f} = \frac{1}{2} \sum {i,j=1}^{n} W {ij} (f(\mathbf{x}_ i) - f(\mathbf{x}_ j))^2 \] 矩阵形式 ：\(||f||_ I^2 = \mathbf{f}^T L \mathbf{f}\)。这可以看作是函数在图上的一种能量。 和形式推导 ：由 \(L = D-W\)，有 \(\mathbf{f}^T L \mathbf{f} = \mathbf{f}^T D \mathbf{f} - \mathbf{f}^T W \mathbf{f} = \sum_ i D_ {ii} f_ i^2 - \sum_ {i,j} W_ {ij} f_ i f_ j = \frac{1}{2} \sum_ {i,j} W_ {ij}(f_ i^2 + f_ j^2 - 2f_ i f_ j) = \frac{1}{2} \sum_ {i,j} W_ {ij}(f_ i - f_ j)^2\)。 直观解释 ：这个和式遍历所有节点对。如果两个节点相似度高（\(W_ {ij}\) 大），而它们的预测值 \(f_ i\) 和 \(f_ j\) 差异大，那么惩罚 \((f_ i - f_ j)^2\) 的权重就大。 最小化这一项，会迫使相似样本的预测值变得相近 ，这完美地体现了“平滑性假设”。 4. 优化求解过程 将流形正则项代入总目标函数。以最常见的 最小二乘损失 为例，目标函数变为： \[ \min_ {\mathbf{f} \in \mathbb{R}^n} \frac{1}{l} \sum_ {i=1}^{l} (y_ i - f_ i)^2 + \gamma_ A \mathbf{f}^T K^{-1} \mathbf{f} + \gamma_ I \mathbf{f}^T L \mathbf{f} \] 这里为了简化，假设函数空间是有限维的，并用核矩阵 \(K\) 来实现 \(||f||_ K^2 = \boldsymbol{\alpha}^T K \boldsymbol{\alpha} = \mathbf{f}^T K^{-1} \mathbf{f}\)，其中 \(\mathbf{f} = K \boldsymbol{\alpha}\)。 由于目标函数是关于 \(\mathbf{f}\) 的二次函数，我们可以直接求导得到 闭合解 。对 \(\mathbf{f}\) 求导并令导数为零： \[ \frac{\partial}{\partial \mathbf{f}} \left[ \frac{1}{l} (\mathbf{y}_ l - J\mathbf{f})^T (\mathbf{y}_ l - J\mathbf{f}) + \gamma_ A \mathbf{f}^T K^{-1} \mathbf{f} + \gamma_ I \mathbf{f}^T L \mathbf{f} \right ] = 0 \] 其中，\(J\) 是一个 \(n \times n\) 的对角选择矩阵，其前 \(l\) 个对角线元素为1（对应有标签点），其余为0。\(\mathbf{y}_ l\) 是扩展的标签向量，其前 \(l\) 个元素为 \(y_ i\)，其余为0。 推导后得到线性系统： \[ ( J^T J + l\gamma_ A K^{-1} + l\gamma_ I L ) \mathbf{f} = J^T \mathbf{y} \] 更具体地，因为 \(J^T J\) 是一个对角矩阵，其前 \(l\) 个对角元为1，其余为0。因此，这个方程可以写成： \[ \mathbf{f} = ( J + l\gamma_ A K^{-1} + l\gamma_ I L )^{-1} \mathbf{y} \] 其中 \(J\) 是上述对角矩阵。这个方程可以通过求解线性系统来得到所有点（包括无标签点）的预测值 \(\mathbf{f}\)。 5. 算法总结与意义 输入 ：有标签集 \(L\)， 无标签集 \(U\)， 正则化参数 \(\gamma_ A, \gamma_ I\)， 图参数（k, \(\sigma\)）。 建图 ：将所有样本点构建成一个近邻图，计算权重矩阵 \(W\) 和度矩阵 \(D\)。 构造正则化矩阵 ：计算图拉普拉斯矩阵 \(L = D - W\)。 构造核矩阵 ：根据选定的核函数（如高斯核），计算所有样本对（有标签+无标签）的核矩阵 \(K\)。 构造标签向量 ：构建长度为 \(n\) 的初始标签向量，有标签位置为 \(y_ i\)， 无标签位置为0。构造选择矩阵 \(J\)。 求解 ：求解线性系统 \((J + l\gamma_ A K^{-1} + l\gamma_ I L) \mathbf{f} = \mathbf{y}\)， 得到对所有 \(n\) 个点的预测向量 \(\mathbf{f}\)。 输出 ：对于新样本 \(\mathbf{x}\)， 其预测值可通过已学得的表示（或通过核技巧）计算得到。 核心意义 ：该方法巧妙地将无标签数据蕴含的 几何结构信息 （通过图拉普拉斯矩阵 \(L\) 编码）作为一种 正则化约束 ，引入到标准的有监督学习框架中。模型在拟合有标签数据的同时，被强制要求在推测的数据流形上保持平滑，从而利用无标签数据极大地提升了泛化性能，成为半监督学习领域一个里程碑式的方法。