本文主要是PRML一书7.1至7.1.2节的笔记。
支持向量机是一种十分流行的机器学习算法，可以解决分类、回归及异常检测等问题。支持向量机的一个重要性质就是确定模型参数等价于一个凸优化问题，因此任意一个局部最优解就是全局最优解。
1. 最大间隔分类器
先来看最简单的二分类问题，给定训练集 $\mathcal{D}=\{(\mathbf{x}_1,t_1),\cdots,(\mathbf{x}_N,t_N)\}$，其中 $t_n\in\{-1,1\}$。我们想在样本空间中找到一个划分超平面，来将正负样本分开，模型即为 $$y(\mathbf{x})=\mathbf{w}^{\mathrm{T}}\mathbf{x}+b\tag{1}$$根据 $y(\mathbf{x})$ 的正负号来分类。这里，我们假设训练集是线性可分的，后面我们会讨论线性不可分的情形。
这样的划分超平面可能不止一个，如下图所示
图中的红线都可以作为划分超平面，直观上看，应该找位于两类样本“正中间”的划分超平面，因为它对训练样本局部的扰动“容忍”性最好。即如果某个样本的位置发生小的变化，细红线就很可能出现划分错误，而粗红线依然可以保证分类正确。
如何确定这个“正中间”的位置呢？支持向量机方法引入了一个概念———间隔（margin）。间隔指的是任一个样本到决策边界的最短距离，如下图所示
故间隔最大的决策边界就是“最中间”的位置
任意一个样本到超平面的距离可以写为$$\cfrac{|y(\mathbf{x})|}{||\mathbf{w}||}$$我们只关心正确分类的样本，即 $t_n y(\mathbf{x_n})>0$，所以这个距离可以写成$$\cfrac{t_n y(\mathbf{x})}{||\mathbf{w}||}=\cfrac{t_n (\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)}{||\mathbf{w}||}\tag{2}$$优化目标如下$$\text{arg}\max_{\mathbf{w},b}\left\{\cfrac{1}{||\mathbf{w}||}\min_{n}[t_n(\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)]\right\}\tag{3}$$即先用$\mathbf{w}$ 和 $b$ 表示出间隔大小，然后最大化它。注意到在(2)式中，如果将 $\mathbf{w}$ 和 $b$ 缩放同样的倍数，距离是不变的。所以，可以令离超平面最近的样本满足 $t_n (\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)=1$，则所有样本满足$$t_n (\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)\ge 1,\quad\qquad n=1,…,N\tag{4}$$又因为最大化 $||\mathbf{w}||^{-1}$ 与最小化 $||\mathbf{w}||^2$ 是等价的，故优化目标可以化为$$\begin{array}{c,l}&\text{arg}\displaystyle\min_{\mathbf{w},b}\cfrac{1}{2}||\mathbf{w}^2||\\ &\text{s.t.}\quad t_n (\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)\ge 1,\quad\qquad n=1,…,N\end{array}\tag{5}$$离超平面最近的样本称为支持向量（support vector）。
2. 对偶问题
(5)式是一个二次规划问题，我们利用拉格朗日乘子法(可参见这里)求解。对每个约束引入一个对应的乘子 $a_n\ge 0$，拉格朗日函数为$$L(\mathbf{w},b,\mathbf{a})=\cfrac{1}{2}||\mathbf{w}||^2-\sum_{n=1}^N a_n\{t_n (\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)-1\}\tag{6}$$其中，$\mathbf{a}=(a_1,\cdots,a_N)^{\mathrm{T}}$。分别令 $L(\mathbf{w},b,\mathbf{a})$ 对 $\mathbf{w}$ 和 $b$ 的偏导数为0，可以得到$$\mathbf{w}=\sum_{n=1}^N a_n t_n\mathbf{x}_n\tag{7}$$ $$0=\sum_{n=1}^N a_n t_n\tag{8}$$将(7)式代入(6)式，并考虑(8)式的约束，可以得到原问题的对偶问题$$\begin{array}{r,c,l}&\displaystyle\max_{\mathbf{a}}&\displaystyle\widetilde{L}(\mathbf{a})=\sum_{n=1}^N a_n-\cfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_n a_mt_nt_m\mathbf{x}_n^{\mathrm{T}}\mathbf{x}_m \\ &\text{s.t. }&\displaystyle\sum_{n=1}^N a_n t_n=0 \\ & &a_n\ge 0,\quad\quad n=1,…N\end{array}\tag{9}$$解出 $\mathbf{a}$ 之后，就可以得到模型$$\begin{array}{r,c,l}y(\mathbf{x})&=&\mathbf{w}^{\mathrm{T}}\mathbf{x}+b \\ &=&\displaystyle\sum_{n=1}^N a_nt_n\mathbf{x}_n^{\mathrm{T}}\mathbf{x}+b\end{array}\tag{10}$$在约束优化问题求解过程中，需要满足KKT条件，即要求$$\begin{cases}a_n\ge 0 \\ t_ny(\mathbf{x}_n)-1\ge 0 \\ a_n(t_ny(\mathbf{x}_n)-1)=0\end{cases}\tag{11}$$于是，对任意训练样本 $(\mathbf{x}_n,t_n)$
- 若 $a_n=0$，则该样本不会在(10)式的求和中出现，故对 $y(\mathbf{x})$ 没有任何影响；
- 若 $a_n>0$，则必有 $t_ny(\mathbf{x}_n)=1$，对应的样本点位于最大间隔的边界上。
这体现了支持向量机一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
3. 核函数
现实中，我们遇到的数据也许并不是线性可分的，比如下图这个例子
对这样的问题，可将样本从原空间映射到一个更高维度的空间，在这个空间里训练集就变成线性可分的了，如下图所示
令 $\phi(\mathbf{x})$ 表示将 $\mathbf{x}$ 映射后的特征向量。于是，在特征空间中划分超平面所对应的模型为$$y(\mathbf{x})=\mathbf{w}^{\mathrm{T}}\phi(\mathbf{x})+b\tag{12}$$类似地，我们可以求出相应的对偶问题$$\begin{array}{r,c,l}&\displaystyle\max_{\mathbf{a}}&\displaystyle\widetilde{L}(\mathbf{a})=\sum_{n=1}^N a_n-\cfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_n a_mt_nt_m\phi(\mathbf{x}_n)^{\mathrm{T}}\phi(\mathbf{x}_m) \\ &\text{s.t. }&\displaystyle\sum_{n=1}^N a_n t_n=0 \\ & &a_n\ge 0,\quad\quad n=1,…N\end{array}\tag{13}$$求解上式涉及到计算 $\phi(\mathbf{x}_n)^{\mathrm{T}}\phi(\mathbf{x}_m)$，这是样本 $\mathbf{x}_n$ 和 $\mathbf{x}_m$ 映射到特征空间之后的内积。由于特征空间维数可能很高，甚至可能是无穷维，因此直接计算 $\phi(\mathbf{x}_n)^{\mathrm{T}}\phi(\mathbf{x}_m)$ 通常是困难的。为了避开这个障碍，可以设想这样一个函数$$k(\mathbf{x}_n,\mathbf{x}_m)=\langle\phi(\mathbf{x}_n),\phi(\mathbf{x}_m)\rangle=\phi(\mathbf{x}_n)^{\mathrm{T}}\phi(\mathbf{x}_m)\tag{14}$$即 $\mathbf{x}_n$ 与 $\mathbf{x}_m$ 在特征空间的内积等于它们在原始空间通过函数 $k(\cdot,\cdot)$ 计算的结果。有了这样的函数，就不必直接去计算高维甚至无穷维特征空间中的内积。类似地，则有$$y(\mathbf{x})=\sum_{n=1}^N a_n t_n k(\mathbf{x}_n,\mathbf{x})+b\tag{15}$$这样的方法称为核技巧（kernel trick）（具体参见这里）。实际中，我们不需要知道 $\phi$ 是什么形式（通常也不可能知道），只需要选择合适的核函数，就可以进行计算。
4. 软间隔
在前面的讨论中，我们都假定训练集在样本空间或特征空间中是线性可分的。然而，实际中往往很难确定合适的核函数使训练集在样本空间中线性可分；退一步说，即便恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这是不是过拟合造成的。
缓解这个问题的一个办法是允许支持向量机在一些样本上犯错，为此，要引入软间隔（soft margin）的概念。
前面介绍的支持向量机形式要求所有样本满足(4)式的约束，即所有样本必须被分类正确，这称为“硬间隔”，而软间隔则允许某些样本不满足(4)式的约束。在最大化间隔的同时，不满足约束的样本应尽可能少。于是，优化目标可以写为$$\min_{\mathbf{w},b}\cfrac{1}{2}||\mathbf{w}||^2+C\sum_{n=1}^N l_{0/1}\{t_n (\mathbf{w}^{\mathrm{T}}\mathbf{x}+b)-1\}\tag{16}$$其中 $C>0$ 是一个常数，$l_{0/1}$ 是“0/1损失函数”$$l_{0/1}(z)=\begin{cases}1,\quad\text{if $z<0$} \\ 0,\quad\text{otherwise}\end{cases}$$显然，当 $C$ 无穷大时，(16)式迫使所有样本满足(4)式的约束，即等价于之前的模型；当 $C$ 取有限值时，(16)式允许部分样本不满足约束。
然而0/1损失函数非凸、非连续，数学性质不太好，因此人们常使用一些替代损失函数。下面是三种常用的替代损失函数：
- hinge 损失：$l_{hinge}(z)=\max(0,1-z)$
- 指数损失：$l_{exp}(z)=\exp(-z)$
- 对率损失：$l_{log}(z)=\log(1+\exp(-z))$
若采用hinge损失，引入松弛变量，则(16)式可以写成$$\begin{array}{r,c,l}&\displaystyle\min_{\mathbf{w},b,\xi_n}&\displaystyle\cfrac{1}{2}||\mathbf{w}||^2+C\sum_{n=1}^N\xi_n \\ &\text{s.t. }& t_n y(\mathbf{x}_n)\ge 1-\xi_n\\ &&\xi_n\ge 0,\quad n=1,…,N\end{array}\tag{17}$$在上式中，每个样本对应的剩余变量表征该样本不满足约束的程度。
类似地，应用拉格朗日乘子法，引入乘子 $\mu_n$，对拉格朗日函数求偏导可以得到 $C=a_n+\mu_n$，最终得到对应的对偶问题为$$\begin{array}{r,c,l}&\displaystyle\max_{\mathbf{a}}&\displaystyle\widetilde{L}(\mathbf{a})=\sum_{n=1}^N a_n-\cfrac{1}{2}\sum_{n=1}^N\sum_{m=1}^Na_n a_mt_nt_m\mathbf{x}_n^{\mathrm{T}}\mathbf{x}_m \\ &\text{s.t. }&\displaystyle\sum_{n=1}^N a_n t_n=0 \\ & &0\le a_n\le C,\quad\quad n=1,…N\end{array}\tag{18}$$对应的KKT条件为$$\begin{cases}\displaystyle a_n\ge 0,\quad \mu_n\ge 0 \\ \displaystyle t_ny(\mathbf{x}_n)-1+\xi_n\ge 0 \\ \displaystyle a_n(t_ny(\mathbf{x}_n)-1+\xi_n)=0\\ \displaystyle\xi_n\ge 0,\quad\mu_n\xi_n=0\end{cases}\tag{19}$$则对于任意样本，若
- $a_n=0$，则该样本不会对 $y(\mathbf{x})$ 有任何影响
- $a_n\gt 0$，则有 $t_n y(\mathbf{x}_n)=1-\xi_n$，说明该样本是支持向量
- $a_n \lt C$，则 $\mu_n\gt 0$，故 $\xi_n=0$，说明该样本恰好在最大间隔边界上
- $a_n=C$，则 $\mu_n=0$：若 $\xi_n\le 1$，则样本落在最大间隔内部；若 $\xi_n > 1$，则样本被错误分类
可见，软间隔支持向量机最终模型仍仅与支持向量有关。另外，上面的内容都可以扩展成核函数的版本。
5. 求解
从上面可以看到，我们可以将支持向量机的训练转化成一个二次规划问题的求解。然而，直接求解需要的计算量太大，是不可行的。主要思想是将大的二次规划问题化成若干小的二次规划问题，许多人提出了不同的方法。其中，最著名的方法就是序列最小优化（sequential minimal optimization）。它利用分块的思想，将每一块分成极限小，即每次只考虑两个拉格朗日乘子。这样，子问题就可以直接得到解析解，然后用启发式算法进行每次的乘子选择。实践中，SMO算法的复杂度介乎线性和平方之间，取决于具体的问题。关于SMO算法的详细介绍可以看这篇文章。
求解出 $\mathbf{a}$ 之后，就可以相应计算出 $\mathbf{w}$，接下来要计算 $b$。
注意到，对任意的支持向量 $(\mathbf{x}_n,t_n)$ 都有 $t_n y(\mathbf{x_n})=1$，即有$$t_n\left(\sum_{m\in\mathcal{S}}a_m t_m k(\mathbf{x_n},\mathbf{x}_m)+b\right)=1$$其中 $\mathcal{S}$ 为所有支持向量的下标集。理论上，可选取任意一个支持向量通过上式解出 $b$。但在实际中，一种数值上更加稳定的方法是：使用所有支持向量求解的平均值，即$$b=\cfrac{1}{|\mathcal{S}|}\sum_{n\in\mathcal{S}}\left(t_n-\sum_{m\in\mathcal{S}}a_m t_m k(\mathbf{x_n},\mathbf{x}_m)\right)\tag{20}$$
6. 与对率回归的关系
如果使用对率损失作为替代损失函数，就几乎可以得到对率回归模型。设想一个对率回归问题，目标变量为 $t\in\{-1,1\}$，正例的概率为 $p(t=1|y)=\sigma(y)$，其中 $y=\mathbf{w}^{\mathrm{T}}\mathbf{x}$，$$\sigma(y)=1/(1+\exp(-y))$$故有 $p(t=-1|y)=1-\sigma(y)=\sigma(-y)$，则有$$p(t|y)=\sigma(yt)\tag{21}$$若取负对数似然函数，并加上正则化项，总的误差函数如下$$\begin{array}{r,c,l}&&\displaystyle-\log\prod_{n=1}^N\sigma(y_nt_n)+\lambda||\mathbf{w}||^2\\ &=&\displaystyle\sum_{n=1}^N\log(\sigma(y_n t_n))+\lambda||\mathbf{w}||^2\end{array}\tag{22}$$
可以看出，(22)式的形式与采用对率损失的支持向量机十分相似，如下图所示。其中，$\lambda$ 类似于 $C$，控制着两项优化目标之间的权衡。
对率回归的优势主要在于其输出具有自然的概率意义，而支持向量机的输出不具有概率意义。采用hinge损失的支持向量机的优势是输出的解更具有稀疏性。
参考资料
- Pattern Recognition and Machine Learning (PRML)
- 《机器学习》by 周志华