Hybrid ranking and regression for algorithm selection

verfasst von

Jonas Hanselle, Alexander Tornede, Marcel Wever, Eyke Hüllermeier

Abstract

Algorithm selection (AS) is defined as the task of automatically selecting the most suitable algorithm from a set of candidate algorithms for a specific instance of an algorithmic problem class. While suitability may refer to different criteria, runtime is of specific practical relevance. Leveraging empirical runtime information as training data, the AS problem is commonly tackled by fitting a regression function, which can then be used to estimate the candidate algorithms’ runtimes for new problem instances. In this paper, we develop a new approach to algorithm selection that combines regression with ranking, also known as learning to rank, a problem that has recently been studied in the realm of preference learning. Since only the ranking of the algorithms is eventually needed for the purpose of selection, the precise numerical estimation of runtimes appears to be a dispensable and unnecessarily difficult problem. However, discarding the numerical runtime information completely seems to be a bad idea, as we hide potentially useful information about the algorithms’ performance margins from the learner. Extensive experimental studies confirm the potential of our hybrid approach, showing that it often performs better than pure regression and pure ranking methods.

Externe Organisation(en)

Universität Paderborn
Heinz Nixdorf Institut (HNI)

Typ

Aufsatz in Konferenzband

Seiten

59-72

Anzahl der Seiten

14

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-58285-2_5 (Zugang: Geschlossen)