《神经网络与机器学习12章支持向量机》

神经网络与机器学习

第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，令其垂直投影到超平面上的对应点为 x₀ ，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\]

因此取等号，必有$w_1^*=\pm 1(w_2^*)=w_2^*$，负号不是解，所以w解唯一。因此，两个最优解$(w,b_1^*)$，$(w,b_2^*)$,还有证明偏置相等，设$x_1^{\’}$,$x_2^{\’}$是集合$\{x_i|y_i=1\}$中分别满足$(w,b_1^*)$，$(w,b_2^*)$不等式成立两个点，而$x_1^{\’\’}$,$x_2^{\’\’}$是集合$\{x_i|y_i=-1\}$的两个点，那么有

\[(w^{\mathrm{T}}x_1^{\’}+b_1^*)-1=0\\
(w^{\mathrm{T}}x_2^{\’}+b_2^*)-1=0\]

\[-(w^{\mathrm{T}}x_1^{\’\’}+b_1^*)-1=0\\
-(w^{\mathrm{T}}x_2^{\’\’}+b_2^*)-1=0\]

因此得到

\[b_1^*=-\frac{1}{2}(w^{\mathrm{T}}x_1^{\’}+w^{\mathrm{T}}x_1^{\’\’})\\
b_2^*=-\frac{1}{2}(w^{\mathrm{T}}x_2^{\’}+w^{\mathrm{T}}x_2^{\’\’})\]

因此得到

\[b_1^*-b_2^*=-\frac{1}{2}[w^{\mathrm{T}}(x_1^{\’}-x_2^{\’})+w^{\mathrm{T}}(x_1^{\’\’}-x_2^{\’\’})]\]

又因为

\[(w^{\mathrm{T}}x_2^{\’}+b_1^*)\geq 1=w^{\mathrm{T}}x_1^{\’}+b_1^*\\
(w^{\mathrm{T}}x_1^{\’}+b_1^*)\geq 1=w^{\mathrm{T}}x_2^{\’}+b_1^*\]

因此$w^{\mathrm{T}}(x_1^{\’}-x_2^{\’})=0$，同理$w^{\mathrm{T}}(x_1^{\’\’}-x_2^{\’\’})=0$，所以$b_1^*=b_2^*$。

支持向量和间隔边界：

支持向量：训练数据集中样本点与分离超平面最近的样本点是支持向量，而支持向量是使得约束条件等号成立

\[y_i(w^{\mathrm{T}}x_i+b)-1=0\]

上图H1和H2两个平面上的点就是支持向量，二者距离称为间隔，二者平行，所以间隔大小等于$\frac{2}{||w||}$。

支持向量非常少，因此支持向量机由少数重要的训练样本组成的。改变支持向量以外的点不改变解，但是增减支持向量将会改变。

§12.3 线性支持向量机学习的对偶法

例子：如图所示的训练数据集，正样本点,$\{[3\quad 3]^{\mathrm{T}}|y_1=1\}$，$\{[4\quad 3]^{\mathrm{T}}|y_2=1\}$,负样本点$\{[1\quad 1]^{\mathrm{T}}|y_3=-1\}$。那么构成了如下优化问题

\[\underset{w,b}{min}\quad \frac{1}{2}||w||^2\\
s.t. \quad 3w_1+3w_2+b-1\geq 0\\
4w_1+3w_2+b-1\geq 0\\
-w_1-w_2-b-1\geq 0\]

求解得到超平面

\[\frac{1}{2}w_1+\frac{1}{2}w_2-2=0\]

下面引用对偶算法，一是对偶算法有时候比上面原优化问题好解决，二是可以自然引入核方法，推广到非线性分类问题。

对偶算法求

\[\underset{w,b}{min}\quad \frac{1}{2}||w||^2\\
s.t.\quad y_i(w^{\mathrm{T}}x_i+b)-1\geq 0,x=1,2,\cdots,N\]

首先构建Lagrange函数，对于每一个约束都引入一个Lagrange乘子

\[L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^N\alpha_iy_i(w^{\mathrm{T}}x_i+b)+\sum_{i=1}^N\alpha_i\]

根据对偶性，原始问题的对偶问题是

