【机器学习】支持向量机(二)----间隔最大化与原始问题

上一篇文章描述了支持向量机的基本思想和间隔的定义，这一篇我们就可以开始好好讨论一下硬间隔最大化，软间隔最大化到底是什么gui

【硬间隔最大化】

先不看软硬(笑)，间隔最大化，顾名思义就是令我的训练样本在分离超平面上的几何间隔最大就是咯，那么如何用数学的语言来描述呢？(题外话：往往我们要说上好几句才能解释清楚的原理或是算法，用上数学语言，就变得言简意赅了，这就是数学的魅力，虽然我的数学还处于社会主义初级阶段，不过我真心觉得数学是一门非常美丽的学科)

用一个公式概括间隔最大化思想：maxωT,bγ$\underset{{\omega }^T,b}{max}\gamma$
当然，我们希望所有的样本点(xi$x_i$,yi$y_i$)的几何间隔都大于γ$\gamma$，所以加上约束条件：yi(ωT||ω||xi+b||ω||)≥γ$y_i(\frac{{\omega }^T}{||\omega ||}{x}_i+\frac{b}{||\omega ||})\ge \gamma$

综合起来就得到了一个约束最优化问题：
　　　maxωT,bγ$\underset{{\omega }^T,b}{max}\gamma$
s.t. 　 yi(ωT||ω||xi+b||ω||)≥γ$y_i(\frac{{\omega }^T}{||\omega ||}{x}_i+\frac{b}{||\omega ||})\ge \gamma$

考虑到几何间隔和函数间隔的关系，即γ=γ^||ω||$\gamma =\frac{\hat{\gamma }}{||\omega ||}$，问题可以变为：
　　　maxωT,bγ^||ω||$\underset{{\omega }^T,b}{max}\frac{\hat{\gamma }}{||\omega ||}$
s.t. 　 yi(ωTxi+b)≥γ^$y_i({\omega }^T{x}_i+b)\ge \hat{\gamma }$

关键一步来了，先说结论：函数间隔γ^$\hat{\gamma }$的取值并不影响最优化问题的解，因此我们取γ^=1$\hat{\gamma }=1$

为什么呢？证明如下图：
1.证明约束项不受影响：

2.证明目标函数优化项不受影响：

好了，根据上面讨论，我们取γ^=1$\hat{\gamma }=1$也不会对我们原来问题产生影响，因此问题又变为了如下形式：
　　　maxωT,b1||ω||$\underset{{\omega }^T,b}{max}\frac{1}{||\omega ||}$
s.t. 　 yi(ωTxi+b)≥1$y_i({\omega }^T{x}_i+b)\ge 1$

emmm，1||ω||$\frac{1}{||\omega ||}$这个函数不是一个凸函数，求它的最大实在不好求，所以我们换个思路。求1||ω||$\frac{1}{||\omega ||}$不就等价于求12||ω||2$\frac{1}{2}||\omega |{|}^2$嘛，而12||ω||2$\frac{1}{2}||\omega |{|}^2$是个凸函数，我们很容易就能求到它的最小值(会一点求导的人都知道)，因此问题又可以变成这样：
　　　minωT,b12||ω||2$\underset{{\omega }^T,b}{min}\frac{1}{2}||\omega |{|}^2$
s.t. 　 yi(ωTxi+b)−1≥0$y_i({\omega }^T{x}_i+b)-1\ge 0$

大功告成，通过三次整容，我们就把一个麻烦的约束最优化问题转化为了一个可解析的凸优化问题(这里是一个凸二次规划问题)，吼吼吼，这下我们就可以欢快的求解了！！

可是！

只求minωT,b12||ω||2$\underset{{\omega }^T,b}{min}\frac{1}{2}||\omega |{|}^2$我会求，可是加了s.t.约束项yi(ωTxi+b)−1≥0$y_i({\omega }^T{x}_i+b)-1\ge 0$的这个问题怎么求呢？这个问题就要引入对偶问题了，我们会再次见到那个熟悉的名字——拉格朗日，不过这个问题留到下一篇再写。

【软间隔最大化】

先不考虑我们怎么解带约束项的优化问题了，我们继续来看SVM在训练数据近似可分的情况下该怎么办？我们还能用上面的优化问题来表示吗？o(￣ヘ￣o＃)显而易见，不能，想想上一篇线性支持向量机的图，某些样本点根本就不能满足我们的约束条件(即不能满足函数间隔大于等于1的条件)，由此看来不能对它的要求太严，我们把约束改的稍微松一点，给你个容限，这里称为松弛变量ξi${\xi }_i$，因此约束条件变成了这样：
　　　　　　 yi(ωTxi+b)≥１－ξi$y_i({\omega }^T{x}_i+b)\ge １－{\xi }_i$
当然啦，我不能无限度的容忍你，不然我还分啥类，所以我们需要在目标函数优化项上加上一个代价：C∑Nn=1ξi$C\sum _{n=1}^N{\xi }_i$　(C>0称为惩罚参数)
这里我觉得其实有点像正则化的思想，在ωT${\omega }^T$和b$b$确定的情况下，C越大，对于ξi${\xi }_i$来说只有取得越小才能使12||ω||2+C∑Nn=1ξi$\frac{1}{2}||\omega |{|}^2+C\sum _{n=1}^N{\xi }_i$越小，也就是说如果我这个样本点稍微偏离了一点我的分类，带来的后果是很严重的，也就是对误分类的惩罚增大了；但是如果C小一些，对于ξi${\xi }_i$来说，我可以比较放肆的加大一些，因为我对你的容忍度高了，也就是对误分类的惩罚减小了。这里呢，ξi${\xi }_i$也可以取不同的形式，如ξ2i${\xi }_i^2$，emmmm，更像正则化了，L2有木有。。
综上，我们可以得出线性支持向量机的学习问题：
　　　minωT,b,ξ12||ω||2+C∑Nn=1ξi$\underset{{\omega }^T,b,\xi }{min}\frac{1}{2}||\omega |{|}^2+C\sum _{n=1}^N{\xi }_i$
s.t. 　 yi(ωTxi+b)≥1−ξi$y_i({\omega }^T{x}_i+b)\ge 1-{\xi }_i$　　　(i=1,2,…N)
s.t.　　ξi≥0${\xi }_i\ge 0$　　　　　(i=1,2,…N)

ε=(´ο｀*)))唉，仔细观察上面这个问题，又多了一个约束项ξi≥0${\xi }_i\ge 0$，这该怎么求呢?不方不方，我们下一篇让拉格朗日大神来大展神威

参考文献：《统计学习方法》、《机器学习》