未标记样本
半监督学习的动机
在许多实际应用中，获取标记数据成本高昂（需要人工标注），而未标记数据容易获取。半监督学习（Semi-Supervised Learning）试图利用少量标记样本和大量未标记样本来提升学习性能。
学习范式对比
监督学习（Supervised）
使用完全标记的数据 Dl = {(x₁,y₁), ..., (xₘ,yₘ)}
半监督学习（Semi-Supervised）
同时使用少量标记数据 Dl 和大量未标记数据 Du = {xₘ₊₁, ..., xₘ₊ᵤ}，通常 u ≫ m
无监督学习（Unsupervised）
只有未标记数据，如聚类、降维
💡 为什么未标记数据有帮助？
未标记数据能够揭示数据的分布结构：
- • 帮助发现数据的簇结构、流形结构
- • 提供关于决策边界位置的信息（应避开高密度区域）
- • 增强模型的泛化能力
半监督学习假设
半监督学习需要对数据分布做一些假设，才能有效利用未标记数据：
1. 聚类假设（Cluster Assumption）
数据存在簇结构，同一簇内的样本倾向于属于同一类别。 决策边界应位于低密度区域，避免穿过簇。
2. 流形假设（Manifold Assumption）
高维数据分布在低维流形上，相近的样本（沿流形的测地线距离）倾向于有相同标记。
3. 平滑假设（Smoothness Assumption）
如果两个样本在高密度区域中相近，则它们的标记应该相同或相似。
警告： 如果数据不满足这些假设，未标记数据可能降低性能！半监督学习不是万能的。
半监督学习假设可视化
展示聚类假设、流形假设、平滑假设在不同数据分布上的效果
🚧 开发中...
生成式方法
生成式半监督学习
生成式方法假设数据由某个概率模型生成， 利用未标记数据来更准确地估计模型参数。
基于混合模型的方法
假设数据由混合模型生成（如高斯混合模型GMM），每个混合成分对应一个类别：
- 用标记数据初始化模型参数（均值、协方差、混合系数）
- E步：计算未标记样本属于各成分的后验概率
- M步：利用所有样本（标记+未标记）更新参数
- 重复2-3直到收敛
对数似然
ℒ = Σ(x,y)∈Dl log P(x, y | θ) + Σx∈Du log P(x | θ)
标记数据提供类别信息，未标记数据帮助估计数据分布
优点：有坚实的概率理论基础，EM算法保证收敛。缺点：依赖模型假设，如果模型不匹配真实分布，效果不佳。
生成式半监督学习演示
用GMM进行半监督分类，观察未标记数据如何改善类别边界
🚧 开发中...
半监督SVM
TSVM（Transductive SVM）
直推式SVM（Transductive SVM, TSVM）也称为S3VM（Semi-Supervised SVM），试图找到一个决策边界，使其穿过低密度区域， 同时对标记样本有较大间隔。
TSVM优化目标
同时优化标记样本的分类精度和未标记样本的置信度：
min ||w||² + ClΣi∈Dlξᵢ + CuΣj∈Duξⱼ
s.t. yᵢ(wTxᵢ + b) ≥ 1 - ξᵢ （标记样本）
|wTxⱼ + b| ≥ 1 - ξⱼ （未标记样本：远离决策边界）
TSVM算法流程
- 在标记数据上训练初始SVM
- 用初始SVM预测未标记样本的标记（伪标记）
- 选择置信度最低的未标记样本，尝试翻转其标记
- 重新训练SVM，如果目标函数下降则接受翻转
- 重复3-4直到收敛或达到最大迭代次数
💡 低密度分离
TSVM体现了聚类假设： 决策边界应位于低密度区域。通过要求未标记样本远离决策边界（|f(x)| ≥ 1）， TSVM避免决策边界穿过数据密集区域。
TSVM是非凸优化问题，通常使用启发式算法求解，难以保证全局最优。
TSVM决策边界演示
对比SVM和TSVM的决策边界，观察低密度分离效果
🚧 开发中...
图半监督学习
基于图的半监督学习
图半监督学习将数据表示为图，节点是样本，边表示样本间的相似度。 标记信息从标记节点沿着边传播到未标记节点。
图的构建
- k近邻图： 如果xⱼ是xᵢ的k个最近邻之一，连接边(i, j)
- ε近邻图： 如果 ||xᵢ - xⱼ|| < ε，连接边(i, j)
- 全连接图： 所有节点两两相连，边权重 wᵢⱼ = exp(-||xᵢ - xⱼ||²/2σ²)（高斯核）
标签传播算法
Label Propagation
迭代地让每个未标记节点从邻居获取标记，直到收敛：
- 初始化：标记样本保持其真实标记，未标记样本随机初始化
- 对每个未标记样本xᵢ，更新其标记为邻居标记的加权平均：
yᵢ ← Σⱼ wᵢⱼyⱼ / Σⱼ wᵢⱼ
- 重复步骤2直到标记不再变化
Label Spreading
Label Propagation的改进版本，允许标记样本的标记也参与更新（软钳制）：
Y(t+1) = αSY(t) + (1-α)Y(0)
S是归一化的相似度矩阵，α∈(0,1)控制标记样本标记的保持程度，Y(0)是初始标记
基于图的正则化
从能量最小化角度看图半监督学习，目标是最小化：
E = Σ(x,y)∈Dl ||f(x) - y||² + λΣᵢⱼ wᵢⱼ||f(xᵢ) - f(xⱼ)||²
第一项：拟合标记数据；第二项：平滑性正则化，相似样本的预测应相近。
✓ 优点
- • 简单直观，易于实现
- • 有封闭解（矩阵求逆）
- • 能利用流形结构
✗ 缺点
- • 计算复杂度高（O(n³)）
- • 对图构建方式敏感
- • 难以处理大规模数据
标签传播交互演示
在k近邻图上观察标签如何从少量标记节点传播到整个网络
图例说明
颜色深浅表示预测置信度，连线表示k近邻关系
💡 标签传播算法
Label Propagation (α=1)
每个未标记样本的标签由其邻居标签的加权平均决定，标记样本的标签保持不变。
Label Spreading (α<1)
允许标记样本的标签也参与更新（软钳制），增强算法鲁棒性。
核心思想
- • 平滑假设：相近的样本倾向于有相同标签
- • 聚类假设：同一簇内的样本属于同一类
- • 流形假设：数据分布在低维流形上
分歧方法
协同训练（Co-Training）
协同训练假设特征可以分为两个充分且条件独立的视图（view）， 利用多视图之间的互补信息进行半监督学习。
Co-Training算法
- 将特征分为两个视图：x = (x(1), x(2))
- 在每个视图上用标记数据训练一个分类器 h(1), h(2)
- 用 h(1) 对未标记数据预测，选择最有信心的样本加入标记集
- 用 h(2) 对未标记数据预测，选择最有信心的样本加入标记集
- 重新训练两个分类器
- 重复3-5直到满足停止条件
💡 为什么有效？
两个视图提供不同的"视角"看数据，一个分类器的高置信度预测可以作为另一个分类器的训练样本， 从而利用未标记数据。关键假设：两个视图充分（每个都足以分类） 且条件独立（给定类别，两个视图独立）。
经典应用：网页分类
网页分类是Co-Training的经典应用场景：
- 视图1：网页自身的文本内容
- 视图2：指向该网页的超链接锚文本
这两个视图都包含关于网页类别的信息，且相对独立。
自训练（Self-Training）
自训练是一种简单的半监督学习方法，反复使用自己的预测来扩充训练集。
Self-Training算法
- 在标记数据上训练初始分类器
- 用分类器预测未标记数据
- 选择置信度最高的k个预测，将其伪标记加入训练集
- 重新训练分类器
- 重复2-4直到未标记数据用完或达到停止条件
✓ 优点
- • 非常简单，易于实现
- • 适用于任何分类器
- • 无需特殊假设
✗ 缺点
- • 错误会累积（一旦加入错误伪标记，难以纠正）
- • 容易产生"确认偏误"
- • 不保证性能提升
提示： Co-Training比Self-Training更可靠，因为两个视图的"意见不一致"能够互相纠错。
Co-Training vs Self-Training
对比协同训练和自训练在双月形数据上的表现
🚧 开发中...
半监督聚类
约束聚类
半监督聚类利用少量监督信息（标记样本或成对约束）来改善聚类结果。
成对约束
- Must-Link（ML）约束： xᵢ 和 xⱼ 必须在同一个簇中
- Cannot-Link（CL）约束： xᵢ 和 xⱼ 不能在同一个簇中
这些约束可以从标记样本自动生成：同类样本产生ML约束，异类样本产生CL约束。
约束k-means算法
- 初始化k个簇中心
- 对于每个样本xᵢ：
- • 找到最近的簇中心Cⱼ
- • 检查是否违反约束：
- - 如果违反CL约束，选择次近的不违反约束的簇
- - 如果违反ML约束，将相关样本也分配到同一簇
- 更新簇中心
- 重复2-3直到收敛
度量学习 + 聚类
另一种策略是利用约束学习距离度量，然后用学到的度量进行聚类：
- 从约束中学习马氏距离矩阵M（ML对应的样本距离应小，CL对应的样本距离应大）
- 用学到的度量 dM(x, x') = √((x-x')TM(x-x')) 进行k-means聚类
💡 应用场景
半监督聚类适用于：用户交互式聚类（用户提供少量标注反馈）、主动学习（选择最有价值的样本询问标签）、 知识发现（利用领域知识改善聚类）。
约束聚类演示
交互式添加ML和CL约束，观察聚类结果的变化
🚧 开发中...