标签： PRML； 核函数

备注：文中可能存在错误，敬请指正。

声明：本文主要整理思路，原创参考资料列在文末，在此鸣谢。手机端显示公式有问题，pc 端可正常浏览。

一. 预备知识

[1] 向量：\vec{x} =[x_1, x_2, \ldots, x_n]^T, \vec{x} \in R^n

示例: \vec{x} = [1,2,3]^T, \vec{y} = [4,5,6]^T

[2] 内积：<\vec{x}, \vec{y}> = \vec{x} \cdot \vec{y} = \sum_{i=1}^n x_i y_i = x_1 y_1 + x_2 y_2 + x_3 y_3 + \ldots + x_n y_n

示例: <\vec{x}, \vec{y}> = 1 \times 4 + 2 \times 5 + 3 \times 6 = 32

[3] 多项式定理：(x_1 + x_2 + \ldots + x_n)^d = \sum_{k=1}^d \frac{d!}{\alpha_1! \alpha_2! \ldots \alpha_n!} {\prod_{i=1}^nx^{\alpha_i}_i} , \forall a_i \in [0,d], \sum_{k=1}^n \alpha_i = d

示例: (a+b)^3 = \frac{3!}{0!3!}a^0b^3 + \frac{3!}{1!2!}a^1b^2 + \frac{3!}{2!1!}a^2b^1 + \frac{3!}{3!0!}a^3b^0 = b^3 + 3ab^2 + 3a^2b + a^3

[4] 泰勒展开：f(x-a)=\sum_i^n \frac{f^{(i)}(x-a)}{i!} + R_n(x-a)

示例：e^x = \sum_k^\infty \frac{x^k}{k!}

[5] 半正定矩阵： 设A是实对称矩阵。如果对任意的实非零列向量\vec{x}有\vec{x}^TA\vec{x} \geq 0，就称A为半正定矩阵。

二. 场景引入

核函数在支持向量机（SVM）中的应用最为经典，但核函数与SVM并没有直接关系，它们是两个独立的命题.

首先观察SVM分类函数:
svm(\vec{x}) = sign(\sum_{i=1}^n a_i<\vec{x_i}, \vec{x}> + b)
对于新数据，只需要计算支持向量与新数据点之间的内积，即可判断新数据点所属的类别.

Q_0: SVM在低维空间线性不可分，怎么办？

A_0: 第一种思路是设置软间隔（soft margin），而第二种思路则是将低维向量（维度为n）映射至高维空间（维度为d，d \geq n，d可以是+\infty），实现高维空间线性可分，如下图所示.

特征映射

定义 1：高维特征映射函数
\phi_d(\vec{x}) : \vec{x} \in R^n \rightarrow \vec{x\prime} \in R^d , n \leq d \leq +\infty

注意这里的 +\infty 是可以取到的，此时的特征空间称为希尔伯特空间，其将有限维度（< +\infty）的欧式空间维度扩展到了无限维（ +\infty）.

经过特征映射后，SVM分类函数变为:
svm(\vec{x}) = sign(\sum_{i=1}^n a_i <\phi_d(\vec{x_i}), \phi_d(\vec{x})> + b)
以上这个过程可能会存在两个困难:

Q_1. 如何寻找映射函数\phi_d(\vec{x}) ?

Q_2. \phi_d(\vec{x})可能会把低维映射到高维，甚至无穷（+\infty）维，这样就会产生维度灾难，计算内积是不现实的.

可分析上述两步的时间复杂度：

• 向量映射过程：特征高维映射，时间复杂度为O(n^2).
• 内积计算过程：高维度向量内积计算，时间复杂度为O(d^2)，如果映射至+\infty维，则无法计算

事实上，我们并不需要知道\phi_d(\vec{x})的具体形式，真正目标是得到内积<\phi_d(\vec{x_i}), \phi_d(\vec{x})>.

为解决上述困难，我们希望能直接对低维空间向量进行内积计算，但又能达到与上述过程同样的效果. 核函数应运而生.

