关于支持向量机(SVM)的高斯核和惩罚因子C的理解（简单易懂）

　　跟小伙伴探讨了支持向量机(Support Vector Machine, SVM)，不自觉地就将话题拉向了高斯核函数和惩罚因子C。本文用简单易懂的形式呈现了自己对于高斯核函数和惩罚因子C的理解。
　　为什么说高斯核对应的映射函数将原始特征空间映射成了无限维空间？高斯核函数的参数σ$\sigma$如何选择？惩罚因子C的加入有何意义？C的取值大小对于SVM的模型有何影响？后文将围绕这几个问题进行探讨。

1 理解高斯核函数

1.1 为什么要有核函数

　　当数据集在原始特征中不是线性可分的时候，支持向量机采用了引入映射函数Φ(⋅)$\mathrm{\Phi }(\cdot )$的策略：通过映射函数将原始特征空间映射为更高维的空间，在原始空间中不可分的数据在高维空间中可能变成线性可分，此时再在高维空间中运用SVM。
　　用一张图片直观地解释这一思想。

图1 映射函数示意

　　那么要实现非线性SVM模型，我们就找出一个合适的映射函数Φ(⋅)$\mathrm{\Phi }(\cdot )$，把特征空间映射到高维空间，在高维空间对样本分类！！So easy!!
　　可是仔细想想，每次都要显式地找到一个映射函数有没有必要？我们不是要在高维空间中对样本分类嘛？如果样本Φ(xi)$\mathrm{\Phi }(x_i)$与样本Φ(xj)$\mathrm{\Phi }(x_j)$的距离∥Φ(xi)−Φ(xj)∥$\Vert \mathrm{\Phi }(x_i)-\mathrm{\Phi }(x_j)\Vert$很近，我们就把样本xi$x_i$和xj$x_j$分为同一类不就好了吗？那我们不知道映射函数Φ(⋅)$\mathrm{\Phi }(\cdot )$的基础上能不能计算∥Φ(xi)−Φ(xj)∥$\Vert \mathrm{\Phi }(x_i)-\mathrm{\Phi }(x_j)\Vert$呢？核函数说：我来。
　　核函数的诀窍在于解决了映射后高维空间中样本距离∥Φ(xi)−Φ(xj)∥$\Vert \mathrm{\Phi }(x_i)-\mathrm{\Phi }(x_j)\Vert$的计算，但又不显式地展示出映射函数Φ(⋅)$\mathrm{\Phi }(\cdot )$。
　　通常表示为：
κ(x1,x2)=<Φ(x1),Φ(x2)>(1)$\begin{array}{}\text{(1)}& \kappa (x_1,x_2)=<\mathrm{\Phi }(x_1),\mathrm{\Phi }(x_2)>\end{array}$
　　从而有：

∥Φ(xi)−Φ(xj)∥2=<Φ(x1)−Φ(x2),Φ(x1)−Φ(x2)>=<Φ(x1),Φ(x1)>−2<Φ(x1),Φ(x2)>+<Φ(x2),Φ(x2)>=κ(x1,x1)−2κ(x1,x2)+κ(x2,x2)(2)$$\begin{array}{}\text{(2)}& \begin{array}{ll}{\Vert \mathrm{\Phi }(x_i)-\mathrm{\Phi }(x_j)\Vert }^2& =<\mathrm{\Phi }(x_1)-\mathrm{\Phi }(x_2),\mathrm{\Phi }(x_1)-\mathrm{\Phi }(x_2)>\\ & =<\mathrm{\Phi }(x_1),\mathrm{\Phi }(x_1)>-2<\mathrm{\Phi }(x_1),\mathrm{\Phi }(x_2)>+<\mathrm{\Phi }(x_2),\mathrm{\Phi }(x_2)>\\ & =\kappa (x_1,x_1)-2\kappa (x_1,x_2)+\kappa (x_2,x_2)\end{array}\end{array}$$

　　不得不感叹核函数简直是一个完美的设计！

1.2 为什么说高斯核函数将原始特征空间映射成了无限维空间

　　先看一个多项式核的例子。
　　取κ(x,z)=<x,z>2$\kappa (x,z)=<x,z{>}^2$，这里x=(x1 x2),z=(z1z2)∈R2$x=\left(\begin{array}{l}{x}_1{x}_2\end{array}\right),z=\left(\begin{array}{l}{z}_1\\ z_2\end{array}\right)\in R^2$，故有：

