A 支持向量机

A1 支持向量机的优化目标

• 可以看到对于一组线性可分的数据，存在很多不同的划分超平面，而想必其中有的泛化性能较好、有的泛化性能差。

  

• 发现每个划分超平面沿法向平移一定距离之后仍能作为正确划分方案，并且称其能前后法向平移的距离 $\gamma$ 为这个 $\boldsymbol w$ 对应的间隙。这里认为能最大化间隙的目标超平面泛化性能最好，也就是我们下面整个「A」部分要求解的目标。

  

  • 称「支持向量」为在间歇边界上的样例，如上画了圈的样例。

A2 对线性划分超平面的基本认识

• 对于在 $N$ 维空间中，方程 $\boldsymbol w^{\rm T} \boldsymbol x + b= 0$ 表示的是一个 $N-1$ 维超平面，其参数有法向量 $\boldsymbol w \in \R^N$ 和偏差 $b \in \R$。自变量为 $\boldsymbol x \in \R^N$，但只有一部分满足方程的 $\boldsymbol x$ 在此超平面上。

  • 此超平面其到原点的距离为 $r = \frac {|b|}{\| \boldsymbol w\|}$。

    推导 I：几何方法

    根据几何知识可以知道，超平面上离原点最近的那点的位矢 $\boldsymbol q$，一定是法向量的某个倍数即 $\boldsymbol q = k \boldsymbol w$。代入方程即联立求直线与超平面的交点 $\boldsymbol w^{\rm T} (k \boldsymbol w) + b= 0$，得到 $k = -\frac b {\| \boldsymbol w \|^2}$，因而 $\boldsymbol q = -\frac b {\| \boldsymbol w \|} \cdot \frac {\boldsymbol w} {\| \boldsymbol w \|}$，因而距离 $r = \| \boldsymbol q \| = \frac {|b|}{\| \boldsymbol w \|}$。

    推导 II：函数方法

    $$ \min \| \boldsymbol x \|^2, \ \ \ {\rm where} \ \ \boldsymbol x \in \R, \ \boldsymbol w^{\rm T} \boldsymbol x + b= 0 $$

    作拉格朗日函数 $L(\boldsymbol x, \lambda) = \| \boldsymbol x \|^2 + \lambda(\boldsymbol w^{\rm T} \boldsymbol x + b)$，让其对 $\boldsymbol x, \lambda$ 偏导为 0：

    $$ \frac{\partial L(\boldsymbol x, \lambda)}{\partial \boldsymbol x} = 2\boldsymbol x + \lambda \boldsymbol w = 0, \ \ \ \ \ \frac{\partial L(\boldsymbol x, \lambda)}{\partial \lambda} = \boldsymbol w^{\rm T} \boldsymbol x + b= 0 $$

    第一式得 $\boldsymbol x = -\frac \lambda 2 \boldsymbol w$，代入二式得 $-\frac \lambda 2 \| \boldsymbol w \|^2 + b= 0$ 得 $\lambda = \frac {2b} {\| \boldsymbol w \|^2}$，回代一式得 $\boldsymbol x = -\frac {b}{\| \boldsymbol w \|^2} \boldsymbol w$，$r = \| \boldsymbol x \| = \frac {|b|}{\| \boldsymbol w\|}$。

• 对于 $f(\boldsymbol x) = \boldsymbol w^{\rm T} \boldsymbol x + b$ 这个去掉偏差 $b$ 就是线性函数的 $\R^N \to \R$ 函数而言（它被称为仿射函数），有两种几何理解方法：
  • 原始空间理解：其相当于在原始空间（$N$ 维空间）中建立等高超平面，等高超平面即由一系列等间距、平行于超平面 $\boldsymbol w^{\rm T} \boldsymbol x + b= 0$ 的 $N-1$ 维超平面构成，其中超平面 $\boldsymbol w^{\rm T} \boldsymbol x + b= 0$ 称为零海拔超平面，在上方已经研究过其性质；
  • 拓展空间理解：当然也可以为 $f(\boldsymbol x)$ 的函数值方向增多一维，从而构成产生拓展空间（$N+1$ 维空间），此时函数图像是一个 $N$ 维超平面。