\[\underset{\alpha}{max}\underset{w,b}{min}\quad L(w,b,\alpha)\]

因此首先求最小

\[\bigtriangledown_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0\\
\bigtriangledown_bL(w,b,\alpha)=-\sum_{i=1}^N\alpha_iy_i=0\]

将$w=\sum_{i=1}^N\alpha_iy_ix_i$，且由于$\sum_{i=1}^N\alpha_iy_i=0$，得到

\[minL(w,b,\alpha)=\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_iy_i\left ( \sum_{i=1}^{N}\alpha_jy_jx_j\cdot x_i+b\right )+\sum_{i=1}^{N}\alpha_i\\
=-\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\]

其次对于Lagrange乘子求最大

\[\underset{\alpha}{max}-\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_j=0\\
\quad \quad \quad \alpha_i\geq 0\]

也等价于对偶问题

\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{i=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_j=0\\
\quad \quad \quad \alpha_i\geq 0\]

定理：设$\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_i)$为上面对偶问题的解，则存在下标

\[\alpha_j> 0\]

求得原始最优化问题的解，KKT条件

\[\bigtriangledown_wL(w,b,\alpha)=w^*-\sum_{i=1}^{N}\alpha_i^*y_ix_i=0\\
\bigtriangledown_bL(w,b,\alpha)=-\sum_{i=1}^{N}\alpha_i^*y_i=0\\
\alpha_i^*(y_i(w^{\mathrm{T}}x_i+b)-1)=0\\
y_i(w^{\mathrm{T}}x_i+b)-1\geq 0\\
\alpha_i^* >0\]

至少存在一个$\alpha_j >0$，对于此下标

\[y_j(w^*x_j+b^*)-1= 0\]

将$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$代入得到

\[y_j(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j+b^*)-1=0\\
y_jb^*=1-y_j(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\\
b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\]

因此超平面为

\[w^*x+b^*=0\\
\sum_{i=1}^{N}\alpha_i^*y_i(x\cdot x_i)+b^*=0\]

而且支持向量一定在间隔边界上，所以满足

\[w^*x_i+b^*\mp 1=0\\\]

例子：正样本点$\{[3\quad 3]^{\mathrm{T}}|y_1=1\}$，$\{[4\quad 3]^{\mathrm{T}}|y_2=1\}$，负样本点$\{[1\quad 1]^{\mathrm{T}}|y_3=-1\}$。

解：根据数据，得到

\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\
=\frac{1}{2}[18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+21\alpha_1\alpha_2-6\alpha_1\alpha_3-7\alpha_2\alpha_3]-\alpha_1-\alpha_2-\alpha_3\\
s.t. \quad \alpha_1+\alpha_2-\alpha_3=0\\
\alpha_i\geq 0\]

解得$\alpha_1+\alpha_2=\alpha_3$，代入

\[min\quad 4\alpha_1^2+6.5\alpha_2^2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2\]

得到解

\[(\alpha_1,\alpha_2)=(1.5,-1)\]

不满足$\alpha_i\geq 0$约束条件，因此寻找边界点。发现解

\[(\alpha_1,\alpha_2,\alpha_3)=(0.25,0,0.25)\]

因此发现

\[\{\begin{bmatrix}
3 & 3
\end{bmatrix}^{\mathrm{T}}|y_1=1\},\{\begin{bmatrix}
1 & 1
\end{bmatrix}^{\mathrm{T}}|y_3=-1\}\]

是支持向量。

\[w^*=\sum_{i=1}^{N}\alpha_i^*y_ix_i=\frac{1}{4}(\begin{bmatrix}
3\\3
\end{bmatrix}-\begin{bmatrix}
1\\ 1
\end{bmatrix})=\begin{bmatrix}
\frac{1}{2}\\
\frac{1}{2}
\end{bmatrix}\\
b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)=-2\]

超平面是

\[\mathbf{w}^*x+b^*=0\\
\begin{bmatrix}
\frac{1}{2}& \frac{1}{2}
\end{bmatrix}\begin{bmatrix}
x_1\\
x_2
\end{bmatrix}-2=0\]

§12.4 软间隔最大化

