【概述】
半监督支持向量机（Semi-Supervised Support Vector Machine，S3VM）是支持向量机在半监督学习上的推广，在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM 试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面
如图下图所示，这里的基本假设是低密度分隔（Low-density Separation），显然，这是聚类假设在考虑线性超平面划分后的推广
在一系列半监督支持向量机中，最著名的是直推支持向量机（Transductive Support Vector Machine，TSVM），与标准 SVM 一样，TSVM 也是针对二分类问题的学习方法
【TSVM】
模型
TSVM 试图考虑对未标记样本进行各种可能的标记指派（Label assignment），即尝试将每个未标记样本分别作为正例或反例，然后在所有这些结果中，寻求一个在所有样本上间隔最大化的划分超平面，一旦划分超平面得以确定,未标记样本的最终标记指派就是其预测结果
对于给定有标记样本集 $D_l=\{(\mathbf{x}_1,y_1),(\mathbf{x}_2,y_2),\cdots,(\mathbf{x}_l,y_l)\}$ 和未标记样本集 $D_u=\{\mathbf{x}_{l+1},\mathbf{x}_{l+2},\cdots,\mathbf{x}_{l+u}\}$，其中 $l$ 和 $u$ 满足 $l\ll u,l+u=n$，标记 $y_i\in \{-1,1\}$，TSVM 的学习目标是为 $D_u$ 中的样本给出预测标记 $\hat{\mathbf{y}}=(\hat{y}_{l+1},\hat{y}_{l+2},\cdots,\hat{y}_{l+u}),\hat{y}_i\in\{-1,1\}$，使得：
其中，$(\mathbf{w},b)$ 确定了一个划分超平面，$\boldsymbol{\xi}$ 为松弛向量，$\xi_i,i=1,2,\cdots,l$ 对应于有标记样本，$\xi_i,i=l+1,l+2,\cdots,n$ 对应于未标记样本，$C_l$ 与 $C_u$ 是用于平衡模型复杂度、有标记样本与无标记样本重要程度的折中参数
显然，尝试未标记样本的各种标记指派是一个穷举过程，当且仅当未标记样本很少时才有可能直接求解，因此必须要考虑更高效的优化策略
学习方法
TSVM 采用局部搜索来迭代地寻找上式的近似解
首先，利用有标记样本学得一个 SVM，即忽略上式中关于 $D_u$ 与 $\hat{\mathbf{y}}$ 的项及约束
然后，利用这个 SVM 对未标记数据进行标记指派，即将 SVM 预测的结果作为伪标记（Pseudo-label），赋予给未标记样本
此时，$\hat{\mathbf{y}}$ 变为已知，将其带回上式中，即可得到一个标准 SVM 问题，于是可求解出新的划分超平面和松弛向量
需要注意的是，此时未标记样本的伪标记很可能不准确，因此 $C_u$ 要设置为比 $C_l$ 更小的值，使有标记样本所起作用更大
进一步，TSVM 找出两个标记指派为异类且很可能发生错误的未标记样本，交换它们的标记，再重新基于上式求解出更新后的划分超平面和松弛向量，再找出两个标记指派为异类且很可能发生错误的未标记样本，逐渐增大 $C_u$ 以提高未标记样本对优化目标的影响，重复这个过程，直到 $C_u=C_l$ 为止
此时，求解得到的 SVM 不仅给未标记样本提供了标记，还能对训练过程中未见的示例进行预测
上述的算法流程如下图所示
类别不平衡问题
在对未标记样本进行标记指派及调整的过程中，有可能出现类别不平衡问题，即某类的样本远多于另一类，这将对SVM 的训练造成困扰
为了减轻类别不平衡性所造成的不利影响，可对上述的学习过程进行改进，即将优化目标中的 $C_u$ 项拆为 $C_u^+$ 与 $C_u^-$ 两项，分别对应于基于伪标记而当作正样本、负样本使用的未标记样本，并在初始化时，令：
其中，$u_+$ 与 $u_-$ 是基于伪标记而当作正样本、负样本使用的未标记样本数
