[吃瓜教程]南瓜书第6章支持向量机

0.补充知识

0.1 超平面

定义： 超平面是指在𝑛维空间中，维度为 𝑛−1的子空间。它是分割空间的一个平面。
性质：
n维空间的超平面$(w^T{x}_b=0,其中w,x\in {\mathbb{R}}^n)$:

• 超平面方程不唯一
  简单理解方程不唯一，假设有如下的超平面方程：
  $$a_1{x}_1+a_2{x}_2+...a_n{x}_n+b=0$$
  将这个方程乘以一个非零常数k，得到：
  $$k(a_1{x}_1+a_2{x}_2+...a_n{x}_n+b)=0$$
  即
  $$k{a}_1{x}_1+k{a}_2{x}_2+...k{a}_n{x}_n+kb)=0$$
  此时，这两组不同的w和b就描述了同一个超平面。
• 法向量w和位移项b确定唯一一个超平面
• 法向量w垂直于超平面（缩放w，b时，若缩放倍数为负数会改变法向量方向）
• 法向量w指向的那一半空间为正空间，另一半为负空间
• 任意点x到超平面的距离公式为
  $$r=\frac{|w^{T}x+b|}{||w||}$$
  上述公式的推理：
  对于任意一点$x_0=(x_1^0,x_2^0,...,x_n^0{)}^T$,设其在超平面$w^{T}x+b=0$上的投影点为$x_1=(x_1^1,x_2^1,...,x_n^1{)}^T$,则$w^T{x}_1+b=0$,且向量$\overrightarrow{x_1{x}_0}$与法向量w平行，
  1）第一步先考虑从哪里可以得到一个距离，可以想到从向量点乘中可以得到，向量$\overrightarrow{x_1{x}_0}$的模长也就是距离，如下：
  $$|w\cdot \overrightarrow{x_1{x}_0}|=|||w||\cdot cos\pi \cdot ||\overrightarrow{x_1{x}_0}|||=||w||\cdot ||\overrightarrow{x_1{x}_0}||=||w||\cdot r$$
  其中绝对值是为了统一表示在正空间和负空间中取的点，r就表示距离了。
  2）上面的式子可以得到r，但是前面的向量的内积的绝对值还是未知的，因此考虑化简向量内积，
  $$w\cdot \overrightarrow{x_1{x}_0}$$
  $$=w_1(x_1^0-x_1^1)+w_2(x_2^0-x_2^1)+...+w_n(x_n^0-x_n^1)$$
  $$=w_1{x}_1^0+w_2{x}_2^0+...+w_n{x}_n^0-(w_1{x}_1^1+w_2{x}_2^1+...+w_n{x}_n^1)$$
  $$=w^T{x}_0-w^T{x}_1$$
  $$=w^T{x}_0+b$$
  即得到了，
  $$|w^T{x}_0+b|=||w||\cdot r$$
  $$r=\frac{|w^{T}x+b|}{||w||}$$

0.2 几何间隔

（1）对于样本点
对于给定的数据集X和超平面$w^{T}x+b=0$,定义数据集X中的任意一个样本点 ( x i , y i ) , y i ∈ { − 1 , 1 } , i = 1 , 2 , . . . , m (x_i,y_i),y_i\in \{-1,1\},i=1,2,...,m (xi​,yi​),yi​∈{−1,1},i=1,2,...,m关于超平面的几何间隔为
$${\gamma }_i=\frac{y_i(w^T{x}_i+b)}{||w||}$$
正确分类时：${\gamma }_i>0$,几何间隔此时等价于点到超平面的距离
没有正确分类时：${\gamma }_i<0$
（2）对于数据集
对于给定的数据集X和超平面$w^{T}x+b=0$,定义数据集X关于超平面的几何间隔为：数据集X中所有样本点的几何间隔最小值
$$\gamma =\underset{i=1,2,...,m}{\min }{\gamma }_i$$

1.算法原理

支持向量机找的是距离正负样本都最远的超平面，相比于感知机，其解是唯一的，且不偏不倚，泛化性能更好。

2.支持向量机

2.1 模型

