支持向量机(Support Vector Machine)

概念

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

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

优点

• 支持小样本
• 支持非线性和高维识别
• 泛化能力强

任务

在二分类的样本集$D={(x_i,y_i)|i=1,2,…,m},y_i\in{1,-1}$中，SVM希望找到一个超平面将不同样本分开，同时希望两边的数据离超平面有尽量大的间隔，以期获得高分类的容忍度；

超平面方程和上下的边界方程如下，对$\mathbf \omega=(\omega_1,\omega_2,…,\omega_d)$为法向量,$\mathbf b$为位移项；
$$
\mathbf \omega^T\mathbf x+\mathbf b=0,1,-1
$$
假设能将训练样本正确分类，必有：
$$
\left.\left{\begin{array}{ll}\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b\geqslant+1,&y_i=+1 ;\\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_i+b\leqslant-1,&y_i=-1 .\end{array}\right.\right.
$$
在上下边界上使得方程等号成立的点就是支持向量，上下边界之间的间隔Margin如下：
$$
\gamma=\frac2{||\boldsymbol{w}||}
$$

最大化间隔等价于如下最优化问题（Primal形式）：
$$
\begin{aligned}&\min_{\boldsymbol{w},b}\quad\frac{1}{2} |\boldsymbol{w}|^{2}\&\mathrm{s.t.} y_{i}(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}_{i}+b)\geqslant1,\quad i=1,2,\ldots,m.\end{aligned}
$$
该形式求解算法的复杂度与样本维度有关；

用Lagrange乘子法约束如下：
$$
L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2} |\boldsymbol{w}|^{2}+\sum_{i=1}^{m}\alpha_{i}\left(1-y_{i}(\boldsymbol{w}^{\mathrm{T}}\boldsymbol{x}{i}+b)\right)
$$
求偏导可知：
$$
\begin{aligned}&\boldsymbol{w}=\sum{i=1}^m\alpha_iy_i\boldsymbol{x}i ,\&0=\sum{i=1}^m\alpha_iy_i .\end{aligned}
$$
当$\alpha_i>0$,意味着第$i$个样本位于最大间隔边界上，也就是支持向量，对于SVM来说，训练结束后大多数样本无需保留，最终模型仅和支持向量有关；

对于二次凸规划问题，满足KKT条件如下（Dual形式）：
$$
\max_{\boldsymbol{\alpha}}\sum_{i=1}^m\alpha_i-\frac12\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^\mathrm{T}\boldsymbol{x}_j
\s.t.\left.\left{\begin{array}{l}\alpha_i\geqslant0 ;\\y_if(\boldsymbol{x}_i)-1\geqslant0 ;\\\alpha_i\left(y_if(\boldsymbol{x}_i)-1\right)=0 ..\end{array}\right.\right.
$$
这个问题有许多技巧处理，比如SMO算法，求解算法的复杂度与样本数量（等于拉格朗日算子$\alpha$的数量）有关；

核函数解决线性不可分问题

将样本映射到高维空间使得样本在高维空间线性可分，具体来说分类器如下：
$$
f(\boldsymbol{x})=\boldsymbol{w}^\mathrm{T}\phi(\boldsymbol{x})+b
$$
对偶问题如下：
$$
\max_{\alpha}:\sum_{i=1}^{m}\alpha_{i}-\frac{1}{2}:\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}\phi(\boldsymbol{x}{i})^{\mathrm{T}}\phi(\boldsymbol{x}{j})\
s.t. \sum_{i=1}^m\alpha_iy_i=0 ,
\alpha_i\geqslant0:,\quad i=1,2,\ldots,m
$$
构造核函数：$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\langle\phi(\boldsymbol{x}_i),\phi(\boldsymbol{x}_j)\rangle=\phi(\boldsymbol{x}_i)^\mathrm{T}\phi(\boldsymbol{x}_j)$

例如：
$$
\begin{aligned}
& k(x,z)=(x\cdot z)^2 \
& x=(x^{(1)},x^{(2)})\text{,}z=(z^{(1)},z^{(2)}) \
&\phi(x)=((x^{(1)})^2,\sqrt{2}x^{(1)}x^{(2)},(x^{(2)})^2)^T \
&\phi(x)\cdot\phi(z)=(x\cdot z)^2=k(x,z)
\end{aligned}
$$
代入得支持向量展式：
$$
\begin{aligned}
f(\boldsymbol{x})& =\boldsymbol{w}^\mathrm{T}\phi(\boldsymbol{x})+b \
&=\sum_{i=1}^m\alpha_iy_i\phi(\boldsymbol{x}i)^\mathrm{T}\phi(\boldsymbol{x})+b \
&=\sum{i=1}^m\alpha_iy_i\kappa(\boldsymbol{x},\boldsymbol{x}_i)+b .
\end{aligned}
$$