非线性SVM与核函数

svm学习笔记，参考《统计学习方法》、深度学习500问

线性支持向量机

如果能用一个超曲面将数据集中正负例分开，则称这个问题为非线性可分问题。

对于上图中的例子，我们可以用一个椭圆形的超曲面将数据集分开，是一个非线性可分问题。

非线性问题往往不好解，如果能通过一个非线性变换，将左图中椭圆变成右图中的直线，就可将非线性分类问题变换为线性分类问题。

所以对于非线性分类问题，我们可以用线性分类方法来求解：首先使用一个变换将原空间的数据映射到新空间，然后在新空间里用线性分类学习方法从训练数据中学习分类模型。因此我们引入核函数到svm中，来使用svm解决非线性分类问题。

通常我们直接计算 K(x,z) 比较简单，所以我们在学习和预测中只定义核函数，而不显示的定义映射函数 $\phi$ 。

在线性svm中，在对偶问题的目标函数(7.37)(见上一篇传送门)中的内积 $x_i\cdot x_j$ 可以用核函数 $K(x_i,x_j)=\phi(x_i)\cdot\phi(x_j)$ 来代替，此时对偶问题的目标函数变为：

而分类决策函数式变为：

这等价于经过映射函数 $\phi$ 将输入空间中的内积 $x_i,x_j$ 变换为特征空间中的内积 $\phi(x_i)\cdot\phi(x_j)$ ，在新的特征空间中从训练样本中学习线性svm。当映射函数是非线性函数时，学习到的含有核函数的svm就是非线性分类模型。

学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数，这样的技巧称为核技巧。

引入核函数目的：把原坐标系里线性不可分的数据用核函数Kernel投影到另一个空间，尽量使得数据在新的空间里线性可分。
核函数方法的广泛应用，与其特点是分不开的：

1）核函数的引入避免了“维数灾难”，大大减小了计算量。而输入空间的维数n对核函数矩阵无影响。因此，核函数方法可以有效处理高维输入。

2）无需知道非线性变换函数Φ的形式和参数。

3）核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能。

4）核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法。

对于设计的函数 K(x,z) 是否是否可以作为核函数，可以通过正定核的充要条件(太长了不看了)来判断。而在实际应用中，往往依赖领域知识直接选择核函数，然后通过实验验证选择的核函数是否有效。

svm的学习问题可以转化为求解凸二次规划问题，但是当样本数很大时，svm算法往往变得非常低效。如何高效地实现svm的学习呢？一种快速实现算法就是序列最小最优化(SMO)算法(有空再看)。