一、支持向量机

1 间隔与支持向量

支持向量机（support vector machines, SVM）是一种二分类模型，给定一组样本集，其中，-1表示反例，+1表示正例。分类学习最基本的想法就是基于样本集在样本空间中找到一个划分超平面，将不同类别的样本分开。但是，可能存在许多种超平面，这些超平面都可以将样本集分开，我们应该找到这些划分方法中最佳的那一个。

从直观上看，应该找到两类训练样本正中间的那个超平面，因为该划分超平面对训练样本局部扰动的容忍性最好。所谓容忍性，也可以叫做鲁棒性，如果训练集的局限性或者由于噪声等因素，训练集外的某些样本可能会更接近划分超平面，这将使之前的许多划分超平面出现错误，而正中间的超平面受到的影响最小。

在样本空间中，划分超平面可通过如下线性方程来描述：其中为法向量，决定了超平面的方向，为位移项，决定了超平面与原点之间的距离。显然，划分超平面由和确定，将其记为，我们要找到的超平面是距离两类样本几何间隔最大的分离超平面（即正中间的那个超平面），因此需要样本到超平面距离的度量。

1.1 几何间隔

超平面与样本空间中的任意样本点到的几何间隔为：考虑简单二维平面的情况，此时划分超平面为一条直线：，设样本点为，此时的几何间隔就是点到直线的距离公式：

几何间隔（点到超平面距离）的公式证明如下。
设，其到超平面几何距离为，为其在超平面的投影，两点在线性空间构成向量，显然与平行，二者内积的绝对值：展开：由于点在超平面上，满足超平面方程，所以有，因此，代入上式得：由于法向量的模，所以有：原式得证。

1.2 支持向量

假设超平面能够将样本正确分类（即假设训练数据集是线性可分的），即对于：

若，则有，
若，则有

令：

如图

距离超平面最近的这几个训练样本点使上面不等式中的等号成立，它们被称为支持向量（support vector），两个不同类的支持向量的到超平面的距离之和为：它们被称为“几何间隔”。

2 SVM基本型

要找到具有“最大间隔“的超平面，也就是寻找和，使得最大。即：由于取值为或，这里是为了去掉绝对值，表示样本集中任意点距离分割超平面的几何间隔均大于等于。

显然，为了最大化问隔，仅需最大化，也就等价于最小化，因此可以改写上面的式子：这就是SVM的基本型，为了求导时约去，不影响结果。这实际上是一个最优化问题，具体来说就是含有不等式约束的凸二次规划问题。对于凸二次规划问题（convex quadratic programming），可以直接使用现成的求解器求解，但是我们可以有更高效¹的方法，不过在此之前，需要简单说明凸优化问题的一些基本定义。

3 拉格朗日对偶²

3.1 凸优化问题的一般形式

在优化问题中，有时候直接求解原始问题往往是很困难的，我们可以考虑将原始问题转化为它的对偶问题，通过求解它的对偶问题来得到原始问题的解。这就是凸优化问题中的对偶问题。

原始最优化问题的一般形式如下：其中，为优化变量，为目标函数，为不等式约束，为等式约束，并且和均为凸函数，为仿射函数。当时，原始问题转化为无约束的极值问题。

原始问题的定义域为：即目标函数、不等式约束和等式约束的定义域的交集，是凸集。

可行集为：即满足原始问题的定义域，且满足等式约束和不等式约束的集合。

3.2 拉格朗日函数

原始问题的拉格朗日函数定义为：其中，称为拉格朗日乘子。可以从两个观点来看拉格朗日函数：

拉格朗日函数如果看成是关于的函数，那它其实就是对原始问题中目标函数与约束条件进行线性加权，目标函数的权系数是1，约束条件的权系数是或；
拉格朗日函数如果看成是关于或的函数，那么其余部分可看成常数，就可以看作是关于或的仿射函数（即最高次幂为1的多项式函数）

3.3 拉格朗日对偶函数

拉格朗日对偶函数（对偶函数）通过对拉格朗日函数关于取下确界得到。它的一般形式如下：其中为取下确界，对偶函数具有如下两个特殊性质：

对偶函数一定是凹函数，其凹性与原目标函数和约束函数凹凸与否无关
对于（向量中的每个分量），如果原问题最优解对应的目标函数值为，则

性质1说明，求解原问题的对偶问题时，并不要求原始问题一定是凸问题。

性质2说明，当不等式约束的拉格朗日乘子均大于等于0时，拉格朗日对偶函数构成了原始问题目标函数值的下界。

3.4 对偶问题

进一步地，根据上述两条性质，既然对偶函数是原始问题最优解的下界，那么最优的下界实际上就是最大化对偶函数（因为性质1，对偶函数为凹函数，故拉格朗日对偶问题一定是凸优化问题）。设对偶函数的最优解为，对应的最优值为，根据性质2，恒有。根据不等式的取等条件，我们可以分为：

