非线性支持向量机

假设给定一个特征空间上的训练数据集

其中，，，，为第个特征向量，也称为实例，为的类标记，当时，称为正例；当时，称为负例，称为样本点。再假设输入空间中数据不是线性可分的，例如下图

线性不可分

于是通过从输入空间到特征空间的映射，其中，，在特征空间上，可以找到超平面

将数据线性划分，如下图：

线性可分

核函数的定义

设是输入空间（欧氏空间的子集或离散集合），又设为特征空间（希尔伯特空间），如果存在一个从到的映射

使得对所有，函数满足条件

则称为核函数，为映射函数，式中为和的内积。

回顾线性支持向量机中超平面公式：

分类的结果与输入和样本在输入空间的内积相关。而在非线性支持向量机中，则与输入和样本在特征空间的内积相关，即核函数。可以通过和线性支持向量机类似推导得到非线性支持向量机的超平面公式：

上式只需计算核函数的结果，而无需计算具体映射函数的结果。例如就是一个核函数，我们可以找到一个映射函数得到。证明过程略。

正定核

如前面所述，我们只需计算核函数而无需知道具体的映射函数。那么我们如何判断一个函数是否具备这样的的映射函数满足核函数的要求呢？我们可以根据核函数的充要条件判断：

设是对称函数，则为正定核函数的充要条件是对任意，，对应的矩阵：

是半正定矩阵。所以核函数也叫正定核函数。证明略。

常用的核函数

多项式核函数

高斯核函数

字符串核函数

计算字符串和的相似程度。具体略。

非线性支持向量机

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

称为非线性支持向量机，是正定核函数。

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

输入：训练数据集，其中，，；

输出：分类决策函数。

（1）选取适当的核函数和适当的参数，构造并求解最优化问题

求得最优解。

（2）选择的一个正分量，计算

（3）构造决策函数

对于的求解，一个快速有效的方法就是序列最小最优化算法
)。