Cross-disciplinary perspectives on meta-learning for algorithm selection

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Cross-disciplinary perspectives on meta-learning for algorithm selection

Full text

Pdf (359 KB)

Source

ACM Computing Surveys (CSUR) archive
Volume 41 , Issue 1 (December 2008) table of contents

Article No. 6

Year of Publication: 2008

ISSN:0360-0300

Author

Kate A. Smith-Miles

Monash University, Australia

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 69, Downloads (12 Months): 679, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1456650.1456656 What is a DOI?

ABSTRACT

The algorithm selection problem [Rice 1976] seeks to answer the question: Which algorithm is likely to perform best for my problem? Recognizing the problem as a learning task in the early 1990's, the machine learning community has developed the field of meta-learning, focused on learning about learning algorithm performance on classification problems. But there has been only limited generalization of these ideas beyond classification, and many related attempts have been made in other disciplines (such as AI and operations research) to tackle the algorithm selection problem in different ways, introducing different terminology, and overlooking the similarities of approaches. In this sense, there is much to be gained from a greater awareness of developments in meta-learning, and how these ideas can be generalized to learn about the behaviors of other (nonlearning) algorithms. In this article we present a unified framework for considering the algorithm selection problem as a learning problem, and use this framework to tie together the crossdisciplinary developments in tackling the algorithm selection problem. We discuss the generalization of meta-learning concepts to algorithms focused on tasks including sorting, forecasting, constraint satisfaction, and optimization, and the extension of these ideas to bioinformatics, cryptography, and other fields.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Achlioptas, D., Naor, A., and Peres, Y. 2005. Rigorous location of phase transitions in hard optimization problems. Nature 435 (Jun.), 759--764.
	2	David W. Aha, Generalizing from case studies: a case study, Proceedings of the ninth international workshop on Machine learning, p.1-10, July 1992, Aberdeen, Scotland, United Kingdom
	3	Ali, S. and Smith, K. A. 2005. Kernel width selection for SVM classification: A meta learning approach. Int. J. Data Warehousing Mining 1, 78--97.
	4	Ali, S. and Smith, K. 2006. On learning algorithm selection for classification. Appl. Soft Comput. 6, 2, 119--138.
	5	Ali, S. and Smith-Miles, K. 2006. A meta-learning approach to automatic kernel selection for support vector machines. Neurocomput. 70, 1-3, 173--186.
	6	Eric Angel , Vassilis Zissimopoulos, On the Hardness of the Quadratic Assignment Problem with Metaheuristics, Journal of Heuristics, v.8 n.4, p.399-414, July 2002 [doi>10.1023/A:1015454612213]
	7	Arinze, B. 1995. Selecting appropriate forecasting models using rule induction. Omega Int. J. Manage. Sci. 22, 6, 647--658.
	8	Bay Arinze , Seung-Lae Kim , Murugan Anandarajan, Combining and selecting forecasting models using rule based induction, Computers and Operations Research, v.24 n.5, p.423-433, May 1997 [doi>10.1016/S0305-0548(96)00062-7]
	9	Warren Armstrong , Peter Christen , Eric McCreath , Alistair P. Rendell, Dynamic Algorithm Selection Using Reinforcement Learning, Proceedings of the International Workshop on on Integrating AI and Data Mining, p.18-25, December 04-05, 2006 [doi>10.1109/AIDM.2006.4]
	10	Asuncion, A and Newman, D.J. 2007. UCI Machine Learning Repository (http://www.ics.uci.edu/~mlearn/MLRepository.html). Irvine, CA: University of California, Department of Information and Computer Science.
	11	Bachelet, V. 1999. Métaheuristiques paralleles hybrides: Application au probleme d'affectation quadratique. Ph.D. dissertation, Universite des Sciences et Technologies de Lille, France. December.
	12	Bensusan, H., Giraud-Carrier, C., and Kennedy, C. 2000. A higher-order approach to meta-learning. In Proceedings of the European Conference on Machine Learning, Workshop on Meta-Learning: Building Automatic Advice Strategies for Model Selection and Method Combination, 109--117.
	13	Hilan Bensusan , Alexandros Kalousis, Estimating the Predictive Accuracy of a Classifier, Proceedings of the 12th European Conference on Machine Learning, p.25-36, September 05-07, 2001
	14	Abraham Bernstein , Foster Provost , Shawndra Hill, Toward Intelligent Assistance for a Data Mining Process: An Ontology-Based Approach for Cost-Sensitive Classification, IEEE Transactions on Knowledge and Data Engineering, v.17 n.4, p.503-518, April 2005 [doi>10.1109/TKDE.2005.67]
	15	Berrer, H., Paterson, I., and Keller, J. 2000. Evaluation of machine-learning algorithm ranking advisors. In Proceedings of the PKDD-00 Workshop on Data Mining, Decision Support, Meta-Learning and ILP: Forum for Practical Problem Presentation and Prospective Solutions, P. Brazdil and A. Jorge, eds.
	16	Borenstein, Y., and Poli, R. 2006. Kolmogorov complexity, optimization and hardness. IEEE Congress on Evol. Comput., 112--119.
	17	Boukeas, G., Halatsis, C., Zissimpoloulos, V., and Stamatopoulos, P. 2004. Measures of instrinsic hardness for constraint satisfaction problem instances. Lecture Notes in Computer Science, vol. 2932, 184--195.
	18	P. B. Brazdil , R. J. Henery, Analysis of results, Machine learning, neural and statistical classification, Ellis Horwood, Upper Saddle River, NJ, 1995
	19	Pavel B. Brazdil , Carlos Soares , Joaquim Pinto Da Costa, Ranking Learning Algorithms: Using IBL and Meta-Learning on Accuracy and Time Results, Machine Learning, v.50 n.3, p.251-277, March 2003 [doi>10.1023/A:1021713901879]
	20	Brodley, C. E. 1993. Addressing the selective superiority problem: Automatic algorithm/model class selection. In Proceedings of the 10th International Machine Learning Conference, 17--24.
	21	Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P., and Schulenburg, S. 2003. Hyper-Heuristics: An emerging direction in modern search technology. In Handbook of Metaheuristics, Glover and Kochenberger, eds. Kluwer Academic, Dordrecht, 457--474.
	22	Castiello, C., Castellano, G., and Fanelli, A. M. 2005. Meta-Data: Characterization of input features for meta-learning. Lecture Notes in Artificial Intelligence, vol. 3558, 457--468.
	23	Philip K. Chan , Salvatore J. Stolfo, On the Accuracy of Meta-learning for Scalable Data Mining, Journal of Intelligent Information Systems, v.8 n.1, p.5-28, Jan./Feb. 1997 [doi>10.1023/A:1008640732416]
	24	Chao-Hsien Chu , Djohan Widjaja, Neural network system for forecasting method selection, Decision Support Systems, v.12 n.1, p.13-24, Aug. 1994 [doi>10.1016/0167-9236(94)90071-X]
	25	Desjardins, M and Gordon, D. F. 1995. Special issue on bias evaluation and selection. Mach. Learn. 20, 1--2.
	26	Duch, W. and Grudzinski, K. 2001. Meta-Learning: Searching in the model space. In Proceedings of the International Conference on Neural Information Processing (ICONIP) I, 235--240.
	27	Vladmir Estivill-Castro , Derick Wood, A survey of adaptive sorting algorithms, ACM Computing Surveys (CSUR), v.24 n.4, p.441-476, Dec. 1992 [doi>10.1145/146370.146381]
	28	Peter W. Frey , David J. Slate, Letter Recognition Using Holland-Style Adaptive Classifiers, Machine Learning, v.6 n.2, p.161-182, March 1991 [doi>10.1023/A:1022606404104]
	29	Furnkranz, J. and Petrak, J. 2001. An evaluation of landmarking variants. In Proceedings of the ECML/PKDD Workshop on Integrating Aspects of Data Mining, Decision Support and Meta-Learning (IDDM), C. Giraud-Carrier et al., eds., 57--68.
	30	Matteo Gagliolo , Jürgen Schmidhuber, Learning dynamic algorithm portfolios, Annals of Mathematics and Artificial Intelligence, v.47 n.3-4, p.295-328, August 2006 [doi>10.1007/s10472-006-9036-z]
	31	João Gama , Pavel Brazdil, Cascade Generalization, Machine Learning, v.41 n.3, p.315-343, Dec. 2000 [doi>10.1023/A:1007652114878]
	32	Joao Gama , Pavel Brazdil, Characterization of Classification Algorithms, Proceedings of the 7th Portuguese Conference on Artificial Intelligence: Progress in Artificial Intelligence, p.189-200, October 03-06, 1995
	33	Glover, F. and Kochenberger, G. 2003. Handbook of Metaheuristics. Kluwer Academic, Dordrecht.
	34	Gnanadesikan, R. 1997. Methods for Statistical Data Analysis of Multivariate Observations, 2nd ed. Wiley, New York.
	35	Haipeng Guo , William H. Hsu, Algorithm selection for sorting and probabilistic inference: a machine learning-based approach, Kansas State University, Manhattan, KS, 2003
	36	Melanie Hilario, Model Complexity and Algorithm Selection in Classification, Proceedings of the 5th International Conference on Discovery Science, p.113-126, November 24-26, 2002
	37	Holger H. Hoos , Thomas Stützle, Towards a characterisation of the behaviour of stochastic local search algorithms for SAT, Artificial Intelligence, v.112 n.1-2, p.213-232, Aug. 1999 [doi>10.1016/S0004-3702(99)00048-X]
	38	Eric Horvitz , Yongshao Ruan , Carla P. Gomes , Henry A. Kautz , Bart Selman , David Maxwell Chickering, A Bayesian Approach to Tackling Hard Computational Problems, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.235-244, August 02-05, 2001
	39	Hyndman, R. 2002. Time Series Data Library, available from http://www-personal.buseco.monash.edu.au/~hyndman/TSDL/.
	40	Jones, N. and Pevzner, P. 2004. An Introduction to Bioinformatics Algorithms. MIT Press, Cambridge, MA.
	41	Terry Jones , Stephanie Forrest, Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms, Proceedings of the 6th International Conference on Genetic Algorithms, p.184-192, July 15-19, 1995
	42	Kalousis, A. and Hilario, M. 2001. Model selection via meta-learning. International. Journal on AI Tools. 10, 4.
	43	Kalousis, A. and Theoharis, T. 1999. Design, implementation and performance results of an intelligent assistant for classifier selection. Intell. Data Anal. 3, 5, 319--337.
	44	Keogh, E. and Folias, T. 2002. The UCR Time Series Data Mining Archive. http://www.cs.ucr.edu/~eamonn/TSDMA/.
	45	Knowles, J. D. and Corne, D. W. 2002. Towards landscape analysis to inform the design of a hybrid local search for the multiobjective quadratic assignment problem. In Soft Computing Systems: Design, Management and Applications, A. Abraham et al., eds. IOS Press, Amsterdam, 271--279.
	46	T. Kohonen, Self-organization and associative memory: 3rd edition, Springer-Verlag New York, Inc., New York, NY, 1989
	47	Kopf, C., Taylor, C., and Keller, J. 2000. Meta-Analysis: From data characterisation for meta-learning to meta-regression. In Proceedings of the PKDD Workshop on Data Mining, Decision Support, Meta-Learning and ILP, P. Brazdil and A. Jorge, eds.
	48	Kuba, P., Brázdil, P., Soares, C., and Woznica, A. 2002. Exploiting sampling and meta-learning for parameter setting for support vector machines. In Proceedings of the Workshop Learning and Data Mining Associated with Iberamia VIII Iberoamerican Conference on Artificial Intelligence. F. Herrera et al., eds., 209--216.
	49	Lagoudakis, M., Littman, M., and Parr, R. 2001. Selecting the right algorithm. In Proceedings of the AAAI Fall Symposium Series: Using Uncertainty within Computation.
	50	Ler, D., Koprinska, I., and Chawla, S. 2005. Utilising regression-based landmarkers within a meta-learning framework for algorithm selection. In Proceedings of the Workshop on Meta-Learning, 22nd International Conference on Machine Learning (ICML), 44--51.
	51	Kevin Leyton-Brown , Eugene Nudelman , Yoav Shoham, Learning the Empirical Hardness of Optimization Problems: The Case of Combinatorial Auctions, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.556-572, September 09-13, 2002
	52	Leyton-Brown, K., Nudelman, E., Andrew, G., Mcfadden, J., and Shoham, Y. 2003a. A portfolio approach to algorithm selection. In Proceedings of the International Joint Conference on Artificial Intelligence, 1542--1543.
	53	Leyton-Brown, K., Nudelman, E., Andrew, G., Mcfadden, J., and Shoham, Y. 2003b. Boosting as a metaphor for algorithm design. In Proceedings of the Conference on Principles and Practice of Constraint Programming, 899--903.
	54	Tjen-Sien Lim , Wei-Yin Loh , Yu-Shan Shih, A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms, Machine Learning, v.40 n.3, p.203-228, Sept. 2000 [doi>10.1023/A:1007608224229]
	55	Linder, C. and Studer, R. 1999. AST: Support for algorithm selection with a CBR approach. In Proceedings of the 16th International Conference on Machine Learning.
	56	Makridakis, S. and Hibon, M. 2000. The M3-competition: Results, conclusions and implications. Int. J. Forecast. 16, 4, 451--476.
	57	Marom, Y. Zukerman, I., and Japkowicz, N. 2007. A meta-learning approach for selecting between response automation strategies in a help-desk domain. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, 907--912.
	58	Oden Maron , Andrew W. Moore, The Racing Algorithm: Model Selection for Lazy Learners, Artificial Intelligence Review, v.11 n.1-5, p.193-225, Feb. 1997 [doi>10.1023/A:1006556606079]
	59	Peter Merz, Advanced fitness landscape analysis and the performance of memetic algorithms, Evolutionary Computation, v.12 n.3, p.303-325, September 2004 [doi>10.1162/1063656041774956]
	60	Donald Michie , D. J. Spiegelhalter , C. C. Taylor , John Campbell, Machine learning, neural and statistical classification, Ellis Horwood, Upper Saddle River, NJ, 1995
	61	Nudelman, E., Leyton-Brown, K., Hoos, H., Devkar, A., and Shoham, Y. 2004. Understanding random SAT: Beyond the clauses-to-variables ratio. Lecture Notes in Computer Science, vol. 3258, 438--452.
	62	Opitz, D. and Maclin, R. 1999. Popular ensemble methods: An empirical study. J. Artif. Intell. Res. 11, 169--198.
	63	Yonghong Peng , Peter A. Flach , Carlos Soares , Pavel Brazdil, Improved Dataset Characterisation for Meta-learning, Proceedings of the 5th International Conference on Discovery Science, p.141-152, November 24-26, 2002
	64	Peterson, A. H. and Martinez, T. R. 2005. Estimating the potential for combining learning models. In Proceedings of the ICML Workshop on Meta-Learning, 68--75.
	65	Bernhard Pfahringer , Hilan Bensusan , Christophe G. Giraud-Carrier, Meta-Learning by Landmarking Various Learning Algorithms, Proceedings of the Seventeenth International Conference on Machine Learning, p.743-750, June 29-July 02, 2000
	66	Prodromidis, A. L., Chan, P., and Stolfo, S. J. 2000. Meta-Learning in distributed data mining systems: Issues and approaches. In Advances of Distributed Data Mining, H. Kargupta and P. Chan, eds. AAAI Press.
	67	Prudêncio, R. and Ludermir, T. 2004. Meta-Learning approaches to selecting time-series models. Neurocomput. 61, 121--137.
	68	Larry Rendell , Howard Cho, Empirical Learning as a Function of Concept Character, Machine Learning, v.5 n.3, p.267-298, Aug. 1990 [doi>10.1023/A:1022651406695]
	69	Rice, J. R. 1953. Classes of recursively enumerable sets and their decision problems. Trans. Amer. Math. Soc. 89, 29--59.
	70	Rice, J. R. 1976. The algorithm selection problem. Advances in Comput. 15, 65--118.
	71	Samulowitz, H. and Memisevic, R. 2007. Learning to solve QBF. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, 255--260.
	72	Alexander K. Seewald , Johann Petrak , Gerhard Widmer, Hybrid Decision Tree Learners with Alternative Leaf Classifiers: An Empirical Study, Proceedings of the Fourteenth International Florida Artificial Intelligence Research Society Conference, p.407-411, May 21-23, 2001
	73	Bart Selman , David G. Mitchell , Hector J. Levesque, Generating hard satisfiability problems, Artificial Intelligence, v.81 n.1-2, p.17-29, March 1996 [doi>10.1016/0004-3702(95)00045-3]
	74	Shannon, C. E. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27 (Jul., Oct.), 379--423 and 623--656.
	75	Slaney, J. and Walsh, T. 2001. Backbones in optimization and approximation. In Proceedings of the International Joint Conference on Artificial Intelligence.
	76	Smith, K. A., Woo, F., Ciesielski, V., and Ibrahim, R. 2001. Modelling the relationship between problem characteristics and data mining algorithm performance using neural networks. In Smart Engineering System Design: Neural Networks, Fuzzy Logic, Evolutionary Programming, Data Mining, and Complex Systems, C. Dagli et al., eds. ASME Press, 11, 356--362.
	77	Smith, K. A., Woo, F., Ciesielski, V., and Ibrahim, R. 2002. Matching data mining algorithm suitability to data characteristics using a self-organising map. In Hybrid Information Systems, A. Abraham and M. Koppen, M., eds. Physica, Heidelberg, 169--180.
	78	Smith-Miles, K. A. 2008. Towards insightful algorithm selection for optimisation using meta-learning concepts. In Proceedings of the IEEE Joint Conference on Neural Networks. 4118--4124.
	79	Carlos Soares , Johann Petrak , Pavel Brazdil, Sampling-Based Relative Landmarks: Systematically Test-Driving Algorithms Before Choosing, Proceedings of the10th Portuguese Conference on Artificial Intelligence on Progress in Artificial Intelligence, Knowledge Extraction, Multi-agent Systems, Logic Programming and Constraint Solving, p.88-95, December 17-20, 2001
	80	Carlos Soares , Pavel B. Brazdil , Petr Kuba, A Meta-Learning Method to Select the Kernel Width in Support Vector Regression, Machine Learning, v.54 n.3, p.195-209, March 2004 [doi>10.1023/B:MACH.0000015879.28004.9b]
	81	Streeter, M., Golovin, D., and Smith, S. F. 2007. Combining multiple heuristics online. In Proceedings of the 22nd AAAI Conference on Artificial Intelligence, 1197--1203.
	82	Stützle, T. and Fernandes, S. 2004. New benchmark instances for the QAP and the experimental analysis of algorithms. Lecture Notes in Computer Science, vol. 3004, 199--209.
	83	Orestis Telelis , Panagiotis Stamatopoulos, Combinatorial Optimization through Statistical Instance-Based Learning, Proceedings of the 13th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'01), p.203, November 07-09, 2001
	84	Ljupco Todorovski , Hendrik Blockeel , Saso Dzeroski, Ranking with Predictive Clustering Trees, Proceedings of the 13th European Conference on Machine Learning, p.444-455, August 19-23, 2002
	85	Ljupčo Todorovski , Sašo Džeroski, Combining Classifiers with Meta Decision Trees, Machine Learning, v.50 n.3, p.223-249, March 2003 [doi>10.1023/A:1021709817809]
	86	Jano I. van Hemert, Evolving combinatorial problem instances that are difficult to solve, Evolutionary Computation, v.14 n.4, p.433-462, December 2006 [doi>10.1162/evco.2006.14.4.433]
	87	Venkatachalam, A. R. and Sohl, J. E. 1999. An intelligent model selection and forecasting system. Int. J. Forecast. 18, 3, 67--180.
	88	Ricardo Vilalta , Youssef Drissi, A perspective view and survey of meta-learning, Artificial Intelligence Review, v.18 n.2, p.77-95, October 2002 [doi>10.1023/A:1019956318069]
	89	Vollmann, T. E. and Buffa, E. S. 1966. The facility layout problem in perspective. Manage. Sci. 12, 10, 450--468.
	90	Wallace, C. S. and Boulton D. M. 1968. An information measure for classification. Comput. J. 11, 2, 185--194.
	91	Mark Wallace , Joachim Schimpf, Finding the Right Hybrid Algorithm – A Combinatorial Meta-Problem, Annals of Mathematics and Artificial Intelligence, v.34 n.4, p.259-269, April 2002 [doi>10.1023/A:1014450507312]
	92	Wang, X. 2005. Characteristic-Based forecasting for time series data, Ph.D. dissertation, Monash University, Australia.
	93	Xiaozhe Wang , Kate Smith , Rob Hyndman, Characteristic-Based Clustering for Time Series Data, Data Mining and Knowledge Discovery, v.13 n.3, p.335-364, November 2006 [doi>10.1007/s10618-005-0039-x]
	94	Ian H. Witten , Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Second Edition (Morgan Kaufmann Series in Data Management Systems), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
	95	Wolpert, D. and Macready, W. 1997. No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1, 67--82.
	96	David H. Wolpert, Stacked generalization, Neural Networks, v.5 n.2, p.241-259, 1992 [doi>10.1016/S0893-6080(05)80023-1]
	97	Xu, L., Hutter, F., Hoos, H., and Leyton-Brown, K. 2007a. Satzilla-07: The design and analysis of an algorithm portfolio for SAT. In Principles and Practices of Constraint Programming. Lecture Notes in Computer Science, 712--727.
	98	Xu, L., Hoos, H., and Leyton-Brown, K. 2007b. Hierarchical hardness models for SAT. In Principles and Practices of Constraint Programming. Lecture Notes in Computer Science, 696--711.
	99	Yang, J. and Jiu, B. 2006. Algorithm selection: A quantitative approach. Algorithmic Trading II: Precision, control, execution. http://www.itg.com/news_events/papers/AlgoSelection20/.