本文将复习并记录支持向量机的概念、数学推导及SMO实现。

本文将要介绍的内容如下图所示：

支持向量机 (Support Vector Machine)

1. 从朴素直觉开始—使用线 or 面分割样本空间

倘若现有两个类样本，样本集的空间可以使用 $D = \{(x_1,y_1),(x_2,y_2),…,(x_n,y_n)\}$ 来表示，属于类A的样本$y_i = 1$，属于类B的样本$y_i = -1$；在这个高维空间中，使用一道劈开两个类的直线或面来将样本集划分为两个区域，一个区域中的所有点都属于类A，另一个区域中的所有点都属于类B似乎是最简单粗暴的方法，同时也符合我们的从线性回归中汲取的直觉。

但是问题接踵而至：如何把$y = wx+b$拓展至多维?如何让这个问题代数化首先使人类理解?在海量数据中如何进行优化并且预测?针对不同的数据问题，这个想法是否适用等等，让我们重新走过上世纪科学家们的老路。

2. 优化问题确立 (硬间隔svm)

2.1 超平面与间隔

在样本空间中，划分超平面(平面上为A类、下为B类)可以使用下面的表达式定义：

$$\textbf{w}^{T}\textbf{x}+b=0 \ ,\ f(x)=sign(\textbf{w}^{T}\textbf{x}+b)$$

其中，$\textbf{w}$为法向量(shape $1\times n$ 列向量形式)，$b$为平面偏置(即截距)，为一个数值，$x$为样本点的行向量(shape $n\times 1$)。

超平面距离样本点的距离可以使用下面的公式计算：

$$\gamma = \frac{|w^Tx+b|}{||w||}=\frac{|\sum_{i=1}^{n}w_{i}x_{i}+b|}{\sqrt{\sum_{i=1}^nw_i^2}}$$

看起来不熟悉？没事，换成二维平面的点到直线距离就昭然若揭了，本质上就是其在高维的推广：

$$d = \frac{|ax+by+c|}{\sqrt{a^2+b^2}}$$

在这个公式中，我们没有考虑分类变量$y$的参与，既然两类的$y$存在着正负的差异，那么我们只要将超平面的方程中$y$的符号取反直接从距离度量中就可以得到间隔，共有两种：

1. 函数间隔：$\hat{\gamma_i} =y_i(wx_i+b)$
2. 几何间隔：$\gamma_i =\frac{y_i|w^Tx+b|}{||w||}$

不难看出 $\hat{\gamma_i} = \frac{\gamma_i}{||w||}$ 。

问题01: 为什么在众多间隔度量中偏偏选中几何间隔？

几何间隔是唯一的、与参数表示无关的距离，对于同一超平面，有无穷多种表示：

$$\mathbf{w}^\top\mathbf{x}+b=0 \quad \Leftrightarrow \quad (k\mathbf{w})^\top\mathbf{x}+(kb)=0$$

对于函数间隔 $\hat{\gamma}$ = $\textbf{y}(\mathbf{w}^\top\mathbf{x}+b)$ 会随 $(\mathbf{w},b)$ 缩放而任意变化而不唯一 ! 引入欧几里得距离的归一化后才能保证尺度在仿射变换后仍不变。

2.2 支持向量 & 间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。使约束条件式成立的数据点如下：

$y_{i}=+1 \rightarrow H_{1}:y_{i}\left(w \cdot x_{i}+b\right)-1=0$

$y_{i}=-1 \rightarrow H_{2}:y_{i}\left(w \cdot x_{i}+b\right)+1=0$

2.3 间隔最大化问题

SVM的中心问题就是求得最大间隔分离超平面，即：

$\begin{aligned}
\max_{\mathbf{w}, b} \quad & \gamma \\
\text{s.t.} \quad & y_i(\mathbf{w}^\top\mathbf{x}_i + b) \geq \gamma, \quad i = 1, \ldots, n
\end{aligned}$

转换为函数间隔表达：

