"> "> 机器学习-支持向量机 | Yufei Luo's Blog

Yufei Luo's Blog

But I was so much older then, I am younger than that now.

Yufei Luo's Blog

机器学习-支持向量机

发表于 更新于 分类于 ， 阅读次数：
本文字数： 26k 阅读时长 ≈ 23 分钟

定义

支持向量机（Support Vector Machine，SVM）是一种二分类模型，属于线性模型的一种，它的学习思想是在空间内找到一个超平面\(\boldsymbol{x}\boldsymbol{w}^T+b=0\)（其中\(\boldsymbol{x}=(x_1,x_2,\dots,x_n)\)代表模型的输入向量，\(\boldsymbol{w}=(w_1,w_2,\dots,w_n)\)与\(b\)为模型参数），能够使得两类样本与超平面的间距最大化。落在超平面两侧的样本，分别对应于\(y=+1\)和\(y=-1\)两种不同的分类。也就是说，在学得超平面的表达式之后，支持向量机模型的分类函数可以写为： \[ y= \begin{cases} 1,~\boldsymbol{x}\boldsymbol{w}^T+b>0 \\ -1,~\boldsymbol{x}\boldsymbol{w}^T+b<0 \\ \end{cases} \]

img

上图所示为SVM在二维平面内的一个简单示例，图中的黑点和白点代表两种不同的类别。在图中有三条不同的直线\(H_1,H_2,H_3\)，我们可以看到，\(H_1\)无法将两种类别的样本正确地分类；\(H_2\)和\(H_3\)都可以将两种类别的样本正确地分类，但是\(H_2\)与最近的数据点之间的间隔明显比\(H_3\)与最近的数据点之间的间隔要小得多。因此我们有理由推测，\(H_3\)在处理未知数据的时候应该对样本点有更好的分类效果。SVM模型便对应于图中\(H_3\)这条直线的表达式，而距离\(H_3\)最近的那个黑点和白点被称为支持向量。

模型推导

硬间隔SVM

优化问题的导出

求解SVM的过程就是求解能够使得两类样本间隔最大的超平面的过程，可以将其转化为优化问题进行求解。简单起见，我们先讨论硬间隔SVM，即超平面与支持向量形成的间隔中不允许有任何样本点；然后再对这一限制条件进行松弛，允许间隔中有部分样本点的出现，从而得到软间隔SVM。

在空间内，任意一个样本\(\boldsymbol{x}_i\)与超平面\(\boldsymbol{x}\boldsymbol{w}^T+b=0\)之间的距离\(d=\frac{||\boldsymbol{x}_i\boldsymbol{w}^T+b||}{||\boldsymbol{w}||}\)。假设在所有样本中，与超平面距离的最小值为\(d_{\min}=\min \frac{||\boldsymbol{x}_i\boldsymbol{w}^T+b||}{||\boldsymbol{w}||}\)，则SVM的优化问题可以表述为下面的形式： \[ \max~d_{\min} \\ s.t.~y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge d_{min}||\boldsymbol{w}|| \] 由于\(\boldsymbol{w}\)和\(b\)的取值不做限制，因此表达式\(||\boldsymbol{x}_i\boldsymbol{w}^T+b||\)与\(||\boldsymbol{w}||\)的值也都是任意的，这增加了求解优化问题的难度。因此，我们需要对上述的优化问题做一些修改，使其变成容易求解的形式。

由于我们在优化样本与超平面之间的距离时，其实只需要考虑的是距离超平面最近的那些样本点；加之\(\boldsymbol{w}\)和\(b\)的取值没有限制，所以\(||\boldsymbol{x}_i\boldsymbol{w}^T+b||\)的取值也可以为任何正实数。因此，我们不妨对\(\boldsymbol{w}\)和\(b\)的取值做一些限制，使得那些距离超平面最近的样本点（即支持向量），表达式\(||\boldsymbol{x}_i\boldsymbol{w}^T+b||=1\)成立。这样也意味着，对于其它距离超平面\(\boldsymbol{x}\boldsymbol{w}^T+b=0\)不是最近的样本点来说，必然有\(||\boldsymbol{x}_i\boldsymbol{w}^T+b||>1\)。如下图所示：

img

通过对\(\boldsymbol{w}\)和\(b\)的取值进行约束之后，SVM的优化问题变为下面这种比较简单的表示形式： \[ \max~\frac{1}{||\boldsymbol{w}||} \\ s.t.~~y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge 1 \] 由于求\(\frac{1}{||w||}\)的最大值其实相当于是求\(\frac{1}{2}||w||^2\)的最小值（通过这样的转换，在求解优化问题的时候能够使得表达式更加简洁，同时也方便后续的求解过程），因此上述优化问题等价于： \[ \min~\frac{1}{2}||\boldsymbol{w}||^2 \\ s.t.~~y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge 1 \]

备注：

在一些介绍SVM的相关文章或者书籍中，\(||\boldsymbol{x}_i\boldsymbol{w}^T+b||\)被称作函数距离，\(\frac{||\boldsymbol{x}_i\boldsymbol{w}^T+b||}{||\boldsymbol{w}||}\)被称作几何距离。函数距离可以为任意的非负实数，而几何距离则为点到直线的真实距离。

求解优化问题

说明：此处涉及到的一些数学概念可以参考本文的附录部分。

