当然是2017年获得NeurIPS Test of the Time Award的Random Fourier Feature。
分类问题经常会用把数据project到高维，再做correlation，即计算  。但是由于lifting function  会把数据投到很高维，使得计算内积变得十分昂贵，所以人们发明了kernel trick，即用一个positive definite的function  , 使得  ,这样就避免了计算两个高维向量的内积。但是kernel trick需要计算数据的gram matrix，即  。如果你有一百万条数据的话，计算gram matrix几乎是不可承受的开销。
于是Ali Rahimi 和 Ben Recht在2007年提出了一种randomized 的feature， 即寻找一种mapping  , 使得  。
虽然这也需要计算内积，但是  的维数远小于  的维数。比如常用的Gauss Kernel，其对应的lifting function会把数据map到无穷维，而  的维度D大概只需要  , 其中  是  和  的误差。
这种approximation既避免了计算gram matrix，又不需要计算无穷维向量的内积，而且它还和真实值偏差不大。那么这种好用又实惠的mapping  怎么寻找呢？数学原理是这样的，先做个傅里叶变换：
对，就是找到一个function  , 使得 是它的傅里叶变换（对 做逆变换即可找到 ）。神奇的地方来了，Bochner's theorem 告诉我们，
当且仅当一个连续函数是一个非负测度的傅里叶变换时，这个函数是positive definite function。
这个theorem很拗口，翻译成人话就是如果 是positive definite(这个我们在前面已经保证过了)的，那么 就一定是一个d维的概率分布。现在我们再来看(1)式，其实就是  这个随机变量的期望啊。如果我们定义  ，那(1)式就等价于  。由于这些量都是实数，我们可以舍弃虚部，只保留cos项，于是我们可以定义  ,最终得到  。
于是我们可以通过sample D个  , 带入 和  ,得到2个D维的向量，再用他们做内积，效果和计算 是“几乎”一样好的。（不要忘了之前我们可是得用俩无穷维的向量做内积的- -）
那么问题来了，这个"几乎一样好"大概有多大概率呢？其实通过随机变量的concentration不难证明：
式子很长，但主要就说了一件事，就是random fourier feature“玩砸”的概率，会随着投影维数D的增大，而指数般的减小。当D趋向无穷时，random fourier feature完全等价kernel trick。
PS. 话说Ali Rahimi就是当年在NIPS上怼深度学习是“炼金术”的那个人，后来还和Lecun在twitter上大战。。 |
