nips nips2013 nips2013-54 nips2013-54-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ali Borji, Laurent Itti
Abstract: Many real-world problems have complicated objective functions. To optimize such functions, humans utilize sophisticated sequential decision-making strategies. Many optimization algorithms have also been developed for this same purpose, but how do they compare to humans in terms of both performance and behavior? We try to unravel the general underlying algorithm people may be using while searching for the maximum of an invisible 1D function. Subjects click on a blank screen and are shown the ordinate of the function at each clicked abscissa location. Their task is to find the function’s maximum in as few clicks as possible. Subjects win if they get close enough to the maximum location. Analysis over 23 non-maths undergraduates, optimizing 25 functions from different families, shows that humans outperform 24 well-known optimization algorithms. Bayesian Optimization based on Gaussian Processes, which exploits all the x values tried and all the f (x) values obtained so far to pick the next x, predicts human performance and searched locations better. In 6 follow-up controlled experiments over 76 subjects, covering interpolation, extrapolation, and optimization tasks, we further confirm that Gaussian Processes provide a general and unified theoretical account to explain passive and active function learning and search in humans. 1
[1] B. Settles, “Active learning.,” in Morgan & Claypool, 2012. 1
[2] D. Jones, “A taxonomy of global optimization methods based on response surfaces.,” Journal of Global Optimization, vol. 21, pp. 345–383, 2001. 1, 3
[3] 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,” Tech R., 2009. 1, 3
[4] L. D. Stone, “The theory of optimal search,” 1975. 1, 8
[5] B. O. Koopman, “The theory of search. i. kinematic bases.,” Operations Research, vol. 4, 1956. 1, 8
[6] J. Najemnik and W. S. Geisler, “Optimal eye movement strategies in visual search.,” Nature, 2005. 1, 8
[7] W. B. Powell and I. O. Ryzhov in Optimal Learning. (J. Wiley and Sons., eds.), 2012. 1
[8] V. V. Fedorov, Theory of Optimal Experiments. Academic Press, 1972. 1
[9] C. E. Rasmussen and C. K. I. Williams, “Gaussian processes for machine learning.,” in MIT., 2006. 1, 3
[10] J. A. Nelder and R. Mead, “A simplex method for function minimization,” Computer Journa, 1965. 3
[11] J. Kennedy and R. Eberhart, “Particle swarm optimization.,” in proc. IEEE ICNN., 1995. 3
[12] J. H. Holland, “Adoption in natural and artificial systems.,” 1975. 3
[13] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. 1989. 3
[14] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing.,” Science., 1983. 3
[15] D. Finkel, DIRECT Optimization Algorithm User Guide. 2003. 3
[16] A. Moore, J. Schneider, J. Boyan, and M. S. Lee, “Q2: Memory-based active learning for optimizing noisy continuous functions.,” in ICML, pp. 386–394, 1998. 3
[17] D. Lewis and W. Gale, “A sequential algorithm for training text classifiers.,” in In Proc. ACM SIGIR Conference on Research and Development in Information Retreival, 1994. 3
[18] H. J. Kushner, “A new method of locating the maximum of an arbitrary multipeak curve in the presence of noise.,” J. Basic Engineering, vol. 86, pp. 97–106, 1964. 3
[19] J. Elder, “Global rd optimization when probes are expensive: the grope algorithm,” in IEEE International Conference on Systems, Man and Cybernetics, 1992. 3
[20] J. Mockus, V. Tiesis, and A. Zilinskas, “The application of bayesian methods for seeking the extremum.,” in Towards Global Optimization. (L. Dixon and E. Szego, eds.), 1978. 3
[21] M. Locatelli, “Bayesian algorithms for one-dimensional global optimization.,” Journal of Global Optimization., vol. 10, pp. 57–76, 1997. 3
[22] D. D. Cox and S. John, “A statistical method for global optimization,” in In Proc. IEEE Conference on Systems, Man and Cybernetics, 1992. 3
[23] M. Osborne, R. Garnett, and S. Roberts, “Gaussian processes for global optimization,” in LION3, 2009. 3
[24] T. L. Griffiths, C. Lucas, J. J. Williams, and M. L. Kalish, “Modeling human function learning with gaussian processes.,” in NIPS, 2009. 4, 8
[25] B. R. Gibson, X. Zhu, T. T. Rogers, C. Kalish, and J. Harrison, “Humans learn using manifolds, reluctantly,” in NIPS, 2010. 8
[26] J. D. Carroll, “Functional learning: The learning of continuous functional mappings relating stimulus and response continua.,” in Education Testing Service, Princeton, NJ, 1963. 8
[27] K. Koh and D. E. Meyer, “Function learning: Induction of continuous stimulus-response relations,” Journal of Experimental Psychology: Learning, Memory, and Cognition, vol. 17, pp. 811–836, 1991. 8
[28] J. Najemnik and G. Geisler, “Eye movement statistics in humans are consistent with an optimal search strategy,” Journal of Vision, vol. 8, no. 3, pp. 1–14, 2008. 8
[29] W. S. Geisler and R. L. Diehl, “A bayesian approach to the evolution of perceptual and cognitive systems.,” Cogn. Sci., vol. 27, pp. 379–402, 2003. 8
[30] R. Castro, C. Kalish, R. Nowak, R. Qian, T. Rogers, and X. Zhu, “Human active learning,” NIPS, 2008. 8
[31] P. V. J. Palmer and M. Pavel, “The psychophysics of visual search.,” Vision Research., vol. 40, 2000. 8
[32] J. M. Wolfe in Attention. (H. E. S. in Attention (ed. Pashler, H.) 13-74 (Psychology Press, ed.), 1998. 8
[33] K. Nakayama and P. Martini, “Situating visual search,” Vision Research, vol. 51, pp. 1526–1537, 2011. 8
[34] M. P. Eckstein, “Visual search: A retrospective.,” Journal of Vision, vol. 11, no. 5, 2011. 8
[35] A. Borji and L. Itti, “State-of-the-art in modeling visual attention.,” IEEE PAMI, 2012. 8
[36] A. C. Kamil, J. R. Krebs, and H. R. Pulliam, Foraging Behavior. (ed) 1987 (New York: Plenum). 8 9