SVM
一、支持向量机
1 间隔与支持向量
支持向量机（support vector machines, SVM）是一种二分类模型，给定一组样本集
从直观上看，应该找到两类训练样本正中间的那个超平面，因为该划分超平面对训练样本局部扰动的容忍性最好。所谓容忍性，也可以叫做鲁棒性，如果训练集的局限性或者由于噪声等因素，训练集外的某些样本可能会更接近划分超平面，这将使之前的许多划分超平面出现错误，而正中间的超平面受到的影响最小。
在样本空间中，划分超平面可通过如下线性方程来描述：
1.1 几何间隔
超平面与样本空间中的任意样本点
几何间隔（点到超平面距离）的公式证明如下。
设
，其到超平面几何距离为 ， 为其在超平面的投影，两点在线性空间构成向量 ，显然 与 平行，二者内积的绝对值： 展开 ： 由于点 在超平面上，满足超平面方程，所以有 ，因此，代入上式得： 由于法向量的模 ，所以有： 原式得证。
1.2 支持向量
假设超平面能够将样本正确分类（即假设训练数据集是线性可分的），即对于
- 若
，则有 ， - 若
，则有
令：
如图
距离超平面最近的这几个训练样本点使上面不等式中的等号成立，它们被称为支持向量（support vector），两个不同类的支持向量的到超平面的距离之和为：
2 SVM基本型
要找到具有“最大间隔“的超平面，也就是寻找
显然，为了最大化问隔
3 拉格朗日对偶2
3.1 凸优化问题的一般形式
在优化问题中，有时候直接求解原始问题往往是很困难的，我们可以考虑将原始问题转化为它的对偶问题，通过求解它的对偶问题来得到原始问题的解。这就是凸优化问题中的对偶问题。
原始最优化问题的一般形式如下：
原始问题的定义域
可行集
3.2 拉格朗日函数
原始问题的拉格朗日函数定义为：
- 拉格朗日函数
如果看成是关于 的函数，那它其实就是对原始问题中目标函数与约束条件进行线性加权，目标函数的权系数是1，约束条件的权系数是 或 ； - 拉格朗日函数
如果看成是关于 或 的函数，那么其余部分可看成常数， 就可以看作是关于 或 的仿射函数（即最高次幂为1的多项式函数）
3.3 拉格朗日对偶函数
拉格朗日对偶函数（对偶函数）通过对拉格朗日函数关于
- 对偶函数一定是凹函数，其凹性与原目标函数和约束函数凹凸与否无关
- 对于
（向量中的每个分量），如果原问题最优解对应的目标函数值为 ，则
性质1说明，求解原问题的对偶问题时，并不要求原始问题一定是凸问题。
性质2说明，当不等式约束的拉格朗日乘子
3.4 对偶问题
进一步地，根据上述两条性质，既然对偶函数是原始问题最优解的下界，那么最优的下界实际上就是最大化对偶函数（因为性质1，对偶函数为凹函数，故拉格朗日对偶问题一定是凸优化问题）。设对偶函数的最优解为
- 当
时，称为弱对偶（weak duality） - 当
时，称为强对偶（strong duality） 称为对偶间隙（duality gap）
具体是强对偶还是弱对偶，取决于原始问题的约束条件。这说明在解存在的情况下，弱对偶总是成立；当满足强对偶时，可以通过求解对偶问题来得到原始问题的解。
3.5 Slater条件
slater条件用于判断强对偶性在何时成立。首先原始问题必须满足凸优化问题，且
slater是强对偶性成立的充分条件，即如果满足该条件，则强对偶一定成立，不满足该条件，强对偶也可能成立。因此，要验证原始问题的解与对偶问题的解一致，可以首先验证slater条件，只有该条件成立时，原始问题与对偶问题的解一致。
3.6 KKT条件
在满足强对偶，且拉格朗日函数
稳定性条件（stationarity）
若
互补松弛条件（complementary slackness）
当
原问题的可行性（primal feasibility）
原问题的最优解必然满足原问题的约束条件。
对偶问题的可行性（dual feasibility）
对偶问题的最优解必然满足对偶问题的约束条件。
KKT条件与最优解的充分必要性
对于一般的原始问题，KKT 条件是
对于原始问题为凸优化的问题，KKT 条件是
4 拉格朗日乘子法求解对偶问题3
我们对希望求解的式（1）使用拉格朗日乘子法可得到其对偶问题（dual problem），对式（1）中的每条约束添加拉格朗日乘子
其中，
关于此处求导的原因，还可以理解为：由于SVM问题满足slater条件，因此满足强对偶性。因此其最优解一定满足KKT条件，而KKT条件的稳定性条件说明，最优解
能使得拉格朗日函数 关于 的一阶导数等于0。
将拉格朗日函数展开：
- 若
，则该样本不会在（7）中所示的模型中出现，也就不会对 有任何影响； - 若
，则必有 ，所对应的样本点位于最大间隔边界上，即一个支持向量。这体现出SVM的一个重要性质：训练完成后，大部分的训练样本都不需要保留，最终模型仅与支持向量有关。
总结一下使用拉格朗日乘子法求解目标函数的步骤：
- 构造拉格朗日函数
- 对拉格朗日函数取下确界（求对偶函数），即对
分别求导，求得极小值 - 最大化对偶函数，即对拉格朗日乘子
求极大 - 得到转化后的目标函数
下面需要求解（6），这是一个二次规划问题（目标函数为二次函数），可以使用一般的二次规划算法求解，但是问题规模正比于训练样本数，这会在实际任务中造成很大开销。为了避开这个障碍，人们通过利用问题本身的特性，提出了很多高效算法，其中SMO（Sequential Minimal Optimization）是比较著名的代表，后面会进行推导。
5 核函数
前面假设我们的训练样本是线性可分得，即存在一个划分超平面能将训练样本正确分类。但现实任务中，原始样本空间也许并不存在一个能够正确划分两类样本的超平面。
对于这样的问题，一种解决思路是将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。比如对于一个二维空间，将其映射到一个合适的三维空间，就能找到一个合适的划分超平面，如果原始空间是有限维的，那么一定存在一个高维特征空间使样本可分。
令
如果已知合适的映射
定理：令
为输入空间， 是定义在 上的对称函数，则 是核函数当且仅当对于任意数据 ，“核矩阵” 总是半正定的：
此定理表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。事实上，对于一个半正定核矩阵，总能找到一个与之对应的映射
如前所述，我们希望样本在特征空间内线性可分，因此特征空间的好坏对支持向量机的性能至关重要。需注意的是，在不知道特征映射的形式时，我们并不知道选择什么核函数是合适的，而核函数也仅是隐式定义了这个特征空间，于是“核函数的选择”称为支持向量机的最大变数。如果选择不合适，则意味着将样本映射到了一个不合适的特征空间，很可能导致性能不佳。根据经验，一般情况下，对于文本类数据通常采用线性核，样本情况不明时可以先尝试高斯核。
常用的核函数如下：
此外，还可以通过函数组合得到：
若
和 为核函数，则对于任意正数 ，其线性组合 也是核函数 若
是核函数，则对于任意函数 也是核函数。
6 软间隔与正则化
前面我们假设训练样本在样本空间中是线性可分的，但实际上现实中往往很难确定一个合适的核函数使得训练样本在特征空间中线性可分，即使恰好找到了某个核函数使训练集在特征空间中线性可分，也很难断定这个貌似线性可分的结果不是由于过拟合造成的。
缓解该问题的方法是允许SVM在一些样本上出错，即允许一些A类样本点被超平面划分到B类，为此需要引入“软间隔”（soft margin）的概念，即允许某些样本点不满足约束：
当然，在允许样本点不满足约束的前提下，还希望这样的点尽可能少，于是优化目标可以写为：
然而0/1损失函数非凸且不连续，数学性质不太好，使得式（9）不容易直接求解。于是通常使用其他一些函数替代，称为“替代损失”（surrogate loss），替代损失函数一般具有比较好的数学性质，比如它们一般是凸的连续函数，且是
- hinge损失：
- 指数损失：
- 对率损失：
若采用hinge损失，则（9）式变成：
- 当
时， - 当
时，
于是有
因此可以将（10）重写为：
式（11）中每个样本都有一个对应的松弛变量，用以表示该样本不满足约束（8）的程度，但这仍然是一个二次规划问题，可以使用拉格朗日乘子法得到
令
将结果代入（12），即可得到对偶问题：
若
，则该样本不会对 有任何影响 若
，则必有 ，即该样本是支持向量，由约束条件 可知，若 ，则 ，进而有 ，即该样本恰好在最大间隔边界上。 若
，则有 ，此时如果 则该样本落在最大间隔内部，如果 则该样本被错误分类。
由此可以看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过hinge损失函数仍然保持稀疏性。
另外，西瓜书132-133页还探讨了使用其他替代损失函数的情况，具体可参考原文。
7 SMO
SMO主要解决以下问题：
SMO每次选择两个变量
- 选取一对需要更新的变量
。 - 固定其它参数，求解（8）式获得更新后的
alipay
wechat
