【ICML2021】随机傅立叶特征的量化算法

非线性核方法是被工业界广泛应用的重要的机器学习模型之一。由于核函数矩阵的维度正比于数据点个数，大规模数据集在时间和存储上都给直接使用非线性核方法带来极大困难。对于最常见的高斯核函数，随机傅立叶特征（Random Fourier Features, RFF）可以有效地在线性时间内接近非线性核学习的效果，并且不需要直接计算庞大的核函数矩阵，因此成为大规模非线性核学习的重要工具之一。

本文首次通过研究随机傅立叶特征的统计分布，提出基于Lloyd-Max（LM）最小失真准则的量化方法，以此进一步显著减少RFF的存储成本。我们给出LM量化下高斯核函数估计量的一系列严格理论结果，证明LM估计量的正确性和优越性，以及规范化量化后的傅立叶特征可以进一步降低高斯核估计的除偏方差。基于多个大规模数据集的实证分析证明，在平均可降低10倍以上的存储成本的前提下，经LM量化后的特征可以达到使用全精度傅立叶特征的准确率。该方法的表现显著优于过去已提出的随机量化方法。本文为工业级大规模非线性核学习提供了一种存储便利且效果极佳的压缩数据表征方法。

http://proceedings.mlr.press/v139/li21i/li21i.pdf