Parallel Support Vector Machine Training on a Budget

机器学习关注的是数据驱动的，因此是预测模型的全自动构建。该领域连接了统计学、计算机科学和优化的元素。支持向量机（svm）是一种标准方法，尤其适用于分类问题。它们被应用于所有科学技术领域，例如生物信息学、机器人技术、医学诊断和文本分析。加速SVM训练。训练非线性支持向量机相当于解决一个大规模的优化问题。它的变量数量与数据点的数量一致。由于数以百万计的点，机器训练成为一项计算上极其苛刻的任务。计算瓶颈与预测模型的无界增长及其评估成本随数据集大小的变化密切相关。为了缓解这个问题，文献中提出了各种各样的近似训练方案。其中，预算法尤其有前景。通过将模型大小限制在一个优先定义的极限，它保证了有限的评估成本。由于它的数据自适应和高度灵活的解表示，它仍然达到了很好的预测精度。这样，它保留了内核方法的表达能力。我们最近开发了第一个具有预算的对偶分解算法，从而大大提高了当前技术的速度。另一种快速训练SVM的方法是并行化。尽管多年来提出了许多并行训练方案，但直到最近，SVM训练才以令人信服的方式并行化：thundersvm求解器通过使用现代图形处理单元（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.