给定有标记样本集合 ,和未标记样本集合 ,其中 。
学习器自动地利用未标记的 来提升学习性能,这就是半监督学习semi-supervised learning
。
半监督学习的现实需求非常强烈,因为现实中往往能够容易地收集到大量未标记样本,但是对其标记需要耗费大量的人力、物力。如:在医学影像分析上,对影像的疾病标记需要专家人工进行。
因此可以通过专家人工标注少量的样本,然后采用半监督学习。
虽然未标记样本集 没有直接包含标记信息,但是如果假设 与带 从同样的数据源独立同分布采样而来,则 所包含的关于数据分布的信息对建立模型是有好处的。
要利用未标记样本,必然需要对未标记样本的分布与已标记样本的分布的关联做出假设。
cluster assumption
:假设数据存在簇结构,同一个簇的样本属于同一个类别。manifold assumption
:假设数据分布在一个流形结构上,邻近的样本拥有相似的输出值。其中,邻近的程度用相似度来刻画。相似的样本有相似的输出
。半监督学习可以划分为:纯pure
半监督学习和直推学习transduction learning
。
纯半监督学习:假定训练数据中的未标记样本集 并非待预测的数据。
纯半监督学习是开放性的,它学得的模型能够适用于额外的未观测数据。
直推学习:假定学习过程中考虑的未标记样本集 就是待预测的数据,学习的目标就是在 上获取最优泛化性能。
直推学习是封闭性的,它学得的模型仅仅是针对学习过程中的未标记样本集 。
生成式generative methods
半监督学习方法:直接基于生成式模型的方法。
生成式半监督学习方法假设所有数据(无论是否有标记),都是由同一个潜在的模型生成的。
EM
算法进行极大似然估计求解。生成式半监督学习方法其实是一个算法框架,内部不同算法的主要区别在于生成式模型的假设:不同的假设将产生不同的方法。
给定样本 ,其真实类别标记为 。
假设样本由高斯混合模型产生,且每个类别对应一个高斯混合成分。即数据样本是基于概率密度:
来产生的。其中:
令 为模型 对 的预测标记, 表示样本 隶属的高斯混合成分。
根据最大化后验概率,有:
考虑到 , 则有:
由于 , 则有:
为已知样本 ,则它由第 个高斯混合成分生成的后验概率
为已知 由第 个高斯混合成分生成,则其类别为 的概率
在 中, 需要知道样本的标记 ; 而 并不需要样本的标记。因此有标记和无标记的数据均可利用。
因此通过引入大量的未标记数据,对 的估计可以由于数据量的增长而更为准确,于是上式的整体估计可能会更准确。
给定标记样本集 ,和未标记样本集 ,其中 。
假设所有样本独立同分布,且都是由同一个高斯混合模型 生成的。
高斯混合模型的参数 采用极大似然法来估计。
的对数似然是:
第一项对数项中,为联合概率 :
第二项对数项中,为概率 :
高斯混合模型参数估计可以用EM
算法求解。迭代更新步骤为:
E
步:根据当前模型参数 计算未标记样本 属于各高斯混合成分的概率:M
步:基于 更新模型参数。
令 为第 类的有标记样本数目,则:
以上过程不断迭代直至收敛,即可获得模型参数。
预测过程:根据式子:
来对样本 进行分类。
如果将上述过程中的高斯混合模型替换成其他模型,则可以推导出其他的生成式半监督学习方法。
生成式半监督学习方法优点:方法简单,易于实现。在有标记数据极少的情况下,往往比其他方法性能更好。
缺点:模型假设必须准确,即假设的生成式模型必须与真实数据分布吻合,否则利用未标记数据反倒会降低泛化性能。
在现实任务中往往很难事先做出准确的模型假设,除非拥有充分可靠的领域知识。
半监督支持向量机Semi-Supervised Support Vector Machine:S3VM
是支持向量机在半监督学习上的推广。
在不考虑未标记样本时,支持向量机试图找到最大间隔划分超平面;在考虑未标记样本之后,S3VM
试图找到能将两类有标记样本分开,且穿过数据低密度区域的划分超平面。
如下图中,蓝色点为未标记样本,紫色点为正类样本,黄色点为负类样本。
半监督 SVM
的基本假设是:低密度分隔low-density separation
。这是聚类假设在考虑了线性超平面划分后的推广。
半监督支持向量机中最著名的是 TSVM:Transductive Support Vector Machine
。
与标准SVM
一样,TSVM
也是针对二分类问题的学习方法。
TSVM
试图考虑对未标记样本进行各种可能的标记指派label assignment
:
给定标记样本集 ,和未标记样本集 ,其中 。
TSVM
学习的目标是:为 中的样本给出预测标记 使得:
其中:
确定了一个划分超平面。
为松弛向量 :
是由用户指定的用于平衡模型复杂度、有标记样本、未标记样本重要程度的折中参数。
TSVM
尝试未标记样本的各种标记指派是一个穷举过程,仅当未标记样本很少时才有可能直接求解。因此通常情况下,必须考虑更高效的优化策略。
TSVM
采用局部搜索来迭代地寻求上式的近似解。具体来说:
首先利用有标记样本学得一个SVM
:即忽略上式中关于 与 的项以及约束。
然后利用这个SVM
对未标记数据进行标记指派:即将SVM
预测的结果作为伪标记pseudo-label
赋予未标记样本。
SVM
问题。于是求解可以解出新的划分超平面和松弛向量。接下来, TSVM
找出两个标记指派为异类且很可能发生错误的未标记样本,交换它们的标记,再重新基于上式求解出更新后的划分超平面和松弛向量。
再接下来,TSVM
再找出两个标记指派为异类且很可能发生错误的未标记样本,交换它们的标记,再重新基于上式求解出更新后的划分超平面和松弛向量。
...
标记指派调整完成后,逐渐增大 以提高未标记样本对优化目标的影响,进行下一轮标记指派调整,直至 达到指定阈值为止。
TSVM
算法:
算法输入:
算法输出: 未标记样本的预测结果
算法步骤:
用 训练一个 SVM_l
用 SVM_l
对 中样本进行预测,得到
初始化 ,其中
迭代,迭代终止条件为 。迭代过程为:
基于 ,求解下式,得到 :
对于所有的一对标记指派为异类且很可能发生错误的未标记样本(其条件为:),执行下列操作:
交换二者的标记: 。
该操作等价于交换标记,因为 异号,且其取值为 -1 或者 +1。
基于 ,重新求解得到得到 。
更新 。这里采用简单的倍乘,也可以采用其它增长函数。
迭代终止时,输出
在对未标记样本进行指标指派及调整的过程中,有可能出现类别不平衡问题,即某类的样本远多于另一类。这将对SVM
的训练造成困扰。
为了减轻类别不平衡性造成的不利影响,可对上述算法稍加改进:将优化目标中的 项拆分为 和 两项,分别对应基于伪标记而当作正、反例使用的未标记样本。并在初始化时,令:
其中 和 分别为基于伪标记而当作反、正例而使用的未标记样本数。
TSVM
最终得到的SVM
不仅可以给未标记样本提供了标记,还能对训练过程中未见的样本进行预测。
在 TSVM
算法中,寻找标记指派可能出错的每一对未标记样本进行调整,这是一个涉及巨大计算开销的大规模优化问题。
《Large Scale Transductive SVMs》
中,约 2000 个未标记样本,原始TVSM
迭代收敛大约需要 1个小时。SVM
研究的一个重点是如何设计出高效的优化求解策略。由此发展成很多方法,如基于图核函数梯度下降的LDS
算法,基于标记均值估计的meanS3VM
算法等。
给定一个数据集,可以将其映射为一个图,数据集中每个样本对应于图中的一个结点。若两个样本之间的相似度很高(或者相关性很强),则对应的结点之间存在一条边,边的强度正比于样本之间的相似度(或相关性)。
将有标记样本所对应的结点视作为已经染色,而未标记样本所对应的结点尚未染色。于是半监督学习就对应于“颜色”在图上扩散或者传播的过程。这就是标记传播算法label propagation
。
给定标记样本集 ,和未标记样本集 ,其中 。
基于 构建一个图 。其中
结点集
边集 的权重可以表示为一个亲和矩阵 affinity matirx
,一般基于高斯函数,其定义为:
其中 是用户指定的高斯函数带宽参数。
可以看到:
假定从图 学得一个实值函数 , 其对应的分类规则为: 。
直观上看,相似的样本应该具有相似的标记,于是可以定义关于 的能量函数energy function
:
两个点距离越远, 平方级的增大,而 指数级下降,因此 下降。
因此能量函数 由距离较近的样本对决定。
标签传播算法假定系统能量最小,即 最小。
考虑到 由距离较近的样本对决定,而 是已知的量,因此算法倾向于使得:距离较近的样本具有相近的输出 。
定义对角矩阵 ,其中 为矩阵 的第 行元素之和。
的物理意义为:第 个顶点的度(所有与它相连的边的权重之和)。因此 也称作度矩阵。
定义 为函数 在所有样本上的预测结果。 其中:
结合 的定义以及 的对称性,有: