SVM

线性模型

一、如何从图形层面找出分类边界？

我们画出一条分类边界，然后将边界向两侧平移接触到一个或同时接触到多个分类点$(支持向量supportvector)$ 为止，此时两条平行线之间的距离称作间隔$margin$，然后我们所要找的边界即为使间隔最大的那两条边界的中线。

二、何为线性可分？

一个训练集$\{(x_i,y_i){\}}_{i=1-N}$线性可分是指：
$$\begin{array}{c}\begin{array}{r}\exists (w,b)使：对于\forall i=1-N有：\\ 若y_i=+1,则w^T{x}_i+b\ge 0\\ 若y_i=-1,则w^T{x}_i+b<0\\ 即y_i(w^T{x}_i+b)\ge 0\end{array}\end{array}$$

三、求线性可分数据的划分超平面$(hyperplane)w^{T}x+b=0$如何转化为如下凸优化问题？如何从图形形象层面转化为数学语言描述的？

(凸优化问题，二次规划问题(凸优化的一种))
$$\begin{array}{c}\begin{array}{rl}& \underset{w,b}{\min }\frac{1}{2}||w|{|}^2\\ & s.t.y_i(w^T{x}_i+b)\ge 1,i=1-N.\end{array}\end{array}$$

事实1：$w^{T}x+b=0与a{w}^{T}x+ab=0,a\in R^{+}$ 是同一个平面。即若$(w,b)$满足公式$(1)$,那么$(aw,ab)$也满足公式$(1)$。
事实2：空间一点$x$到超平面$(w,b)$的距离为：$d=\frac{|w^{T}x+b|}{||w||}$

我们可以用a去缩放$(w,b)->(aw,ab)$，最终使在所有支持向量$x_0$上有$|w^T{x}_0+b|=1$，此时支持向量$x_0$与平面的距离$d=\frac{1}{||w||}$

改变$a$，划分超平面不变，但$w和b$有所改变，假如原先$|w^T{x}_0+b|=\beta$，那么此处只需令$a=1/\beta$即可实现$|w^T{x}_0+b|=1$

所以要想让间隔$\frac{2}{||w||}$更大，只需$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2$；此外，支持向量以外的点到平面的距离必须要$>1$,而且要满足训练样本线性可分(公式(1)),故需满足条件$y_i(w^T{x}_i+b)\ge 1$

首先$y_i(w^T{x}_i+b)\ge 0$，其次由于$|w^T{x}_i+b|\ge 1$，故$y_i(w^T{x}_i+b)\ge 1$

批注：

1. $s.t.$的右端的1可以是其他数值，无非是变一下$a$。
2. 二次规划问题：目标函数是二次项 && 限制条件是一次项
   二次规划问题要么无解(问题不线性可分)，要么只有一个极值，即局部极值即最值。

非线性模型

对于线性不可分的训练集，优化问题如下：

引入松弛变量${\xi }_i$

先引入松弛变量${\xi }_i$，此时可解决训练集非线性可分(决策边界
仍然是线性的，但找不到一条直线分开所有训练集)的情况。

