前面的文章讲述的都是将SVM用于线性可分或者近似线性可分的情况，对于非线性可分的情况，正是本文要讨论的内容。

核技巧

线性不可分问题是指不能用一个超平面将数据划分成两个部分，如下图所示：

但是如果我们对原始数据进行非线性变换，则有可能将原始数据映射到能够线性可分的空间中：

对于上面这样的数据，如何实现这样的变换？

设原始特征空间为：$\mathcal X \subset R^2，x = (x^{(1)}, x^{(2)})^T \in \mathcal X$X⊂R2，x=(x(1),x(2))T∈X，新的特征空间为：$\mathcal Z \subset R^2，z = (z^{(1)}, z^{(2)})^T \in\mathcal Z$Z⊂R2，z=(z(1),z(2))T∈Z。

定义原空间到新空间的映射为：
$z = \phi(x) = ((x^{(1)})^2, (x^{(2)})^2)^T$z=ϕ(x)=((x(1))2,(x(2))2)T
则原空间的椭圆：
$w_1(x^{(1)})^2 + w_2(x^{(2)})^2 + b = 0$w1​(x(1))2+w2​(x(2))2+b=0
变为了新空间的直线：
$w_1 z^{(1)} + w_2 z^{(2)} + b = 0$w1​z(1)+w2​z(2)+b=0
于是，只要把所有的样本都映射到新的空间中，就可以用线性可分SVM完成分类了。我们称这样的变换思想为核技巧。

核技巧的基本想法是：通过一个非线性变换将输入空间对应于一个特征空间，使得输入空间$R^n$Rn中的超曲面对应于特征空间$\mathcal{H}$H的超平面。这样，分类问题的学习任务通过在特征空间中求解线性SVM就可以完成。

核函数

假设映射$\phi(x): \mathcal{X} \to \mathcal{H}$ϕ(x):X→H是一个从低维的输入空间$\chi$χ（欧式空间的子集或者离散集合）到高维的希尔伯特空间的$\mathcal{H}$H映射。那么如果存在函数$K(x,z)$K(x,z)，对于任意$x, z \in \chi$x,z∈χ，都有：
$K(x, z) = \phi(x) \cdot \phi(z)$K(x,z)=ϕ(x)⋅ϕ(z)
则称$K(x, z)$K(x,z)为核函数。其中$\phi(x) \cdot \phi(z)$ϕ(x)⋅ϕ(z)表示x与z的内积，结果是一个常数。

为什么要引入核函数呢？

通常映射$\phi$ϕ需要将低维的输入空间映射到更高维度的空间才可以线性可分(例如对异或进行分类)，那么分别计算$\phi(x)，\phi(z)$ϕ(x)，ϕ(z)的话，运算量比较大。如果存在K(x, z)可以等效的计算$\phi(x) \cdot \phi(z)$ϕ(x)⋅ϕ(z)，则可以极大的减少运算量。

举个例子：

