An evaluation of machine learning in algorithm selection for search problems

被引:51
作者
Kotthoff, Lars [1 ]
Gent, Ian P. [1 ]
Miguel, Ian [1 ]
机构
[1] Sch Comp Sci, St Andrews KY16 9SX, Fife, Scotland
基金
英国工程与自然科学研究理事会;
关键词
Algorithm selection; machine learning; combinatorial search; MULTI-ENGINE SOLVER; CLASSIFICATION;
D O I
10.3233/AIC-2012-0533
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
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.
引用
收藏
页码:257 / 270
页数:14
相关论文
共 40 条
[1]  
[Anonymous], P 6 ONL WORLD C SOFT
[2]  
[Anonymous], D91 SECURESCM
[3]  
[Anonymous], 2007, Introduction to Statistical Relational Learning
[4]  
[Anonymous], 2007, ICAPS 2007 WORKSH AI
[5]  
[Anonymous], 2006, P ACMSIGKDD INT C KN
[6]  
[Anonymous], 2003, IJCAI
[7]  
[Anonymous], 2010, 3 WORKSH TECHN IMPL
[8]  
[Anonymous], 2008, IR C ART INT COGN SC
[9]  
Bharat Rao R., 1995, Machine Learning. Proceedings of the Twelfth International Conference on Machine Learning, P471
[10]  
Borrett J. E., 1996, ECAI 96. 12th European Conference on Artificial Intelligence, P160