支持向量机

图来源：《机器学习》周志华著

超平面用方程表示为

w^Tx+b=0

，

\gamma=\frac{2}{||w||}

为间隔(margin)。我们需要找到具有最大间隔的划分超平面，故得到：

\underset{w,b}{argmin}\frac12||w||^2

s.t. y_i(w^Tx+b)>=1,i=1,2,...,m

1.问题求解：

(1)拉格朗日乘子法

定义拉格朗日函数
$L(w,b,\mu)=\frac{1}{2}||w||^2+\sum_{i=1}^{m}\mu_i(1-y_i(w^Tx+b))$ ，
KKT条件为：
$\begin{cases} \mu _{ i }>=0 \\ 1-y_{ i }(w^{ T }x+b)<=0 \\ \mu_i(1-y_i(w^Tx+b))=0\end{cases}$
求极值，则令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\mu_iy_ix_i=0$
$\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}\mu_iy_i=0$
得到：
$w=\sum_{i=1}^{m}\mu_iy_ix_i$
$\sum_{i=1}^{m}\mu_iy_i=0$
代入 $L(w,b,\mu)$ 消去 $w$ 和 $b$ ,得到原问题的对偶问题为
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
由KKT条件得到：对于任意训练样本 $(x_i,y_i)$ 总有 $\mu_i=0$ 或 $y_i(w^Tx_i+b)=1$ ,这就意味着当 $\mu_i=0$ 时，该样本并不会对 $f(x)=w^Tx+b$ 产生而任何影响，当 $y_i(w^Tx_i+b)=1$ 时，此时意味着训练样本在最大间隔的边界上，该样本点称之为支持向量。

(2)对偶问题求解：

2.核函数

假设样本线性可分，即存在一个超平面对样本进行分类。而实际任务中，样本往往是非线性可分。此时，我们将 $x_i$ 映射到高维特征空间，在特征空间中找到超平面使得样本线性可分，记 $\phi(x_i)$ 为 $x_i$ 映射到高维特征空间所对应的特征向量。
因此，对应的模型可以表示为
$f(x)=w^T\phi(x)+b$
实际只需要求解如下函数：
$\underset{w,b}{argmin}\frac12||w||^2$
$s.t. y_i(w^T\phi(x_i)+b)>=1,i=1,2,...,m$
对偶问题为：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_j\phi(x_i)^T\phi(x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
当特征空间维度很高时，计算 $\phi(x_i)^T\phi(x_j)$ 困难，故定义核函数 $k(.,.)$ 使得 $\phi(x_i)^T\phi(x_j)=k(x_i,x_j)$ ,
则对偶问题重写为：
$\underset{\mu}{argmax} \sum_{i=1}^{m}\mu_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\mu_i\mu_jy_iy_jk(x_i,x_j)$
$s.t. \sum_{i=1}^{m}\mu_iy_i=0,\mu_i>=0,i=1,2,...m$
求解该对偶问题得到
$f(x)=\sum_{i=1}^{m}\mu_iy_i\phi(x_i)^Tx+b$
$=\sum_{i=1}^{m}\mu_iy_ik(x_i,x)+b$

3.软间隔

图中红色样本是被分错的

前面介绍的支持向量机形式是要求所有样本均满足约束 $y_i(w^Tx+b)>=1,i=1,2,...,m$ ，即所有样本都必须划分正确，这称为"硬间隔" (hard margin)，而软间隔则是允许某些样本不满足约束。当然我们是希望这样不满足约束的样本越少越好。因此目标函数定义为
$\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{0/1}( y_i(w^Tx+b)-1)$ ,其中
$l_{0/1}(z)=\begin{cases} 1\quad ,if\quad z<0 \\ 0\quad ,otherwise \end{cases}$

由于 $l_{0/1}$ 非凸、非连续，常用其他损失函数替代，如下图所示:

三种常见的替代损失函数:hinge损失，指数损失，对率损失

采用hinge损失得到：

\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}max(0, 1-y_i(w^Tx+b))

引入松弛变量得到:

软间隔支持向量机

$\underset{w,b}{argmin}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i$
$s.t. y_i(w^Tx+b)>=1-\xi_i,i=1,2,...,m$
$\xi_i>=0,i=1,2,...,m$
采用拉格朗日乘子法
$L(w,b,\alpha,\xi,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}\xi_i+\sum_{i=1}^{m}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^{m}\mu_i\xi_i$ ，求极值，令
$\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}\alpha_iy_ix_i=0 \Rightarrow w=\sum_{i=1}^{m}\alpha_iy_ix_i$
$\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}\alpha_iy_i=0$
$\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i$
带入L得到原问题的对偶问题为:
$\underset{\alpha}{argmax}\sum_{i=1}^{m}\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j$
$s.t. \sum_{i=1}^{m}\alpha_iy_i=0$
$0<=\alpha_i<=C,i=1,2,...,m$
KKT条件要求:
$\begin{cases} \alpha _{ i }>=0, \mu_i>=0\\ 1-\xi_i-y_{ i }(w^{ T }x+b)<=0 \\\xi_i>=0\\ \alpha_{ i }(1-\xi_i-y_{ i }(w^{ T }x+b))=0 \\\mu_i\xi_i=0\end{cases}$
由此可得：