通过对上述的表达式使用拉格朗日乘子法，我们可以得到： \[ \mathcal{L}(\boldsymbol{w},b,\alpha_i)=\frac{1}{2}||\boldsymbol{w}||^2-\sum_{i=1}^{n}\alpha_i[y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)-1] \\ s.t.~ \alpha_i\ge 0 \] 因此，我们的优化目标为： \[ \min_{\boldsymbol{w},b}\max_{\alpha_i \ge 0}\mathcal{L}(\boldsymbol{w},b,\alpha_i) \] 由于这一优化问题满足KKT条件与Slater条件，因此可以通过求解如下的对偶问题，来获得原始问题的解： \[ \max_{\alpha_i \ge 0}\min_{\boldsymbol{w},b}\mathcal{L}(\boldsymbol{w},b,\alpha_i) \] 对于上述的对偶问题，我们首先求解\(\min_{\boldsymbol{w},b}\mathcal{L}(\boldsymbol{w},b,\alpha_i)\)。分别对\(\boldsymbol{w}\)和\(b\)求偏导，可得： \[ \frac{\partial \mathcal{L}}{\partial \boldsymbol{w}}=\boldsymbol{w}-\sum_{i=1}^{n}\alpha_iy_i\boldsymbol{x}_i \\ \frac{\partial \mathcal{L}}{\partial b}=-\sum_{i=1}^{n}\alpha_iy_i \] 令上述两个偏导数的值为0，我们可得： \[ \boldsymbol{w}=\sum_{i=1}^{n}\alpha_iy_i\boldsymbol{x}_i \\ \sum_{i=1}^{n}\alpha_iy_i=0\\ \] 将上述两式代入到\(\mathcal{L}(\boldsymbol{w},b,\alpha_i)\)的表达式中，可得： \[ \min_{\boldsymbol{w},b}\mathcal{L}(\boldsymbol{w},b,\alpha_i)=\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i\boldsymbol{x}_j^T \] 这样，待优化表达式中便只剩下\(\alpha_i\)。接下来我们便可以通过优化\(\alpha_i\)的取值，来求解\(\max_{\alpha_i}\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i\boldsymbol{x}_j^T\)。这一求解过程可以通过SMO算法来求解，在下文中会对其进行详细说明。最终，在得到一系列的\(\alpha_i\)的取值之后，我们便可以通过\(\boldsymbol{w}=\sum_{i=1}^{n}\alpha_iy_i\boldsymbol{x}_i\)来计算得到\(\boldsymbol{w}\)的值，然后使用支持向量去计算\(b\)的值。

软间隔SVM

优化问题的修改

在上面的硬间隔SVM中，我们假设原始数据是线性可分的情况。但是在实际中，由于噪声以及离群点的影响，常常会遇到数据线性不可分的情况；也或者是数据虽然线性可分，但是硬间隔SVM得到的超平面与支持向量之间的距离很近（也就是说支持向量与超平面形成的间隔过窄），从而出现过拟合的现象。此时可以对约束条件进行一些松弛，允许部分样本落入到间隔内，甚至是被分类到错误的类别中去。这样得到的SVM模型被称为软间隔SVM。

对于软间隔SVM，它的优化问题如下： \[ \min~\frac{1}{2}||\boldsymbol{w}||^2+C\sum_{i=1}^{n}\xi_i \\ \begin{aligned} s.t.~&y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge 1-\xi_i\\ &\xi_i\ge 0 \end{aligned} \] 其中\(C>0\)为模型的超参数，代表对落入间隔或者被错误分类的样本的惩罚。\(C\)的值越大，代表惩罚越大，如果\(C=+\infty\)则变成了硬间隔SVM。

求解优化问题

对于这一优化问题，我们同样使用拉格朗日乘子法进行求解。首先构造如下的拉格朗日函数： \[ \mathcal{L}(\boldsymbol{w},b,\alpha_i,\beta_i,\xi_i)=\frac{1}{2}||\boldsymbol{w}||^2+C\sum_{i=1}^{n}\xi_i-\sum_{i=1}^{n}\alpha_i[y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)-1+\xi_i]-\sum_{i=1}^{n}\beta_i\xi_i \\ \begin{aligned} s.t.~& \alpha_i\ge 0 \\ &\beta_i\ge 0 \end{aligned} \] 因此，我们的优化目标为： \[ \min_{\boldsymbol{w},b,\xi_i}\max_{\alpha_i \ge 0,\beta_i \ge 0}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\beta_i,\xi_i) \] 类似地，这一优化问题满足KKT条件与Slater条件，因此可以通过求解如下的对偶问题，来获得原始问题的解： \[ \max_{\alpha_i \ge 0,\beta_i \ge 0}\min_{\boldsymbol{w},b,\xi_i}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\beta_i,\xi_i) \] 对于上述的对偶问题，我们首先求解\(\min_{\boldsymbol{w},b}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\beta_i,\xi_i)\)。分别对\(\boldsymbol{w}\)，\(b\)和\(\xi_i\)求偏导，可得： \[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial \boldsymbol{w}}&=\boldsymbol{w}-\sum_{i=1}^{n}\alpha_iy_i\boldsymbol{x}_i \\ \frac{\partial \mathcal{L}}{\partial b}&=-\sum_{i=1}^{n}\alpha_iy_i \\ \frac{\partial \mathcal{L}}{\partial \xi_i}&=C-\alpha_i-\beta_i \end{aligned} \] 令上述三个偏导数的值为0，我们可得： \[ \boldsymbol{w}=\sum_{i=1}^{n}\alpha_iy_i\boldsymbol{x}_i \\ \sum_{i=1}^{n}\alpha_iy_i=0\\ \alpha_i+\beta_i=C \] 将上述三式代入到\(\mathcal{L}(\boldsymbol{w},b,\alpha_i,\beta_i,\xi_i)\)的表达式中，可以消去所有关于\(\xi_i\)的表达式，但是表达式\(\alpha_i+\beta_i=C\)却为\(\alpha_i\)加入了新的限制条件。此时可得： \[ \min_{\boldsymbol{w},b}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\beta_i,\xi_i)=\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i\boldsymbol{x}_j^T \\ s.t.~0\le \alpha_i \le C \] 接下来便是通过优化\(\alpha_i\)来求解优化问题\(\max_{\alpha_i}\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i\boldsymbol{x}_j^T\)，这一问题的求解与硬间隔SVM一样使用SMO算法，但是在优化过程中需要对\(\alpha_i\)的取值进行限制。

从损失函数角度看SVM

