统计学习方法第七章支持向量机（3）——非线性支持向量机

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

对解线性分类问题，线性分类支持向量机是一种非常有效的方法。但是，有时分类问题是非线性的，这时可以使用非线性支持向量机。

7.3.1 核技巧

非线性分类问题

非线性分类问题是指通过利用非线性模型才能很好的进行分类的问题。如果能用一个超曲面把正负例正确分开，则称这个问题是非线性可分问题。

非线性问题往往不好求解，所以希望能用解线性分类问题的方法解决这个问题。所采取的方法是进行一个非线性变换。

用线性方法求解非线性问题分为两步：

使用一个变换将原空间的数据映射到新空间
在新空间里用线性分类学习方法从训练数据集中学习到分类模型

核技巧（kernel trick）应用到支持向量机，其基本思想就是通过一个非线性变换将输入空间（欧式空间 $\mathbb{R}^n$ 或离散空间）对应于一个特征空间（希尔伯特空间 ${\cal H}$。在数学里，希尔伯特空间 Hilbert space，即完备的内积空间，也就是说一个带有内积的完备向量空间。希尔伯特空间是有限维欧几里得空间的一个推广，使之不局限于实数的情形和有限的维数，但又不失完备性），使得在输入空间中的超曲面模型对应于特征空间中的超平面模型（支持向量机）。

核函数的定义

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

$$\phi(x):{\cal X}\to{\cal H}$$

使得对所有的 $x,z\in{\cal X}$，函数 $K(x,z)$ 满足条件
$$K(x,z)=\phi(x)\cdot\phi(z)$$
则称 $K(x,z)$ 为核函数，$\phi(x)$ 为映射函数，式中 $\cdot$ 为内积运算。

核技巧的想法是，在学习和预测中只定义核函数 $K(x,z)$，而不显示的定义映射函数 $\phi$。通常，直接计算 $K(x,z)$ 比较容易，而通过内积计算 $K(x,z)$ 并不容易。

特征空间 ${\cal H}$ 一般是高维或无穷维的，对于给定的核 $K(x,z)$，特征空间核映射函数的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间里也可以取不同的映射。

例 7.3 假设输入空间是 $\mathbb{R}^2$，核函数是 $K(x,z)=(x\cdot z)^2$，试找出其相关的特征空间 ${\cal H}$ 和映射 $\phi(x):\mathbb{R}^2\to{\cal H}$

解：取特征空间 ${\cal H}=\mathbb{R}^3$，记 $x=\left(x^{(1)},x^{(2)}\right)^\text{T}$，$z=\left(z^{(1)},z^{(2)}\right)^\text{T}$，由于

$$\begin{eqnarray} (x\cdot z)^2 &=& \left(x^{(1)}z^{(1)}+x^{(2)}z^{(2)}\right)^2 \\ &=& \left(x^{(1)}z^{(1)}\right)^2+2x^{(1)}z^{(1)}x^{(2)}z^{(2)}+\left(x^{(2)}z^{(2)}\right)^2 \end{eqnarray}$$

所以可以取映射

$$\phi(x)=\left(\left(x^{(1)}\right)^2,\sqrt{2}x^{(1)}x^{(2)},\left(x^{(2)}\right)^2\right)^\text{T}$$

容易验证

$$\phi(x)\cdot\phi(z)=(x\cdot z)^2=K(x,z)$$

仍取 ${\cal H}=\mathbb{R}^3$ 以及

$$\phi(x)=\frac{1}{\sqrt{2}}\left(\left(x^{(1)}\right)^2-\left(x^{(2)}\right)^2,2x^{(1)}x^{(2)},\left(x^{(1)}\right)^2+\left(x^{(2)}\right)^2\right)^\text{T}$$

同样有 $\phi(x)\cdot\phi(z)=(x\cdot z)^2=K(x,z)$

还可以取 ${\cal H}=\mathbb{R}^4$ 和

