现实生活中，平面有两个坐标，平面空间可以表示为
Φ(x,y)=[ab][xy]
;三维空间表示为
Φ(x,y)=[abc]⎡⎣⎢⎢xyz⎤⎦⎥⎥
。我们需要处理的信息包含多个特征，即包含更多的维度，我们可以建立抽象的超空间来放置这些信息。其中超平面定义为
wTx+b=0
。
x
是信息的特征向量。
SVM中文叫支持向量机。设想超空间中有两个可分离的集合，我们可以用无限个超平面来分离这两个集合，但其中支持平面是唯一，即支持平面刚好在两个集合之间的中心。SVM便是找到这个支持平面的算法。
为了方便计算，我们将两个可分离集合中距离最近的两个元素向量定义为支持向量，将分类元素的判别值
g(x)=wTx+b
分别归一化为1和-1。解析几何中，三维点到三维平面的距离的公式为
r=Ax+By+Cz+DA2+B2+C2‾‾‾‾‾‾‾‾‾‾‾‾‾√
，推广到超平面就是
r=g(x)||w||
。为了最大可能地分离两个集合，我们计算得到此时支持向量的距离为
sum(r0)=1/||w||−(−1)/||w||=2/||w||
，因此有
r∝1/||w||→argmin(||w||)
。我们要在当前限制条件下，尽量缩小w的模值。
从上述结论中，我们得到一个最优化问题。对于支持向量有
argminΦ(w)=1/2wTw,subject to dig(xi)=1
，非支持向量有
argminΦ(w)=1/2wTw,subject to dig(xi)>1
。因此有
argminΦ(w)=1/2wTw,subject to dig(xi)≥1
，其中
di
是判别结果，取值为1和-1。
但是实际情况中，两个待区分的集合，边界可能是模糊的，总有几个偏离点，因此要引入松弛变量来弹性控制分类力度。上述式子写成
argminΦ(w)=12wTw+C∑ξi,subject to dig(xi)−(1−ξi)≥0ξi≥0
接下来使用拉格朗日乘数法进行对偶问题转换，引入非负辅助变量
α,β
。为了取得最小值，我们求取导数来找到极值：
J=12wTw+C∑ξi−∑αi[dig(xi)−(1−ξi)]−∑βiξi,αi≥0,βi≥0∂J∂w=w−∑αidixi=0→w=∑αidixi∂J∂b=∑αidi=0∂J∂ξi=C−αi−βi=0→C=αi+βi,αi≤C
代回J函数中有
J=12∑i∑jαiαjdidjxTixj+∑i(αi+βi)ξi−∑i∑jαiαjdidjxTixj−b∑iαidi+∑iαi−∑i(αi+βi)ξi=∑iαi−12∑i∑jαiαjdidjxTixjsubject to ∑αidi=0,0≤αi≤C
这里看到，
ξ
和
β
被消去了，只剩下
α,d,x
，跟不考虑松弛变量情况下的对偶问题是差不多的，区别只在于
α
的取值范围。我可以调整
α
的取值范围，来控制SVM的松弛程度。
引入核方法也比较简单，令
k(x)
为核函数，有
g(k(xi))=wTk(xi)+b
，那么
∂J∂w=w−∑iαidik(xi)=0J=∑iαi−12∑i∑jαiαjdidjk(xi)Tk(xj)=∑iαi−12∑i∑jαiαjdidjK(xi,xj)subject to ∑αidi=0,0≤αi≤C
一般使用的核函数有
- 多项式核
(xixj+1)p
- 径向基核
e−12σ2|xi−xj|2
- 双曲核
tanh(αxixj+β)
如何求解上述问题是个麻烦的过程，一般大家都用SMO算法来求解，还得考虑KKT条件之类的复杂的数学过程，这导致普通用户要实现算法，是非常困难且效率低下，一般需要求助于libSVM之类的库。如果要求求解速度快，对精度又有所妥协，可以参考下一篇最小二乘支持向量机（LSSVM）。
