第13章半监督学习

🎯 学习目标

理解半监督学习的基本假设和动机
掌握自训练和协同训练方法
理解生成式和判别式半监督学习
了解图半监督学习和标签传播

13.1 未标记样本

半监督学习的动机

在许多实际应用中，获取标记数据成本高昂（需要人工标注），而未标记数据容易获取。半监督学习（Semi-Supervised Learning） 试图利用少量标记样本和大量未标记样本来提升学习性能。

学习范式对比

监督学习（Supervised）：使用完全标记的数据 $D_{l} = {(x_{1}, y_{1}), \dots, (x_{m}, y_{m})}$
半监督学习（Semi-Supervised）：同时使用少量标记数据 $D_{l}$ 和大量未标记数据 $D_{u} = {x_{m + 1}, \dots, x_{m + u}}$ ，通常 $u ≫ m$
无监督学习（Unsupervised）：只有未标记数据，如聚类、降维

💡 为什么未标记数据有帮助？

未标记数据能够揭示数据的分布结构：

帮助发现数据的簇结构、流形结构
提供关于决策边界位置的信息（应避开高密度区域）
增强模型的泛化能力

半监督学习假设

半监督学习需要对数据分布做一些假设，才能有效利用未标记数据：

聚类假设（Cluster Assumption）：数据存在簇结构，同一簇内的样本倾向于属于同一类别。决策边界应位于低密度区域，避免穿过簇。
流形假设（Manifold Assumption）：高维数据分布在低维流形上，相近的样本（沿流形的测地线距离）倾向于有相同标记。
平滑假设（Smoothness Assumption）：如果两个样本在高密度区域中相近，则它们的标记应该相同或相似。

注意

如果数据不满足这些假设，未标记数据可能降低性能！半监督学习不是万能的。

13.2 生成式方法

生成式半监督学习

生成式方法 假设数据由某个概率模型生成，利用未标记数据来更准确地估计模型参数。

基于混合模型的方法

假设数据由混合模型生成（如高斯混合模型GMM），每个混合成分对应一个类别：

用标记数据初始化模型参数（均值、协方差、混合系数）
E步：计算未标记样本属于各成分的后验概率
M步：利用所有样本（标记+未标记）更新参数
重复2-3直到收敛

对数似然：

L = \sum_{(x, y) \in D_{l}} \log P (x, y | θ) + \sum_{x \in D_{u}} \log P (x | θ)

标记数据提供类别信息，未标记数据帮助估计数据分布。

优点：有坚实的概率理论基础，EM算法保证收敛。缺点：依赖模型假设，如果模型不匹配真实分布，效果不佳。

13.3 半监督SVM

TSVM（Transductive SVM）

直推式SVM（Transductive SVM, TSVM） 也称为S3VM（Semi-Supervised SVM），试图找到一个决策边界，使其穿过低密度区域，同时对标记样本有较大间隔。

TSVM优化目标

同时优化标记样本的分类精度和未标记样本的置信度：

min ∥ w ∥^{2} + C_{l} \sum_{i \in D_{l}} ξ_{i} + C_{u} \sum_{j \in D_{u}} ξ_{j}

约束条件：

$y_{i} (w^{T} x_{i} + b) \geq 1 - ξ_{i}$ （标记样本）
$| w^{T} x_{j} + b | \geq 1 - ξ_{j}$ （未标记样本：远离决策边界）

TSVM算法流程

在标记数据上训练初始SVM
用初始SVM预测未标记样本的标记（伪标记）
选择置信度最低的未标记样本，尝试翻转其标记
重新训练SVM，如果目标函数下降则接受翻转
重复3-4直到收敛或达到最大迭代次数

💡 低密度分离

TSVM体现了聚类假设：决策边界应位于低密度区域。通过要求未标记样本远离决策边界（ $| f (x) | \geq 1$ ），TSVM避免决策边界穿过数据密集区域。

TSVM是非凸优化问题，通常使用启发式算法求解，难以保证全局最优。

13.4 图半监督学习

基于图的半监督学习

图半监督学习 将数据表示为图，节点是样本，边表示样本间的相似度。标记信息从标记节点沿着边传播到未标记节点。

图的构建

k近邻图：如果 $x_{j}$ 是 $x_{i}$ 的k个最近邻之一，连接边(i, j)
ε近邻图：如果 $∥ x_{i} - x_{j} ∥ < ε$ ，连接边(i, j)
全连接图：所有节点两两相连，边权重 $w_{i j} = \exp (- ∥ x_{i} - x_{j} ∥^{2} / 2 σ^{2})$ （高斯核）

