Duales Training nichtlinearer Support-Vektor-Maschinen mit Budget
Zusammenfassung der Projektergebnisse
We have designed a fast dual algorithm for non-linear SVM training on a budget. It combines many different components into a single solver: We replace primal BSGD with dual BSCA, incorporate adaptive coordinate frequencies (ACF) for improved working variable selection, speed up merging through a randomization heuristic and a fast lookup, and introduce a robust and reliable stopping criterion. The BSCA algorithm greatly outperform the primal BSGD method as an optimization algorithm (in terms of primal and dual objective function) and as a learning algorithm (in terms of predictive accuracy). The ACF method offers a further speedup, in particular for the dual objective. We can clearly recommend our methods, BSCA and ACF-BSCA, as plug-in replacements for primal methods. It is rather straightforward to extend our algorithms to other kernel machines with boxconstrained dual problems, like regression and some multi-class classification schemes. These achievements make work package 1 a complete success. We have demonstrated that our random-59 search heuristic for merge candidates can speed up budget maintenance by a significant factor. Furthermore, we combine this technique with a fast lookup. With these techniques, we reduce the budget maintenance overhead by about factor 10, to only a few percent of the overall runtime. With these achievements we go beyond the project plan. Finally, we have designed a robust and reliable stopping criterion for dual training with budget. It is related to the KKT-based stopping criterion of exact solvers, but stabilized through aggregation over a full epoch. By performing a logarithmic transformation we obtain a rather robust criterion that works well and reliable across a wise range of data sets. We have not used this stopping criterion as a basis for adjusting the budget size automatically, however, we greatly narrowed down the relevant range for the parameter. Hence, work package 2 is not a complete success, but it delivered a satisfactory result. We have demonstrated empirically that all of the above techniques contribute to a faster and/or more stable training process. Compared to the state-of-the-art BSGD algorithm, the combined improvements in speed and stability are tremendous. They mark significant progress, enabling truly large-scale kernel learning. We have demonstrated these advantages in detail in a several computational studies using standard benchmark problems as well as application problems from the material science domain. This work successfully completes work package 3. Overall, relatively little restructuring was necessary compared to the project plan. We were able to compensate minor deficiencies in work package 2 through additional speed-ups that were not foreseen in the project plan. We therefore rate the project a success. Highlights of the main resutls: • Presentation of the first dual decomposition algorithm for support vector machine training on a budget. • Demonstrate significant speed-ups over primal budgeted training, as well as increased stability. • Implementation of a fast plug-in replacement for the iterative strategy in the merging process. • Design of an adaptive and robust stopping criterion. • An efficient C++ implementation of the dual training algorithm including its most relevant variants, available on github under an open source license.
Projektbezogene Publikationen (Auswahl)
- Multi-Merge Budget Maintenance for Stochastic Coordinate Ascent SVM Training. Artificial Intelligence International Conference., 2018
Sahar Qaadan and Tobias Glasmachers
- Multi-Merge Budget Maintenance for Stochastic Gradient Descent SVM Training. 13th WiML Workshop, Co-located with NeurIPS., 2018
Sahar Qaadan and Tobias Glasmachers
- Speeding Up Budgeted Dual SVM Training with Precomputed GSS. The 23rd Iberoamerican Congress on Pattern Recognition. M. M. G. Ruben Vera-Rodriguez Sergio Velastin & Morales, A., Eds., 2018
Tobias Glasmachers and Sahar Qaadan
- Speeding Up Budgeted Stochastic Gradient Descent SVM Training with Precomputed Golden Section Search. The 4th International Conference on machine Learning, Optimization and Data science - LOD 2018. Nicosia, Pardalos, Giuffrida, Umeton and Sciacca, Eds., 2018
Tobias Glasmachers and Sahar Qaadan
- Dual SVM Training on a Budget. The 8th International Conference in Pattern Recognition Applications and Methods, 2019
Sahar Qaadan, Merlin Schüler and Tobias Glasmachers
