Advanced Methods for Automated Optimization and Modeling of the Empirical Performance of Highly Parameterized Heuristic Algorithms
Theoretical Computer Science
Final Report Abstract
Algorithmen (als abstraktes Konzept von Software) sind heutzutage essentieller Bestandteil unseres Lebens geworden, bspw. auf dem klassischen PC oder aber auch in Smartphones, Smartwatches, Smart-TVs oder Autos. Dadurch nimmt die Zahl an Algorithmen und möglichen Anwendungsgebieten stetig zu und die Anforderungen an Software-Entwickler werden immer größer. Eine besondere Eigenschaft dabei ist, dass Algorithmen viele Einstellmöglichkeiten (sogenannte Parameter) haben (ähnlich wie Autos mit verschiedenen Motoren, Reifen, Auspuffmodellen o.Ä.) und diese Parameter müssen für unterschiedliche Anwendungsäalle neu eingestellt werden. Beispielsweise muss ein mobiles Betriebssystem auf einem Smartphone anders angepasst werden als auf einem Tablet. Um langwierige und fehleranfallige händische Optimierung dieser Parameter von verschiedensten Algorithmen zu vermeiden, beschäftigt sich die Emmy Noether Gruppe von Prof. Frank Hutter mit der automatischen Optimierung dieser Parameter. Im Rahmen der Emmy-Noether Förderung durch die DFG hat sich Prof. Hutters Gruppe insbesondere mit der Optimierung von Algorithmen fíir kombinatorische Probleme (wie z.B. dem aussagenlogischen Erfüllbarkeitsproblem) beschäftigt, sowie mit Algorithmen des maschinellen Lernens. Während die erste Klasse von Algorithmen hohe Relevanz u.a. in Planung, Logistik, und Verifikation von Software und Hardware hat, ist maschinelles Lernen zu einem weiteren Eckpfeiler der künstlichen Intelligenz geworden und hat in den letzten Jahren beeindruckende Ergebnisse bspw. in Bild- und Spracherkennung gezeigt. Um die Verwendung und Entwicklung solcher Algorithmen durch Parameteroptimierung zu erleichtern, hat Prof. Hutters Gruppe neue Methoden entwickelt, um das automatische Optimieren effizienter zu gestalten, um sich automatisch an gegebene Anwendungsgebiete anzupassen, und um die Verfügbarkeit von parallelen Ressourcen (bspw. Multi-Core, Multi-CPU oder Computer-Cluster) effektiv nutzen zu können. Zudem waren solche Methoden bisher nicht transparent für Nutzer, was manchmal Skepsis an ihren Ergebnissen erzeugte. Um dem entgegen zu treten, entwickelte Prof. Hutters Gruppe neue Methoden, um direkte Einsichten in die Parameteroptimierung zu gewähren, bspw. durch die Analyse der Wichtigkeit einzelner Parameter. Ein fundamentales Problem in der Forschungsgemeinschaft war bisher, dass es keinen einheitlichen Standard fíir Benchmarks gabs, um neue Erkenntnisse fair zu vergleichen. Daher investierte Prof. Hutters Gruppe viel Aufwand darin, Benchmark-Bibliotheken zu entwickeln und zur Verfügung zu stellen, welche es nun Forschern auf der ganzen Welt ermöglichen, ihre Algorithmen in einer wissenschaftlich fundierten und reproduzierbaren Art und Weise zu evaluieren. Dies wird der Forschung auf diesem Gebiet sowohl kurz- als auch langfristig helfen, weiterhin große Fortschritte zu machen und diese auch fundiert belegen zu können.
Publications
- Algorithm runtime prediction: Methods and evaluation. Artificial Intelligence, 206:79–111, 2014
F. Hutter, L. Xu, H. Hoos, and K. Leyton-Brown
(See online at https://doi.org/10.1016/j.artint.2013.10.003) - An efficient approach for assessing hyperparameter importance. In E. Xing and T. Jebara, editors, Proceedings of the 31th International Conference on Machine Learning, (ICML’14), pages 754–762. Omnipress, 2014
F. Hutter, H. Hoos, and K. Leyton-Brown
- Autofolio: An automatically configured algorithm selector. Journal of Artificial Intelligence Research, 53:745–778, 2015
M. Lindauer, H. Hoos, F. Hutter, and T. Schaub
(See online at https://doi.org/10.1613/jair.4726) - Efficient Benchmarking of Hyperparameter Optimizers via Surrogates In B. Bonet and S. Koenig, editors, Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI’15), 2015
K. Eggensperger, F. Hutter, H. Hoos, and K. Leyton-Brown
- ASlib: A benchmark library for algorithm selection. Artificial Intelligence, 237:41–58. 2016
B. Bischl, P. Kerschke, L. Kotthoff, M. Lindauer, Y. Malitsky, A. Frechétte, H. Hoos, F. Hutter, K. Leyton-Brown, K. Tierney, and J. Vanschoren
(See online at https://doi.org/10.1016/j.artint.2016.04.003) - Bayesian optimization in a billion dimensions via random embeddings. Journal of Artificial Intelligence Research, 55:361–387, 2016
Z. Wang, F. Hutter, M. Zoghi, D. Matheson, and N. de Feitas
(See online at https://doi.org/10.1613/jair.4806) - Efficient parameter importance analysis via ablation with surrogates. In S. Singh and S. Markovitch, editors, Proceedings of the Conference on Artificial Intelligence (AAAI’17), pages 773–779. AAAI Press, 2017
A. Biedenkapp, M. Lindauer, K. Eggensperger, C. Fawcett, H. Hoos, and F. Hutter
- The configurable SAT solver challenge (CSSC). Artificial Intelligence. 243:1–25, 2017
F. Hutter, M. Lindauer, A. Balint, S. Bayless, H. H. Hoos, and K. Leyton-Brown
(See online at https://doi.org/10.1016/j.artint.2016.09.006) - Warmstarting of model-based algorithm configuration. In S. McIlraith and K. Weinberger, editors, Proceedings of the Conference on Artificial Intelligence (AAAI’18), pages 1355–1362. AAAI Press, 2018
M. Lindauer and F. Hutter
- Pitfalls and best practices in algorithm configuration. Journal of Artificial Intelligence Research (JAIR), 64:861–893, 2019
K. Eggensperger, M. Lindauer, and F. Hutter
(See online at https://doi.org/10.1613/jair.1.11420)