假设输入空间是$\R^2$R2，有$x = (x^{(1)}, x^{(2)})，z = (z^{(1)}, z^{(2)})，K(x,z)=(x\cdot z)^2$x=(x(1),x(2))，z=(z(1),z(2))，K(x,z)=(x⋅z)2，可以取：
$\mathcal{H}=\R^4, \phi(x)=((x^{(1)})^2, x^{(1)}x^{(2)}, x^{(1)}x^{(2)}, (x^{(2)})^2)^T$H=R4,ϕ(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$ϕ(x)⋅ϕ(z)=K(x,z)=(x⋅z)2
也就是说二者结果相同，但是可以明显发现$\phi(x) \cdot \phi(z)$ϕ(x)⋅ϕ(z)的计算复杂度要高得多。不过映射函数不唯一，下面的映射也能达到相同的效果：
$\mathcal{H}=\R^3, \phi(x)=((x^{(1)})^2, \sqrt2x^{(1)}x^{(2)}, (x^{(2)})^2)^T$H=R3,ϕ(x)=((x(1))2,2​x(1)x(2),(x(2))2)T
核函数的价值在于它虽然也是将特征进行从低维到高维的转换，但核函数好在它在低维上进行计算，而将实质上的分类效果表现在了高维上，这样避免了直接在高维空间中的复杂计算。

正定核

已知映射函数$\phi$ϕ，可以通过$\phi(x)$ϕ(x)和$\phi(z)$ϕ(z)的内积求得核函数$K(x,z)$K(x,z)。不构造$\phi$ϕ能否直接判断某个函数$K(x,z)$K(x,z)是核函数？

一般核函数指的是正定核函数，充要条件是：假设$K(x,z)$K(x,z)是对称函数，对于任意的$x_i \in \chi ， i=1,2,3…m $, $K(x_i,x_j)$K(xi​,xj​)对应的Gram矩阵$K = \bigg[ K(x_i, x_j )\bigg]_{m\times m}$K=[K(xi​,xj​)]m×m​ 是半正定矩阵，则$K(x,z)$K(x,z)是正定核函数，此时$K(x,z)$K(x,z)是核函数。 也就是说，一个函数要想成为正定核函数，必须满足任何点的集合形成的Gram矩阵是半正定的。

基于上面的充要条件，可以检验是否是核函数，但是实际计算过程并不容易。一般我们都直接用现成的已经证明好的核函数。

常用核函数

1，线性核函数(Linear Kernel)

就是最普通的线性可分SVM，表达式为：
$K(x, z) = x \cdot z$K(x,z)=x⋅z

2，多项式核函数(Polynomial Kernel)

是线性不可分常用的核函数之一，表达式为：
$K(x,z)=(x\cdot z + 1)^p$K(x,z)=(x⋅z+1)p
对应的支持向量机是一个p次多项式分类器。

3，高斯核函数(Gaussian Kernel)

在SVM中也称为径向基核函数(Radial Basis Function,RBF)，是非线性SVM最主流的核函数，libsvm默认的核函数就是它。表达式为：
$K(x,z) = exp(-\gamma||x-z||^2)$K(x,z)=exp(−γ∣∣x−z∣∣2)
其中$\gamma \gt 0$γ>0是需要指定的超参数。

4，Sigmoid核函数(Sigmoid Kernel)

也是线性不可分SVM常用的核函数之一，表达式为：
$K(x, z) = tanh（\gamma x \bullet z + r)$K(x,z)=tanh（γx∙z+r)
其中$\gamma , r$γ,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}$αmin​ s.t.   ​21​i=1∑m​j=1∑m​αi​αj​yi​yj​(xi​⋅xj​)−i=1∑m​αi​i=1∑m​αi​yi​=00⩽αi​⩽C,i=1,2,…,m​
将要优化的函数中的内积$x_i \cdot x_j$xi​⋅xj​用核函数$K(x_i,x_j)=\phi(x_i) \cdot \phi(x_j)$K(xi​,xj​)=ϕ(xi​)⋅ϕ(xj​)来代替。此时对偶问题的目标问题以及分类决策函数变为：
$\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)$αmin​21​i=1∑N​j=1∑N​αi​αj​yi​yj​K(xi​,xj​)−i=1∑N​αi​f(x)=sign(i=1∑Ns​​αi∗​yi​ϕ(xi​)⋅ϕ(x)+b∗)=sign(i=1∑Ns​​αi∗​yi​K(xi​,x)+b∗)
这意味着我们甚至不需要指定映射函数$\phi$ϕ，就可以隐式的借助核函数等价的将输入空间映射到高维空间，进而在更高维的空间中找到划分超平面。在实际应用中，需要结合领域知识来选择合适的核函数。

非线性SVM算法流程

输入：训练集$T={(x_1,y_1), (x_2,y_2), ..., (x_m,y_m)}$T=(x1​,y1​),(x2​,y2​),...,(xm​,ym​)，其中x为n维特征向量，$y \in \{-1, 1\}$y∈{−1,1}。

输出：分离超平面的参数$w^*, b^*$w∗,b∗以及分类决策函数。

算法流程：

(1) 选择适当的核函数$K(x,z)$K(x,z)和一个惩罚系数$C\gt0$C>0, 构造约束优化问题
$\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$αmin​21​i=1,j=1∑m​αi​αj​yi​yj​K(xi​,xj​)−i=1∑m​αi​

$s.t. \; \sum\limits_{i=1}^{m}\alpha_iy_i = 0 \\ 0 \leq \alpha_i \leq C$s.t.i=1∑m​αi​yi​=00≤αi​≤C

(2) 利用SMO算法求出最优解 $\alpha^* = (\alpha^*_1, \alpha^*_2, ...,\alpha^*_m)^T$α∗=(α1∗​,α2∗​,...,αm∗​)T

(3) 找出所有满足$0 < \alpha_s < C$0<αs​<C对应的的S个支持向量，对支持向量集合中的每个样本$(x_s,y_s)$(xs​,ys​)，通过：
$y_s(\sum\limits_{i=1}^{m}\alpha_iy_iK(x_i,x_s)+b) = 1$ys​(i=1∑m​αi​yi​K(xi​,xs​)+b)=1
计算出每个支持向量$(x_s, y_s)$(xs​,ys​)对应的$b_s^{*}$bs∗​，即：
$b_s^{*} = y_s - \sum\limits_{i=1}^{m}\alpha_iy_iK(x_i,x_s)$bs∗​=ys​−i=1∑m​αi​yi​K(xi​,xs​)
所有的$b_s^{*}$bs∗​对应的平均值即为最终的$b^*$b∗：
$b^{*} = \frac{1}{S}\sum\limits_{i=1}^{S}b_s^{*}$b∗=S1​i=1∑S​bs∗​
(4) 构造决策函数：
$f(x) = sign(\sum\limits_{i=1}^{m}\alpha_i^{*}y_iK(x, x_i)+ b^{*})$f(x)=sign(i=1∑m​αi∗​yi​K(x,xi​)+b∗)

参考链接：

《统计学习方法 第二版》

支持向量机原理(三)线性不可分支持向量机与核函数

李航-统计学习方法-笔记-7：支持向量机- PilgrimHui - 博客园