An evaluation of machine learning in algorithm selection for search problems

Issue title: The Symposium on Combinatorial Search

Article type: Research Article

Authors: Kotthoff, Lars^; | Gent, Ian P. | Miguel, Ian

Affiliations: School of Computer Science, Jack Cole Building, North Haugh, St Andrews, KY16 9SX, UK. E-mails: {larsko, ipg, ianm}@cs.st-andrews.ac.uk

Note: [] Corresponding author. E-mail: [email protected].

Abstract: Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared with other approaches. We compare the performance of a large number of different machine learning techniques from different machine learning methodologies on five data sets of hard algorithm selection problems from the literature. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that there is significant scope for improvement both compared with existing systems and in general. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to achieve good performance in the context of algorithm selection problems. In particular, we show that linear regression and alternating decision trees have a very high probability of achieving better performance than always selecting the single best algorithm.

Keywords: Algorithm selection, machine learning, combinatorial search

DOI: 10.3233/AIC-2012-0533

Journal: AI Communications, vol. 25, no. 3, pp. 257-270, 2012