AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.3 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Instance-Specific Algorithm Selection via Multi-Output Learning

Kai Chen( ), Yong Dou, Qi Lv, Zhengfa Liang
National Laboratory for Parallel and Distributed Processing, National University of Defense Technology, Changsha 410037, China.
College of Computer, National University of Defense Technology, Changsha 410037, China.
Show Author Information

Abstract

Instance-specific algorithm selection technologies have been successfully used in many research fields, such as constraint satisfaction and planning. Researchers have been increasingly trying to model the potential relations between different candidate algorithms for the algorithm selection. In this study, we propose an instance-specific algorithm selection method based on multi-output learning, which can manage these relations more directly. Three kinds of multi-output learning methods are used to predict the performances of the candidate algorithms: (1) multi-output regressor stacking; (2) multi-output extremely randomized trees; and (3) hybrid single-output and multi-output trees. The experimental results obtained using 11 SAT datasets and 5 MaxSAT datasets indicate that our proposed methods can obtain a better performance over the state-of-the-art algorithm selection methods.

Keywords

performance predictionalgorithm selectionmulti-output learningextremely randomized treesconstraint satisfaction

References

[1]
Kotthoff L., Algorithm selection for combinatorial search problems: A survey, Ai Magazine, vol. 35, no. 3, pp. 48-60, 2012.
Crossref Google Scholar
[2]
Rice J. R., The algorithm selection problem, Advances in Computers, vol. 15, pp. 65-118, 1976.
Crossref Google Scholar
[3]
Xu L., Hutter F., Hoos H., and Leyton-Brown K., Evaluating component solver contributions to portfolio-based algorithm selectors, in Proceedings of the 15th International Conference on Theory and Applications of Satisfiability Testing, 2012, pp. 228-241.
Crossref
[4]
Xu L., Hutter F., and Hoos H. H., SATzilla: Portfolio-based algorithm selection for SAT, Journal of Artificial Intelligence Research, vol. 32, no. 1, pp. 565-606, 2008.
Crossref Google Scholar
[5]
Soos M., Nohl K., and Castelluccia C., Extending sat solvers to cryptographic problems, in International Conference on Theory and Applications of Satisfiability Testing, 2009, pp. 244-257.
Crossref
[6]
Eén N. and Sörensson N., An extensible sat-solver, in Theory and Applications of Satisfiability Testing, 6th International Conference, Santa Margherita Ligure, Italy, 2003, pp. 502-518.
Crossref
[7]
Tsoumakas G., Spyromitros-Xioufis E., Vrekou A., and Vlahavas I., Multi-target regression via random linear target combinations, in ECML PKDD 2014, 2014, pp. 225-240.
Crossref
[8]
Han Z., Liu Y., Zhao J., and Wang W., Real time prediction for converter gas tank levels based on multi-output least square support vector regressor, Control Engineering Practice, vol. 20, no. 3, pp. 1400-1409, 2012.
Crossref Google Scholar
[9]
Aho T., Enko B., eroski S., and Elomaa T., Multi- target regression with rule ensembles, Journal of Machine Learning Research, vol. 13, no. 1, pp. 2367-2407, 2012.
Google Scholar
[10]
O’Mahony E., Hebrard E., Holland A., Nugent C., and O’Sullivan B., Using case-based reasoning in an algorithm portfolio for constraint solving, in Irish Conference on Artificial Intelligence & Cognitive Science, 2013.
[11]
Kadioglu S., Malitsky Y., Sabharwal A., Samulowitz H., and Sellmann M., Algorithm selection and scheduling, in Proceedings of the 17th International Conference on Principles and Practice of Constraint Programming, 2011, pp. 454-469.
Crossref
[12]
Samulowitz H., Reddy C., Sabharwal A., and Sellmann M., Snappy: A simple algorithm portfolio, in Proceedings of the 16th International Conference on Theory and Applications of Satisfiability Testing, 2013, pp. 422-428.
Crossref
[13]
Oentaryo R. J., Handoko S. D., and Lau H. C., Algorithm selection via ranking, in AAAI Conference on Artificial Intelligence, 2015.
[14]
Malitsky Y., Sabharwal A., Samulowitz H., and Sellmann M., Algorithm portfolios based on cost-sensitive hierarchical clustering, in IJCAI’13 Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, 2013, pp. 608-614.
[15]
Godbole S. and Sarawagi S., Discriminative methods for multi-labeled classification, in Advances in Knowledge Discovery and Data Mining, Springer, 2004, pp. 22-30.
Crossref
[16]
Geurts P., Ernst D., and Wehenkel L., Extremely randomized trees, Machine Learning, vol. 63, no. 1, pp. 3-42. 2006.
Crossref Google Scholar
[17]
Hutter F., Xu L., Hoos H. H., and Leyton-Brown K., Algorithm runtime prediction: Methods & evaluation, Artificial Intelligence, vol. 206, pp. 79-111, 2014.
Crossref Google Scholar
[18]
Borchani H., Varando G., Bielza C., and Larraaga P., A survey on multi-output regression, Wiley Interdisciplinary Reviews Data Mining & Knowledge Discovery, vol. 5, no. 5, pp. 216-233, 2015.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 22 Issue 2,
April 2017
Pages 210-217
DOI: 10.23919/TST.2017.7889642
Cite this article:
Chen K, Dou Y, Lv Q, et al. Instance-Specific Algorithm Selection via Multi-Output Learning. Tsinghua Science and Technology, 2017, 22(2): 210-217. https://doi.org/10.23919/TST.2017.7889642

493

Views

17

Downloads

1

Crossref

N/A

Web of Science

2

Scopus

1

CSCD

Altmetrics
Received: 30 April 2016
Revised: 15 June 2016
Accepted: 26 September 2016
Published: 06 April 2017
© The author(s) 2017
Return