上面的学习算法对应线性不可分问题是不适用的，约束不在成立。这里利用软间隔最大化，则可以解决线性不可分问题。

给定特征空间上的训练数据集

\[\left \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\right \}\]

$x_i$是实向量，而$y_i$是标签，取值{+1，-1}。数据集中总是有些特异点（outlier），将这些造成线性不可分的问题的特异点去除，则剩下的大部分点是线性可分的。

第一种黄蓝各自都有一个数据异常

第二种改变了分离平面的异常点

异常点造成线性不可分，因为异常点不满足函数间隔大于等于1的约束条，为了解决不可分问题，对训练集里面的每个样本$(x_i,y_i)$引入了一个松弛变量$\xi_i\geq 0$，使函数间隔加上松弛变量大于等于1，约束条件变成

\[y_j(w^*x_j+b^*)\geq 1-\xi_i\]

对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。松弛变量加入有成本的，每一个松弛变量$\xi_i\geq 0$ 对应了一个代价$\xi_i$，这样优化目标函数从$\frac{1}{2}||w||^2$，变成了

\[\frac{1}{2}\left \| w\right \|^2+C\sum_{i=1}^{N}\xi_i\]

C>0为惩罚参数，可以理解为分类问题正则化时候的参数。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。因此目标函数即希望$\frac{1}{2}||w||^2$尽量小，间隔最大，同时使得误分类的点尽可能的少，C是协调两者关系的参数。

因此我们把下面的凸二次规划问题称为软间隔最大化：

\[\underset{w,b}{min}\frac{1}{2}\left \| w\right \|^2+C\sum_{i=1}^{N}\xi_i\\
s.t. \quad y_j(w^*x_j+b^*)\geq 1-\xi_i,i=1,2,\cdots,N\\
\quad \quad \quad \xi_i\geq 0\]

构建Lagrange函数

\[L(w,b,\xi,\alpha,u)=\frac{1}{2}\left \| w\right \|^2+C\sum_{i=1}^{N}\xi_i-\sum_{i=1}^{N}\alpha_i[y_i(w^{\mathrm{T}}x_i+b)-1+\xi_i]-\sum_{i=1}^{N}u_i\xi_i\\
\alpha_i> 0,u_i> 0\]

根据对偶性，原始问题的对偶问题是

\[\underset{\alpha}{min}\underset{w,b,\xi}{max}L(w,b,\xi,\alpha,u)\]

因此首先求最小

上面都代入$L(w,b,\xi,\alpha,u)$，因此得到

\[\underset{w,b,\xi}{min}L(w,b,\xi,\alpha,u)=-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^{N}\alpha_i\]

再对$\alpha_i$求极大，就是求下面极小

\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t.\quad \sum_{i=1}^{N}\alpha_iy_i=0\\
C-\alpha_i-u_i=0\\
\alpha_i\geq 0,u_i> 0\]

利用$C-\alpha_i=u_i$，$\alpha_i\geq 0$，$u_i> 0$可以写成

定理：若存在一个分量$0\leq \alpha_j^*\leq C$，原始问题的解为

\[w^*=\sum_{i=1}^{N}a_i^*y_ix_i\\
b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\]

证明：由KKT条件

\[\bigtriangledown_wL(w,b,\xi,\alpha,u)=w-\sum_{i=1}^{N}\alpha_iy_ix_i=0\\
\bigtriangledown_bL(w,b,\xi,\alpha,u)=-\sum_{i=1}^{N}\alpha_iy_i=0\\
\bigtriangledown_{\xi}L(w,b,\xi,\alpha,u)=C-\alpha_i-u_i=0\\
\alpha_i[y_i(w^{\mathrm{T}}x_i+b)-1+\xi_i]=0\\
u_i\xi_i=0\\
y_i(w^{\mathrm{T}}x_i+b)-1+\xi_i\geq 0\\
\alpha_i\geq 0,u_i> 0,\xi_i\geq 0\]

若存在一个分量$0\leq \alpha_j\leq C$，则

\[(C-\alpha_i)\xi_i=0\Rightarrow \xi_i=0\]

那么

\[\alpha_i[y_i(w^{\mathrm{T}}x_i+b)-1]=0\]

