本文是周志华《机器学习》（西瓜书）第13章 半监督学习（Semi-Supervised）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

①. 问题概述与基本假设

为什么半监督学习有效？三大核心假设

🎓 生活类比：考前临时抱佛脚

期末复习只有 10 道有答案的例题（标注数据），但你手里有 1000 份历年试卷但没有答案（无标签数据）。半监督学习就是：虽然不知道 1000 份的答案，但通过观察这些题目的规律和分布——“这类题总是一起出现”、”这两道题很像”——来辅助你学习那 10 道有答案的题，效果远好于只看 10 道题。

📌 问题设定

设有有标记样本集 Dl={(x1,y1),…,(xl,yl)}D_l = \{(\boldsymbol{x}_1, y_1), \ldots, (\boldsymbol{x}_l, y_l)\}，以及无标记样本集 Du={xl+1,…,xl+u}D_u = \{\boldsymbol{x}_{l+1}, \ldots, \boldsymbol{x}_{l+u}\}，通常 l≪ul \ll u（标注远少于未标注）。

半监督学习的目标：利用 Dl∪DuD_l \cup D_u 学习一个比仅用 DlD_l 更好的模型。

监督学习 ✓ ✓ ✓ ✓ 全部有标签 半监督学习 ✨ ✓ ✓ 少量标签 + 大量无标签 无监督学习 全部无标签 实心圆=有标签，虚线圆=无标签

🏗️ 三大基本假设

半监督学习有效性建立在以下假设之上，若假设不成立，引入无标签数据可能有害！

平滑性假设（Smoothness）

若两个样本在输入空间中距离很近，则它们的输出标签也应相似。

→ 决策边界应穿过低密度区域

聚类假设（Cluster）

同一聚类中的样本倾向于属于同一类别，数据的自然聚类结构揭示类别信息。

→ 聚类等价于分类边界

流形假设（Manifold）

高维输入数据分布在某个低维流形上，同一流形上相邻的样本应有相似标签。

→ 在流形空间中距离近的点具有相似标签（平滑性假设的低维形式）

②. 生成式方法

EM 算法 + 高斯混合模型：用概率模型整合无标签数据

🎲 生活类比：猜测蘑菇种类

你是个蘑菇专家，见过 5 种有明确标签的蘑菇样本，还有 100 个不知道种类的蘑菇。生成式方法的思路是：假设所有蘑菇都服从某种混合高斯分布（不同种类是不同的高斯分量），用 EM 算法反复猜测：先猜每个无标签蘑菇最可能是哪一类（E步），再基于这些猜测更新每一类的参数（M步），直到收敛。

📐 高斯混合模型（GMM）半监督

假设数据由高斯混合分布生成，每个类别对应一个或多个高斯分量：

📐 混合模型

p(x)=∑k=1Kαk⋅p(x∣μk,Σk) p(\boldsymbol{x}) = \sum_{k=1}^{K} \alpha_k \cdot p(\boldsymbol{x} \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)

其中 αk≥0,∑k=1Kαk=1\alpha_k \geq 0, \sum_{k=1}^K \alpha_k = 1，p(x∣μk,Σk)p(\boldsymbol{x} \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) 是第 kk 个高斯分量。

对数似然函数同时考虑有标签和无标签数据：

📐 联合对数似然

L=∑(xi,yi)∈Dlln⁡p(xi,yi)⏟有标签部分+∑xj∈Duln⁡p(xj)⏟无标签部分 \mathcal{L} = \underbrace{\sum_{(\boldsymbol{x}_i, y_i)\in D_l} \ln p(\boldsymbol{x}_i, y_i)}_{\text{有标签部分} } + \underbrace{\sum_{\boldsymbol{x}_j \in D_u} \ln p(\boldsymbol{x}_j)}_{\text{无标签部分} }

EM 算法求解流程

Algorithm: 半监督 GMM（EM算法）
输入: 有标签集 D_l，无标签集 D_u，类别数 K
初始化: 由 D_l 估计初始参数 {α_k, μ_k, Σ_k}