SVM的另一个解读是从它的损失函数出发。考虑如下的折页损失函数（Hinge Loss）： \[ L(\boldsymbol{x},y)=\max[0,1-y(\boldsymbol{x}\boldsymbol{w}^T+b)] \] 折页损失函数的值与支持向量机模型的分类结果有如下几种对应的情形：

  1. \(y\)与\(\boldsymbol{x}\boldsymbol{w}^T+b\)同号，且\(||\boldsymbol{x}\boldsymbol{w}^T+b||>1\)。代表样本被正确分类，且样本在分类间隔的两侧。此时\(1-y(\boldsymbol{x}\boldsymbol{w}^T+b)<0\)，因此对应的损失函数值为0。
  2. \(y\)与\(\boldsymbol{x}\boldsymbol{w}^T+b\)同号，且\(||\boldsymbol{x}\boldsymbol{w}^T+b||=1\)。代表样本被正确分类，且样本刚好位于分类间隔的边界处。此时\(1-y(\boldsymbol{x}\boldsymbol{w}^T+b)=0\)，对应于损失函数的临界值。
  3. \(y\)与\(\boldsymbol{x}\boldsymbol{w}^T+b\)同号，但\(0\le ||\boldsymbol{x}\boldsymbol{w}^T+b||< 1\)；或\(y\)与\(\boldsymbol{x}\boldsymbol{w}^T+b\)异号。代表样本点落在分类间隔内，或是被错误分类。此时\(1-y(\boldsymbol{x}\boldsymbol{w}^T+b)>0\)，因此损失函数的值也为\(1-y(\boldsymbol{x}\boldsymbol{w}^T+b)\)。

因此，SVM的损失函数\(\ell(\boldsymbol{w},b)\)相当于是带有L2正则化的折页损失函数，即： \[ \ell(\boldsymbol{w},b)=\sum_{i=0}^{n} \max[0,1-y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)]+\lambda||\boldsymbol{w}||^2 \] SVM的优化过程就是求\(\ell(\boldsymbol{w},b)\)的最小值。

我们令\(\max[0,1-y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)]=\xi_i\)，其中\(\xi_i\ge 0\)。因此有：\(1-y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\le \xi_i\)，也就是\(y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge 1-\xi_i\)。将其代入到\(\ell(\boldsymbol{w},b)\)中，可得： \[ \ell(\boldsymbol{w},b)=\sum_{i=0}^{n}\xi_i+\lambda||\boldsymbol{w}||^2 \\ \begin{aligned} s.t.~&y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge 1-\xi_i \\ &\xi_i\ge 0 \end{aligned} \] 因此，求解\(\ell(\boldsymbol{w},b)\)的最小值等价于软间隔SVM的优化问题。这一优化问题的求解可参考软间隔SVM部分，不再赘述。

支持向量机回归

问题导出

支持向量机模型也可以用来解决回归问题。使用SVM做回归问题时，使用如下的\(\epsilon\)-sensitive误差函数来计算回归误差： \[ L(\boldsymbol{x},y)=\max[0,|y-(\boldsymbol{x}\boldsymbol{w}^T+b)|-\epsilon] \] 其中，\(\epsilon>0\)代表模型的超参数。

如果从几何角度考虑这一损失函数，相当于是超平面\(y=\boldsymbol{x}\boldsymbol{w}^T+b+\epsilon\)与\(y=\boldsymbol{x}\boldsymbol{w}^T+b-\epsilon\)构成了一个宽度为\(2\epsilon\)的间隔。当样本点落在这一间隔内时，对应损失函数的值为0；而样本落在这一间隔外时，对应损失函数的值大于0。在对一个未知样本点做预测时，通过\(y=\boldsymbol{x}\boldsymbol{w}^T+b\)进行预测，相当于是取间隔的中间位置。如下图所示：

在这里插入图片描述

与支持向量机做分类时类似，支持向量机回归的损失函数\(\ell(\boldsymbol{w},b)\)也是带有L2正则化的\(\epsilon\)-sensitive损失函数： \[ \ell(\boldsymbol{w},b)=\sum_{i=1}^{n}\max[0,|y_i-(\boldsymbol{x}_i\boldsymbol{w}^T+b)|-\epsilon]+\lambda||\boldsymbol{w}||^2 \] 求解模型参数即为求解优化问题\(\min_{\boldsymbol{w},b}\ell(\boldsymbol{w},b)\)。为此，我们为每个样本点引入两个约束变量\(\xi_i\ge 0\)和\(\xi_i'\ge 0\)，使得\(y_i-(\boldsymbol{x}_i\boldsymbol{w}^T+b)>0\)时，有\(y_i-(\boldsymbol{x}_i\boldsymbol{w}^T+b)-\xi_i \le \epsilon\)；\(y_i-(\boldsymbol{x}_i\boldsymbol{w}^T+b)<0\)时，有\((\boldsymbol{x}_i\boldsymbol{w}^T+b)-y_i-\xi_i' \le \epsilon\)。这样我们便可以得到如下的优化问题： \[ \min_{\boldsymbol{w},b}~\sum_{i=1}^{n}(\xi_i+\xi_i')+\lambda||\boldsymbol{w}||^2 \\ \begin{aligned} s.t.~&y_i-(\boldsymbol{x}_i\boldsymbol{w}^T+b)-\xi_i \le \epsilon \\ &(\boldsymbol{x}_i\boldsymbol{w}^T+b)-y_i-\xi_i' \le \epsilon \\ &\xi_i\ge 0 \\ &\xi_i'\ge 0 \end{aligned} \] 上述的优化问题可以改写为等价问题： \[ \min_{\boldsymbol{w},b}~C\sum_{i=1}^{n}(\xi_i+\xi_i')+\frac{1}{2}||\boldsymbol{w}||^2 \\ \begin{aligned} s.t.~&y_i-(\boldsymbol{x}_i\boldsymbol{w}^T+b)-\xi_i \le \epsilon \\ &(\boldsymbol{x}_i\boldsymbol{w}^T+b)-y_i-\xi_i' \le \epsilon \\ &\xi_i\ge 0 \\ &\xi_i'\ge 0 \end{aligned} \]

求解优化问题

为了求解这一问题，我们构造拉格朗日函数： \[ \mathcal{L}(\boldsymbol{w},b,\alpha_i,\alpha_i',\beta_i,\beta_i',\xi_i,\xi_i')=\frac{1}{2}||\boldsymbol{w}||^2+C\sum_{i=1}^{n}(\xi_i+\xi_i')-\sum_{i=1}^{n}\alpha_i(\xi_i+\epsilon-y_i+\boldsymbol{x}_i\boldsymbol{w}^T+b)-\sum_{i=1}^{n}\alpha_i'(y_i-\boldsymbol{x}_i\boldsymbol{w}^T-b+\epsilon+\xi_i')-\sum_{i=1}^{n}\beta_i \xi_i-\sum_{i=1}^{n}\beta_i \xi_i' \\ \begin{aligned} s.t.~&\alpha_i\ge 0\\ &\alpha_i'\ge 0\\ &\beta_i\ge 0 \\ &\beta_i'\ge 0 \end{aligned} \]