得到

\[y_i(w^{\mathrm{T}}x_i+b)-1=0\]

即

\[b^*=y_j-(\sum_{i=1}^{N}\alpha_i^*y_ix_i\cdot x_j)\\
w=\sum_{i=1}^{N}\alpha_iy_ix_i\]

支持向量：在线性不可分的情况下，对偶问题中对应$0\leq \alpha_j^*\leq C$的样本点$(x_i,x_j)$称为软间隔的支持向量。情况更加复杂，分割平面是实线，边界是虚线。

这些支持向量或者在边界上，或者在边界内或外

若$0\leq \alpha_j^*\leq C$，$\xi_i=0$，则正好在边界上，称为支持向量，

若$\alpha_j^*=C$，$0< \xi_i<1$, 此时分类正确，在边界之间，

若$\alpha_j^*=C$，$\xi_i=1$, 此时在超平面上

若$\alpha_j^*=C$，$\xi_i>1$, 此时位于超平面的另一侧，误分的一侧

合页损失（hinge loss）函数：

上面解释的线性支持向量机，学习策略是软间隔最大化，分离超平面是$y_i(w^{\mathrm{T}}x_i+b)=1$，学习算法是凸二次规划。

线性支持向量机另外一个解释就是最小化目标函数

\[\sum_{i=1}^{N}[y_i(w^{\mathrm{T}}x_i+b)-1]_+ +\lambda||w||^2\]

第一项是经验风险函数，又称为合页损失函数，下标+表示取正值