重复直到收敛:
// E步：计算每个无标签样本属于各分量的后验概率
for x_j in D_u:
γ_jk = α_k · p(x_j|μ_k, Σ_k) / Σ_k’ [α_k’ · p(x_j|μ_k’, Σ_k’)]

// M步：利用 D_l（硬标签）和 D_u（软标签 γ）更新参数
for k = 1,…,K:
μ_k ← (Σ_{有标签 y_i=k} x_i + Σ_{无标签} γ_jk · x_j) / (n_k + Σ_j γ_jk)
Σ_k ← 类似加权协方差更新
α_k ← (n_k + Σ_j γ_jk) / (l + u)

输出: 分类决策函数 f(x) = argmax_k γ_k(x)

⚠️ 生成式方法的风险

模型假设（如高斯分布）若与实际数据分布不符，无标签数据不但无益，反而会降低性能——这就是”假设不成立时半监督有害”的典型案例。

③. 半监督支持向量机（S³VM / TSVM）

让决策超平面穿过低密度区域

✂️ 生活类比：沿峡谷划边界

普通 SVM 只看有标签点，在它们之间找最宽的”街道”。TSVM 的直觉是：我不仅要让标注点分开，还要让分割线尽量走在数据的”峡谷”（低密度区域），避免把紧密聚集的无标签点群切成两半——因为同一群点很可能是同一类。

📐 TSVM 优化目标

直觉核心：决策边界应穿过特征空间中数据分布稀疏的区域，这与平滑性假设一致。

为无标签样本分配伪标签 y^j∈{−1,+1}\hat{y}_j \in \{-1, +1\}，然后同时优化：

📐 TSVM 优化问题

min⁡w,b,y^,ξ,ξ^12∥w∥2+Cl∑i=1lξi+Cu∑j=1uξ^j \min_{\boldsymbol{w},b,\hat{y},\boldsymbol{\xi},\hat{\boldsymbol{\xi} } } \frac{1}{2}\|\boldsymbol{w}\|^2 + C_l\sum_{i=1}^l \xi_i + C_u\sum_{j=1}^u \hat{\xi}_j
s.t.yi(w⊤xi+b)≥1−ξi,ξi≥0(i=1,…,l) \text{s.t.}\quad y_i(\boldsymbol{w}^\top\boldsymbol{x}_i+b)\geq 1-\xi_i,\quad \xi_i\geq 0 \quad (i=1,\ldots,l)
y^j(w⊤xj+b)≥1−ξ^j,ξ^j≥0(j=1,…,u) \hat{y}_j(\boldsymbol{w}^\top\boldsymbol{x}_j+b)\geq 1-\hat{\xi}_j,\quad \hat{\xi}_j\geq 0 \quad (j=1,\ldots,u)

其中 Cl,CuC_l, C_u 分别控制有标签/无标签样本的惩罚力度，通常令 CuC_u 从小到大逐渐增大。

普通 SVM（仅用有标签点） + + - - ❌ 边界穿过数据密集区 TSVM（利用无标签点） + + - - ✅ 边界走低密度区间隙

💡 实现策略：逐步增大 CuC_u

从 Cu≪ClC_u \ll C_l 开始，逐渐增大 CuC_u，使无标签数据的约束越来越严格，防止局部最优陷阱。这是一种从监督到半监督的平滑过渡策略。

④. 基于图的半监督学习

标签传播：让标签在数据图上”流动”

🕸️ 生活类比：谣言传播

把所有样本看成城市里的人，样本越相似，两人之间的”道路”越宽。知道身份的人（有标签）是信息源，通过人际网络把”标签信息”传播出去。住得近（相似度高）的人更容易被影响，最终每个人都会有一个稳定的”标签信念值”。

🔧 图构建与标签传播算法

Step 1：构建样本图

将所有 l+ul+u 个样本视为图的节点，边权重 wijw_{ij} 反映样本相似度，常用高斯核：

📐 高斯权重

wij=exp⁡ ⁣(−∥xi−xj∥22σ2) w_{ij} = \exp\!\left(-\frac{\|\boldsymbol{x}_i - \boldsymbol{x}_j\|^2}{2\sigma^2}\right)