$\begin{aligned}
\max_{\mathbf{w}, b} \quad & \frac{\hat{\gamma_i}}{|\mathbf{w}|} \\
\text{s.t.} \quad & y_i(\mathbf{w}^\top\mathbf{x}_i + b) \geq 1, \quad i = 1, \ldots, n
\end{aligned}$

直接优化此式复杂，不如将函数间隔固定为1，仿射变换$w$,$b$，$\hat{\gamma}$也会等价变换，同时最小化 $\frac{1}{2}|\mathbf{w}|^2$（至于1/2的系数我认为是方便导数的计算） 等价于最大化 $\frac{1}{|\mathbf{w}|}$ , 最终优化问题可表述为：

$\begin{aligned}
\min_{\mathbf{w}, b} \quad & \frac{1}{2}|\mathbf{w}|^2 \\
\text{s.t.} \quad & y_i(\mathbf{w}^\top\mathbf{x}_i + b) -1\geq 0, \quad i = 1, \ldots, n
\end{aligned}$

这就是SVM的基本形式，不难看出，目标函数为凸函数，问题转换成了一个凸二次规划问题。btw，最大间隔分离超平面具有唯一存在性，详细证明可参考李航老师撰写的《统计学习方法》Page117。

2.4 对偶问题转化

对上述的凸优化二次规划问题构建拉格朗日函数，引入拉格朗日乘子 $\alpha_i$ ,将不等式、等式约束写成 $L(·) = f(x) + \lambda_1 g(x) + \cdots + \lambda_k h(x)$ 引入定义：

$$L(w,b,\alpha) = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}\alpha_i[y_i(\mathbf{w}^\top\mathbf{x}_i + b) - 1] = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}\alpha_iy_i(\mathbf{w}^\top\mathbf{x}_i + b) - \sum_{i=1}^{n}\alpha_i$$

$\alpha = \{\alpha_1, \alpha_2, …, \alpha_n\}$为拉格朗日乘子向量

将原始问题变为

$$\max_{\alpha}\min_{\textbf{w},b} L(w,b,\alpha)$$

对于优化问题接触不多的盆友们或许觉得优化变量的变化，以及minmax的提出莫名其妙，我们一一解答：

问题02: 对偶问题和原问题等价吗？

在满足KKT条件下，两问题的最优值相等，$x^{*}$ 是原问题最优解 $\iff$ 存在 $(\lambda^{*}, \nu^{*})$ 满足KKT条件，其中：

$$\lambda^* f_i(x^*) = 0$$ $$\nabla f_0(x^*) + \sum \lambda_i^* \nabla f_i(x^*) + \sum \nu_j^* \nabla h_j(x^*) = 0$$

若问题不满足强对偶条件（比如非凸问题），可能出现 $d^ < p^$
这个差值叫对偶间隙——此时对偶问题只能给出原问题的下界，不能完全替代。

问题03: 对偶问题为什么这样优化？

换个优化顺序，把困难的问题变简单，
对于固定的 $\alpha$，我们对 $w$ 和 $b$ 求偏导：

$$\frac{\partial L}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i = 0 \Rightarrow \mathbf{w} = \sum_{i=1}^n \alpha_i y_i \mathbf{x}_i$$ $$\frac{\partial L}{\partial b} = -\sum_{i=1}^n \alpha_i y_i = 0 \Rightarrow \sum_{i=1}^n \alpha_i y_i = 0$$

将这个最优 $\mathbf{w}$ 代回拉格朗日函数：

$$\begin{aligned} L(w,b,\alpha) &= \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^n \alpha_i y_i (\mathbf{w}^{\top}\mathbf{x}_i + b) + \sum_{i=1}^n \alpha_i \\ &= \frac{1}{2}\|\mathbf{w}\|^2 - \mathbf{w}^{\top}\mathbf{w} - b\sum_{i=1}^n \alpha_i y_i + \sum_{i=1}^n \alpha_i \\ &= -\frac{1}{2}\|\mathbf{w}\|^2 + \sum_{i=1}^n \alpha_i \quad (\sum \alpha_i y_i = 0) \\ &= \sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j {x}_i^\top {x}_j \end{aligned}$$

