Extreme Algorithm Selection with Dyadic Feature Representation

authored by

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.

External Organisation(s)

Paderborn University

Type

Contribution to book/anthology

Volume

12323

Pages

309-324

No. of pages

16

Publication date

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-61527-7_21 (Access: Unknown)