支持向量机（SVM）算法详解

与感知机算法不同，在支持向量机（Support Vector Machines，SVM）中，求解出的分隔超平面不仅能够正确划分训练数据集，而且几何间隔最大。

间隔最大化

对于几何间隔最大的分隔超平面： 同时，对于每一个样本，需要满足： 考虑到几何间隔和函数间隔之间的关系，则上述的几何间隔最大的分隔超平面可以等价为： 同时需要满足： 在函数间隔中，函数间隔的取值并不影响到最优问题的解，如上所述，当参数 W 和 b 同时扩大为原来的 2 倍，函数间隔也会同时扩大为原来的 2 倍，这对于上述的优化问题和约束条件并没有影响，因此，可以取值为 1，则上述的优化问题变成：

支持向量和间隔边界

对于如图 1 所示的线性可分的二分类问题，在 m 个训练样本中，与分隔超平面距离最近的样本称为支持向量（Support Vector）。支持向量 X⁽ⁱ⁾ 对应着约束条件为：

当 y⁽ⁱ⁾=+1 时，支持向量所在的超平面为：

当 y⁽ⁱ⁾=-1 时，支持向量所在的超平面为：

对于支持向量所在的超平面 H₁ 和 H₂ ，如图 2 所示。


在图 2 中，超平面 H₁ 和超平面 H₂ 之间的距离成为间隔，超平面 H₁ 和超平面 H₂ 又称为间隔边界。在确定最终的分隔超平面时，只有支持向量起作用，其他的样本点并不起作用，由于支持向量在确定分割超平面中起着重要的作用，因此，这种分类模型被称为支持向量机。

线性支持向量机

对于如图 1 所示的数据集，其条件极为苛刻，要求所有的样本都是线性可分的，即存在分隔超平面，能够将所有的正样本和负样本正确区分开，但是在实际情况中，数据集很难满足这样的条件，对于一个数据集，其中存在部分的特异点，但是将这些特异点除去后，剩下的大部分的样本点组成的集合是线性可分的。

对于线性不可分的某些样本点 (X⁽ⁱ⁾，y⁽ⁱ⁾) 意味着其不能满足函数间隔大于或等于 1 的约束条件，为了解决这个问题，可以对每个样本点 (X⁽ⁱ⁾，y⁽ⁱ⁾) 引进一个松弛变量 ξ_i≥0，使得函数间隔加上松弛变量大于或等于 1，这样，约束条件变为：

同时，对每个松弛变量 ξ_i，支付一个代价 C，此时，目标函数变为：
此时的优化目标为：