Dual Training of Nonlinear Support Vector Machines on a Budget

机器学习算法从数据中创建预测模型。这门学科将统计学、计算机科学和最优化联系在一起。支持向量机（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.