Proceedings

Algorithm Portfolios Based on Cost-Sensitive Hierarchical Clustering

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 608-613.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Different solution approaches for combinatorial problems often exhibit incomparable performance that depends on the concrete problem instance to be solved. Algorithm portfolios aim to combine the strengths of multiple algorithmic approaches by training a classifier that selects or schedules solvers dependent on the given instance. We devise a new classifier that selects solvers based on a cost-sensitive hierarchical clustering model. Experimental results on SAT and MaxSAT show that the new method outperforms the most effective portfolio builders to date.

  1. [Amadini et al., 2013] Roberto Amadini, Maurizio Gab- brielli, and Jacopo Mauro. An empirical evaluation of portfolios approaches for solving csps. In CPAIOR-2013, 2013.
  2. [Elkan, 2001] Charles Elkan. The foundations of cost- sensitive learning. In IJCAI-01, pages 973-978, 2001.
  3. [Geibel and Wysotzki, 2004] Peter Geibel and Fritz Wysotzki. Learning perceptrons and piecewise lin- ear classifiers sensitive to example dependent costs. Appl. Intell., 21(1):45-56, 2004.
  4. [Gomes and Selman, 2001] C.P. Gomes and B. Selman. Al- gorithm portfolios. Artificial Intelligence Journal, 126(1- 2):43-62, 2001.
  5. [Guyon and Elisseeff, 2003] Isabelle Guyon and André Elis- seeff. An introduction to variable and feature selection. J. Mach. Learn. Res., 3:1157-1182, 2003.
  6. [Kadioglu et al., 2010] S. Kadioglu, Y. Malitsky, M. Sell- mann, and K. Tierney. Isac -instance-specific algorithm configuration. Proc. of the 19th European Conference on Artificial Intelligence (ECAI), pages 751-756, 2010.
  7. [Kadioglu et al., 2011] S. Kadioglu, Y. Malitsky, A. Sabhar- wal, H. Samulowitz, and M. Sellmann. Algorithm selec- tion and scheduling. CP, 2011.
  8. [Klinkenberg and Rüping, 2003] Ralf Klinkenberg and Ste- fan Rüping. Concept drift and the importance of example. In Text Mining, pages 55-78, 2003.
  9. [Lenarcik and Piasta, 1998] Andrzej Lenarcik and Zdzislaw Piasta. Rough classifiers sensitive to costs varying from object to object. In Rough Sets and Current Trends in Computing, pages 222-230, 1998.
  10. [Malitsky, 2013] Yuri Malitsky. Algorithm portfolio bench- mark set, 2013. http://4c.ucc.ie/ ∼ ymalitsky/algorithm portfolio benchmark set.html. Link
  11. [O'Mahony et al., 2008] E. O'Mahony, E. Hebrard, A. Hol- land, C. Nugent, and B. O'Sullivan. Using case-based reasoning in an algorithm portfolio for constraint solving. Irish Conference on Artificial Intelligence and Cognitive Science, 2008.
  12. [Silverthorn and Miikkulainen, 2010] B. Silverthorn and R. Miikkulainen. Latent class models for algorithm portfolio methods. AAAI, 2010.
  13. [Stern et al., 2010] D. Stern, H. Samulowitz, R. Herbrich, T. Graepel, L. Pulina, and A. Tacchella. Collaborative ex- pert portfolio management. AAAI, 2010.
  14. [Streeter and Smith, 2007] M. Streeter and S.F. Smith. Using decision procedures efficiently for optimization. ICAPS, pages 312-319, 2007.
  15. [Ting, 2002] K. M. Ting. An instance-weighting method to induce cost-sensitive trees. IEEE Trans. on Knowl. and Data Eng., 14(3):659-665, 2002.
  16. [Wysotzki and Geibel, 2009] Fritz Wysotzki and Peter Geibel. A new information measure based on example- dependent misclassification costs and its application in decision tree learning. Adv. Artificial Intellegence, 2009.
  17. [Xu et al., 2008] L. Xu, F. Hutter, H.H. Hoos, and K. Leyton- Brown. Satzilla: Portfolio-based algorithm selection for sat. JAIR, 32(1):565-606, 2008.
  18. [Xu et al., 2012a] L. Xu, F. Hutter, J. Shen, H.H. Hoos, and K. Leyton-Brown. Satzilla2012: Improved algo- rithm selection based on cost-sensitive classification mod- els. solver description, 2012. SAT Challenge 2012.
  19. [Xu et al., 2012b] Lin Xu, Frank Hutter, Holger Hoos, and Kevin Leyton-Brown. Evaluating component solver con- tributions to portfolio-based algorithm selectors. In SAT- 2012, pages 228-241, 2012.
  20. [Zadrozny et al., 2003] Bianca Zadrozny, John Langford, and Naoki Abe. Cost-sensitive learning by cost- proportionate example weighting. In 3rd Intl. Conf. on Data Mining, pages 435-442, 2003.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards