核方法 Kernel method

1.内积（点积）

内积，又叫做点积，数量积或标量积。假设存在两个向量$a=[a_1,a_2,...,a_n]$和$b=[b_1,b_2,...,b_n]$，内积的计算方法为：
$$a\cdot b=a_1{b}_1+a_2{b}_2+\cdots +a_n{b}_n$$

2.核方法 ¹

核方法的主要思想是基于这样一个假设：“在低维空间中不能线性分割的点集，通过转化为高维空间中的点集时，很有可能变为线性可分的” ，例如有两类数据，一类为$x<a\cup x>b$；另一部分为$a<x<b$。要想在一维空间上线性分开是不可能的。然而我们可以通过F(x)=(x-a)(x-b)把一维空间上的点转化到二维空间上，这样就可以划分两类数据$F(x)>0$，$F(x)<0$；从而实现线性分割。如下图所示：

定义一个核函数$K(x_1,x_2)=*\varphi (x_1),\varphi (x_2)*$, 其中$x_1$和$x_2$是低维度空间中的点（在这里可以是标量，也可以是向量），$\varphi (x_i)$是低维度空间的点转化为高维度空间中的点的表示，$*,*$表示向量的内积。这里核函数的表达方式一般都不会显式地写为内积的形式，即我们不关心高维度空间的形式。
这里有个很重要的问题，就是我们为什么要关心内积。一般的我们可以把分类或回归问题分为两类：参数学习和基于实例的学习。参数学习就是通过一堆训练数据把模型的参数学习出来，训练完成之后训练数据就没有用了，新数据使用已经训练好的模型进行预测，例如人工神经网络。而基于实例的学习（又叫基于内存的学习)是在预测的时候会使用训练数据，例如KNN算法，会计算新样本与训练样本的相似度。计算相似度一般通过向量的内积来表示。从这里可以看出，核方法不是万能的，它一般只针对基于实例的学习。

3.核方法的定义和例子²

给定一个映射关系$\varphi$，我们定义相应的核函数为:
$$K(x,y)=\varphi (x{)}^T\varphi (y)$$
则内积运算$<\varphi (x),\varphi (y)>$可以用核$K(x,y)$来表示。

