核函数技巧（Kernel Trick）

核函数是另外一类技巧，是指当数据无法线性分类时，可以通过升维或降纬（不过一般是升纬，因为我们处理数据的过程是从低维度慢慢过渡到高纬度空间）的方式，通过数据自身的某些特点，或者映射，使得数据能够在高纬度空间中可分。

上面这段话比较拗口，所以我们来看下面这个例子。

例如对于某二维分类问题，对圆点和方块所表示的样本难以使用简单的一维空间中进行区分，因为如果我们要在一维空间中区分圆点和方块，就需要极为复杂的超平面（hyper plane）完成这个分类。

注意，对于ML任务来说，我们使用到的函数和方法都应该尽量简单而直接，因为这不仅能降低预测函数的过拟合情况，还对于我们设计出「通类」方法极为重要。所以，对于SVM问题，我们的 hyper plane 的表述方程应该尽量是一个 $y=x\cdot w+b$ 的简单一维方程集合。

所以上述问题，自然无法使用 $y=w\cdot x+b$ 进行表述。

那么我们就需要引入一个变换或者映射函数 $K$，使得所有样本点 $p(x_i,y_i)$ 通过 $K$函数可以在高纬空间中，被映射为 $K(x_i,y_i)\Rightarrow \varphi (x_i)\cdot \varphi (x_j)\cdot \varphi (\cdots )$。

于是，当我们升维到某个时候，我们又可以继续沿用原有的线性方程，得到如下表达式：

$$f(x)={\mathbf{w}}^T\varphi (x)+b$$

与之前一样，$\mathbf{w}$ 和 $b$ 都是模型参数，而且它依然从形式上是一个简单的线性方程（组）。所以这里就可能有人看出来，对于SVM问题，最难的部分可能是选取合适的核函数，如果在低维度空间，数据是线性可分的，那么我们只需要引入 梯度下降 算法就可以得到一个还过得去的超平面。

但是如果需要把数据升到高维度空间，比如对于上面这个问题，选取合适的函数处理这个过程就显得特别重要。对于上面这个问题，一个比较可行的核函数是使用 二维高斯函数（2D gaussian function）

该函数式表示为：

$$G(x,y)=\frac{1}{\sqrt{2\pi {\sigma }^2}}{e}^{-\frac{x^2+y^2}{2{\sigma }^2}}$$

只要选取合适的标准差 $\sigma$，就能把上面这种搅在一起的样本数据，「抬升」出合适的样子，然后让我们愉快的使用超平面方程进行分类。除了高斯函数以外，我们还有很多可用的核函数方程，比如 Sigmoid Kernel，Polynomial Kernel 等，关于这些函数的一些具体应用或者表述公式，可以在我的往期文章中找到，也可以在网上搜索一下。

对偶问题 （Dual Problem）

现在我们来深入讨论一下另外一个和SVM有关的问题 —— Dual Problem。在 上一章 中，我们已经介绍过求解最适合超平面，是需要求解方程

$$L=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _i^N{a}_i[y_i({\omega }^T{x}_i+b)-1]$$

这里，$a_i>0$，由拉格朗日约束（Lagrangian Multiplier）得到，关于详细细节可以参考我在上一章中写过的内容。因此，对于求解如上问题 $L$，我们需要做的就是求解 $\min$ 值。

通常，在高数课程中接触到拉格朗日数乘问题都相对简单，只要令 $L=0$，然后分别求解等式中的偏微分就可以得到拉格朗日约束方程的最优解。但是有时候直接用上述思路求解SVM中的问题会比较困难，所以就有人提出利用对称函数来解决问题，只要找到了对称函数的解，也就找到了原函数的解，即：

如果 Primal Problem 的曲线表示原函数 $L$，求解 $L$ 就是找到原函数中最小的点 $P^{\ast }$，如果这个问题比较困难，我们可以将函数反向映射，得到它的对偶函数（Dual Problem）或者你理解为它的对称函数 $D$，如果对称函数有一点 $D^{\ast }$ 使得函数最大，那么该点同时也是P的最小值。

于是SVM的 $L$ 问题

$$\underset{\vec{w},b}{\min }\underset{\vec{a}\ge 0}{\max }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _i^N{a}_i[y_i({\omega }^T{x}_i+b)-1]$$

它的Dual Problem 就可以表示为下面这个函数

$$\underset{\vec{a}\ge 0}{\max }\underset{\vec{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _i^N{a}_i[y_i({\omega }^T{x}_i+b)-1]$$

因此，我们可以得到

$$\frac{\partial L}{\partial w}=w-\sum _i{a}_i{y}_i{x}_i\Rightarrow w=\sum a_i{y}_i{x}_i$$

$$\frac{\partial L}{\partial b}=-\sum a_i{y}_i\Rightarrow \sum a_i{y}_i=0$$

所以，我们就可以求解到极为关键的变量 $a_i$ ！而上式的结果同样可以从原方程得到。

因此当 $a>0$时，如果约束条件存在，那么就可以得到如下方程：

$$\begin{array}{c}\mathbf{w}={\sum }_i{a}_i{y}_i{x}_i\\ b=y-\mathbf{w}\cdot {\mathbf{x}}_{\mathbf{k}}\end{array}$$

不过，我个人觉得对偶问题知道就好，因为在使用具体函数库的时候并不影响。只不过在一些论文或书籍中，我们经常会利用对偶问题，变换函数的表达形式，所以这个要注意一下。