随机傅里叶特征(Random Fourier Features)

作者：凯鲁嘎吉 - 博客园 http://www.cnblogs.com/kailugaji/

1. 基本知识

1.1 傅里叶变换与逆傅里叶变换

1.2 平移不变性核

 具有平移不变性的核有：

1.3 Bochner定理

2. 介绍

    随机傅里叶特征方法是一种近似核函数的方法，旨在找到一个低阶的映射函数z(x)，将D维原始数据映射到d维随机特征空间中，随机特征空间中两个特征的内积约等于核函数，即z(x)’z(y)≈k(x,y)=k(x-y)

算法具体流程：

注：我的表述与算法流程中的不一样，我的表述是z：从D->d维。

3. 具体推导

    给定一个平移不变性的核，怎样找到这样的映射z(x)呢？

（1）平移不变性

（2）傅里叶变换与逆傅里叶变换

（3）w~p(w)

（4）e^-iθ=cos(θ)-i*sin(θ)，只取实部

（5）具体推导过程

（6）蒙特卡洛方法

4. 结论

    至此，找到随机映射z(x)，使得原始数据x映射到d维随机特征空间中。

我的理解：

    原先支持向量机(SVM)通过核函数将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分，而问题是这个映射函数没法显式地求出具体表达式，这个特征空间维度不确定，可能很高，甚至是无穷维，为了避免计算映射函数，于是用两个样本在特征空间的内积等于它们在原始样本空间通过函数k(xi,xj)计算的结果来进行计算，这样就不用直接去计算高维甚至无穷维特征空间中的内积。但是当训练样本个数很大时，用SVM求解时间复杂度很高。

    现在是找一个映射函数z来近似原先的映射函数，找到的映射函数z有显式的表达式，z的维度是可以人为控制的，是已知的，这个映射函数与原先的SVM的映射函数相比，维度要低，并且在新的特征空间中训练线性学习器，计算复杂度也比原先的低，在大规模数据集上可以有效提高计算效率。但是随机特征空间维度d的选择是一个值得思考的问题，实验表明，随着随机特征维度的增加，结果越好，这是因为高维度的随机特征能够更好地近似核函数，但维度升高也会导致时间复杂度增加，因此如何在保证结果较好的情况下，又不会使时间复杂度很高，如何选择d，能对我们的结果有利，是一个值得研究的问题。

    文献截图中的-j就是我这里的i。

5. 参考文献

[1] Rahimi and B. Recht, “Random features for large-scale kernel machines,” in Advances in Neural Information Processing Systems 20, pp. 1177–1184, Curran Associates, Inc., 2008.

     代码：https://github.com/kma32527/Random-Fourier-Features

[2] Random Fourier Features  http://gregorygundersen.com/blog/2019/12/23/random-fourier-features

[3] Karris S T. Signals and systems with MATLAB computing and Simulink modeling[M]. Orchard publications, 2007.

[4] 王迎旭. 基于随机特征的多核分布式协同模糊聚类算法研究[D].济南大学,2019.