\[[z]_+=\left\{\begin{matrix}
z,z>0\\
0,z\leq 0
\end{matrix}\right.\]

也就是说当样本点$(x_i,y_i)$被正确分类，且函数间隔$y_i(w^{\mathrm{T}}x_i+b)>1$时，损失为0，否则损失就是$1-y_i(w^{\mathrm{T}}x_i+b)$。而第二项就是正则化项。

定理：线性支持向量机优化问题

\[\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i\\
s.t.\quad y_j(w^*x_j+b^*)\geq 1-\xi_i,i=1,2,\cdots,N\\
\quad \quad \quad\xi_i\geq 0\]

等价于

\[\underset{w,b,\xi}{min}\sum_{i=1}^{N} [y_i(w^{\mathrm{T}}x_i+b)-1]_++\lambda||w||^2\]

证明：令

\[[1-y_j(w^*x_j+b^*)]_+=\xi_i\geq 0\]

因此当$1-y_j(w^*x_j+b^*)>0$

\[1-y_j(w^*x_j+b^*)=\xi_j\]

当$1-y_j(w^*x_j+b^*)<0$

\[0=\xi_j\]

所以约束条件成立

\[y_j(w^*x_j+b^*)\geq 1-\xi_i\]

这和原问题的约束条件是一致的，优化问题等价于

\[\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i\]

0-1损失函数是真正的二分类损失函数，合页损失函数是其上界，但是0-1损失函数不是连续可导的，直接优化困难，所以选择优化0-1损失上界–合页损失函数。合页损失函数不仅要求分类正确，还要确信度足够高损失才是0，对于学习要求更加高。

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

线性可分问题，支持向量机非常有效，但是非线性分类问题则需要引入核函数。如下图

非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。如左图，是一个分类问题，图中”·”表示正实例点，”×”表示负实例点。由图可见，

无法用直线（线性模型）将正负实例正确分开，但可以用一条椭圆曲线（非线性模型）将它们正确分开。非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。对图中所示的例子，通过变换，将左图中椭圆变换成右图中的直线，将非线性分类问题变换为线性分类问题。

设原空间为$\mathbf{X}\in R^2$，$x=[x^{(1)},x^{(2)}]^{\mathrm{T}}\in \mathbf{X}$，新空间为$\mathbf{Z}\in R^2$，$z=[z^{(1)},z^{(2)}]^{\mathrm{T}}\in \mathbf{Z}$定义从原空间到新空间的变换（映射）：

\[z=\phi(x)\]

经过变换，原空间$\mathbf{X}\in R^2$变换为新空间$\mathbf{Z}\in R^2$，原空间中的点相应地变换为新空间中的点，原空间中的椭圆变换成为新空间中的直线。在变换后的新空间里，直线$w_1z^{(1)}+w_2z^{(2)}+b=0$可以将变换后的正负实例点正确分开。这样，原空间的非线性可分问题就变成了新空间的线性可分问题。

上面的例子说明，用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

核技巧应用到支持向量机：基本想法就是通过一个非线性变换将输入空间（欧氏空间或离散集合）对应于一个特征空间（希尔伯特空间），使得在输入空间中的超曲面模型对应于特征空间中的超平面模型（支持向量机）。这样，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成。

核函数：设$\mathbf{X}\in R^n$欧式空间或离散集合，有特征空间H（希尔伯特空间），存在一个映射

\[\phi(x):X\rightarrow H\]

对于所有的$x,y\in X$，函数满足

\[K(x,y)=\phi(x)\cdot \phi(y)\]

则$K(x,y)$称为核函数，$\phi(x)$是映射函数，$\phi(x)\cdot \phi(y)$是二者内积。

核技巧的想法是，在学习与预测中只定义核函数$K(x,y)$，而不显式地定义映射函数$\phi(x)$。通常，直接计算$K(x,y)$比较容易，而通过$\phi(x)$和$\phi(y)$计算$K(x,y)$并不容易。注意，$\phi(x)$是输入空间到特征空间的映射，特征空间一般是高维的，甚至是无穷维的。可以看到，对于给定的核$K(x,y)$，特征空间和映射函数$\phi(x)$的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。下面举一个简单的例子来说明核函数和映射函数的关系。

例子：设输入空间为$\mathbf{X}\in R^2$，核函数$K(x,y)=(x\cdot y)^2$

如果取特征空间$H\in R^3$, 由于

\[(x\cdot y)^2=(x_1y_1+x_2y_2)^2=(x_1y_1)^2+2x_1y_1x_2y_2+(x_2y_2)^2\]

所以映射可以选取

\[\phi(x)=[(x_1)^2,\sqrt2x_1x_2,(x_2)^2]^{\mathrm{T}}\\
\phi(x)=\frac{1}{\sqrt2}[(x_1)^2-(x_2)^2,2x_1x_2,(x_1)^2-(x_2)^2]^{\mathrm{T}}\]

如果取特征空间$H\in R^4$, 映射可以选取

\[\phi(x)=[(x_1)^2,x_1x_2,x_1x_2,(x_2)^2]^{\mathrm{T}}\]

核函数的应用：

我们注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积$x_i\cdot x_j$。在对偶问题的目标函数中的内积$x_i\cdot x_j$可以用核函数

\[K(x_i,x_j)=\phi(x_i)\cdot \phi(x_j)\]

来代替。此时对偶问题的目标函数成为

\[\underset{\alpha}{min}\quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i\]

分类决策函数中的内积也可以用核函数代替，而分类决策函数式成为

\[sign(\sum_{i=1}^{N}\alpha_i^*y_iK(x,x_i)+b^*)\]

这等价于经过映射函数将原来的输入空间变换到一个新的特征空间，将输入空间中的内积变换为特征空间中的内积$\phi(x_i)\cdot \phi(x_j)$，在新的特征空间里从训练样本中学习线性支持向量机。当映射函数是非线性函数时，学习到的含有核函数的支持向量机是非线性分类模型。也就是说，在核函数$K(x_i,x_j)$给定的条件下，可以利用解线性分类问题的方法求解非线性分类问题的支持向量机。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。

正定核

已知映射函数$\phi$的内积求得核函数$K(x_i,x_j)$,不用构造映射$\phi$能否直接判断一个给定的函数$K(x_i,x_j)$是不是核函数？或者说，函数$K(x_i,x_j)$满足什么条件才能成为核函数？

本节叙述正定核的充要条件。通常所说的核函数就是正定核函数（positive definite kernel function）。为证明此定理先介绍有关的预备知识。

假设$K(x_i,x_j)$是对称函数，并且对任意的$x_1,x_2,\cdots,x_m$，$K(x_i,x_j)$关于$x_1,x_2,\cdots,x_m$的Gram矩阵是半正定的。可以依据函数$K(x_i,x_j)$，构成一个希尔伯特空间（Hilbert space），其步骤是：首先定义映射$\phi$并构成向量空间；然后在上定义内积构成内积空间；最后将完备化构成希尔伯特空间。

1．定义映射，构成向量空间

先定义映射

\[\phi(x):x\rightarrow K(x,\cdot)\]

根据这一映射，对任意$x\in X$，$\alpha\in R$, i＝1,2,…,m，定义线性组合

\[f(\cdot)=\sum_{i=1}^{m}\alpha_iK(x_i,\cdot)\]

考虑由线性组合为元素的集合S。由于集合S对加法和数乘运算是封闭的，所以构成一个向量空间。

2．在S上定义内积，使其成为内积空间

\[f(\cdot)*g(\cdot)=\sum_{j=1}^{l}\beta_j\sum_{i=1}^{m}\alpha_iK(x_i,z_j)\]

比如

\[f(\cdot)*f(\cdot)=\sum_{j=1}^{l}\alpha_j\sum_{i=1}^{m}\alpha_iK(x_i,x_j)\geq 0\]

Gram矩阵是半正定的。

3．将内积空间完备化为希尔伯特空间

现在将内积空间完备化。由式内积可以得到范数

\[\left \| f(x)\right \|=\sqrt{(\cdot)*f(\cdot)}\]

因此，是一个赋范向量空间。根据泛函分析理论，对于不完备的赋范向量空间，一定可以使之完备化，得到完备的赋范向量空间。一个内积空间，当作为一个赋范向量空间是完备的时候，就是希尔伯特空间。这一希尔伯特空间称为再生核希尔伯特空间（reproducing kernel Hilbert space，RKHS）。这是由于核$K(x_i,x_j)$具有再生性，即满足

\[K(x,\cdot)*f(x)=\sum_{i=1}^{m}\alpha_iK(x_i,x)=f(x)\]

及

\[K(x,\cdot)*K(z,\cdot)=K(x,z)\]

称为再生核。

4．正定核的充要条件

定理7.5（正定核的充要条件）　设K: X→R是对称函数，则$K(x_i,x_j)$为正定核函数的充要条件是对任意$x_1,x_2,\cdots,x_m$，$K(x_i,x_j)$关于$x_1,x_2,\cdots,x_m$的Gram矩阵是半正定的。对应的Gram矩阵

\[K=[K(x_i,z_j)]_{m\times m}\succeq 0\]

这一定义在构造核函数时很有用。但对于一个具体函数$K(x_i,x_j)$来说，检验它是否为正定核函数并不容易，因为要求对任意有限输入集$x_1,x_2,\cdots,x_m$验证$K=[K(x_i,z_j)]_{m\times m}$对应的Gram矩阵是否为半正定的。在实际问题中往往应用已有的核函数。下面介绍一些常用的核函数。

多项式核函数：

\[K(x,y)=(x\cdot y+1)^p\]

高斯核函数：

\[K(x,y)=exp(-\frac{||x-y||^2}{2\sigma^2})\]

字符核函数：还可以定义在离散数据集合，在文本分类、信息检索方面应用广泛。

https://www.cnblogs.com/yifanrensheng/p/12354948.html

《统计学习》，李航

§12.6 非线性支持向量机的序列最小优化算法

我们知道，支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致无法使用。所以，如何高效地实现支持向量机学习就成为一个重要的问题。目前人们已提出许多快速实现算法。本节讲述其中的序列最小最优化（sequential minimaloptimization，SMO）算法，这种算法1998年由Platt提出。

SMO算法就是求解凸二次规划的对偶问题

\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0\\
\quad \quad \quad C\geq \alpha_i\geq 0,i=1,2,\cdots,N\]

