随机傅里叶特征方法及应用

本文介绍随机傅里叶特征方法，它是为了解决在核函数的应用中，需要计算核矩阵所带来的计算复杂度过高的问题；其思想是将输入数据映射到一个随机的低维特征空间，使其内积运算近似等于所指定的移位不变核的特征空间中的内积，从而使得我们应用线性方法就可以完成各种应用；

该方法获得NIPS 2017 时间检验奖；

背景

在《再生核希尔伯特空间及应用》中，介绍过分布在再生核希尔伯特空间中的嵌入表示以及若干应用，包括两样本检验（MMD距离）、独立性度量（HSIC指标）等；

将低维数据映射到高维空间是常见的思想，而核函数的巧妙之处在于，将无穷维向量内积计算转为计算原空间中的核函数，从而降低计算复杂度；然而我们会注意到，在有关核函数的应用中，需要计算核矩阵（kernel matrix）,其计算复杂度是 （ 表示原数据维度， 表示数据量），这也使得这些方法不适合应用于超大数据集中；

MMD距离：

HSIC指标：

SVM模型：

原理

随机傅里叶特征方法（Random Fourier Features, RFF）的提出是为了解决由于核矩阵计算复杂度高，而无法应用于超大规模数据集的问题；

在RKHS空间中： ，映射函数 将样本点 映射成无穷维向量；RFF的思想在于使用有限维向量去近似，即 ；

RFF方法主要考虑的是移位不变核（shift-invariant kernel），什么是移位不变性质？

如果核函数 值只取决于 ，则称 为移位不变核，表示为 ，其中函数 将 中向量映射为核函数值， 是定值，决定数据的放缩；

高斯核函数 和拉普拉斯核函数 都是移位不变核；

根据Bochner定理，对一个连续函数而言，它是正定的充分必要条件是其傅里叶变换是一个有限的Borel非负测度 ；

我们所说的核函数大部分都是正定核，并且由于测度有限，因此可以通过适当的对函数进行放缩，令测度积分为1，变为概率测度 ；

以高斯核举例，

则其傅里叶变换为

可以发现 本身就是多元正态分布 ，表明它是概率测度； 因此对其进行傅里叶逆变换，可恢复出原函数：

第三个等号，正是由于 是概率测度，因此可以看作是积分求期望的形式；

如何完成第三个等号，有两种映射方式：

• 第一种：由于 和核函数都是实数，因此对于 只关注实数部分，忽略虚部；

  第四个等号使用采样方式近似，从 分布中随机采样出 个 ；

  综上， 可以映射为 的向量形式，向量长度为 ；

• 第二种：纯余弦映射；引入偏置 ，

  ， ；

  证明：

  因此：

  其中第5个等号成立的原因在于， ，因此 ；

  相比于第一种映射方式，第二种只使用余弦进行表示，更加方便，但在算法实现中也需要对 进行均匀采样： ；

应用

回到最开始，随机傅里叶特征方法的提出是为了降低计算复杂度，我们拿HSIC指标举个例子：

HSIC指标是衡量两变量独立性的指标，表示为 ，对其计算需要首先得到核矩阵，复杂度为 ；

用随机傅里叶特征呢？可以表示为 ，有限样本形式为：

出处：[4].

相当于RFF方法是将RKHS空间中的核运算，又转变为欧式空间中的低维向量的内积计算，不需要再计算核矩阵，复杂度降为 ；

总结

随机傅里叶特征方法的提出是为了降低在核函数的应用中，需要计算核矩阵所带来的计算复杂度过高的问题，将RKHS空间中的核运算，近似为欧式空间中的低维向量的内积运算，从而大幅降低计算复杂度；方法适用于位移不变核，原理是基于Bochner定理，通过对核函数适当放缩，使其傅里叶变换为一个概率测度，继而以期望的视角对测度进行傅里叶逆变换将核函数恢复，而期望计算可以由多次随机采样近似，最终得到低维的向量表示；

参考

[1] Rahimi, A., & Recht, B. (2007). Random features for large-scale kernel machines. Advances in neural information processing systems, 20.

[2] Lecture: 4. Dimensionality Reduction and Learning, continued. CMSC 35900

[3] Strobl, E. V., Zhang, K., & Visweswaran, S. (2019). Approximate kernel-based conditional independence tests for fast non-parametric causal discovery. Journal of Causal Inference, 7(1).

[4] Zhang, X., Cui, P., Xu, R., Zhou, L., He, Y., & Shen, Z. (2021). Deep stable learning for out-of-distribution generalization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (pp. 5372-5382).