AAAI 2014 Tutorial
|
When creating software, particularly solvers for the computationally challenging problems arising in many areas of AI, developers frequently explore multiple ways of achieving certain tasks. Often, these alternatives are eliminated or abandoned early in the process, based on the belief that the flexibility afforded by them would be difficult or impossible to exploit later. Programming by Optimization (PbO) is a design paradigm that aims to avoid such premature design choices and to actively develop promising alternatives for parts of the design. Rather than build a single program for a given purpose, software developers specify a rich and potentially large design space of programs. From this specification, programs that perform well in a given use context are generated automatically through powerful optimisation techniques. PbO allows human experts to focus on the creative task of imagining possible mechanisms for solving given problems or subproblems, while the tedious job of determining what works best in a given use context is performed automatically, substituting human labor with computation. Furthermore, using PbO, per-instance algorithm selectors and parallel algorithm portfolios can be obtained from the same sequential source.
In this tutorial, we will share the vision of PbO, describe key algorithmic techniques that, fuelled by recent advances in optimization and machine learning, make PbO practical, and illustrate the power of the approach based on several case studies. Specifically, we will survey and explain state-of-the-art methods for automated algorithm configuration (which optimize algorithm parameters for a particular distribution of problem instances), portfolio-based algorithm selection (which select between different algorithms in an instance-specific way) and automated portfolio construction (which identify sets of complementary algorithms or parameter configurations). We will also discuss practical tools that facilitate PbO-based software development. Our application examples and case studies, taken from the recent literature, illustrate how the use of PbO and the computer-aided algorithm design techniques it is based on resulted in substantial improvements of the state of the art (often by orders of magnitude) for various challenging computational problems, including SAT-based software verification, planning and timetabling, supervised machine learning, as well as mixed integer programming – perhaps the most widely used approach for solving optimization problems in industry. Our tutorial is aimed at AI researchers interested in using the PbO approach and the practical tools that support to better realize the performance potential inherent in their algorithmic ideas.
The slides shown at the tutorial in Beijing can be found here and can be used freely for non-commercial purposes; of course, we'd love to hear from you if you find them useful.
Holger Hoos is a Professor for Computer Science at the University of British Columbia in Vancouver (Canada), where he also holds an appointment as an Associate of the Peter Wall Institute for Advanced Studies. His main research interests span empirical algorithmics, artificial intelligence, bioinformatics and computer music. He is known for his work on the automated design of high-performance algorithms and on stochastic local search methods. Holger is a co-author of the book Stochastic Local Search: Foundations and Applications, and his research has been published in numerous book chapters, journals, and at major conferences in artificial intelligence, operations research, molecular biology and computer music. Since 2009, he serves as President of the Canadian Artificial Intelligence Association (CAIAC). He regularly teaches courses at all levels at UBC; he has also given tutorials at various conferences (including IJCAI-03, AAAI-04, SLS-09, LION-10, PPSN-12, and IJCAI-13) and is regularly invited to speak at conferences (e.g., ICAPS 2010, ECAI 2014), academic institutions (e.g., Harvard, MIT, University of Toronto) and industrial research laboratories (e.g., AT&T Research, Google Research, Microsoft Research).
Frank Hutter is an Emmy Noether Research Group Lead (eq. Assistant Professor) at the Com- puter Science Department of Freiburg University (Germany). Frank’s research focuses on machine learning and optimization for the automated design of algorithms, with an emphasis on algorithms for solving NP-hard problems. His PhD thesis on algorithm configuration at the University of British Columbia (UBC) received the CAIAC doctoral dissertation award for the best PhD thesis in Artificial Intelligence completed at a Canadian University in 2009. Frank worked as part of the science education initiative of Nobel laureate Carl Wieman for one year to improve UBC’s undergraduate AI curriculum (CPSC 322 and CPSC 422) and taught CPSC 322 at UBC in the following year. He also taught a graduate course at Freiburg University, co-taught tutorials at IJCAI 2013 and AAAI 2013, and has recently given invited presentations at several institutions, including MIT, Google, Microsoft Research, and IBM Research.
Further PbO-related information and resources (including software):
Please send any questions, concerns or comments to Holger Hoos or Frank Hutter