支持向量机 (SVM) 的解析与推导

两年前在面某司 AI Lab 的时候，就有被问到支持向量机（support vector machines, SVM）的推导。正好上一学期在 Machine Learning 的课上又学到，这里便记录一下 SVM 的基本推导过程。

前言

在开始之前先推荐一下李航的《统计学习方法》以及周志华的《机器学习》。这两本书可以结合起来看，对理解许多机器学习的原理有非常大的帮助。SVM 的推导中有大量的定理以及数学公式，看着确实挺吓人，但是只要一步步地弄懂，就也不是非常的难。这篇文章花费了挺长的时间来写，参考了上面提到的两本书，以及尽量简单的将每一步解释清楚，不过还是有一些数学的细节以及严谨证明略过了，因为也不在本文的讨论范围之内。

这里将讨论最基本的二分类的支持向量机（support vector machines, SVM），考虑训练样本集 $D={ (\vec{x_1},y_1),...,(\vec{x_m},y_m), y_i \in {-1,+1} }$。将从最基本的超平面划分训练样本开始，导出 SVM 的基本问题，再利用对偶问题求解，最后讨论 SVM 的核技巧，以及如何在 Python 中使用 SVM。

超平面

超平面（Hyper Plane）是在样本空间中的一个平面。在我们熟悉的二维平面上，一条直线的方程可以表示为 $ax+by+c=0$，推广到多维的情况之后，超平面可以用向量的形式表示为 $\vec{w}\cdot\vec{x}+b=0$，记为 $(\vec{w}, b)$ 的形式，其中 $\vec{w}$ 是法向量，而 $b$ 为位移项。

考虑任意一点 $\vec{x}$ 到超平面之间的距离，可以表示为：

$$ \gamma=\frac{\vert\vec{w}\cdot\vec{x}+b\vert}{\Vert \vec{w} \Vert} $$

超平面能将样本空间划分成两部分。假设超平面 $(\vec{w}, b)$ 将所有样本正确分类，即对于任意的 $(\vec{x_i},y_i)\in D$，若 $y_i=+1$，那么 $\vec{w}\cdot\vec{x}+b > 0$，若 $y_i=-1$，那么 $\vec{w}\cdot\vec{x}+b < 0$。像这样的决策函数可以表示为：

$$ y_i=\text{sign}(\vec{w}\cdot\vec{x_i}+b) $$

那么，在一个空间中，会存在多个超平面能够将训练样本分开，那么究竟该努力去找哪一个超平面呢？

最大间隔

对于 $(\vec{x_i}, y_i)$，我们可以将上面的距离公式的分子部分代入 $y_i$ 改写成：

$$ \gamma_i=\frac{y_i(\vec{w}\cdot\vec{x}+b)}{\Vert \vec{w} \Vert} $$

定义间隔（margin）$\gamma$ 为所有样本中离超平面最近的那个，即 $\gamma=\min \gamma_i$，那么 $\gamma_i \ge \gamma$ 总是成立的，代入上式可得：

$$ \frac{y_i(\vec{w}\cdot\vec{x}+b)}{\Vert \vec{w} \Vert} \ge \gamma $$

因此，SVM 的问题就变成了找到“最大间隔”（maximum margin）的超平面，使得 $\gamma$ 最大，即：

$$ \begin{array}{l}\max\limits_{(\vec{w},b)} \ \min\limits_{i} \frac{1}{\Vert\vec{w}\Vert}\vert\vec{w}\cdot\vec{x_i}+b\vert \\ \text{s.t.} \quad y_i(\vec{w}\cdot\vec{x_i}+b) > 0, \quad i=1,2,...,m \end{array} $$

因为间隔始终大于 0，即 $\vert\vec{w}\cdot\vec{x_i}+b\vert > 0$，则可以通过缩放 $(\vec{w}, b)$ 使得 $\min\limits_i \vert\vec{w}\cdot\vec{x_i}+b\vert =1$，那么上面的问题就变成 $\max\frac{1}{\Vert\vec{w}\Vert} $，即 $\min\Vert\vec{w}\Vert$，在其它书里通常会被等价成 $\min\frac{1}{2}\Vert\vec{w}\Vert^2$，于是上式可以重写成：

