有人说学习某个知识不能只看一本书，要多看同一知识的不同书籍，这样可以在学习中作对比。最近我在学习支持向量机（support vector machines, SVM），不仅看了李航的《统计学习方法》和周志华的《机器学习》的书，而且在网上看了不少关于 SVM 原理与公式推导的博客。所以趁现在还记得，赶紧把它写下来。本文主要记录 SVM 的原理、公式推导和 Python 使用 SVM 的例子。
1. 间隔与超平面
给定 \(D = \lbrace (x_0, y_0), (x_1, y_1), \cdots, (x_N, y_N) \rbrace\) 的训练样本集，分类学习最基本的想法就是基于训练集 \(D\) 在样本空间中找到一个分离超平面，将不同类别的样本分开。但是能将训练样本分开的超平面可能有很多，如图所示，我们应该努力去找到哪一个呢？
直观上看，应该去找位于两类训练样本“正中间”的分离超平面，即上图中红色的那个。因为该分离超平面对训练样本局部扰动的“容忍”性最好。在样本空间中，分离超平面可通过如下线性方程来描述： \[\begin{aligned} \omega^T x + b = 0 \end{aligned}\]
其中 \(\omega = (w_0; w_1; \cdots; w_d)\) 为法向量，决定了超平面的方向；\(b\) 为位移项，决定了超平面与原点之间的距离。显然，分离超平面可被法向量 \(\omega\) 和位移 \(b\) 所确定。下面我们用 \((\omega, b)\) 来代表分离超平面。在样本空间中，任意点 \(x\) 到超平面 \((\omega, b)\) 的距离可写为： \[\begin{aligned} \gamma = \frac{\left | \omega^T + b \right | }{\left \| \omega \right \| } \end{aligned}\]
一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面 \((\omega, b)\) 确定的情况下，\(\left | \omega x + b \right |\) 能够相对地表示点 \(x\) 距离超平面的远近。而 \(\omega x + b\) 的符号与类标记 \(y\) 的符号是否一致能够相对地表示分类是否正确。所以可用量 \(y(\omega x + b)\) 来表示分类的正确性及确信度，这就是函数间隔（functional margin）的概念。对于给定的训练样本 \(D\) 和超平面 \((\omega, b)\)，定义超平面 \((\omega, b)\) 关于样本点 \((x_i, y_i)\) 的函数间隔为： \[\begin{aligned} \hat{\gamma_i} = y_i(\omega x_i + b) \end{aligned}\]
函数间隔可以表示分类预测的正确性及确信度。但是在选择分离超平面时，只有函数间隔还不够。因为只要成比例地改变 \(\omega\) 和 \(b\)，例如将它们改为 \(2\omega\) 和 \(2b\)，超平面并没有改变，但函数间隔却成了原来的 2 倍。这一事实告诉我们，可以对分离超平面的法向量 \(\omega\) 加某些约束，如规范化，\({\left \| \omega \right \| = 1}\)，使得间隔是确定的。这时函数间隔成为几何间隔（geometric margin）。 \[\begin{aligned} \gamma_i = \frac{y_i(\omega x_i + b)}{\left \| \omega \right \| } \end{aligned}\]
2. 间隔最大化
定义几何间隔 \(\gamma\) 为所有样本中离分离超平面最近的那个，即 \(\gamma = \mathop{\min}\limits_{i=1,\cdots,N} \gamma_i\)。又因为 \(\gamma_i \geq \gamma\)，故可得： \[\begin{aligned} \frac{y_i(\omega x_i + b)}{\left \| \omega \right \| } \geq \gamma \end{aligned}\]
同理可得函数间隔不等式： \[\begin{aligned} \begin{aligned} y_i(\omega x_i + b) \geq \hat{\gamma} \end{aligned} \end{aligned}\]
由上述两式子可得函数间隔和几何间隔关系： \[\begin{aligned} \gamma_i = \frac{\hat{\gamma_i}}{\left \| \omega \right \| } \end{aligned}\]
\[\begin{aligned} \gamma = \frac{\hat{\gamma}}{\left \| \omega \right \| } \end{aligned}\]
SVM 的基本思想是求解出能够正确划分数据集且几何间隔最大的分离超平面，间隔最大化意味着有充分大的确信度能对数据集进行分类。然而如何寻找间隔最大的分离超平面？这个问题可以表示为下面的约束最优化问题： \[\begin{array}{l} \mathop{\max}\limits_{\omega, b} \quad \gamma \\ s.t. \quad \frac{y_i(\omega x_i + b)}{\left \| \omega \right \| } \geq \gamma, \quad i = 1, 2, \cdots, N \end{array}\]
结合函数间隔和几何间隔的关系，约束最优化问题可改写为： \[\begin{array}{l} \mathop{\max}\limits_{\omega, b} \quad \frac{\hat{\gamma}}{\left \| \omega \right \| } \\ s.t. \quad y_i(\omega x_i + b) \geq \hat{\gamma} , \quad i = 1, 2, \cdots, N \end{array}\]
函数间隔 \(\hat{\gamma}\) 的取值并不影响最优化问题的解。事实上，假设将 \(\omega\) 和 \(b\) 按比例改变为 \(\lambda \omega\) 和 \(\lambda b\) ，这时函数间隔成为 \(\lambda \hat{\gamma}\)。函数间隔的这一改变对上面最优化问题的不等式约束没有影响，对目标函数的优化也没有影响。所以再次将上式改为： \[\begin{array}{l} \mathop{\max}\limits_{\omega, b} \quad \frac{1}{2} \left \| \omega \right \|^2 \\ s.t. \quad y_i(\omega x_i + b) - 1 \geq 0 , \quad i = 1, 2, \cdots, N \end{array}\]
上式是 SVM 的目标函数，同时也是一个凸二次规划（convex quadratic programming）问题。
3. 对偶问题与求解
对上式 SVM 目标函数使用拉格朗日乘子法可得到其“对偶问题”（dual problem）。具体来说，对目标函数的每条约束添加拉格朗日乘子 \(\alpha_i \geq 0\)，则该问题的拉格朗日函数可改写为： \[\begin{aligned} L(\omega, b, \alpha) = \frac{1}{2} \left \| \omega \right \|^2 + \sum_{i=1}^{m} \alpha_i(1 - y_i(\omega^T x_i + b)) \end{aligned}\]
其中 \(\alpha = (\alpha_0;\alpha_1;\cdots;\alpha_m)\)。令 \(L(\omega, b, \alpha)\) 对 \(\omega\) 和 \(b\) 的偏导为零可得： \[\begin{aligned} \omega = \sum_{i=0}^{m} \alpha_i y_i x_i \end{aligned}\]
\[\begin{aligned} 0 = \sum_{i=0}^{m} \alpha_i y_i \end{aligned}\]
将上式代入 SVM 的拉格朗日函数，即可将 \(L(\omega, b, \alpha)\) 中的 \(\omega\) 和 \(b\) 消去，再考虑到约束条件，就得到目标函数的对偶问题： \[\begin{array}{l} \mathop{\max}\limits_{\alpha} \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 x_i^T x_j \\ s.t. \quad \sum_{i=1}^{m} \alpha_i y_i \quad \alpha_i \geq 1,2,\cdots,m \\ \end{array}\]
解出 \(\alpha\) 后，求出 \(\omega\) 和 \(b\) 即可得到模型： \[\begin{aligned} f(x) & = \omega^T x + b \\ & = \sum_{i=1}^{m} \alpha_i y_i x_i^T x +b \end{aligned}\]
从对偶问题解出的 \(\alpha_i\) 是拉格朗日乘子，它恰好对应着训练样本 \((x_i, y_i)\)。注意到目标函数的不等式约束条件，因此上述过程需满足 KKT （Karush-Kuhn-Tucker）条件，即要求： \[\begin{cases} \alpha_i \geq 0 \\ y_i f(x_i) - 1 \geq 0 \\ \alpha_i(y_i f(x_i) - 1) = 0 \end{cases}\]
在程序上求解对偶问题有一个很著名算法 SMO (Sequential minimal optimization)，这里我就不展开叙述了。
4. Python 代码
使用 iris 数据集训练 SVM 模型
1 | from sklearn import svm, datasets |
运行程序
1 | python svm.py |