conference paper
Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis
Alexander
Tornede
author 38209
Marcel Dominik
Wever
author 33176 https://orcid.org/0000-0001-9782-6818
Stefan
Werner
author
Felix
Mohr
author
Eyke
Hüllermeier
author 48129
34
department
355
department
26
department
12th Asian Conference on Machine Learning
SFB 901
project
SFB 901 - Project Area B
project
SFB 901 - Subproject B2
project
Computing Resources Provided by the Paderborn Center for Parallel Computing
project
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, where "suitability" often refers to an
algorithm's runtime. Due to possibly extremely long runtimes of candidate
algorithms, training data for algorithm selection models is usually generated
under time constraints in the sense that not all algorithms are run to
completion on all instances. Thus, training data usually comprises censored
information, as the true runtime of algorithms timed out remains unknown.
However, many standard AS approaches are not able to handle such information in
a proper way. On the other side, survival analysis (SA) naturally supports
censored data and offers appropriate ways to use such data for learning
distributional models of algorithm runtime, as we demonstrate in this work. We
leverage such models as a basis of a sophisticated decision-theoretic approach
to algorithm selection, which we dub Run2Survive. Moreover, taking advantage of
a framework of this kind, we advocate a risk-averse approach to algorithm
selection, in which the avoidance of a timeout is given high priority. In an
extensive experimental study with the standard benchmark ASlib, our approach is
shown to be highly competitive and in many cases even superior to
state-of-the-art AS approaches.
2020Bangkok, Thailand
eng
ACML 2020
A. Tornede, M.D. Wever, S. Werner, F. Mohr, E. Hüllermeier, in: ACML 2020, 2020.
Tornede, Alexander, Marcel Dominik Wever, Stefan Werner, Felix Mohr, and Eyke Hüllermeier. “Run2Survive: A Decision-Theoretic Approach to Algorithm Selection Based on Survival Analysis.” In <i>ACML 2020</i>, 2020.
Tornede A, Wever MD, Werner S, Mohr F, Hüllermeier E. Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis. In: <i>ACML 2020</i>. ; 2020.
Tornede, Alexander, et al. “Run2Survive: A Decision-Theoretic Approach to Algorithm Selection Based on Survival Analysis.” <i>ACML 2020</i>, 2020.
@inproceedings{Tornede_Wever_Werner_Mohr_Hüllermeier_2020, title={Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis}, booktitle={ACML 2020}, author={Tornede, Alexander and Wever, Marcel Dominik and Werner, Stefan and Mohr, Felix and Hüllermeier, Eyke}, year={2020} }
Tornede, A., Wever, M. D., Werner, S., Mohr, F., & Hüllermeier, E. (2020). Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis. <i>ACML 2020</i>. 12th Asian Conference on Machine Learning, Bangkok, Thailand.
A. Tornede, M. D. Wever, S. Werner, F. Mohr, and E. Hüllermeier, “Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis,” presented at the 12th Asian Conference on Machine Learning, Bangkok, Thailand, 2020.
182762020-08-25T12:09:28Z2022-01-06T06:53:28Z