支持向量机 (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。

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}) = \underbrace{\frac{1}{2}\Vert\vec{w}\Vert^2}_{f(\vec{w},b)} + \sum \alpha_i \underbrace{\left(1-y_i(\vec{w}\cdot\vec{x_i}-b)\right)}_{h_i(\vec{w},b)\le0} $$

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

$$ \begin{cases} \frac{\partial \mathcal {L}}{\partial \vec{w}} = \vec{w}-\sum\alpha_i y_i \vec{x_i}=0 \\ \frac{\partial \mathcal {L}}{\partial b} =\sum\alpha_i y_i =0 \end{cases} $$

可得:

$$ \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$ 即可得到模型:

$$ \begin{aligned} f(\vec{x}) &=\vec{w}\cdot\vec{x}+b \\ &=\sum_{i=1}^{m}\alpha_i y_i \left(\vec{x_i}\cdot\vec{x}\right)+b \end{aligned} $$

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

$$ \begin{cases} \alpha_i\ge 0 \ ; \\ y_i f(\vec{x_i}) - 1\ge 0 \ ; \\ \alpha_i(y_i f(\vec{x_i})-1) = 0 \ . \end{cases} $$

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

软间隔

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

$$ \xi_i=\max\left\{ 1-y_i(\vec{w}\cdot\vec{x_i}+b), 0 \right\} $$
那么原来的 SVM 的优化问题就会变成: $$ \begin{array}{l} \min\limits_{\vec{w},b}\ \frac{1}{2}\Vert\vec{w}\Vert^2 + C\sum_{i=1}^{m}\max\left\{1-y_i(\vec{w}\cdot\vec{x_i}+b), 0\right\} \\ \text{s.t.} \quad 1-y_i(\vec{w}\cdot\vec{x_i}+b) \le 0, \quad i=1,2,...,m \end{array} $$ 其中的 $\max(1-z, 0)$ 称为“折页损失”(hinge loss)。接着引入“松弛变量”(slack variable) $\xi_i\ge0$,将上式重写为: $$ \begin{aligned} &\min\limits_{\vec{w},b}\ \frac{1}{2}\Vert\vec{w}\Vert^2 + C\sum_{i=1}^{m}\xi_{i} \\ \text{s.t.}\quad &y_i(\vec{w}\cdot\vec{x_i}+b) \ge 1-\xi_i \\ &\xi_i \ge 0, \ i=1,2,...,m \end{aligned} $$ 即可得到“软间隔支持向量机”(soft margin SVM)。求解方法与前面是一样的,具体过程可以参考西瓜书。

核方法

当遇到样本是非线性可分时,一般的线性 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)

参考:

加载评论