SVM（支持向量机）笔记-对偶问题，软间隔

作者: RossH | 来源:发表于2019-10-31 21:52 被阅读0次

对偶问题

我们希望求解式子
$\begin{aligned} &\mathop{min}\limits_{w,b}\frac{1}{2}\Vert{w}\Vert^2\\ &s.t.\quad y_i(w^Tx_i + b) \ge 1,i = 1,2,3\ldots,m\\ \end{aligned} \tag{1}$
来得到最大间隔划分超平面所对应的模型
$f(x) = w^Tx + b$
其中w和b是模型参数。

对式 $(1)$ 使用拉格朗日乘子法可得到其“对偶问题”，即对式 $(1)$ 的每条约束添加拉格朗日乘子 $\alpha_i \geq 0$ ，则该问题的拉格朗日函数可写成：
$L(w, b, \alpha) = \frac{1}{2}\Vert{w}\Vert^2 + \sum^m_{i = 1}\alpha_i(1 - y_i(w^Tx_i + b)) \tag{2}$

其中 $\alpha = (\alpha_1,\alpha_2,\dots,\alpha_m)$ 。对式 $(2)$ 可作如下展开：

对w和b分别求偏导数并令其等于0:

最终得到以下两式：

$\begin{aligned} w = \sum^m_{i = 1}\alpha_iy_ix_i \\ 0 = \sum^m_{i = 1}\alpha_iy_i \end{aligned}$

将 $w = \sum^m_{i = 1}\alpha_iy_ix_i$ 代入式 $(2)$ ，即可将 $L(w, b, \alpha)$ 中的w和b消去，再考虑约束 $\sum^m_{i = 1}\alpha_iy_i = 0$ ，就得到式 $(1)$ 的对偶问题。

解出 $\alpha$ 后，求出w与b即可得到模型：

$\begin{aligned} f(x) &= w^Tx + b \\ &= \sum^m_{i = 1}\alpha_iy_ix^T_ix + b \end{aligned}$

上述过程需满足KKT条件，即要求：

$\begin{equation} \left\{ \begin{array}{lr} \alpha_i \geq 0 \\ y_if(x_i) - 1\geq 0\\ \alpha_i(y_if(x_i) - 1) = 0 \end{array} \right. \end{equation}$
至此，一切都很完美。但这里有个前提，数据必须100%线性可分。然而实际上，几乎所有的数据都不怎么“干净”。我们可以用软间隔来解决这个问题。

软间隔

由于数据存在一些噪声、不是完全线性可分，所以我们允许某些样本不满足约束
$y_i(w^Tx_i + b) \ge 1$
这称为“软间隔”，而前面介绍的所有样本都要满足约束，即全部划分正确的，称之为“硬间隔”。
软间隔允许存在一点点错误，于是我们的优化目标改写成：
$\mathop{min}\limits_{w,b}\frac{1}{2}\Vert{w}\Vert^2 + C\sum^m_{i=1}l_{0/1}(y_i(w^Tx_i + b)-1)$
其中C是一个常数， $l_{0/1}$ 是“0/1损失函数”，类似于sigmoid函数，不符合条件（损失）为1，符合为0。这里将 $y_i(w^Tx_i + b)-1$ 设为z，那么

但由于 $l_{0/1}$ 非凸非连续，求解比较困难，通常用其他函数来替代，称为“替代损失”。这里采用hinge损失，式子改写为
$\mathop{min}\limits_{w,b}\frac{1}{2}\Vert{w}\Vert^2 + C\sum^m_{i=1}max(0, 1-y_i(w^Tx_i + b))$
设 $y_i(w^Tx_i + b)$ 为z，那么当z符合约束，即 $z \ge 1$ 时，hinge(z)为0，当 $z \lt 1$ 时， $hinge(z) = 1-y_i(w^Tx_i + b)$ ，此时画图可以发现是连续函数。

引入松弛变量 $\xi_i$ ，可将式子重写为
$\begin{aligned} &\mathop{min}\limits_{w,b}\frac{1}{2}\Vert{w}\Vert^2+ C\sum^m_{i=1}\xi_i\\ &s.t.\quad y_i(w^Tx_i + b) \ge 1 - \xi_i\\ & \qquad\xi_i \ge 0, i = 1,2,3\ldots,m \end{aligned}$
软间隔的求解过程跟前面硬间隔的求解过程类似，也是转成对偶问题，然后利用KKT条件，这里不再赘述，省略具体推导过程。

将约束乘以拉格朗日乘子 $\alpha_i$ 和 $\mu_i$ ，加入式子求偏导为0得

代入拉格朗日函数得对偶问题

KKT条件：

从第三个条件可以知道，对于任意样本 $(x_i,y_i)$ ，总有 $\alpha_i = 0$ 或者 $y_if(x_i) = 1-\xi_i$ 。若 $\alpha_i = 0$ ，则该样本对f(x)不会有影响；若 $\alpha_i \gt 0$ ，则必有 $y_if(x_i) = 1-\xi_i$ ，即该样本为支持向量。其中，若 $0 \lt \alpha_i \lt C$ ，则 $\mu_i \gt 0$ ，进而有 $\xi_i = 0$ ，即该样本恰好在最大间隔边界上；若 $\alpha_i = C$ ，则 $\mu_i = 0$ ，此时若 $\xi_i \le 1$ ，则该样本落在最大间隔内部，若 $\xi_i \gt 1$ ，则该样本被错误分类。