• 如果只是要确定一个能对给定数据集 $(\boldsymbol x^{(i)}, y^{(i)}) \ (i \in [1, |X|] \cap \Z )$ 进行线性划分的超平面，只需要找到函数 $f(\boldsymbol x) = \boldsymbol w^{\rm T} \boldsymbol x + b$ 的一组参数 $\boldsymbol w, b$，使得对所有样本而言，函数值的正负性与函数的正负性相同：

  $$ \begin{cases} \boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b > 0, & y^{(i)} = +1 \\

  \boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b < 0, & y^{(i)} = -1 \end{cases}, \ \ \ \ \ i \in [1, |X|] \cap \Z $$

  • 或者统一记为如下形式：

    $$ y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) > 0, \ \ \ i \in [1, |X|] \cap \Z $$

  • 显然就如「A1」中所言，对于线性可分数据集而言，这样的超平面是不唯一的，它们有不同的「间隔」。

A3 对线性划分超平面的拓展认识

• 可以证明对于上述函数 $f(\boldsymbol x) = \boldsymbol w^{\rm T} \boldsymbol x + b$ 而言，原始空间中任意点 $\boldsymbol x\in \R^N$ 到此函数的零海拔超平面的距离 $r(\boldsymbol x) = \frac {|f(\boldsymbol x)|}{\| \boldsymbol w \|} = \frac {|\boldsymbol w^{\rm T} \boldsymbol x + b|}{\| \boldsymbol w \|}$。

  推导 I：几何方法

  称要求到零海拔超平面距离的目标点为 $\boldsymbol x_0$。可以将函数 $f(\boldsymbol x) = \boldsymbol w^{\rm T} \boldsymbol x + b$ 和目标点全部位移 $-\boldsymbol x_0$，得到新空间中的函数为 $f(\boldsymbol x + \boldsymbol x_0) = \boldsymbol w^{\rm T} (\boldsymbol x + \boldsymbol x_0) + b = \boldsymbol w^{\rm T} \boldsymbol x + \boldsymbol w^{\rm T}\boldsymbol x_0 + b$（其偏差项是 $\boldsymbol w^{\rm T}\boldsymbol x_0 + b$），新空间中的目标点即为零点 $\boldsymbol 0$，因而套用新空间中原点到新函数零海拔超平面的距离公式 $r = \frac {|\boldsymbol w^{\rm T}\boldsymbol x_0 + b|}{\| \boldsymbol w\|}$ 即得到原空间中目标点到原函数零海拔超平面的距离公式 $r(\boldsymbol x_0) = \frac {|f(\boldsymbol x_0)|}{\| \boldsymbol w\|}$。

  推导 II：函数方法

  称零海拔超平面上离目标点 $\boldsymbol x$ 最近的点为 $\boldsymbol p^*$。问题就变成：

  $$ \min \| \boldsymbol p - \boldsymbol x \|^2, \ \ \ {\rm where} \ \ \boldsymbol p \in \R, \ \boldsymbol w^{\rm T} \boldsymbol p + b= 0 $$

  作拉格朗日函数 $L(\boldsymbol p, \lambda) = \| \boldsymbol p - \boldsymbol x \|^2 + \lambda(\boldsymbol w^{\rm T} \boldsymbol p + b)$，让其对 $\boldsymbol x, \lambda$ 偏导为 0：

  $$ \frac{\partial L(\boldsymbol p, \lambda)}{\partial \boldsymbol p} = 2(\boldsymbol p - \boldsymbol x) + \lambda \boldsymbol w = 0, \ \ \ \ \ \frac{\partial L(\boldsymbol x, \lambda)}{\partial \lambda} = \boldsymbol w^{\rm T} \boldsymbol p + b= 0 $$

  第一式得 $\boldsymbol p = \frac 12 (-\lambda \boldsymbol w + 2\boldsymbol x)$，代入二式得 $-\frac \lambda 2 \| \boldsymbol w \|^2 + \boldsymbol w ^{\rm T} \boldsymbol x + b = 0$，整理得 $\lambda = \frac 2 {\| \boldsymbol w \|^2} (\boldsymbol w^{\rm T} \boldsymbol x + b)$，目标根据一式变形 $\| \boldsymbol p - \boldsymbol x \| = \frac {|\lambda|} 2 \| \boldsymbol w \| = \frac {|\boldsymbol w^{\rm T} \boldsymbol x + b|}{\| \boldsymbol w \|} = \frac {|f(\boldsymbol x)|}{\| \boldsymbol w \|}$。

