如果我们不是固定分母，改为固定分子，作为分类模型有没有改进呢？

　　　　这些问题在我们引入SVM后会详细解释。

2. 函数间隔与几何间隔

　　　　在正式介绍SVM的模型和损失函数之前，我们还需要先了解下函数间隔和几何间隔的知识。

　　　　在分离超平面固定为wTx+b=0$w^{T}x+b=0$的时候，|wTx+b|$|w^{T}x+b|$表示点x到超平面的相对距离。通过观察wTx+b$w^{T}x+b$和y是否同号，我们判断分类是否正确，这些知识我们在感知机模型里都有讲到。这里我们引入函数间隔的概念，定义函数间隔γ′${\gamma }^{{}^{\prime }}$为：

　　　　可以看到，它就是感知机模型里面的误分类点到超平面距离的分子。对于训练集中m个样本点对应的m个函数间隔的最小值，就是整个训练集的函数间隔。

　　　　函数间隔并不能正常反应点到超平面的距离，在感知机模型里我们也提到，当分子成比例的增长时，分母也是成倍增长。为了统一度量，我们需要对法向量w$w$加上约束条件，这样我们就得到了几何间隔γ$\gamma$,定义为：

　　　　几何间隔才是点到超平面的真正距离，感知机模型里用到的距离就是几何距离。

3. 支持向量

　　　　在感知机模型中，我们可以找到多个可以分类的超平面将数据分开，并且优化时希望所有的点都被准确分类。但是实际上离超平面很远的点已经被正确分类，它对超平面的位置没有影响。我们最关心是那些离超平面很近的点，这些点很容易被误分类。如果我们可以让离超平面比较近的点尽可能的远离超平面，最大化几何间隔，那么我们的分类效果会更好一些。SVM的思想起源正起于此。

　　　　如下图所示，分离超平面为wTx+b=0$w^{T}x+b=0$，如果所有的样本不光可以被超平面分开，还和超平面保持一定的函数距离（下图函数距离为1），那么这样的分类超平面是比感知机的分类超平面优的。可以证明，这样的超平面只有一个。和超平面平行的保持一定的函数距离的这两个超平面对应的向量，我们定义为支持向量，如下图虚线所示。

　支持向量到超平面的距离为1/||w||2$1/||w|{|}_2$,两个支持向量之间的距离为2/||w||2$2/||w|{|}_2$。

4. SVM模型目标函数与优化

　　　　SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：

　　　　一般我们都取函数间隔γ′${\gamma }^{{}^{\prime }}$为1，这样我们的优化函数定义为：

　　　　也就是说，我们要在约束条件yi(wTxi+b)≥1(i=1,2,...m)$y_i(w^T{x}_i+b)\ge 1(i=1,2,...m)$下，最大化1)||w||2$\frac{1)}{||w|{|}_2}$。可以看出，这个感知机的优化方式不同，感知机是固定分母优化分子，而SVM是固定分子优化分母，同时加上了支持向量的限制。

　　　　由于1||w||2$\frac{1}{||w|{|}_2}$的最大化等同于12||w||22$\frac{1}{2}||w|{|}_2^2$的最小化。这样SVM的优化函数等价于：

　　　　由于目标函数12||w||22$\frac{1}{2}||w|{|}_2^2$是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数，这和最大熵模型原理小结中讲到了目标函数的优化方法一样。具体的，优化函数转化为：

　　　　由于引入了朗格朗日乘子，我们的优化目标变成：

　　　　和最大熵模型一样的，我们的这个优化函数满足KKT条件，也就是说，我们可以通过拉格朗日对偶将我们的优化问题转化为等价的对偶问题来求解。如果对凸优化和拉格朗日对偶不熟悉，建议阅读鲍德的《凸优化》。

　　　　也就是说，现在我们要求的是：$$\underset{{\alpha }_i\ge 0}{\underbrace{max}}\underset{w,b}{\underbrace{min}}L(w,b,\alpha )$$

　　　　从上式中，我们可以先求优化函数对于w和b$w和b$的极小值。接着再求拉格朗日乘子α的极大值。

　　　　首先我们来求L(w,b,α)$L(w,b,\alpha )$基于w和b$w和b$的极小值，即minbL(w,b,α)$\underset{w,b}{\underbrace{min}}L(w,b,\alpha )$。这个极值我们可以通过对w和b$w和b$分别求偏导数得到：

 　　　　从上两式子可以看出，我们已经求得了w和α$w和\alpha$的关系，只要我们后面接着能够求出优化函数极大化对应的α$\alpha$，就可以求出我们的w了，至于b，由于上两式已经没有b，所以最后的b可以有多个。

　　　　好了，既然我们已经求出w和α$w和\alpha$的关系，就可以带入优化函数L(w,b,α)$L(w,b,\alpha )$消去w了。

　　　　现在我们来看将w$w$替换为α$\alpha$的表达式以后的优化函数ψ(α)$\psi (\alpha )$的表达式：