$$ \begin{array}{l} \min\ \frac{1}{2}\Vert\vec{w}\Vert^2 \\ \text{s.t.} \quad y_i(\vec{w}\cdot\vec{x_i}+b) \ge 1, \quad i=1,2,...,m \end{array} $$

是一个凸二次规划（convex quadratic programming）问题，这样就能够利用上现有的求解优化问题的方法。

对偶问题

首先考虑一个最优化问题：

$$ \begin{array}{l}\min f(\vec{z}) \\ \text{s.t.} \quad h_i(\vec{z})\le 0 \end{array} $$

引入拉格朗日函数 $\mathcal{L}(\vec{z},\vec{\alpha})$，其中 $\vec{\alpha}=(\alpha_1,...,\alpha_m)$，$\alpha_i \ge 0$ 为拉格朗日乘子，则有：

$$ \mathcal{L}(\vec{z},\vec{\alpha})=f(\vec{z})+\sum \alpha_i h_i(\vec{z}) $$

那么上面的最优化问题等价于：

$$ \min\limits_{\vec{z}}\ \max\limits_{\vec{\alpha}\ge 0 } \ \mathcal{L} (\vec{z}, \vec{\alpha}) $$

称为原始问题（primal problem）。下面来证明其等价于一开始的优化问题，主要思路是将拉格朗日函数展开代入，再利用 $\vec{\alpha}\ge0$的条件消去第二项：

$$ \begin{aligned} & \min\limits_{\vec{z}}\ \max\limits_{\vec{\alpha}\ge 0 } \ \mathcal{L} (\vec{z}, \vec{\alpha}) \\ = &\min\limits_{\vec{z}}\left( f(\vec{z})+\max\limits_{\vec{\alpha}\ge 0}\sum \alpha_i h_i(\vec{z})\right) \\ =& \min\limits_{\vec{z}}\left( f(\vec{z})+ \begin{cases}0, &\text{if } h_i(\vec{z})\le 0 \\ \infty, &\text{if } h_i(\vec{z})\gt 0 \end{cases} \right) \\ =&\min\limits_{\vec{z}} f(\vec{z}) \end{aligned} $$

将该问题的中的 $\min$ 和 $\max$ 交换位置，即可得到其对偶问题（dual problem）：

$$ \max\limits_{\vec{\alpha}\ge 0 }\ \min\limits_{\vec{z}} \mathcal{L} (\vec{z}, \vec{\alpha}) $$

原始问题与对偶问题的关系：

$$ \max\limits_{\vec{\alpha}\ge 0 }\ \min\limits_{\vec{z}} \mathcal{L} (\vec{z}, \vec{\alpha}) \le \min\limits_{\vec{z}}\ \max\limits_{\vec{\alpha}\ge 0 } \mathcal{L} (\vec{z}, \vec{\alpha}) $$

在某些条件下，原始问题与对偶问题的最优值相等，这时候可以用解对偶问题代替解原始问题。该条件称为 KKT（Karush-Kunh-Tucker）条件，具体证明超出了本文的涉及范围，我自己也不会，就先略过。在这个条件下，可以从 SVM 问题的对偶问题求解，进而得到 SVM 的解。

求解 SVM

将 SVM 的问题用拉格朗日函数的形式重写为：

令 $\mathcal{L}(\vec{w}, b, \vec{\alpha})$ 对于 $\vec{w}$ 和 $b$ 的偏导数等于零：

可得：

$$ \begin{aligned} \vec{w}&=\sum\alpha_i y_i \vec{x_i} \\ 0 &=\sum\alpha_i y_i \end{aligned} $$

将上式代入 $\mathcal{L}(\vec{w}, b, \vec{\alpha})$ 可得：

