支持向量机(SVM)是一种二分类模型，跟之前介绍的感知机有联系但也有区别。简单来讲，感知机仅仅是找到了一个平面分离正负类的点，意味着它是没有任何约束性质的，可以有无穷多个解，但是(线性可分)支持向量机和感知机的区别在于，支持向量机有一个约束条件，即利用间隔最大化求最优分离超平面，这时，支持向量机的解就是唯一存在的。

　　首先来看线性可分的支持向量机，对于给定的数据集，需要学习得到的分离超平面为：

以及对应的分类决策函数：

　　一般而言，一个点距离分离超平面的远近可以表示分类预测的确信程度。如果超平面确定，那么能够相对的表示点到超平面的距离，而和的符号是否一致能表示分类是否正确。所以用来表示分类的正确性及确信度，这就是函数间隔。对于给定的数据集，需要寻找的是函数间隔的最小值，但是这仍然不够，假如成比例的改变和，那么函数间隔也会随之改变，那么需要使，使得间隔确定，这时函数间隔变成了几何间隔。

　　从而函数间隔和几何间隔有下面的关系：

　　那么要寻找一个超平面的问题首先是转化为求几何间隔最大的问题，然后由几何间隔和函数间隔的关系，可以改写为：

可以看出，的取值并不影响最优化问题的解，那么可以取。并且最大化和最小化是等价的，于是得到线性可分支持向量机的最优化问题：

　　在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量，支持向量是使上面的约束条件取等号的点。为了求解上述问题，利用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解。首先，构建拉格朗日函数，对每一个不等式约束引进拉格朗日乘子,定义拉格朗日函数：

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题:

先求，可得:

带入拉格朗日函数，再求对的极大，即是对偶问题：

将目标函数由极大转化为极小，就得到了下面与之等价的对偶函数的最优化问题：

 　　线性可分问题的支持向量机学习方法(硬间隔最大化)，对线性不可分训练数据是不适用的，线性不可分意味着某些样本点不能满足函数间隔大于等于1的约束条件。为了解决这一问题，可以对每个样本点引进一个松弛变量，使函数间隔加上松弛变量大于等于1。这样，约束条件变为：

同时，对每个松弛变量，支付一个代价。目标函数由原来的变成

这里，称为惩罚函数，起到了调和误分类惩罚和间隔的关系，一般由应用问题决定。

　　于是，线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题(原始问题)：

同样的，利用拉格朗日的对偶性，可以求得上述原始问题的对偶问题：

解出之后，按照与和的关系，对其进行求解，既可得出超平面。

　　上面介绍的两种方法都是解线性分类问题，但是，有时分类问题是非线性的，这时可以用非线性支持向量机，非线性支持向量机主要是利用核技巧，核技巧不仅应用于支持向量机还应用于其他的统计学问题。

　　核技巧应用到支持向量机，其基本想法就是通过一个非线性变换将输入空间(欧式空间或者离散集合)对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型，这样，便将非线性问题转化为了线性问题求解。常用的核函数有多项式核，高斯核等。

　　对偶问题中的内积可以用表示，此时，非线性支持向量机的最优化问题可以表示为：

而为了解决上述问题，便需要SMO算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他的变量，针对这两个变量构建一个二次规划问题。

　　不失一般性，假设选择的两个变量是，其它变量是固定的。于是SMO的最优化问题的子问题可以写成：

　　为了求解两个变量的二次规划问题，首先分析约束条件，然后在此约束条件下求极小；由于只有两个变量，约束可以用二维空间的图形表示。假设上述问题的初始可行解为，最优解为，并且假设在沿着约束方向未经剪辑时的最优解为。并且的取值范围必须满足条件：

如果，则

如果，则

　　下面先求沿着约束方向未经剪辑时的最优解；然后再求剪辑后的的解。为了方便叙述，记：

当时，为函数对输入的预测值与真实值之差。

　　上述最优化问题沿着约束方向未经剪辑时的解是：

 其中，

经过剪辑之后的的解是：

由求得是：

为了更加高效的选择两个变量使得目标函数下降最快，即SMO算法中启发式选择：

 　　SMO称选择第一个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第一个变量，其中优先选择间隔边界上的支持向量的点，检验它们是否满足KKT条件；第二个过程为内层循环，即寻找第二个变量，标准是希望能使第二个变量有足够大的变化。

统计学习笔记之支持向量机