【半监督学习】理论与实现

介绍

有时候，我们的数据是这样的：l个样本是 labeled 的，u个样本是 unlabeled，并且l≪ul≪u，我们希望把u个样本也用起来。

• 主动学习（active learning）：先在DlDl上训练一个模型，然后用这个模型挑选DuDu上一个对模型改善最有帮助的样本，获取其label。这种方法优点是大幅降低标记成本。缺点是引入专家，通过外部交互来获取额外信息。
• 半监督学习（semi-supervised learning）：不依赖外界交互，但也是用 unlabeled sample 的方法。现实中往往获取标签是昂贵的，而获取数据是廉价的，如医学影像等。

半监督学习又分两类：

• pure semi-supervised learning 假定 unlabeled sample 不是待预测的样本。
• transductive learning（直推学习） 假定 unlabeled sample 是待预测的样本

生成式模型

假设所有数据都是由同一个潜在模型“生成”的。高斯混合模型、朴素贝叶斯等算法都可以推广为生成式模型。

半监督SVM

Semi-Supervised Support Vector Machine（半监督支持向量机） 思路是找到这样的超平面：

1. 能将两类 labeled sample 分开
2. 穿过数据低密度区域，“低密度分割”（low-density separation）

模型

最著名的是 TSVM（Transductive Support Vector Machine） (针对二分类的半监督SVM方法)
思路是对所有的 unlabeled sample 进行各种可能的标记指派（label assignment，也就是尝试对每个 unlabeled sample 作为正例或反例），然后在所有这些结果中找到间隔最大化的超平面。

数学表示：
给定Dl={(x1,y1),(x2,y2),...,(xk,yk)},Dl={(x1,y1),(x2,y2),...,(xk,yk)},
minw,b,y^,ξ12∣∣w∣∣22+Cl∑i∈labeledξi+Cu∑i∈unlabeledξiminw,b,y^,ξ12∣∣w∣∣22+Cl∑i∈labeledξi+Cu∑i∈unlabeledξi
s.t.
yi(wTxi+b)≥1−ξi,i∈labeledyi(wTxi+b)≥1−ξi,i∈labeled
y^i(wTxi+b)≥1−ξi,i∈unlabeledy^i(wTxi+b)≥1−ξi,i∈unlabeled
ξi≥,i∈labeled∪unlabeledξi≥,i∈labeled∪unlabeled

算法

直接解上面这个最优化有些困难，用迭代方法来解。

图半监督学习

思路是把数据集映射成一个图，然后用图的分割算法。

step1：把数据集映射成一个图。其中给每个样本是一个节点，边的权重可以用样本间的相似度来体现，例如，Wij=exp(−∣∣xi−xj∣∣222σ2),i≠jWij=exp⁡(−∣∣xi−xj∣∣222σ2),i≠j
step2：使用LP算法，以WijWij为概率执行标签传播，并保持 labeled data 的标签不变。
step3：重复执行step2，直到满足停止条件。

算法改进（效率上）

转移概率为[PllPulPluPuu][PllPluPulPuu]

其中，Pll,YlPll,Yl都是事先已知的，
算法就是 fu←Puufu+pulYlfu←Puufu+pulYl
然后上面这个迭代式还能求出解析解。fu=(I−Puu)−1Pulflfu=(I−Puu)−1Pulfl

图半监督学习的实现

from sklearn import datasets
import scipy.stats as stats
import matplotlib.pyplot as plt

data,label=datasets.make_circles(n_samples=300,noise=0.1,factor=0.5)
unlabeled_idx=stats.uniform().rvs(size=len(label))

label[unlabeled_idx>0.3]=-1

data1=data[label==1]
data2=data[label==0]
data3=data[label==-1]
plt.plot(data1[:,0],data1[:,1],'.r',label='case1')
plt.plot(data2[:,0],data2[:,1],'.b',label='case2')
plt.plot(data3[:,0],data3[:,1],'.g',label='unlabeled')
plt.legend()
plt.show()

from sklearn.semi_supervised import LabelSpreading
label_prop_model = LabelSpreading()
label_prop_model.fit(data, label)
Y_predict=label_prop_model.predict(data)

结果可视化

data1=data[Y_predict==1]
data2=data[Y_predict==0]
plt.plot(data1[:,0],data1[:,1],'.r',label='case1')
plt.plot(data2[:,0],data2[:,1],'.b',label='case2')
plt.legend()
plt.show()

基于分歧的方法

一个数据对象同时拥有多个 attribute set，每个attribute set 构成一个 view. 例如，要做电影分类，那么图像和声音就是两个 view

协同训练的思路是这样的：对第一个 view 建立一个分类器，然后把最有把握的未标记数据赋予未标记，让第二个分类器去学习。然后第二个分类器做同样的操作。这个“互相学习、共同进步”

理论显示，如果两个试图充分且条件独立，那么用未标记数据通过协同训练可以将弱分类器的泛化性能提升到任意高。进一步，协同训练无须多视图。

参考资料

周志华：《机器学习》