　其中，(1)式到(2)式用到了范数的定义||w||22=wTw$||w|{|}_2^2=w^{T}w$, (2)式到(3)式用到了上面的w=∑i=1mαiyixi$w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$， (3)式到(4)式把和样本无关的wT$w^T$提前，(4)式到(5)式合并了同类项，(5)式到(6)式把和样本无关的b$b$提前，(6)式到(7)式继续用到w=∑i=1mαiyixi$w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$，（7）式到(8)式用到了向量的转置。由于常量的转置是其本身，所有只有向量xi$x_i$被转置，（8）式到(9)式用到了上面的∑i=1mαiyi=0$\sum _{i=1}^m{\alpha }_i{y}_i=0$，（9）式到(10)式使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…$(a+b+c+\dots )(a+b+c+\dots )=aa+ab+ac+ba+bb+bc+\dots$的乘法运算法则，（10）式到(11)式仅仅是位置的调整。

　　　　从上面可以看出，通过对w,b$w,b$极小化以后，我们的优化函数ψ(α)$\psi (\alpha )$仅仅只有α$\alpha$向量做参数。只要我们能够极大化ψ(α)$\psi (\alpha )$，就可以求出此时对应的α$\alpha$，进而求出w,b$w,b$.

　　　　对ψ(α)$\psi (\alpha )$求极大化的数学表达式如下:

　　　　可以去掉负号，即为等价的极小化问题如下：

 　　　　只要我们可以求出上式极小化时对应的α$\alpha$向量就可以求出w和b$w和b$了。具体怎么极小化上式得到对应的α$\alpha$，一般需要用到SMO算法，这个算法比较复杂，我们后面会专门来讲。在这里，我们假设通过SMO算法，我们得到了对应的α的值α∗。

　　　　那么我们根据w=∑i=1mαiyixi$w=\sum _{i=1}^m{\alpha }_i{y}_i{x}_i$，可以求出对应的w的值

　　　　求b则稍微麻烦一点。注意到，对于任意支持向量(xx,ys)$(x_x,y_s)$，都有

　　　　假设我们有S个支持向量，则对应我们求出S个b∗$b^{\ast }$,理论上这些b∗$b^{\ast }$都可以作为最终的结果， 但是我们一般采用一种更健壮的办法，即求出所有支持向量所对应的b∗s$b_s^{\ast }$，然后将其平均值作为最后的结果。注意到对于严格线性可分的SVM，b$b$的值是有唯一解的，也就是这里求出的所有b∗$b^{\ast }$都是一样的，这里我们仍然这么写是为了和后面加入软间隔后的SVM的算法描述一致。

　　　　怎么得到支持向量呢？根据KKT条件中的对偶互补条件α∗i(yi(wTxi+b)−1)=0${\alpha }_i^{\ast }(y_i(w^T{x}_i+b)-1)=0$，如果αi>0${\alpha }_i>0$则有yi(wTxi+b)=1$y_i(w^T{x}_i+b)=1$ 即点在支持向量上，否则如果αi=0${\alpha }_i=0$则有yi(wTxi+b)≥1$y_i(w^T{x}_i+b)\ge 1$，即样本在支持向量上或者已经被正确分类。

5. 线性可分SVM的算法过程

　　　　这里我们对线性可分SVM的算法过程做一个总结。

　　　　输入是线性可分的m个样本(x1,y1),(x2,y2),...,(xm,ym),$(x_1,y_1),(x_2,y_2),...,(x_m,y_m),$,其中x为n维特征向量。y为二元输出，值为1，或者-1.

　　　　输出是分离超平面的参数w∗和b∗$w^{\ast }和b^{\ast }$和分类决策函数。

　　　　算法过程如下：

　　　　1）构造约束优化问题

　　　　2）用SMO算法求出上式最小时对应的α$\alpha$向量的值α∗${\alpha }^{\ast }$向量.

　　　　3) 计算w∗=∑i=1mα∗iyixi$w^{\ast }=\sum _{i=1}^m{\alpha }_i^{\ast }{y}_i{x}_i$

　　　　4) 找出所有的S个支持向量,即满足αs>0对应的样本(xs,ys)${\alpha }_s>0对应的样本(x_s,y_s)$，通过 ys(∑i=1mαiyixTixs+b)=1$y_s(\sum _{i=1}^m{\alpha }_i{y}_i{x}_i^T{x}_s+b)=1$，计算出每个支持向量(xx,ys)$(x_x,y_s)$对应的b∗s$b_s^{\ast }$,计算出这些b∗s=ys−∑i=1mαiyixTixs$b_s^{\ast }=y_s-\sum _{i=1}^m{\alpha }_i{y}_i{x}_i^T{x}_s$. 所有的b∗s$b_s^{\ast }$对应的平均值即为最终的b∗=1S∑i=1Sb∗s$b^{\ast }=\frac{1}{S}\sum _{i=1}^S{b}_s^{\ast }$

 　　　　这样最终的分类超平面为：w∗∙x+b∗=0$w^{\ast }\bullet x+b^{\ast }=0$，最终的分类决策函数为：f(x)=sign(w∗∙x+b∗)$f(x)=sign(w^{\ast }\bullet x+b^{\ast })$

　　　　线性可分SVM的学习方法对于非线性的数据集是没有办法使用的， 有时候不能线性可分的原因是线性数据集里面多了少量的异常点，由于这些异常点导致了数据集不能线性可分， 那么怎么可以处理这些异常点使数据集依然可以用线性可分的思想呢？ 我们在下一节的线性SVM的软间隔最大化里继续讲。

（欢迎转载，转载请注明出处。欢迎沟通交流： liujianping-ok@163.com）