背景

基本概念

支撑向量机（Support Vector Machine, SVM）的目的是在线性分类的基础上，找到鲁棒性最好的那条分类直线（超平面），所谓的鲁棒性最好，其实就是找到分类间隔最大的那个超平面（可参考林轩田教程）。

SVM的分类：

1. Hard-margin SVM（最大间隔分类器）；
2. Soft-margin SVM;

   1. Kernel method;

约束优化必备知识

SVM的模型求解需要约束优化的相关知识，总结如下：
约束问题的形式如下：

定义Lagrange函数：

因此原问题等价于：

其对偶形式为：

注意
，也就是说，对偶问题的解小于等于原问题的解，若满足严格小于的条件，则成为弱对偶，否则为强对偶。

对偶问题的解小于等于原问题的解的几何解释： 为简化，我们设原问题： 对偶问题： 定义域为。 构建区域，如图所示。 ，图中红色部分； 其中，，根据直线的位置可以确定。

定义Slater条件：存在定义域内部存在一点，满足不等式约束小于等于零严格成立：。对于凸优化问题，满足Slater条件时，原问题与对偶问题之间为强对偶关系。一般的凸优化问题都满足Slater条件，另外还有一种松弛的Slater条件，即只需令约束条件中仿射映射以外的函数满足Slater条件即可。
另一种与强对偶关系等价的时KKT（Karush-Kuhn-Tucker）条件：

1. 可行域：；
2. 互补松弛条件：；
3. 梯度为零：；

当满足KKT条件时，设原问题的解为，对偶问题的解为时：


，可见两个解等价，上述推导中，第一个红色等号用到了梯度为零的条件，第二个红色等号则用到了互补松弛条件。

Hard-margin SVM

模型构建

符号：
要实现最大间隔，求解模型可以概括为：

我们定义间隔值（）为数据点到超平面的最小距离：

，从而优化问题可以改写为：

，这里不妨取，这是因为该值不同的取值只是对的等比例放缩，最终得到的是同一个分类超平面，因此优化问题进一步写为（注意，）：


该问题转化为了包含N个约束的凸优化问题。
若N非常大，求解或遇到困难，引入Lagrange函数：

原问题等价无约束问题：，其对偶形式为：
，由于约束条件全部为仿射函数，因此对偶解就是原问题的解。

模型求解

代入L：

，

由此可得：

因此对偶问题为：

由于存在强对偶关系，因此优化问题也满足KKT条件：

1. ；
2. ；
3. ；
4. ；

从而得到：


计算得到这两个参数便得到了鲁棒性更好的决策超平面：，而根据上面的表达式可知这些参数是满足的向量的线性组合，这些满足条件的向量被称为支撑向量。

Soft-margin SVM

当数据是不可分的情况时，可以在损失函数中加入错误分类的可能性，错误分类的个数为：，由于该函数不连续，因此可将其改写成：，称之为Hinge function，将error引入Hard-SVM后得到：

其中的C为Hyperparameters代表错误水平，由人为设定，如果实际问题中，对错误的容许很低，例如加密工作等，就可以增大这个值来加大惩罚。对于被错误分类的点，我们假设该点与支撑向量所在超平面的距离为，自然距离是正定的即；结合图可知此时约束可以被改写为：，因此模型可改写为：

核方法

背景

1. 当数据严格不可分时，可以引入特征转化函数将其转为线性可分的数据集，例如将数据转为高纬度，高维化的数据比低维度的数据更容易线性可分；
2. 引入特征函数后，其对偶形式造成了需要对特征函数求内积：

，
。而大量的内积运算求解困难，主要是特征函数相对难求，为此引入核函数（kernel function）的概念。

核函数的定义

满足如下条件的映射构成的函数被称为核函数：

满足内积性质的核函数，即，使得：

其中是Hilbert空间，则是正定核函数。

Hilbert空间： Hilbert是一个完备的（对极限运算封闭）可能是无限维的被赋予内积运算的线性函数空间，满足以下性质：

1. 对称性：；
2. 正定性：，当且仅当时取等；
3. 线性：；

正定核函数的例子： 其中，取 ，所以，

正定核函数的等价定义

如果核函数满足：

1. 对称性：；
2. 正定性：，对应的Gram矩阵（）是半正定的；则为正定核函数。

   证明： 充分性： 内积定义使其满足对称性，记 ， 其中，；，根据Hilbert空间的线性性质，，使得 ，因此Gram矩阵K是半正定的。 必要性： 已知K是半正定矩阵，那么K的特征值，且有分解：，令，是K的特征值对应的特征向量，因此： ，因此是正定核函数。 证毕