SVM

What

SVM即Support Vector Machines——支持向量机，是一种分类器，属于监督学习的范畴。

Q: 给定训练样本{(x1,y1),....,(xi,yi)},yi∈{−1,+1}$\{({\mathit{x}}_1,y_1),....,({\mathit{x}}_i,y_i)\},y_i\in \{-1,+1\}$，找到一个划分超平面，将不同类别样本分开。
(图:wiki)

对于上述问题，任意二分线性分类器都可以分类。作为一个二分线性分类器，SVM与之不同的是其特殊的划分超平面：要求间隔(margin)最大。如图所示，也就是图中两条虚线之间的间隔最大，划分超平面处于间隔的中间。仔细观察可知，该间隔只与距离超平面最近的几个点有关，而这几个点就被称为Support Vector，这也就是SVM的名字来源。

SVM

这个超平面可以表示为

则SVM分类器可表示为

如果wTx+b≥0,则g(wTx+b)=1${\mathit{w}}^T\mathit{x}+b\ge 0,则g({\mathit{w}}^T\mathit{x}+b)=1$ ，反之g(wTx+b)=−1$g({\mathit{w}}^T\mathit{x}+b)=-1$

函数间隔(functional margin)

对任意的样本(xi,yi)$({\mathit{x}}_i,y_i)$，定义函数间隔为

显而易见的是，当分类正确时，yi$y_i$和wTxi+b${\mathit{w}}^T{\mathit{x}}_i+b$是同号的且距离超平面越远值越大，由于y∈{1,−1}$y\in \{1,-1\}$，则γ^i${\hat{\gamma }}_i$的值为|wTxi+b|$|{\mathit{w}}^T{\mathit{x}}_i+b|$。
那么在真个训练样本上，我们定义函数间隔为所有训练样本中最小的一个:

函数间隔可以表示分类是否正确且可以衡量分类的正确程度，但是，当我们同时缩放x,b$\mathit{x},b$时并不会改变超平面，但是函数间隔的值会通样进行缩放。为了避免对求解的影响，接下来引入几何间隔。

几何间隔(geometric margin)

给任意一个样本A(xi,yi${\mathit{x}}_i,y_i$)，则其到超平面的垂点B为xi−γiw||w||${\mathit{x}}_i-{\gamma }_i\frac{\mathit{w}}{||\mathit{w}||}$，代入超平面解出几何间隔γ^i${\hat{\gamma }}_i$

求解为：

几何间隔定义为

特别的，当||w||=1$||w||=1$时，几何间隔和函数间隔相等。
则全局几何间隔为

基本型

由于约束中的||w||=1$||w||=1$无法通过优化算法进行求解，所以需要去掉该项，转化为

为了约束w和b的变化，将γ^$\hat{\gamma }$设为一个固定值，

最终，SVM的基本型为

待完善

参考

Andrew Ng 在Stanford时的课堂讲义