机器学习5_支持向量机_原问题和对偶问题—

机器学习5_支持向量机_原问题和对偶问题——MOOC

原问题与对偶问题的定义

定义该原问题的对偶问题如下

在定义了函数的基础上，对偶问题如下：

综合原问题和对偶问题的定义得到：

定理一

对偶差距（Duality Gap）

强对偶定理（Strong Duality Theorem）

假如成立，又根据定理一推出不等式

转化为对偶问题

首先将

得到

最小化：

限制条件：

再整理一下

最小化：或

限制条件：

用对偶理论求解该问题的对偶问题

对偶问题

按照对偶问题的定义，可以将对偶问题写成如下形式：

如何将原问题化为对偶问题

原问题（Prime Problem）

对偶问题（Dual Problem）

原问题与对偶问题的定义

最小化（Minimize）： $f\left ( \omega \right )$

限制条件（Subject to）： $g_i(\omega )\leq 0,i=1\sim K$

$h_i(\omega )= 0,i=1\sim m$

自变量为 $\omega\Leftarrow$ 多维向量

目标函数是 $f\left ( \omega \right )$

定义该原问题的对偶问题如下

定义函数：

$L(\omega ,\alpha ,\beta )=f(\omega )+\displaystyle\sum_{i=1}^{K}\alpha _ig_i(\omega )+\displaystyle\sum_{i=1}^{K}\beta _ih_i(\omega )$

向量的形式 $\Rightarrow$ $=f(\omega )+\alpha ^Tg(\omega )+\beta ^Th(\omega )$

其中 $\alpha =[\alpha _1,\alpha _2,...,\alpha _k]^T$ ， $\beta =[\beta _1,\beta _2,...,\beta _M]^T$

$g(\omega )=[g_1(\omega ),g_2(\omega ),...,g_K(\omega )]^T$ ， $h(\omega )=[h_1(\omega ),h_2(\omega ),...,h_M(\omega )]^T$

在定义了函数 $L(\omega ,\alpha ,\beta )$ 的基础上，对偶问题如下：

最大化： $\theta (\alpha ,\beta )=inf\text{ }L(\omega ,\alpha ,\beta )$ ，所有定义域内的 $\omega$

限制条件： $\alpha _i\geq 0,i=1\sim K$

综合原问题和对偶问题的定义得到：

定理一

如果 $\omega ^*$ 是原问题的解， $(\alpha ^*,\beta ^*)$ 是对偶问题的解则有：

$f(\omega ^*)\geqslant \theta (\alpha ^*,\beta ^*)$

证明： $\theta (\alpha^* ,\beta ^*)=inf\text{ }L(\omega ,\alpha^* ,\beta ^*)$

$\leq L(\omega^* ,\alpha^* ,\beta^* )$

$=f(\omega ^)+\alpha ^{T}g(\omega ^)+\beta ^{T}h(\omega ^*)$

$\leq f(\omega ^*)$

$\because$ $\omega ^*$ 是原问题的解

$\therefore$ $g(\omega ^*)\leqslant 0$ ， $h(\omega ^*)= 0$

$\because$ $(\alpha ^*,\beta ^*)$ 是对偶问题的解

$\therefore$ $\alpha (\omega ^*)\geqslant 0$

对偶差距（Duality Gap）

$f(\omega ^*)- \theta (\alpha ^*,\beta ^*)$

根据定理一，对偶差距 $\geqslant 0$

强对偶定理（Strong Duality Theorem）

如果 $g(\omega )=A\omega +b$ ， $h(\omega )=C\omega +d$ ， $f(\omega )$ 为凸函数，则有 $f(\omega ^*)= \theta (\alpha ^*,\beta ^*)$ ，则对偶差距为0。

如果：原问题的目标函数是凸函数，限制条件是线性函数。

那么原问题的解 $f(\omega ^*)= \theta (\alpha ^*,\beta ^*)$ ，对偶差距等于0。

假如 $f(\omega ^)= \theta (\alpha ^,\beta ^*)$ 成立，又根据定理一推出不等式

若 $f(\omega ^*)= \theta (\alpha ^*,\beta ^*)$ ，则定理一中必然能够推出，对于所有的 $i=1\sim K$ ，要么 $\alpha _i=0$ ，要么 $g_i(\omega ^*)=0$ 。这个条件成为KKT条件。

转化为对偶问题

支持向量机的原问题满足强对偶定理

首先将

$\delta _i\geq 0(i=1\sim N)$ 转换成 $\delta _i\leq 0(i=1\sim N)$

得到

最小化： $\frac{1}{2}\left \| \omega \right \|^2-C \displaystyle\Sigma _{i=1}^N \delta _i$

限制条件：

（1） $\delta _i\leq 0(i=1\sim N)$

（2） $y_i[\omega ^T\varphi (X_i)+b]\geq 1+\delta _i,(i=1\sim N)$

再整理一下

最小化： $\frac{1}{2}\left \| \omega \right \|^2-C \displaystyle\Sigma _{i=1}^N \delta _i$ 或 $\frac{1}{2}\left \| \omega \right \|^2+C \displaystyle\Sigma _{i=1}^N \delta _i$

$\Uparrow$ 情况1 $\Uparrow$ 情况2

限制条件：

（1） $\delta _i\leq 0(i=1\sim N)$

（2） $1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib\leq 0 ,(i=1\sim N)$

两个限制条件都是线性的，支持向量机的目标函数是凸的，它满足强对偶定理。

用对偶理论求解该问题的对偶问题

对偶问题

自变量 $\omega$ 等于这里的 $\left ( \omega ,b,\delta _i \right )$

不等式 $g_i(\omega )\leq 0$ 在这里被分成了两部分，

一部分： $\delta _i\leq 0(i=1\sim N)$

另一部分： $1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib\leq 0 ,(i=1\sim N)$

不存在 $h_i(\omega )$

按照对偶问题的定义，可以将对偶问题写成如下形式：

最大化：

$\theta (\alpha ,\beta )=inf_{\omega ,\delta _i,b} \left \{ \frac{1}{2}\left \| \omega \right \|^2-C \sum_{i=1}^{N}\beta _i\delta _i+\sum_{i=1}^{N} \alpha _i\left [1+\delta _i-y_i\omega ^T\varphi (X_i)-y_ib \right ] \right \}$

限制条件：

（1） $\alpha _i\geq 0$

（2） $\beta _i\geq 0$

如何将原问题化为对偶问题

遍历所有 $\left ( \omega ,b,\delta _i \right )$ 求最小值

对 $\left ( \omega ,b,\delta _i \right )$ 求导并令导数为 $\textbf{0}$

（1） $\frac{\partial \theta }{\partial\omega }=\omega-\sum_{i=1}^{N}\alpha _i\varphi (X_i)y_i=0 \text{ } \Rightarrow \text{ } \omega=\sum_{i=1}^{N}\alpha _iy_i\varphi (X_i)$