$\alpha_i$是拉格朗日乘子，每个$\alpha_i$对应一个样本点$(x_i,x_j)$。

SMO算法是启发式算法，，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。

注意，子问题的两个变量中只有一个是自由变量。假设$\alpha_1$,$\alpha_2$为两个变量，其他乘子固定，那么由等式约束$\sum_{i=1}^{N}\alpha_iy_i=0$可知

\[\alpha_1=-y_1\sum_{i=2}^{N}\alpha_iy_i\]

所以子问题中同时更新两个变量。整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。

两个变量二次规划的求解方法不失一般性，假设选择的两个变量是$\alpha_1$,$\alpha_2$其他变量$\alpha_i$是固定的。于是SMO的最优化问题的子问题可以写成：

\[\underset{\alpha_1,\alpha_2}{min}\quad W(\alpha_1,\alpha_2)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i\\
=\frac{1}{2}[K]_{11}\alpha_1^2+\frac{1}{2}[K]_{22}\alpha_2^2+y_1y_2[K]_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^{N}\alpha_iy_iK(x_i,x_1)+y_2\alpha_2\sum_{i=3}^{N}\alpha_iy_iK(x_i,x_2)\\
s.t.\quad y_1\alpha_1+y_2\alpha_2=-\sum_{i=1}^{N}\alpha_iy_i=k\\
\quad\quad\quad C\geq \alpha_i\geq 0,i=1,2,\cdots,N\]