给定线性可分数据集X，支持向量机模型希望求得数据集X关于超平面的几何间隔$\gamma$达到最大的那个超平面，然后再用一个sign函数包装实现分类功能
$$y=sign(w^{T}x+b)=\{\begin{array}{ll}1& ,w^{T}x+b>0\\ -1& ,w^{T}x+b<0\end{array}$$
这里的要求几何间隔达到最大直观上理解其实就是超平面正确划分了正负样本且距离正负样本都比较远，没有特别偏向哪一边，体现了支持向量机的强泛化性。

2.2策略

给定线性可分数据集X，设X中几何间隔最小的样本为$(x_{m}in,y_{m}in)$,那么支持向量机找超平面的过程可以转化为以下带约束条件的优化问题
$$max\gamma$$
$$s.t.{\gamma }_i>=\gamma ,i=1,2,...,m$$
将几何间隔的公式带入得到，
$$\underset{w,b}{\max }\frac{y_{min}(w^T{x}_{min}+b)}{||w||}$$
$$s.t.\frac{y_i(w^T{x}_i+b)}{||w||}>=\frac{y_{min}(w^T{x}_{min}+b)}{||w||},i=1,2,...,m$$
进一步化简得
$$\underset{w,b}{\max }\frac{y_{min}(w^T{x}_{min}+b)}{||w||}$$
$$s.t.y_i(w^T{x}_i+b)>=y_{min}(w^T{x}_{min}+b),i=1,2,...,m$$
为了使得上式有唯一解，添加进一步的限制，因为在一定的w和b的条件下可以使得上面式子得分子为1，因此，就假设上式中得分子为1，得到：
$$\underset{w,b}{\max }=\frac{1}{||w||}$$
$$s.t.y_i(w^T{x}_i+b)>=1,i=1,2,...,m$$
进一步变为最小化问题，得到
$$\underset{w,b}{\max }\frac{1}{2}||w|{|}^2$$
$$s.t.1-y_i(w^T{x}_i+b)<=0,i=1,2,...,m$$
该优化问题为含不等式约束的优化问题，且为凸优化问题。在这里通常用拉格朗日对偶来求解。
补充——拉格朗日对偶：
对于一般地约束优化问题（不一定是凸优化问题）：
$$minf(x)$$
$$s.t.g_i(x)<=0,i=1,2,...,m$$
$$h_i(x)=0,j=1,2,...,n$$
设上述优化问题的定义域为
，可行集为
，显然

最优值为 p ∗ = m i n { f ( x ~ ) } p*=min\{f( \widetilde x)\} p∗=min{f(x )}。由拉格朗日函数的定义可知上述优化问题的拉格朗日函数为

接下来定义上述优化问题的拉格朗日对偶函数$\Gamma (\mu ,\lambda )为L(x,\mu ,\lambda )$关于x的下确界，也即
$$\Gamma (\mu ,\lambda )=\underset{x\in D}{\inf }L(x,\mu ,\lambda )=\underset{x\in D}{\inf }(f(x)+\sum _{i=1}^m{\mu }_i{g}_i(x)+\sum _{j=1}^n{\lambda }_j{h}_j(x))$$
对偶函数的性质：

• 无论优化问题是否为凸优化问题，其对偶函数恒为凹函数
• 当$\mu$大于等于0时，$\Gamma (\mu ,\lambda )$构成了上述优化问题最优值$p^{\ast }$的下界，也即
  $$\Gamma (\mu ,\lambda )<=p\ast$$
  进一步定义在满足$\mu$大于等于0这个约束条件下求对偶函数最大值的优化问题为拉格朗日对偶问题（原优化问题为主问题）
  $$\max \Gamma (\mu ,\lambda )$$
  $$s.t.\mu >=0$$
  设该优化问题的最优值为$d^{\ast }$,显然$d^{\ast }<=p^{\ast }$，此时称为弱对偶性成立，若$d^{\ast }=p^{\ast }$,则称为强对偶性成立。
  支持向量机满足Slater条件（若主问题是凸优化问题，且可行集中存在一点能使得所有不等式约束的不等号成立，则强对偶成立），而该条件使得强对偶成立，就找到了一种间接求$p^{\ast }$的方法。