二、半监督 SVM

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

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

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

    二、半监督 SVM - 图1

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

2.1 TVSM

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

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

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

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

  3. 给定标记样本集 二、半监督 SVM - 图2 ，和未标记样本集 二、半监督 SVM - 图3，其中 二、半监督 SVM - 图4 。

    TSVM学习的目标是：为 二、半监督 SVM - 图5 中的样本给出预测标记 二、半监督 SVM - 图6 使得：

    二、半监督 SVM - 图7

    其中：

    • 二、半监督 SVM - 图8 确定了一个划分超平面。

    • 二、半监督 SVM - 图9 为松弛向量 ：

      • 二、半监督 SVM - 图10 对应于有标记样本。
      • 二、半监督 SVM - 图11 对应于未标记样本。
    • 二、半监督 SVM - 图12 是由用户指定的用于平衡模型复杂度、有标记样本、未标记样本重要程度的折中参数。

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

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

    • 首先利用有标记样本学得一个SVM：即忽略上式中关于 二、半监督 SVM - 图13 与 二、半监督 SVM - 图14 的项以及约束。

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

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

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

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

    • …

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

  5. TSVM算法：

    • 算法输入：

      • 有标记样本集 二、半监督 SVM - 图20 ，其中 二、半监督 SVM - 图21
      • 未标记样本集 二、半监督 SVM - 图22 ，其中 二、半监督 SVM - 图23
      • 折中参数 二、半监督 SVM - 图24

    • 算法输出： 未标记样本的预测结果 二、半监督 SVM - 图25

    • 算法步骤：

      • 用 二、半监督 SVM - 图26 训练一个 SVM_l

      • 用 SVM_l 对 二、半监督 SVM - 图27 中样本进行预测，得到 二、半监督 SVM - 图28

      • 初始化 二、半监督 SVM - 图29 ，其中 二、半监督 SVM - 图30

      • 迭代，迭代终止条件为 二、半监督 SVM - 图31 。迭代过程为：

        • 基于 二、半监督 SVM - 图32 ，求解下式，得到 二、半监督 SVM - 图33：

          二、半监督 SVM - 图34

        • 对于所有的一对标记指派为异类且很可能发生错误的未标记样本（其条件为：二、半监督 SVM - 图35），执行下列操作：

          • 交换二者的标记：二、半监督 SVM - 图36 。

            该操作等价于交换标记，因为 二、半监督 SVM - 图37 异号，且其取值为 -1 或者 +1。

          • 基于 二、半监督 SVM - 图38，重新求解得到得到 二、半监督 SVM - 图39 。

        • 更新 二、半监督 SVM - 图40 。这里采用简单的倍乘，也可以采用其它增长函数。

      • 迭代终止时，输出 二、半监督 SVM - 图41

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

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

    二、半监督 SVM - 图45

    其中 二、半监督 SVM - 图46 和二、半监督 SVM - 图47 分别为基于伪标记而当作反、正例而使用的未标记样本数。

2.2 性质

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

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

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