支持向量机（SVM），非常的神秘而众所周知的名字，其出来就受到了很大的追捧，号称最优秀的算法之一，简单地理论构造了复杂的算法，简单地用法实现了复杂的问题，一个词形容就是perfect！

本文旨在从基础出发，实例化的形式一探SVM的究竟。现在网上分析讲解SVM的博文多不胜数，当然对于那些基础好的一看就懂，但对于我这种渣渣来说看一遍也只能浅薄的了解，过两天又忘了公式的缘由。

比如说，在研究SVM之前你是否听过拉格朗日乘子法？是否听过对偶问题？是否了解它们的原理以及如何运用的？还有令人蛋疼的KKT条件了。请问我有没有说到你的心里去啊，但是不用怕，学学就会了。所谓拉格朗日乘子法，大学应该在概率论的点估计中应该学过，但你是否理解了它，如果你那时候理解了，我相信你肯定潜力无限，也不必看我这篇文章了。

1 关于拉格朗日乘子法和KKT条件

1）关于拉格朗日乘子法

首先了解一下拉格朗日乘子法，那么我们怎样了解它呢？你只需要记住，有拉格朗日乘子法的地方，肯定会是一个组合优化的问题。带约束的优化问题很好说，比如下面这个问题：

\begin{equation}
\begin{split}
min \ f\ =\ &2x{_1^2}+3x{_2^2}+7x{_3^2} \\
s.t. \ &2x_1 + x_2 = 1 \\
&2x_2 + 3x_3 = 2
\end{split}
\end{equation}

这是一个带等式约束的优化问题，有目标值，有约束条件。那么如果假设没有这个约束条件，这个问题该如何求解呢？

是不是直接f对x求导等于0，解x就可以了，可以看到没有约束的话，求偏导等于0，那么各个x均等于0，这样f=0了。但是x都为0不满足约束条件，那么问题就来了。在这里说一点，为什么上面说求导为0就可以呢？理论上多数问题是可以的，但是有的问题不可以。如果求导为0一定可以的话，那么f就是一个凸优化问题，什么是凸呢，像下面这个左图：

SVM（一）拉格朗日乘子法与 KKT条件

凸就是开口朝一个方向（向下或者向上）。准确的数学关系就是：

\begin{equation}
\begin{split}
&\frac{f(x_1) + f(x_2)}{2} > f(\frac{x_1+x_2}{2}) \ or \\
&\frac{f(x_1) + f(x_2)}{2} < f(\frac{x_1+x_2}{2})
\end{split}
\end{equation}

注意的是这个条件是对函数的任意值x取值。如果满足第一个就是开口向上的凸，反之开口向下的凸。

对于凸问题你可以去求导，从图中可以很容易看出只有一个极点，那么它就是最优点，直观也很合理。类似的看看右边的图，有时候满足第一个关系，有时候满足第二个关系。所以它是一个非凸的问题，对它进行求导会得到很多个极点。

从上图可以看出，只有一个极点是最优解，其他的是局部最优解，那么真实问题时候你选择哪个？所以我们想说的是，拉格朗日乘子法是一定适合于凸问题的，不一定适合其他的问题，还好我们最终的问题是凸问题。

回头再来看看有约束的问题，既然有了约束不能直接求导，那么把约束去掉不就可以了吗。那么怎么去掉呢？拉格朗日大法来了。既然是等式约束，那么就把这个约束乘一个系数加到目标函数里面去，比如上面的函数就变为：

\begin{equation}
\begin{split}
\ f\ =\ &2x{_1^2}+3x{_2^2}+7x{_3^2} + \alpha{_1} (1-2x_1 - x_2) + \alpha{_2}(2-2x_2 - 3x_3)
\end{split}
\end{equation}

现在这个优化目标函数没有约束条件吧，既然这样，我们对于x求偏导等于0，如下所示：

\begin{equation}
\begin{split}
&\frac{\partial f}{\partial x_1} = 4x_1 - 2\alpha_1 = 0 \Rightarrow \ x_1 = 0.5\alpha_1 \\
&\frac{\partial f}{\partial x_2} = 6x_2 - \alpha_1 - 2\alpha_2 = 0 \Rightarrow \ x_2 = \frac{\alpha_1 + 2 \alpha_2}{6} \\
&\frac{\partial f}{\partial x_3} = 14x_3 - 3\alpha_2 = 0 \Rightarrow \ x_3 = \frac{3\alpha_2}{14}
\end{split}
\end{equation}

