6.2.3　随机傅里叶特征近似

随机傅里叶特征（Random Fourier Features，RFF）是一个扩展核方法的有效技术。它利用了连续、移不变的正定核函数（即k（xi，xj）=k（xi-xj））和定理6.3所示的随机过程之间有趣的对偶性。

定理6.3　一个连续的、实值的、对称和移不变的函数在上k（xi-xj）是正定核，当且仅当存在一个在上的有限非负度量使得

其中，是一个在[0，2π]上的均匀分布，我们将基函数记为ϕω（x）。

为了高效计算定理6.3中的积分形式，我们用蒙特卡洛采样对其进行近似：

其中，D是随机傅里叶特征个数；采样自，为了方便表示，将等式中的ωz堆叠为矩阵ω（即）。具体来说，对于RBF核，是一个密度与成正比的高斯分布。对于拉普拉斯核，是一个柯西分布。计算随机特征映射ϕ需要计算原始输入特征的线性组合（即ωTx+b），其是可以纵向划分的。这样的特性使得随机特征近似特别适合联邦学习。