统计学习方法学习笔记-07-支持向量机03

包含对三种支持向量机的介绍，包括线性可分支持向量机，线性支持向量机和非线性支持向量机，包含核函数和一种快速学习算法-序列最小最优化算法SMO。

非线性支持向量机与核函数

核技巧

非线性分类问题

给定一个训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$，其中$x_i$属于输入空间， x i ∈ X = R n , y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , ⋯   , N x_i \in \mathcal{X} = R^n,y_i \in \mathcal{Y} = \{-1,+1\},i = 1,2,\cdots,N xi​∈X=Rn,yi​∈Y={−1,+1},i=1,2,⋯,N，如果可以用$R^n$中的一个超曲面将正负例正确分开，则称这个问题为非线性可分问题
用线性分类方法求解非线性问题分为两步，首先使用一个变换将原空间的数据映射到新空间，然后在新空间里用线性分类方法从训练数据中学习分类模型，基本想法就是通过一个非线性变换将输入空间对应于一个特征空间

核函数的定义

设$\mathcal{X}$是输入空间(欧式空间$R^n$的子集或离散集合)，又设$\mathcal{H}$为特征空间(希尔伯特空间)，如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射：
$$\varphi (x):\mathcal{X}\to \mathcal{H}$$
使得对所有$x,z\in \mathcal{X}$，函数$K(x,z)$满足条件:
$$K(x,z)=\varphi (x)\cdot \varphi (z)$$
则称$K(x,z)$为核函数，$\varphi (x)$为隐射函数，式中$\varphi (x)\cdot \varphi (z)$是两者的内积，核技巧的想法是，在学习与预测中只定义核函数$K(x,z)$，而不显示地定义隐射函数$\varphi$，可以看到，对于给定的核$K(x,z)$，特征空间$\mathcal{H}$和隐射函数$\varphi$的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射

核技巧在支持向量机中的应用

在线性支持向量机的对偶问题中，无论是目标函数还是决策函数都只涉及输入实例与实例之间的内积
$$\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\cdot x_j)-\sum _{i=1}^N{\alpha }_i$$
在对偶问题的目标函数中的内积$x_i\cdot x_j$可以用核函数$K(x,z)=\varphi (x)\cdot \varphi (z)$来代替，此时对偶问题的目标函数为：
$$W(\alpha )=\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^N{\alpha }_i$$
同样，分类决策中的内积也可以用核函数代替：
$$f(x)=sign\left(\sum _{i=1}^{N_s}{\alpha }_i^{\ast }{y}_{i}K(x_i,x)+b^{\ast }\right)$$
这等价于经过映射函数$\varphi$将原来的输入空间变换到一个新的特征空间，将输入空间的内积$x_i\cdot x_j$变换为特征空间中的内积$\varphi (x_i)\cdot \varphi (x_j)$

正定核

目的：函数$K(x,z)$成为核函数的条件

正定核的充要条件

设$K:\mathcal{X}\times \mathcal{X}\to R$是对称函数，则$K(x,z)$为正定核的充要条件是对任意$x_i\in \mathcal{X},i=1,2,\cdots ,m,K(x,z)$对应的Gram矩阵：
$$K=[K(x_i,x_j){]}_{m\times m}$$
是半正定矩阵

正定核的等价定义

设$\mathcal{X}\subset R^n,K(x,z)$是定义在$\mathcal{X}\times \mathcal{X}$上的对称函数，如果对任意的$x_1,x_2,\cdots ,x_m\in \mathcal{X},K(x,z)$关于$x_1,x_2,\cdots ,x_m$的Gram矩阵$K=[K(x_i,x_j){]}_{m\times m}$是半正定矩阵，则称$K(x,z)$是正定核。

常用核函数

多项式核函数polynomial kernel function

此时对应的支持向量机是一个$p$次多项式分类器
$$K(x,z)=(x\cdot z+1{)}^p$$

高斯核函数gaussain kernel function

此时对应的支持向量机是高斯径向基函数分类器
$$K(x,z)=exp\left(-\frac{||x-z|{|}^2}{2{\sigma }^2}\right)$$

非线性支持向量分类机

非线性支持向量机学习算法

输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$，其中 x i ∈ X = R n , y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , ⋯   , N x_i \in \mathcal{X} = R^n,y_i \in \mathcal{Y} = \{+1,-1\},i = 1,2,\cdots,N xi​∈X=Rn,yi​∈Y={+1,−1},i=1,2,⋯,N
输出：分类决策函数

• 选择适当的核函数$K(x,z)$和惩罚参数$C>0$，构造并求解约束最优化问题求得最优解${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },\cdots ,{\alpha }_N^{\ast }{)}^T$
  m i n α   1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i s . t .   ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , ⋯   , N
  minα⁡ 12∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαis.t. ∑i=1Nαiyi=00≤αi≤C,i=1,2,⋯,N" role="presentation" style="position: relative;">minα s.t. 12∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαi∑i=1Nαiyi=00≤αi≤C,i=1,2,⋯,N$$\begin{array}{rl}\underset{\alpha }{min}& \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\sum _{i=1}^N{\alpha }_i\\ s.t.& \sum _{i=1}^N{\alpha }_i{y}_i=0\\ & 0\le {\alpha }_i\le C,i=1,2,\cdots ,N\end{array}$$
  αmin​ s.t. ​21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)−i=1∑N​αi​i=1∑N​αi​yi​=00≤αi​≤C,i=1,2,⋯,N​
