nips nips2010 nips2010-38 nips2010-38-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Javad Azimi, Alan Fern, Xiaoli Z. Fern
Abstract: Bayesian optimization methods are often used to optimize unknown functions that are costly to evaluate. Typically, these methods sequentially select inputs to be evaluated one at a time based on a posterior over the unknown function that is updated after each evaluation. In many applications, however, it is desirable to perform multiple evaluations in parallel, which requires selecting batches of multiple inputs to evaluate at once. In this paper, we propose a novel approach to batch Bayesian optimization, providing a policy for selecting batches of inputs with the goal of optimizing the function as efficiently as possible. The key idea is to exploit the availability of high-quality and efficient sequential policies, by using Monte-Carlo simulation to select input batches that closely match their expected behavior. Our experimental results on six benchmarks show that the proposed approach significantly outperforms two baselines and can lead to large advantages over a top sequential approach in terms of performance per unit time. 1
[1] B. S. Anderson, A. W. More, and D. Cohn. A nonparametric approach to noisy and costly optimization. In ICML, 2000.
[2] A. G. Barto, R. S. Sutton, and C. W. Anderson. Neuronlike adaptive elements that can solve difficult learning control problems. 13:835–846, 1983.
[3] D. Bond and D. Lovley. Electricity production by geobacter sulfurreducens attached to electrodes. Applications of Environmental Microbiology, 69:1548–1555, 2003.
[4] E. Brochu, M. Cora, and N. de Freitas. A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. Technical Report TR2009-23, Department of Computer Science, University of British Columbia, 2009.
[5] M. Brunato, R. Battiti, and S. Pasupuleti. A memory-based rash optimizer. In AAAI-06 Workshop on Heuristic Search, Memory Based Heuristics and Their applications, 2006.
[6] E. H. Burrows, W.-K. Wong, X. Fern, F. W. Chaplen, and R. L. Ely. Optimization of ph and nitrogen for enhanced hydrogen production by synechocystis sp. pcc 6803 via statistical and machine learning methods. Biotechnology Progress, 25:1009–1017, 2009.
[7] M. F. G Nemhauser, L Wolsey. An analysis of the approximations for maximizing submodular set functions. Mathematical Programmingn, 14:265–294, 1978.
[8] Y. Guo and D. Schuurmans. Discriminative batch mode active learning. Proceedings of Advances in Neural Information Processing Systems (NIPS2007), 6, 2007.
[9] V. P. Il’ev. An approximation guarantee of the greedy descent algorithm for minimizing a supermodular set function. Discrete Applied Mathematics, 114(1-3):131–146, 2001.
[10] D. Jones. A taxonomy of global optimization methods based on response surfaces. Journal of Global Optimization, 21:345–383, 2001.
[11] L. Kaufman and P. J. Rousseeuw. Clustering by means of medoids. Statistical data analysis based on L1 norm, pages 405–416, 1987.
[12] D. Lizotte. Practical Bayesian optimization. PhD thesis, University of Alberta, 2008.
[13] S. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137, 1982.
[14] M. Locatelli. Bayesian algorithms for one-dimensional globaloptimization. J. of Global Optimization, 10(1):57–76, 1997.
[15] Z. Michalewicz. Genetic algorithms + data structures = evolution programs (2nd, extended ed.). Springer-Verlag New York, Inc., New York, NY, USA, 1994.
[16] A. Moore and J. Schneider. Memory-based stochastic optimization. In NIPS, 1995.
[17] G. Nemhauser and L. Wolsey. Integer and combinatorial optimization. Wiley New York, 1999.
[18] D. Park and J. Zeikus. Improved fuel cell and electrode designs for producing electricity from microbial degradation. Biotechnol.Bioeng., 81(3):348–355, 2003.
[19] C. E. Rasmussen and C. K. I. Williams. Gaussian Processes for Machine Learning. MIT, 2006.
[20] A. M. Ross. Computing Bounds on the Expected Maximum of Correlated Normal Variables . Methodology and Computing in Applied Probability, 2008.
[21] M. Schonlau. Computer Experiments and Global Optimization. PhD thesis, University of Waterloo, 1997.
[22] H. D. Vinod. Integer programming and the theory of grouping. Journal of the American Statistical Association, 64(326):506–519, 1969. 9