把它再带到约束条件中去，可以解出\(\alpha_1\) 和 \(\alpha_2\)两个变量，这样再带回去求x就可以了。那么一个带等式约束的优化问题就通过拉格朗日乘子法完美的解决了。那么带有不等式的约束问题怎么办呢？因此，我们需要更一般化的的拉格朗日乘子法和KKT条件来解决这些问题。

2）关于KKT条件

继续讨论关于带等式以及不等式的约束条件的凸函数优化。任何原始约束问题无非最多三类，等式约束，大于约束，小于约束，而大于约束可以转为小于约束，因此最终可转为两个约束：等于约束和小于约束。举个简单地例子，假设原始约束条件为下面所示：

\begin{equation}
\begin{split}
min \ f\ =\ &x_1^2 - 2x_1 + 1 + x_2^2 + 4x_2 + 4 \\
s.t. \ &x_1 + 10x_2 > 10 \\
&10x_1 - 10x_2 < 10
\end{split}
\end{equation}

我们把约束条件变成下面的形式：

\begin{equation}
\begin{split}
s.t. \ &10 - (x_1 + 10x_2) < 0 \\
&10 -(10x_1 - 10x_2) <0
\end{split}
\end{equation}

现在我们将约束条件放入目标函数中去：

\begin{equation}
\begin{split}
L( x , \alpha ) = f(x) + \alpha_1 g_1(x) + \alpha_2 g_2(x)
= x_1^2 - 2x_1 + 1 + x_2^2 + 4x_2 + 4 + \alpha_1 (10-x_1 - 10x_2 ) + \alpha_2 (10x_1 - x_2 - 10)
\end{split}
\end{equation}

那么KKT条件的定理是什么呢？就是如果一个优化问题在转变后变成

\begin{equation}
L(x,\alpha,\beta) = f(x) + \sum \alpha_i g_i (x) + \sum \beta_i h_i (x)
\end{equation}

其中\(g_i\)是不等式约束，\(h_i\)是等式约束（像满足上面那个只有不等式约束，也有可能是等式约束）。那么KKT条件就是函数的最优值必须满足下面条件：

\begin{equation}
\begin{split}
( 1 )&L对各个x_i 求导为0 \\
( 2 )&h_i (x) = 0 \\
( 3 )&\sum \alpha_i g_i(x) = 0,\alpha_i \geq 0
\end{split}
\end{equation}

这三个式子前两个很好理解，那么第三个呢？我们知道在约束条件变完之后。所有的 \(g_i (x) \leq 0\)，然后求和还要为0，无非就是告诉你，要么某个不等式\(g_i (x) = 0\)，要么其对应的系数\( \alpha_i = 0\)，那么为什么KKT条件是这样的呢？

我们假设我们有一个目标函数，以及它的约束条件，形象的画出来就如下：
SVM（一）拉格朗日乘子法与 KKT条件

假设只有这几个约束条件，最终约束是把自变量约束在一定的范围内，函数是在这个范围内求最优解。函数一开始肯定不知道最优解在哪的，因此我们随便取一个，假设某次取得的自变量的集合为\(x_1\)，发现一看，不满足约束条件，然后我们换一个集合，比如说\(x_2\)，发现这时候满足条件，但是这个时候函数值不是最优的，并且\(x_2\)使得\(g_1 (x)\)和\(g_2 (x)\)等于0，并且\(g_3 (x) < 0\)，这个时候我们在\(x_2\)的基础上再寻找一组更优解该怎么办呢？当然是要靠约束条件\(g_1 (x)\) 和 \(g_2 (x)\)，因为它们等于0了，非常的极限，只要稍微不留神就会不满足它们两个了，这个时候我们选择往它们的梯度方向往下走，这样才能最大程度的满足\(g_1 (x)\) 和 \(g_2 (x)\)等于0，至于这个时候需不需要\(g_3 (x)\)呢？

正常来说管不管都可以，如果管了，也取\(g_3(x)\)在\(x_2\)处的梯度的话，因为\(g_3(x)\)已经满足了小于0的条件，这个时候也取在\(x_2\)处的梯度，我们不能保证它往好的变了还是坏的变了。