例如，给定两个$n$维向量$x$和$y$，$x,y\in {\mathbb{R}}^n$，我们定义一个核函数$K(x,y)=(x^{T}y{)}^2$，将该二次多项式展开会得到如下表达式：$(x_1{y}_1+...+x_n{y}_n{)}^2$。
但$K(x,y)$还可以写成：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ K(x,y)&=(x^{T}…
如果$n$为2的话，即$x^T=(x_1,x_2)$，$y^T=(y_1,y_2)$。若直接对$(x^{T}y{)}^2$进行计算
$$(x^{T}y{)}^2=(x_1{y}_1+x_2{y}_2{)}^2=(x_1{y}_1{)}^2+2x_1{y}_1{x}_2{y}_2+(x_2{y}_2{)}^2$$
如果我们先对$x$和$y$进行映射，$\varphi (x)$可以将$x$映射为：
$$\varphi (x)=\left[\begin{array}{c}{x}_1{x}_1\\ x_1{x}_2\\ x_2{x}_1\\ x_2{x}_2\end{array}\right]$$
$\varphi (y)$可以将$y$映射为：
$$\varphi (y)=\left[\begin{array}{c}{y}_1{y}_1\\ y_1{y}_2\\ y_2{y}_1\\ y_2{y}_2\end{array}\right]$$

然后再对$\varphi (x)$和$\varphi (y)$进行内积运算：
$$<\varphi (x),\varphi (y)>=(x_1{y}_1{)}^2+2x_1{x}_2{y}_1{y}_2+(x_2{y}_2{)}^2$$
我们发现结果和直接展开运算一样，但是直接展开经过了一次平方运算，复杂度为$O(n^2)$，而经过映射之后只需一次内积运算，复杂度为$O(n)$，大大提高了效率。

再比如，对于核函数：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ K(x,y)&=(x^{T}…
同上，若$x$和$y$均为二维向量，则映射函数为:
$$\varphi =\left[\begin{array}{c}{x}_1{x}_1\\ x_1{x}_2\\ x_2{x}_1\\ x_2{x}_2\\ \sqrt{2c}{x}_1\\ \sqrt{2c}{x}_2\end{array}\right]$$
从多项式可以看到，参数$c$控制着一阶和二阶多项式的权重。如果将二阶多项式推广到$d$阶，则核函数$K(x,y)=(x^{T}y+c{)}^d$会将原来的向量映射到$\left(\begin{array}{c}n+d\\ d\end{array}\right)$维，尽管在该空间中的复杂度为$O(n^d)$，但经过$\phi $映射后计算复杂度为$O(n)$。

4. 常见的核方法

常见的三种核方法：
线性核(Linear kernel)：$K(x,y)=x^{T}y$
径向基核(Radial basis function kernel, RBF kernel)：$K(x,y)=exp(-\gamma {\Vert x-y\Vert }^2)$
$d$次多项式核(Polynomial kernel)：$K(x,y)=(x^{T}y+c{)}^d$
下面我们依次使用这些核函数对非线性问题进行分类，如下图所示，有两个待分类标签，显然他们在二维空间是线性不可分的，我们需要使用核函数把它们映射到更高维空间中，让它们线性可分。

4.1 线性核

核函数：
$$K(x,y)=x^{T}y$$
令$x=(x_1,x_2{)}^T$，$y=(y_1,y_2{)}^T$，即维度为2，我们得到：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ K(\begin{pmatr…
可以看到线性核的映射$\varphi (x)$就是$x$本身。

代码：

import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits import mplot3d
from IPython.display import HTML, Image

%matplotlib inline
sns.set()

from sklearn.datasets import make_circles

def feature_map_1(X):
    return np.asarray((X[:,0], X[:,1], X[:,0]*X[:,1])).T

X, y = make_circles(100, factor=.1, noise=.1)
Z = feature_map_1(X)

#2D scatter plot
fig = plt.figure(figsize = (16,8))
ax = fig.add_subplot(1, 2, 1)
ax.scatter(X[:,0], X[:,1], c = y, cmap = 'viridis')
ax.set_xlabel('$x_1$')
ax.set_ylabel('$x_2$')
ax.set_title('Original dataset')

#3D scatter plot
ax = fig.add_subplot(1, 2, 2, projection='3d')
ax.scatter3D(Z[:,0],Z[:,1], Z[:,2],c = y, cmap = 'viridis' ) #,rstride = 5, cstride = 5, cmap = 'jet', alpha = .4, edgecolor = 'none' )
ax.set_xlabel('$z_1$')
ax.set_ylabel('$z_2$')
ax.set_zlabel('$z_3$')
ax.set_title('Transformed dataset')

我们将线性核函数映射后的数据可视化，得到的结果如图3所示，但从结果发现，线性映射之后的数据点仍然不是线性可分的。

4.2 多项式核

二维二阶多项式核函数：

因此，$\varphi (\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right))=\left(\begin{array}{c}\sqrt{2}{x}_1{x}_2\\ x_1^2\\ x_2^2\end{array}\right)$

画出经二阶多项式映射后的数据分布：

import numpy as np
import pandas as pd
import seaborn as sns
from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
from mpl_toolkits import mplot3d
from IPython.display import HTML, Image

#%matplotlib inline
sns.set()

from sklearn.datasets import make_circles

def feature_map_0(X):
    return np.asarray((X[:,0]**2, X[:,1]**2, np.sqrt(2)*X[:,0]*X[:,1])).T

X, y = make_circles(100, factor=.1, noise=.1)
Z = feature_map_0(X)

#2D scatter plot
fig = plt.figure(figsize = (16,8))
ax = fig.add_subplot(1, 2, 1)
ax.scatter(X[:,0], X[:,1], c = y, cmap = 'viridis')
ax.set_xlabel('$x_1$')
ax.set_ylabel('$x_2$')
ax.set_title('Original dataset')

#3D scatter plot
ax = fig.add_subplot(1, 2, 2, projection='3d')
ax.scatter3D(Z[:,0],Z[:,1], Z[:,2],c = y, cmap = 'viridis' ) #,rstride = 5, cstride = 5, cmap = 'jet', alpha = .4, edgecolor = 'none' )
ax.set_xlabel('$z_1$')
ax.set_ylabel('$z_2$')
ax.set_zlabel('$z_3$')
ax.set_title('Transformed dataset')

本文原载于我的简书。

参考