SVM 核函数相关知识
前面的文章讲述的都是将SVM用于线性可分或者近似线性可分的情况，对于非线性可分的情况，正是本文要讨论的内容。
核技巧
线性不可分问题是指不能用一个超平面将数据划分成两个部分，如下图所示：
但是如果我们对原始数据进行非线性变换，则有可能将原始数据映射到能够线性可分的空间中：
对于上面这样的数据，如何实现这样的变换？
设原始特征空间为：\mathcal X \subset R^2，x = (x^{(1)}, x^{(2)})^T \in \mathcal X，新的特征空间为：\mathcal Z \subset R^2，z = (z^{(1)}, z^{(2)})^T \in\mathcal Z。
定义原空间到新空间的映射为：
z = \phi(x) = ((x^{(1)})^2, (x^{(2)})^2)^T
则原空间的椭圆：
w_1(x^{(1)})^2 + w_2(x^{(2)})^2 + b = 0
变为了新空间的直线：
w_1 z^{(1)} + w_2 z^{(2)} + b = 0
于是，只要把所有的样本都映射到新的空间中，就可以用线性可分SVM完成分类了。我们称这样的变换思想为核技巧。
核技巧的基本想法是：通过一个非线性变换将输入空间对应于一个特征空间，使得输入空间R^n中的超曲面对应于特征空间\mathcal{H}的超平面。这样，分类问题的学习任务通过在特征空间中求解线性SVM就可以完成。
核函数
假设映射\phi(x): \mathcal{X} \to \mathcal{H}是一个从低维的输入空间\chi（欧式空间的子集或者离散集合）到高维的希尔伯特空间的\mathcal{H}映射。那么如果存在函数K(x,z)，对于任意x, z \in \chi，都有：
K(x, z) = \phi(x) \cdot \phi(z)
则称K(x, z)为核函数。其中\phi(x) \cdot \phi(z)表示x与z的内积，结果是一个常数。
为什么要引入核函数呢？
通常映射\phi需要将低维的输入空间映射到更高维度的空间才可以线性可分(例如对异或进行分类)，那么分别计算\phi(x)，\phi(z)的话，运算量比较大。如果存在K(x, z)可以等效的计算\phi(x) \cdot \phi(z)，则可以极大的减少运算量。
举个例子：
假设输入空间是\R^2，有x = (x^{(1)}, x^{(2)})，z = (z^{(1)}, z^{(2)})，K(x,z)=(x\cdot z)^2，可以取：
\mathcal{H}=\R^4, \phi(x)=((x^{(1)})^2, x^{(1)}x^{(2)}, x^{(1)}x^{(2)}, (x^{(2)})^2)^T
可以得到：
\phi(x) \cdot \phi(z) =K(x, z) = (x\cdot z)^2
也就是说二者结果相同，但是可以明显发现\phi(x) \cdot \phi(z)的计算复杂度要高得多。不过映射函数不唯一，下面的映射也能达到相同的效果：
\mathcal{H}=\R^3, \phi(x)=((x^{(1)})^2, \sqrt2x^{(1)}x^{(2)}, (x^{(2)})^2)^T
核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果表现在了高维上，这样避免了直接在高维空间中的复杂计算。
正定核
已知映射函数\phi，可以通过\phi(x)和\phi(z)的内积求得核函数K(x,z)。不构造\phi能否直接判断某个函数K(x,z)是核函数？
一般核函数指的是正定核函数，充要条件是：假设K(x,z)是对称函数，对于任意的x_i \in \chi ， i=1,2,3…m , K(x_i,x_j)对应的Gram矩阵K = \bigg[ K(x_i, x_j )\bigg]_{m\times m} 是半正定矩阵，则K(x,z)是正定核函数，此时K(x,z)是核函数。 也就是说，一个函数要想成为正定核函数，必须满足任何点的集合形成的Gram矩阵是半正定的。
基于上面的充要条件，可以检验是否是核函数，但是实际计算过程并不容易。一般我们都直接用现成的已经证明好的核函数。
常用核函数
1，线性核函数(Linear Kernel)
就是最普通的线性可分SVM，表达式为：
K(x, z) = x \cdot z
2，多项式核函数(Polynomial Kernel)
是线性不可分常用的核函数之一，表达式为：
K(x,z)=(x\cdot z + 1)^p
对应的支持向量机是一个p次多项式分类器。
3，高斯核函数(Gaussian Kernel)
在SVM中也称为径向基核函数(Radial Basis Function,RBF)，是非线性SVM最主流的核函数，libsvm默认的核函数就是它。表达式为：
K(x,z) = exp(-\gamma||x-z||^2)
其中\gamma \gt 0是需要指定的超参数。
4，Sigmoid核函数(Sigmoid Kernel)
也是线性不可分SVM常用的核函数之一，表达式为：
K(x, z) = tanh（\gamma x \bullet z + r)
其中\gamma , r是需要指定的超参数。
这么多核函数，各自都有什么特点，面对实际问题要如何选择，效果如何，这里先挖个坑，等到将sklearn的SVM调参时一起说。
核函数在SVM中的应用
回顾之前文章学习的SVM对偶问题：
\begin{aligned} \min_\alpha\ &\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^m\alpha_i\\ s.t.\ \ \ &\sum_{i=1}^m\alpha_iy_i=0\\ &0\leqslant \alpha_i \leqslant C,i=1,2,\dots,m \end{aligned}
将要优化的函数中的内积x_i \cdot x_j用核函数K(x_i,x_j)=\phi(x_i) \cdot \phi(x_j)来代替。此时对偶问题的目标问题以及分类决策函数变为：
\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\\ f(x)=sign\left(\sum_{i=1}^{N_s}\alpha_i^*y_i\phi(x_i)\cdot \phi(x)+b^*\right)=sign\left(\sum_{i=1}^{N_s}\alpha_i^*y_iK(x_i,x)+b^*\right)
这意味着我们甚至不需要指定映射函数\phi，就可以隐式的借助核函数等价的将输入空间映射到高维空间，进而在更高维的空间中找到划分超平面。在实际应用中，需要结合领域知识来选择合适的核函数。
非线性SVM算法流程
输入：训练集T={(x_1,y_1), (x_2,y_2), ..., (x_m,y_m)}，其中x为n维特征向量，y \in \{-1, 1\}。
输出：分离超平面的参数w^*, b^*以及分类决策函数。
算法流程：
(1) 选择适当的核函数K(x,z)和一个惩罚系数C\gt0, 构造约束优化问题
\min\limits_{\alpha} \;\; \frac{1}{2}\sum\limits_{i=1,j=1}^{m}\alpha_i\alpha_jy_iy_jK(x_i,x_j) - \sum\limits_{i=1}^{m}\alpha_i
s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0 \\ 0 \leq \alpha_i \leq C
(2) 利用SMO算法求出最优解 \alpha^* = (\alpha^*_1, \alpha^*_2, ...,\alpha^*_m)^T
(3) 找出所有满足0 < \alpha_s < C对应的的S个支持向量，对支持向量集合中的每个样本(x_s,y_s)，通过：
y_s(\sum\limits_{i=1}^{m}\alpha_iy_iK(x_i,x_s)+b) = 1
计算出每个支持向量(x_s, y_s)对应的b_s^{*}，即：
b_s^{*} = y_s - \sum\limits_{i=1}^{m}\alpha_iy_iK(x_i,x_s)
所有的b_s^{*}对应的平均值即为最终的b^*：
b^{*} = \frac{1}{S}\sum\limits_{i=1}^{S}b_s^{*}
(4) 构造决策函数：
f(x) = sign(\sum\limits_{i=1}^{m}\alpha_i^{*}y_iK(x, x_i)+ b^{*})
参考链接：
《统计学习方法 第二版》