1.svm定义
SVM从线性可分情况下的最优分类面发展而来 。最优分类面就是要求分类线不但能将两类正确分开( 训练错误率为0)，且使分类间隔最大。SVM 考虑寻找一个满足分类要求的超平面，并且使训练集中的点距离分类面尽可能的远，也就是寻找一个分类面 使它两侧的空白区域(Margin) 最大 。如下图所示：
左边是一个分类超平面，但是不是最佳的，显然右边的分类超平面是最佳的，我们的目标就是要找到最佳的分类超平面。
2.间隔最大化
先给出一般的线性分类超平面的定义：
样本集{xn,tn},n=1,2,...,N,xn∈Rd,tn∈{−1,1}
分类器：y(x)=wTx+b
tn={1,−1,y(xn)>0y(xn)<0
也就是如果预测值大于0则为类别1，预测值小于0则为类别-1。总之，有:
tny(xn)>0
样本集任意一点xn到分类面( 满足 tny(xn)>0) 的距离为：
tny(xn)||w||=tn(wTxn+b)||w||
这类似于点到直线的距离的求发。假设有一条直线:
x1+x2+2=0,我们求点
(xi,xj) 到该直线的举例就是
xi+xj+2x21+x22√，只是上面的分母它用了一个向量的形式来表示所有的变量
(w1,w2,...,wm)。
而SVM要找的分类平面是，使得离该平面最近的点（边界点）离该平面的距离尽可能的远，用数学公式表示就是:
argmaxw,b{1||w||minn[tn(wTx+b)]}
里面表示距离分类面最近的点的距离，外面表示使得该距离最大。因为距离平面最近的点对应的
tn(wT+b) 必定为某个正数
k，我们假设该值就是1，并不会影响参数
w,b 的取值。例如点
(2,1) 在
2x1+3x2−4 中的取值为3，要使得该值为1，只需要相应的
w,b 同时缩小为原来的
13,即变为
23x1+x2−43，但是表示的仍然是同一条直线。所以原问题就转化为:
argmaxw,b{1||w||}
并且上面假设了离分类面最近的点的距离为1，那么其他点对应的
tn(wT+b)>1。
因为问题转化为最大化||w||−1 ,等价于最小化12||w||2,则上述问题可以用下面的数学表达式来描述：
argminw,b12||w||2,s.t.tn(wTx+b)≥1
解这种含不等式约束的极值点要用拉格朗日乘子法，构造拉格朗日函数如下：
L(w,b,a)=12||w||2−∑n=1Nan(tn(wTx+b)−1),an>0
其中
an 是拉格朗日乘子，是一个正数。
对于上述的
L(w,b,a)，对它的最大值进行讨论。
1.当
tn(wTx+b)>=1时:
显然有
(wTx+b)−1≥0，又
an是一个正数，所以
∑n=1Nan(tn(wTx+b)−1)≥0
所以:
L(w,b,a)=12||w||2−∑n=1Nan(tn(wTx+b)−1)=12||w||2−非负数
所以，很显然这种情况下
maxL(w,b,a)=12||w||2
2.当tn(wTx+b)<1时:
显然有(wTx+b)−1≥0，又an是一个正数,所以该累加项趋近于负无穷，即∑Nn=1an(tn(wTx+b)−1)趋于−∞，所以maxL(w,b,a) 值是趋近于+∞
总结之后就是:
maxL(w,b,a)={12||w||2,+∞,tn(wTx+b)>=1tn(wTx+b)<1
又前面假设中已经有任意点都满足
tn(wTx+b)>=1，所以
maxL(w,b,a)=
12||w||2。
然后我们再回到原始的优化问题：
argminw,b12||w||2,s.t.tn(wTx+b)≥1
因为
maxL(w,b,a)=
12||w||2，用
L(w,b,a)替换
w，所以该问题就等价于:
argminw,bmaxaL(w,b,a),s.t.tn(wTx+b)≥1
但是这样不容易求解，我们需要考虑它的对偶问题。
3.拉格朗日对偶性
求下面极值：
minwf(w)
在等式约束下的极值问题
s.t.hi(w)=1,...,l L(w,β)=f(w)+∑i=1lβihi(w)
在不等式约束下的极值问题
s.t.gi(w)≤0,i=1,...,k;hi(w)=1,...,l L(w,α,β)=f(w)+∑i=1kαigi(w)+∑j=1lβjhj(w)
定义θP(w)=maxα,βL(w,α,β),s.t.αi≥0，只有满足基本约束条件时，θP才会有最大值，基本约束条件就是上面不等式约束下的那些约束条件：
θP(w)={f(w),+∞,if w satisfies premal constraintsotherwise
原问题minwf(w) 转化为minwθP(w)=minwmaxα,βL(w,α,β)，记为p∗,直接求解不容易，需要转向另一个问题θD(w)=minwL(w,α,β),先固定α,β，然后再求拉格朗日函数关于w的最小值，之后再求θD(w)的最大值。即:
maxα,βθD(w)=maxα,βminwL(w,α,β)
该问题是原问题的对偶问题，记为
d∗，很容易推出有下面大小关系:
d∗=maxα,βminwL(w,α,β)≤minwmaxα,βL(w,α,β)=p∗
即最小值的最大取值一定要小于等于最大值的最小取值。
为了使得原问题的解和对偶问题的解相等，即p∗=d∗，必须使得它们的解(w∗,α∗,β∗)满足KKT条件，即:
∂∂wiL(w∗,α∗,β∗)=0,i=1,...,n
∂∂βiL(w∗,α∗,β∗)=0,i=1,...,l
α∗igi(w∗)=0,i=1,...,k称为KKT对偶互补条件
gi(w∗)≤0,i=1,...,k
a∗≥0,i=1,...,k
如果(w∗,α∗,β∗)都满足KKT条件，那么它们就是原问题和对偶问题的解。
补充条件隐含如果 a∗>0，那么gi(w∗)=0， 即w处于可行域的边界上，是起作用的(Active) 约束 ，而位于可行域内部的点都是不起作用的约束，其 a∗=0。
4.最优间隔分类器
接到第2小节，该优化问题：
argminw,bmaxaL(w,b,a),s.t.tn(wTx+b)≥1
转化为对偶问题就是:
argmaxaminw,bL(w,b,a),s.t.tn(wTx+b)≥1
该对偶问题表示，先求L(w,b,a)关于参数w,b的最小值，然后再求关于参数a的最大值。关于参数w,b的最小值，直接求导，找到极值点。
L(w,b,a)=12||w||2−∑Nn=1an(tn(wTx+b)−1),an≥0
∂∂wL(w,b,a)=0⇒w−∑n=1Nantnxn=0
∂∂bL(w,b,a)=0⇒∑n=1Nantn=0
将
w=∑Nn=1antnxn和
∑Nn=1antn=0带入原
L(w,b,a)，可以求得
L(w,b,a)=∑n=1Nan−12∑i=1N∑j=1NaiajtitjxTixj
s.t.ai≥0,∑Ni=1aiti=0
推导过程为:
注意变换过的L(w,b,a)式子中，xi表示第i个样本，是已知的；ti表示第i个样本对应的类别值，为1或-1，也是已知的；所以该式子中仅有一个参数a 是未知的。所以进一步的优化就是找到某一组a，让L(w,b,a) 取得最大值，而只要找到一组a，它能够使得所有的样本都满足KKT条件时，便能够取得最大值。具体的实现算法参考SMO算法。