定义 2：核函数
K_d(\vec{x}, \vec{y}) = \phi_d(\vec{x})^T \cdot \phi_d(\vec{y}) = <\phi_d(\vec{x}), \phi_d(\vec{y})>
从定义可知，核函数是二元函数，其入参是变换之前的两个低维向量，其输出结果与变换之后的两个高维向量的内积计算结果相等.

将定义的核函数代入SVM分类函数中：
svm(\vec{x}) = sign(\sum_{i=1}^n a_i K_d(\vec{x_i}, \vec{x}) + b)

这样就只需要低维空间直接进行计算，避免了构造特征映射函数和高维空间内积计算的“两步走”模式.

那么，问题来了...

Q_3: 如何构造核函数满足等式K_d(\vec{x}, \vec{y}) = \langle \phi_d(\vec{x}), \phi_d(\vec{y}) \rangle ?

A_3: 第4节将会介绍如何构造核函数，我们先验证下利用核函数进行计算这一方案的可行性. 验证思路如下：

Step1. 给定某个核函数，利用核函数定义公式反推得到相应的特征映射函数.
Step2. 利用特征映射函数将原始低维向量映射至高维特征空间，并进行内积计算，得到结果1.
Step3. 利用核函数对始低维向量直接计算，得到结果2.
Step4. 比较结果1和2是否一致，一致说明核函数方案可行，否则不可行.

三. 特征映射

3.1 多项式核函数的特征映射

多项式核函数： K(\vec{x}, \vec{y}) = (\vec{x}^T \cdot \vec{y})^m

问题描述：已知核函数K(\vec{x}, \vec{y})，如何得到相应的高维映射函数\phi_d(\vec{x})？

<\vec{x\prime}, \vec{y\prime}> = K(\vec{x}, \vec{y}) = (\vec{x}^T \cdot \vec{y})^m （多项式核函数）

= (\sum_{i=1}^n x_i y_i)^m

= (x_1 y_1 + x_2 y_2 + x_3 y_3 + \ldots + x_n y_n )^m

= \sum_{k=1}^{m+1} \frac{m!} {\alpha_1! \alpha_2! \ldots \alpha_n!} {\prod_{i=1}^n x^{\alpha_i}_i y^{\alpha_i}_i} , \forall a_i \in [0,m], \sum_{i=1}^n \alpha_i = m （多项式定理）

= \sum_{k=1}^{m+1} (\sqrt{\frac{m!} {\alpha_1! \alpha_2! \dots \alpha_n!}}{\prod_{i=1}^n x^{\alpha_i}_i}) \cdot (\sqrt{\frac{m!}{\alpha_1! \alpha_2! \ldots \alpha_n!}} {\prod_{i=1}^n y^{\alpha_i}_i})（开根号）

= <(\sqrt{\frac{m!}{\alpha_1! \alpha_2! \ldots \alpha_n!}} {\prod_{i=1}^n x^{\alpha_i}_i}) , (\sqrt{\frac{m!}{\alpha_1! \alpha_2! \ldots \alpha_n!}}{\prod_{i=1}^n y^{\alpha_i}_i})> （内积形式）

根据核函数定义，K(\vec{x}, \vec{y}) = <\phi_d(\vec{x}), \phi_d(\vec{y})>

于是，我们找到了m次多项式核函数所对应的特征映射函数：
\phi_d(\vec{x}) = \sqrt{\frac{m!}{\alpha_1! \alpha_2! \ldots \alpha_n!}} {\prod_{i=1}^n x^{\alpha_i}_i} , \forall a_i \in [0,m], \sum_{i=1}^n \alpha_i = m

考虑简单的情况做个验证:

对于二维空间向量（n=2）：\vec{x} =[x_1, x_2]^T , \vec{y} =[y_1, y_2]^T

当m=2时，多项式核函数变为： K(\vec{x}, \vec{y}) = (\vec{x}^T \cdot \vec{y})^2

此时特征映射函数为

\phi_2(\vec{x}) = \sqrt{\frac{2!}{\alpha_1! \alpha_2!}} {\prod_{i=1}^2 x^{\alpha_i}_i} , \forall a_i \in [0,2], \sum_{i=1}^n \alpha_i = 2

