上一篇，讲了线性支持向量机SVM，将其构造成约束最优化问题，求出最优解作为分类决策函数。我们将其定义为原始最优化问题(primal)。

为了给支持向量机引入更高级的特性，比如核函数，我们首先将应用拉格朗日对偶性，通过求解对偶问题(dual)，来得到原始问题的最优解。

关于拉格朗日对偶性 及 KKT条件的详细解答，可以看之前的文章《广义拉格朗日函数 及其 对偶算法》

上节课的约束最优化问题，也就是原始最优化问题如下：

$$ \begin{aligned} min_w \quad & f(w)& \\ s.t. \quad & g_i(w) \le 0,\quad i=1,...,k\\ & h_i(w) =0,\quad i=1,...,l\\ \end{aligned} $$

广义拉格朗日函数(generalized Lagrangian function)的定义如下：

$$ L(w,\alpha,\beta)=f(w)+\sum^k_{i=1}\alpha_ig_i(w)+\sum^l_{i=1}\beta_ih_i(w) $$

广义拉格朗日函数和其对偶形式的关系如下：

$$ d^\ast = \max_{\alpha,\beta:\alpha_i\geq 0}\min_w L(w,\alpha,\beta) \leq \min_w \max_{\alpha,\beta:\alpha_i\geq 0}L(w,\alpha,\beta) =p^\ast $$

也就是说，对偶问题是原始问题的下限。想让他们相等，需要满足下面的KKT条件：

$$ \begin{aligned} \frac{\partial}{\partial w}L(w^\ast,\alpha^\ast,\beta^\ast) &= 0,\quad i=1,...,n & \text(K1)\\ \frac{\partial}{\partial \alpha}L(w^\ast,\alpha^\ast,\beta^\ast) &= 0,\quad i=1,...,n & \text(K2)\\ \frac{\partial}{\partial \beta}L(w^\ast,\alpha^\ast,\beta^\ast)&= 0 ,\quad i=1,...,l & \text(K3)\\ \alpha_i^\ast g_i(w^\ast)&= 0,\quad i=1,...,k & \text(K4)\\ g_i(w^\ast)&\leq 0,\quad i=1,...,k & \text(K5)\\ \alpha_i^\ast &\geq 0,\quad i=1,...,k &\text(K6)\\ h_j(x^*)&=0,\quad j=1,...,l&\text(K7) \end{aligned} $$

原始问题是这样的：

$$ \begin{aligned} min_{\gamma,w,b} \quad & \frac12 \parallel w\parallel ^2\\ &\\ s.t. \quad &y^{(i)}(w^Tx^{(i)}+b)\geq 1,\quad i=1,...,m\\ \end{aligned} $$

我们可以将原始问题定义为广义拉格朗日函数，用$g$来代替约束条件，也就是：

$$ g_i(w)=-y^{(i)}(w^Tx^{(i)}+b)+1\leq 0 $$

原始问题的拉格朗日函数形式如下

$$ L(w,b,\alpha )=\frac{1}{2}\parallel w\parallel ^2 - \sum^N_{i=1}\alpha_i [y^{(i)}(w^Tx^{(i)}+b)-1] $$

根据KKT条件(K1)($b$也算在拉格朗日函数的$w$中)，可知满足KKT条件的$w$与$b$,必满足下面公式：

$$ \begin{aligned} \frac{\partial}{\partial w} L(w,b,\alpha)&=w-\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)} =0\\ \frac{\partial}{\partial b}L(w,b,\alpha)&=\sum^N_{i=1}\alpha_i y^{(i)}=0 \end{aligned} $$

从中，可以得出：

$$ \begin{aligned} &w=\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)}\\ &\sum^N_{i=1}\alpha_i y^{(i)}=0 \end{aligned} $$

满足KKT条件必须满足这两个公式，所以可以将它们带入公式中，可得：

$$ \begin{aligned} L(w,b,\alpha)&=\frac{1}{2}\parallel w\parallel ^2 - \sum^N_{i=1}\alpha_i [y^{(i)}(w^Tx^{(i)}+b)-1]\\ &=\sum^N_{i=1}\alpha_i-\frac12 \sum^N_{i,j=1} y^{(i)}y^{(j)}\alpha_i\alpha_j(x^{(i)})^Tx^{(j)}-b\sum^N_{i=1}\alpha_i y^{(i)} \end{aligned} $$