• 选择${\alpha }^{\ast }$的一个分量$0<{\alpha }_j^{\ast }<C$，计算：
  $$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K(x_i,x_j)$$
• 求得决策函数：
  $$f(x)=sign\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K(x,x_i)+b^{\ast }\right)$$

序列最小最优化算法(SMO算法)

sequential minimal optimization
目的：当训练样本容量很大的时候，快速实现支持向量机学习
SMO算法要解的问题如下：
m i n α   1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i , x j ) − ∑ i = 1 N α i s . t .   ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , ⋯   , N

αmin​ s.t. ​21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)−i=1∑N​αi​i=1∑N​αi​yi​=00≤αi​≤C,i=1,2,⋯,N​
变量是${\alpha }_i$，算法是一种启发式算法，
基本思路如下，如果所有变量的解都满足此最优化问题的KKT条件，那么此时最优化问题的解就得到了，因为KKT条件是最优化问题的充分必要条件，否则选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题，这个二次规划问题关于这两个变量的解应该更加接近原始二次规划问题的解，因为这会使原始二次规划问题的目标函数值变小，
重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度，
子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定，假设${\alpha }_1,{\alpha }_2$为两个变量，${\alpha }_3,{\alpha }_4,\cdots ,{\alpha }_N$固定，那么由约束不等式${\sum }_{i=1}^N{\alpha }_i{y}_i=0$和$y_1^2=1$可知：
$${\alpha }_1=-y_1\sum _{i=2}^N{\alpha }_i{y}_i$$
整个SMO算法包含两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法

两个变量二次规划的求解方法

不失一般性，假设${\alpha }_1,{\alpha }_2$为两个变量，${\alpha }_3,{\alpha }_4,\cdots ,{\alpha }_N$固定，省略不含${\alpha }_1,{\alpha }_2$的常数项，于是最优化问题可以写为：
m i n α 1 , α 2   W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 N y i α i K i 1 + y 2 α 2 ∑ i = 3 N y i α i K i 2 s . t .   α 1 y 1 + α 2 y 2 = − ∑ i = 3 N y i α i = ζ 0 ≤ α i ≤ C , i = 1 , 2

α1​,α2​min​ s.t. ​W(α1​,α2​)=21​K11​α12​+21​K22​α22​+y1​y2​K12​α1​α2​−(α1​+α2​)+y1​α1​i=3∑N​yi​αi​Ki1​+y2​α2​i=3∑N​yi​αi​Ki2​α1​y1​+α2​y2​=−i=3∑N​yi​αi​=ζ0≤αi​≤C,i=1,2​
约束可以用二维空间中的图形表示：

不等式约束使得$({\alpha }_1,{\alpha }_2)$在盒子$[0,C]\times [0,C]$中，等式约束使得$({\alpha }_1,{\alpha }_2)$在平行于盒子对角线的直线上，因此要求的是目标函数在一条平行于对角线的线段上的最优值，这使得两个变量的最优化问题成为实质上的单变量的最优化问题，此时考虑${\alpha }_2$的最优化问题
最优值${\alpha }_2^{new}$的取值范围需要满足条件：
$$L\le {\alpha }_2^{new}\le H$$
其中$L,H$是${\alpha }_2^{new}$所在的对角线段端点的界：

• $y_1\ne y_2$
  $$L=max(0,{\alpha }_2^{old}-{\alpha }_1^{old}),H=min(C,C+{\alpha }_2^{old}-{\alpha }_1^{old})$$
• $y_1=y_2$
  $$L=max(0,{\alpha }_2^{old}+{\alpha }_1^{old}-C),H=min(C,{\alpha }_2^{old}+{\alpha }_1^{old})$$

