Parallel Support Vector Machine Training on a Budget

机器学习关注的是数据驱动的预测模型的全自动构建。该领域将统计学、计算机科学和优化等学科联系在一起。支持向量机是分类问题的标准方法之一。它们广泛应用于生物信息学、机器人学、医学诊断学和文本分析等科学技术领域。加速了支持向量机的训练。训练一个非线性支持向量机就相当于解决了一个大规模的优化问题。它的变量数量与数据点的数量一致。为了缓解这一问题，文献中提出了多种近似的训练方案。其中，预算方法尤其有希望。通过将模型大小限制在a-优先级定义的限制内，它保证了有限的评估成本。由于它的数据自适应性和对解的高度灵活的表示，它仍然获得了很好的预测精度，这样它就保持了核方法的表达能力。我们最近开发了第一个有预算的对偶分解算法，导致了相对于现有技术的显著加速。另一种快速训练支持向量机的方法是并行化。尽管多年来提出了许多并行训练方案，但直到最近，支持向量机训练才以令人信服的方式并行化：雷神支持向量机解算器通过使用现代图形处理单元(GPU)实现了超过两个数量级的加速。这与利用大规模计算能力GPU进行机器学习的大趋势是一致的。这个硬件平台已经是该领域的主力，这一趋势可以安全地预测到(可预见的)未来。该项目的目标。该项目的一个中心目标是将这些最近的成功结合到一个新的支持向量机训练算法中。新方法将使用ThunderSVM算法的并行方法，同时对预算进行操作，就像我们的双重预算算法所做的那样。当在GPU上以高度并行的方式执行预算求解器的快速迭代时，加速应该成倍增加。虽然这个理想的结果可能有点过于乐观，但我们预计会接近，导致比目前的预算解算器和非预算的ThunderSVM解算器都有非常显著的加速。进一步的目标是将已建立的在线问题缩小和内核缓存的加速技术整合到(并行)预算解算器中。此外，我们的目标是为我们的算法提供理论保证。也许最重要的是，我们将提供专门针对高端GPU硬件的高度调优的开源实现。

Maschine learning is concerned with the data-driven and hence fullyautomated construction of predictive models. The field connects elementsof statistics, computer science, and optimization. Support vectormachines (SVMs) are one of the standard methods, in particular forclassification problems. They are applied in all areas of science andtechnology, e.g., in bioinformatics, robotics, medical diagnostics andtext analysis.Accelerated SVM training.Training an non-linear SVM amounts to solving a large scale optimizationproblem. Its number of variables coincides with the number of datapoints. With many millions of points, machine training becomes acomputationally extremely demanding task.The computational bottleneck is closely related to the unbounded growthof the predictive model and its evaluation cost with the data set size.To mitigate this problem, a wide variety of approximate training schemeswas proposed in the literature. Among these, the budget method isparticularly promising. By limiting the model size to an a-prioridefined limit it guarantees a bounded evaluation cost. It still achievesexcellent prediction accuracy due to its data-adaptive and highlyflexible representation of the solution.This way it retains the expressive power of a kernel method. We haverecently developed the first dual decomposition algorithm with budget,resulting in a significant speed-up over the state of the art.A different route to fast SVM training is parallelization. Despite manyparallel training schemes proposed over the years it was only veryrecently that SVM training was parallelized in a convincing manner: theThunderSVM solver achieves speed-ups of more than two orders ofmagnitude by using modern graphics processing units (GPU). This is inline with the general trend of leveraging the massive computing powerGPUs for machine learning. This hardware platform is already theworkhorse of the field, a trend that can safely be projected into the(foreseeable) future.Project goals.A central goal of the project is to combine these recent successes intoa new SVM training algorithm. The new method will use the parallelapproach of the ThunderSVM algorithm while operating on a budget as itis done in our dual budget algorithm. When executing the fast iterationsof the budget solver in a highly parallel manner on a GPU, then thespeed-ups should multiply. While this ideal result would be slightlyover-optimistic, we expect to come close, resulting in very substantialspeed-ups over present budget solvers as well as over the non-budgetedThunderSVM solver.A further goal is the incorporation of the established speed-uptechniques of online problem shrinking and a kernel cache into the(parallel) budget solver.We furthermore aim to provide theoretical guarantees for our algorithm.Maybe most importantly, we will provide highly tuned open sourceimplementations specialized for high-end GPU hardware.