Step 2：标签传播（Label Propagation）

定义概率转移矩阵 T\boldsymbol{T}（行归一化）：Tij=wij∑kwikT_{ij} = \frac{w_{ij} }{\sum_k w_{ik} }

📐 迭代传播公式

F(t+1)=αTF(t)+(1−α)Y \boldsymbol{F}(t+1) = \alpha \boldsymbol{T} \boldsymbol{F}(t) + (1-\alpha)\boldsymbol{Y}

其中 F\boldsymbol{F} 是标签置信矩阵，Y\boldsymbol{Y} 是初始标签矩阵（有标签行用 one-hot，无标签行全零），α∈(0,1)\alpha \in (0,1) 控制传播强度。

迭代收敛的闭式解：

📐 闭式解

F∗=(1−α)(I−αT)−1Y \boldsymbol{F}^* = (1-\alpha)(\boldsymbol{I} - \alpha\boldsymbol{T})^{-1}\boldsymbol{Y} 标注 + ? ? ? 标注 - ? w=0.9 w=0.8 w=0.85 → 传为"+" → 中性 → 传为"-" 标签沿高权重边传播，与有标签节点越近（边权越大）影响越强

🔑 标签传播 vs. 标签扩散

  • 标签传播（Label Propagation）：有标签节点的标签固定（钳制），标签只向无标签节点传播。
  • 标签扩散（Label Spreading）：引入正则化参数 α\alpha，有标签节点也可被邻居”影响”，更鲁棒但可能偏移原始标签。

⑤. 基于分歧的方法（协同训练）

多视图学习：让不同视角的模型互相”教”对方

👫 生活类比：两个专家互相补课

数学老师和物理老师共同批改同一批没有答案的题。数学老师对某道题有 95% 把握，就把它的”答案”告诉物理老师补充训练；物理老师对另一道题有把握，反过来告诉数学老师。通过互相”喂高置信样本”，两位老师的综合能力越来越强。

🔄 协同训练（Co-Training）算法

🔑 多视图假设

数据可分解为两个充分且条件独立的视图（特征集），如：一个网页的文字内容和超链接锚文本。

Algorithm: Co-Training（协同训练）
输入: 有标签集 L，无标签池 U，视图1特征 X¹，视图2特征 X²

// 初始化两个分类器
h₁ ← 在 (X¹_L, Y_L) 上训练
h₂ ← 在 (X²_L, Y_L) 上训练

重复 T 轮:
// 各自对无标签数据预测，挑出最有把握的
P₁ ← h₁ 在 U 上预测置信度最高的 p 个正例和 n 个负例
P₂ ← h₂ 在 U 上预测置信度最高的 p 个正例和 n 个负例

// 互相”喂”高置信样本（关键！）
用 P₁ 的伪标签扩充 h₂ 的训练集
用 P₂ 的伪标签扩充 h₁ 的训练集

// 更新两个分类器
从 U 中移除 P₁ ∪ P₂

输出: 集成分类器 h₁ + h₂

✅ 优点

  • 不要求生成式假设，适用性广
  • 两个视图的”分歧”提供了天然的信号
  • 理论保证：若视图充分且独立，性能随无标签数据增多单调提升

⚠️ 局限

  • 需要自然存在的多视图（特征分割有时很难）
  • 若两个视图有相关性，效果打折
  • 错误的伪标签会累积（error accumulation）

单视图变体：自训练（Self-Training）

只用一个模型，每轮将自己最自信的预测结果加入训练集，循环迭代。简单有效但误差积累风险更高。

Algorithm: Self-Training（自训练）
输入: 有标签集 L，无标签池 U
h ← 在 L 上训练初始模型

重复直到 U 为空或达到上限:
对 U 中所有样本预测，取置信度 > θ 的样本集合 Û
将 (Û, 伪标签) 加入 L，从 U 移除
h ← 在新的 L 上重新训练

输出: h

⑥. 半监督聚类

用少量先验约束引导聚类方向

🔗 约束 k-均值（Constrained k-Means）

在经典 k-Means 基础上引入**必连（must-link）和勿连（cannot-link）**约束：