假设问题的初始可行解为${\alpha }_1^{old},{\alpha }_2^{old}$，最优解为${\alpha }_1^{new},{\alpha }_2^{new}$，并且假设沿着约束方向未经剪辑时${\alpha }_2$的最优解为${\alpha }_2^{new,unc}$
先记:
$$\begin{gathered} g(x)=\sum _{i=1}^N{\alpha }_i{y}_{i}K(x_i,x)+b \\ {E}_i=g(x_i)-y_i=\left(\sum _{i=1}^N{\alpha }_i{y}_{i}K(x_i,x)+b\right)-y_i \end{gathered}$$
最优化问题沿着约束方向未经剪辑时的解为：
$${\alpha }_2^{new,unc}={\alpha }_2^{old}+\frac{y_2(E_1-E_2)}{\eta }$$
其中：
$$\eta =K_{11}+K_{22}-2K_{12}=||\Phi (x_1)-\Phi (x_2)|{|}^2$$
经剪辑后${\alpha }_2$的解是：
α 2 n e w = { H , α 2 n e w , u n c > H α 2 n e w , u n c , L ≤ α 2 n e w , u n c ≤ H L , α 2 n e w , u n c < L \alpha_2^{new} =

α2new​=⎩ ⎨ ⎧​H,α2new,unc​,L,​α2new,unc​>HL≤α2new,unc​≤Hα2new,unc​<L​
由${\alpha }_2^{new}$求得${\alpha }_1^{new}$是：
$${\alpha }_1^{new}={\alpha }_1^{old}+y_1{y}_2({\alpha }_2^{old}-{\alpha }_2^{new})$$

变量的选择方法

SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件。

• 第1个变量的选择
  选择第一个变量的过程为外层循环，在训练样本中选取违反KKT条件最严重的点，检查样本点$(x_i,y_i)$满足KKT条件的方法：
  α i = 0 ⇔ y i g ( x i ) ≥ 1 0 < α i < C ⇔ y i g ( x i ) = 1 α i = C ⇔ y i g ( x i ) ≤ 1
  αi=0⇔yig(xi)≥10<αi<C⇔yig(xi)=1αi=C⇔yig(xi)≤1" role="presentation" style="position: relative;">αi=00<αi<Cαi=C⇔yig(xi)≥1⇔yig(xi)=1⇔yig(xi)≤1$$\begin{array}{rl}{\alpha }_i=0& \iff y_{i}g(x_i)\ge 1\\ 0<{\alpha }_i<C& \iff y_{i}g(x_i)=1\\ {\alpha }_i=C& \iff y_{i}g(x_i)\le 1\end{array}$$
  αi​=00<αi​<Cαi​=C​⇔yi​g(xi​)≥1⇔yi​g(xi​)=1⇔yi​g(xi​)≤1​
  其中$g(x_i)={\sum }_{j=1}^N{\alpha }_j{y}_{j}K(x_i,x_j)+b$，在检验过程中，首先遍历所有满足条件$0<{\alpha }_i<C$的样本点，即在间隔边界上的支持向量点，检查是否满足KKT条件，然后检查整个训练数据集
• 第2个变量的选择
  在找到第一个变量${\alpha }_1$的基础上寻找${\alpha }_2$，已知${\alpha }_2^{new}$依赖于$|E_1-E_2|$，而且${\alpha }_1$确定，所以$E_1$确定，如果$E_1$是正的，选择最小的$E_i$作为$E_2$，否则选择最大的$E_i$作为$E_2$，如果选择的${\alpha }_2$不能使目标函数有足够的下降，那么采用启发式规则继续选择${\alpha }_2$试用，如果还是找不到合适的${\alpha }_2$，就重新找另外的${\alpha }_1$
• 计算阈值$b$和差值$E_i$

SMO算法

输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),\cdots ,(x_N,y_N)\}$，其中 x i ∈ X = R n , y i ∈ Y = { + 1 , − 1 } , i = 1 , 2 , ⋯   , N x_i \in \mathcal{X} = R^n,y_i \in \mathcal{Y} = \{+1,-1\},i = 1,2,\cdots,N xi​∈X=Rn,yi​∈Y={+1,−1},i=1,2,⋯,N，精度$\epsilon$
输出：近似解$\hat{\alpha }$

• 取初值${\alpha }^{(0)}=0,k=0$;
• 选取优化变量${\alpha }_1^{(k)},{\alpha }_2^{(k)}$，解析求解两个变量的最优化问题，过程见上上小结，求解得到最优解${\alpha }_1^{(k+1)},{\alpha }_2^{(k+1)}$，更新$\alpha$为${\alpha }^{(k+1)}$；
• 若在精度$\epsilon$范围内满足停机条件
  ∑ i = 1 N α i y i = 0 , 0 ≤ α i ≤ C , i = 1 , 2 , ⋯   , N y i ⋅ g ( x i ) { ≥ 1 , { x i ∣ α i = 0 } = 1 , { x i ∣ 0 < α i < C } ≤ 1 , { x i ∣ α i = C } \sum_{i = 1}^N\alpha_iy_i = 0,0 \leq \alpha_i \leq C,i = 1,2,\cdots,N \\ y_i \cdot g(x_i)
  {≥1,{xi|αi=0}=1,{xi|0<αi<C}≤1,{xi|αi=C}" role="presentation" style="position: relative;">⎧⎩⎨≥1,=1,≤1,{xi|αi=0}{xi|0<αi<C}{xi|αi=C}$$\{\begin{array}{ll}\ge 1,& \{x_i|{\alpha }_i=0\}\\ =1,& \{x_i|0<{\alpha }_i<C\}\\ \le 1,& \{x_i|{\alpha }_i=C\}\end{array}$$
  i=1∑N​αi​yi​=0,0≤αi​≤C,i=1,2,⋯,Nyi​⋅g(xi​)⎩ ⎨ ⎧​≥1,=1,≤1,​{xi​∣αi​=0}{xi​∣0<αi​<C}{xi​∣αi​=C}​
  其中$g(x_i)={\sum }_{j=1}^N{\alpha }_j{y}_{j}K(x_i,x_j)+b$
  则转第四步，否则令$k=k+1$，转到第二步
• 取$\hat{\alpha }={\alpha }^{(k+1)}$