支持向量机(Support Vector Machine)

支持向量机(Support Vector Machine)是Vapnik等于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。

SVM是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以期获得最好的推广(泛化)能力

在二分类的样本集中，SVM希望找到一个超平面将不同样本分开，同时希望两边的数据离超平面有尽量大的间隔，以期获得高分类的容忍度；

超平面方程和上下的边界方程如下，对为法向量,为位移项；

假设能将训练样本正确分类，必有：

在上下边界上使得方程等号成立的点就是支持向量，上下边界之间的间隔Margin如下：

最大化间隔等价于如下最优化问题（Primal形式）：

该形式求解算法的复杂度与样本维度有关；

用Lagrange乘子法约束如下：

求偏导可知：

当,意味着第个样本位于最大间隔边界上，也就是支持向量，对于SVM来说，训练结束后大多数样本无需保留，最终模型仅和支持向量有关；

对于二次凸规划问题，满足KKT条件如下（Dual形式）：

这个问题有许多技巧处理，比如SMO算法，求解算法的复杂度与样本数量（等于拉格朗日算子的数量）有关；

将样本映射到高维空间使得样本在高维空间线性可分，具体来说分类器如下：

对偶问题如下：

构造核函数：

例如：

代入得支持向量展式：