2. 在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面；在考虑未标记样本之后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。

   如下图中，蓝色点为未标记样本，紫色点为正类样本，黄色点为负类样本。

3. 半监督 SVM 的基本假设是：低密度分隔low-density separation。这是聚类假设在考虑了线性超平面划分后的推广。

1. 半监督支持向量机中最著名的是 TSVM:Transductive Support Vector Machine。

   与标准SVM一样，TSVM也是针对二分类问题的学习方法。

2. TSVM试图考虑对未标记样本进行各种可能的标记指派label assignment：

   • 尝试将每个未标记样本分别作为正例或者反例。
   • 然后在所有这些结果中，寻求一个在所有样本（包括有标记样本和进行了标记指派的未标记样本）上间隔最大化的划分超平面。
   • 一旦划分超平面得以确定，未标记样本的最终标记指派就是其预测结果。

3. 给定标记样本集 ，和未标记样本集 ，其中 。

   TSVM学习的目标是：为 中的样本给出预测标记 使得：

   其中：

   • 确定了一个划分超平面。

   • 为松弛向量 ：

     • 对应于有标记样本。
     • 对应于未标记样本。

4. TSVM 采用局部搜索来迭代地寻求上式的近似解。具体来说：

   • 首先利用有标记样本学得一个SVM：即忽略上式中关于 与 的项以及约束。

   • 然后利用这个SVM 对未标记数据进行标记指派：即将SVM预测的结果作为伪标记pseudo-label赋予未标记样本。

     • 此时 得到求解，将其代入上式即可得到一个标准SVM问题。于是求解可以解出新的划分超平面和松弛向量。
     • 注意到此时的未标记样本的伪标记很可能不准确，因此 要设置为比 小的值，使得有标记样本所起的作用更大。

   • 接下来， TSVM 找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，再重新基于上式求解出更新后的划分超平面和松弛向量。

   • 再接下来，TSVM 再找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，再重新基于上式求解出更新后的划分超平面和松弛向量。

   • …

   • 标记指派调整完成后，逐渐增大 以提高未标记样本对优化目标的影响，进行下一轮标记指派调整，直至 达到指定阈值为止。

5. TSVM算法：

   • 算法输入：

     • 有标记样本集 ，其中
     • 未标记样本集 ，其中
     • 折中参数

   • 算法输出： 未标记样本的预测结果

6. 在对未标记样本进行指标指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类。这将对SVM的训练造成困扰。

   为了减轻类别不平衡性造成的不利影响，可对上述算法稍加改进：将优化目标中的 项拆分为 和 两项，分别对应基于伪标记而当作正、反例使用的未标记样本。并在初始化时，令：

   

   其中 和 分别为基于伪标记而当作反、正例而使用的未标记样本数。

2.2 性质

2. 在 TSVM 算法中，寻找标记指派可能出错的每一对未标记样本进行调整，这是一个涉及巨大计算开销的大规模优化问题。

   • 在论文《Large Scale Transductive SVMs》 中，约 2000 个未标记样本，原始TVSM 迭代收敛大约需要 1个小时。
   • 半监督SVM研究的一个重点是如何设计出高效的优化求解策略。由此发展成很多方法，如基于图核函数梯度下降的LDS算法，基于标记均值估计的算法等。