Details

Autor(en) / Beteiligte

• Tornede, Alexander
• Hüllermeier, Eyke[Akademischer Betreuer]
• Ngonga Ngomo, Axel-Cyrille[Akademischer Betreuer]
• Lindauer, Marius[Akademischer Betreuer]

Titel

Advanced Algorithm Selection with Machine Learning : Handling Large Algorithm Sets, Learning From Censored Data and Simplifying Meta Level Decisions

Ort / Verlag

Paderborn

Erscheinungsjahr

2023

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 19.06.2023
• ger: Für die meisten rechenintensiven Probleme gibt es eine Vielzahl an Algorithmen, die alle ihre Stärken und Schwächen auf verschiedenen Instanzen der genannten Probleme haben. Dementsprechend sehen sich Anwender ständig mit der Frage kon- frontiert: Welcher Algorithmus sollte für dieses spezielle Problem gewählt werden, um eine hohe Lösungsgüte zu erreichen? Die Forschung auf dem Gebiet der Algorith- menselektion versucht, diese Frage zu beantworten, indem sie Entscheidungsstrate- gien, so genannte Algorithmenselektoren, entwickelt, die einen Algorithmus für eine bestimmte Probleminstanz vorschlagen. Die meisten dieser Selektoren basieren auf datengetriebenen Lernmethoden, die auf Basis aufgezeichneter Evaluationen von Algorithmen auf Probleminstanzen betrieben werden. Obwohl in den letzten Jahrzehnten viele Algorithmenselektoren entwickelt wurden, bleiben die Auswahl aus großen Mengen von Algorithmen, das Lernen auf Basis zensierter Daten, und die Wahl eines geeigneten Algorithmenselektors selbst, wichtige praktische Her- ausforderungen. In dieser Arbeit verbessern wir die praktische Anwendbarkeit der Algorithmenauswahl erheblich, indem wir Fortschritte bei den zugrunde liegenden Methoden des maschinellen Lernens vorschlagen, um die oben genannten Heraus- forderungen zu bewältigen. Insbesondere zeigen wir, dass die Darstellung von Algorithmen in Form von Featurevektoren es ermöglicht, einen Algorithmenselektor effizient zu lernen, der in der Lage ist, aus einer extrem großen Menge von Algo- rithmen auszuwählen. Darüber hinaus nutzen wir Methoden aus dem Bereich der Überlebensanalyse und der mehrarmigen Banditen, um Algorithmenselektoren aus zensierten Daten in Offline- und Online-Settings zu lernen. [...] (shortened due to size constraints)
• eng: There exists a plethora of algorithms for most computationally hard problems, which all have their strengths and weaknesses on different instances of said problems. Correspondingly, practitioners are constantly faced with the question: Which algorithm should be chosen for this particular problem instance to achieve strong performance? Research on algorithm selection tries to answer this question by developing decision policies, called algorithm selectors, prescribing an algorithm for a given problem instance. Most of such selectors are based on data-driven learning methods leveraging recorded evaluations of algorithms on problem instances. Although many algorithm selectors have been developed over the last few decades, selecting from large sets of algorithms, learning from censored data, and choosing an appropriate algorithm selector itself remain important practical challenges. With this thesis, we substantially improve the practical applicability of algorithm selection by suggesting advances to the underlying machine learning methods to cope with the challenges mentioned above. In particular, we demonstrate that representing algorithms in the form of feature vectors enables one to efficiently learn an algorithm selector capable of selecting from an extremely large set of algorithms. Moreover, we leverage methods from the field of survival analysis and multi-armed bandits to let algorithm selectors learn from censored data in offline and online settings. On a more abstract level, we employ ensemble learning techniques to combine multiple algorithm selectors into a single meta selector, reducing the burden of selecting an appropriate algorithm selector for a practitioner and further improving the robustness of algorithm selection. In extensive experimental evaluations on standard algorithm selection benchmarks, we demonstrate the effectiveness of our solutions. ...