10.8 SVM核函数原理#
在第10.2节内容中我们简单介绍了SVM中的线性不可分以及核函数的使用示例，在本节内容中我们将基于10.7节中所介绍的SVM权重参数的求解过程来详细介绍核函数的具体原理。
10.8.1 将低维特征映射到高维空间#
在10.2节中我们介绍到，核函数的作用就是将特征从低维空间映射到高维空间中，以此在高维空间中找到一个线性可分的超平面。例如可以通过一个函数$\phi(x)$将一维特征$x$映射到三维特征$x$、$x^2$、$x^3$。根据式(10-70)可知，假如此时已求得${{\alpha }_{i}}$和$b$，那么对一个新输入的样本点其预测结果为
$$ {{w}^{T}}x+b=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}{{x}^{(i)}}x+b=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}\langle {{x}^{(i)}},x\rangle +b \tag{10-119} $$其中${{x}^{(i)}}$表示训练集中的样本点（其实就是支持向量），$x$为新输入的样本点。$\langle a,b\rangle$表示$a$和$b$之间的内积（Inner Product）。当且仅当式(10-119)大于0时，新输入样本$x$的类别为$y=1$。
按照上面提到的通过函数$\phi(x)$将低维映射到高维的思想，只需要在预测时将之前的$x$全部替换成$\phi(x)$，则此时有
$$ y=\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}\langle {{x}^{(i)}},x\rangle +b =\sum\limits_{i=1}^{m}{{{\alpha }_{i}}}{{y}^{(i)}}\langle \phi ({{x}^{(i)}}),\phi (x)\rangle +b \tag{10-120} $$虽然这样一来算是一定程度上解决了SVM中线性不可分的难题，但是又出现了一个新的问题——“维度爆炸”。
假设现有数据集$X$，其样本点${{x}^{(i)}}$有3个维度，分别为$x_{1}^{(i)}$、$x_{2}^{(i)}$、$x_{3}^{(i)}$（下面简写为$x_1$、$x_2$、$x_3$）。现通过函数$\phi(x)$将其映射到某个9维空间中，并且假设映射后的9个维度分别为$x_1x_1$、$x_1x_2$、$x_1x_3$、$x_2x_1$、$x_2x_2$ 、 $x_2x_3$、$x_3x_1$、${{x}_{3}}{{x}_{2}}$、$x_3x_3$。如果此时要对新样本$z$进行预测，则首先需要对$\langle \phi(x),\phi(z)\rangle$进行计算，此时有
$$ \begin{cases} \phi (x)={{[{{x}_{1}}{{x}_{1}},{{x}_{1}}{{x}_{2}},{{x}_{1}}{{x}_{3}},{{x}_{2}}{{x}_{1}},{{x}_{2}}{{x}_{2}},{{x}_{2}}{{x}_{3}},{{x}_{3}}{{x}_{1}},{{x}_{3}}{{x}_{2}},{{x}_{3}}{{x}_{3}}]}^{T}} \\[1ex] \phi (z)={{[{{z}_{1}}{{z}_{1}},{{z}_{1}}{{z}_{2}},{{z}_{1}}{{z}_{3}},{{z}_{2}}{{z}_{1}},{{z}_{2}}{{z}_{2}},{{z}_{2}}{{z}_{3}},{{z}_{3}}{{z}_{1}},{{z}_{3}}{{z}_{2}},{{z}_{3}}{{z}_{3}}]}^{T}} \\[1ex] \langle \phi (x),\phi (z)\rangle =[{{x}_{1}}{{x}_{1}}{{z}_{1}}{{z}_{1}}+{{x}_{1}}{{x}_{2}}{{z}_{1}}{{z}_{2}}+\cdots +{{x}_{3}}{{x}_{3}}{{z}_{3}}{{z}_{3}}] \\ \end{cases}\tag{10-121} $$此时各位读者应该会发现这个过程的计算量太大了，整体复杂度为$O(n^2)$（分别为$O(n^2)$、$O(n^2$)、$O(n)$），其中$n$为特征的维数，因此，若是在高维数据中进行更为复杂的映射，那么整个过程的时间复杂度将不可想象，而这就是“维度爆炸”。但是此时仔细想一想，“映射”和“预测”之间到底是什么关系？“映射”是作为一种思想将低维映射到高维，从而解决线性不可分到可分的问题，而“预测”时所计算的则是$\langle \phi(x),\phi(z)\rangle$，但其实它就是一个值。不管最后采用的是什么样的映射规则，在预测时都只需计算这么一个值，因此，假如能通过某种“黑箱”直接计算出这个值岂不最好？那么有没有这样的“黑箱”呢？当然有，这一“黑箱”操作被称为核技巧（Kernel Trick）。
10.8.2 SVM中的核技巧#
设$\mathcal{X}$是输入空间（欧氏空间$R^n$的子集或离散集合），又设$\mathcal{H}$为特征空间，如果存在一个从$\mathcal{X}$到$\mathcal{H}$的映射$\phi (x):\mathcal{X}\to \mathcal{H}$使对所有$x,z\in\mathcal{X}$，函数$K(x,z)$满足条件$K(x,z)=\phi(x)\cdot\phi(z)$，则称$K(x,z)$为核函数，$\phi(x)$称为映射函数[1]。
说得简单一点，存在某个映射并能够找到一个与之相应的核函数$K(x,z)$来代替计算$\langle \phi(x),\phi(z)\rangle$，从而避免了上面出现“维度爆炸”的问题，因此，核函数可以看作是实现“黑箱”操作（核技巧）的工具。
现假设式(10-121)中的两个样本点分别为$x=(1,2,3)^T,z=(2,3,4)^T$，则此时有
$$ \begin{cases} \phi (x)&={{({{x}_{1}}{{x}_{1}},{{x}_{1}}{{x}_{2}},{{x}_{1}}{{x}_{3}},{{x}_{2}}{{x}_{1}},{{x}_{2}}{{x}_{2}},{{x}_{2}}{{x}_{3}},{{x}_{3}}{{x}_{1}},{{x}_{3}}{{x}_{2}},{{x}_{3}}{{x}_{3}})}^{T}} \\[1ex] & ={{(1\times 1,1\times 2,1\times 3,2\times 1,2\times 2,2\times 3,3\times 1,3\times 2,3\times 3)}^{T}} \\[1ex] \phi (z)&={{({{z}_{1}}{{z}_{1}},{{z}_{1}}{{z}_{2}},{{z}_{1}}{{z}_{3}},{{z}_{2}}{{z}_{1}},{{z}_{2}}{{z}_{2}},{{z}_{2}}{{z}_{3}},{{z}_{3}}{{z}_{1}},{{z}_{3}}{{z}_{2}},{{z}_{3}}{{z}_{3}})}^{T}} \\[1ex] & ={{(2\times 2,2\times 3,2\times 4,3\times 2,3\times 3,3\times 4,4\times 2,4\times 3,4\times 4)}^{T}} \\[1ex] \langle \phi (x),&\phi (z)\rangle ={{({{x}_{1}}{{x}_{1}}{{z}_{1}}{{z}_{1}}+{{x}_{1}}{{x}_{2}}{{z}_{1}}{{z}_{2}}+\cdots +{{x}_{3}}{{x}_{3}}{{z}_{3}}{{z}_{3}})}} \\[1ex] & =4+12+24+12+36+72+24+72+144=400 \end{cases}\tag{10-122} $$同时，还可以通过另外一种方式来计算这个结果
$$ K(x,z)={{({{x}^{T}}z)}^{2}}={{(2+6+12)}^{2}}=400\tag{10-123} $$此时可以发现，虽然式(10-122)与式(10-123)计算得到的结果相同，但是两者的计算过程却大相径庭。前者需要 $O(n^2)$的时间复杂度，但后者只需$O(n)$的时间复杂度。接着可能有读者会疑惑，我们是怎么知道$(x^Tz)^2$等于$\phi(x)\cdot\phi(z)$的呢？下面就是推导
$$ \begin{aligned} & {{({{x}^{T}}z)}^{2}}=\left( \sum\limits_{i=1}^{n}{{{x}_{i}}}{{z}_{i}} \right)\left( \sum\limits_{j=1}^{n}{{{x}_{j}}}{{z}_{j}} \right)=\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{{{x}_{i}}}}{{x}_{j}}{{z}_{i}}{{z}_{j}} \\[1ex] & ={{x}_{1}}{{x}_{1}}{{z}_{1}}{{z}_{1}}+{{x}_{1}}{{x}_{2}}{{z}_{1}}{{z}_{2}}+{{x}_{1}}{{x}_{3}}{{z}_{1}}{{z}_{3}}+\cdots +{{x}_{n}}{{x}_{n}}{{z}_{n}}{{z}_{n}} \\[2ex] & =\phi (x)\cdot \phi (z) \end{aligned}\tag{10-124} $$其实也就是说，我们先进行了推导并知道$(x^Tz)^2$等于$\phi(x)\cdot\phi(z)$，然后在举例过程中才列出了$\phi(x)$这个映射规则，但是话又说回来，我们关心映射规则干什么？我们需要的是映射规则吗？我们需要的不就是这个内积吗？假如我们换成$K(x,z)={{({{x}^{T}}z)}^{5}}$，那么只需计算${{(2+6+12)}^{5}}$的值，而根本不用关心原始特征被映射到了一个什么样的高维空间，并且从一定程度上来讲映射到的空间越高越有利于找到分类决策面，所以我们需要担心的应该是核$K(x,z)$背后所表示的空间是否存在，即核函数的有效性。
10.8.3 从高维到无穷维#
根据上面的介绍，从一定程度上来讲映射到越高维度的空间就越有利于找到分类决策面，因此，一种自然而然的想法就是如果能将原始特征映射到$n$维空间岂不是更好？话虽没错，但这该怎么实现呢？是令$K(x,z)={{({{x}^{T}}z)}^{n}}$吗？要实现从低维到无穷维的映射的方法之一就是借助高斯核函数（Gaussian Kernel）或者称为径向基函数（Radial Basis Function, RBF）[2]。
$$ \begin{aligned} & K(x,z)=\exp \left( \frac{-||x-z|{{|}^{2}}}{2{{\sigma }^{2}}} \right) \\[2ex] & =\exp \left( \frac{-||x|{{|}^{2}}}{2{{\sigma }^{2}}} \right)\exp \left( \frac{-||z|{{|}^{2}}}{2{{\sigma }^{2}}} \right)\exp \left( \frac{\langle x,z\rangle }{{{\sigma }^{2}}} \right) \end{aligned}\tag{10-125} $$不过为什么借助式(10-125)就能实现到无穷维的映射呢？回忆一下泰勒展开就会得出，式(10-125)中第2行第3项的泰勒展开式为
$$ \exp \left( \frac{\langle x,z\rangle }{{{\sigma }^{2}}} \right)=1+\frac{\langle x,z\rangle }{{{\sigma }^{2}}}+\frac{{{\langle x,z\rangle }^{2}}}{2{{\sigma }^{4}}}+\frac{{{\langle x,z\rangle }^{3}}}{3!{{\sigma }^{6}}}+\cdots =\sum_{i=0}^n\frac{{{\langle x,z\rangle }^{n}}}{n!{{({{\sigma }^{2}})}^{n}}} \tag{10-126} $$也就是说，由于泰勒展开的存在，RBF自然也就隐含地实现了从低维到无穷维的映射。
10.8.4 常见核函数#
在实际解决问题的时候，甚至不用关心核函数到底是如何映射的，只需正确选用核函数，以便实现分类的目的。下面是一些常见的核函数，其中使用最为广泛的是高斯核函数[3]。
1. 线性核（Linear Kernel）
$$ K(x,z)=\langle x,z\rangle\tag{10-127} $$2. 多项式核（Polynomial Kernel）
$$ K(x,z)={{(\gamma \langle x,z\rangle +r)}^{d}}\tag{10-128} $$其中，$\gamma >0$为核函数系数； $r$为常数。
3. 高斯核(Gaussian Kernel)
$$ K(x,z)=\exp \left( -\gamma ||x-z|{{|}^{2}} \right)\tag{10-129} $$其中，$\gamma >0$为核函数系数。这里需要注意的是，式(10-129)与式(10-125)虽然在形式上有所差异，但是本质上是一样的，主要是为了保持和sklearn中的形式一致，所以这里我们采用了式(10-129)中的形式。
4. Sigmoid核
$$ K(x,z)=\tanh(\gamma \langle x,z\rangle +r)\tag{10-130} $$其中，$\gamma >0$为核函数系数；$\tanh$为双曲正切函数。
通过10.8.2节内容的讨论可知，我们总希望能够找到一个使样本点线性可分的特征映射空间，因此对于核函数的选择就显得至关重要了。同时需要注意的是，由于核函数仅仅隐式地定义了这个特征空间，所以核函数的选择成为支持向量机最大的变数。
10.8.5 小结#
在本节内容中，我们首先回顾了核函数的目的，并举例说明了如何将特征维度从低维空间映射到高维空间中；接着详细介绍了核函数的基本原理并进一步地说明了为什么使用核函数就能够将低维特征映射到无穷维；最后介绍了SVM中常见的4种核函数的定义。在下一节内容我们将开始用于优化求解SVM的启发式算法序列最小优化算法。