核技巧(The Kernel Trick)

点击量:6972

引言

很多人介绍核技巧时总会扯上SVM,大概是很多人第一次碰到核技巧就是在SVM里吧。其实,核技巧是一个非常纯粹的数学方法,不应该一上来就扯上SVM。因为这个技巧不仅应用在SVM中,还有其他领域也有应用。它解决了数据映射到高维空间之后点积的计算量过于复杂的问题。很多人啰啰嗦嗦说了一大堆,把原本很简单的东西搞的很复杂,其实这玩意很好理解。

问题描述

给定两个向量\(x_i\)和\(x_j\),我们的目标是要计算他们的内积\(I = <x_i, x_j>\)。现在假设我们通过某种非线性变换:

$$
\Phi : x \rightarrow \phi(x)
$$

把他们映射到某一个高维空间中去,那么映射后的向量就变成:\(\phi(x_i)\)和\(\phi(x_j)\),映射后的内积就变成:\(I’ = <\phi(x_j),\phi(x_j)>\)。现在改如何计算映射后的内积呢?传统方法是先计算映射后的向量\(\phi(x_i)\)和\(\phi(x_j)\),然后再计算它俩的内积。但是这样做计算很复杂,因为映射到高维空间后的数据维度很高。比如,假设\(x_i\)和\(x_j\)在映射之后都是一个\( 1 \times 10000\)维的向量,那么他们的内积计算就需要做\(10000\)次加法操作和\(10000\)次乘法操作,显然复杂度很高。于是,数学家们就想出一个办法:能不能在原始空间找到一个函数\(K(x_i,x_j)\)使得\(K(x_i,x_j) = <\phi(x_j),\phi(x_j)>\)呢? 如果这个函数存在,那么我们只需要在低维空间里计算函数\(K(x_i,x_j)\)的值即可,而不需要先把数据映射到高维空间,再通过复杂的计算求解映射后的内积了。庆幸的是,这样的函数是存在的。这样一来计算的复杂度就大大降低了,这种简化计算的方法被称为核技巧(The Kernel Trick),而函数\(K\)就是核函数(Kernel Function)。

与SVM的关系

之前的一篇介绍支持向量机的文章里我们说过:支持向量机为了解决数据在低维度不容易线性分割的情况下,会通过某非线性变换 \(\phi(x)\),将输入空间映射到高维特征空间。于是,就得到如下求解公式:

$$
\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j\phi(x_i)^{T}phi(x_j)-\sum_{i=1}^{N}\alpha_i\\\text{s.t.}\\0\leq\alpha_1\leq C\\ \sum_{i=1}^{N} y_{i}\alpha _{i}=0
$$

观察上面的公式你会发现里面有一个内积运算

$$
\phi \left ( x_{i} \right )^{T}\phi \left ( x_{j} \right )
$$
于是,为了降低计算复杂度,解决映射后可能产生的维度爆炸问题,我们在求解的时候引入了核技巧。核技巧并不仅仅应用在SVM中,在其他需要处理高维映射计算的问题中也有很多应用。

常用的核函数

主要有以下几种:

  • 线性核,其实就是没有映射
    \(\kappa \left ( x_{1},x_{2} \right ) = \left \langle x{1},x{2} \right \rangle\)

  • 高斯核函数,使用最为广泛,它能够把原始特征映射到无穷维。
    \(\kappa \left ( x_{1},x_{2} \right ) = \exp \left ( -\frac{\left | x_{1}-x_{2} \right |^{2}}{2\sigma ^{2}} \right )\)

  • 多项式核函数,它能把数据映射到\(C_{n+d}^{n}\)维。
    \(\kappa \left ( x_{1},x_{2} \right ) = \left ( \left \langle x_{1},x_{2} \right \rangle +R\right )^{d}\)

由此可见:选择什么样的核函数将会决定你把数据映射到什么样的维度。

核函数的满足条件

Mercer 定理:任何半正定的函数都可以作为核函数。所谓半正定的函数\(f(x_i,x_j)\),是指拥有训练数据集合\(x_1,x_2,…x_n\),我们定义一个矩阵的元素\(a_{ij} = f(x_i,x_j)\),这个矩阵是\(n \times n\)的,如果这个矩阵是半正定的,那么\(f(x_i,x_j)\)就称为半正定的函数。

这个mercer定理不是核函数必要条件,只是一个充分条件,即还有不满足mercer定理的函数也可以是核函数。

     

原创不易,如果您觉得本文对您有帮助,可以打赏博主一杯咖啡,鼓励博主持续创作!


  • Ethereum/Polygon/Bsc/Arbitrum: 0xa8c00949fd7dD23b5Ec36A9181966c8C8436A015
  • Bitcoin: bc1qdvf0j0rntarvdal62n35etwmjzwk307w4jtyjz
  •    
  • 支付宝:

  • 核技巧(The Kernel Trick)》上有7条评论

    1. Chloe Wang

      您好:
      请问文中的“假设xi和xj都是一个1×10000维的向量,那么他们的内积计算就需要做10000×10000次乘法操作,显然复杂度很高”,不是很理解为什么是10000×10000次乘法操作呢。内积不是两个向量对应位置上的值相乘求和即可吗,也就是10000次乘法再全部相加。
      盼回复,谢谢!

      回复
      1. fanyy 文章作者

        童鞋你好,感谢你的指正啊,这段描述确实有误,应该是10000次加法和10000次乘法操作。我当时写的时候没仔细想内积是如何运算的,我已改正,多谢。

        回复
    2. Pingback引用通告: smile~

    3. kll

      博主,最近在学习一篇使用再生核希尔伯特空间方法来解决某个实际问题的论文”Model-free inference of diffusion networks using RKHS embeddings”,然后查资料时很荣幸看到你写的这篇关于核技巧的博客,感觉博主对于这个方法应该是很了解的。而正在看的这篇论文里好多公式不知道是怎么来的(论文中的公式17前的一个公式到公式21之间的公式),所以想请教一下博主,想要知道这些公式是怎么推导出来的,需要掌握哪些基础知识呢?

      回复
    4. Pingback引用通告: 机器学习核方法_Python技术站

    fanyy进行回复 取消回复

    邮箱地址不会被公开。 必填项已用*标注