前言
在机器学习中，支持向量机（英语：support vector machine，常简称为SVM，又名支持向量网络）是在分类与回归分析中分析数据的监督式学习模型与相关的学习算法。给定一组训练实例，每个训练实例被标记为属于两个类别中的一个或另一个，SVM训练算法建立一个将新的实例分配给两个类别之一的模型，使其成为非概率二元（英语：binary classifier）线性分类器。SVM模型是将实例表示为空间中的点，这样映射就使得单独类别的实例被尽可能宽的明显的间隔分开。然后，将新的实例映射到同一空间，并基于它们落在间隔的哪一侧来预测所属类别。
除了进行线性分类之外，SVM还可以使用所谓的核技巧（英语：kernel trick）有效地进行非线性分类，将其输入隐式映射到高维特征空间中。
间隔与支持向量
给定训练样本集 \(D=\{(\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2), ..., (\boldsymbol{x}_m,y_m)\},y_i \in \{-1,+1\}\)，分类学习最基本的思想就是基于训练集 \(D\) 在样本空间找到一个划分超平面，将不同的类别分开。但是这样的超平面有很多，哪个才是我们要找的呢？
直观上看，我们应该去找位于两类样本之间的超平面。因为这类的超平面对驯良样本的局部扰动的“容忍性”最好。换言之泛化能力最强。
在样本空间中，划分超平面可通过如下线性方程来描述:
\[ \boldsymbol{w}^T\boldsymbol{x}+b=0 \tag{1} \]
其中 \(\boldsymbol{w}=(w_1;w_2;...;w_d)\) 为法向量，决定了超平面的方向；\(b\) 为位移项，决定了超平面与原点之间的距离。显然超平面可由 \(\boldsymbol{w}\) 和 \(b\) 确定。样本空间中任意点 \(\boldsymbol{x}\) 到超平面 \((\boldsymbol{w},b)\) 的距离可写为
\[ r=\frac{|\boldsymbol{w}^T\boldsymbol{x}+b|}{||\boldsymbol{w}||} \tag{2} \]
假设超平面 \((\boldsymbol{w},b)\) 能将训练样本正确分类，即对于 \((\boldsymbol{x}_i,y_i) \in D\)，若 \(y_i=+1\)，则有 \(\boldsymbol{w}^T\boldsymbol{x}_i+b>0\)；若 \(y_i=-1\)，则有 \(\boldsymbol{w}^T\boldsymbol{x}_i+b<0\)。令
\[ \begin{cases} \boldsymbol{w}^T\boldsymbol{x}_i+b \ge 0, & y_i=+1 \\ \boldsymbol{w}^T\boldsymbol{x}_i+b \le 0, & y_i=-1 \end{cases} \tag{3} \]
距离超平面最近的这几个训练样本点使得上式等号成立，他们被称为“支持向量”，两个异类支持向量到超平面的距离之和为
\[ \gamma=\frac{2}{||\boldsymbol{w}||} \tag{4} \]
它被称为间隔。
欲找到具有“最大间隔”的划分超平面，也就是要找到满足式 \((3)\) 中约束的参数 \(\boldsymbol{w}\) 和 \(b\)，使得 \(\gamma\) 最大，即
\[ \begin{aligned} & \max_{\boldsymbol{w},b}\frac{2}{||\boldsymbol{w}||}\\ &s.t.\quad y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b) \ge 1, \qquad i=1,2,...,m. \end{aligned} \tag{5} \]
显然，为了最大化间隔，仅需最大化 \(||\boldsymbol{w}||^{-1}\)，这等价于最小化 \(||\boldsymbol{w}||^2\)。于是，式 \((5)\) 可重写为
\[ \begin{aligned} & \max_{\boldsymbol{w},b} \frac{1}{2}||\boldsymbol{w}||^2\\ &s.t.\quad y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b) \ge 1, \qquad i=1,2,...,m. \end{aligned} \tag{6} \]
这就是支持向量机（SVM）的基本型。
对偶问题
我们希望求解式 \((6)\) 来得到大间隔划分超平面所对应的模型
\[ f(\boldsymbol{x})=\boldsymbol{w}^T\boldsymbol{x}+b \tag{7} \]
其中 \(\boldsymbol{w}\) 和 \(b\) 是模型参数。注意到式 \((6)\) 本身是一个凸二次规划问题，能直接使用线程的优化计算包求解，但是也有更高效的办法。
对式\(6\) 使用拉格朗日乘子法可得到其“对偶问题”。具体来说，对式 \((6)\) 的每条约束添加拉格朗日乘子法 \(\alpha \ge 0\)，则该问题的拉格朗日函数可写为
\[ L(\boldsymbol{w},b,\boldsymbol{\alpha})= \frac{1}{2}||\boldsymbol{w}||^2+ \sum_{i=1}^m\alpha_i(1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)) \tag{8} \]
其中 \(\boldsymbol{\alpha}=(\alpha_i;\alpha_2;...;\alpha_m)\)。令 \(L(\boldsymbol{w},b,\boldsymbol{\alpha})\) 对 \(\boldsymbol{w}\) 和 \(b\) 的偏导数为零可得
\[ \boldsymbol{w}=\sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i \tag{9} \]
\[ 0=\sum_{i=1}^m \alpha_iy_i \tag{10} \]
将式 \((9)\) 代入 \((8)\)。即可将 \(L(\boldsymbol{w},b,\boldsymbol \alpha)\) 中的 \(\boldsymbol{w}\) 和 \(\boldsymbol{\alpha}\)消去，在考虑式 \((10)\) 的约束，就得到式 \((6)\) 的对偶问题
\[ \max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i- \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j \tag{11} \]
\[ \begin{aligned} s.t.\quad & \sum_{i=1}^m\alpha_iy_i=0 \\ & \alpha_i \ge 0, \qquad i=1,2,...,m. \end{aligned} \]
解出 \(\boldsymbol{\alpha}\) 后，求出 \(\boldsymbol{w}\) 和 \(b\) 即可得到模型
\[ \begin{aligned} f(\boldsymbol{x})&=\boldsymbol{w}^T\boldsymbol{x}+b \\ &=\sum_{i=1}^m\alpha_iy_i\boldsymbol{x}_i^T\boldsymbol{x}_i+b \end{aligned} \tag{12} \]
从对偶问题 \((11)\) 解出的 \(\alpha_i\) 是式 \((8)\) 中的拉格朗日乘子，它恰对应着训练样本 \((\boldsymbol{x}_i,y_i)\)。注意到式 \((6)\) 中有不等式约束，因此上述过程须满足 KKT （Karush-Kuhn-Tucher）条件，即要求
\[ \begin{cases} \alpha_i \ge 0; \\ y_i f(\boldsymbol{x}_i)-1 \ge 0; \\ \alpha_i(y_if(\boldsymbol{x}_i)-1)=0; \end{cases} \tag{13} \]
于是对任意训练样本 \((\boldsymbol{x}_i,y_i)\)，总有 \(\alpha_i=0\) 或者 \(y_if(\boldsymbol{x}_i)=1\)。若 \(\alpha_i=0\)，则该样本将不会出现在式 \((12)\) 的求和中，也就不会对 \(f(\boldsymbol{x})\) 有任何影响；若 \(\alpha_i > 0\)，则必有 \(y_if(\boldsymbol{x}_i)=1\)，所对应的样本点位于最大间隔边界上，是一个支持向量。这显示出支持向量机的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终的模型仅与支持向量有关。
求解式 \((11)\) 可以通过 SMO算法。
SMO 算法
SMO 的基本思路是先固定 \(\alpha_i\) 之外的所有参数，然后求 \(\alpha_i\) 上的极值。由于存在约束 \(\sum_{i=1}^m \alpha_i y_i=0\)，若固定 \(\alpha_i\) 之外的其他变量，则 \(\alpha_i\) 可由其他变量导出，于是，SMO 每次选择两个变量 \(\alpha_i\) 和 \(\alpha_j\)，并固定其他参数。这样，在参数初始化后，SMO 不断执行如下两个步骤直至收敛:
- 选取一对需要更新的变量 \(\alpha_i\) 和 \(\alpha_j\)
- 固定 \(\alpha_i\) 和 \(\alpha_j\) 以外的参数。求解式 \((11)\) 获得更新后的 \(\alpha_i\) 和 \(\alpha_j\)
SMO 优先选取违背 KKT 条件程度最大的变量。第二个变量应该选一个使得目标函数增长最快的变量。因为这个过程比较复杂，所以SMO选取了一个启发式：使选取的两变量所对应样本之间的间隔最大。
SMO 算法之所以高效，是由于在固定其他参数之后，仅优化两个参数的过程能做到非常高效。具体来说，仅考虑 \(\alpha_i\) 和 \(\alpha_j\) 时，式 \((11)\) 中的约束可重写为
\[ \alpha_i y_i + \alpha_j y_j=c \qquad \alpha_j \ge 0 \tag{14} \]
其中
\[ c=-\sum_{k \neq i,j} \alpha_k y_k \tag{15} \]
是使得 \(\sum_{i=1}^m \alpha_i y_i=0\) 成立的常数。用
\[ \alpha_i y_i + \alpha_j y_j=c \tag{16} \]
消去式 \((11)\) 中的变量 \(\alpha_j\)，则得到一个关于 \(\alpha_i\) 的单变量二次规划问题，仅有的约束是 \(\alpha_i \ge 0\)。不难发现，这样的二次规划问题具有闭式解，于是不必调用数值优化算法即可高效地计算出更新后的 \(\alpha_i\) 和 \(\alpha_j\)。
注意到对任意的支持向量 \((\boldsymbol{x}_s, y_s)\) 都有 \(y_s f(\boldsymbol{x_s})=1\)，即
\[ y_s (\sum_{i \in S} \alpha_iy_i \boldsymbol{x}_i^T \boldsymbol{x}_s + b)=1 \tag{17} \]
其中 \(S=\{i|\alpha_i > 0,i=1,2,...,m\}\) 为所有支持向量的下标集。理论上，可选任意支持向量并通过求解式 \((17)\) 获得 \(b\)，但现实中往往采取一种更鲁棒的做法：使用所有支持向量求解的平均值
\[ b=\frac{1}{|S|}\sum_{s \in S} (\frac{1}{y_s}-\sum_{i \in S} \alpha_iy_i \boldsymbol{x}_i^T \boldsymbol{x}_s) \tag{18} \]
核函数
以上讨论的 SVM 仅适用于训练样本线性可分，在不可分时算法不会收敛。对于这样的问题， 我们可以让空间从原本的线性空间变成一个更高维的空间，在这个高维的线性空间下，再用一个超平面进行划分。如果原始空间是有限维的，那么一定存在一个高位特征空间使样本可分。
令 \(\phi (\boldsymbol{x})\) 表示将 \(\boldsymbol{x}\) 映射后的特征向量，于是，在特征空间中划分超平面所对应的模型可表示为
\[ f(\boldsymbol{x})=\boldsymbol{w}^T \phi(\boldsymbol{x})+b \tag{19} \]
类似式 \((6)\) 有
\[ \begin{aligned} & \max_{\boldsymbol{w},b} \frac{1}{2}||\boldsymbol{w}||^2\\ &s.t.\quad y_i(\boldsymbol{w}^T \phi(\boldsymbol{x}_i)+b) \ge 1, \qquad i=1,2,...,m. \end{aligned} \tag{20} \]
其中的对偶问题是
\[ \max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i- \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j \phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}_j) \tag{21} \]
\[ \begin{aligned} s.t.\quad & \sum_{i=1}^m\alpha_iy_i=0 \\ & \alpha_i \ge 0, \qquad i=1,2,...,m. \end{aligned} \]
求解式 \((21)\) 涉及到计算 \(\phi(\boldsymbol{x}_i)^T\phi(\boldsymbol{x}_j)\)，这是样本 \(\boldsymbol{x}_i\) 与 \(\boldsymbol{x}_j\) 映射到特征空间之后的内积。由于特征空间维数可能很高，甚至是无穷维，因此直接计算十分困难。所以我们可以采用这样一个函数：
\[ \kappa(\boldsymbol{x}_i, \boldsymbol{x}_j)= \langle \phi (\boldsymbol{x}_i), \phi (\boldsymbol{x}_j) \rangle =\phi (\boldsymbol{x}_i)^T \phi (\boldsymbol{x}_j) \tag{22} \]
即 \(\boldsymbol{x}_i\) 与 \(\boldsymbol{x}_j\) 在特征空间中的内积等于它们在原始样本空间中通过函数 \(\kappa \langle \cdot,\cdot \rangle\) 计算的结果。有了这样的函数，我们就不比直接去计算高维甚至无穷维特征空间中的内积，于是式 \((21)\) 可重写为
\[ \max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i- \frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m \alpha_i\alpha_jy_iy_j \kappa \langle \boldsymbol{x}_i, \boldsymbol{x}_j \rangle \tag{23} \]
\[ \begin{aligned} s.t.\quad & \sum_{i=1}^m\alpha_iy_i=0 \\ & \alpha_i \ge 0, \qquad i=1,2,...,m. \end{aligned} \]
求解后得到
\[ \begin{aligned} f(\boldsymbol{x}) &=\boldsymbol{w}^T\phi(\boldsymbol{x})+b \\ &=\sum_{i=1}^m\alpha_i y_i \phi (\boldsymbol{x}_i)^T \phi (\boldsymbol{x}) +b \\ &=\sum_{i=1}^m\alpha_i y_i \kappa \langle \boldsymbol{x}, \boldsymbol{x}_i \rangle +b \end{aligned} \]
这里的 \(\kappa \langle \cdot,\cdot \rangle\) 就是核函数。式 \((24)\) 显示出模型最优解可通过训练样本的核函数展开，这一展开式亦称“支持向量展式”。
常用核函数
1、线性核函数：这是最简单的核函数，它直接计算两个输入特征向量的内积。
- 优点：简单高效，结果易解释，总能生成一个最简洁的线性分割超平面
- 缺点：只适用线性可分的数据集
\[\kappa \langle \boldsymbol{x}_i,\boldsymbol{x}_j \rangle=\boldsymbol{x}_i^T \boldsymbol{x}_j\]
2、多项式核函数：通过多项式来作为特征映射函数
- 优点：可以拟合出复杂的分割超平面。
- 缺点：多项式的阶数不宜太高否则会给模型求解带来困难。
\[\kappa \langle \boldsymbol{x}_i,\boldsymbol{x}_j \rangle=(\boldsymbol{x}_i^T \boldsymbol{x}_j)^d\]
3、高斯核函数：
- 优点：可以把特征映射到无限多维，并且没有多项式计算那么困难，参数也比较好选择。
- 缺点：不容易解释，计算速度比较慢，容易过拟合。
\[\kappa \langle \boldsymbol{x}_i,\boldsymbol{x}_j \rangle =\exp (- \frac{||\boldsymbol{x}_i - \boldsymbol{x}_j||^2}{2\sigma^2})\]
核函数的线性组合、直积还是核函数
若 \(\kappa_1\) 为核函数，则对于任意函数 \(g(\boldsymbol{x})\)
\[ \kappa \langle \boldsymbol{x}, \boldsymbol{z} \rangle = g(\boldsymbol{x}) \kappa_1 \langle \boldsymbol{x}, \boldsymbol{z} \rangle g(\boldsymbol{z}) \]
也是核函数
软间隔
线性不可分意味着有样本点不满足约束条件，为了解决这个问题，对每个样本引入一个松弛变量 \(\xi_i \ge 0\)，这样约束条件变为：
\[ y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) \ge 1- \xi_i \]
目标函数则变为
\[ \min_{w,b,\xi} \quad \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{N} \xi_i \]
其中，C为惩罚函数，目标函数有两层含义：
- margin尽量大
- 误分类的样本点计量少
C 为调节二者的参数。通过构造拉格朗日函数并求解偏导（具体推导略去），可得到等价的对偶问题：
\[ \min_{\alpha} \quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N} {\alpha_i} \]
\[ \begin{aligned} s.t. \quad & \sum_{i=1}^{N}\alpha_i y_i = 0 \cr & 0 \le \alpha_i \le C, \quad i=1,2,\cdots,N \end{aligned} \]
与线性可分的对偶问题相比，只是约束条件αi发生变化，问题求解思路与之类似。
总结
SVM的空间复杂度：SVM 所占内存，是样本数据量的平方。
《A Tutorial on Support Vector Machines for Pattern Recognition》 1998KluwerAcademicPublishers,Boston，训练计算复杂度在O(Nsv3+LNsv2+dLNsv)和O(d*L^2)之间，其中Nsv是支持向量的个数，L是训练集样本的个数，d是每个样本的维数(原始的维数，没有经过向高维空间映射之前的维数).
总的来讲，SVM的SMO算法根据不同的应用场景，其算法复杂度为~N 到~N^2.2之间，而chunking scale的复杂度为~N^1.2 到~N^3.4之间。一般SMO比chunking算法有一阶的优势。
线性SVM比非线性SVM的smo算法要慢一些。所以，据原著论文的测试，SMO算法，在线性svm上快1000倍，在非线性上快15倍。
对于SVM的SMO算法的内存需求时线性的，这使得其能适用比较大的训练集。
所以，如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用了简单的naive bayes分类器，或者是使用逻辑回归模型分类。
其他观点：
SVM在小样本训练集上能够得到比其它算法好很多的结果。支持向量机之所以成为目前最常用，效果最好的分类器之一，在于其优秀的泛化能力，这是是因为其本身的优化目标是结构化风险最小，而不是经验风险最小，因此，通过margin的概念，得到对数据分布的结构化描述，因此减低了对数据规模和数据分布的要求。
VM也并不是在任何场景都比其他算法好，对于每种应用，最好尝试多种算法，然后评估结果。如SVM在邮件分类上，还不如逻辑回归、KNN、bayes的效果好。