Support Vector Machine

在还没有coursera的时候, Andrew Ng有个openclass的网站，当时我就学了他的课程。当时写了个包叫mlass，本意是ml + class，后来发现这包叫ml + ass，我真的不是故意的。好多年了，都没再去动过，这包应该是不能装了。

支持向量机(Support Vector Machines, SVM)最初由Vladimir Vapnik于1997年提出，SVM最简单的形式就是找出一下区分界限（descision boundary），也称之为超平面(hyperplane)，使得离它最近的点（称之为support vectors）与之间隔最大。

这和logistic regression有些相似，区别在于logistic regression要求所有的点尽可能地远离中间那条线，而SVM是要求最接近中间线的点尽可能地远离中间线。也就是说SVM的主要目标是区分那些最难区分的点。

SVM对于hyperplane的定义，在形式上和logistic regression一样,logistic
regression的decision boundary由

确定,SVM则用

表示,其中b相当于logistic regression中的，从形式上看，两者并无区别，当然如前面所说，两者的目标不一样，logistic regression着眼于全局，SVM着眼于support vectors。有监督算法都有label变量y，logistic regression取值是{0,1}，而SVM为了计算距离方便，取值为{-1,1}。

那么SVM的问题就变成为，确定参数w和b，以满足：


对于上图中最简单的例子，中间线可以由Ax+By+c=0表示，图上一个

的点到中间线的距离为

对于更高维的空间，点到hyperplane上的距离也是一样计算，定义为：

要距离最大，也就是求||w||的最小值。 那么问题就相当于在给定条件g(x):

下，求f(x): 的最大值。

这是一个限定条件下的优化问题，可以通过Lagrange multiplier解决。
这里，拉格朗日公式为：

通过对拉格朗日公式的分析，问题变为： 给定

的最大值。

对于alpha值，通常训练算法还通过C参数进行限制

，这个参数相当于logistic regression里的lambda参数，对outlier数据点的penalty。

通过Sequential Minimal Optimization（SMO）算法，可以快速地给出解。
对于无法进行线性区分的数据，需要进行transformation，把数据映射到另一个空间里，使之可以线性区分，这就是kernel function所干的事情。
参考了《machine learning in action》和ml-class的材料后，我在mlass包里实现了简化版本的SMO算法。

require(mlass) data(ex6data2) model <- svmTrain(X,y, C=1, kernelFunction="gaussianKernel") plot(model, X,y, type="nonlinear")