支持向量机（四）——核方法

〇、说明

支持向量机(Support Vector Machine,SVM)是监督学习中非常经典的算法。笔者主要参考学习的是李航老师《统计学习方法（第二版）》[1]和周志华老师的西瓜书《机器学习》[2]。

如有错误疏漏，烦请指正。如要转载，请联系笔者，hpfhepf@gmail.com。

一、问题引出

对于线性分类问题，前面所述的线性可分支持向量机和软间隔支持向量机是非常有效的方法。现实任务中，往往更多的是非线性的分类问题，线性模型就无能为力了。例如异或问题，如下图

图1[2]

这样的问题，可以考虑将样本从原始的特征空间映射到一个更高维的特征空间，使得样本在新的特征空间线性可分。在图1中，若将原始的二维空间映射到一个合适的三维空间，就能找到一个合适的分类超平面。如果原始的特征空间是有限维，那么一定存在一个高维特征空间使样本线性可分。[2]

利用核方法，可以将线性支持向量机扩展到非线性支持向量机。

二、核函数简介

李航老师在其《统计学习方法（第二版）》中对核函数有较为详细的介绍。这里简单介绍一下核函数的定义和常用核函数。

核函数定义[1]：

设 $\mathcal X$ 是输入空间（欧式空间 $\mathbb{R}^n$ 的子集或离散集合），又设 $\mathcal H$ 为特征空间（希尔伯特空间），如果存在一个从 $\mathcal X$ 到 $\mathcal H$ 的映射

$\phi (x):\mathcal X \rightarrow \mathcal H \tag{1}$

使得对所有 $x,z\in \mathcal X$ ，函数 $K(x,z)$ 满足条件

$K(x,z)=\phi(x) \cdot \phi(z) \tag{2}$

则称 $K(x,z)$ 为核函数， $\phi(x)$ 为映射函数。

正定核函数定义[1]:

设 $\mathcal X\subset \mathbb{R}^n$ ， $K(x,z)$ 是定义在 $\mathcal X \times \mathcal X$ 上的对称函数，如果对任意 $x_{i}\in \mathcal X, i=1,2,\dots,m$ ， $K(x,z)$ 对应的Gram矩阵

$\textbf{K}=[K(x_{i},x_{j})]_{m\times m} \tag{3}$

是半正定矩阵，则称 $K(x,z)$ 是正定核函数。

用定义验证核函数并不容易，实际应用中往往使用已有的核函数。在使用中，通常只定义核函数，不用显式定义映射函数。

常用核函数：

1.线性核函数

$K(x,z)=x\cdot z \tag{4}$

就是内积。

2.多项式核函数[3]

$K(x,z)=(x\cdot z+c)^d \tag{5}$

当 $c=0,d=1$ 时，退化为线性核函数。

3.高斯核函数

$K(x,z)=exp(-\frac{||x-z||^2}{2\sigma^2}) \tag{6}$

也叫径向基核函数。

三、非线性支持向量机

在线性支持向量机[4]对偶问题的目标函数中，将样本内积 $x_{i} \cdot x_{j}$ 替换成核函数 $K(x_{i},x_{j})$ ，非线性支持向量机如下

$\begin{split}&\mathop{min}\limits_{\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} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2,\dots,N\end{split} \tag{7}$

求得最优非线性分类模型参数为

$\begin{align}& w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \\& b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}K(x_{i},x_{j}) , \ 0<\alpha^*_{j} <C \end{align}\tag{8}$