支持向量机（SVM）是机器学习的主流技术之一。很多学者认为它是监督学习最好的定式算法。它的基本思想是在正确分类的前提下，尽可能将不同类分开。为了突破线性不可分的限制，SVM采用核函数技巧，将数据从原特征空间映射到高维特征空间，使得不同类数据变得可分。SVM方法具有十分严格的数学理论基础，且在实际应用中泛化能力强，因此是监督学习领域中最受欢迎的方法之一。
基本原理及算法
原问题及对偶问题
SVM的原问题是在正确划分标签的约束条件下，最大化两个异类支持向量到超平面之间的间隔，数学上该问题可以描述为： \[ min_{\mathbf{w},b} \frac{1}{2} \|\mathbf{w}\|^2 \\ s.t.\ y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1, i=1, 2, ..., m. \] 将带约束条件的反问题转化为无约束条件反问题。引入拉格朗日乘子\(\alpha_i \geq 0, i=1,2,...,m\)，对应的拉格朗日函数可写为： \[ L(\mathbf{w}, b, \mathbf{\alpha}) = \frac{1}{2} \| \mathbf{w} \|^2 - \sum_{i=1}^{m} \alpha_i \left (y_i (\mathbf{w}^T \mathbf{x}_i + b) -1 \right) \] 分别关于\(\mathbf{w}\)和\(b\)求偏导数： \[ \mathbf{w} = \sum_{i=1}^{m} \alpha_i y_i \mathbf{x}_i \\ 0 = \sum_{i=1}^{m} \alpha_i y_i \] 带入上面\(\mathbf{w}\)的公式，可将拉格朗日函数改为： \[ L(\mathbf{\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 \mathbf{x}_i^T \mathbf{x}_j^T \] 原问题可以转化为以下的对偶问题： \[ max_{\mathbf{\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 \mathbf{x}_i \mathbf{x}_j^T \\ s.t. \ \sum_{i=1}^m \alpha_i y_i = 0, \\ \] 需要注意的是：假如原问题在\(\mathbf{w}^*\)上取得极小值，由于拉格朗日函数第二项总是小于0，因此，最优解\(\alpha^*\)位于拉格朗日函数的极大值点上。 解出\(\mathbf{\alpha}\)后，求出\(\mathbf{w}\)和\(b\)即可得到模型： \[ f(\mathbf{x}) = \mathbf{w}^T \mathbf{x} + b = \sum_{i=1}^m \alpha_i y_i \mathbf{x}_i^T \mathbf{x} +b. \] 另外，求解对偶问题得到的\(\alpha_i\)需要满足KKT（Karush-Kuhn-Tucker）条件， \[ \alpha_i \geq 0, i=1, 2, ..., m \\ y_i f(\mathbf{x}_i) - 1 \geq 0 \\ \alpha_i (y_i f(\mathbf{x}_i) - 1) = 0 \] 其中KKT第一个条件是拉格朗日乘子本身的要求，第二个条件是原问题的约束条件，第三个条件使得对偶问题的目标函数和原问题的目标函数相同。
软边界及正则化
前面假定训练样本是线性可分的，然而实际应用中往往很难找到一个超平面（甚至核函数）将不同类的样本完全分开；退一步说，即便找了了某个超平面或者核函数可以将训练集在特征空间中分开，但是也很难断定这不是过拟合产生的。缓解这个问题的一个办法是引入“软间隔”的概念，以允许SVM在某些样本上出错。 数学上，目标函数变为： \[
min_{\mathbf{w},b, \xi_i} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^{m} \xi_i \\
s.t.\ y_i(\mathbf{w}^T \mathbf{x}_i + b) + \xi_i - 1 \geq 0, i=1, 2, ..., m. \\
\xi_i \geq 0, i=1, 2, ..., m.
\] 上式实际上用hinger函数替代0/1损失函数推导之后得到的结果。
引入拉格朗日乘子\(\alpha_i \geq 0,\beta_i \geq 0\)，拉格朗日函数为： \[
L(\mathbf{w}, b, \xi_i, \mathbf{\alpha}, \mathbf{\beta}) = \frac{1}{2} \| \mathbf{w} \|^2 + C \sum_{i=1}^{m} \xi_i - \sum_{i=1}^{m} \alpha_i \left (y_i (\mathbf{w}^T \mathbf{x}_i + b) + \xi_i -1 \right) - \sum_{i=1}^{m} \beta_i \xi_i \\
= \frac{1}{2} \| \mathbf{w} \|^2 + \sum_{i=1}^{m} (C-\alpha_i -\beta_i) \xi_i - \left (\sum_{i=1}^m \alpha_i y_i \mathbf{x}_i^T \right) \mathbf{w} - \left( \sum_{i=1}^m \alpha_i y_i \right) b + \sum_{i=1}^m \alpha_i
\] 分别关于\(\mathbf{w}, b, \xi_i\)求偏导数： \[
\mathbf{w} = \sum_{i=1}^{m} \alpha_i y_i \mathbf{x}_i \\
0 = \sum_{i=1}^{m} \alpha_i y_i \\
\alpha_i = C - \mu_i
\] 将上面的公式带入拉格朗日函数中，得到： \[
L(\mathbf{\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 \mathbf{x}_i^T \mathbf{x}_j^T
\] 原问题可以转化为以下的对偶问题： \[
max_{\mathbf{\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 \mathbf{x}_i^T \mathbf{x}_j \\
s.t. \ \sum_{i=1}^m \alpha_i y_i = 0, \\
\] 解出\(\mathbf{\alpha}\)后，求出\(\mathbf{w}\)和\(b\)即可得到模型： \[
f(\mathbf{x}) = \mathbf{w}^T \mathbf{x} + b = \sum_{i=1}^m \alpha_i y_i \mathbf{x}_i^T \mathbf{x} +b.
\] 另外，求解对偶问题得到的\(\alpha_i, \beta_i, i=1, 2, ..., m\)需要满足KKT（Karush-Kuhn-Tucker）条件， \[
0 \leq \alpha_i \leq C \\
\beta_i \geq 0 \\
\ y_i(\mathbf{w}^T \mathbf{x}_i + b) + \xi_i - 1 \geq 0 \\
\xi_i \geq 0 \\
\alpha_i \left (y_i (\mathbf{w}^T \mathbf{x}_i + b) + \xi_i -1 \right) = 0 \\
\beta_i \xi_i = 0
\]
SMO 算法
不管是硬边界还是软边界，对偶问题都是一个二次规划问题，可以使用通用的二次规划算法来求解。但是这个问题的规模正比于训练样本数，这在实际任务中造成很大的开销，为了避免这个问题，一种高效的做法是使用SMO(Sequential Minimal OPtimization)算法。 SMO算法的基本思想是固定\(a_i\)以外的所有参数，然后求\(\alpha_i\)上的极值。但是由于存在约束\(\sum_{i=1}^m \alpha_i y_i = 0\)，如果固定除\(\alpha_i\)之外的其他参数，则\(\alpha_i\)可以直接求出，因此，SMO每次选择两个变量\(\alpha_i，\alpha_j\)，并固定其他参数。这样，在参数初始化之后，SMO不断执行如下2个步骤直至收敛： - 选取一对待更新的变量\(\alpha_i, \alpha_j\) - 固定\(\alpha_i, \alpha_j\)以外的参数，更新\(\alpha_i, \alpha_j\) \[ \alpha_j^{new} = \alpha_j^{old} + \frac{y_j (E_j^{old} - E_i^{old})}{\eta} \\ \alpha_i^{new} = \alpha_i^{old} - \frac{s y_j (E_j^{old} - E_i^{old})}{\eta} \] 其中 \[ \eta = 2K_{ij} - K_{ii} - K_{jj} \\ s = y_i y_j \\ K_{ii} = \mathbf{x}_i^T \mathbf{x}_i \\ K_{ij} = \mathbf{x}_i^T \mathbf{x}_j \\ K_{jj} = \mathbf{x}_j^T \mathbf{x}_j \\ \] 在更新\(\alpha_j\)之后、\(\alpha_i\)之前,需要限制\(\alpha_j\)的范围： - 当\(s=1\)时，下边界为\(max(0, \alpha_i+\alpha_j-C)\)，上边界为\(min(C, \alpha_i+\alpha_j)\) - 当\(s=-1\)时，下边界为\(max(0, \alpha_j-\alpha_i)\)，上边界为\(min(C, C+\alpha_j-\alpha_i)\)
1 | from numpy import * |
1 | def smoSimple(dataMatIn, classLabels, C, toler, maxIter): |
1 | dataArr, labelArr = loadDataSet('testSet2.txt') |
1 | print(b,alphas[alphas>0]) #输出b和大于0的alpha |
[[-3.76119735]] [[ 0.13268982 0.03391035 0.18867574 0.00656234 0.36183825]]1 | # 输出支持向量 |
[4.658191, 3.507396] -1.0
[3.223038, -0.552392] -1.0
[3.457096, -0.082216] -1.0
[2.893743, -1.643468] -1.0
[6.080573, 0.418886] 1.01 | class optStruct: |
1 | def innerL(i, oS): |
与原来的函数区别有： 1. 使用了oS类 2. 使用了selectJ而不是selectJrand来选择第2个alpha值 3. alpha值改变之后，更新了Ecache
1 | def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)): |
1 | dataArr, labelArr = loadDataSet('testSet2.txt') |
1 | def calWs(alphas, dataArr, classLabels): |
1 | ws = calWs(alphas, dataArr, labelArr) |
array([[ 0.53103017],
[-0.19632991]])1 | # 预测分类，> 0为1类，< 0为-1类 |
matrix([[ 1.50030532]])1 | # 真实类为： |
1.0核函数
前面的讨论假定训练样本线性可分，即存在一个超平面可以将训练样本正确分类。然而实际应用中，往往不存在这样一个超平面。例如“异或”问题就不是线性可分的。对这样的问题，一种解决方案是将原始空间映射到一个更高维度的特征空间。另\(\phi(\mathbf{x})\)表示将\(\mathbf{x}\)映射后的特征向量，则在特征空间中划分超平面所对应的模型可以表示为： \[ f(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b \] 同样的可以推导得到对偶问题： \[ max_{\mathbf{\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 \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) \\ s.t. \ \sum_{i=1}^m \alpha_i y_i = 0, \\ \alpha_i \geq 0 \] 由于特征空间的维度可能很高，甚至是无限维，因此直接计算\(\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)\)通常是困难的。为了避免这个问题，可以假定这样一个函数： \[ \kappa(\mathbf{x})=\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) \] 则， \[ max_{\mathbf{\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 \kappa(\mathbf{x}) \\ s.t. \ \sum_{i=1}^m \alpha_i y_i = 0, \\ \alpha_i \geq 0 \] 同样可以利用SMO算法求解\(\alpha_i\)，然后带入： \[ f(\mathbf{x}) = \mathbf{w}^T \phi(\mathbf{x}) + b \\ = \sum_{i=1}^m \alpha_i y_i \phi(\mathbf{x}_i)^T \phi(\mathbf{x}) + b \\ = \sum_{i=1}^m \alpha_i y_i \kappa(\mathbf{x},\mathbf{x}_i) + b. \] 常用的核函数有多种，本文使用的是径向基（高斯）核函数： \[ \kappa(\mathbf{x}, \mathbf{x}_i) = exp \left( \frac{-\|\mathbf{x} - \mathbf{x}_i \|^2}{2\sigma^2} \right) \]
1 | def kernelTrans(X, A, kTup): |
1 | class optStruct: |
1 | def innerL(i, oS): |
1 | def testRbf(k1=1.3): |
1 | def smoP(dataMatIn, classLabels, C, toler, maxIter, kTup=('lin', 0)): |
1 | testRbf() |
there are 17 support vectors
the training error rate is: 0.000000
the test error rate is: 0.050000实例：手写识别
1 | def img2vector(filename): |
1 | def loadImages(dirName): |
1 | testDigits(('lin', 100)) |
there are 23 support vectors
the training error rate is: 0.044776
the test error rate is: 0.043011| kenel, \(\sigma\) | train error(%) | test error(%) | # support vectors |
|---|---|---|---|
| RBF, 1 | 0 | 52.2 | 402 |
| RBF, 10 | 0 | 0.5 | 86 |
| RBF, 50 | 0 | 1.07 | 30 |
| RBF, 100 | 3.2 | 4.3 | 31 |
| Linear | 4.5 | 4.3 | 31 |
结论及讨论
结论
- 优点：泛化错误率低，计算开销不大，结果容易解释
- 缺点：对参数调节和核函数的选择敏感
讨论
- 本文讨论的是SMO算法的简化版本，还有一些优化技术并没有讨论，有兴趣者可以参考资料[3]
- 本文只讨论了二分类问题，实际上，利用"one-vs-all"策略也可以推广到多分类问题；
- 采用相同的思想，也可以解决回归问题，该方法称为支持向量回归（SVR），解决思路容许预测值和真实值之间最多有\(\epsilon\)的偏差，只有当误差大于\(\epsilon\)时才计算损失。\(\epsilon\)-不敏感损失函数定义为： \[ L_{\epsilon}(z) = 0, if |z| \leq \epsilon; \\ L_{\epsilon}(z) = |z| - \epsilon, otherwise. \]
- SVM也可以推广到非监督学习领域。
参考资料
- Peter Harrington, Machine learning in action, Manning Publications, 2012
- 周志华，机器学习，清华大学出版社， 2016
- Keerthi et al, Improvements to Platt's SMO Algorithm for SVM Classifier Design. Neural computation, 2001
- OF Svm, Sequential Minimal Optimization for SVM.