$$\begin{array}{c}\begin{array}{rl}& \underset{w,b,\xi }{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i\\ s.t.& y_i(w^T{x}_i+b)\ge 1-{\xi }_i,i=1-N.\\ & {\xi }_i\ge 0,i=1-N\end{array}\end{array}$$

1. 约束条件增加N个，${\xi }_i$称作松弛变量
2. 每个样本点对应一个${\xi }_i$；${\xi }_i>1$：分类错误；${\xi }_i=1$：在分类超平面上；${\xi }_i\in (0,1)$：分类正确但确信度不是最大；${\xi }_i\le 0$：点在间隔边界上或之外；
3. 目标函数中需要控制${\xi }_i$都要比较小
4. $C{\sum }_{i=1}^N{\xi }_i$ 被称作正则项 $regulationterm$
5. $C$是事先设定的参数，称作惩罚参数，$C>0$

引入高维映射函数$\varphi (x)$

进一步引入高维映射$\varphi (x)$
$$x->\varphi (x)低维->高维$$

那么优化问题变成：
$$\begin{array}{c}\begin{array}{rl}& \underset{w,b,\xi }{\min }\frac{1}{2}||w|{|}^2+C\sum _{i=1}^N{\xi }_i\\ s.t.& y_i(w^T\varphi (x_i)+b)\ge 1-{\xi }_i,i=1-N.\\ & {\xi }_i\ge 0,i=1-N\end{array}\end{array}$$

一、那么如何选取 / 求出$\varphi (x)$? 不用求!

首先$\varphi (x)$常是无限维，伴随着，你需要求出无限维的$w$，那么该优化问题无法求解。
那么精髓来了，利用一个有限维的手段做出了无限维的$\varphi (x)$:
我们可以不知道无限维映射$\varphi (x)$的显示表达，我们只要知道一个核函数$KernelFunction$:
$$K(x_1,x_2)=\varphi (x_1{)}^T\varphi (x_2)$$

那么上述优化问题仍然可解。

注：核函数的自变量$x_1,x_2$是低维向量，核函数的结果是两个无限维向量$\varphi (x_1),\varphi (x_2)$的内积(一个数)。

常用核函数：
$$高斯核K(x_1,x_2)=exp(-\frac{||x_1-x_2|{|}^2}{2{\sigma }^2})=\varphi (x_1{)}^T\varphi (x_2)$$

$$多项式核K(x_1,x_2)=(x_1^T{x}_2+1{)}^d=\varphi (x_1{)}^T\varphi (x_2)$$

根据证明，高斯核可拆分为无限维度的$\varphi (x_1{)}^T\varphi (x_2)$，我们只需要知道$K$，并不需要知道$\varphi (x)$的具体形式。多项式h核可拆分为有限维度吧。

$K(x_1,x_2)$能写成$\varphi (x_1{)}^T\varphi (x_2)$的充要条件($Merce{s}^{\prime }stheorem$)：
① $K(x_1,x_2)=K(x_2,x_1)(交换性)$
②$\forall c_i,x_i(i=1-N),有:\sum _{i=1}^N\sum _{j=1}^N{c}_i{c}_{j}K(x_i,x_j)\ge 0(半正定性)$

二、如何求优化问题(式($4$))(利用核函数$K$)?

1、先根据对偶理论中原问题$(primeproblem)$形式，转化一下优化问题(4):
$$\begin{array}{c}\begin{array}{rl}& \underset{w,b,\xi }{\min }\frac{1}{2}||w|{|}^2-C\sum _{i=1}^N{\xi }_i\\ s.t.& 1+{\xi }_i-y_i{w}^T\varphi (x_i)-y_{i}b\le 0,i=1-N.\\ & {\xi }_i\le 0,i=1-N\end{array}\end{array}$$

P问题：
$$\begin{gathered} \underset{x\in {\mathbf{R}}^n}{\min }f(x) \\ s.t.c_i(x)⩽0,i=1,2,\cdots ,k \\ {h}_j(x)=0,j=1,2,\cdots ,l \end{gathered}$$

2、将原问题转为对偶问题$(dualproblem)$
$$\begin{array}{c}\begin{array}{rl}& \underset{\alpha ,\beta }{\max }\theta (\alpha ,\beta )=\underset{\alpha ,\beta }{\max }\underset{w,b,{\xi }_i}{\min }\frac{1}{2}\Vert w{\Vert }^2-C\sum _{i=1}^N{\xi }_i+\sum _{i=1}^N{\beta }_i{\xi }_i+\sum _{i=1}^N{\alpha }_i\left(1+{\xi }_i-y_i{w}^T\varphi \left(x_i\right)-y_{i}b\right).\\ & \text{ s.t. }\{\begin{array}{l}{\alpha }_i⩾0,i=1\sim N\\ {\beta }_i⩾0,i=1\sim N\end{array}\end{array}\end{array}$$

D问题：
$$\begin{array}{c}\underset{\alpha ,\beta }{\max }{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta }{\max }\underset{x}{\min }L(x,\alpha ,\beta )\\ \text{ s.t. }{\alpha }_i⩾0,i=1,2,\cdots ,k\end{array}$$

那么欲求对偶问题的解，先求$\underset{w,b,{\xi }_i}{\min }L(w,b,{\xi }_i,\alpha ,\beta )$，那么需要求偏导：
$$\begin{array}{c}\begin{array}{rl}\frac{\partial L}{\partial w}& =w-\sum _{i=1}^N{\alpha }_i{y}_i\varphi (x_i)=0\\ \frac{\partial L}{\partial b}& =-\sum _{i=1}^N{\alpha }_i{y}_i=0\\ \frac{\partial L}{\partial {\xi }_i}& =-C+{\beta }_i+{\alpha }_i=0\end{array}\end{array}$$

$$\begin{gathered} 所以w=\sum _{i=1}^N{\alpha }_i{y}_i\varphi (x_i) \\ {\alpha }_i+{\beta }_i=C \end{gathered}$$

将上述代入式子$(6)$:

即$\theta (\alpha ,\beta )=\min L=\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)$

3、将对偶问题(6)变成：
$$\begin{gathered} \underset{\alpha }{\max }\theta (\alpha )=\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j \\ s.t.0\le {\alpha }_i\le C \\ \sum _{i=1}^N{\alpha }_i{y}_i=0 \end{gathered}$$

第一个约束条件是${\alpha }_i\ge 0,{\beta }_i\ge 0,{\alpha }_i+{\beta }_i=C合并而来$
第二个约束来自于上述推导过程
此优化问题可通过$SMO$算法求解出$\alpha$

4、该求参数w和b了，还是说可以不用求直接做出决策？
此时，我们需要求$w和b$，已知$w=\sum _{i=1}^N{\alpha }_i{y}_i\varphi (x_i)$，那么我们还是需要求$\varphi (x)$，对吗？不对。
因为我们决策时，类别$y$：
$$y=sign(w^T\varphi (x)+b)=sign(\sum _{i=1}^N{\alpha }_i{y}_{i}K(x_i,x)+b)$$

所以无需通过$\varphi (x)$求$w$，利用$K(x_i,x)$即可，然后求出$b$即可。

5、那么如何求$b$？
根据$KKT$的对偶互补条件：$$\forall i=1-K,要么{\alpha }_i^{\ast }=0,要么c_i(x^{\ast })=0$$
取一个$0<{\alpha }_i<C$，根据式子(5)，两个约束条件变为等式，据此得到：
$$b=\frac{1-y_i\sum _{j=1}^N{\alpha }_i{y}_{i}K(x_i,x_j)}{y_i}$$

三、$SVM$算法整体流程

1、训练流程
输入N个训练样本$(x_i,y_i)$，解优化问题，解得$\alpha$:
$$\begin{gathered} \underset{\alpha }{\max }\theta (\alpha )=\sum _{i=1}^N{\alpha }_i-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j \\ s.t.0\le {\alpha }_i\le C \\ \sum _{i=1}^N{\alpha }_i{y}_i=0 \end{gathered}$$

取一个$0<{\alpha }_i<C$，计算$b$：
$$b=\frac{1-y_i\sum _{j=1}^N{\alpha }_i{y}_{i}K(x_i,x_j)}{y_i}$$

注：现实中取所有满足${\alpha }_i\in (0,C)$的${\alpha }_i$，求出$b$的平均值

2、测试流程
输入测试样本$x$
$$y=sign(w^T\varphi (x)+b)=sign(\sum _{i=1}^N{\alpha }_i{y}_{i}K(x_i,x)+b)$$

完结撒花。