支持向量机 SVM(Support Vector Machine) 要解决的问题就是：如果让分类器的泛化能力达到最高？
下面三张图，哪个泛化能力更好？
只要不傻，肯定都觉得第3个是最好的，因为第3个的分类超平面与样本点间的距离最远，所以在预测新样本的时候，第3个的误分类可能性更低。
基于上面的思想，如何让这条线能正确分类的情况下，还能与所有样本点的距离达到最远，把封面上那两条线中间的范围变得更宽(如标题图中所示，两条线的区域越宽越好)，就是SVM要解决的问题。
算法思路：
假设要对一个二值分类的问题建立一个线性分类器，分类特征(feature)为$x$, 分类标签(label)为$y$，$y\in\{-1,+1\}$。那么，可以建立一个分类器：
$$ h_{w,b}(x)=g(w^Tx+b) $$
其中，$w$是权值(weight)，$b$是偏置(bias)，$wx+b=0$就是分类超平面(在2维情况下，$wx+b=0$一条线，但3维及以上时，就是一个平面/超平面了)。
$g$是sign函数(也称符号函数)，公式如下：
$$ g(z)=\begin{cases} +1&,z\ge 0\\ -1&,z<0 \end{cases} $$
这个分类器能够在输入样本$x$后，输出相应的$\hat y$。
为了让这个分类器的泛化能力更高，就要让所有样本点与分类超平面距离更远。
根据高中点到直线(平面)的距离公式，样本点$(x^{(i)}, y^{(i)})$到超平面的距离为：
$$ \frac{|w^Tx^{(i)}+b|}{||w||} $$
上面的式子等同于
$$ \|\frac{w^T}{||w||}x^{(i)}+\frac{b}{||w||}\| $$
假设分类器完全正确分类所有样本，也就是$y^{(i)}$与$g(w^Tx^{(i)}+b)$同号。那么可以推出：
$$ \begin{vmatrix} \frac{w^T}{||w||}x^{(i)}+\frac{b}{||w||}\end{vmatrix}\equiv y^{(i)}(\frac{w^T}{||w||}x^{(i)}+\frac{b}{||w||}) $$
那么，最大化全部样本点与超平面的距离的问题，就变成了约束最优化问题：
$$ \max\limits_{w,b}\gamma\\ s.t.\ \ \ y_i(\frac{w^T}{||w||}x_i+\frac{b}{||w||})\ge \gamma,\ \ i=1,2,...,N $$
上面的式子是说，我们希望最大化超平面$(w,b)$与与所有样本点的距离至少为$\gamma$。将限制条件改写一下，两边同时乘$||w||$，则会得到：
$$ \max\limits_{w,b}\gamma\\ s.t.\ \ \ y_i(w^Tx_i+b)\ge \gamma\cdot ||w||,\ \ i=1,2,...,N $$
另$\gamma\cdot ||w||=\hat \gamma$，则可以将公式改写为：
$$ \max\limits_{w,b}\frac{\hat \gamma}{||w||}\\ s.t.\ \ \ y_i(w^Tx_i+b)\ge \hat \gamma,\ \ i=1,2,...,N $$
由于$\hat \gamma=\gamma\cdot ||w||$，是受到$||w||$ 取值控制的，于是，$\hat \gamma$的取值，可以用$w$的量级来控制(让$w=2w,b=2b$不影响分类的决策结果)，所以我们可以将$\hat \gamma$ 限制在$\hat\gamma=1$，并将其带入优化问题：
$$ \max\limits_{w,b}\frac{1}{||w||}\\ s.t.\ \ \ y_i(w^Tx_i+b)-1\ge 0,\ \ i=1,2,...,N $$
$\frac{1}{||w||}$取得最大值的时候，$\frac{1}{2}||w||^2$取得最小值，所以可以将优化问题改写为：
$$ \min\limits_{w,b}\frac{1}{2}||w||^2\\ s.t.\ \ \ y_i(w^Tx_i+b)-1\ge 0,\ \ i=1,2,...,N $$
这是一个凸二次规划(convex quadratic programming,缩写QP)问题。
凸优化问题就是指约束最优化问题
$$ \min\limits_w f(w)\\ \begin{eqnarray} s.t.\ \ &g_i(w)\le 0,\ \ &i=1,2,...,k\\ &h_i(w)=0, &i=1,2,...,l \end{eqnarray} $$
其中，目标函数$f(w)$与约束函数$g_i(w)$都是$R^n$上的连续可微函数
求出了这个约束最优化问题，就求出了线性可分支持向量机。
算法
线性可分SVM的算法如下：
输入：$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中，$x_i\in R^n$,$y_i\in\{-1,+1\}$
输出：最大间隔分类超平面$(w,b)$和分类决策函数$f(x)$
(1)构造并求解约束最优化问题：
$$ \min\limits_{w,b}\frac{1}{2}||w||^2\\ \begin{eqnarray} s.t.\ \ y_i(w^Tx+b)-1\ge0,\ \ i=1,2,...N \end{eqnarray} $$
求出最优的$w^*$，$b^*$。
(2)得到超平面：
$$ w^*x+b^*=0 $$
分类决策函数
$$ f(x)=sign(w^*x+b^*) $$
这一篇，了解了基础的线性可分SVM。下一篇，将讲解SVM学习的对偶算法。