🔗 必连约束（Must-Link）

样本 xi\boldsymbol{x}_i 与 xj\boldsymbol{x}_j 必须在同一簇中。

来源：已知同类的标注对

⛔ 勿连约束（Cannot-Link）

样本 xi\boldsymbol{x}_i 与 xj\boldsymbol{x}_j 必须在不同簇中。

来源：已知异类的标注对

Algorithm: Constrained k-Means
输入: 样本集 X，簇数 k，约束集 M（必连）, C（勿连）
初始化: 随机选 k 个中心 {μ₁,…,μk}

重复直到收敛:
for x_i in X:
// 找最近中心，但要满足约束
λ(x_i) ← argmin_{k} d(x_i, μ_k) s.t. 不违反 M 和 C 中的约束

// 更新中心
μ_k ← mean({x_i : λ(x_i) = k})

若无满足约束的分配: 报错（约束冲突）

半监督聚类的另一思路：带标签引导

直接利用少量标注样本初始化聚类中心，或用标注样本的分布来调整距离度量，让聚类空间更符合任务目标。

💡 两种监督信息来源

  • 标注信息：部分样本已知类别，可直接作为聚类锚点
  • 成对约束：只知道”这两个是同类”或”不同类”，无需具体类别标签，更易获取

⑦. 方法横向对比与总结

四类半监督方法的适用场景与优劣

方法类别 代表算法 核心假设 优点 缺点/风险 适用场景
生成式方法 GMM + EM 数据来自参数化分布 有概率解释，可计算不确定性 模型误规约导致性能下降 分布假设较合理的低维数据
半监督 SVM TSVM、S³VM 决策面走低密度区 最大间隔原则，鲁棒 计算代价高，非凸优化 中小规模二分类
图半监督 LPA、LGC、流形正则 平滑性/流形假设 直觉清晰，支持多类 图构建开销大，不易泛化到新点 有明显流形结构的数据
协同训练 Co-Training、Self-Training 多视图充分且独立 无分布假设，灵活 错误累积，视图分割难 存在多视图的文本/多模态数据
半监督聚类 约束 k-Means 聚类结构对齐分类 利用成对约束，标注代价低 约束冲突导致失败 获取成对约束比类别标签更容易时

🎯 半监督学习使用决策树

有无标签数据可用？ l ≪ u 是 否 数据有自然多视图？ （多特征集） 使用普通监督学习 是 协同训练 否 数据有流形结构？ （高维但低维分布） 图半监督学习 TSVM / 生成式

📝 核心公式速查

方法 关键公式 含义
GMM-EM E步 γjk=αkp(xj∣μk,Σk)∑k′αk′p(xj∣μk′,Σk′)\gamma_{jk} = \dfrac{\alpha_k p(\boldsymbol{x}_j|\boldsymbol{\mu}_k,\boldsymbol{\Sigma}_k)}{\sum_{k'}\alpha_{k'} p(\boldsymbol{x}_j|\boldsymbol{\mu}_{k'},\boldsymbol{\Sigma}_{k'})} 无标签样本属于第 kk 个分量的后验概率
TSVM 目标 min⁡12∥w∥2+Cl∑ξi+Cu∑ξ^j\min \frac{1}{2}\|\boldsymbol{w}\|^2 + C_l\sum\xi_i + C_u\sum\hat{\xi}_j 同时最大化有/无标签样本间隔
标签传播 F∗=(1−α)(I−αT)−1Y\boldsymbol{F}^* = (1-\alpha)(\boldsymbol{I}-\alpha\boldsymbol{T})^{-1}\boldsymbol{Y} 迭代传播的闭式稳态解
图权重 wij=exp⁡(−∥xi−xj∥2/2σ2)w_{ij} = \exp(-\|\boldsymbol{x}_i-\boldsymbol{x}_j\|^2 / 2\sigma^2) 高斯核衡量样本相似度

半监督学习的核心矛盾：无标签数据理论上能帮助模型，但只有当数据假设（平滑性/聚类/流形）成立时才真的有帮助——这要求我们在使用前仔细检验数据结构，而非盲目引入无标签数据。