神经网络与机器学习
第12章 支持向量机
§12.1 绪论
支持向量机（support vector machines， SVM）是二分类模型，定义位特征空间上间隔最大的线性分类器，引入核函数，SVM也包含了非线性分类器，其学习策略是间隔最大化，可以化成一个凸二次规划问题。 SVM更关心的是靠近中间分割线的点，让他们尽可能地远离中间线，而不是在所有点上达到最优。
§12.2 线性可分SVM
二分类问题，输入空间和特征空间是两个不同空间，特征空间可以为欧氏空间或者希尔伯特空间，假设两个空间一一对应。
定义：线性可分支持向量机，给定线性可分数据集
\[\left \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\right \}\]
$x_i$是实向量，而$y_i$是标签，取值{+1，-1}，通过间隔最大或者凸二次规划学习的分离两类的超平面位
\[\mathrm{w}^{\mathrm{T}}\mathrm{x}+\mathrm{b}=0\]
分类决策函数
\[f(x)=sign(\mathrm{w}^{\mathrm{T}}\mathrm{x}+\mathrm{b}=0)\]
\[\begin{bmatrix}
1 & 1
\end{bmatrix}\begin{bmatrix}
x_1\\ x_2
\end{bmatrix}-1=0,w=\begin{bmatrix}
1\\1
\end{bmatrix}\]
超平面例子
图 12.1 超平面
定义：函数间隔与几何间隔。假定对于一个点A，令其垂直投影到超平面上的对应点为 x0 ，w 是垂直超平面向量，r为样本点A到超平面的距离，如图12.1所示。
几何间隔和函数间隔：那么A点到超平面的垂直距离设为(只是大小)，按照方向和几何关心，A点的向量表示
\[x=x_0+r\frac{w}{\left \|w \right \|}\]
$x_0$在超平面$w^{\mathrm{T}}x+b=0$上，所以肯定满足$w^{\mathrm{T}}x_0+b=0$，那么得到$w^{\mathrm{T}}x=-b$，那么上式同时乘以$w^{\mathrm{T}}$
\[w^{\mathrm{T}}x=w^{\mathrm{T}}x_0+r\frac{w^{\mathrm{T}}w}{\left \|w \right \|}\]
得到
\[r\frac{w^{\mathrm{T}}w}{\left \|w \right \|}=r\left \|w \right \|=w^{\mathrm{T}}x-w^{\mathrm{T}}x_0=f(x)\\
\Rightarrow r=\frac{f(x)}{\left \|w \right \|}=\frac{w^{\mathrm{T}}x+b}{\left \|w \right \|}\]
而点A可能在正的一侧，也可能在负的一侧，所以几何间隔应该乘以分类y，定义为
\[r=y\frac{w^{\mathrm{T}}x+b}{\left \|w \right \|}\]
其中
\[\widehat{r}=y(w^{\mathrm{T}}x+b)\]
称为函数间隔，几何间隔与函数间隔就是差||w||范数，这样能够避免成比例改变w和b造成的函数间隔缩扩。
间隔最大化：
线性可分数据集有很多分离超平面，但是几何间隔最大的超平面是唯一的，又称为硬间隔最大化。因此，可以表示为下面约束最优化问题
\[\left\{\begin{matrix}
\underset{w,b}{max}\quad r\\
s.t.\quad y_i(w^{\mathrm{T}}x_i+b)-1\geq r,i=1,2,\cdots,N
\end{matrix}\right.\]
求几何间隔最大就是函数间隔最大
\[\left\{\begin{matrix}
\underset{w,b}{max}\quad \widehat{r}\\
s.t.\quad y_i(w^{\mathrm{T}}x_i+b)-1\geq \widehat{r},i=1,2,\cdots,N
\end{matrix}\right.\]
注意可以等价为最小化||w||，而把$\widehat{r}=1$固定，因此成为
\[\left\{\begin{matrix}
\underset{w,b}{min}\quad \frac{1}{2}\left \| w\right \|^2\\
s.t.\quad y_i(w^{\mathrm{T}}x_i+b)-1\geq 0,i=1,2,\cdots,N
\end{matrix}\right.\]
这样变成了一个凸二次规划问题，因为$||w||^2$是凸函数，约束是仿射函数。
间隔最大分离平面的存在唯一性：
定理： 如训练集线性可分，那么把训练集和中样本点完全正确分开的最大间隔分类超平面存在且唯一。
证明：存在性。凸优化肯定有解，而且w=0不是最优解，因为训练数据有正有负，所以$w \neq 0$，因此肯定存在。
唯一性：假设存在两个最优解$(w_1^*,b_1^*)$，$(w_2^*,b_2^*)$，显然最小值都满足
\[\left \| w_1^*\right \|=\left \| w_2^*\right \|=c\\
c \leq \left \| w\right \|\leq \frac{1}{2}(\left \| w_1^*\right \|+\left \| w_2^*\right \|)=c\]