k是个常数。$W(\alpha_1,\alpha_2)$省掉很多不含$\alpha_1,\alpha_2$的常数项。

由于只有两个变量$\alpha_1,\alpha_2$，所以约束可以表示为平面区域

约束$y_1\alpha_1+y_2\alpha_2=-\sum_{i=1}^N\alpha_iy_1=k$限制了目标函数在平行对角线的直线上寻优，所以实质是单变量优化问题，那么

当$y_1\neq y_2$时，$\alpha_1-\alpha_2=k$，所以给定一组旧的可行解$\alpha_1^{old}$，$\alpha_2^{old}$和新的可行解都满足

\[\alpha_1^{old}-\alpha_2^{old}=k\\
\alpha_1^{new}-\alpha_2^{new}=k=\alpha_1^{old}-\alpha_2^{old}\]

那么

\[0\leq \alpha_1^{new}\leq C\\
0\leq \alpha_2^{new}\leq C\]

得出

\[0\leq \alpha_2^{new}+\alpha_1^{old}-\alpha_2^{old}\leq C\]

\[0\leq \alpha_2^{new}\leq C\]

也是

\[\alpha_2^{old}-\alpha_1^{old}\leq \alpha_2^{new}\leq C+\alpha_2^{old}-\alpha_1^{old}\]

\[-k\leq \alpha_2^{new}\leq C-k\]

\[0\leq \alpha_2^{new}\leq C\]

因此$\alpha_2^{new}$所在对角线端点的界为

\[L=max(0,\alpha_2^{old}-\alpha_1^{old})H=min(C,C+\alpha_2^{old}-\alpha_1^{old})\]

同理，当$y_1=y_2$时，$\alpha_1+\alpha_2=k$，所以给定一组旧的可行解$\alpha_1^{old}$,$\alpha_2^{old}$，和新的可行解$\alpha_1^{new}$,$\alpha_2^{new}$，所在对角线端点的界为

\[L=max(0,\alpha_2^{old}+\alpha_1^{old}-C)H=min(C,\alpha_2^{old}+\alpha_1^{old})\]

定理：记

\[g(x)=\sum_{i=1}^{N}\alpha_iy_iK(x_i,x)+b\]

令

\[E_i=g(x_i)-y_i=(\sum_{j=1}^{N}\alpha_jy_jK(x_i,x_j)+b)-y_i\]

表示输入$x_i$的预测值和标签$y_i$的差。

利用$y_1=\mp1$

\[y_1\alpha_1+y_2\alpha_2=k\\
\alpha_1=y_1(k-y_2\alpha_2)\]

代入$\underset{\alpha_1,\alpha_2}{min}W(\alpha_1,\alpha_2)$，则只是成了$\alpha_2$的二次函数优化问题了，那么利用

\[\frac{\partial{W}}{\partial{\alpha_2}}=0\]

得到

\[\alpha_2^{new,un}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{[K]_{11}+[K]_{22}-2[K]_{12}}\]

又注意到边界，所以