=[x^2_1, x^2_2, \sqrt2 x_1 x_2]^T

当原始空间维度为n，多项式核函数中指数m，则映射后的高维空间维度d=\frac{(n+m)!}{n!m!}.

上例中，原始空间维度为n=2，多项式核函数中指数m=2，则映射后的高维空间维度 d=\frac{(n+m)!}{n!m!}=\frac{(2+2)!}{2!2!}=3.

接下来比较两个方案的计算结果，验证一致性.

方案 1: 两步走

Step1: 将低维特征映射到高维空间

\vec{x} =[x_1, x_2]^T \rightarrow \vec{x\prime} = [x^2_1, x^2_2, \sqrt2 x_1 x_2]^T
\vec{y} =[y_1, y_2]^T \rightarrow \vec{y\prime} = [y^2_1, y^2_2, \sqrt2 y_1 y_2]^T
时间复杂度为 O(n^2)

Step2: 在高维空间中进行内积计算

<\vec{x\prime}, \vec{y\prime}> = (\vec{x\prime})^T \vec{y\prime} = [x^2_1, x^2_2, \sqrt2 x_1 x_2] \cdot [y^2_1, y^2_2, \sqrt2 y_1 y_2]^T = x^2_1 y^2_1 + x^2_2 y^2_2 + 2x_1x_2y_1y_2
时间复杂度为 O(d^2)

方案 2: 核函数

<\vec{x\prime}, \vec{y\prime}> = K_2(\vec{x}, \vec{y}) = (\vec{x} \cdot \vec{y})^2 = (\sum_{i=1}^2 x_i y_i)^2 = x^2_1 y^2_1 + x^2_2 y^2_2 + 2x_1x_2y_1y_2
时间复杂度为 O(n)

可以发现，两种方案最终能得到的结果是一样的，但核方法计算效率更高。

3.2 RBF 核函数的特征映射

RBF核函数：K(\vec{x}, \vec{y}) = exp( -\frac{||\vec{x} - \vec{y}||^2}{2\sigma^2} )

= exp(-\frac{1}{2\sigma^2}(\vec{x}-\vec{y})^T(\vec{x}-\vec{y}))

= exp(-\frac{1}{2\sigma^2}(\vec{x}^T\vec{x}+\vec{y}^T\vec{y}-2\vec{y}^T\vec{x}))

= exp(-\frac{1}{2\sigma^2}( ||\vec{x}||^2 + ||\vec{y}||^2 )) \cdot exp(\frac{1}{\sigma^2}\vec{y}^T \cdot \vec{x})

= C \cdot exp(\frac{1}{\sigma^2}\vec{y}^T \cdot \vec{x}) (前面是常数)

= C \cdot \sum_i^\infty \frac{(\frac{1}{\sigma^2}\vec{y}^T\vec{x})^i}{i!} （泰勒展开）

= \sum_i^\infty \frac{C}{\sigma^{2i}i!}(\vec{y}^T \cdot \vec{x})^i （多项式核函数组合）

可见，RBF核函数是所有多项式核函数的线性组合，其将低维空间映射至无限维空间。该实例证明了映射到无穷维空间的可操作性。

然而，上述显示推理高维映射函数的过程较为繁琐.

其实我们并不需要在意这个核函数对应的高维映射函数是什么，核函数已经封装了特征映射和内积计算这两个步骤，并可大大降低计算成本.

接下来回答问题Q_3，如何构造核函数？.

四. 核函数构造

4.1 核函数有效性判定

问题描述：给定一个函数K(\vec{x}, \vec{y})，我们能否使用K(\vec{x}, \vec{y})来代替计算<\phi(\vec{x})^T,\phi(\vec{y})>?

以多项式核函数为例，也就是回答: 给定 K(\vec{x}, \vec{y}) = (\vec{x}^T \cdot \vec{y})^p，能否认为其是一个有效的核函数？

给定训练样本集\{\vec{x_1}, \vec{x_2}, \cdots,\vec{x_m}\}, \forall x_i \in R^n，那么我们可以将任意两个特征向量\vec{x_i}, \vec{x_j}, \forall i, j \in [1, m]代入至K(\vec{x}, \vec{y})，计算得到 K(\vec{x_i}, \vec{x_j}) = (\vec{x_i}^T \cdot \vec{x_j})^p。

