Hybrid Ranking and Regression for Algorithm Selection

authored by

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.

External Organisation(s)

Paderborn University

Type

Contribution to book/anthology

Volume

12325

Pages

59-72

No. of pages

14

Publication date

09.09.2020

Publication status

Published

Peer reviewed

Yes

ASJC Scopus subject areas

Theoretical Computer Science, Computer Science(all)

Electronic version(s)

https://doi.org/10.1007/978-3-030-58285-2_5 (Access: Closed)