标题： 局部支持向量机的最优学习率 显示英文标题

标题： Optimal Learning Rates for Localized SVMs

摘要： 支持向量机（SVMs）在大规模应用中的一个限制因素是其计算需求随着训练样本数量呈超线性增长。 为了解决这个问题，文献中提出了几种在大型数据集的许多小块上分别训练SVM的方法。 到目前为止，然而，几乎所有这些方法都只进行了经验研究。 此外，它们的动机总是基于计算需求。 在本工作中，我们考虑一种基于输入空间划分的局部SVM方法。 对于这种局部SVM，我们推导了一个一般的oracle不等式。 然后我们将这个oracle不等式应用于使用高斯核的最小二乘回归，并推导出在回归函数的一些标准平滑性假设下本质上是最优的局部学习率。 这给出了第一个使用局部SVM的动机，该动机不是基于计算需求，而是基于对泛化性能的理论预测。 我们进一步为我们的局部SVM方法引入了一种数据相关的参数选择方法，并证明该方法达到了与之前相同的学习率。 最后，我们展示了我们的局部SVM的更大规模实验，表明它在计算需求仅为全局SVM的一小部分的情况下，基本上实现了相同的测试性能。 此外，结果表明，局部SVM的计算需求与普通随机分块方法相似，而达到的测试误差则显著更好。 显示英文摘要

摘要： One of the limiting factors of using support vector machines (SVMs) in large scale applications are their super-linear computational requirements in terms of the number of training samples. To address this issue, several approaches that train SVMs on many small chunks of large data sets separately have been proposed in the literature. So far, however, almost all these approaches have only been empirically investigated. In addition, their motivation was always based on computational requirements. In this work, we consider a localized SVM approach based upon a partition of the input space. For this local SVM, we derive a general oracle inequality. Then we apply this oracle inequality to least squares regression using Gaussian kernels and deduce local learning rates that are essentially minimax optimal under some standard smoothness assumptions on the regression function. This gives the first motivation for using local SVMs that is not based on computational requirements but on theoretical predictions on the generalization performance. We further introduce a data-dependent parameter selection method for our local SVM approach and show that this method achieves the same learning rates as before. Finally, we present some larger scale experiments for our localized SVM showing that it achieves essentially the same test performance as a global SVM for a fraction of the computational requirements. In addition, it turns out that the computational requirements for the local SVMs are similar to those of a vanilla random chunk approach, while the achieved test errors are significantly better.