《SVM笔记系列之二》SVM的拉格朗日函数表示以及其对偶问题-电源网

本文转自徐飞翔的“《SVM笔记系列之二》SVM的拉格朗日函数表示以及其对偶问题”

版权声明：本文为博主原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。

SVM的原问题的拉格朗日乘数表示

我们在上一篇博文《SVM笔记系列1，SVM起源与目的》中，谈到了SVM的原问题，这里摘抄如下：

其满足形式:

假设原问题为 $\theta_P(x)$ ，并且其最优解为 $p^*=\theta_P(x^*)$ 。这是一个有约束的最优化问题，我们利用广义拉格朗日乘子法(具体移步《拉格朗日乘数法和KKT条件的直观解释》)，将其转换为无约束的形式：

变形为：

我们将会得到原问题的另一个表述为：

这里我觉得有必要解释下为什么可以表述为 $max_{\alpha}$ $L(W, b, \alpha)$ 这种形式。假设我们有一个样本点是不满足原问题的约束条件 $1-y_i(W^Tx_i+b) \leq 0$ 的，也就是说 $1-y_i(W^Tx_i+b) \gt0$ ，那么在 $max_{\alpha}$ 这个环节就会使得 $a_i \rightarrow +\infty$ 从而使得 $L(W,b,\alpha) \rightarrow+\infty$ 。如果是满足约束条件的，那么为了求得最大值，因为 $1-y_i(W^Tx_i+b) \leq 0$ 而且 $a_i \geq 0$ ，所以就会使得。由此我们得知：

因此在满足约束的情况下，

不满足约束条件的样本点则因为无法对正无穷求最小值而自然抛弃。这个时候，我们试图去解 $max_{\alpha}L(W,b,\alpha)$ 中的 $max_{\alpha}$ 我们会发现因为 $L(W,b,\alpha)=\frac{1}{2}||W||^2 + \sum_{i=1}^N {\alpha_i}-\sum_{i=1}^N{\alpha_iy_i(W^Tx_i+b)}$ 对于 $\alpha$ 是线性的，非凸的1，因此无法通过梯度的方法求得其最大值点，其最大值点应该处于可行域边界上，因此我们需要得到SVM的对偶问题进行求解。至此，我们得到了原问题的最小最大表述：

SVM的对偶问题

从上面的讨论中，我们得知了SVM的原问题的最小最大表达形式为：

设SVM的对偶问题为 $\theta_D(\alpha)$ ，其最优解为 $d^*=\theta_D(\alpha^*)$ ，可知道其为：

此时，我们得到了对偶问题的最大最小表述，同样的，我们试图去求解 $\theta_D(\alpha)$ 中的 $min_{W,b}$ ，我们会发现由于 $L(W,b,\alpha)=\frac{1}{2}||W||^2 + \sum_{i=1}^N {\alpha_i}-\sum_{i=1}^N{\alpha_iy_i(W^Tx_i+b)}$ 对于W来说是凸函数，因此可以通过梯度的方法求得其最小值点（即是其极小值点）。

求解 $min_{W,b} L(W,b,\alpha)$ ，因为 $L(W,b,\alpha)$ 是凸函数，我们对采用求梯度的方法求解其最小值（也是KKT条件中的， $\nabla_WL(W,b,\alpha)=0$ 和 $\nabla_b L(W,b,\alpha)=0$ ：

得出：

将其代入，注意到 $\sum_{i=1}^N\alpha_iy_i=0$ ,得：

整理为:

等价为求最小问题:

根据Karush–Kuhn–Tucker(KKT)条件2,我们有：

前两个式子我们已经在求极值的时候利用了，得知:

并且其中至少有一个 $a_j^* \gt 0$ ，对此有，代入刚才的，我们有

所以决策超平面为：

分类超平面为：

其中，我们可以观察到超平面只是依赖于 $\alpha_i^*>0$ 的样本点，而其他样本点对其没有影响，所以这些样本是对决策超平面起着决定性作用的，因此我们将 $\alpha_i^*>0$ 对应的样本点集合称为支持向量。同时，我们可以这样理解当 $\alpha^*_i >0$ 时，我们有，这个恰恰是表明了支持向量的函数间隔都是1，恰好和我们之前的设定一致。

至此，我们得到了硬间隔线性支持向量机的数学表述形式，所谓硬间隔线性支持向量机，就是满足我之前的假设

两类样本是线性可分的，总是存在一个超平面可以将其完美分割开。

但是，在现实生活中的数据往往是或本身就是非线性可分但是近似线性可分的，或是线性可分但是具有噪声的，以上两种情况都会导致在现实应用中，硬间隔线性支持向量机变得不再实用，因此我们将会在后续讨论用以解决近似线性可分的软间隔线性支持向量机和基于kernel的支持向量机，后者可以解决非线性可分的问题。下图表示了硬间隔线性支持向量机和软间隔支持向量机之间的区别。

在下一篇中，我们紧接着现在的内容，介绍序列最小最优化算法（Sequential Minimal Optimization,SMO），用于求解 $\theta_D(x)$ ，得到 $\alpha^*_i$ 以便于得到超平面的和b。我们将在其他文章中介绍软间隔线性支持向量机，广义拉格朗日乘数法，KKT条件和基于kernel的支持向量机。

这里我们要记住我们需要最优化的目的式子，我们以后将会反复提到这个式子。

1.易证明。参考wikipedia的凸函数定义。 ↩︎

2.事实上，如果 $\theta_D(x)$ 的 $L(W,b,\alpha)$ 满足KKT条件，那么在SVM这个问题中，和和 $\alpha^*_i$ 同时是原问题和对偶问题的解的充分必要条件是满足KKT条件，具体见《统计学习方法》附录和《拉格朗日乘数法和KKT条件的直观解释》。