那么如果不管呢？因为\(g_1 (x)\)和\(g_2 (x)\)已经在边缘了，所以取它的梯度是一定会让目标函数变好的，综合来看这个时候我们就不需要考虑\(g_3 (x)\)了，那么再往下走，假设自变量走到了\(x_3 (x)\)，这个时候发现\(g_2 (x)\)和\(g_3 (x)\)等于0，也就是走到边了，而\(g_1 (x)\)小于0，可变化的空间绰绰有余，那么这个时候需要取\(g_2 (x)\)和\(g_3 (x)\)梯度方向作为变化方向而不需要考虑\(g_1 (x)\)。

那么这样一直这样走下去，最终找到最优解，可以看到的是，上述\(g_1 (x)\)和\(g_2 (x)\)等于0的话，我们是需要优化它的，又因为他们本身的条件是小于0的，所以最终的公式推导表明，要是乘一个正系数作为他们梯度增长的倍数，而那些不需要管的\(g_i (x)\)为了统一表示，我们可以将这个系数赋为0，那么这一项在优化中就没有了。

比如上面的例子的目标值和约束：

\begin{equation}
\begin{split}
s.t. \ &10 - (x_1 + 10x_2) < 0 \\
&10 -(10x_1 - 10x_2) <0
\end{split}
\end{equation}

将约束提取到函数中有：

此时分别对\(x_1\)和\(x_2\)求导数：

\begin{equation}
\begin{split}
&\frac{\partial L}{\partial x_1} = 2x_1 - 2 - \alpha_1 + 10 \alpha_2 = 0 \Rightarrow \ x_1 = 0.5(\alpha_1 - 10 \alpha_2 + 2) \\
&\frac{\partial L}{\partial x_2} = 2x_2 + 4 - 10 \alpha_1 - \alpha_2 = 0 \Rightarrow \ x_2 = 0.5(10 \alpha_1 + \alpha_2 -4 ) \\
\end{split}
\end{equation}

同时我们还有一个条件就是：

\begin{equation}
\sum \alpha_i g_i(x) = 0,\alpha_i \geq 0
\end{equation}

这样我们就可以讨论，要么\(g_i(x) = 0\)，要么\(\alpha_i = 0\)，这里有两个\(g_i\)两个\(\alpha_i\),这样我们就需要讨论四种情况，可能会说，这里是约束条件少的情况，如果约束条件有100个，是不是有很多的排列组合呢？但是换个思路来看，我们为什么非得100个一起去讨论？

人类的智慧是无穷的，机智的人们想到一种方法，我们两个两个的讨论不就可以了，比如现在我就讨论第7个第8个，让其它的不变，为什么至少选择两个讨论呢，因为，这个式子求和为0，显然改变一个是不行的。那么为什么不讨论三个呢，三个的话，你不觉得非常的麻烦呢，三个和尚没水喝，假设你改变了一个，那么其它两个你要怎么办呢，你会陷入选择的窘境。这个就是SMO算法的精髓，就是随便选择两个去变化，结果好的话就接受，否则就舍弃这两个。

因此，我们对上述的例子进行讨论：

\begin{equation}
\begin{split}
(1)\ &\alpha_1 = \alpha_2 = 0，那么我们可以得到 x_1 = 1,\ x_2 = -2，\\ &带入不等式中，发现不满足第一个不等式（10 - 1 + 20）< 0，舍弃； \\
(2)\ &g_1 (x) = g_2 (x) = 0，带进去解得，x_1 = \frac{110}{101}, x_2 = \frac{90}{101}，再带回去求解 \alpha_1, \alpha_2，\\ &发现\alpha_1 = \frac{58}{101}，\alpha_2 = \frac{4}{101}，满足条件，显然是一组解； \\
(3)\ &其他两种情况讨论发现是不行的。
\end{split}
\end{equation}

可以看到，像这样简单地讨论之后就可以得到解了。

那么得到的解对不对呢，因为这里的函数比较简单，我们可以用matlab画出来，如下所示：

SVM（一）拉格朗日乘子法与 KKT条件

这是截取下来的符合约束要求的目标面
SVM（一）拉格朗日乘子法与 KKT条件

可以看到最优解确实就是我们上面所求出来的解。既然问题可以这样解，那么复杂一点的只需要简单化，照样可以解出来，至此KKT条件解这类约束性问题就是这样，它对后续SVM求解是至关重要的，大家都理解了吗？

SVM（一） 拉格朗日乘子法 与 KKT条件

1 关于拉格朗日乘子法和KKT条件