SVM简明教程

发表于 更新于 分类于 ，

本文为浙江大学胡浩基老师《机器学习》课程中 SVM 部分的笔记。先前久闻 SVM 大名而不知其原理，特学此内容，整理笔记成此博客。

SVM 处理线性可分问题

线性可分问题

一个训练样本集${(X_i,y_i)}]$，在$i=1 \sim N$线性可分，是指存在$(w,b)$使得使得对$i=1 \sim N$有：

  1. 若$y_i = +1$，则$w^TX_i+b>0$
  2. 若$y_i = -1$，则$w^TX_i+b<0$

上述定义即：

如果$y_i=+1$或$-1$，一个训练样本集${(X_i,y_i)}]$，在$i=1 \sim N$线性可分（Linear Separable），是指存在$(w,b)$使得使得对$i=1 \sim N$有$y_i(w^Tx_i + b)>0$

支持向量机寻找的最优分类超平面应满足 3 个条件：

  1. 该超平面分开了两类；
  2. 该超平面最大化间隔（margin）
  3. 该超平面处于间隔的中间，到所有的支持向量距离相等。

SVM

假定训练样本集是线性可分的，支持向量机（Support Vector Machine）需要满足限制条件$y_i(w^Tx_i + b)>0,i=1 \sim N$寻找的是最大化间隔（margin）的超平面：

点$X_0$到超平面$w^T+b=0$的距离为：
$$d= \frac{w^Tx_0+b}{||w||} $$

点到直线距离公式：
$$d= \frac {\vert Ax_0 + By_0 + C \vert} {\sqrt{A^2 + B^2}}$$
点到平面距离公式：
$$d= \frac {\vert Ax_0 + By_0 + Cz_0 + D \vert} {\sqrt{A^2 + B^2 + C^2}}$$

完成上述问题的目标函数为：

$$\max d = \max \frac{w^Tx_0+b}{||w||} = \max \frac{1}{||w||}$$

最大化支持向量到超平面的距离等价于最小化$\frac{1}{2} || w || ^2$，即最小化$||w||$.

限制条件为

$$y_i(w^Tx_i + b) \ge 1,i=1 \sim N$$

因为这是一个凸优化问题，要么有唯一解要么无解，所以可以用梯度下降法求得其值。

处理线性模型小结

  1. SVM 是最大化间隔(Margin)的分类算法
  2. 最小化$0.5 \vert \vert w\vert \vert ^2$
  3. 限制条件：$y_i(w^Tx_i + b)\ge 1,i=1 \sim N$

SVM 处理非线性模型

处理非线性模型

  1. 最小化
    $$\frac{1}{2} \vert \vert w\vert \vert ^2 + C \sum_{i=1}^{N}\delta_i$$
    或
    $$\frac{1}{2} \vert \vert w\vert \vert ^2 + C \sum_{i=1}^{N}\delta_i^2$$
    其中，$\delta_i$ 为松弛变量（slack variable），提供非线性项；$C$ 为比例因子，用于平衡两项，是一个超参数。

  2. 限制条件：

    1. $\delta_i \ge 0 (i=1 \sim N)$
    2. $y_i[w^T \varphi (X_i) + b] \ge 1,i=1 \sim N$

$\varphi(X_i)$ 为核函数（kernel function），$w$与 $\varphi(X_i)$ 维度相同

核函数

$$K(X_1, X_2)=\varphi(X_1)^T\varphi(X_2)$$

$K(X_1, X_2)$为核函数，$\varphi(X)$是低维向量至高维向量的映射关系。

如：
$$X_1=[x_{11}, x_{12}]^T, X_2=[x_{21}, x_{22}]^T$$
则
$$\varphi(X_1)=[x_{11}^2, x_{11}x_{12}, x_{12}^2] \quad \varphi(X_2)=[x_{21}^2, x_{21}x_{22}, x_{22}^2]$$ $$\begin{split}K(X_1, X_2) & = \varphi(X_1)^T\varphi(X_2) \\ & = [x_{11}^2, x_{11}x_{12}, x_{12}^2][x_{21}^2, x_{21}x_{22}, x_{22}^2]^T \\ & = x_{11}^2 x_{21}^2 + x_{11}x_{12}x_{21}x_{22} + x_{12}^2x_{22}^2 \end{split}$$