• 另外，可以发现函数 $f(\boldsymbol x) = \boldsymbol w^{\rm T} \boldsymbol x + b$ 等高超平面的间距，或者说拓展空间中的「斜率」，由 $b$ 和 $\boldsymbol w$ 共同决定。

  • 容易发现，对于法向量 $\boldsymbol w$ 和偏差 $b$ 都是原来 $m$ 倍的新函数 $g(\boldsymbol x) = (m \boldsymbol w)^{\rm T} \boldsymbol x + mb = m f(\boldsymbol x)$，其在 $g(\boldsymbol x)=0$ 时的方程与原函数 $f(\boldsymbol x) = 0$ 一样，也即零海拔超平面一样；但是因为发生了函数值的 $m$ 倍缩放，等高线的间距或者拓展空间中的「斜率」会有所变化。
  • 因而通过对函数其进行任意倍的缩放，就是对等高超平面的间距进行操纵，甚至缩放倍数的正负决定了翻转方向。

• 可以知道，如果 $\boldsymbol x$ 沿着法向量 $\boldsymbol w$ 所指的方向运动，函数值 $f(\boldsymbol x)$一定越来越大。

  证明

  因为 $\frac{\partial f}{\partial \boldsymbol x} = \boldsymbol w$，而梯度指向函数值增长最快的方向。

• 可以知道两个函数值差距为 1 的等高超平面间的距离为 $\frac {1}{\| \boldsymbol w \|}$。

  证明

  设此距离为 $\rho$，那么对于任意自变量 $\boldsymbol x \in \R^N$ 沿法向量 $\boldsymbol w$ 方向有 $f(\boldsymbol x + \rho \frac {\boldsymbol w}{\| \boldsymbol w \|}) - f(\boldsymbol x) = 1$。展开为 $\boldsymbol w^{\rm T} (\boldsymbol x + \rho \frac {\boldsymbol w}{\| \boldsymbol w \|} - \boldsymbol x) = \rho \|\boldsymbol w\| = 1$，即得 $\rho = \frac {1}{\| \boldsymbol w \|}$。

• 我们在之前确定线性划分超平面的基础上加以改进，认定条件如下：

  $$ \begin{cases} \boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b \ge \underline {+1}, & y^{(i)} = +1 \\

  \boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b \le \underline {-1}, & y^{(i)} = -1 \end{cases}, \ \ \ \ \ i \in [1, |X|] \cap \Z \\

  {\rm i. e.} \ \ \ \ \ y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) \ge 1, \ \ \ i \in [1, |X|] \cap \Z $$

  • 认为满足上述条件的 $f(\boldsymbol x) \in [-1, +1]$ 的范围内就是「间隙」。正例都在间隙的正外侧，负例都在间隙的负外侧。易知「间隙」的大小是函数值差距为 2 的等高超平面间的距离 $\frac {2}{\| \boldsymbol w \|}$。
  • 要最大化「间隙」$\frac {2}{\| \boldsymbol w \|}$，即最小化 $\| \boldsymbol w \|^2$ 或者说更方便求导的 $\frac 12\| \boldsymbol w \|^2$。因而问题写作：

  $$ \argmin_{\boldsymbol w, b} \frac 12\| \boldsymbol w \|^2, \ \ \ {\rm where} \ \ y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) \ge 1, \ \ i \in [1, |X|] \cap \Z $$

  • 这便是支持向量机的优化问题。

A4 求支持向量机优化问题的对偶问题

