Faster Kernel Interpolation for Gaussian Processes
Faster Kernel Interpolation for Gaussian Processes
复制标题
DOI：
--
复制
发表时间：
2021-01
期刊：
影响因子：
--
通讯作者：
Mohit Yadav;D. Sheldon;Cameron Musco
中科院分区：
文献类型：
--
作者：
Mohit Yadav;D. Sheldon;Cameron Musco
将高斯过程（GP）回归扩展到大规模数据集的一个关键挑战是，精确的推理需要使用密集的n x n核矩阵进行计算，其中n是数据点的数量。重要的工作集中在通过使用较小的m个诱导点集的插值来逼近核矩阵。结构化核插值（SKI）是最具可扩展性的方法之一：通过在密集网格上放置诱导点并使用结构化矩阵代数，SKI实现了近似推理的每次迭代时间为O（n + m log m）。这种n的线性缩放使得可以对非常大的数据集进行推理；然而，代价是每次迭代，这对于极大的n仍然是一个限制。我们表明，通过将SKI重构为解决具有固定m个紧基函数集的自然贝叶斯线性回归问题，在单个O(n)时间预计算步骤后，SKI的每次迭代时间可以减少到O（m log m）。对于固定网格，每次迭代的复杂度与数据集大小n无关，我们的方法可以扩展到真正的大规模数据集。我们在实践中展示了m和n范围内的加速，并将该方法应用于具有超过1亿个点的三维气象雷达数据集的GP推断。
A key challenge in scaling Gaussian Process (GP) regression to massive datasets is that exact inference requires computation with a dense n x n kernel matrix, where n is the number of data points. Significant work focuses on approximating the kernel matrix via interpolation using a smaller set of m inducing points. Structured kernel interpolation (SKI) is among the most scalable methods: by placing inducing points on a dense grid and using structured matrix algebra, SKI achieves per-iteration time of O(n + m log m) for approximate inference. This linear scaling in n enables inference for very large data sets; however the cost is per-iteration, which remains a limitation for extremely large n. We show that the SKI per-iteration time can be reduced to O(m log m) after a single O(n) time precomputation step by reframing SKI as solving a natural Bayesian linear regression problem with a fixed set of m compact basis functions. With per-iteration complexity independent of the dataset size n for a fixed grid, our method scales to truly massive data sets. We demonstrate speedups in practice for a wide range of m and n and apply the method to GP inference on a three-dimensional weather radar dataset with over 100 million points.