因此，我们的优化目标为： \[ \min_{\boldsymbol{w},b,\xi_i}\max_{\alpha_i \ge 0,\alpha_i'\ge 0,\beta_i\ge 0}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\alpha_i',\beta_i,\beta_i',\xi_i,\xi_i') \] 类似地，这一优化问题满足KKT条件与Slater条件，因此可以通过求解如下的对偶问题，来获得原始问题的解： \[ \max_{\alpha_i \ge 0,\alpha_i'\ge 0,\beta_i \ge 0,\beta_i' \ge 0}\min_{\boldsymbol{w},b,\xi_i,\xi_i'}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\alpha_i',\beta_i,\beta_i',\xi_i,\xi_i') \] 对于上述的对偶问题，我们首先求解\(\min_{\boldsymbol{w},b,\xi_i,\xi_i'}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\alpha_i',\beta_i,\beta_i',\xi_i,\xi_i')\)。分别对\(\boldsymbol{w}\)，\(b\)，\(\xi_i\)和\(\xi_i'\)求偏导，可得： \[ \begin{aligned} \frac{\partial \mathcal{L}}{\partial \boldsymbol{w}}&=\boldsymbol{w}-\sum_{i=1}^{n}\alpha_i\boldsymbol{x}_i+\sum_{i=1}^{n}\alpha_i'\boldsymbol{x}_i \\ \frac{\partial \mathcal{L}}{\partial b}&=\sum_{i=1}^{n}\alpha_i'-\sum_{i=1}^{n}\alpha_i \\ \frac{\partial \mathcal{L}}{\partial \xi_i}&=C-\alpha_i-\beta_i\\ \frac{\partial \mathcal{L}}{\partial \xi_i'}&=C-\alpha_i'-\beta_i' \end{aligned} \] 令上述四个偏导数的值为0，我们可得： \[ \boldsymbol{w}=\sum_{i=1}^{n}(\alpha_i'-\alpha_i)\boldsymbol{x}_i \\ \sum_{i=1}^{n}(\alpha_i'-\alpha_i)=0\\ \alpha_i+\beta_i=C \\ \alpha_i'+\beta_i'=C \] 将上述四式代入到\(\min_{\boldsymbol{w},b,\xi_i,\xi_i'}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\alpha_i',\beta_i,\beta_i',\xi_i,\xi_i')\)的表达式中，可得： \[ \min_{\boldsymbol{w},b,\xi_i,\xi_i'}\mathcal{L}(\boldsymbol{w},b,\alpha_i,\alpha_i',\beta_i,\beta_i',\xi_i,\xi_i')=-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}(\alpha_i'-\alpha_i)(\alpha_j'-\alpha_j)\boldsymbol{x}_i\boldsymbol{x}_j-\sum_{i=1}^{n}(\alpha_i'-\alpha_i)y_i-\sum_{i=1}^{n}(\alpha_i'+\alpha_i)\epsilon \\ \begin{aligned} s.t.~&\sum_{i=1}^{n}(\alpha_i'-\alpha_i)=0\\ &0\le \alpha_i\le C \\ &0\le \alpha_i'\le C \end{aligned} \] 之后便可以使用SMO算法进行求解。

模型求解—SMO算法

迭代公式的导出

SMO算法来自于论文《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》。这一算法的思想是每次从所有的\(\alpha_i\)中随机抽取出任意两个\(\alpha_1\)和\(\alpha_2\)，固定其它所有的\(\alpha_i\)，使得目标函数只是关于\(\alpha_1\)和\(\alpha_2\)的函数，然后求解这一子问题。通过这样不断地迭代求解子问题，从而最终达到求解原问题的目的。因此需要注意，在下面的推导过程中，\(\alpha_1\)和\(\alpha_2\)可以对应于任意两个约束条件的乘子。

回顾SVM最终需要优化的问题： \[ \max_{\alpha_i}~\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i\boldsymbol{x}_j^T \\ \] 按照SMO算法的思路，子问题的目标函数可以写作： \[ \Psi(\alpha_1,\alpha_2)=\alpha_1+\alpha_2-\frac{1}{2}K_{11}\alpha_1^2-\frac{1}{2}K_{22}\alpha_2^2-y_1y_2K_{12}\alpha_1\alpha_2-v_1y_1\alpha_1-v_2y_2\alpha_2+\text{const} \]

其中： \[ K_{ij}=\boldsymbol{x}_i\boldsymbol{x}_j^T \\ v_i=\sum_{j=3}^{n}y_j\alpha_jK_{ij} \]

令\(f(\boldsymbol{x})=\boldsymbol{x}\boldsymbol{w}^T+b=\sum_{i=1}^{n}y_i\alpha_i\boldsymbol{x}\boldsymbol{x}_i^T+b\)，因此\(v_i\)也可以记作如下的格式（这在后面的推导中将会用到）： \[ v_i=f(\boldsymbol{x}_i)-y_1\alpha_1K_{1i}-y_2\alpha_2K_{2i}-b \] 假设选取的两个乘子\(\alpha_1\)和\(\alpha_2\)在更新之前的值为\(\alpha_1^{old}\)和\(\alpha_2^{old}\)，更新之后为\(\alpha_1^{new}\)和\(\alpha_2^{new}\)，那么它们更新前后满足如下的约束关系： \[ \alpha_1^{old}y_1+\alpha_2^{old}y_2=\alpha_1^{new}y_1+\alpha_2^{new}y_2=\zeta \] 其中\(\zeta\)为一个常数，\(\zeta=-\sum_{i=3}^{n}\alpha_iy_i\)。

由于同时求解两个乘子较困难，因此可以先计算\(\alpha_2^{new}\)，然后再通过\(\alpha_2^{new}\)来表示\(\alpha_1^{new}\)。