对所有特征向量进行计算，可得到一个m*m的核函数矩阵K（Kernel Matrix）.

K = \left[ \begin{matrix} K(\vec{x_1}, \vec{x_1}) & K(\vec{x_1}, \vec{x_2}) & \cdots & K(\vec{x_1}, \vec{x_m}) \\ K(\vec{x_2}, \vec{x_1}) & K(\vec{x_2}, \vec{x_2}) & \cdots & K(\vec{x_2}, \vec{x_m}) \\ \vdots & \vdots & \ddots & \vdots \\ K(\vec{x_m}, \vec{x_1}) & K(\vec{x_m}, \vec{x_2}) & \cdots & K(\vec{x_m}, \vec{x_m}) \ \end{matrix} \right]

如果K(\vec{x}, \vec{y})是一个有效的核函数，那么按照核函数的定义，K(\vec{x_i}, \vec{x_j}) = K(\vec{x_j}, \vec{x_i})，因此核函数矩阵K是一个对称矩阵.

根据矩阵正定性判别定理，若对于任意的向量\vec{z}：

\vec{z}^TK\vec{z} = \sum_i^m \sum_j^m \vec{z_i} \cdot K(\vec{x_i}, \vec{x_j}) \cdot \vec{z_j}

= \sum_i^m \sum_j^m \vec{z_i} \langle \phi(\vec{x_i})^T,\phi(\vec{x_j}) \rangle \vec{z_j} （核函数定义）

= \sum_i^m \sum_j^m \vec{z_i} (\sum_k^d\phi(\vec{x_i})^{(k)} \cdot \phi_k(\vec{x_j})^{(k)} ) \vec{z_j} (高维空间向量内积计算）

= \sum_k^d\sum_i^m \sum_j^m (\vec{z_i} \phi(\vec{x_i})^{(k)} \cdot \phi_k(\vec{x_j})^{(k)}\vec{z_j} )

= \sum_k^d \lgroup \sum_i^m\vec{z_i} \phi(\vec{x_i})^{(k)} \rgroup^2 \geq 0 (利用对称性)

因此，核函数矩阵K是一个半正定矩阵.

根据上述过程，得到必要条件：

如果K(\vec{x}, \vec{y})是一个有效的核函数，那么核函数矩阵K是一个半正定矩阵.

同时，根据Mercer's condition，这也是个充分条件：

如果核函数矩阵K是一个半正定矩阵，那么K(\vec{x}, \vec{y})是一个有效的核函数.

敲黑板划重点：

如果K是一个有效的核函数，当且仅当对于训练样本集\{\vec{x_1}, \vec{x_2}, \cdots,\vec{x_m}\}, \forall x_i \in R^n，其相应的核函数矩阵K是对称半正定的.

4.2 核函数的种类

常用的核函数如下：

线性核函数：K(v_1, v_2) = \langle v_1, v_2 \rangle

多项式核函数: K(v_1, v_2) =( \gamma \langle v_1, v_2 \rangle+c)^n

RBF核函数: K(v_1, v_2) = exp(-\gamma ||v_1 - v_2||^2)

Sigmoid核函数: K(v_1, v_2) = tanh(\gamma \langle v_1, v_2 \rangle + c)

不同的核可以提升到不同种类的高维空间，甚至是无穷维.

Q_4: 在实际应用中，如何选择合适的核函数？

A_4: 尝试选择某类核函数，再根据实际数据进行调参.

五. 应用展示

六. 总结

6.1 优点

1.核函数能大大降低计算量，实现线性可分，其可应用一切存在内积计算的场景，可用来改善存在内积计算的算法.

6.2 缺点

1.如果\phi_d(\vec{x})具有足够高的维数，我们总是有足够的能力来拟合训练集，但是对于测试集的泛化往往不佳.

2.核函数的选择依赖于实际数据，暂时没有通用的方法论.

七. 参考资料

[1] http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988406.html
[2] https://www.zhihu.com/question/24627666