$K(X_1, X_2)$能写成$\varphi(X_1)^T\varphi(X_2)$的充要条件：

  1. 交换性：$K(X_1, X_2)=K(X_2, X_1)$
  2. 半正定性：$\forall C_i(i=1 \sim N), \forall N$ 有 $\sum_{i=1}^{N}\sum_{j=1}^{N}C_iC_jK(X_iX_j)$

常用的核函数有高斯核函数：
$$K(X_1, X_2)=e^{-\frac{||x_1-x_2||^2}{2 \sigma ^2}}$$

核函数还有：

  • Linear(线性内核): $K(x, y)= x^Ty$

  • Ploy(多项式核): $K(x, y)= (x^Ty + 1)^d$

  • Rbf (高斯径向基函数核): $K(x,y) =e^{- \frac{||x-y||^2}{\sigma^2}}$

  • Tanh(Tanh 核): $K(x, y) = \tanh{(\beta x^Ty +b)}$

  • $(X_1X_2+1)^N$

原问题与对偶问题

  • 原问题（prime question）：
    • 最小化：$f(\omega )$
    • 限制条件：
      • $g_{i}(\omega )\leq 0,i=1 \sim K$
      • $h_{i}(\omega )=0,i=1 \sim m$

定义函数

$$
\begin{split}
L(\omega, \alpha, \beta)= & f(\omega)+\sum_{i=1}^K\alpha_ig_i(\omega)+\sum_{i=1}^K\beta _ig_i(\omega) \\
= & f(\omega)+ \alpha^Tg(\omega) + \beta^Th(\omega) \\
\end{split}
$$

$$
\begin{split}
\text{其中，}\alpha = & [\alpha_1, \alpha_2, \dots , \alpha_k] \\
\beta = & [\beta_1, \beta_2, \dots , \beta_M] \\
g(\omega) = & [g_1(\omega), g_2(\omega), \dots , g_k(\omega), ]^T \\
h(\omega) = & [h_1(\omega), h_2(\omega), \dots , h_M(\omega), ]^T \\
\end{split}
$$

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

  • 对偶问题（prime question）：

    • 最大化：$\theta (\alpha, \beta)=\inf L(\omega, \alpha, \beta)$，$\omega$在所有定义域内
    • 限制条件：$\alpha_i \ge 0, i=1 \sim K$

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

  • KKT 条件：若$f(\omega^*) =\theta(\alpha^* ,\beta^*)$，对于所有$i=0…K$，要么$\alpha_{i}=0$，要么$g_{i}(\omega^* )=0$。）

支持向量机转化为对偶问题

支持向量机的原问题满足强对偶定理，写成原问题的形式为：

  • 最小化：$\frac{1}{2} \vert \vert w\vert \vert ^2-C\sum\nolimits_{i=1}^N \delta_{i} 或 \frac{1}{2} \vert \vert w\vert \vert ^2-C\sum\nolimits_{i=1}^N \delta_{i} ^2$
  • 限制条件：
    1. $\delta _{i}\leq 0, (i=1 \sim N)$
    2. $1+\delta_{i}- y_{i} w^T\varphi (X_{i}) -y_{i}b\leq 0 ,(i=1 \sim N)$

化为对偶问题形式：

  • 最大化：
    $$\theta (\alpha ,\beta )=\inf_{\omega,b,\delta_{i}} { \frac{1}{2}\vert \vert w\vert \vert ^2-\sum_{i=1}^N(C-\beta_{i})\delta_{i}+\sum_{i=1}^{N} \alpha_{i}[1+\delta_{i}- y_{i} w^T\varphi (X_{i})-y_{i}b]}$$

  • 限制条件：

    1. $\alpha _{i}\geq 0, (i=1 \sim N)$
    2. $\beta _{i}\geq 0, (i=1 \sim N)$

遍历所有 $(\omega ,b,\delta_{i})$ 求最小值，对 $(\omega,b,\delta_{i})$求导并令导数为 0:

  1. $\begin{split}\frac{\partial \theta }{\partial \omega } =\omega -\sum\nolimits_{i}^N\alpha_{i}y_{i}\varphi (X_{i})=0 \\ \implies \omega =\sum\nolimits_{i}^N\alpha_{i}y_{i}\varphi (X_{i})\end{split}$

  2. $\begin{split} \frac{\partial \theta }{\partial b} =-\sum\nolimits_{i=1}^N\alpha_{i}y_{i}=0 \\ \implies \sum\nolimits_{i=1}^N\alpha_{i}y_{i}=0\end{split}$

  3. $\begin{split} \frac{\partial \theta }{\partial \delta_{i}} =-C+\alpha_{i}+\beta_{i}=0 \\ \implies \alpha_{i}+\beta_{i}=C\end{split}$

