Algorithm Selection as Superset Learning: Constructing Algorithm Selectors from Imprecise Performance Data
 verfasst von
 Jonas Hanselle, Alexander Tornede, Marcel Wever, Eyke Hüllermeier
 Abstract
Algorithm selection refers to the task of automatically selecting the most suitable algorithm for solving an instance of a computational problem from a set of candidate algorithms. Here, suitability is typically measured in terms of the algorithms’ runtimes. To allow the selection of algorithms on new problem instances, machine learning models are trained on previously observed performance data and then used to predict the algorithms’ performances. Due to the computational effort, the execution of such algorithms is often prematurely terminated, which leads to rightcensored observations representing a lower bound on the actual runtime. While simply neglecting these censored samples leads to overly optimistic models, imputing them with precise though hypothetical values, such as the commonly used penalized average runtime, is a rather arbitrary and biased approach. In this paper, we propose a simple regression method based on socalled superset learning, in which rightcensored runtime data are explicitly incorporated in terms of intervalvalued observations, offering an intuitive and efficient approach to handling censored data. Benchmarking on publicly available algorithm performance data, we demonstrate that it outperforms the aforementioned naïve ways of dealing with censored samples and is competitive to established methods for censored regression in the field of algorithm selection.
 Externe Organisation(en)

Universität Paderborn
 Typ
 Beitrag in Buch/Sammelwerk
 Band
 12712
 Seiten
 152163
 Anzahl der Seiten
 12
 Publikationsdatum
 2021
 Publikationsstatus
 Veröffentlicht
 Peerreviewed
 Ja
 ASJC Scopus Sachgebiete
 Theoretische Informatik, Informatik (insg.)
 Elektronische Version(en)

https://doi.org/10.1007/9783030757625_13 (Zugang:
Geschlossen)