当时，称为弱对偶（weak duality）
当时，称为强对偶（strong duality）
称为对偶间隙（duality gap）

具体是强对偶还是弱对偶，取决于原始问题的约束条件。这说明在解存在的情况下，弱对偶总是成立；当满足强对偶时，可以通过求解对偶问题来得到原始问题的解。

3.5 Slater条件

slater条件用于判断强对偶性在何时成立。首先原始问题必须满足凸优化问题，且使得约束条件满足：表示原始凸问题可行域除了边界以外的所有点，只要存在一个这样的点使原始凸优化问题的等式约束依然成立，且不等式约束的全部取不等号成立，那么对偶函数就具有强对偶性。

slater是强对偶性成立的充分条件，即如果满足该条件，则强对偶一定成立，不满足该条件，强对偶也可能成立。因此，要验证原始问题的解与对偶问题的解一致，可以首先验证slater条件，只有该条件成立时，原始问题与对偶问题的解一致。

3.6 KKT条件

在满足强对偶，且拉格朗日函数对可微的条件下，设分别是原问题和对偶问题的最优解，则以下四组条件称为 KKT 条件：

稳定性条件（stationarity）

若是原问题的最优解（极值点），则在处的微分等于0。

互补松弛条件（complementary slackness）

当时，，当时，。

原问题的可行性（primal feasibility）

原问题的最优解必然满足原问题的约束条件。

对偶问题的可行性（dual feasibility）

对偶问题的最优解必然满足对偶问题的约束条件。

KKT条件与最优解的充分必要性

对于一般的原始问题，KKT 条件是为最优解的必要条件，即只要为最优解，则一定满足 KKT 条件。

对于原始问题为凸优化的问题，KKT 条件是为最优解的充要条件。

4 拉格朗日乘子法求解对偶问题³

我们对希望求解的式（1）使用拉格朗日乘子法可得到其对偶问题（dual problem），对式（1）中的每条约束添加拉格朗日乘子，将问题改写为：

其中，，无等式约束。下面要求其对偶函数，即对拉格朗日函数取下确界：下面需要对拉格朗日函数求导。这是因为：前面提到原问题为凸优化问题，拉格朗日函数为凸函数。因此求下确界可以改为求最小值，对求导并令导数等于0解出来的点一定是最小值点。

关于此处求导的原因，还可以理解为：由于SVM问题满足slater条件，因此满足强对偶性。因此其最优解一定满足KKT条件，而KKT条件的稳定性条件说明，最优解能使得拉格朗日函数关于的一阶导数等于0。

将拉格朗日函数展开：对求导并令其等于零得：对求导并令其等于零得：将（4）代入（3）中，得：根据（5），，因此得到对偶函数：下面求对偶函数的最大值，即：不要忘记约束条件，下面是完整的对偶问题：下面需要解出，即可代入（4）和（5），进而求得模型：从（6）中的对偶问题解出的是（2）中的拉格朗日乘子，它对应着训练样本。由于原始问题具有不等式约束，其需要满足前面提到的KKT条件，即：根据互补松弛条件，对于任意训练样本，总有或：

若，则该样本不会在（7）中所示的模型中出现，也就不会对有任何影响；
若，则必有，所对应的样本点位于最大间隔边界上，即一个支持向量。这体现出SVM的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。

总结一下使用拉格朗日乘子法求解目标函数的步骤：

构造拉格朗日函数
对拉格朗日函数取下确界（求对偶函数），即对分别求导，求得极小值
最大化对偶函数，即对拉格朗日乘子求极大
得到转化后的目标函数

下面需要求解（6），这是一个二次规划问题（目标函数为二次函数），可以使用一般的二次规划算法求解，但是问题规模正比于训练样本数，这会在实际任务中造成很大开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法，其中SMO（Sequential Minimal Optimization）是比较著名的代表，后面会进行推导。

5 核函数

前面假设我们的训练样本是线性可分得，即存在一个划分超平面能将训练样本正确分类。但现实任务中，原始样本空间也许并不存在一个能够正确划分两类样本的超平面。

对于这样的问题，一种解决思路是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。比如对于一个二维空间，将其映射到一个合适的三维空间，就能找到一个合适的划分超平面，如果原始空间是有限维的，那么一定存在一个高维特征空间使样本可分。