κ(x,z)=<x,z>2=(x1z1+x2z2)2=(x1z1)2+2x1x2z1z2+(x2z2)2(3)$$\begin{array}{}\text{(3)}& \begin{array}{ll}\kappa (x,z)& =<x,z{>}^2\\ & =(x_1{z}_1+x_2{z}_2{)}^2\\ & =(x_1{z}_1{)}^2+2x_1{x}_2{z}_1{z}_2+(x_2{z}_2{)}^2\end{array}\end{array}$$

　　取Φ(x)=(x21, x1x2, x22)$\mathrm{\Phi }(x)=\left(\begin{array}{l}{x}_1^2,x_1{x}_2,x_2^2\end{array}\right)$，则有κ(x,z)=<Φ(x),Φ(z)>$\kappa (x,z)=<\mathrm{\Phi }(x),\mathrm{\Phi }(z)>$成立。也就是说此时映射函数将二维特征空间(x1x2)$\left(\begin{array}{l}{x}_1\\ x_2\end{array}\right)$映射成了三维空间⎛⎝⎜x21x1x2x22⎞⎠⎟$\left(\begin{array}{l}{x}_1^2\\ x_1{x}_2\\ x_2^2\end{array}\right)$，即Φ:R2→R3$\mathrm{\Phi }:R^2\to R^3$。
　　然后再回过头来看高斯核函数：
κ(x,z)=exp(−∥x−z∥22σ2)(4)$\begin{array}{}\text{(4)}& \kappa (x,z)=\exp (-\frac{{\Vert x-z\Vert }^2}{2{\sigma }^2})\end{array}$
　　高等数学中，我们学过，应用泰勒展开，有：
ex=1+x1!+x22!+x33!+… =∑n=0∞xnn!(5)$\begin{array}{}\text{(5)}& \begin{array}{l}{e}^x=1+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots =\sum _{n=0}^{\mathrm{\infty }}\frac{x^n}{n!}\end{array}\end{array}$
　　所以我们有：

κ(x,z)=exp(−∥x−z∥22σ2)=exp[−12σ2<x−z,x−z>]=exp[−12σ2(∥x∥2+∥z∥2−2xTz)]=exp(γ∥x∥2)∗exp(γ∥z∥2)∗exp(−2γxTz),γ=−12σ2(6)$$\begin{array}{}\text{(6)}& \begin{array}{ll}\kappa (x,z)& =\exp (-\frac{{\Vert x-z\Vert }^2}{2{\sigma }^2})\\ & =\exp [-\frac{1}{2{\sigma }^2}<x-z,x-z>]\\ & =\exp [-\frac{1}{2{\sigma }^2}({\Vert x\Vert }^2+{\Vert z\Vert }^2-2x^{T}z)]\\ & =\exp (\gamma {\Vert x\Vert }^2)\ast \exp (\gamma {\Vert z\Vert }^2)\ast \exp (-2\gamma x^{T}z),\gamma =-\frac{1}{2{\sigma }^2}\end{array}\end{array}$$

　　其中：

exp(γ∥x∥2)=∑n=0∞(γ∥x∥2)nn!=∑n=0∞γn(x21+x22+...x2k)nn!,x=(x1,x2...xk)T(7)$$\begin{array}{}\text{(7)}& \begin{array}{ll}\exp (\gamma {\Vert x\Vert }^2)& =\sum _{n=0}^{\mathrm{\infty }}\frac{{(\gamma {\Vert x\Vert }^2)}^n}{n!}\\ & =\sum _{n=0}^{\mathrm{\infty }}\frac{{\gamma }^n{(x_1^2+x_2^2+...x_k^2)}^n}{n!},x=(x_1,x_2...x_k{)}^T\end{array}\end{array}$$

　　也就是说，exp(γ∥x∥2)$\exp (\gamma {\Vert x\Vert }^2)$含有了无穷多项的多项式，对应的映射函数Φ(⋅)$\mathrm{\Phi }(\cdot )$将k维空间映射成了无限维空间，即： Φ:Rk→R∞$\mathrm{\Phi }:R^k\to R^{\mathrm{\infty }}$。

1.3 高斯核中的参数σ$\sigma$的理解

　　由式子(2)和式子(4)我们可知：
　　情况①：

