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)
-
Heinz Nixdorf Institute
Paderborn University
- Type
- Conference contribution
- Pages
- 309-324
- No. of pages
- 16
- Publication date
- 2020
- Publication status
- Published
- Peer reviewed
- Yes
- ASJC Scopus subject areas
- Theoretical Computer Science, General Computer Science
- Electronic version(s)
-
https://doi.org/10.1007/978-3-030-61527-7_21 (Access:
Closed)