对于任意 $(x_i,y_i)$ ,当 $\alpha_i=0$ 时，该样本不会对 $f(x)$ 产生任何影响；当 $\alpha_i>0$ 时，必有 $y_{ i }(w^{ T }x+b)=1-\xi_i$ ,此时该样本是支持向量。当 $\alpha_i<C$ 时， $\mu_i>0$ ,则 $\xi_i=0$ ,此时样本处于最大间隔边界上，当 $\alpha_i=C$ 时， $\mu_i=0$ ，则 $\xi_i>0$ ；若 $\xi_i>1$ ,样本被错误分类;若 $\xi_i<1$ ,样本落在最大间隔内部。
软间隔支持向量机模型仅与支持向量有关。

4.支持向量回归

（1）考虑 $f(x)$ 与 $y$ 最多允许有 $\varepsilon$ 的误差
（2）构建宽度为 $2\varepsilon$ 的间隔带，如图：

落入间隔带的样本被认为是预测正确的

目标函数：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}l_{\varepsilon}( f(x_i)-y_i)

l_{\varepsilon}(z)=\begin{cases} 0\quad ,if\quad |z|<=\varepsilon \\|z|-\varepsilon\quad ,otherwise \end{cases}

可允许间隔带两侧的松弛程度有所不同，故引入松弛变量

\xi

和

\overset{\wedge}{\xi}

,得到SVR问题：

\underset{w,b}{argmin}\frac{1}{2}||w||+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

s.t. f(x_i)-y_i<=\varepsilon+\xi_i

y_i- f(x_i)<=\varepsilon+\overset{\wedge}{\xi}_i

\xi_i>=0,\overset{\wedge}{\xi}_i>=0,i=1,2,...,m

拉格朗日乘子法

L(w,b,\xi,\overset{\wedge}{\xi},\alpha,\overset{\wedge}{\alpha},\mu,\overset{\wedge}{\mu})=\frac{1}{2}||w||^2+C\sum_{i=1}^{m}(\xi_i+\overset{\wedge}{\xi}_i)

+\sum_{i=1}^{m}\alpha_i( f(x_i)-y_i-\varepsilon-\xi_i)+\sum_{i=1}^{m}\overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)

-\sum_{i=1}^{m}\mu_i\xi_i-\sum_{i=1}^{m}\overset{\wedge}{\mu}_i\overset{\wedge}{\xi}_i

，求极值，令

\frac{\partial{L}}{\partial{w}}=w-\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i=0 \Rightarrow w=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i

\frac{\partial{L}}{\partial{b}}=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

\frac{\partial{L}}{\partial{\xi_i}}=C-\alpha_i-\mu_i=0 \Rightarrow C=\alpha_i+\mu_i

\frac{\partial{L}}{\partial{\overset{\wedge}{\xi}_i}}=C-\overset{\wedge}{\alpha}_i-\overset{\wedge}{\mu}_i=0 \Rightarrow C=\overset{\wedge}{\alpha}_i+\overset{\wedge}{\mu}_i

代入L,得到SVR的对偶问题：

\underset{\alpha,\overset{\wedge}{\alpha}}{argmax}\sum_{i=1}^{m}y_i(\overset{\wedge}{\alpha}_i-\alpha_i)-\varepsilon(\overset{\wedge}{\alpha}_i+\alpha_i)

-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)(\overset{\wedge}{\alpha}_j-\alpha_j)x_i^Tx_j

s.t. \sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)=0

0<=\alpha_i,\overset{\wedge}{\alpha}_i<=C,i=1,2,...,m

KKT条件为：

\begin{cases} \alpha_i(f(x_i)-y_i-\varepsilon-\xi_i)=0 \\ \overset{\wedge}{\alpha}_i(y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i)=0 \\ \alpha_i \overset{\wedge}{\alpha}_i=0,\xi\overset{\wedge}{\xi}_i=0\\(C-\alpha_i)\xi=0,(C-\overset{\wedge}{\alpha}_i)\overset{\wedge}{\xi}_i=0 \end{cases}

当且仅当 $f(x_i)-y_i-\varepsilon-\xi_i=0$ , $\alpha_i$ 为非零；当且仅当 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ , $\overset{\wedge}{\alpha}_i$ 为非零.换言之，样本 $(x_i,y_i)$ 没有落在 $\varepsilon$ -间隔带时， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 为非零。此外， $f(x_i)-y_i-\varepsilon-\xi_i=0$ 和 $y_i-f(x_i)-\varepsilon-\overset{\wedge}{\xi}_i=0$ 不能同时成立。因此， $\alpha_i$ 和 $\overset{\wedge}{\alpha}_i$ 至少有一个为零。
由 $f(x)=\sum_{i=1}^{m}(\overset{\wedge}{\alpha}_i-\alpha_i)x_i^Tx+b$ 可知，只有 $(\overset{\wedge}{\alpha}_i-\alpha_i)$ 非零时， $(x_i,y_i)$ 为SVR的支持向量，且落在 $\varepsilon$ -间隔带之外。落在 $\varepsilon$ -间隔带中的样本，满足 $\alpha_i=\overset{\wedge}{\alpha}_i=0$

支持向量机