半监督SVM

这里是阅读周志华的《机器学习》中关于半监督SVM（S3VM）的笔记。

什么是半监督学习

在数据的搜集中，获得标记数据的成本是高昂的，而获得未标记的数据则是低廉的，为此人们提出了半监督的学习方法，旨在利用少量的标记数据和大量的未标记数据进行学习，从而节约成本。这是可能做到的，比如有一些未被标记的数据和一个被标记的正样本数据非常相似，那么我们就可以将这些未被标记的样本视为正样本来学习。半监督学习有区别于主动学习，主动学习要利用未标记样本需要有一个外部的“专家”给出一个真实标记，而半监督学习则是自己预测。半监督学习具体还可以分为两类，即（纯）半监督学习和直推学习，前者假定训练数据中的未标记样本并非待预测的数据，模型用于预测样本之外的数据，而后者则假定学习过程中所考虑的未标记样本恰是待预测数据。

半监督SVM要做什么

S3VM是SVM在半监督学习上的推广。在不考虑未标记样本时，SVM 试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面，如图所示。

TSVM

半监督SVM中最著名的是TSVM（Transductive Support Vector Machine）形式化说，给定 $D_l = \{(x_1,y_1),(x_2,y_2),...,(x_l,y_l)\}$和 $D_u = \{x_{l+1},x_{l+2},...,x_{l+u}\}$，其中 $y_i\in \{-1,+1\}$， $l\ll u$且 $l+u=m$。TSVM的学习目标是为 $D_u$中的样本给出预测标记 $\hat y = (\hat y_{l+1},\hat y_{l+2},...,\hat y_{l+u})$， $\hat y_i \in \{-1, +1\}$，使得
$\min_{w,b,\hat y, \xi} \frac{1}{2}\|w\|+C_l\sum_{i=1}^l\xi_i+C_u\sum_{i=l+1}^m\xi_i\\ s.t. \quad y_i(w^Tx_i+b)\geq 1-\xi_i,i=1,2,...,l, \\ \quad \quad \quad \quad \quad \quad y_i(w^Tx_i+b)\geq 1-\xi_i,i=l+1,l+2,...,m,\\ \xi_i\geq 0, i=1,2,...,m.$
其中， $(w,b)$确定了一个超平面。具体来说，TSVM算法如下：首先用已标记的数据训练一个SVM，用这个SVM划分未标记的数据，进行”预标记“；将 $C_u$定为一个较小的值，找出可能出错的指派标记对，这两个样本的预标记为一正一副，且对应的松弛变量都大于0且相加大于1，将这些标记点对的指派互换；增加 $C_u$直到 $C_u=C_l$为止。下是TSVM 的伪代码。这里 $C_u$ 的作用在于一开始预测比较不准确，因此未标记数据的权重应该比较低，随着算法的进行，预测准确度上升， $C_u$ 的值也随之上升。

周志华教授还提到了一个防止TSVM划分不均匀的办法，那就是将预测正样本和预测负样本的参数 $C_u$分隔开来，标为 $C^+$ 和 $C^-$ ，然后令两者的比值等于预测负样本数与预测正样本数的比值。这样做的思想是，当标记点不均匀时，相对较多的那一类目标函数中乘上的常数较小，每个点越界的惩罚就较小，场平面就会相对往点多的那一类的方向移动。

转载：https://blog.csdn.net/Hai0bin1Wang2/article/details/100990342