Details zu Publikationen

Extreme Algorithm Selection with Dyadic Feature Representation

verfasst von
Alexander Tornede, Marcel Wever, Eyke Hüllermeier
Abstract

Algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidate algorithms most suitable for a specific instance of an algorithmic problem class, e.g., choosing solvers for SAT problems. Benchmark suites for AS usually comprise candidate sets consisting of at most tens of algorithms, whereas in algorithm configuration (AC) and combined algorithm selection and hyperparameter optimization (CASH) problems the number of candidates becomes intractable, impeding to learn effective meta-models and thus requiring costly online performance evaluations. In this paper, we propose the setting of extreme algorithm selection (XAS), which, despite assuming limited time resources and hence excluding online evaluations at prediction time, allows for considering thousands of candidate algorithms and thereby facilitates meta learning. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic representation, in which both problem instances and algorithms are described in terms of feature vectors. We find this approach to significantly improve over the current state of the art in various metrics.

Externe Organisation(en)
Universität Paderborn
Typ
Beitrag in Buch/Sammelwerk
Band
12323
Seiten
309-324
Anzahl der Seiten
16
Publikationsdatum
2020
Publikationsstatus
Veröffentlicht
Peer-reviewed
Ja
ASJC Scopus Sachgebiete
Theoretische Informatik, Informatik (insg.)
Elektronische Version(en)
https://doi.org/10.1007/978-3-030-61527-7_21 (Zugang: Unbekannt)