Bayesian optimization explains human active search
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.
Paper 68 – Bayesian optimization explains human active 
      search The authors explore different optimization strategies for 
      1-D continuous functions and their relationship to how people optimize the 
      functions. They used a wide variety of continuous functions (with one 
      exception): polynomial, exponential, trigonometric, and the Dirac 
      function. They also explore how people interpolate and extrapolate noisy 
      samples from a latent function (which has a long tradition in psychology 
      under the name of function learning) and how people select an additional 
      sample to observe under the task of interpolating or extrapolating. Over 
      all, they found that Gaussian processes do a better job at describing 
      human performance than any of the approx. 20 other tested optimization 
      methods. Broadly, I really enjoyed this paper and I believe that 
      it is a strong NIPS submission. They tackled interesting problems for 
      machine learning-oriented cognitive scientists (although the stimuli may 
      be a bit too abstract to be of interest for many cognitive psychologists): 
      optimizing a function, and active interpolation and extrapolation. It is 
      well written and besides for some minor quibbles, the presentation is very 
      good. Besides for some minor points that I enumerate below, I have 
      two main criticisms of the paper. 1. In contrast to most function 
      learning experiments, the experimental stimuli and procedure were 
      maximally abstract (dots from a function and “find the maximum value of a 
      function”). This is not ecologically valid and thus, it is difficult to 
      interpret what the mean for actual human function learning. The functions 
      used in the experiments are probably not those functions that people 
      expect in their everyday lives. Additionally, there typically is a strong 
      effect of context on this sort of human learning and it is not clear how 
      their results can be extended to account for context (which in my opinion 
      would be a very interesting direction for them to go into for future 
      research.). It is not enough to merely state “note that many real-world 
      problems can be translated into our synthetic tasks here.” There needs to 
      be examples and a justification for why the synthetic tasks can be 
      generalized to real-world examples. However, they got compelling results, 
      where participants seem to be doing the task. 2. I would have 
      liked to see the authors integrate their experiments and results better 
      with previous human function learning work. For example, I do not see why 
      they did not choose to do their experiment using the standard cover story 
      and stimuli of a function learning experiment. I understand why the 
      authors did not just use a positive or negative linear function (although 
      given f20 of experiment 1 is unbounded, it seems reasonable to include 
      these too), but it seems including a piecewise linear function would have 
      been a smart choice. As f16 is nearly a negative linear function and has 
      been previously shown to be easy to learn, it is sensible that it would be 
      one of the easiest function to maximize (and this is the sort of 
      integration with previous work that I would have liked to have seen). 
      Integrating with previous work would have made the paper stronger and the 
      results more interpretable. More minor concerns: 
      Personally, I would have preferred to see the previous 
      psychological work to be earlier in the paper (e.g., in the introduction) 
      rather than thrown in at the very end. Figure 1 is unreadable when 
      printed out in B&W. The stimuli generation in Experiment 1 
      seemed odd. Why not directly generate the functions via generating random 
      coefficients rather than sample random points and fit a polynomial? If 
      there was a good reason for this, explaining it in the paper would be 
      helpful. “Model-free results” -> “Human results” At 
      times, the framing gets into hairy theoretical territory as to the level 
      of analysis of the paper, but at other times, it is fine. Examples of 
      troubling language include “humans might be following a GP,” and “humans 
      may use GP.” This ventures dangerously into the process level. The authors 
      have not shown any evidence that the cognitive mechanism is “GP-like” 
      whatever that might mean. An example of language at the appropriate level 
      of analysis is “Results of optimization tasks suggest that human clicks 
      during search for a maximum of a 1D function can be predicted by a 
      Gaussian processes [sic] model.” (Perhaps “a Gaussian processes model” 
      should be “a Gaussian process model” instead?). I think the 
      authors should report the rank-order correlation of the DVs for people and 
      each optimization method (where the correlation is over the different 
      function types). I don’t understand why different tolerance levels 
      were used for different optimization algorithms, although I do not see how 
      it would prejudice their results in favor of their conclusion. 
      Figure 3 is extremely difficult to read when printed out in 
      B&W. Text is too small on Figure 4. Results of 
      Experiment 2 & 3: “Interestingly, on Deg5 functions, GP is closer to 
      human clicks than the actual function (signed-rank test, p = 0.053) 
      implying that GP captures clicks well in this case.” Would this hold up 
      after correcting for multiple comparisons? (you tested Deg2 and Deg3 as 
      well). Experiments 2 & 4 are essentially function learning 
      experiments. Figure 5 is pretty difficult to read when printed out 
      in B&W. Experiment 5: Why were subjects always asked to guess 
      the value of f(200) rather than a few different values? Also for the 
      active extrapolation in this case, why not ask to find the value of the 
      point right next to f(200) and guess basically that value? Another 
      control method for the interpolation and extrapolation methods that would 
      have been nice to see how people and GPs relate to is estimating the 
      parameters of a polynomial of degree up to m (and vary m). Some 
      recent work on optimal foraging presented at last year’s NIPS was Abbott, 
      Austerweil, & Griffiths (2011) and a GP account might relate to the 
      model used by Hills et al. (2011).