Dual Training of Nonlinear Support Vector Machines on a Budget

预算内非线性支持向量机的双重训练

• 批准号: 287461288
• 负责人: Professor Dr. Tobias Glasmachers
• 金额: --
• 依托单位: Institut für Neuroinformatik (INI)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/287461288?language=en
• 关键词: Dual; Training; Nonlinear; Support; Vector

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.

机器学习算法从数据中创建预测模型。这门学科将统计学、计算机科学和优化联系在一起。支持向量机已被确立为一种标准方法。支持向量机广泛应用于生物信息学、机器人学、医学图像处理等科学技术领域，训练支持向量机需要解决优化问题。建立的标准求解器是一种对偶分解算法。尽管它的效率相对较高，但它未能跟上可用数据集的快速增长(“大数据”挑战)。这是由于支持向量机模型的形式，它是基函数的线性展开，其数量随着数据集的大小而增长，这种基函数的增长被认为是大规模数据上有效的支持向量机训练的关键障碍。预算方法是一种相对较新的近似方法。它们定义了允许的基函数(预算)的先验上限。用户对预算大小的选择定义了每次迭代的计算时间和解的准确性之间的隐式权衡。正确把握这一价值观是学习成功的关键。因此，该值对(类型)数据的强烈依赖是有问题的。此外，预算方法目前仅适用于原始优化算法，与标准解算器相比，原始优化算法的收敛速度明显较慢。项目目标该项目的第一个目标是开发一个具有预算约束的对偶分解解算器。这种方法承诺将双重标准算法的快速收敛与预算方法的快速迭代相结合。预期的结果是大大缩短计算时间，超过标准方法和原始预算方法。第二个目标是开发自动调整预算数额的方法。这种方法的需要与优化算法无关。预算将进行调整，以便在给定培训时间或目标精确度的情况下最适合。这两种方法都允许在预算内指定有意义的、与数据无关的支持向量机训练目标。在该项目中开发的算法将基于对收敛行为和逼近误差的分析。一个有效的实施将在自由软件许可下可用。