论文标题
通过位置敏感的哈希缩放内核脊回归
Scaling up Kernel Ridge Regression via Locality Sensitive Hashing
论文作者
论文摘要
在Rahimi和Recht（2007）的开创性论文中引入的随机binning特征是使用局部敏感哈希近似内核矩阵的有效方法。随机binning功能提供了一种非常简单，有效的方法来近似拉普拉斯内核，但不幸的是，不适用于许多重要类的内核，特别是生成光滑的高斯过程的内核，例如高斯内核和matern内核。在本文中，我们介绍了一个简单的加权版本的随机包装功能，并表明相应的内核函数会生成任何所需平滑度的高斯过程。我们表明，加权的随机包装特征为相应的内核矩阵提供了光谱近似，从而导致核脊回归的有效算法。大规模回归数据集的实验表明，我们的方法优于随机傅立叶特征方法的准确性。
Random binning features, introduced in the seminal paper of Rahimi and Recht (2007), are an efficient method for approximating a kernel matrix using locality sensitive hashing. Random binning features provide a very simple and efficient way of approximating the Laplace kernel but unfortunately do not apply to many important classes of kernels, notably ones that generate smooth Gaussian processes, such as the Gaussian kernel and Matern kernel. In this paper, we introduce a simple weighted version of random binning features and show that the corresponding kernel function generates Gaussian processes of any desired smoothness. We show that our weighted random binning features provide a spectral approximation to the corresponding kernel matrix, leading to efficient algorithms for kernel ridge regression. Experiments on large scale regression datasets show that our method outperforms the accuracy of random Fourier features method.