接着，处理问题，就简单许多(在哪┭┮﹏┭┮)

$$\begin{aligned} \min_\alpha \quad & -\sum_{i=1}^n \alpha_i + \frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j ({x}_i · {x}_j) \\ \text{s.t.} \quad &\sum_{i=1}^n \alpha_i y_i = 0, \quad i = 1, \ldots, n \\ \quad & \alpha_i \geq 0, \quad i = 1, \ldots, n \end{aligned}$$

3. 从硬到软：线性不可分问题

3.1 软间隔支持向量机

上述的支持向量机算法针对问题仅局限于线性可分问题，若使用SVM处理线性不可分问题最大的问题即是找不到支持向量或间隔过小算法无法收敛。允许有部分数据点不守规则的方法就变为软间隔，对约束而言：$ y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}$ ，单个点的违反 $\xi_{i}$ 是被允许的，而所有点的违背值得尽可能最小：

$$\begin{align*} \min _{w, b, \xi} & \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i} \\ \text { s.t. } & y_{i}\left(w \cdot x_{i}+b\right) +\xi_{i}\geqslant 1 \\ & \xi_{i} \geqslant 0, \quad i=1,2, \cdots, nn \end{align*}$$

转化为对偶问题并化简，不难发现 $C$ 就是算法中可以调参的超参数之一：

$$\begin{align*} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & 0 \leqslant \alpha_{i} \leqslant C, \quad i=1,2, \cdots, n \end{align*}$$

3.2 hinge loss function 引入

对于约束条件 $\xi_i \geq 1-y_i(w\cdot x_i+b)$ 和 $\xi_i \geq 0$ 而言，解得：$\xi_i \geq \max(0,1-y_i(w\cdot x_i+b))$ 这样可以将问题合并为一个式子：

$$\min_{w,b} \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{n}\max(0,1-y_i(w\cdot x_i+b))$$

而 $\max(0,1-y_i(w\cdot x_i+b))$ 则是合页损失函数 (hinge loss function) 。

4. 线性到非线性：核技巧

4.1 非线性问题阐释

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。对给定的一个训练数据集 $D = {(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}$，其中，数据点 $x_i$ 对应的标记有两类 $y_i ∈ Y = {-1,+1}，i = 1,2,…,n$。如果能用 $Rⁿ$ 中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。

简单地说，在SVM中使用核函数技巧就像把地面上投射着两团浑在一起的影子（原始数据），映射到真实空间中，发现影子其实来自空中两座分离的雕塑——一座A雕塑，一座B雕塑，彼此清晰分开，中间可以轻松地使用玻璃板之类的平面隔开。

4.2 核技巧

在前文对偶问题中，我们已经得到了一个非常关键的形式：

$$\begin{align*} \min_\alpha \quad \frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle - \sum_{i=1}^n \alpha_i \end{align*}$$

可以发现，样本空间中数据点从头到尾只以内积的形式出现。如果设想存在一个映射函数：

$$\phi: \mathbb{R}^n \rightarrow \mathcal{H}$$

将原始空间中的样本 $x$ 映射到一个更高维（甚至无限维）的特征空间中，使得原本线性不可分的数据在该空间中反而线性可分。

在映射后的空间中，SVM 的对偶问题形式变为：

$$\begin{align*} \min_\alpha \quad \frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j \langle \phi(x_i), \phi(x_j) \rangle - \sum_{i=1}^n \alpha_i \end{align*}$$

就像我们提出设想时那样，理论上可能出现的无限维空间的内积庞大计算量，仅有计算同该空间内积值相同的某个可计算的函数才有实现的可能。这就是核技巧的核心思想：用核函数直接计算高维空间的内积，避免维度灾难。

使用 $K(x_i,x_j)$ 代替 $\phi(x_i) \cdot \phi(x_j)$ ，可计算的问题最终形式如下：

$$\begin{aligned} \min_\alpha \quad & \frac{1}{2}\sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j K(x_i,x_j) - \sum_{i=1}^n \alpha_i \\ \text{s.t.} \quad & \sum_{i=1}^n \alpha_i y_i = 0 \\ & 0 \le \alpha_i \le C \end{aligned}$$

最终的分类决策函数为：

$$\begin{aligned} f(x) = \text{sign}\left( \sum_{i=1}^n \alpha_i y_i K(x_i, x) + b \right) \end{aligned}$$

4.3 常用核函数

并非任意函数都可以作为核函数。根据 Mercer 定理，一个合法核函数必须对应某个特征空间中的内积。以下是最常见的几类核函数。

4.3.1 多项式核（Polynomial Kernel）

$$K(x_i, x_j) = (\gamma x_i^\top x_j + \xi)^n$$

• 相当于引入特征之间的高阶组合
• 参数：
  • $n$：多项式阶数
  • $\gamma$、$\xi$ 分别表示尺度变化和偏置变化
• 高阶时容易过拟合！当$\gamma = 1$、$\xi = 0$ 、$n=1$时为线性核

4.3.3 高斯核 / RBF 核

$$K(x_i, x_j) = e^{\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)}$$