标签传播算法

Label Propagation

迭代地让每个未标记节点从邻居获取标记，直到收敛：

初始化：标记样本保持其真实标记，未标记样本随机初始化
对每个未标记样本 $x_{i}$ ，更新其标记为邻居标记的加权平均：

y_{i} \leftarrow \frac{\sum_{j} w_{i j} y_{j}}{\sum_{j} w_{i j}}

重复步骤2直到标记不再变化

Label Spreading

Label Propagation的改进版本，允许标记样本的标记也参与更新（软钳制）：

Y^{(t + 1)} = α S Y^{(t)} + (1 - α) Y^{(0)}

S是归一化的相似度矩阵， $α \in (0, 1)$ 控制标记样本标记的保持程度， $Y^{(0)}$ 是初始标记。

基于图的正则化

从能量最小化角度看图半监督学习，目标是最小化：

E = \sum_{(x, y) \in D_{l}} ∥ f (x) - y ∥^{2} + λ \sum_{i j} w_{i j} ∥ f (x_{i}) - f (x_{j}) ∥^{2}

第一项：拟合标记数据；第二项：平滑性正则化，相似样本的预测应相近。

在k近邻图上观察标签如何从少量标记节点传播到整个网络：

迭代次数

标记样本

未标记样本

准确率

平滑参数 α: 0.80

标签传播 (α=1)标签扩散 (α<1)

图例说明

标记样本（类别0）

标记样本（类别1）

未标记样本

颜色深浅表示预测置信度，连线表示k近邻关系

13.5 分歧方法

协同训练（Co-Training）

协同训练 假设特征可以分为两个充分且条件独立的视图（view），利用多视图之间的互补信息进行半监督学习。

Co-Training算法

将特征分为两个视图： $x = (x^{(1)}, x^{(2)})$
在每个视图上用标记数据训练一个分类器 $h^{(1)}, h^{(2)}$
用 $h^{(1)}$ 对未标记数据预测，选择最有信心的样本加入标记集
用 $h^{(2)}$ 对未标记数据预测，选择最有信心的样本加入标记集
重新训练两个分类器
重复3-5直到满足停止条件

经典应用：网页分类 — 视图1：网页自身的文本内容；视图2：指向该网页的超链接锚文本。

💡 为什么有效？

两个视图提供不同的"视角"看数据，一个分类器的高置信度预测可以作为另一个分类器的训练样本，从而利用未标记数据。关键假设：两个视图充分（每个都足以分类）且条件独立（给定类别，两个视图独立）。

自训练（Self-Training）

自训练 是一种简单的半监督学习方法，反复使用自己的预测来扩充训练集。

Self-Training算法

在标记数据上训练初始分类器
用分类器预测未标记数据
选择置信度最高的k个预测，将其伪标记加入训练集
重新训练分类器
重复2-4直到未标记数据用完或达到停止条件

优点：非常简单，易于实现，适用于任何分类器。缺点：错误会累积（一旦加入错误伪标记，难以纠正），容易产生"确认偏误"。

提示

Co-Training比Self-Training更可靠，因为两个视图的"意见不一致"能够互相纠错。

13.6 半监督聚类

约束聚类

半监督聚类 利用少量监督信息（标记样本或成对约束）来改善聚类结果。

成对约束

Must-Link（ML）约束： $x_{i}$ 和 $x_{j}$ 必须在同一个簇中
Cannot-Link（CL）约束： $x_{i}$ 和 $x_{j}$ 不能在同一个簇中

这些约束可以从标记样本自动生成：同类样本产生ML约束，异类样本产生CL约束。

约束k-means算法

初始化k个簇中心
对于每个样本 $x_{i}$ ：找到最近的簇中心 $C_{j}$ ，检查是否违反约束
如果违反CL约束，选择次近的不违反约束的簇
如果违反ML约束，将相关样本也分配到同一簇
更新簇中心
重复2-5直到收敛

度量学习 + 聚类

另一种策略是利用约束学习距离度量，然后用学到的度量进行聚类：从约束中学习马氏距离矩阵M，用学到的度量 $d_{M} (x, x^{'}) = \sqrt{(x - x^{'})^{T} M (x - x^{'})}$ 进行k-means聚类。

💡 应用场景

半监督聚类适用于：用户交互式聚类（用户提供少量标注反馈）、主动学习（选择最有价值的样本询问标签）、知识发现（利用领域知识改善聚类）。

第13章 半监督学习 ​

🎯 学习目标 ​

13.1 未标记样本 ​

13.2 生成式方法 ​

13.3 半监督SVM ​

13.4 图半监督学习 ​