线性可分支持向量机

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

两类样本的情况，离分类面最近的样本到分类面的距离称为分类间隔，最优超平面又叫最大间隔超平面。

支持向量就是决定最大间隔超平面的数据点。

一、函数间隔和几何间隔

超平面wx+b=0 完全由(w,b)决定。
线性可分支持向量机利用间隔最大化求最优分离超平面，这时解是唯一的。

1.1, 函数间隔

在超平面wx+b=0确定的情况下，|wx+b|能够表示点x到距离超平面的远近，而通过观察 wx+b 的符号与类标记y的符号是否一致可判断分类是否正确，所以，可以用*( y(wx+b) )*的正负性来判定或表示分类的正确性。于此，我们便引出了函数间隔（functional margin）的概念。

函数间隔： 定义超平面(w, b)关于样本点$(x_i,y_i)$的函数间隔为：
     $\widehat{{\gamma }_i}=y_i(\omega \cdot x_i+b)$
注意到：
选择分离超平面时，只要成比例地改变w和b, 例如将它们改为cw和cb(c是常数)，超平面并没有改变，但函数间隔却成为原来的c倍。

要选择最大间隔的超平面，还需要对法向量$\omega$加上某些约束，比如规范化，使得间隔是确定的。
这时函数间隔成为几何间隔(geometric margin)。
此时，上述常数$c=\frac{1}{||\omega ||}$。

怎样才能使分类间隔最大呢？先计算分类间隔，然后优化求解。

1.2 如何计算几何间隔呢？

先看一个点到超平面的间隔(也就是距离)。

第一种视角：

考虑二维空间中点到直线的“间隔”：
点(x0, y0)到直线 ax + by + c = 0的距离公式：
$d=\frac{|a{x}_0+b{y}_0+c|}{\sqrt{a^2+b^2}}$
扩展到 n 维空间中：
$d^n=\frac{|a_1{x}_1+a_2{x}_2+...+a_n{x}_n+c|}{\sqrt{a_1^2+a_2^2+...+a_n^2}}$
然后表示成向量形式：
$D=\frac{1}{||\omega ||}|\omega \cdot x+b|$
其中，$||\omega ||$ 是向量w的二范数，w = {w1,w2,w3,…,wn}。

第二种视角：
https://blog.csdn.net/yjn03151111/article/details/46746839

向量知识：${\omega }^T\omega =||\omega |{|}^2$

假设任意一个样本x，在分类超平面${\omega }^{T}x+b=0$上的投影记为$x_0$，x到分类平面的距离记为d(d >= 0)。
w是垂直于超平面的法向量，法向量的方向(单位向量)是法向量除以它的模长：$\frac{\omega }{||\omega ||}$，可以得到：
   $x-x_0=d\cdot \frac{\omega }{||\omega ||}\Rightarrow x=x_0+d\cdot \frac{\omega }{||\omega ||}$
两边同时左乘${\omega }^T$：
$$\begin{gathered} {\omega }^{T}x-{\omega }^T{x}_0=d\cdot \frac{{\omega }^T\omega }{||\omega ||}=d||\omega || \\ d||\omega ||={\omega }^{T}x-{\omega }^T{x}_0-b+b={\omega }^{T}x-({\omega }^T{x}_0+b)+b \end{gathered}$$

又由于x0在超平面${\omega }^T{x}_0+b=0$上，代入得
$d=\frac{|{\omega }^{T}x+b|}{||\omega ||}$ (d >= 0)

第三种视角：
https://www.jianshu.com/p/097ab4f0d4d4

设X1是决策边界上的一点，那么任意点X到决策边界的距离D，是向量X X1长度在垂直于决策边界方向上的投影，既$dist=X-X_1=||X-X_1||cos(\alpha )$，alpha为向量X X1与垂直于决策边界方向的夹角。

两个向量相乘等于向量长度的乘积再与向量夹角余弦值的乘积，由于w是决策边界的法向量，
所以w与X - X_1 的夹角就是上式中的alpha，于是：
$$\begin{gathered} \omega (X-X_1)=||\omega ||\ast ||X-X_1||cos(\alpha ) \\ \frac{\omega }{||\omega ||}(X-X_1)=|X-X_1||\ast cos(\alpha )=dist \end{gathered}$$

所以$dist=\frac{\omega }{||\omega ||}(X-X_1)=\frac{{\omega }^{T}X-{\omega }^T{X}_1}{||\omega ||}$

又由于X1在超平面${\omega }^T{X}_1+b=0$，代入得
$dist=\frac{1}{||\omega ||}({\omega }^{T}X+b)$

为了确保距离非负，我们在${\omega }^{T}X+b$外面加一个绝对值符号。

1.3 几何间隔和函数间隔的关系