首先我们可以根据约束条件\(\sum_{i=1}^{n}\alpha_iy_i=0\)，消掉\(\Psi(\alpha_1,\alpha_2)\)中的\(\alpha_1\)。在关系式\(\alpha_1y_1+\alpha_2y_2=\zeta\)的两端同时乘上\(y_1\)，可得： \[ \alpha_1=y_1\zeta-y_1y_2\alpha_2 \] 将上式代入到\(\Psi(\alpha_1,\alpha_2)\)的表达式中，\(\Psi\)就变成了关于\(\alpha_2\)的一元函数： \[ \Psi(\alpha_2)=y_1\zeta-y_1y_2\alpha_2+\alpha_2-\frac{1}{2}K_{11}(y_1\zeta-y_1y_2\alpha_2)^2-\frac{1}{2}K_{22}\alpha_2^2-K_{12}(y_2\zeta-\alpha_2)\alpha_2-v_1(\zeta-y_2\alpha_2)-v_2y_2\alpha_2+\text{const} \] 接下来我们对\(\alpha_2\)求导，可得： \[ \frac{d\Psi}{d\alpha_2}=-y_1y_2+1+K_{11}(y_2\zeta-\alpha_2)-K_{22}\alpha_2-K_{12}(y_2\zeta-2\alpha_2)+v_1y_2-v_2y_2 \] 令\(\frac{d\Psi}{d\alpha_2}=0\)，并将上式中的\(1\)替换为\(y_2y_2\)，便可以得到求解\(\alpha_2^{new}\)的表达式： \[ (K_{11}+K_{22}-2K_{12})\alpha_2^{new}=(K_{11}-K_{12})y_2\zeta+(v_1^{old}-v_2^{old}+y_2-y_1)y_2 \] 在上式中，由于每一次迭代计算时选取的\(\alpha_1\)和\(\alpha_2\)都不同，这就要求每次迭代的时候都要计算一次\(v_1\)、\(v_2\)的值，增加了不少的计算开支。因此，我们考虑对\(v_1-v_2\)进行化简，可得： \[ \begin{aligned} v_1-v_2=&f(\boldsymbol{x}_1)-y_1\alpha_1K_{11}-y_2\alpha_2K_{21}-f(\boldsymbol{x}_2)+y_1\alpha_1K_{12}+y_2\alpha_2K_{22} \\ =&f(\boldsymbol{x}_1)-f(\boldsymbol{x}_2)+y_1\alpha_1(K_{12}-K_{11})+y_2\alpha_2(K_{22}-K_{12}) \\ =&f(\boldsymbol{x}_1)-f(\boldsymbol{x}_2)+y_1(y_1\zeta-y_1y_2\alpha_2)(K_{12}-K_{11})+y_2\alpha_2(K_{22}-K_{12}) \\ =&f(\boldsymbol{x}_1)-f(\boldsymbol{x}_2)+\zeta(K_{12}-K_{11})+y_2\alpha_2(K_{11}+K_{22}-2K_{12}) \end{aligned} \] 将其代入到求解\(\alpha_2^{new}\)的表达式中，可得： \[ (K_{11}+K_{22}-2K_{12})\alpha_2^{new}=(K_{11}+K_{22}-2K_{12})\alpha_2^{old}+[f(\boldsymbol{x}_1)-f(\boldsymbol{x}_2)+y_2-y_1]y_2 \] 在上式中，我们记\(\eta=(K_{11}+K_{22}-2K_{12})\)，\(e_i=f(\boldsymbol{x}_i)-y_i=\sum_{j=1}^{n}y_j\alpha_j\boldsymbol{x}_i\boldsymbol{x}_j^T+b-y_i\)，便可得到计算\(\alpha_2^{new}\)的表达式： \[ \alpha_2^{new}=\alpha_2^{old}+\frac{(e_1-e_2)y_2}{\eta} \] 这样，我们便可通过\(\alpha_2^{old}\)计算出\(\alpha_2^{new}\)，而\(\alpha_1^{new}\)可以通过\(\alpha_1^{new}=\alpha_1^{old}+(\alpha_2^{old}-\alpha_2^{new})y_1y_2\)来计算。

迭代结果的修剪

上面得出的迭代公式可以直接用来迭代求解硬间隔SVM的\(\alpha_i\)。但是对于软间隔SVM来说，由于限制条件\(0\le \alpha_i \le C\)的加入，就要求我们在迭代求解的每一步都需要对计算结果进行修剪。同时需要注意的是，在计算\(\alpha_1^{new}\)时，需要先对\(\alpha_2^{new}\)的结果进行修剪之后再计算。

首先我们确定\(\alpha_2^{new}\)的取值范围，假设它的取值范围是\(L\le \alpha_2^{new}\le H\)，我们分不同情况来讨论\(L\)和\(H\)的取值：

  • \(y_1\ne y_2\)：此时有\(\alpha_1^{new}-\alpha_2^{new}=\zeta\)或\(\alpha_2^{new}-\alpha_1^{new}=\zeta\)，结合约束条件\(0<\alpha_1^{new}<C\)与\(0<\alpha_2^{new}<C\)，可得，
    • 当\(\alpha_1^{new}-\alpha_2^{new}=\zeta\)时，\(L=\max(0,-\zeta)\)，\(H=\min(C-\zeta,C)\)。
    • 当\(\alpha_2^{new}-\alpha_1^{new}=\zeta\)时，\(L=\max(0,\zeta)\)，\(H=\min(C+\zeta,C)\)。
  • \(y_1=y_2\)：此时有\(\alpha_1^{new}+\alpha_2^{new}=\zeta\)，结合约束条件\(0<\alpha_1^{new}<C\)与\(0<\alpha_2^{new}<C\)可得\(L=\max(0,\zeta-C)\)，\(H=\min(C,\zeta)\)

可以用下图来标识上述的两种情况：

这里写图片描述

接下来，我们便可以根据所确定的\(L\)与\(R\)的值来对\(\alpha_2^{new,unclipped}\)的值进行修剪： \[ \alpha_2^{new}= \begin{cases} \begin{aligned} L~~~~~~~~~~~~~~~~~~~~~&\alpha_2^{new,unclipped}<L \\ \alpha_2^{new,unclipped}~~~&L\le \alpha_2^{new,unclipped}\le H \\ H~~~~~~~~~~~~~~~~~~~~& H<\alpha_2^{new,unclipped} \end{aligned} \end{cases} \]

临界情况的处理

大部分情况下都有\(\eta>0\)成立，但是当\(\boldsymbol{x}_1\)与\(\boldsymbol{x}_2\)共线的时候，\(\eta=0\)；如果使用了不满足Mercer定理的核函数（即使用核函数\(\kappa\)将运算\(\boldsymbol{x}_i\boldsymbol{x}_j^T\)替换为\(\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)\)），会出现\(\eta<0\)的情况。对于这些情况，需要做一些特殊的处理。

