< Back to previous page

Project

Extending Automatic Algorithm Selection to the Online Setting

The goal of this PhD is to extend the methodology of automatic algorithm selection to the online setting. The goal of automatic algorithm selection is to automatically select the best algorithm to solve a problem with. This field of research is motivated by the observation that for many problems in artificial intelligence and operations research no clear best algorithm exists. Rather, each algorithm performs well on some of the problem instances, but not on others. Successful application domains include constraint satisfaction, combinatorial optimisation  and machine-learning (where it is known as meta-learning)

Learning which algorithm is best for which kind of instance is done by identifying instance features: characteristics that correlate with algorithm performance. Once such features have been identified, a set of training instances is collected and each algorithm is run on each of the instances. The performance of each algorithm is observed and this training is used to create a selection map from vectors of instance-feature-values to algorithms. This selection mapping is then used to predict the best algorithm for new instances.

In current automatic algorithm selection approaches the selection mapping remains fixed after the training phase. The motivating observation underlying this PhD is that when the selection mapping is used to predict which algorithm is best for new instances, additional data becomes available. For every new instance an algorithm is selected to solve it with and its performance on the instance becomes known. The main goal of this PhD is to outline and investigate a methodology to use this data to further improve the selection map while it is use, or in other terms online.

A secondary goal is to investigate the exploration vs. exploitation trade-off that arises when bringing automatic algorithm selection into the online world. In standard offline algorithm selection it never makes sense not to select the predicted best algorithm. This is not true in the online setting. On top of obtaining good performance on the current instance, the selection of an algorithm influences the data available for future predictions. It can be beneficial in the long run to suffer an immediate loss in expected performance by selecting a predicted non-best algorithm, if the data so obtained sufficiently improves successive decisions to offset this loss. A trade-off needs to be found between always selecting the predicted best algorithm (exploitation) and considering alternatives (exploration).

This exploration vs. exploitation trade-off is the research-focus of the multi-armed bandit community. A hypothesis of this PhD is that the online automatic algorithm selection problem can be modelled as a contextual multi-armed bandit. If shown to be true, methods from the multi-armed bandit literature can be used to solve it. These methods have the advantage of coming with guarantees on the expected regret. Regret is incurred in the algorithm selection setting every time an algorithm is selected that is not the actual best one for an instance.

Several methods from the multi-armed bandit literature will be tested on standard algorithm selection benchmarks. The goal here is to provide algorithm selection users with a good strategy for using the online data that freely becomes available.

On top of testing the methodology on benchmark problems, it will also be applied to new problems, to which algorithm selection has not yet been applied.

Date:2 Sep 2014 →  15 Sep 2018
Keywords:Online learning, Algorithm Selection, Automatic Algorithm Selection, Multi-armed bandits
Disciplines:Applied mathematics in specific fields, Computer architecture and networks, Distributed computing, Information sciences, Information systems, Programming languages, Scientific computing, Theoretical computer science, Visual computing, Other information and computing sciences, Artificial intelligence, Cognitive science and intelligent systems
Project type:PhD project