IJCAI 2017 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 Melbourne 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 of computer science at the Leiden Institute of Advanced Computer Science (LIACS) at Universiteit Leiden, The Netherlands and at the Computer Science Department of 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. He has been elected a Fellow of the AAAI in 2015 and is a past president of the Canadian Artificial Intelligence Association (CAIAC). 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. He regularly teaches courses at all levels at UBC; he has also given tutorials at various conferences (including PPSN-12, ICAPS-13, IJCAI-13, AAAI-14 and IJCAI-16) and is regularly invited to speak at conferences (e.g., CP/ICLP/SAT 2017, GECCO 2016, ECAI 2014, ICAPS 2010), academic institutions (e.g., Oxford University, Harvard, MIT, University of Toronto) and industrial research laboratories (e.g., AT&T Research, Google Research, Microsoft Research).
Frank Hutter is a professor of computer science at the Computer Science Department of the University of Freiburg (Germany). His research focuses on machine learning and optimization for the automated design of algorithms, with an emphasis on algorithms for machine learning and for solving NP-hard problems. He received a doctoral dissertation award from the Canadian Artificial Intelligence Association for his 2009 PhD thesis at the University of British Columbia (UBC) and, with his coauthors, won several best paper awards (including from JAIR and IJCAI) and prizes in international competitions on machine learning, SAT solving, and AI planning. In 2016 he received an ERC Starting Grant for a project on automating deep learning based on Bayesian optimization, Bayesian neural networks, and deep reinforcement learning. Frank regularly teaches courses at all levels at the University of Freiburg; he also co-taught tutorials at IJCAI 2013 & 2016 and AAAI 2013, 2014 & 2016, and has been invited to speak at several conferences (e.g., ECML 2017), workshops (e.g., NIPS and ICML), academic institutions (e.g., MIT, Oxford, Cambridge), and industrial research labs (e.g., DeepMind, Google, Microsoft Research, and IBM Research).
Further material on the tutorial topic by the presenters include a CACM article on programming by optimization, a JAIR article on algorithm configuration and a JAIR article on the portfolio-based algorithm selection approach SATzilla (which received the 2010 IJCAI/JAIR Best Paper Prize).
Further PbO-related information and resources (including software):
Please send any questions, concerns or comments to Holger Hoos or Frank Hutter