代入，可转化为以下形式：

  • 最大化：$\theta (\alpha )=\sum\nolimits_{i=1}^n \alpha_{i}-\frac{1}{2} \sum\nolimits_{i=1}^N\sum\nolimits_{j=1}^N\alpha_{i}y_{i}\alpha_{j}y_{j}\varphi (X_{i})^T\varphi (X_{j})$
  • 限制条件：
    1. $0\leq \alpha_{i}\leq C,i=1 \sim N$
    2. $\sum\nolimits_{i=1}^N\alpha_{i}y_{i}=0,i=1 \sim N$

这样，使用 SMO 算法即可求出 $\varphi (X_{i})^T \varphi (X_{j})$。不过，我们需要求得的是$w$和$b$

考虑到 SVM 测试流程为测试样本$X$：

  • 若 $w^T \varphi (X)+b \ge 0$，则 $y=+1$
  • 若 $w^T \varphi (X)+b < 0$，则 $y=-1$

所以有

$$
\begin{split}
w^T = & \sum\nolimits_{i=1}^N[\alpha_{i}y_{i}\varphi (X_{i})]^T\varphi (X) \\
= & \sum\nolimits_{i=1}^N\alpha_{i}y_{i}\varphi (X_{i})^T\varphi (X) \\
= & \sum\nolimits_{i=1}^N\alpha_{i}y_{i}K(X_i, X) \\
\end{split}
$$

而 $\sum\nolimits_{i=1}^N\alpha_{i}y_{i}K(X_i, X)$ 在优化问题中已经求出，故 $w$不需要具体解出。

$b$ 的求解，根据 KKT 条件，

$\alpha_{i}[ 1+\delta_{i}- y_{i} w^T\varphi (X_{i}) -y_{i}b]=0$
$\beta_{i}\delta_{i}=0\implies (C-\alpha_{i})\delta_{i}=0$

如果对某个$i$（仅仅一个就行），$\alpha_{i}\neq 0且\alpha_{i}\neq C$，根据 KKT 条件，必有 $\delta_{i}=0,1+\delta_{i}- y_{i} w^T\varphi (X_{i}) -y_{i}b=0$，可得
$$b=\frac{1-y_{i}\sum\nolimits_{j=1}^N\alpha_{j}y_{j}K(X_{j},X_{i}) }{y_{i}} ,0<\alpha_{i}<C$$

SVM 算法流程

训练流程

输入 ${(x_i, y_i)}_{i=1 \sim N}$ ，使用 SMO 算法解优化问题：

  • 最大化：$\theta (\alpha )=\sum\nolimits_{i=1}^n \alpha_{i}-\frac{1}{2} \sum\nolimits_{i=1}^N\sum\nolimits_{j=1}^N\alpha_{i}y_{i}\alpha_{j}y_{j}\varphi (X_{i})^T\varphi (X_{j})$
  • 限制条件：
    1. $0\leq \alpha_{i}\leq C,i=1 \sim N$
    2. $\sum\nolimits_{i=1}^N\alpha_{i}y_{i}=0,i=1 \sim N$

算 $b$，找一个 $0<\alpha_i<C$，$b=\frac{1-y_{i}\sum\nolimits_{j=1}^N\alpha_{j}y_{j}K(X_{j},X_{i}) }{y_{i}}$

测试流程

输入测试样本 $X$：

考察测试数据 X，预测它的类别 y：

  • 如果 $\sum\nolimits_{i=1}^N\alpha_{i}y_{i}K(X_{i},X)+b\geq 0$,则 $y=+1$
  • 如果 $\sum\nolimits_{i=1}^N\alpha_{i}y_{i}K(X_{i},X)+b< 0$,则 $y=-1$

有用的资源

后记

这文章零零散散写了两三个星期，战线拖得很长，非常难受。另一边还有ZeroBot的东西还在写，SICP也还在看，因为近两个星期家里事情比较多，真正的主业计算机视觉都还没推进，不过终于把SVM给写完了。写得确实一般般，后面再修吧。

在markdown里用 $\LaTeX$ 写这么多东西真累，下次再也不这样干了。这种markdown格式的东西拿来记记代码就顶破天了，真的很难有时间去看完以后再记下来。会的仍然会，不会的仍然不会，希望后面有用吧。