×

zbMATH — the first resource for mathematics

Are humans Bayesian in the optimization of black-box functions? (English) Zbl 07250741
Sergeyev, Yaroslav D. (ed.) et al., Numerical computations: theory and algorithms. Third international conference, NUMTA 2019, Crotone, Italy, June 15–21, 2019. Revised selected papers. Part II. Cham: Springer (ISBN 978-3-030-40615-8/pbk; 978-3-030-40616-5/ebook). Lecture Notes in Computer Science 11974, 32-42 (2020).
Summary: Many real-world problems have complicated objective functions whose optimization requires sophisticated sequential decision-making strategies. Modelling human function learning has been the subject of intense research in cognitive sciences. The topic is relevant in black-box optimization where information about the objective and/or constraints is not available and must be learned through function evaluations. The Gaussian process based Bayesian learning paradigm is central in the development of active learning approaches balancing exploration/exploitation in uncertain conditions towards effective generalization in large decision spaces. In this paper we focus on Bayesian optimization and analyse experimentally how it compares to humans while searching for the maximum of an unknown 2D function. A set of controlled experiments with 53 subjects confirm that Gaussian processes provide a general model to explain different patterns of learning enabled search and optimization in humans.
For the entire collection see [Zbl 1435.65017].
MSC:
65 Numerical analysis
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adam, S.P., Alexandropoulos, S.A.N., Pardalos, P.M., Vrahatis, M.N.: No free lunch theorem: a review. In: Demetriou, I.C., Pardalos, P.M. (eds.) Approximation and Optimization. SOIA, vol. 145, pp. 57-82. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-12767-1_5 · Zbl 1425.90111
[2] Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Mach. Learn. 47(2-3), 235-256 (2002) · Zbl 1012.68093
[3] Borji, A., Itti, L.: Bayesian optimization explains human active search. In: Advances in Neural Information Processing System 26 (NIPS 2013), pp. 55-63 (2013) · Zbl 1373.94046
[4] Candelieri, A., Perego, R., Archetti, F.: Bayesian optimization of pump operations in water distribution systems. J. Glob. Optim. 71, 213-235 (2018) · Zbl 1402.90126
[5] Chapelle, O., Li, L.: An empirical evaluation of thompson sampling. In: Advances in Neural Information Processing Systems, pp. 2249-2257 (2011)
[6] Eggensperger, K., Lindauer, M., Hutter, F.: Pitfalls and best practices in algorithm configuration. J. Artif. Intell. Res. 64, 861-893 (2019) · Zbl 07056106
[7] Gershman, S.J.: Uncertainty and exploration. bioRxiv 265504 (2018). https://doi.org/10.1101/265504
[8] Gopnik, A., O’Grady, S., Lucas, C.G., Griffiths, T.L., Wente, A., Bridgers, S., Dahl, R.E.: Changes in cognitive flexibility and hypothesis search across human life history from childhood to adolescence to adulthood. Proc. Nat. Acad. Sci. 114(30), 7892-7899 (2017)
[9] Kruschke, J.K.: Bayesian approaches to associative learning: from passive to active learning. Learn. Behav. 36(3), 210-226 (2008)
[10] Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Glob. Optim. 13(4), 455-492 (1998) · Zbl 0917.90270
[11] Li, K., Malik, J.: Learning to optimize. (2016) arXiv preprint arXiv:1606.01885
[12] May, B.C., Korda, N., Lee, A., Leslie, D.S.: Optimistic Bayesian sampling in contextual-bandit problems. J. Mach. Learn. Res. 13(Jun), 2069-2106 (2012) · Zbl 1435.62034
[13] Mehlhorn, K., Newell, B.R., Todd, P.M., Lee, M.D., Morgan, K., Braithwaite, V.A., Gonzalez, C.: Unpacking the exploration-exploitation tradeoff: a synthesis of human and animal literatures. Decision 2(3), 191 (2015)
[14] Gershman, S.J.: Quantifying mismatch in Bayesian optimization. In: NIPS Workshop on Bayesian Optimization: Black-Box Optimization and Beyond (2016)
[15] Schulz, E., Tenenbaum, J., Duvenaud, D.K., Speekenbrink, M., Gershman, S.J.: Probing the compositionality of intuitive functions. In: Advances in Neural Information Processing Systems, pp. 3729-3737 (2016)
[16] Schulz, E., Speekenbrink, M., Krause, A.: A tutorial on Gaussian process regression: modelling, exploring, and exploiting functions. J. Math. Psychol. 85, 1-16 (2018) · Zbl 1416.62648
[17] Srinivas, N., Krause, A., Kakade, S., Seeger, M.: Gaussian process optimization in the bandit setting: no regret and experimental design. In: Proceedings of the 27th International Conference on Machine Learning, pp. 1015-1022. Omnipress, June 2010
[18] Thompson, W.R.: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25(3/4), 285-294 (1933) · JFM 59.1159.03
[19] Wilson, R.C., Geana, A., White, J.M., Ludvig, E.A., Cohen, J.D.: Humans use directed and random exploration to solve the explore-exploit dilemma. J. Exp. Psychol. Gen. 143(6), 2074 (2014)
[20] Wu, C.M., Schulz, E., Speekenbrink, M., Nelson, J.D., Meder, B.: Generalization guides human exploration in vast decision spaces. Nat. Hum. Behav. 2(12), 915 (2018)
[21] Zhigljavsky, A.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.