其中，最后一项$b\sum^N_{i=1}\alpha_i y^{(i)}​$恒等于0，于是得出：

$$ L(w,b,\alpha)=\sum^N_{i=1}\alpha_i-\frac12 \sum^N_{i,j=1} y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)}x^{(j)}\rangle $$

最终，结合原始问题，得出如下对偶优化问题:

$$ \begin{aligned} \max_\alpha \quad & W(\alpha) =\sum^N_{i=1}\alpha_i-\frac12\sum^N_{i,j=1}y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)} x^{(j)} \rangle\\ s.t. \quad & \alpha_i \geq 0,\quad i=1,...,N\\ & \sum^N_{i=1} \alpha_iy^{(i)}=0 \end{aligned} $$

可以证明，这个优化问题是满足 和 KKT 条件的，也就是 $p^\ast = d^\ast​$。这样，就可以使用对偶问题来解决原始问题。只要求出$\alpha​$，使$W(\alpha)​$最大化，就可以利用$w=\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)}\\​$来求出$w^\ast​$的值，根据$w^\ast​$ 就可以找到最优的$b^*​$：

$$ b^\ast =y_j-\sum\limits_{i=1}^{N}\alpha^\ast_iy_i\langle x^{(i)}x^{(j)}\rangle $$

注意一点，根据KKT条件的(K4)条件，可知：

$$ \alpha_i^\ast g_i(w^\ast)= \alpha_i(1-y^{(n)}(w^T x^{(i)}+b))=0 $$

可以知道：当$1-y^{(n)}(w^T x^{(i)}+b)​$不等于0，也就是$y^{(n)}(w^T x^{(i)}+b)\ne1​$时，$\alpha_i​$必等于0。

也就可以推出，当$\alpha_i\ne0$，$y^{(i)}(w^T x^{(i)}+b)=1=\hat\gamma$($\hat\gamma$的定义详见上一篇文章)，也就是说，$a_i\ne0$可以推出$(x^{i},y^{i})$是离分类超平面最近的点，刚好在两条线上的点。

而$w=\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)}​$，可以看出，$w​$完全是这些离分离超平面最近的样本点的线性组合，这些点也被称为支持向量(support vectors)，这就是支持向量机名字的由来。

当我们要用这个分类器预测一个新的点$x$时，可以使用如下公式

$$ \begin{aligned} w^Tx+b&= (\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)})^Tx+b & \text{(12)}\\ &= \sum^N_{i=1}\alpha_i y^{(i)}\langle x^{(i)},x \rangle+b & \text{(13)}\\ \end{aligned} $$

上面式子，很多的$\alpha_i​$都等于0，只有支持向量对应的$\alpha_i​$才不会等于0，所以计算量其实并不大。

算法

线性可分SVM的对偶算法如下：

输入：$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}​$，其中，$x_i\in R^n​$,$y_i\in{-1,+1}​$

输出：最大间隔分类超平面$(w,b)$和分类决策函数$f(x)$

(1)构造并求解约束最优化问题：

$$ \min\limits_{\alpha}\frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\alpha_i\alpha_jy_iy_j\langle x^{(i)},x^{(j)} \rangle-\sum\limits_{i=1}^{N}\alpha_i\\ \begin{eqnarray} s.t.\ \ &\sum\limits_{i=1}^{N}\alpha_iy_i=0\\ &\alpha_i\ge0,\ \ i=1,2,...N \end{eqnarray} $$

求出最优解决$\alpha^\ast=(\alpha^\ast_1,\alpha^\ast_2,...,\alpha^\ast_N)^T​$。

(2)计算：

$$ w^\ast=\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)}\\ $$

选择一个$\alpha_i>0$的样本，得出：

$$ b^\ast =y_j-\sum\limits_{i=1}^{N}\alpha^\ast_iy_i(x_i\cdot x_j) $$

(3)求得分类超平面

$$ (w^\ast)^Tx+b=0 $$

分类决策函数：

$$ f(x)=sgn((w^\ast)^Tx+b=0) $$

这一篇，我们更深入的了解了支持向量机的内在结构，并将其转换为对偶形式，并使用内积形式来编写整个算法。

后面将会将软间隔、核技巧等概念引入SVM中，让SVM更加强大。