$$ \begin{aligned} \mathcal{L}(\vec{w}, b, \vec{\alpha}) =& \frac{1}{2}\left(\sum\alpha_i y_i \vec{x_i}\right)\cdot\left(\sum\alpha_i y_i \vec{x_i}\right) \\ &+ \sum\alpha_i\left(1-y_i\left(\left(\sum\alpha_i y_i \vec{x_i}\right)\cdot\vec{x_i}-b)\right)\right) \\ =&\sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j \left(\vec{x_i}\cdot \vec{x_j}\right) \end{aligned} $$

这样，对偶问题就变成：

$$ \begin{aligned} &\max\limits_{\vec{\alpha}\ge 0 }\ \min\limits_{\vec{z}} \mathcal{L} (\vec{z}, \vec{\alpha}) \\ \implies & \max\limits_{\vec{\alpha}\ge 0 } \sum_{i=1}^{m}\alpha_i - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i \alpha_j y_i y_j \left(\vec{x_i}\cdot \vec{x_j}\right) \\ &\ \text{s.t.}\quad \sum\alpha_i y_i = 0,\ \alpha_i \ge 0 \end{aligned} $$

解出 $\vec{\alpha}$ 后，求出 $\vec{w}$ 与 $b$ 即可得到模型：

具体求解过程需要满足上面提到的 KTT 条件：

求解上面的对偶问题的一个著名算法是 SMO (Sequential Minimal Optimization)，这里不展开叙述。

软间隔

上面我们考虑的都是数据可以分隔的情况，那么当数据集并不是完全能被超平面分隔，即有些点不满足约束 $y_i(\vec{w}\cdot\vec{x_i}+b) \ge 1$，那可以设定一个惩罚项：

核方法

当遇到样本是非线性可分时，一般的线性 SVM 就无法很好的分类，这时候可以采用核技巧（kernel trick），将样本映射至高维空间，变成高维空间中线性可分的即可。

考虑一个映射函数 $\phi(\vec{x})$，将 $d$ 维特征映射至 $m$ 维： $$ \phi(\vec{x}): \mathbb{R}^d \to \mathbb{R}^m $$ 定义核函数（kernel function）： $$ K(\vec{x_i}, \vec{x_j})= \phi(\vec{x_i}) \cdot \phi(\vec{x_j}) $$ 核技巧的思想是用核函数 $K$ 避免在高维 $m$ 空间中计算映射函数的内积，这样能够极大简化运算。

根据 Mercer's theorem，函数 $K$ 能够满足成为核函数的充分必要条件是 $K$ 是半正定（positive semidefinite），即

$$ \sum_{i,j=1}^m c_i c_j K(\vec{x_i}, \vec{x_j}) \geq 0 $$ 常用的核函数有多项式核函数（Polynomial function）：

$$ K(\vec{x_i}, \vec{x_j}) = (\vec{x_i} \cdot \vec{x_j} + 1)^d $$ 以及高斯核函数（Guassian radial basis function），通常称为 RBF Kernel：

$$ K(\vec{x_i}, \vec{x_j}) = \exp \left(- \frac{\Vert\vec{x_i}-\vec{x_j}\Vert^2}{2\sigma^2} \right) $$

更多的关于核方法的详细推导，可以参考推荐的两本书中的相应章节。

Python 中使用 SVM

在 Python 中可以用 scikit-learn 非常方便的使用 SVM。对于二分类或多分类问题，通常使用 SVC()，可以在参数中指定它的 kernel，当 kernel='linear' 时便退化成了线性支持向量机。一般使用 rbf 核的 SVM 会有较好的分类效果。

1
2
3
4
5

from sklearn import svm
X = [[0, 0], [1, 1]]
y = [0, 1]
clf = svm.SVC()
clf.fit(X, y)

参考：

• 《统计学习方法》李航
• 《机器学习》周志华
• Support vector machine - Wikipedia
• 从零推导支持向量机(SVM)