机器算法验证 - 随机厨房水槽如何工作？ - 吾爱随笔录

随机厨房水槽如何工作？

机器算法验证机器学习支持向量机高斯过程近似

2022-01-26 23:58:55

去年在 NIPS 2017 上，Ali Rahimi 和 Ben Recht 凭借他们的论文“大型内核机器的随机特征”获得了时间测试奖，他们介绍了随机特征，后来被编为随机厨房水槽算法。作为宣传他们论文的一部分，他们展示了他们的模型可以在 5 行 matlab 中实现。

% Approximates Gaussian Process regression
%     with Gaussian kernel of variance gamma^2
% lambda: regularization parameter
% dataset: X is dxN, y is 1xN
% test: xtest is dx1
% D: dimensionality of random feature

% training
w = randn(D,d);
b = 2 * pi * rand(D, 1);
Z = cos(gamma * w * X + b * ones(1,N));

alpha = (lambda * eye(D) +Z * Z') \ (Z * y);

% testing
ztest = alpha' * cos(gamma * w * xtest + b);

我不清楚上述算法如何学习任何东西。随机厨房水槽如何工作？它如何逼近高斯过程和支持向量机？

编辑

重温 Rahimi 的演讲，随机厨房水槽一词并没有在他们获奖的论文中介绍，而是在以“大型内核机器的随机特征”开头的论文三部曲的结尾处介绍。其他论文是：

拉希米、阿里和本杰明·雷赫特。“具有随机基数的函数的统一逼近。” 通信、控制和计算，2008 年第 46 届阿勒顿年度会议。IEEE，2008 年。

拉希米、阿里和本杰明·雷赫特。“随机厨房水槽的加权总和：用学习中的随机化代替最小化。” 神经信息处理系统的进展。2009 年。

我认为上面介绍的代码片段是上一篇论文中算法 1 的特化。

1个回答

随机厨房水槽（或随机傅立叶特征）和其他相关方法并不努力执行推理，而是试图减少基于内核的推理方法的瓶颈。

核方法在许多情况下都很棒，但它们通常依赖于矩阵的操作，例如求解线性方程组和找到矩阵行列式。如果矩阵是 $n \times n$ 然后天真地这些计算通常会花费 $O(n^3)$ 这限制了它们可以应用于只有几千个观察值的问题的应用。解决这个瓶颈最流行的方法往往是低秩方法（尽管存在其他方法，例如基于 Kronecker 的方法、H 矩阵和贝叶斯委员会机器等等）。

随机傅里叶特征 (Rehimi & Recht 2007) 考虑通过仅对内核傅里叶分量的随机子集进行采样来创建移位不变内核的低秩近似。由于傅立叶空间是移位不变的，因此保留了该属性，但现在通过这些傅立叶分量的并集形成了一个明确的有限维再现核希尔伯特空间。曾经无限维的 RKHS 由退化的近似核来近似。

代码片段注释：在 5 行中有一些细节被刷过。最重要的是，高斯函数也是傅里叶空间中的高斯函数，只是方差被倒置了。这就是为什么他们从 randn 采样然后乘以方差。然后他们生成 alpha，这只是查找 ztest 的子过程。本质上，正常的内核预测看起来像，

$z_{test} = K(x_{test}, x)(K(x, x) + \lambda I)^{-1} y.$

$z_{test} = \Phi(x_{test})^T\Phi(x)(\Phi(x)^T\Phi(x) + \lambda I)^{-1} y.$

在哪里 $\Phi(\cdot)$ 是评估的随机傅里叶特征向量。

旁注：你应该使用它吗？答案并不明确是的。这完全取决于您要建模的内容。傅立叶空间的使用不一定适用于非平稳非移位不变核。伙计们从未声称它会在这种情况下工作，但如果你刚刚开始在那个领域，有时细微差别并不明显。

其它你可能感兴趣的问题

上一篇为什么累积分布函数 (CDF) 唯一地定义分布？下一篇样条可以用于预测吗？