此时，分别取\(\alpha_2^{new}=L\)和\(\alpha_2^{new}=H\)，计算出相应的\(\alpha_1^{new}\)，然后将其代入到\(\Psi(\alpha_1,\alpha_2)\)中，取\(\Psi\)较大的一组作为\(\alpha_1^{new}\)和\(\alpha_2^{new}\)的值。

偏置的更新

在更新完\(\alpha_1\)和\(\alpha_2\)的值之后，我们还需要更新偏置\(b\)的值，它关系到\(f(\boldsymbol{x})\)的计算，从而影响到\(e_i\)的计算。

\(b\)的更新方式可以分为如下三种情况：

  1. 如果在硬间隔SVM中\(\alpha_1>0\)，软间隔SVM中\(0<\alpha_1<C\)，此时\(y_1(\boldsymbol{x}_1\boldsymbol{w}^T+b)=1\)成立，据此可以算出更新后的\(b\)值。
  2. 如果在硬间隔SVM中\(\alpha_2>0\)，软间隔SVM中\(0<\alpha_2<C\)，此时\(y_2(\boldsymbol{x}_2\boldsymbol{w}^T+b)=1\)成立，据此可以算出更新后的\(b\)值。需要说明的是，如果1和2同时满足，它们计算出的\(b\)值应该是相等的。
  3. 以上都不满足，此时按照\(y_1(\boldsymbol{x}_1\boldsymbol{w}^T+b)=1\)和\(y_2(\boldsymbol{x}_2\boldsymbol{w}^T+b)=1\)可以分别算出\(b_1\)和\(b_2\)，最终取\(b=\frac{1}{2}(b_1+b_2)\)。

按照上述的分析，可以将\(b\)的更新方法总结如下： \[ b^{new}= \begin{cases} \begin{aligned} b_1~~~~~~~~~~~&if~~0<\alpha_1<C\\ b_2~~~~~~~~~~~&else~if~~0<\alpha_2<C\\ \frac{b_1+b_2}{2}~~&else \end{aligned} \end{cases} \] 其中， \[ b_1=-e_1-y_1K_{11}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{12}(\alpha_2^{new}-\alpha_2^{old})+b^{old} \\ b_2=-e_2-y_1K_{12}(\alpha_1^{new}-\alpha_1^{old})-y_2K_{22}(\alpha_2^{new}-\alpha_2^{old})+b^{old} \]

变量的选择

上述分析是在\(N\)个\(\alpha_i\)中随机选出两个变量进行优化的方法，接下来的问题便是考虑如何选择\(\alpha_1\)和\(\alpha_2\)（其实也就是选择它们相对应的样本点），从而使得目标函数下降地最快。

具体来说，第一个变量\(\alpha_1\)的选择被称为外循环，它是违反KKT条件最严重的；而另外一个变量\(\alpha_2\)的选择被称为内循环，它的选择希望能够在优化过程中使得\(\alpha_2\)有较大的变化。

备注：

以软间隔SVM为例，根据KKT条件，SVM在优化过程中所对应的\(\alpha_i\)的含义如下：

  • \(\alpha_i=0\)：\(y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\ge 1\)，代表样本点被正确分类或是在间隔边界上
  • \(0<\alpha_i<C\)：\(y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)=1\)，代表样本点在间隔边界上
  • \(\alpha_i=C\)：\(y_i(\boldsymbol{x}_i\boldsymbol{w}^T+b)\le 1\)（因此时\(\beta_i=0\)），样本点可能在间隔边界上，可能在间隔边界之间，也可能被错误分类

违反KKT条件的意思便是上述的对应关系不满足。

但是需要说明的是，满足条件\(\alpha_i>0\)所对应的那些点都被称为支持向量（此处参考《统计学习方法》中的叙述）。

优缺点

优点：

  1. SVM 的最终决策函数只由少数的支持向量所确定，计算的复杂性取决于支持向量的数目，而不是样本空间的维数，这在某种意义上避免了维数灾难；
  2. 少数支持向量决定了最终结果，这不但可以剔除大量冗余样本，而且具有较好的鲁棒性。

缺点：

  1. SVM算法对大规模训练样本的训练较慢；
  2. SVM本身只能做二分类，如果要解决多分类问题则需要构造多个模型；
  3. 对参数和核函数的选择敏感

代码示例

分类

我们使用Sklearn自带的Iris数据集，来演示如何用sklearn中的支持向量机分类器做分类任务。

Iris数据集的四个特征分别为：sepal length (cm)、sepal width (cm)、petal length (cm)、petal width (cm)，三种不同的类别0、1、2分别对应于Iris-Setosa、Iris-Versicolour和Iris-Virginica这三类。

为了方便做可视化，我们对数据进行精简，只选取2、3两列来训练与预测模型。我们取petal length (cm)和petal width (cm)这两个特征来训练和预测。

1
2
3
4
5
6
7
8
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC,LinearSVC
from sklearn.metrics import confusion_matrix
from sklearn.preprocessing import KBinsDiscretizer
1
2
3
X,y=load_iris(return_X_y=True)
X=X[:,2:4]
train_x,test_x,train_y,test_y=train_test_split(X,y,test_size=0.3)

支持向量机分类器SVC的主要参数包括：

  • C：惩罚因子，C越大则对误分类的惩罚越大
  • kernel：代表使用的核函数，默认为高斯核
  • degree：使用多项式核时，多项式的阶数，默认为3
  • gamma：默认使用'scale'，代表自动选取；也可以自己传入数值。这一参数适用于rbf、poly和sigmoid三个核函数
  • coef0：核函数中的独立参数，适用于poly和sigmoid核函数

此外，Sklearn还提供了LinearSVC线性分类器，与SVC相比，它默认使用线性核，默认的损失函数为squared_hinge。它的重要参数包括：

  • penalty：正则项，默认为l2，也可以改为l1
  • loss：损失函数，默认为squared_hinge，也可以改为hinge
  • C：对于误分类样本的惩罚因子，C越大则对误分类的惩罚越大

由于二者的用法类似，因此我们以SVC为例来展示其用法。同时为了比较不同核函数的区别，我们分别作图展示在使用linear、poly、rbf三种核函数时，其得到的分类边界。