\[\alpha_2^{new}=\left\{\begin{matrix}
H,\alpha_2^{new.un}>H\\
\alpha_2^{new.un},L\leq \alpha_2^{new.un}\leq H\\
L,\alpha_2^{new.un}<L
\end{matrix}\right.\]

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

1．第1个变量的选择

SMO称选择第1个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量$\alpha_1$。

2．第2个变量的选择

SMO称选择第2个变量的过程为内层循环。第2个变量选择的标准是希望能使$\alpha_2$有足够大的变化。

Matlab 二分类支持项

>> load fisheriris

inds = ~strcmp(species,\’setosa\’);

X = meas(inds,3:4);

y = species(inds);

>> SVMModel = fitcsvm(X,y)

SVMModel =

ClassificationSVM

ResponseName: \’Y\’

CategoricalPredictors: []

ClassNames: {\’versicolor\’ \’virginica\’}

ScoreTransform: \’none\’

NumObservations: 100

Alpha: [24×1 double]

Bias: -14.4149

KernelParameters: [1×1 struct]

BoxConstraints: [100×1 double]

ConvergenceInfo: [1×1 struct]

IsSupportVector: [100×1 logical]

Solver: \’SMO\’

>> sv = SVMModel.SupportVectors;

figure

gscatter(X(:,1),X(:,2),y)

hold on

plot(sv(:,1),sv(:,2),\’ko\’,\’MarkerSize\’,10)

legend(\’versicolor\’,\’virginica\’,\’Support Vector\’)

hold off

支持向量

load fisheriris

X = meas(:,3:4);

Y = species;

figure

gscatter(X(:,1),X(:,2),Y);

h = gca;

lims = [h.XLim h.YLim]; % Extract the x and y axis limits

title(\'{\bf Scatter Diagram of Iris Measurements}\’);

xlabel(\’Petal Length (cm)\’);

ylabel(\’Petal Width (cm)\’);

legend(\’Location\’,\’Northwest\’);

SVMModels = cell(3,1);

classes = unique(Y);

rng(1); % For reproducibility

for j = 1:numel(classes)

indx = strcmp(Y,classes(j)); % Create binary classes for each classifier

SVMModels{j} = fitcsvm(X,indx,\’ClassNames\’,[false true],\’Standardize\’,true,…

\’KernelFunction\’,\’rbf\’,\’BoxConstraint\’,1);

end

d = 0.02;

[x1Grid,x2Grid] = meshgrid(min(X(:,1)):d:max(X(:,1)),…

min(X(:,2)):d:max(X(:,2)));

xGrid = [x1Grid(:),x2Grid(:)];

N = size(xGrid,1);

Scores = zeros(N,numel(classes));

for j = 1:numel(classes)

[~,score] = predict(SVMModels{j},xGrid);

Scores(:,j) = score(:,2); % Second column contains positive-class scores

end

[~,maxScore] = max(Scores,[],2);

figure

h(1:3) = gscatter(xGrid(:,1),xGrid(:,2),maxScore,…

[0.1 0.5 0.5; 0.5 0.1 0.5; 0.5 0.5 0.1]);

hold on

h(4:6) = gscatter(X(:,1),X(:,2),Y);

title(\'{\bf Iris Classification Regions}\’);

xlabel(\’Petal Length (cm)\’);

ylabel(\’Petal Width (cm)\’);

legend(h,{\’setosa region\’,\’versicolor region\’,\’virginica region\’,…

\’observed setosa\’,\’observed versicolor\’,\’observed virginica\’},…

\’Location\’,\’Northwest\’);

axis tight

hold off

fitcecoc

Fit multiclass models for support vector machines or other classifiers

本文链接：https://www.cnblogs.com/Prof-Loser/p/14728070.html

《神经网络与机器学习12章支持向量机》

合页损失（hinge loss）函数：

《神经网络与机器学习12章支持向量机》的更多相关文章

随机推荐

热门专题

目录导航

《神经网络与机器学习12章 支持向量机》

合页损失（hinge loss）函数：

《神经网络与机器学习12章 支持向量机》的更多相关文章

随机推荐

热门专题

目录导航

《神经网络与机器学习12章支持向量机》

《神经网络与机器学习12章支持向量机》的更多相关文章