SVM 由浅入深的尝试（二）对偶问题的理解

首先，在这里回答一个问题， SVM算法问什么要转为对偶问题？
原因就在于，SVM的代价函数里我们要求最大间隔分隔超平面，传统的方法就是通过样本计算出最优解w,b，但是这种做法严重依赖数据的维度，对偶问题就是将SVM从依赖多个维度转变为依赖N个数据点。

从上篇我们得到了求最大间隔分隔超平面的最优化问题和约束条件。

#发现简书里用latex写的公式容易失效，所以把代码保留下来
![](http://latex.codecogs.com/svg.latex?\min_{w,b}\qquad\frac{1}{2}||w||^2)
![](http://latex.codecogs.com/svg.latex?\\s.t.\;y_i(w\cdot\,x_i+b)-1\geq0,\;i=1,2,...N)

• 构建拉格朗日函数 lagrange function

在拉格朗日函数中，我们将目标函数和约束条件合并起来，我们对每一个不等式的约束引进拉格朗日乘子 alpha_i，我们规定alpha≥0。

![](http://latex.codecogs.com/svg.latex?\iota(w,b,a)=\frac{1}{2}||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot\,x_i+b)+\sum_{i=1}^N\alpha_i)

根据拉格朗日的对偶性，我们目标函数的最小问题被转化为极大极小问题。

![](http://latex.codecogs.com/svg.latex?\max_\alpha\min_{w,b}\iota(w,b,\alpha))

接下来我们对lagrange function进行求w,b偏导

![](http://latex.codecogs.com/svg.latex?\frac{\partial\iota}{\partial\,w}=w-\sum_{i=1}^N\alpha_iy_ix_i=0)
![](http://latex.codecogs.com/svg.latex?\frac{\partial\iota}{\partial\\b}=-\sum_{i=1}^N\alpha_iy_i=0)

得，

![](http://latex.codecogs.com/svg.latex?w=\sum_{i=1}^N\alpha_iy_ix_i)
![](http://latex.codecogs.com/svg.latex?\sum_{i=1}^N\alpha_iy_i=0)

将以上两式带入lagrange function
得到，

![](http://latex.codecogs.com/svg.latex?\min_{w,b}\iota=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot\,x_j)+\sum_{i-1}^N\alpha_i)

此时的方程只与alpha有关系，
接下来我们对min求alpha的极大，这就是对偶问题。
也就是

![](http://latex.codecogs.com/svg.latex?\max_\alpha\;-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot\,x_j)+\sum_{i-1}^N\alpha_i)
![](http://latex.codecogs.com/svg.latex?\\s.t.\sum_{i=1}^N\alpha_iy_i=0,\\\alpha_i\geq0,i=1,2,...,N)

我们将上述目标函数由极大转为极小，就得到下面等价的对偶优化问题

![](http://latex.codecogs.com/svg.latex?\min_\alpha\;\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot\,x_j)-\sum_{i-1}^N\alpha_i)
![](http://latex.codecogs.com/svg.latex?\\s.t.\sum_{i=1}^N\alpha_iy_i=0,\\\alpha_i\geq0,i=1,2,...,N)

至此，以上问题就可以通过计算alpha从而得到整个目标函数的最优解。