Home | Publications | BB23

Shapley-Based Feature Selection for Online Algorithm Selection

MCML Authors

Viktor Bengs

Dr.

* Former Member

→ Group Eyke Hüllermeier
Artificial Intelligence and Machine Learning

Abstract

Online algorithm selection concerns the task of designing a dynamic algorithm selector that observes sequentially arriving problem instances of an algorithmic problem class for which it must select a suitable algorithm from a given pool of candidate algorithms. Typically the suitability of a candidate algorithm is determined by its average runtime for solving a problem instance. Recent work has shown that multi-armed bandit algorithms can be leveraged for specifying a suitable algorithm selector by taking available feature information of problem instances into account. In this paper, we investigate whether the performance of these bandit-based selection strategies can be further improved by incorporating feature selection. To this end, we use the concept of Shapley values from cooperative game theory to specify the contribution of the features with respect to the suitability of the candidate algorithms and adapt the bandit-based selection strategies to consider only features with the highest contribution. We present two different Shapley value-based approaches and show empirically that UCB-based bandit selection strategies can be improved, while Thompson sampling-based strategies actually deteriorate in terms of average runtime.

inproceedings

DynXAI @ECML-PKDD 2023

Workshop on Explainable Artificial Intelligence: From Static to Dynamic at the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases. Turin, Italy, Sep 18-22, 2023.