核技巧

核函数

在机器学习领域，点积 $q^{T}k$ 是一种最基础的相似度度量。它只能捕捉向量之间的线性关系（比如方向是否一致）。

而点积，正是“核函数”家族中最简单的一员，我们称之为**线性核。

$$k_{\text{linear}}(x,x^{\prime })=x^T{x}^{\prime }$$

深入“核”心：核技巧的魔力

一旦我们把 $q^{T}k$ 视作一个“可替换”的相似度计算模块，我们就打开了新世界的大门。

核函数，或者说“核技巧”，其核心思想是提供一种非线性的相似度度量。

一个核函数 $k(x,x^{\prime })$，它等价于将原始向量 $x$ 和 $x^{\prime }$ 通过一个（可能非常高维，甚至是无限维）的非线性特征映射 $\varphi (\cdot )$，映射到新的特征空间，然后再计算这个新空间中的内积。

$$k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$$

这个定义的精妙之处在于，我们根本不需要知道 $\varphi (\cdot )$ 究竟长什么样，也不需要真的去执行这个（可能计算量爆炸）的映射。我们只需要能直接计算 $k(x,x^{\prime })$ 的值即可。而核技巧实际上是 Mercer 定理的直接应用。

一个热身练习：二次核的推导

这个过程初看起来可能有些抽象，我们不妨用一个例子来推导一遍，感受一下它的精妙。我们来看一个常见的二次多项式核：

$$k(x,x^{\prime })=(x^T{x}^{\prime }{)}^2$$

假设我们的输入 $x$ 和 $x^{\prime }$ 都是二维向量，即 $x=[x_1,x_2]$ 和 $x^{\prime }=[x_1^{\prime },x_2^{\prime }]$。

我们来试着把这个核函数展开：

$$\begin{array}{rl}k(x,x^{\prime })& =(x_1{x}_1^{\prime }+x_2{x}_2^{\prime }{)}^2\\ & =(x_1{x}_1^{\prime }{)}^2+2(x_1{x}_1^{\prime })(x_2{x}_2^{\prime })+(x_2{x}_2^{\prime }{)}^2\\ & =(x_1^2)(x_1^{\prime 2})+(2x_1{x}_2)(x_1^{\prime }{x}_2^{\prime })+(x_2^2)(x_2^{\prime 2})\end{array}$$

写到这里，我相信大家都能看出点端倪了。这个展开式，不就正是一个内积的形式吗？

如果我们定义一个特征映射 $\varphi (x)$ 如下：

$$\varphi (x)=[x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2]$$

那么，这个 $\varphi (x)$ 和 $\varphi (x^{\prime })$ 在新空间中的内积 $⟨\varphi (x),\varphi (x^{\prime })⟩$ 是：

$$\begin{array}{rl}⟨\varphi (x),\varphi (x^{\prime })⟩& =(x_1^2)(x_1^{\prime 2})+(\sqrt{2}{x}_1{x}_2)(\sqrt{2}{x}_1^{\prime }{x}_2^{\prime })+(x_2^2)(x_2^{\prime 2})\\ & =x_1^2{x}_1^{\prime 2}+2x_1{x}_2{x}_1^{\prime }{x}_2^{\prime }+x_2^2{x}_2^{\prime 2}\end{array}$$

这和我们 $k(x,x^{\prime })$ 的展开式完全一致！

这个发现太重要了。它告诉我们：

1. 我们把原始的2维空间 $x=[x_1,x_2]$ 映射到了3维的特征空间 $\varphi (x)=[x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2]$。
2. 在这个3维空间里计算内积，其结果等价于在原始2维空间里计算 $(x^T{x}^{\prime }{)}^2$。

这就是核技巧的威力：我们根本不需要费力去计算 $\varphi (x)$（当维度非常高时，这几乎是不可能的），我们只需要在原始空间计算 $k(x,x^{\prime })$ 即可。但我们享受到的，却是高维特征空间中的非线性相似性度量。