Support Vector Machines

Support Vector Machines 支持向量机

前提：经过了感知器等基本概念的学习，我们以及知道如何训练出可以用于解决分类问题的超平面

说明：本文将讨论一个同样能够完成分类问题的较为复杂的想法——支持向量机 SVM（Support Vector Machines）

它由 美国计算机学家 Vladimir Vapnik 提出，用来确定分类问题的决策边界

参考：https://www.youtube.com/watch?v=_PwhiWxHK8o

Intro 引入

目前我们有很多方法能够画出各种决策边界

Vapnik 对此提出：

• 对空间中的线性可分的两类样本，要画出决策边界，无非是一个超平面，但是选择哪一个边界是个问题。
• 例如下图的例子，我们希望的是画出一个与两类样本间隔最宽的直线（下图虚线），把这个空白的间隔范围（两个橙色线之间）想象成一个沟渠。

• 其中，$\overrightarrow{\omega }$ 是垂直于决策边界的任意长度向量，$\overrightarrow{v}$ 是我们想判断分类的样本点

• 如果 $\overrightarrow{w}\cdot \overrightarrow{u}\ge C$ 那么样本很明显是在直线右侧的一类（+）

• 换个方式来描述这个分类规则, 令 $C=-b$，有 :

• $$\overrightarrow{w}\cdot \overrightarrow{u}+b\ge 0,THEN(+),[\ast \mathrm{公}\mathrm{式}1]$$
  • $\overrightarrow{u}$ 是我们已知，待分类的样本
  • $\overrightarrow{\omega }$ 和 $b$ ，分别是我们需要进一步确定的 权值 和 偏置
  • 由于我们希望确定一个唯一的最优结果，所以我们要考虑这个优化问题的限制。

Support Vector 支持向量

对于我们已知的训练集，它包含两类样本，分别是$x_{+}$和$x_{-}$ $$\begin{gathered} \overrightarrow{\omega }\cdot \overrightarrow{x_{+}}+b\ge 1,\mathrm{对}\mathrm{于}+\mathrm{样}\mathrm{本} \\ \overrightarrow{\omega }\cdot \overrightarrow{x_{-}}+b\le -1,\mathrm{对}\mathrm{于}-\mathrm{样}\mathrm{本} \end{gathered}$$

• 这两类样本之间存在一个空白区域从-1到1

我们引入一个变量$y_i$来明确第$i$个样本属于哪一类： $$\begin{gathered} y_i=+1,\mathrm{对}\mathrm{于}+\mathrm{样}\mathrm{本} \\ {y}_i=-1,\mathrm{对}\mathrm{于}-\mathrm{样}\mathrm{本} \end{gathered}$$ 这样我们将得到 $y_i(\overrightarrow{w}\cdot \overrightarrow{x_i}+b)\ge 1$ 把1移到左边 $y_i(\overrightarrow{w}\cdot \overrightarrow{x_i}+b)-1\ge 0,[\ast \mathrm{公}\mathrm{式}2]$ 如果 $y_i(\overrightarrow{w}\cdot \overrightarrow{x_i}+b)-1=0$, 这个样本$\overrightarrow{x_i}$在沟渠边界，其实就是支持向量，如下图在两个边界上的点

• 这个间隔的宽度等于正负边界上的支持向量的差$(\overrightarrow{x_{+}}-\overrightarrow{x_{-}})$乘上垂直于边界的单位方向向量，在前面我们有$\overrightarrow{\omega }$ 是垂直于决策边界的任意长度向量，那么它除以自身的模就是单位向量了，因此有： $Width=(\overrightarrow{x_{+}}-\overrightarrow{x_{-}})\cdot \frac{\overrightarrow{w}}{||\overrightarrow{w}||}$

Max the width 最大间隔问题

• 从[*公式2]可以知道对于一个支持向量$\overrightarrow{x_{+}}$ 有：
  • $y_i(\overrightarrow{w}\cdot \overrightarrow{x_{+}}+b)-1=0$
  • $y_i=+1,\mathrm{对}\mathrm{于}+\mathrm{样}\mathrm{本}$
  • 因此：$\overrightarrow{w}\cdot \overrightarrow{x_{+}}=1-b$
• 类似的对于支持向量$\overrightarrow{x_{-}}$
  • $y_i(\overrightarrow{w}\cdot \overrightarrow{x_{-}}+b)-1=0$
  • $y_i=-1,\mathrm{对}\mathrm{于}-\mathrm{样}\mathrm{本}$
  • 因此：$\overrightarrow{w}\cdot \overrightarrow{x_{-}}=-1-b$
  • $\overrightarrow{w}\cdot \overrightarrow{x_{+}}-\overrightarrow{w}\cdot \overrightarrow{x_{-}}=1-b-(-1-b)=2$

• 所以宽度公式可以进一步表示为 $Width=(\overrightarrow{x_{+}}-\overrightarrow{x_{-}})\cdot \frac{\overrightarrow{w}}{||\overrightarrow{w}||}=\frac{2}{||\overrightarrow{w}||},[\ast \mathrm{公}\mathrm{式}3]$

• 我们的问题就在于如何得到最大的间隔宽度$Width$

• 忽略掉常数，我们需要最大化$\frac{1}{

  \vec{w}

  }$，\mathrm{也}\mathrm{就}\mathrm{是}\mathrm{要}\mathrm{最}\mathrm{小}\mathrm{化}${

  \vec{w}

  }$

