Question

1. 半监督支持向量机Semi-Supervised Support Vector Machine：S3VM 是支持向量机在半监督学习上的推广。

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

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

   

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

2.1 TVSM

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

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

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

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

3. 给定标记样本集 $ MathJax-Element-124 $ ，和未标记样本集 $ MathJax-Element-236 $ ，其中 $ MathJax-Element-109 $ 。

   TSVM学习的目标是：为 $ MathJax-Element-473 $ 中的样本给出预测标记 $ MathJax-Element-111 $ 使得：

   $ \min_{\mathbf{\vec w},b,\hat{\mathbf{\vec y}},\vec\xi} \frac 12 ||\mathbf{\vec w}||_2^{2}+C_l\sum_{i=1}^{l}\xi_i+C_u\sum_{i=l+1}^{N}\xi_i\\ s.t.\; y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=1,2,\cdots,l\\ \hat y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=l+1,l+2,\cdots,N\\ \xi_i \ge 0,\quad i=1,2,\cdots,N $

   其中：

   • $ MathJax-Element-112 $ 确定了一个划分超平面。

   • $ MathJax-Element-113 $ 为松弛向量 ：

     • $ MathJax-Element-114 $ 对应于有标记样本。
     • $ MathJax-Element-115 $ 对应于未标记样本。

   • $ MathJax-Element-128 $ 是由用户指定的用于平衡模型复杂度、有标记样本、未标记样本重要程度的折中参数。

4. TSVM尝试未标记样本的各种标记指派是一个穷举过程，仅当未标记样本很少时才有可能直接求解。因此通常情况下，必须考虑更高效的优化策略。

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

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

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

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

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

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

   • ...

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

5. TSVM算法：

   • 算法输入：

     • 有标记样本集 $ MathJax-Element-124 $ ，其中 $ MathJax-Element-125 $
     • 未标记样本集 $ MathJax-Element-236 $ ，其中 $ MathJax-Element-127 $
     • 折中参数 $ MathJax-Element-128 $

   • 算法输出： 未标记样本的预测结果 $ MathJax-Element-129 $

   • 算法步骤：

     • 用 $ MathJax-Element-428 $ 训练一个 SVM_l

     • 用 SVM_l 对 $ MathJax-Element-473 $ 中样本进行预测，得到 $ MathJax-Element-474 $

     • 初始化 $ MathJax-Element-133 $ ，其中 $ MathJax-Element-134 $

     • 迭代，迭代终止条件为 $ MathJax-Element-135 $ 。迭代过程为：

       • 基于 $ MathJax-Element-141 $ ，求解下式，得到 $ MathJax-Element-142 $ ：

         $ \min_{\mathbf{\vec w},b,\hat{\mathbf{\vec y}},\vec\xi} \frac 12 ||\mathbf{\vec w}||_2^{2}+C_l\sum_{i=1}^{l}\xi_i+\tilde C_u\sum_{i=l+1}^{N}\xi_i\\ s.t.\; y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=1,2,\cdots,l\\ \hat y_i(\mathbf{\vec w}^{T}\mathbf{\vec x}_i+b) \ge 1-\xi_i,\quad i=l+1,l+2,\cdots,N\\ \xi_i \ge 0,\quad i=1,2,\cdots,N $

       • 对于所有的一对标记指派为异类且很可能发生错误的未标记样本（其条件为： $ MathJax-Element-138 $ ），执行下列操作：

         • 交换二者的标记： $ MathJax-Element-139 $ 。

           该操作等价于交换标记，因为 $ MathJax-Element-140 $ 异号，且其取值为 -1 或者 +1。

         • 基于 $ MathJax-Element-141 $ ，重新求解得到得到 $ MathJax-Element-142 $ 。

       • 更新 $ MathJax-Element-143 $ 。这里采用简单的倍乘，也可以采用其它增长函数。

     • 迭代终止时，输出 $ MathJax-Element-474 $

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

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

   $ C_u^{+}=\frac{u_-}{u_+}C_u^{- } $

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

2.2 性质

1. TSVM 最终得到的SVM 不仅可以给未标记样本提供了标记，还能对训练过程中未见的样本进行预测。

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

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