• 对应无限维希尔伯特空间

证明:

$$K(x_i, x_j) = e^{-\frac{\|x_i - x_j\|^2}{2\sigma^2}}\\ = e^{-\frac{1}{2\sigma^2}(\|x_i\|^2 - 2x_i^\top x_j + \|x_j\|^2)}\\ = (e^{\|x_i\|^2}\cdot e^{\|x_j\|^2} \cdot e^{-2x_i^\top x_j})^{-\frac{1}{2\sigma^2}}$$

对第三项进行泰勒展开：

$$e^{\frac{x_i^\top x_j}{\sigma^2}} = \sum_{k=0}^\infty \frac{1}{k!} \left(\frac{x_i^\top x_j}{\sigma^2}\right)^k\\ \text{注意 我这的} x_i^\top x_j \text{是内积形式，对于样本空间而言,相当与下面的东西：}\\ \left(x^{\top} x^{\prime}\right)^{n}=\sum_{|\alpha|=n} \frac{n!}{\alpha!}\left(\prod_{i=1}^{d} x_{i}^{\alpha_{i}}\right)\left(\prod_{i=1}^{d} x_{i}^{\prime \alpha_{i}}\right)\\ K(x, x') = \left(x^{\top} x^{\prime}\right)^{n}=\sum_{|\alpha|=n} \frac{n!}{\alpha!}\left(\prod_{i=1}^{d} x_{i}^{\alpha_{i}}\right)\left(\prod_{i=1}^{d} x_{i}^{\prime \alpha_{i}}\right)k\left(x, x^{\prime}\right)=\\ \sum_{n=0}^{\infty} \sum_{|\alpha|=n}\left[\exp \left(-\frac{\|x\|^{2}}{2 \sigma^{2}}\right) \frac{1}{\sqrt{\alpha!\sigma^{2 n}}} \prod_{i=1}^{u} x_{i}^{\alpha_{i}}\right]\left[\exp \left(-\frac{\left\|x^{\prime}\right\|^{2}}{2 \sigma^{2}}\right) \frac{1}{\sqrt{\alpha!\sigma^{2 n}}} \prod_{i=1}^{u} x_{i}^{\prime \alpha_{i}}\right]=\phi_{\alpha}(x)\cdot\phi_{\alpha}(x')\\ \text{映射函数为}\phi_{\alpha}(x)\quad 其中\alpha\in\mathbb{N}^{d}\quad 理论上维数无限$$

• 局部性强，拟合能力极强
• 超参数：
  • $\gamma$：控制样本影响范围
  • (C)：控制间隔与误差权衡

5. 序列最小化算法 (SMO)

流程说明：

本文参考了如下的书籍，衷心感谢每位老师对于基础知识普及教育的坚守！：

1. 统计学习方法 第二版 李航 清华大学出版社
2. 机器学习 周志华 清华大学出版社
3. bilbili up主 简博士