• 更进一步，最小化$\frac{1}{2}{

  \vec{w}

  }^2$, 这种形式方便我们直接套用数学上的优化问题的解决方法——拉格朗日公式

Lagrange mutipliers 拉格朗日乘子

• 对于一个有限制（边界条件）的函数，用拉格朗日乘子可以求函数的极值

• $$L=\frac{1}{2}{||\overrightarrow{w}||}^2-\sum {\alpha }_i[y_i(\overrightarrow{w}\cdot \overrightarrow{x_i}+b)-1]$$
  • L 表示我们要最大化的量
  • ${\alpha }_i$ 是拉格朗日乘子，支持向量对应的是1，其他的是0
  • $y_i(\overrightarrow{w}\cdot \overrightarrow{x_i}+b)-1$是限制条件
  • 如果需要进一步了解可以参考https://zhuanlan.zhihu.com/p/542402242

• 要求一个函数的极值，我们可以先求导来判断 $\frac{\partial L}{\partial \overrightarrow{w}}=\overrightarrow{w}-\sum {\alpha }_i{y}_i\overrightarrow{x_i}=0$

  • 对于向量的求导我们不做展开说明，其基本形式与标量类似，特殊情况我们再做说明。

  • $$\overrightarrow{w}=\sum {\alpha }_i{y}_i\overrightarrow{x_i},[\ast \mathrm{公}\mathrm{式}4]$$
• 接下来我们对$b$求偏导

$$\frac{\partial L}{\partial b}=-\sum {\alpha }_i{y}_i=0$$

• $$\sum {\alpha }_i{y}_i=0,[\ast \mathrm{公}\mathrm{式}5]$$
• 我们把[*公式4]带入到拉格朗日公式里得到

$$\begin{gathered} L=\frac{1}{2}{(\overrightarrow{w})}^2-\sum {\alpha }_i{y}_i\overrightarrow{x_i}(\overrightarrow{w})-\sum {\alpha }_i{y}_{i}b+\sum {\alpha }_i \\ =\frac{1}{2}(\sum {\alpha }_i{y}_i\overrightarrow{x_i})\cdot (\sum {\alpha }_j{y}_j\overrightarrow{x_j})\mathrm{①} \\ -(\sum {\alpha }_i{y}_i{x}_i)\cdot (\sum {\alpha }_j{y}_j\overrightarrow{x_j})\mathrm{②} \\ -\sum {\alpha }_i{y}_{i}b\mathrm{③}+\sum {\alpha }_i\mathrm{④} \end{gathered}$$

• 上面的结果一共有①-④项，我们来分析一下

  • ①和②是同类项，合并后系数为$-\frac{1}{2}$
  • ③中b对于求和来说是常数，可以提出来，由$\sum {\alpha }_i{y}_i=0,[\mathrm{公}\mathrm{式}5]$发现③项等于0
  • ④项保留
• $$L=-\frac{1}{2}(\sum {\alpha }_i{y}_i\overrightarrow{x_i})\cdot (\sum {\alpha }_j{y}_j\overrightarrow{x_j})+\sum {\alpha }_i$$

• 最终得到

• $$L=\sum {\alpha }_i-\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j\overrightarrow{x_i}\cdot \overrightarrow{x_j},[\ast \mathrm{公}\mathrm{式}6]$$

  至此，我们所有的问题都转化为了，求[*公式6]这个表达式的最大值

这个形式清楚的表达了，这个最大值与这些样本向量（训练集）的关系。

我们发现这个最优值取决于这些样本，它们两两之间的内积，也就是$\overrightarrow{x_i}\cdot \overrightarrow{x_j}$

• 同样带入[公式4]我们的决策条件（分类规则）[*公式1]也变成了：

• $$\sum {\alpha }_i{y}_i\overrightarrow{x_i}\cdot \overrightarrow{u}+b\ge 0,THEN(+)$$

分类规则也同样取决于训练集的样本（支持向量）和测试样本之间的内积，$\overrightarrow{x_i}\cdot \overrightarrow{u}$

Kernel Function 核函数

在当前维度，如果样本线性不可分，可以使用核（Kernel）来把样本映射到更高维的空间，使样本线性可分。 $\overrightarrow{x}\to \varphi (\overrightarrow{x})$ 上一小节我们得出结论：无论是优化问题还是分类规则都与样本向量两两间的内积有关，因此我们可以考虑映射后的内积的表达

• 对于$L$, 需要求：

$$\varphi (\overrightarrow{x_i})\cdot \varphi (\overrightarrow{x_j})$$

• 对于分类规则，需要：

$$\varphi (\overrightarrow{x_i})\cdot \varphi (\overrightarrow{u})$$

因此我们定义核函数为： $K(\overrightarrow{x_i},\overrightarrow{x_j})=\varphi (\overrightarrow{x_i})\cdot \varphi (\overrightarrow{x_j})$ 我们甚至无需确定映射的规则（$\varphi (\overrightarrow{x})$ 的表达式）,只需要知道核函数$K(\overrightarrow{x_i},\overrightarrow{x_j})$ 的表达式足矣

• 几种常用的核函数：

  • $$K(u,v)=(u^T\cdot v+1{)}^n$$
  • $$K(u,v)=u^T\cdot v$$
  • $$K(u,v)=e^{-\frac{||u-v||}{\sigma }}$$