σ→0,−∥x−z∥22σ2→−∞,κ(x,z)→0(8)$$\begin{array}{}\text{(8)}& \sigma \to 0,-\frac{{\Vert x-z\Vert }^2}{2{\sigma }^2}\to -\mathrm{\infty },\kappa (x,z)\to 0\end{array}$$

|Φ(x)−Φ(z)|2=κ(x,x)−2κ(x,z)+κ(z,z) =2−2κ(x,z) =2(9)$\begin{array}{}\text{(9)}& \begin{array}{l}{\left|\mathrm{\Phi }(x)-\mathrm{\Phi }(z)\right|}^2=\kappa (x,x)-2\kappa (x,z)+\kappa (z,z)=2-2\kappa (x,z)=2\end{array}\end{array}$
　　情况②：

σ→∞,−∥x−z∥22σ2→0,κ(x,z)→1(10)$$\begin{array}{}\text{(10)}& \sigma \to \mathrm{\infty },-\frac{{\Vert x-z\Vert }^2}{2{\sigma }^2}\to 0,\kappa (x,z)\to 1\end{array}$$

|Φ(x)−Φ(z)|2=κ(x,x)−2κ(x,z)+κ(z,z) =2−2κ(x,z) =0(11)$\begin{array}{}\text{(11)}& \begin{array}{l}{\left|\mathrm{\Phi }(x)-\mathrm{\Phi }(z)\right|}^2=\kappa (x,x)-2\kappa (x,z)+\kappa (z,z)=2-2\kappa (x,z)=0\end{array}\end{array}$

　　式子(9)表明：σ$\sigma$很小的情况下，所有映射后的点彼此之间的距离均相等（为2–√$\sqrt{2}$），即不存在聚类现象（聚类直观上理解就是各个点聚在一起，之间的距离较小）。这样一来每个样本点将被单独形成一个分类。
　　式子(11)表明：σ$\sigma$很大的情况下，两个不同的点经过映射后，成为高维空间上的同一个点（相互之间距离为0）。这样一来，所有的样本点将被划分成同一个类，无法区分开来。
　　总结：参数σ$\sigma$越小，分的类别会越细，也就是说越容易导致过拟合；参数σ$\sigma$越大，分的类别会越粗，导致无法将数据区分开来。

2 对于惩罚因子C的理解

　　加入松弛因子ξ(i)$\xi (i)$后，支持向量机优化的目标函数和约束条件为;

min12∥w∥2+C∑i=1nξ(i)s.t.y(i)(wTΦ(x(i))+b)≥1−ξ(i),i=1,2...n(12)$$\begin{array}{}\text{(12)}& \begin{array}{l}min\frac{1}{2}{\Vert w\Vert }^2+C\sum _{i=1}^n\xi (i)\\ s.t.y^{(i)}(w^T\mathrm{\Phi }(x^{(i)})+b)\ge 1-\xi (i),i=1,\mathrm{2...}n\end{array}\end{array}$$

　　为了最小化目标函数：①当C很大时，ξ(i)$\xi (i)$只能趋近于0，也就是说对处于边界之间的样本（只有处于两条边界之间的样本对应的松弛因子ξ(i)$\xi (i)$不为0，边界上（支持向量）和边界内（正确划分的样本）的样本对应的松弛因子ξ(i)$\xi (i)$均为0）的容忍度很低，错分较少，对样本的拟合性较好，但不一定预测效果好；②C的取值小的时候，处于两条边界之间的样本变多，错分的可能性变大，对样本的拟合性下降，但却可能更合理，因为样本之间往往可能带有噪声。
　　从风险的角度来看，C权衡了经验风险（对样本的拟合能力）和结构风险（对测试样本的预测能力）：为使目标函数越小，C越大时，正则化项(ξ(i)$\xi (i)$ )越小，说明结构风险越大，经验风险越小，容易出现过拟合；反之，C越小，模型的复杂度越低，结构风险越小。

3 总结

　　① 高斯核的参数σ$\sigma$取值与样本的划分精细程度有关：σ$\sigma$越小，低维空间中选择的曲线越复杂，试图将每个样本与其他样本都区分开来；分的类别越细，容易出现过拟合；σ$\sigma$越大，分的类别越粗，可能导致无法将数据区分开来，容易出现欠拟合。
　　② 惩罚因子C的取值权衡了经验风险和结构风险：C越大，经验风险越小，结构风险越大，容易出现过拟合；C越小，模型复杂度越低，容易出现欠拟合。