$$\phi(x)=\left(\left(x^{(1)}\right)^2,x^{(1)}x^{(2)},x^{(1)}x^{(2)},\left(x^{(2)}\right)^2\right)^\text{T}$$

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

注意到在线性支持向量机的对偶问题中，无论是目标函数还是决策函数（分离超平面）都只涉及输入实例与实例之间的内积。在对偶问题的目标函数中的内积可以用核函数来代替。此时对偶问题的目标函数变为

$$W(\alpha)=\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$$

同样，分类决策函数中的内积也用核函数代替，变为

$$f(x)=\text{sign}\left(\sum_{i=1}^{N_s}\alpha_i^\star y_iK(x_i,x)+b^\star\right)$$

学习是隐式的在特征空间进行的，不需要显式的定义特征空间和映射函数。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。

7.3.2 正定核

已知映射函数 $\phi(x)$，可以通过内积求得核函数 $K(x,z)$，不用构造映射 $\phi(x)$ 能否直接判断一个给定的函数 $K(x,z)$ 是不是核函数呢？我们有如下关于正定核函数（positive definite kernel function）的定理。

定理 7.5（正定核的充要条件）设 $K:{\cal X}\times{\cal X}\to\mathbb{R}$ 是对称函数，则 $K(x,z)$ 为正定核的充要条件是对任意 $x_i\in{\cal X}$，$K(x,z)$ 对应的 Gram 矩阵

$$K=\left[K(x_i,x_j)\right]_{m\times m}$$

是半正定矩阵。

7.3.3 常用核函数

(a) 多项式核函数（polynomial kernel function）

$$K(x,z)=(x\cdot z+1)^p$$

对应的支持向量机是一个 $p$ 次多项式分类器。决策函数为

$$f(x)=\text{sign}\left(\sum_{i=1}^{N_s}a_i^\star y_i(x_i\cdot x+1)^p+b^\star\right)$$

(b) 高斯核函数（Gaussian kernel function）

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

对应的支持向量机是高斯径向基函数（radial basis function）分类器。决策函数为

$$f(x)=\text{sign}\left(\sum_{i=1}^{N_s}a_i^\star y_i\exp\left(-\frac{\|x-z\|^2}{2\sigma^2}\right)+b^\star\right)$$

7.3.4 非线性支持向量分类机

定义 7.8（非线性支持向量机）从非线性分类训练集，通过核函数与软间隔最大化，或凸二次规划，学习得到的分类决策函数

$$f(x)=\text{sign}\left(\sum_{i=1}^{N}\alpha_i^\star y_iK(x_i,x)+b^\star\right)$$

称为非线性支持向量机，$K(x,z)$ 是正定核函数。

算法 7.4（非线性支持向量机学习算法）
输入：训练数据集 $T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，其中 $x_i\in{\cal X}=\mathbb{R}^n$，$y_i\in{\cal Y}=\{+1,-1\}$，$i=1,2,\cdots,N$
输出：分类决策函数
(1) 选择适当的核函数 $K(x,z)$ 和惩罚参数 $C>0$，构造并求解约束最优化问题

$$\min_{\alpha} \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 \\ \text{s.t.}\ \ \ \ \begin{eqnarray} \sum_{i=1}^N\alpha_iy_i &=& 0 \\ 0\leq\alpha_i\leq C,\ i &=& 1,2,\cdots,N \end{eqnarray}$$

求得最优解 $\alpha^\star=\left(\alpha_1^\star,\alpha_2^\star,\cdots,\alpha_N^\star\right)^\text{T}$
(2) 选择 $\alpha^\star$ 的一个分量满足 $0<\alpha_i^\star<C$，计算
$$b^\star=y_j-\sum_{i=1}^N\alpha_i^\star y_iK(x_i,x_j)$$
(3) 构造分类决策函数
$$f(x)=\text{sign}\left(\sum_{i=1}^N\alpha_i^\star y_iK(x,x_i)+b^\star\right)$$
当 $K(x,z)$ 是正定核函数时，最优化问题是凸二次规划问题，解是存在的。