SVM（四）：非线性支持向量机

3 非线性SVM

3.1 问题定义

现实任务中，训练样本经常不是线性可分的，即原始样本空间中并不存在一个能正确划分两类样本的超平面。
SVM（四）：非线性支持向量机
对于这样的问题，基于Mercer核展开定理，通过内积函数定义的非线性变换，将样本从原始空间映射到一个高维特征空间（Hibbert空间），使得样本在这个高维特征空间内线性可分（升维线性化）。

令 $\phi(\boldsymbol x)$ 表示将 $\boldsymbol x$ 映射后的特征向量，在特征空间中划分超平面对应的模型可表示为
$f(\boldsymbol x) = \boldsymbol w^T \phi(\boldsymbol x) + b$ 优化目标为
$\begin{aligned} & \min \; \frac{1}{2}||\boldsymbol w||^2 \\ & s.t. \;\; y_i(\boldsymbol w^T \phi(\boldsymbol x_i) + b) \geq 1,i =1,2,...m \end{aligned}$ 其对偶问题为
$\begin{aligned} \max_{\alpha} & \sum\limits_{i=1}^{m}\alpha_i - \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(\boldsymbol x_i)^T \phi(\boldsymbol x_j) \\ s.t. \; & \sum\limits_{i=1}^{m}\alpha_iy_i = 0, \\ & \alpha_i \geq 0, \; i=1,2,...m \end{aligned}$

该问题和线性可分SVM的优化目标函数的区别仅仅是将内积 $\boldsymbol x_i \boldsymbol x_j$ 替换为 $\phi (\boldsymbol x_i)^T \phi(\boldsymbol x_j)$ 。

$\phi (\boldsymbol x_i)^T \phi(\boldsymbol x_j)$ 是 $\boldsymbol x_i$ 与 $\boldsymbol x_j$ 映射到特征空间后的内积，由于特征空间维数很高，甚至是无穷维，因此直接计算 $\phi (\boldsymbol x_i)^T \phi(\boldsymbol x_j)$ 通常是困难的。

如对于一个2维特征的数据 $(x_1,x_2)$ ，需要将其映射到5维 $(1, x_1, x_2, x_{1}^2, x_{2}^2, x_{1}x_2)$ 来做特征的内积。

3.2 核函数

假设 $\phi$ 是一个从低维的输入空间 $\chi$ （欧式空间的子集或者离散集合）到高维的希尔伯特空间 $\mathcal{H}$ 的映射。如果存在函数 $\boldsymbol K( ,)$ 对于任意 $\boldsymbol x_i, \boldsymbol x_j \in \chi$ 都有：

$\boldsymbol K(x_i,x_j) = <\phi(\boldsymbol x_i),\phi(\boldsymbol x_j)> = \phi(\boldsymbol x_i)^T\phi(\boldsymbol x_j)$

即 $\boldsymbol x_i$ 与 $\boldsymbol x_j$ 在特征空间的内积等于它们在原始样本空间中通过函数 $\boldsymbol K( , )$ 计算的结果，则称 $\boldsymbol K( , )$ 为核函数。
核函数使得计算在低维特征空间中进行，避免了高维特征空间中的巨大计算量，同时还利用了高维空间线性可分的特性。

凡是满足Mercer定理的函数都可以作为支持向量机的核函数。
一般所说核函数为正定核函数（正定核比Mercer更具一般性），一个函数为正定核函数的充分必要条件是如下：

对于任意 $x_i \in \chi, i=1,2,3...m$ ， $\boldsymbol K(\cdot , \cdot )$ 是正定核函数，当且仅当 $\boldsymbol K(x_i,x_j)$ 对应的Gram矩阵 $\boldsymbol K = \bigg[ K(x_i, x_j )\bigg]$ 为半正定矩阵。

常用核函数如下
SVM（四）：非线性支持向量机
径向基函数核（RBF,Radial basis Function）又称高斯核。

4 一分类SVM（1-SVM）/多分类SVM

4.1 1-SVM

用于异常检测，通过超球提实现一分类：找到一个以 $\alpha$ 为中心，以 $R$ 为半径的包含样本本的最小超球。

4.2 多分类SVM

直接法：直接修改目标函数，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。简单但是计算复杂度较高，只适合小型问题。
间接法：主要通过组合多个二分类器来实现多分类器的构造，如：一对多（one-against-all）和一对一（one-against-one）方法。

（1）一对多法

训练时依次把某个类别的样本归为一类，其它样本归为另一类，这样 $k$ 个类别的样本构造了 $k$ 个SVM，分类时将未知样本分类为具有最大分类函数值的那类。

优点：训练 $k$ 个分类器，个数较少，分类速度相对较快
缺点：
- 训练速度会随训练样本数量的增加而急剧减慢
- 样本不对称：负类样本的数据要远远大于正类样本的数据（可通过引入不同的惩罚因子解决，对样本点较少的正类采用较大的惩罚因子 $C$ ）
- 新的类别加入，需要对所有的模型重新训练

（2）一对一法

在任意两类样本之间设计一个SVM，因此 $k$ 个类别的样本需要设计 $k(k-1)/2$ 个SVM，当对一个未知样本进行分类时，得票最多的类即为该样本的类别。当类别很多时，模型个数也很多，计算代价大。