• 结论如下：上述支持向量机优化问题的对偶问题为下式。

  $$ \argmax_{\lambda_1, \lambda_2, \cdots, \lambda_{|X|}} \left ( \sum_{i = 1}^{|X|} \lambda_i - \frac 12 \sum_{i = 1}^{|X|} \sum_{j = 1}^{|X|} \lambda_i \lambda_j y^{(i)} y^{(j)} {\boldsymbol x^{(i)}} ^{\rm T}\boldsymbol x^{(j)} \right ), \\ {\rm where} \begin{cases}

  \lambda_i \ge 0 & (\forall i) \\

  \sum_{i = 1}^{|X|} \lambda_i y^{(i)} = 0

  \end{cases} $$

  证明

  可以知道原问题是一个受到多个不等式约束的极值问题（自变量有俩 $\boldsymbol w, b$，但是本质上和一个多维自变量一样）。因而作拉格朗日函数：

  $$ L(\boldsymbol w, b, \{\lambda_i\}) = \frac 12\|\boldsymbol w \|^2 + \sum_{i = 1}^{|X|} \lambda_i \left( 1 - y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) \right) $$

  其 KKT 条件中关于 $\frac{\partial L}{\partial \boldsymbol w}, \frac{\partial L}{\partial b}$ 的部分如下：

  $$ \begin{cases}

  \frac{\partial L}{\partial \boldsymbol w} = \boldsymbol w - \sum_{i = 1}^{|X|} \lambda_i y^{(i)} \boldsymbol x^{(i)} = \boldsymbol 0 & {\rm (1)} \\

  \frac{\partial L}{\partial b} = -\sum_{i = 1}^{|X|} \lambda_i y^{(i)} = 0 & {\rm (2)} \\

  \end{cases} $$

  即：

  $$ \boldsymbol w = \sum_{i = 1}^{|X|} \lambda_i y^{(i)} \boldsymbol x^{(i)}, \ \ \ \ \ \sum_{i = 1}^{|X|} \lambda_i y^{(i)} = 0 $$

  拉格朗日函数完全拆开，就能根据上面两式消掉 $\boldsymbol w, b$：

  $$ \begin{align*}

  L(\boldsymbol w, b, \{\lambda_i\}) &= \frac 12 \boldsymbol w^{\rm T} \boldsymbol w + \sum_{i = 1}^{|X|} \lambda_i - \boldsymbol w^{\rm T} \left( \sum_{i = 1}^{|X|} \lambda_i y^{(i)} \boldsymbol x^{(i)} \right) - b\sum_{i = 1}^{|X|} \lambda_i y^{(i)} \\

  &= \sum_{i = 1}^{|X|} \lambda_i - \frac 12 \boldsymbol w^{\rm T} \boldsymbol w \\

  &= \sum_{i = 1}^{|X|} \lambda_i - \frac 12 \sum_{i = 1}^{|X|} \sum_{j = 1}^{|X|} \lambda_i \lambda_j y^{(i)} y^{(j)} {\boldsymbol x^{(i)}} ^{\rm T}\boldsymbol x^{(j)} \\

  \end{align*} $$

  KKT 条件中剩下的部分为：

  $$ \begin{cases}

  \frac{\partial L}{\partial \lambda_i} = \phi_i(\boldsymbol x) \le 0 \ : \ y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) \ge 1 & {\rm (3)}\\

  \lambda_i \ge 0 & {\rm (4)}\\

  \lambda_i \phi_i(\boldsymbol x) = 0 \ : \ \lambda_i \left ( 1-y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) \right ) = 0 & {\rm (5)}

  \end{cases} $$

  最终只选用 $\lambda_i \ge 0 \ (\forall i)$ 与 $\sum_{i = 1}^{|X|} \lambda_i y^{(i)} = 0$ 这两个与 $\boldsymbol w, b$ 无关的作为判断条件。

  先前利用导数为零只是为原问题指出了一个下界，对偶问题的目标就是将这个下界提到最高，求得下界的其最大值：

  $$ \argmax_{\lambda_1, \lambda_2, \cdots, \lambda_{|X|}} \left ( \sum_{i = 1}^{|X|} \lambda_i - \frac 12 \sum_{i = 1}^{|X|} \sum_{j = 1}^{|X|} \lambda_i \lambda_j y^{(i)} y^{(j)} {\boldsymbol x^{(i)}} ^{\rm T}\boldsymbol x^{(j)} \right ), \\ {\rm where} \begin{cases}

  \lambda_i \ge 0 & (\forall i) \\

  \sum_{i = 1}^{|X|} \lambda_i y^{(i)} = 0

  \end{cases} $$

• 通过一些方法可以求得 $\lambda_1, \lambda_2, \cdots, \lambda_{|X|}$，因为对偶问题现在是一个二次优化问题。

  • **SMO（Sequential Minimal Optimization）**是其中一个较快的、著名的代表算法。

• 根据 KKT 条件，如果有 $\lambda_i > 0$ 就必有 $y^{(i)} (\boldsymbol w^{\rm T} \boldsymbol x^{(i)} + b) = 1$，因而 $\lambda_i > 0$ 时对应的样本一定为支持向量的样本。换句话说，只考虑各个支持向量的话，基本上就会是 $\lambda_i > 0$ 的部分。