一、基本概念
SVM 寻找一个最大边缘超平面（maximal margin hyperplane），使得将数据分开，并且有最大的margin，泛化能力。
（1）结构风险最小化（structual risk minimization，SRM）
线性分类器的边缘与泛化误差之间的关系，分类器的泛化误差在最坏的情况下：
$$R\leqslant R_{e}+\varphi \left(\frac{h}{N},\frac{log(\eta )}{N}\right)$$
$\varphi$是h的单调增函数，$1-\eta$表示概率。
（2）SVM线性分类器
模型：
$$ w\cdot x+b=0$$
线性分类图：
于是我们有：
$$ w\cdot x_{s}+b=k,w\cdot x_{c}+b=k$$
其中，k>0，左边表示在决策边界的上面。k’<0，右边表示在决策边界下面。
如果我们标记一个类为+1，另一个类为-1，则有：
距离：
$$ w(x_{1}-x_{2})=2\rightarrow d=\frac{2}{\left | w \right |},\left | w \right |=\sqrt{w_{1}^{2}+w_{2}^{2}+…+w_{k}^{2}}$$
（3）线性SVM：可分情况
决策边界的参数
上面的为+1，下面的为-1，则可以概括为：
$$ y_{i}(w\cdot x_{i}+b)\geqslant 1,i=1,2,…,N$$
最大化边缘，等价于最小化下面目标函数：
$$f(w)=\frac{\left|w\right|^{2}}{2}$$
目标函数是二次的，约束在w、b上是线性的，这是一个凸优化问题，通过拉格朗日乘子求解。
$$L_{p}=\frac{1}{2}\left|w\right|^{2}-\sum_{i=1}^{N}\lambda _{i}(y_{i}\left(w\cdot x_{i}+b)-1\right)$$
Karuch-Kuhn-Tucher（KKT）：
把不等式约束转换为等式约束，限制拉格朗日乘子非负。
$$ \lambda_{i}\geqslant 1$$
$$ \lambda_{i}[y_{i}(w\cdot x_{i}+b)-1]=0$$
下面的等式，使得许多拉格朗日乘子都变为零。该约束表明，除非$y_{i}(w*x_{i}+b)=1$，否则拉格朗日乘子必须为零。
那些$\lambda>0$的训练实例在两个超平面上，称为支持向量，$lambda=0$的肯定不在超平面上。决策边界w、b仅仅依赖这些支持向量。
此外，也可以使用对偶拉格朗日，使用二次规划求解。
SVM的例子：
<简书>：我的心在滴血啊，写了一下午，你居然没有保存，网站页面设计的“保存中…”“已保存”就是个普通js吗？没有事务的吗？就修改文档的时候触发一下，然后也不判断是否联网，是否保存等。逗！！再不用简书。
