支持向量机（Support Vector Machine，SVM）算法原理

SVM简介

支持向量机（support vector machines, SVM）是一种二分类模型，它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机；SVM还包括核技巧，这使它成为实质上的非线性分类器。SVM的的学习策略就是间隔最大化，可形式化为一个求解凸二次规划的问题，也等价于正则化的合页损失函数的最小化问题。SVM的的学习算法就是求解凸二次规划的最优化算法。

SVM发展史

margin

SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

拉格朗日优化有约束条件的目标函数

原目标函数是一个含有不等式约束的凸二次规划问题，可以对其使用拉格朗日乘子法得到其对偶问题（dual problem）。将有约束的原始目标函数转换为无约束的新构造的拉格朗日目标函数。

simple example

soft margin

实际情况下几乎不存在完全线性可分的数据，为了解决这个问题，引入了“软间隔”的概念，即允许某些点不满足约束，可以在间隔内。

非线性SVM

对于输入空间中的非线性分类问题，通过非线性变换将它转化为某个维特征空间中的线性分类问题，在高维特征空间中学习线性支持向量机。

由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例和实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数替换当中的内积。


通过核函数，实现了在原始空间线性不可分问题转化为高维空间线性可分问题，同时又避免了高维空间计算复杂度过高的问题。

核函数

多项式核函数、高斯核函数等

将原始空间的内积转化为高维空间内积，进而转换为核函数。