《Introduction of Semi-supervised learning》总结5

第六章：半监督学习支持向量机

介绍之前先介绍一下点到直线的距离公式，点 $(x_{0},y_{0})$ 到直线的距离为：

$d=frac{left| Ax_{0}+By_{0}+C ight|}{sqrt{A^{2}+B^{2}}}$

decision boundary(决策边界)是一些列直线的集合： $left{ mathbf x| mathbf w^{T}mathbf x+b=0 ight}$ ;

设 $f(mathbf x)=mathbf w^{T}mathbf x+b$ ,那么决策边界就可以用来定义了。同时的标签也可以用含有的式子来定义： ,那么instance 和决策边界之间的距离可以定义为： $frac{left| f(mathbf x) ight|}{left| mathbf w ight|}$ .

因为对于任意一个instance ,在决策边界的作用下，当时，其标签为正，当，则标签为负，则上式的instance 和决策边界之间的距离可以重新写为： $frac{ yf(mathbf x) }{left| mathbf w ight|}$ .当然，不要忘了，前提条件是整个set是linear separable(线性可分)的。

下面引入了另一个概念signed geometric margin：它是被标签过的数据中到决策边界最短的那个距离： $mathop{min}_{i=1}^{l} y_{i}f(mathbf x_{i})/ | mathbf w |$

如果决策边界将将所有训练数据都分类开来，那么这个geometric margin就是正值。接下来找一个让geometric margin最大的决策边界：

$mathop{max}_{mathbf w ,b}mathop{min}_{i=1}^{l} y_{i}f(mathbf x_{i})/ | mathbf w |$ ，(6.4)

我们就达到目标了:找到一个最鲁棒的决策边界。

总结一下这个过程：分两步走：第一步：不断的画出一条一条的decision boundary ，计算它到离它最近的点的signed geometric margin。如果是正的，留下，负的去除(即能够正确分类数据的决策边界)。然后我们就得出一系列能够将数据正确分类的decision boundary 。

第二步：在这些剩下的decision boundary 中，找到signed geometric margin最大的那一条。

通过6.4式得到的决策边界，其通过scale一下，就又是一条线，所以必须要对6.4式加上限制条件，我们规定： $mathop{min}_{i=1}^{l} y_{i}f(mathbf x_{i})=1$ ，这一条件表明， $y_{i}f(mathbf x_{i})=y_{i}(mathbf w^{T}mathbf x_{i}+b)geq1$ ,所以整个式子又可以写成下式： $mathop{max}_{mathbf w ,b} quadfrac{1}{left| mathbf w ight|} \ subject quad to quad y_{i}(mathbf w^{T}mathbf x_{i}+b)geq1,i=1...l.$

又可以写成：

$mathop{min}_{mathbf w ,b} quad{left| mathbf w ight|}^{2} \ subject quad to quad y_{i}(mathbf w^{T}mathbf x_{i}+b)geq1,i=1...l.$

然而，有一点需要注意，就是每一个instance都必须满足这个条件，但有些点(比如给了错误的标签的原因)是不可能满足这个条件的，我们就要给这个公式一个relaxation。我们引入slack variable的概念，每一个instance一个relaxation， $xi_{i}geq 0,i=1...l$ ,上式的目标函数可以写成： $mathop{min}_{mathbf w ,b,xi} quadsum_{i=1}^{l}xi_{i}+lambda{left| mathbf w ight|}^{2} \ subject quad to quad y_{i}(mathbf w^{T}mathbf x_{i}+b)geq1-xi_{i},i=1...l. \ xi_{i}geq0.$ （6.9）其中 $sum_{i=1}^{l}xi_{i}$ 是所有relaxation的总和。

下面举例子说明一个即将用到的解决上式的方法。

$mathop{min}_{mathbf xi} quadxi \ subject quad to quad xigeq z\ quad quad quad quadquadquadxigeq0$

上式等于 ,则 $y_{i}(mathbf w^{T}mathbf x_{i}+b)geq1-xi_{i}$ 可以写为 $xi_{i} geq 1-y_{i}(mathbf w^{T}mathbf x_{i}+b)$ ，那么式6.9可以写为： $mathop{min}_{mathbf w ,b}sum_{i=1}^{l}max(1-y_{i}(mathbf w^{T}mathbf x_{i}+b),0)+lambdaleft| x ight|^{2}$ ,第一项是损失函数，第二项是正则化项。第一项也叫hinge loss（折页损失函数），此函数如下图所示：

我们知道，正确分类的instance有，那relax的instance就小于，从图中可以看出越小，其惩罚越重。

6.2 SEMI-SUPERVISED SUPPORT VECTOR MACHINES（S3VMs）

现在考虑怎么将无标签的数据加入到SVM里。给无标签的数据以推定标签：一个instance 的推定标签为 ,那么：

$c(mathbf x,hat{y},f(mathbf x))=max(1-hat y(mathbf w^{T}mathbf x+b),0)\ quad quad quad quad quad quad quad quad quad quad quad =max(1-sign(mathbf w^{T}mathbf x+b)(mathbf w^{T}mathbf x+b),0)\ quad quad quad quad quad =max(1-left| mathbf w^{T}mathbf x+b) ight|,0)$ ,（6.15）

这里使用了公式。6.15式的最后一行也叫做hat loss。如下图所示：

图中可以看出，在margin 之外是没有惩罚的(分类正确)，在之内的(分类不正确)，就有惩罚了。

那么整个S3VM的目标函数可以写成下式：

但是这样得出来的解是不平衡的(imbalanced)，即无标签的instance大部分会被分类到一个类中。那就加入均衡的限制： $frac{1}{u}sum_{j=l+1}^{l+u}{f(mathbf x_{j})}=frac{1}{l}sum_{i=1}^{l}{f(mathbf y_{i})}$ ，将无标签和有标签的数据的量平衡一下。