1
2
3
X_mesh,Y_mesh=np.meshgrid(np.linspace(0,8,200),np.linspace(0,5,100))
XY_mesh=np.concatenate([X_mesh.reshape(-1,1),Y_mesh.reshape(-1,1)],axis=1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
kernels=['linear','rbf','poly']
fig=plt.figure(figsize=(15,3))
axes=fig.subplots(1,3)
for i in range(3):
    clf=SVC(kernel=kernels[i],gamma=2)
    clf.fit(train_x,train_y)
    mesh=clf.predict(XY_mesh)
    axes[i].set_title('kernel function: {}'.format(kernels[i]))
    axes[i].set_xlabel('sepal length (cm)')
    axes[i].set_ylabel('sepal width (cm)')
    contour=axes[i].contourf(X_mesh,Y_mesh,mesh.reshape(X_mesh.shape),cmap='Greys')
    fig.colorbar(contour,ax=axes[i])
    axes[i].scatter(test_x[test_y==0][:,0],test_x[test_y==0][:,1],label='Iris-Setosa')
    axes[i].scatter(test_x[test_y==1][:,0],test_x[test_y==1][:,1],label='Iris-Versicolour')
    axes[i].scatter(test_x[test_y==2][:,0],test_x[test_y==2][:,1],label='Iris-Virginica')
    axes[i].legend()
SVC示例

回归

我们使用Sklearn自带的Diabetes数据集，来演示如何用sklearn中的SVM做回归任务。

这一数据集共有10个特征，且这些特征都已经被标准化至\((-2,2)\)区间内，待预测的值是25-346范围内的整数。由于我们的目的主要是说明模型的用法，因此省略了特征工程的步骤，将这些数据直接用来训练模型。

1
2
3
from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split
from sklearn.svm import LinearSVR, SVR
1
2
X,y=load_diabetes(return_X_y=True)
train_x,test_x,train_y,test_y=train_test_split(X,y,test_size=0.3)

LinearSVR回归器的主要参数有：

  • epsilon：代表epsilon-insensitive损失函数中的epsilon参数，相当于是误差在0-epsilon范围内都会被记作0。默认值为0
  • C：正则参数，数值越大则对于模型参数的惩罚力度越小。默认值为1.0
  • loss：模型的损失函数，可以选择'epsilon-insensitive'或者'squared_epsilon-insensitive'。默认为'epsilon-insensitive'

SVR回归器的主要参数有：

  • kernel：模型使用的核函数，可以选择'linear', 'poly', 'rbf', 'sigmoid', 'precomputed'，或是自己传入一个函数。默认为'rbf'
  • degree：使用'poly'核时多项式的系数。默认为3
  • gamma：使用'rbf', 'poly'和'sigmoid'三种核函数时，核函数中的gamma参数。默认为'scale'，也可以传入'auto'，或者是一个浮点数
  • coef0：使用'poly'和'sigmoid'核函数时，核函数中的独立项。默认为0
  • epsilon：代表epsilon-insensitive损失函数中的epsilon参数，相当于是误差在0-epsilon范围内都会被记作0。默认值为0.1
  • C：正则参数，数值越大则对于模型参数的惩罚力度越小。默认值为1.0

LinearSVR相当于是SVR在使用线性核时的特殊情况，但是SVR默认使用epsilon-insensitive损失函数且不能修改。

1
2
3
4
reg=SVR()
reg.fit(train_x,train_y)
pred=reg.predict(test_x)
errors=pred-test_y

附：广义约束优化问题

拉格朗日乘子法与KKT条件

给定如下的约束优化问题 \[ \max_{\boldsymbol{x}}f(\boldsymbol{x}) \\ \begin{aligned} s.t. ~&g_i(\boldsymbol{x})\le0,i=1,2,\dots,p \\ &h_j(\boldsymbol{x})=0,j=1,2,\dots,q \end{aligned} \] 也就是说，函数\(f(\boldsymbol{x})\)的自变量为一个\(n\)维向量，要最大化的目标函数\(f(\boldsymbol{x})\)满足若干的等式和不等式约束（如果优化目标是求\(\min_{\boldsymbol{x}}f(\boldsymbol{x})\)，则将约束条件中的不等关系改为\(g_i(\boldsymbol{x})\ge 0\)即可，下面的内容中不再赘述）。我们可以构造如下的拉格朗日函数： \[ \mathcal{L}(\boldsymbol{x},\mu,\lambda)=f(\boldsymbol{x})-\sum_{i}\mu_i g_i(\boldsymbol{x})-\sum_{j}\lambda_j h_j(\boldsymbol{x}) \\ \] 其中，\(\mu_i\ge 0\)，\(\lambda_j\in R\)为拉格朗日乘子。

对于不等式约束，只要满足KKT条件，则依然可以使用拉格朗日乘子法解决。KKT条件是指，如果有一个点\(\boldsymbol{x}^*\)是满足上述所有约束的极值点，则如下关系成立： \[ \nabla f(\boldsymbol{x}^*)-\sum_{i}\mu_i\nabla g_i(\boldsymbol{x}^*)-\sum_{j}\lambda_j\nabla h_j(\boldsymbol{x}^*)=0 \\ \begin{aligned} s.t.~ &\mu_i\ge 0 \\ &\mu_i g_i(\boldsymbol{x}^*)=0 \\ &g_i(\boldsymbol{x}^*)\le 0\\ &h_j(\boldsymbol{x}^*)=0 \end{aligned} \] 也就是说，在这个极值点处，拉格朗日函数的梯度为0，相当于\(f\)的梯度是一系列的不等式约束\(g_i\)的梯度和等式约束\(h_i\)的梯度所形成的线性组合。在这个线性组合中，等式约束梯度的权值\(\lambda_j\)没有要求；不等式约束梯度的权值\(\mu_i\)为非负值。并且如果某个\(g_i(\boldsymbol{x}^*)\)严格小于0，那么这个约束不会出现在加权式中，也就是对于优化问题没有影响；只有\(\boldsymbol{x}^*\)恰好在边界\(g_i(\boldsymbol{x}^*)=0\)的那些\(g_i\)的梯度才对优化问题有影响，它们则会出现在加权式中。

如果KKT条件满足，则优化目标就变为求解拉格朗日函数\(\mathcal{L}(\boldsymbol{x},\mu,\lambda)\)的最大值。

在上面的表述中，如果去掉不等式约束的部分，就变成了等式约束条件下的拉格朗日乘子法。

拉格朗日对偶问题

考虑如下的约束优化问题： \[ \max_{\boldsymbol{x}}f(\boldsymbol{x}) \\ \begin{aligned} s.t. ~&g_i(\boldsymbol{x})\le0,i=1,2,\dots,p \\ &h_j(\boldsymbol{x})=0,j=1,2,\dots,q \end{aligned} \] 以及这一优化问题对应的拉格朗日函数： \[ \mathcal{L}(\boldsymbol{x},\mu,\lambda)=f(\boldsymbol{x})-\sum_{i}\mu_i g_i(\boldsymbol{x})-\sum_{j}\lambda_j h_j(\boldsymbol{x}) \\ \] 其中，\(\mu_i\ge 0\)，\(\lambda_j\in R\)为拉格朗日乘子。

对于上述的拉格朗日函数\(\mathcal{L}(\boldsymbol{x},\mu,\lambda)\)，当我们固定\(\boldsymbol{x}\)的值时，它满足如下关系： \[ f(\boldsymbol{x})=\min_{\mu_i\ge 0,\lambda} \mathcal{L}(\boldsymbol{x},\mu,\lambda)\le \mathcal{L}(\boldsymbol{x},\mu,\lambda) \] 由于在\(\mathcal{L}(\boldsymbol{x},\mu,\lambda)\)的表达式中，所有的\(h_j(\boldsymbol{x})\)项都为0，同时所有的\(\mu_ig_i(\boldsymbol{x}) \le 0\)恒成立，因此最小值只有在它们都取0的时候得到。反之，如果上述的任意一个约束条件不满足，则只需要令相应的乘子取无穷大，便可以取得\(f(\boldsymbol x)\rightarrow -\infty\)，这样便会导致问题无解，也就是说约束条件必须满足。因此，我们便得到了上述的不等关系。

经过这样的转变之后，我们便将约束融合到一起，得到了如下的无约束优化目标： \[ \max_{\boldsymbol{x}}f(\boldsymbol{x})=\max_{\boldsymbol{x}}\min_{\mu_i\ge 0,\lambda} \mathcal{L}(\boldsymbol{x},\mu,\lambda) \] 这一表达式与原优化问题等价，我们将其称为原始问题，并将其解记作\(\boldsymbol{p}^*\)。

在优化理论中，每个原始问题都有一个与之对应的对偶问题（对偶问题的对偶又会变成原问题）。无论原始问题是什么形式，对偶问题总是一个凸优化的问题，这样对于那些难以求解的原始问题 （甚至是 NP 问题），均可以通过转化为对偶问题。而且当满足一定条件时，原始问题与对偶问题的解是完全等价的。

接下来我们说明上述原始问题的对偶问题。首先为对偶问题定义如下的对偶函数： \[ D(\mu,\lambda)=\max_{\boldsymbol{x}}\mathcal{L}(\boldsymbol{x},\mu,\lambda) \] 根据这一对偶函数便可得到如下的对偶问题。它的形式与原始问题类似，只是交换了最小化和最大化的顺序： \[ \min_{\mu_i\ge 0,\lambda}\max_{\boldsymbol{x}} \mathcal{L}(\boldsymbol{x},\mu,\lambda) \] 我们定义对偶问题的解为\(\boldsymbol{d}^*\)，它与原始问题的解并不相同，而是满足\(\boldsymbol{d}^*\ge \boldsymbol{p}^*\)。这是因为： \[ D(\mu,\lambda)=\max_{\boldsymbol{x}}\mathcal{L}(\boldsymbol{x},\mu,\lambda)\ge \mathcal{L}(\boldsymbol{x},\mu,\lambda)\ge \min_{\mu_i\ge 0,\lambda} \mathcal{L}(\boldsymbol{x},\mu,\lambda)=f(\boldsymbol{x}) \] 也就是说，对偶问题中的最小值比原始问题中的最大值还要大。因此，我们通过对偶性，为原始问题引入了一个下界\(\boldsymbol{d}^*\ge \boldsymbol{p}^*\)。这一性质对于所有的优化问题都成立（即使原始问题非凸），被称为弱对偶性。其中，\(D(\mu,\lambda)-f(\boldsymbol{x})\)被称为对偶间隔，\(\boldsymbol{d}^*-\boldsymbol{p}^*\)被称作最优对偶间隔。

与弱对偶性相对应的一个概念为强对偶性，即满足\(\boldsymbol{d}^*=\boldsymbol{p}^*\)的优化问题。在强对偶成立的情况下，可以通过求解对偶问题来获得原始问题的解。对于上述优化问题来说，如果满足KKT条件（强对偶成立的必要条件）和Slater条件（强对偶成立的充分条件），那么强对偶性成立，即存在一组\(\boldsymbol{x}^*,\mu^*,\lambda^*\)使得原始问题与对偶问题的最优值相等。Slater条件是指原始问题为凸优化问题，且存在点\(\boldsymbol{x}\)，使得所有的\(g_i(\boldsymbol{x})<0\)成立。

参考

  1. 统计学习方法，李航
  2. 机器学习，周志华
  3. https://zhuanlan.zhihu.com/p/49331510
  4. https://blog.csdn.net/v_JULY_v/article/details/7624837
  5. https://blog.csdn.net/u013019431/article/details/79952483
  6. https://www.zhihu.com/question/23311674
  7. https://www.cnblogs.com/xinchen1111/p/8804858.html
  8. https://blog.csdn.net/blackyuanc/article/details/67640844
  9. https://www.zhihu.com/question/58584814
  10. https://www.cnblogs.com/ooon/p/5721119.html
  11. https://www.cnblogs.com/ooon/p/5723725.html
  12. https://blog.csdn.net/weixin_44273380/article/details/109034549
  13. https://blog.csdn.net/weixin_44037337/article/details/109804487
  14. https://blog.csdn.net/qq_32742009/article/details/81435141
  15. https://blog.csdn.net/weixin_44508906/article/details/89979684
  16. https://zhuanlan.zhihu.com/p/29212107
  17. https://blog.csdn.net/luoshixian099/article/details/51227754
  18. https://blog.csdn.net/qq_38734403/article/details/80442535