【统计学习方法】学习笔记——支持向量机（下）

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

非线性支持向量机，其主要特点是利用核技巧（kernel trick）。

3.1 核技巧

1. 非线性分类问题、
   非线性分类问题是指通过利用非线性模型才能很好地进行分类的问题。
   一般来说，对给定的一个训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中，实例$x_i$属于输入空间，$x_i\in \mathcal{X}=R^n$，对应的类标记有两类$y_i\in y=\{-1,+1\},i=1,2,...,N$。如果能用$R^n$中的一个超曲面将正负例正确分来，则称这个问题为非线性可分问题。
   
   左图分类问题无法用直线（线性模型）将正负实例正确分开，但可以用一条椭圆曲线（非线性模型）将它们正确分开。

如果能用一个超曲面将正负例正确分开，则称这个问题为非线性可分问题。非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换，将非线性问题变换为线性问题。通过求解线性问题来求解原问题。
设原空间为$\mathcal{X}\subset R^2，x=(x^{(1)},x^{(2)}{)}^T\in \mathcal{X}$，新空间为$\mathcal{Z}\subset R^2$，$z=(z^{(1)},z^{(2)}{)}^T\in \mathcal{Z}$，定义原空间到新空间的映射：$$z=\varphi (x)=((x^{(1)}{)}^2,(x^{(2)}{)}^2{)}^T$$
则原空间的椭圆$$w_1(x^{(1)}{)}^2+w_2(x^{(2)}{)}^2+b=0$$
变换成新空间的直线$$w_1{z}^{(1)}+w_2{z}^{(2)}+b=0$$

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

2. 核函数的定义
   
   核技巧的想法是，学习与预测中只定义核函数$K(x,z)$，而不是显示的定义映射函数$\varphi$。通过，直接计算$K(x,z)$比较容易，而通过$\varphi (x)$和$\varphi (z)$计算$K(x,z)$并不容易。特征空间$\mathcal{H}$一般是高维的，甚至是无穷维的。

对于给定的核$K(x,z)$，特征空间$\mathcal{H}$和映射函数$\varphi$的取法并不唯一，可以取不同的特征空间，即使在同一特征空间里也可以取不同映射。

3. 核技巧在支持向量机中的应用
   在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中的内积$x_i\cdot x_j$可以用核函数$K(x_i,x_j)=\varphi (x_i)\cdot \varphi (x_j)$来代替。此时对偶问题的目标函数成为：$$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(\sum _{i=1}^{N_s}{\alpha }_i^{\ast }{y}_i\varphi (x_i)\cdot \varphi (x)+b^{\ast })=sign(\sum _{i=1}^{N_s}{\alpha }_i^{\ast }{y}_{i}K(x_i,x)+b^{\ast })$$

在新的特征空间里从训练样本中学习线性SVM。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧。当映射函数是非线性函数时，学习到的含有核函数的SVM是非线性分类模型。

在实际应用中，往往依赖领域知识直接选择核函数，核函数的有效性需要通过实验验证。

3.2 正定核

函数$K(x,z)$满足什么条件才能称为核函数呢？通常所说的核函数就是正定核函数（positive definite kernel function）。首先介绍一些预备知识。
假设$K(x,z)$是定义在$\mathcal{X}\times \mathcal{X}$上的对称函数，并且对任意的$x_1,x_2,...,x_m\in \mathcal{X}$，$K(x,z)$关于$x_1,x_2,...,x_m$的Gram矩阵是半正定的。可以依据函数$K(x,z)$，构成一个希尔伯特空间，其步骤是：首先定义映射$\varphi$并构成向量空间$\mathcal{S}$；然后在$\mathcal{S}$上定义内积构成内积空间；最后将$\mathcal{S}$完备化构成希尔伯特空间。

1. 定义映射，构成向量空间$\mathcal{S}$
   先定义映射$$\varphi :x\to K(\cdot ,x)$$
   根据这一映射，对任意$x_i\in \mathcal{X}，{\alpha }_i\in R,i=1,2,...,m$，定义线性组合$$f(\cdot )=\sum _{i=1}^m{\alpha }_{i}K(\cdot ,x_i)$$考虑由线性组合为元素的集合$\mathcal{S}$。由于集合$\mathcal{S}$对加法和数乘运算是封闭的，所以$\mathcal{S}$构成一个向量空间。

2. 在$\mathcal{S}$上定义内积，使其成为内积空间
   在$\mathcal{S}$上定义一个运算$\ast$：对任意$f,g\in \mathcal{S}$，$$f(\cdot )=\sum _{i=1}^m{\alpha }_{i}K(\cdot ,x_i)$$$$g(\cdot )=\sum _{j=1}^l{\beta }_{j}K(\cdot ,z_j)$$定义运算$\ast$
   $$f\ast g=\sum _{i=1}^m\sum _{j=1}^l{\alpha }_i{\beta }_{j}K(x_i,z_j)$$

3. 将内积空间$\mathcal{S}$完备化为希尔伯特空间
   现在将内积空间$\mathcal{S}$完备化，由上式定义的内积可以得到范数$$||f||=\sqrt{f\cdot f}$$
   因此，$\mathcal{S}$是一个赋范向量空间。根据泛函分析理论，对于不完备的赋范向量空间$\mathcal{S}$，一定可以使之完备化，得到完备的赋范向量空间$\mathcal{H}$。一个内积空间，当作为一个赋范向量空间是完备的时候，就是希尔伯特空间。这样，就得到了希尔伯特空间$\mathcal{H}$。

