Dual Training of Nonlinear Support Vector Machines on a Budget

机器学习算法从数据中创建预测模型。该学科连接统计学，计算机科学和优化。支持向量机（SVM）已经被确立为标准方法。SVM分类器应用于许多科学和技术领域，例如，在生物信息学、机器人技术、（医学）图像处理等领域，SVM在预算上的训练训练SVM模型需要解决一个优化问题。所建立的标准求解器是一个对偶分解算法。尽管其效率相对较高，但未能跟上可用数据集的快速增长（“大数据”挑战）。这是由于SVM模型的形式，它是基函数的线性扩展，基函数的数量随着数据集的大小而增长。这种基函数数量随着数据集大小的增长已经被确定为大规模数据上有效SVM训练的关键障碍。预算方法是一种相对较新的近似方法。他们定义了一个先验上限上的允许数量的基础功能（预算）。这使得训练算法的迭代速度更快，从而整体减少了运行时间。用户对预算大小的选择定义了每次迭代的计算时间和解决方案精度之间的隐含权衡。正确理解这一价值观是学习成功的关键。因此，这个值对数据（类型）的强烈依赖是有问题的。此外，预算方法目前仅适用于原始优化算法，与标准求解器相比，其收敛速度明显较慢。项目目标该项目的第一个目标是开发具有预算约束的对偶分解求解器。这种方法有望将双标准算法的快速收敛与预算方法的快速迭代结合联合收割机。预期的结果是一个显着减少的计算时间比标准的方法，以及超过原始预算方法。第二个目标是发展的方法，自动调整的预算规模。对这种方法的需求与优化算法无关。预算将被调整，以便它最适合给定的训练时间或目标精度。这两种方法都允许在预算范围内指定一个有意义的和数据独立的SVM训练目标。本项目中开发的算法将通过对收敛行为和近似误差的分析得到支持。一个有效的实现将在自由软件许可证下提供。

Machine learning algorithms create predictive models from data. The discipline connects statistics, computer science, and optimization. Support Vector Machines (SVMs) have been established as a standard method. SVM classifiers are applied in many areas of science and technology, e.g., in bioinformatics, robotics, (medical) image processing, and many more.SVM Training on a BudgetTraining an SVM model requires solving an optimization problem. The established standard solver is a dual decomposition algorithm. Despite its relatively high efficiency it fails to keep up with the rapid growth of available data sets ("big data" challenge). This is due to the form of the SVM model, which is a linear expansion of basis functions, the number of which grows with the size of the data.This growth of the number of basis functions with the data set size has been identified as a key obstacle for efficient SVM training on large-scale data. Budget methods are a relatively recent approximation approach. They define an a priori upper bound on the allowable number of basis functions (the budget). This results in faster iterations of the training algorithm, yielding an overall reduction of the runtime.The choice of the budget size by the user defined an implicit trade-off between computation time per iteration and solution accuracy. Getting this value right is key to the success of learning. Hence the strong dependence of this value on the (type of) data is problematic. Furthermore, budget methods are currently available only for primal optimization algorithms, which converge at a significantly slower rate compared to the standard solver.Project GoalsA first goal of the project is the development of a dual decomposition solver with budget constraint. This approach promises to combine the fast convergence of the dual standard algorithm with fast iterations of the budget approach. The expected result is a significant reduction of computation time over the standard approach as well as over primal budget methods.A second goal is the development of methods for the automatic adjustment of the budget size. The need for such methods is independent of the optimization algorithm. The budget will be adjusted so that it is best suited either given a training time or a target accuracy. Both approaches allow for the specification of a meaningful and data independent goal of SVM training on a budget.The algorithms developed within this project will be underpinned with an analysis of convergence behavior and approximation error. An efficient implementation will be made available under a free software license.