记 y∈{−1,1} 为分类标签，间隔公式乘以类别标签，所以$|w^{T}x+b|=y_i(w^{T}x+b)$，我们可以以此消去上式的绝对值。于是
N 个样本 Xi 和分类超平面的几何间隔的表达式：
   $\gamma =\frac{y_i(w^T{x}_i+b)}{\Vert \omega \Vert },i=1,2,...,N$
由函数间隔的表达式：$\hat{\gamma }=y_i(\omega \cdot x_i+b)$ 可知，
     $\gamma =\frac{yf(x)}{\Vert \omega \Vert }=\frac{\hat{\gamma }}{\Vert \omega \Vert }$

几何间隔就是函数间隔除以||w||

二、最大化分类间隔

这里要解释 $margin=min\frac{1}{2}\Vert \omega {\Vert }^2$ 是怎么来的。

第一种视角：

根据上面的几何间隔公式，求解能使间隔最大化的参数w和b，即求解以下优化函数：
${\max }_{w,b}\gamma =max\left\{\frac{y_i(w^T{x}_i+b)}{\Vert w\Vert }|i=1,2,...,n\right\}$
最大分类间隔的目标函数写成：
   $\{\begin{array}{rl}& \underset{w,b}{\max }\frac{y_0(w^T{x}_0+b)}{\Vert w\Vert }\\ & s.t.y_i(w^T{x}_i+b)\ge y_0(w^T{x}_0+b),i=1,2,...,N\end{array}$

我们令$\hat{\mathbf{w}}=\mathbf{w}/{\mathbf{y}}_0({\mathbf{w}}^{\mathbf{T}}{\mathbf{x}}_0+\mathbf{b}),\hat{\mathbf{b}}=\mathbf{b}/{\mathbf{y}}_0({\mathbf{w}}^{\mathbf{T}}{\mathbf{x}}_0+\mathbf{b})$ ;
则优化函数可写成：
   $1/\Vert \hat{w}\Vert s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,N$
再用w替换 $\hat{\omega }$，并且利用 ${\max }_{w}1/\Vert w\Vert and{\max }_{w}1/\Vert w{\Vert }^2$ 等价的原理，可以得到以下下等价的优化问题：
   $\{\begin{array}{rl}& \underset{w,b}{\max }\frac{1}{\Vert w{\Vert }^2}\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1,2,...,N\end{array}$

第二种视角：

对一个数据点进行分类，当这个点和超平面之间的间隔越大的时候，分类正确的把握越大。对于一个包含n个点的数据集，我们可以很自然地定义它的间隔为所有这n个点的间隔中最小的那个。
要正确划分训练数据集{x1,x2,…xn}，满足y=1时，所有点的间隔 $\gamma >=d_{min}$，y=-1时，所有点的间隔 $\gamma <=d_{min}$ ，写成下面的公式：

   $\{\begin{array}{ll}({\mathbf{\omega }}^T{\mathbf{x}}_i+b)/||\mathbf{\omega }||\ge d_{min}& \forall y_i=1\\ ({\mathbf{\omega }}^T{\mathbf{x}}_i+b)/||\mathbf{\omega }||\le -d_{min}& \forall y_i=-1\end{array}$

两边先除以d, 然后w和b都成比例缩放，令 ${\omega }^{\prime }=\frac{\omega }{d_{min}||\omega ||},b^{\prime }=\frac{b}{d_{min}||\omega ||}$ 得到：

   $\{\begin{array}{ll}({{\mathbf{\omega }}^{\prime }}^T{\mathbf{x}}_{\mathbf{i}}+b^{\prime })\ge 1& \forall y_i=1\\ ({{\mathbf{\omega }}^{\prime }}^T{\mathbf{x}}_i+b^{\prime })\le -1& \forall y_i=-1\end{array}$

只有当$x_i$是决策面 ${\omega }^{T}x+b=0$ 所对应的支持向量时，等于1或-1的情况才会出现。
此时有 $y_i({\omega }^T{x}_i+b)=1$

代入之前 1.3 中的间隔公式$\gamma =\frac{y_i(w^T{x}_i+b)}{\Vert \omega \Vert }$，得到：
支持向量到超平面的距离为$\frac{1}{||\mathbf{\omega }||}$，两侧的距离加起来就是$\frac{2}{\Vert \omega \Vert }$。

我们希望距离越大越好，也就是说$\frac{1}{\Vert \omega \Vert }$越大越好，同时对于数据集中数据的分布满足$y({\omega }^{T}x+b)\ge 1$。因此，我们得到了如下的优化问题：
     $\{\begin{array}{c}\begin{array}{rl}& \max \frac{1}{\Vert \omega \Vert }\\ & s.t.y_i({\omega }^T{x}_i+b)⩾1,i=1,2,...,n\end{array}\end{array}$