统计学习方法笔记09

李航. 统计学习方法[M]. 清华大学出版社, 2012.

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

7.3.1 核技巧

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

核技巧应用到支持向量机，其基本思想就是通过一个非线性变换将输入空间（欧式空间或离散空间）对应于一个特征空间，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型（支持向量机）。

核函数

设 $\mathcal{X}$ 是输入空间，又设 $\mathcal{H}$ 为特征空间，如果存在一个从 $\mathcal{X}$ 到

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

核技巧的想法是，在学习与预测过程中只定义核函数 $K(x,z)$ ，而不显式地定义映射函数 $\phi$ 。对于给定的核 $K(x,z)$ ，特征空间 $\mathcal{H}$ 和映射函数 $\phi$ 的取法并不唯一。

在对偶问题的目标函数中的内积可以用核函数来代替，于是对偶问题的目标函数成为

$W(\alpha) = \dfrac{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^* y_i K(x_i,x) + b^* \right)$

7.3.2 正定核

正定核的充要条件

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

正定核的等价定义

设 $\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矩阵 $K=[K(x_i,x_j)]_{m\times m}$ 是半正定矩阵，则称 $K(x,z)$ 是正定核(positive definite kernel function)。

7.3.3 常用核函数

多项式核函数(polynomial kernel function)

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

高斯核函数(Gaussian kernel function)

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

字符串核函数(string kernel function)

$[\phi_n(s)]_u = \sum_{i:s(i)=u} \lambda^{l(i)}$

$\begin{aligned}k_n(s,t) &= \sum_{u\in \Sigma^n} [\phi_n(s)]_u [\phi_n(t)]_u \\&= \sum_{u\in \Sigma^n} \sum_{(i,j):s(i)=t(j)=u} \lambda^{l(i)} \lambda^{l(j)}\end{aligned}$

7.3.4 非线性支持向量分类机

非线性支持向量机

从非线性分类训练集，通过核函数与软间隔最大化，或下面算法中的凸二次规划，学习到的分类决策函数

$f(x) = sign\left( \sum_{i=1}^N \alpha_i^* y_i K(x,x_i) + b^* \right)$

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

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

输入：训练数据集 $T=\{(x_i,y_i)\}$ ，其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\{-1,+1\}$ ， $i=1,\dots,N$

输出：分类决策函数

(1) 选取适当的核函数 $K(x,z)$ 和适当的参数 $C$ ，构造并求解最优化问题

$\begin{equation}\begin{aligned}\min_{\alpha} \quad & \dfrac{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 \\\text{s.t.} \quad & \sum_{i=1}^N \alpha_i y_i = 0 \\& 0 \leq \alpha_i \leq C, i=1,2,\dots,N\end{aligned}\end{equation}$

(2) 选择 $\alpha^*$ 的一个正分量 $0<\alpha_j^*<C$ ，计算

$b^* = y_j - \sum_{i=1}^N \alpha_i^* y_i K(x_i,x_j)$

(3) 构造决策函数 $f(x) = sign\left( \sum_{i=1}^N \alpha_i^* y_i K(x,x_i) + b^* \right)$

7.4 序列最小最优化算法

序列最小最优化算法(sequential minimal optimization, SMO)算法旨在高效实现支持向量机学习，是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件(Karush-Kuhn-Tucker conditions)，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。

SMO算法

输入：训练数据集 $T=\{(x_i,y_i)\}$ ，其中 $x_i\in\mathcal{X}=\mathbb{R}^n$ ， $y_i\in\{-1,+1\}$ ，精度 $\varepsilon$

输出：近似解 $\hat{\alpha}$

(1) 取初值 $\alpha^{(0)}=0$ ，令 $k=0$ ；

(2) 选取优化变量 $\alpha_1^{(k)},\alpha_2^{(k)}$ ，解析求解两个变量的最优化问题

$\begin{aligned}\min_{\alpha_1,\alpha_2} \quad & W(\alpha_1,\alpha_2) = \dfrac{1}{2} K_{11}\alpha_1^2 + \dfrac{1}{2} K_{22}\alpha_2^2 + y_1 y_2 K_{12} \alpha_1 \alpha_2 - (\alpha_1+\alpha_2) + \\& \qquad\qquad\qquad y_1 \alpha_1 \sum_{i=3}^N y_i\alpha_i K_{i1} + y_2 \alpha_2 \sum_{i=3}^N y_i \alpha_i K_{i2}\\\text{s.t.} \quad & \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^N y_i \alpha_i = \varsigma \\& 0 \leq \alpha_i \leq C, i=1,2\end{aligned}$