SVM推导过程注解
前言
支持向量机(Support Vector Machine)的原理其实比较简单，它是基于结构风险最小化理论之上在特征空间中建构最优分割超平面。在二维中就是线，在三维中就是面，但我们统称为超平面。
就我所看到的相关书本、论文以及网上博文情况来看，其一般步骤通常如下：
- 在二维平面中的线性可分情况开始讲解，求解硬间隔最优化
- 随后放宽条件，这时可以引入松弛向量，然后求解软间隔最优化
- 再后面拓展到线性不可分的情况，这时引入核函数方法（kernel trick），将低维数据映射到高维特征空间，在高维特征空间中，这些训练样本便是线性可分的了。
SVM在数据挖掘与统计机器学习的书中是必讲的，网上优秀的教程也很多；故这里我只是将某些一笔带过或者模棱两可的推导步骤结合自己学习过程做一些补充，错误与不尽之处还望大家不吝指教！欢迎大家使劲儿拍砖耶！
求解硬间隔最优化时的相关注解
首先我们回忆一下初中所学的知识,两条平行线的方程分别为：
$ax + by = c1$
$ax + by = c2$ (1)
两条平行线的距离d为：
$ d = \frac{|c_1-c_2|}{\sqrt(a^2+b^2)} $ (2)范数(norm)相关知识：
p-范数 $||X||_p = (|x_1|^p + |x_2|^p+…+ |x_n|^p)^{1/p}$;也即:1-范数 =$|x_1| + |x_2|+…+ |x_n|$
2-范数 =$ (|x_1|^2 + |x_2|^2 + …+|x_n|^2)^{1/2}$
$\infty-范数 = MAX(|x_1|, |x_2|, …, |x_n|)$
跟博文http://blog.csdn.net/buracag_mc/article/details/75159437中所讲的闵可夫斯基距离是否有些似曾相识；的确是这样的，p-范数确实满足范数的定义。其中三角不等式的证明不是平凡的，这个结论通常称为闵可夫斯基不等式。
其中2-范数简单记为||X||,也就是我们通常意义上所说的欧式距离！
先描述一下，假设我们有N个训练样本${(x_1, y_1),(x_1, y_1), …, (x_n, y_n)}$，x是2维向量，而$y_i \in {+1, -1}$是训练样本的标签，分别代表两个不同的类。这里我们需要用这些样本去训练学习一个线性分类器：$f(x)=sgn(w^Tx + b)$，sgn函数就是一个符号函数，也就是说$w^Tx+ b$大于0的时候，输出f(x) = 1，小于0的时候，f(x) = -1。而$w^Tx + b=0$就是我们要寻找的分类超平面，如下图所示：
我们需要这个超平面分隔这两类的效果最好，也就是说让这个超平面到这两个类的最近的那个样本的距离相同且最大。为了更好的说明，找到两个和这个超平面平行和距离相等的超平面，其实在平面几何中我们知道这就是平行线的移动，OK,如果各移动m个单位就达到要求，即：
$H_1: y = w^Tx + b=m$
$H_2: y = w^Tx + b=-m$
形式是不跟教材中的不一样？没关系，这里我们只是需要方程两边同时除以一个m即可：
$H_1: y = (\frac{w}{m})^Tx + \frac{b}{m}=1$
$H_2: y = (\frac{w}{m})^Tx + \frac{b}{m}=-1$(4)
这里为了统一起见，我们令w = w/m, b=b/m，注意与前面所说的$w^Tx + b=0$中的w和b是有区别的。(其实对于$w^Tx + b=0$,我们可以进行同样处理$H_1: y = (\frac{w}{m})^Tx + \frac{b}{m}=\frac{0}{m}$,再令w=w/m, b=b/m,即可完全统一了)
在H1左侧的函数值大于1，所有其分类为+1；在H2右侧的函数值小于1，所有其分类为-1，
可以统一记为记为$y_i(W^T.x_i + b) \geq 1$
这样便是我们熟悉的形式了！
下面大家便可以猜想到了，求$H_1$和$H_2$之间的最大距离。当然如果是在二维平面中(当然，这里是以二维特征来说的，当然就是二维平面了)，易知便是两条平行线之间的距离，根据前面所所述平行线的距离即可求出，这里我们称之为margin。
即：margin = 2/||W||
这里对于二维特征$W^T = (w_1,w_2)$，||W||便是参数W的二范数(有的教科书又称之“模”)，将上式展开表示我们熟悉的平行线的距离了$margin = \frac{2}{\sqrt(w_1^2 + w_2^2)}$
但是，在统计机器学习中，我们要让它符合更多一般的情况，美其名曰便是“泛化能力”。将特征空间拓展到多维的情况，便是用向量来进行表示了，故在多维特征空间中，我们同样求margin= 2/||W||。
要使margin最大，即需W最小，故我们设我们的目标函数：
$min \frac{1}{2}||W||^2$
$s.t. yi(W^Tx_i + b) \geq 1, \forall x_i$ (5)
很多人会纠结W前面的系数1/2，这里加不加1/2其实没关系，这是为了求导时消去。其实在机器学习中， 我们常见的平方损失函数便是进行了同样的处理，在前面加了个常数系数1/2。
对于(5)式，准确的讲这是一个带有不等式约束的条件极值问题，根据高等数学和基础运筹学内容可以知道，我们可以用拉格朗日方法求解。
这里我必须要补充的一点是：通过查阅教科书以及在阅读网上的优秀教程，我发现不同教科书和网上不同的教程都有不同的说法，虽然实质是不变的，但当时我遇到的坑必须给大家给填了。
首先带不等式约束的条件极值问题中会有大于号约束、小于号约束两种(这里我们暂且先不说带等号，下文将KKT条件的时候一并补充)
第一种说法如下：将所有不等式约束条件统一为小于号约束，然后拉格朗日方程的构建规则是用约束方程乘以非负的拉格朗日系数，然后再加上目标函数即可。
第二种说法如下：将所有不等式约束条件统一为大于号约束，然后拉格朗日方程的构建规则是用约束方程乘以非负的拉格朗日系数，然后再从目标函数中减去即可。
其实我们可以发现这两种说法是等价的！事实确实如此，但是很多博文在讲解拉格朗日函数的构建时要么说用目标函数加上约束方程乘以非负的拉格朗日系数，要么说用目标函数减去约束方程乘以非负的拉格朗日系数。
可能某些文章作者完全没有申明大前提，他们准确的说法应该是，当统一成小于号约束时，拉格朗日函数的构建时是用目标函数加上约束方程乘以非负的拉格朗日系数；当统一成大于号约束时，拉格朗日函数的构建时是用目标函数减去约束方程乘以非负的拉格朗日系数。在不提前申明不同的大前提下，可能会误导不细心以及课程学的不仔细的读者(当时包括我=_=！)，导致某些人纳闷了，咦，这个拉格朗日咋一会儿是加上约束约束乘以拉格朗日系数，一会儿又是减去约束方程乘以拉格朗日系数啊？？？
为了统一与方便说明起见，故下文我们运用的第一种规则，将不等式约束条件统一成小于号约束。于是得到拉格朗日方程如下：
$L(w,b,a) = \frac{1}{2}||W||^2 + \sum_{i=1}^{n}a_i(1-y_i(wx_i+b)) = \frac{1}{2}||W||^2 - \sum_{i=1}^{n}a_i(y_i(wx_i+b)) + \sum_{i=1}^{n}a_i $
(6)
拉格朗日函数构建好后接下来便是简单的求解问题了，分别对W和b求偏导数并令其为零，得到如下结果：
$W = \sum_{i=1}^{n}a_iy_ix_i$ (7)
$\sum_{i=1}^{n}a_iy_i = 0$ (8)
带入(6)式即可得到:
$Max.W(a) =\sum_{i=1}^{n}a_i - \frac{1}{2}\sum_{i=1,j=1}^{n}a_ia_jy_iy_jx_i^Tx_j$
$s.t. a_i \geq 0, \sum_{i=1}^{n}a_iy_i = 0$(9)
为什么$min \frac{1}{2}||W||^2$问题变成了
$Max.W(a) =\sum_{i=1}^{n}a_i - \frac{1}{2}\sum_{i=1,j=1}^{n}a_ia_jy_iy_jx_i^Tx_j$
当然是对偶问题的求解了！对偶问题是怎么推导过来的？很多文章仅仅只是一笔带过了这么重要的推导内容。。。导致很多人有些小困惑哈~，为什么构建拉格朗日函数后就将求最小化问题变成求最大化问题？OK，既然本文的定位是SVM推导过程中的解析及注解，必定是要把这个问题完整给推导清楚的。
SVM中对偶问题的注解
再回看(6)式，
$L(w,b,a) = \frac{1}{2}||W||^2 + \sum_{i=1}^{n}a_i(1-y_i(W^Tx_i+b)) = \frac{1}{2}||W||^2 - \sum_{i=1}^{n}a_i(y_i(W^Tx_i+b)) + \sum_{i=1}^{n}a_i $
$s.t. a_i \geq 0$
我们要处理的最优化问题最正确的表达形式其实为：
(10)
上式才是严格带有不等式约束条件下的拉格朗日条件极值的表达式。我读的很多介绍SVM的文章(包括我看的书本)都是没说的！(10)式便是一个凸规划问题。
其意义是先对a求偏导，令其等于0消掉a，然后再对W和b求L的最小值。
要直接求解(10)式是有难度的，幸好这个问题可以通过拉格朗日对偶问题来解决。常说对偶问题对偶问题，现在就是真正发挥这把利器的时候了。对(10)式做一个简单的等价变换：
(11)
上式即为对偶变换，这样就把这个凸规划问题转换成了对偶问题
其意义是：原凸规划问题可以转化为先对W和b求偏导，令两个偏导数都等于0消掉W和b，然后再对a求L的最大值。与(10)的意义是相反的，或者说是对偶的！不知我讲到这步，大家是否对对偶问题有了一个豁然开朗的感觉———啊！原来对偶问题就是这啊！！
然后将求得的(7)式和(8)式带入(6)式，得：
(12)
将(12)式带入(11)式得：
(13)
再考虑到(8)式，对偶问题的完整表达为：
(14)
到了这一步，我们便可以直接用数值方法计算求解拉格朗日乘数a了。求得a过后根据(7)式可以得到W，然后根据超平面方程可以求出b。最终便得到了我们想要的超平面和分类决策函数，也就是我们训练好的SVM分类器。那么对于待分类样本X，其分类为为：
(15)
我们根据(15)式可以发现，对于一个待分类样本，我们先计算待分类样本和训练样本的内积然后加权就和再加上b值即可。训练样本特别大的情况下，如果对所有训练样本做运算是否太耗时了啊？很多教科书以及网上教程都是直接说根据KKT条件可知，只有支持向量的乘子(拉格朗日乘数)$a_i$不等于0，其他训练样本的乘子都为0，这样便会大大减少运算量，也是后面SVM引入核函数(kernel)的铺垫。这又会引起新的疑惑，为什么只有支持向量对应的乘子不为0呢？
SVM中KKT条件注解
这里还是继续讨论一下带等式和不等式约束的条件极值问题。任何极值问题的约束条件不外乎3种：等式、大于号和小于号，为了统一起见，我们将不等式约束统一为小于号。
例如：
$min(max) f(x) $
$s.t. g_i(x) \leq0,i=1,2…n_1$
$ h_j(x) = 0,j=1,2…n_2$
那么一个极值优化问题我们转化为：
- KKT条件就是函数的最优值必须满足以下条件：
- L对各个x的偏导为零
- h(x) = 0
- $\sum_{i=1}^{n_1}a_ig_i(x) =0 , a_i\geq0$
假设一个目标函数，3个不等式约束条件把自变量约束在一定范围，而目标函数是在这个范围内寻找最优解。
1.函数开始也不知道该取哪一个值是吧，假设某一次取得自变量集合为x1*，发现不满足约束，然后再换呀换；
2.假设到x2满足约束条件，但是这个时候函数值不是最优的，并且x2使得g1(x)与g2(x)等于0了，而g3(x)还是小于0。这个时候，我们发现在x2*的基础上再寻找一组更优解要靠谁呢？当然是要靠约束条件g1(x)与g2(x)，因为他们等于0了，很极限呀，一不小心，走错了就不满足这两个约束的条件了，这个时候我们会选择g1(x)与g2(x)的梯度方向往下走，以寻找最优值解。
3.这个时候需不需要管约束条件g3(x)呢？正常来说管不管都可以，如果管，也取g3在x2处的梯度的话，由于g3已经满足小于0的条件，这时候再取在x2处的梯度，有可能更快得到结果，也有可能适得其反；如果不管g3，由于g1和g2已经在边缘了，只取g1和g2的梯度，是肯定会让目标函数接近解的；故我们这时候是不用考虑g3的；
4.再往下走，到了x3*处发现g2和g3等于0了，也就是说走到边了，而g1是满足约束小于0的，这时候我们重复上一步，取g2和g3的梯度方向作为变化方向，而不用管g1.
5.一直循环3(4)步，直到找到最优解。
可以看到的是，如果如果g1、g2=0时，由于他们本身的条件是小于0的，我们是需要优化他们的，操作上便是乘以一个正常数a作为他们梯度增长的倍数(或者说学习效率)，那些暂且不需要考虑的约束，例如这里说的g3，我们可以乘以系数0，即在下一次的优化中是不用考虑这些约束的。综上所述的话：
$\sum_{i=1}^{n_1}a_ig_i(x) = 0, a_i\geq0$
如上，简单直观地说便是KKT条件中第三个式子的意义了。
回到SVM的推导上来，对于(6)式，我们知道其KKT条件中的第三个式子为:
$\sum_{i=1}^{n_1}a_i(1-y_i(W^T.x_i+b)) = 0$，
我们知道除了支持向量，对于其他训练样本有：
$y_i(W^T.x_i + b) > 1$ 也即$1 - y_i(W^T.x_i + b) <0$根据前面所述的内容知道，其对应的乘子为0。
对于支持向量来说：$y_i(W^T.x_i + b) =1$ 也即$1 - y_i(W^T.x_i + b) =0$，其对应的乘子不为0。
也就是说，新来的待分类样本只需与支持向量求内积即可，这便大大减少了计算量！这便是KKT条件在SVM关键推导中的应用。
这里我再补偿一下另外一种思路，其实本质还是KKT条件：
由于(5)式与(10)式等价，即：
(16)
故要使(16)式成立，只有令$a_i(1-y_i(W^T.x_i+b)) = 0$成立，由此得到KKT的第三个条件：
$\sum_{i=1}^{n_1}a_i(1-y_i(W^T.x_i+b)) = 0$
同样可出结论：支持向量对应的乘子为正系数；如果一个样本不是支持向量，则其对应的乘子为0。