这一希尔伯特空间$\mathcal{H}$称为再生核希尔伯特空间。这是由于核K具有再生性，即满足$$K(\cdot ,x)\cdot f=f(x)$$及$$K(\cdot ,x)\cdot K(\cdot ,z)=K(x,z)$$
称为再生核。

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

定义：正定核的等价定义：设$\mathcal{X}\subset R^2,K(x,z)$是定义在KaTeX parse error: Undefined control sequence: \tims at position 13: \mathcal{X} \̲t̲i̲m̲s̲ ̲\mathcal{X}上的对称函数，如果对任意$x_i\in \mathcal{X}，i=1,2,...,m,K(x,z)$对应的Gram矩阵
$$K=[K(x_i,x_j){]}_{m\times n}$$
是半正定矩阵，则称$K(x,z)$是正定核。

3.3 常用核函数

（1）多项式核函数（polynomial kernel function）
$$K(x,z)=(x\cdot z+1{)}^p$$
对应的支持向量机是一个p次多项式分类器。在此情形下，分类决策函数成为
$$f(x)=sign(\sum _{i=1}^{N_s}{\alpha }_i^{\ast }{y}_i(x_i\cdot x+1{)}^p+b^{\ast })$$
（2）高斯核函数（Gaussian kernel function）
$$K(x,z)=exp(-\frac{||x-z|{|}^2}{2{\sigma }^2})$$
对应的支持向量机是高斯径向基函数分类器。在此情形下，分类决策函数成为
$$f(x)=sign(\sum _{i=1}{N}_s{\alpha }_i^{\ast }{y}_{i}exp(-\frac{||x-z|{|}^2}{2{\sigma }^2})+b^{\ast })$$
（3）字符串核函数
核函数不仅可以定义在欧式空间上，还可以定义在离散数据的集合上。比如，字符串核是定义在字符串集合上的核函数。字符串核函数在文本分类，信息检索，生物信息等方面都有应用。

判断核函数
（1）给定一个核函数$K$，对于$a>0$，$aK$也为核函数。
（2）给定两个核函数$K\prime$和$K\prime \prime$，$K\prime K\prime \prime$也为核函数。
（3）对输入空间的任意实值函数$f(x)$，$K(x_1,x_2)=f(x_1)f(x_2)$为核函数。

3.4 非线性支持向量机

定义：非线性支持向量机： 从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划，学习得到的分类决策函数$$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K(x,x_i)+b^{\ast })$$称为非线性支持向量机，$K(x,z)$是正定核函数。

算法：非线性支持向量机学习算法
输入：训练数据集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$，其中，$x_i\in \mathcal{X}=R^n$，$y_i\in y=\{-1,+1\},i=1,2,...,N$;
输出：分类决策函数
（1）选取适当的核函数$K(x,z)$和适当的参数C，构造并求解最优化问题
$$\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,...,N$$
求得最优解${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast }{)}^T$。
（2）选择${\alpha }^{\ast }$的一个分量${\alpha }_j^{\ast }$适合条件$0<{\alpha }_j^{\ast }<C$，计算$b^{\ast }=y^j-{\sum }_{i=1}^N{y}_i{\alpha }_i^{\ast }{y}_{i}K(x_i\cdot x_j)$
（3）构造决策函数：
$$f(x)=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}K(x\cdot x_i)+b^{\ast })$$
当$K(x,z)$是正定核函数时，上述过程是求解凸二次规划问题，解是存在的。

4. 序列最小最优化算法

SMO算法：如何高效地实现支持向量机学习，是一种启发式算法，基本思路是：
如果变量的解都满足此最优化问题的KKT条件（Karush-Kuhn-Tucker conditions），那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。

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

为了求解两个变量的二次规划问题，首先分析约束条件，然后又在此约束条件下求极小。

4.2 变量的选择方法

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

（1）第一个变量的选择

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

（2） 第2个变量的选择

SMO称选择第2个变量的过程为内层循环。假设在外层循环中已经找到第1个变量$a_1$，现在要在内层循环中找第2个变量$a_2$. 第2个变量选择标准是希望能使$a_2$有足够大的变化。

（3）计算阀值$b$和差值$E_i$
在每次完成两个变量的优化后，都要重新计算阀值b。在每次完成两个变量的优化之后，还必须更新对应的$E_i$值，并将它们保存在列表中。

4.3 SMO算法

总结

• 支持向量机最简单的情况是线性可分支持向量机，或硬间隔支持向量机。构建它的条件是训练数据线性可分。其学习策略是最大间隔法。
• 现实中训练数据集时线性可分的情况较少，训练集往往是近似线性可分的，这时使用线性支持向量机，或软间隔支持向量机。线性支持向量机是最基本的支持向量机。
• 对于输入空间中的非线性分类问题，可以通过非线性变换将它转化为某个高维特征空间中的线性分类问题，在高维特征空间中学习支持向量机。由于在线性支持向量机学习的对偶问题里，目标函数和分类决策函数都只涉及实例与实例之间的内积，所以不需要显式地指定非线性变换，而是用核函数来替换当中的内积。核函数表示，通过一个非线性转换后的两个实例之间的内积。
• SMO算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止，这样通过启发式的方法得到原二次规划问题的最优解。

内容来源

[1] 《统计学习方法》 李航
[2] https://blog.csdn.net/qq_42794545/article/details/121080091