令表示将映射后的特征向量，于是在特征空间中划分超平面所对应的模型可以表示为：其中是模型参数，于是类似地可以写出如下问题：其对偶问题是：求解上式涉及到计算，这是样本与映射到特征空间之后的内积，由于特征空间的维度可能很高，甚至是无穷维，因此直接计算通常是困难的。为了避开这个障碍，可以设想这样一个函数： $𝓀$ 即与在特征空间的内积等于它们在原始样本空间中通过函数 $𝓀$ 计算的结果。通过这种方式避免在高位空间上计算内积，于是我们的目标函数可以改写为： $𝓀$ 求解后，即可得到： $𝓀$ 这里的函数 $𝓀$ 被称为核函数（kernel function），上式还展示出模型的最优解可以通过训练样本的核函数展开，这一展式称为“支持向量展式”（support vector expansion）。

如果已知合适的映射的具体形式，则可以写出核函数 $𝓀$ 。但是现实任务中往往并不知道是什么形式。那么合适的核函数是否一定存在呢？什么样的函数能做核函数呢？

定理：令为输入空间， $𝓀$ 是定义在上的对称函数，则 $𝓀$ 是核函数当且仅当对于任意数据，“核矩阵”总是半正定的： $𝓀 𝓀 𝓀 𝓀 𝓀 𝓀 𝓀 𝓀 𝓀$

此定理表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射，也就是说任何一个核函数都隐式定义了一个称为“再生核希尔伯特空间”（Reproducting Kernel Hilbert Space，RKHS）的特征空间。

如前所述，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，我们并不知道选择什么核函数是合适的，而核函数也仅是隐式定义了这个特征空间，于是“核函数的选择”称为支持向量机的最大变数。如果选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。根据经验，一般情况下，对于文本类数据通常采用线性核，样本情况不明时可以先尝试高斯核。

常用的核函数如下：

此外，还可以通过函数组合得到：

若 $𝓀$ 和 $𝓀$ 为核函数，则对于任意正数，其线性组合 $𝓀 𝓀$ 也是核函数
若 $𝓀$ 是核函数，则对于任意函数 $𝓀 𝓀$ 也是核函数。

6 软间隔与正则化

前面我们假设训练样本在样本空间中是线性可分的，但实际上现实中往往很难确定一个合适的核函数使得训练样本在特征空间中线性可分，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合造成的。

缓解该问题的方法是允许SVM在一些样本上出错，即允许一些A类样本点被超平面划分到B类，为此需要引入“软间隔”（soft margin）的概念，即允许某些样本点不满足约束：而前文的SVM称为硬间隔的SVM，即所有的样本都必须划分正确。

当然，在允许样本点不满足约束的前提下，还希望这样的点尽可能少，于是优化目标可以写为： $𝓁$ 其中是一个常数， $𝓁$ 是“0/1损失函数” $𝓁$ 显然当为无穷大时，式（9）迫使所有样本均满足约束（8），当取有限值时，式（9）允许一些样本不满足约束。

然而0/1损失函数非凸且不连续，数学性质不太好，使得式（9）不容易直接求解。于是通常使用其他一些函数替代，称为“替代损失”（surrogate loss），替代损失函数一般具有比较好的数学性质，比如它们一般是凸的连续函数，且是 $𝓁$ 的上界。常用的三种替代损失函数：

hinge损失： $𝓁$
指数损失： $𝓁$
对率损失： $𝓁$

若采用hinge损失，则（9）式变成：引入“松弛变量”，即令

当时，
当时，

于是有

因此可以将（10）重写为：这就是常用的“软间隔支持向量机”。

式（11）中每个样本都有一个对应的松弛变量，用以表示该样本不满足约束（8）的程度，但这仍然是一个二次规划问题，可以使用拉格朗日乘子法得到其中是拉格朗日乘子。

令对的偏导为零可得：

将结果代入（12），即可得到对偶问题：所以求对偶函数的最大值，即由于约束条件：消去可得等价约束条件为：因此最终得到问题：将（13）与硬间隔下的对偶问题（6）对比：二者唯一的差别就在于对偶变量的约束不同，前者是，后者是，因此同样地需要满足KKT条件：于是对于任意样本，总有或。

若，则该样本不会对有任何影响
若，则必有，即该样本是支持向量，由约束条件
可知，若，则，进而有，即该样本恰好在最大间隔边界上。
若，则有，此时如果则该样本落在最大间隔内部，如果则该样本被错误分类。

由此可以看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过hinge损失函数仍然保持稀疏性。

另外，西瓜书132-133页还探讨了使用其他替代损失函数的情况，具体可参考原文。

7 SMO

SMO主要解决以下问题：基本思路是先固定之外的所有参数，然后求上的极值，由于存在约束，如果固定之外的其它变量，则可以由其它变量导出。

SMO每次选择两个变量，并固定其它参数，这样在参数初始化后，SMO不断执行如下两个步骤直至收敛：

选取一对需要更新的变量。
固定其它参数，求解（8）式获得更新后的