论文标题
基于扰动的内核近似框架
A Perturbation-Based Kernel Approximation Framework
论文作者
论文摘要
内核方法是各种数据分析任务中的强大工具。但是，在许多情况下，它们的时间和空间复杂性使它们对于大型数据集使其不切实际。提出了各种内核近似方法来克服此问题，最突出的方法是NyStr {Ö} M方法。在本文中，我们得出了一个基于扰动的核近似框架，基于经典扰动理论的结果。我们为该框架提供了一个错误分析，并证明它实际上概括了NyStr {Ö} M方法及其几种变体。此外，我们表明我们的框架产生了新的内核近似方案，可以调节以利用近似内核矩阵的结构。我们以数值支持我们的理论结果，并证明了我们近似框架在合成和现实世界数据上的优势。
Kernel methods are powerful tools in various data analysis tasks. Yet, in many cases, their time and space complexity render them impractical for large datasets. Various kernel approximation methods were proposed to overcome this issue, with the most prominent method being the Nystr{ö}m method. In this paper, we derive a perturbation-based kernel approximation framework building upon results from classical perturbation theory. We provide an error analysis for this framework, and prove that in fact, it generalizes the Nystr{ö}m method and several of its variants. Furthermore, we show that our framework gives rise to new kernel approximation schemes, that can be tuned to take advantage of the structure of the approximated kernel matrix. We support our theoretical results numerically and demonstrate the advantages of our approximation framework on both synthetic and real-world data.
