14-Support Vector Machine

在线性可分的例子中， 我们也是希望margin越大越好， 它能给予更大的泛化能力

接下来就是寻找w的过程了。 我们做了两个预先的假定：就是对w进行normalize， 使得最靠近超平面的w具有1的性质(其实1的表达应该统一成2的表达比较好）， 这个性质我们后面会用到； 以及还原w， 将bias抽离出来， 这个也是为了方便后面的计算。

计算margin上面的点到超平面的距离。 其中可以证明的是w就是法向量，因此计算margin上面的点对w的projection就是点到平面的距离了。 在这里有必要对w进行单位化， 经过推导可知要优化的就是1/||w||。

问题的转化：maximize转化为minimize。 其中观察到绝对值的符号可以通过乘以y的方式来去掉， 并且将严格等于1转化为≥。

solution就是拉格朗日乘子法。对w， b求导并重新代入可得L只跟alpha相关， 消去的过程注意右边的部分只有b的那个部分可以直接去掉。

quadratic programming为我们提供了solution的方案， 一旦我们得到alpha， 代入即可求解w， 知道了w也可以从其中一个support vector代入求得b。根据之前的定义， margin上面的点满足|w^Tx+b|=1， 其对应的alpha>0， 而 并且我们注意到只有alpha大于0的项对应的x才是support vector， 它们一起构成了w。

非线性变换。SVM的对偶问题可以引出一个很好的因子x^Tx， 这为以后的核函数做了铺垫， 因为我们指希望得到x向量乘积之后得到的scalar。另外衡量SVM的泛化能力的一个指标就是support vector的数量。