半监督支持向量机（S3VMs）

　　今天我们主要介绍SVM分类器以及它的半监督形式S3VM，到这里我们关于半监督学习基础算法的介绍暂时告一段落了。之后小编还会以论文分享的形式介绍一些比较新的半监督学习算法。让我们开始今天的学习吧~

引入

　　支持向量机（SVM）相信大家并不陌生吧？但是如果数据集中有大量无标签数据（如下图b），那么决策边界应该如何去确定呢？仅使用有标签数据学得的决策边界（如下图a）将穿过密集的无标签数据，如果我们假定两个类是完全分开的，那么该决策边界并不是我们想要的，我们希望的决策边界是下图（b）中的黑色实线。

　　新的决策边界可以很好地将无标签数据分成两类，而且也正确地分类了有标签数据（虽然它到最近的有标签数据的距离比SVM小）。

支持向量机SVM

　　首先我们来讨论SVMs，为我们接下来要介绍的S3VMs算法做铺垫。为了简单起见，我们讨论二分类问题，即y{-1,1}，特征空间为并定义决策边界如下其中w是决定决策边界方向和尺度的参数向量，b是偏移量。举个例子，，b=-1，决策边界就如下图蓝色线所示，决策边界总是垂直于w向量。

　　我们的模型为，决策边界是f(x)=0，我们通过sign(f(x))来预测x的标签，我们感兴趣的是实例x到决策边界的距离，该距离的绝对值为，比如原点x=(0,0)到决策边界的距离为，如上图中的绿色实线。我们定义有标签实例到决策边界的有符号距离为。假设训练数据是线性可分的（至少存在一条线性决策边界正确分类所有的标签数据）。有符号的决策边距是决策边界到距离它最近的有标签数据的距离：，如果一个决策边界能分离有标签训练样本，几何边界是正的，我们通过寻找最大几何边距来发现决策边界：，这个式子很难直接优化，所以我们将它重写为等价形式。首先我们注意到参数（w,b）可以任意缩放为（cw, cb）,所以我们要求最接近决策边界的实例满足：，接下来，目标方程可以重写为约束优化问题的形式：，而且，最大化1/||w||相当于最小化||w||的平方：

 　　到目前为止，我们都是基于训练样本是线性可分的，现在我们放宽这个条件，那么上述目标方程不再满足。我们要对约束条件进行松弛使得在某些实例上，同时对这些松弛进行惩罚，重写目标方程为：

 　　然而，将目标函数转换成一个正则化的风险最小化的形式是有必要的（这关系到我们将其拓展到S3VMs）。考虑这样一个优化问题：

 　　很容易可以看出当z<=0时，目标函数值为0，否则为z，所以可以简写为

 　　注意（*）中的约束条件可以重写为，利用刚才的结论，我们将（*）重写为

 　　其中第一项代表的是hinge loss损失函数，第二项是正则项。

　　我们这里不再深入讨论SVMs的对偶形式或者核技巧（将特征映射到更高维度的空间来解决非线性问题），虽然这两个问题是SVMs的关键，但不是我们要介绍的S3VMs的重点（当然也可以将核技巧直接应用到S3VMs上），感兴趣的同学可以去看相关的论文。

半监督支持向量机（S3VMs）

　　在上文中我们提到用hinge loss来使有标签数据分类尽可能正确，但是如果存在无标签数据呢？没有标签的话就不能知道是否分类正确，就更别提惩罚了。

　　我们已经学习出来一个标签预测器sign(f(x))，对于无标签样本，它的预测标签为，我们假定该预测值就是x的标签，那么就可以在x上应用hinge损失函数了

 　　我们称它为hat loss。

　　由于我们标签就是用f(x)生成的，无标签样本总是能被正确分类，然而hat loss 仍然可以惩罚一定的无标签样本。从式子中可以看出，hat