Modelling human active search in optimizing black-box functions

GPs are a powerful nonparametric model for implementing both regression and classification. One way to interpret a GP is as a distribution over functions, with inference taking place directly in the space of functions (Williams and Rasmussen 2006). A GP, therefore, is a collection of correlated random variables, any finite number of which have a joint Gaussian distribution. A GP is completely specified by its mean function \(\mu \left( x \right)\) and covariance function \({\text{cov}}\left( {f\left( x \right),f\left( {x^{\prime}} \right)} \right) = k\left( {x,x^{\prime}} \right)\):and will be denoted by: \(f\left( x \right)\sim GP\left( {\mu \left( x \right),k\left( {x,x^{\prime}} \right)} \right)\). This means that the behaviour of the model can be controlled entirely through the mean and covariance.

Usually, for notational simplicity we will take the prior of the mean function to be zero, although this is not necessary. The covariance function assumes a critical role in the GP modelling, as it specifies the distribution over functions, depending on a sample \(X_{1:n} = \left\{ {x_{1} , \ldots ,x_{n} } \right\}\). More precisely, \(f\left( {X_{1:n} } \right)\sim {\mathcal{N}}\left( {0,K\left( {X_{1:n} ,X_{1:n} } \right)} \right)\) with \(K\left( {X_{1:n} ,X_{1:n} } \right)\) an \(n \times n\) matrix whose entry \(K_{ij} = k\left( {x_{i} ,x_{j} } \right)\) with \(k\) a kernel function specifying a prior about the smoothness of the function to be approximated and optimized.

We usually have access only to noisy function values, denoted by \(y = f\left( x \right) + \varepsilon\), with \(\varepsilon\) an additive independent identically distributed Gaussian noise with variance \(\lambda^{2}\).

Let \(y = \left( {y_{1} , \ldots ,y_{n} } \right)\) denote a set of \(n\) noisy function evaluations, then the resulting covariance matrix becomes \(K\left( {X_{1:n} ,X_{1:n} } \right) + \lambda^{2} I\).

Let \(D_{1:n} = \left\{ {\left( {x_{i} ,y_{i} } \right)} \right\}_{i = 1,..,n}\) denote the set containing both the locations and the associated function evaluations, then the predictive equations for GP regression are updated by conditioning the joint Gaussian prior distribution on \(D_{1:n}\):where \(k\left( {x,X_{1:n} } \right) = \left[ {k\left( {x,x_{1} } \right), \ldots , k\left( {x,x_{n} } \right)} \right]\).

The covariance function is the crucial ingredient in a GP predictor, as it encodes assumptions about the function to approximate: function evaluations that are near to a given point should be informative about the prediction at that point. Under the GP view, it is the covariance function that defines nearness or similarity. Once the prior mean and the kernel are chosen, they are updated with the observation of \(f\left( x \right)\) to find a-posterior distribution \(f{(}x {|} D_{1:n} )\) and this allows us to find the expected value of the function at any point and to calculate its uncertainty through its predicted variance.

Examples of covariance (aka kernel) functions:The hyperparameter \(\ell\), in all the reported kernels, is the characteristic length-scale (updated by maximum likelihood estimation). The hyperparameter \(v > 0\) in the Matérn kernel governates the smoothness of the GP samples, which are \(v - 1\) differentiable, and where \({\Gamma }\left( \nu \right) \) is the gamma function and \(K_{\nu }\) is the modified Bessel function of the second kind. The most widely adopted versions, specifically in the machine learning community and considered in this paper, are \(\nu = 3/2\) and \(\nu = 5/2\). The Matérn kernel encodes the expected smoothness of the target function explicitly.

Random forest (RF) is an ensemble learning method, based on decision trees, for both classification and regression problems (Ho 1995). According to the originally proposed implementation, RF aims at generating a multitude of decision trees, at training time, and providing as output the mode of the classes (classification) or the mean/median of the predictions (regressions) of the individual trees.

Although originally designed and presented as a machine learning algorithm, RF is also an effective and efficient alternative to GP for implementing BO. RF consists of an ensemble of different regressors (i.e. decision trees); it is possible to compute—as for GP—both \(\mu \left( x \right)\) and \(\sigma \left( x \right)\), simply as mean and variance of the samples of the individual outputs provided by the regressors. Due to the different nature of RF and GP, they result in significantly different surrogate models. While GP is well suited to model smooth functions in search space spanned by continuous variables, RF can also deal with discrete and conditional variables.

Moreover, fitting an RF is computationally more efficient than fitting a GP; indeed, the kernel matrix inversion required to fit a GP is a well-known computational issue.

The acquisition function is the mechanism to implement the trade-off between exploration and exploitation in BO. More precisely, any acquisition function aims to guide the search of the optimum towards points with potentially high values of objective function either because the prediction of \(f\left( x \right)\), based on the probabilistic surrogate model, is high or the uncertainty, also based on the same model, is high (or both). Indeed, exploitation means to consider the area providing more chance to improve over current solution, while exploration means to move towards less explored regions of the search space where predictions based on the surrogate model are more uncertain, with higher variance. There are many acquisition functions, we quote only those used in this study. Probability of improvement (PI) (Kushner 1964) and expected improvement (EI) (Mockus 1975) measure, respectively, the probability and the expectation of the improvement over the best observed value of \(f\left( x \right)\) given the predictive distribution of the probabilistic surrogate model. More precisely, they are defined as follows: with \(y^{ + }\) the best value observed so far and \({\Phi }\) is the cumulative density function of a normal distribution. The next evaluation point, \(x_{n + 1}\), is obtained by maximizing \({\text{EI}}\left( x \right)\) or \({\text{PI}}\left( x \right)\). More recently, Upper/Lower Confidence Bound, (Srinivas et al. 2010), denoted with UCB/LCB, is widely used. It is an acquisition function that manages exploration–exploitation by being optimistic in the face of uncertainty where UCB and LCB are used, respectively, for maximization and minimization problems: where \(\beta \ge 0\) is the parameter to manage the trade-off between exploration and exploitation (\(\beta = 0\) is for pure exploitation; on the contrary, higher values of \(\beta\) emphasizes exploration by inflating the weight of model uncertainty). In Srinivas et al. (2010), a policy is provided for updating the value of \(\beta\) along function evaluations, with also a proof of convergence of such a policy. In the case of a maximization problem, the next point is chosen as \(x_{n + 1} = \mathop {{\text{argmax}}}\limits_{x \in X} UCB\left( x \right)\) while in the case of a minimization problem the next point is selected as \(x_{n + 1} = \mathop {{\text{argmin}}}\limits_{x \in X} LCB\left( x \right)\).

Algorithm 1 summarizes a general BO schema where the acquisition function, whichever it is, is denoted by \(\alpha \left( {x,D_{1:n} } \right)\). In order to maintain the schema as general as possible we do not specify the probabilistic surrogate model, as well as the kernel in the case of a GP.

In this study we have used both GP (considering the kernel types presented in the previous section) and RF as surrogate probabilistic models. The three different acquisition functions previously described have been used for both the two surrogates.

The software related to the game playing has been developed by implementing 15 stimuli, that are 15 different 2D functions. Each subject was informed about the goal of the experiment and the available number of clicks for the play, before to start. Subjects started by clicking at any point in the screen and getting the corresponding value; previously clicked points and their values remained on the screen until the end of the trial game. More specifically, points are coloured and resized according to the associated score (i.e. the value of \(f\) at that point), providing a visual feedback about the distribution of the scores collected so far.

Moreover, the software has been developed to manage three different game modalities. At the start of each game, along with the test function, also the modality is randomly chosen among the following.

Find a point whose associated evaluation is close to \(f^{*} = f\left( {x^{*} } \right)\), but without knowing \(f^{*}\) a-priori. From an optimization point of view, this means that the human player searches for \(y_{n}^{ + } = \mathop {\max }\limits_{i = 1, \ldots ,n} y_{i}\), with \(y_{i} = f\left( {x_{i} } \right)\) the value observed for the \(i\)th location sequentially chosen by the player. This is equivalent to optimize the simple regret (without knowing \(f^{*}\)):

As in the previous game modality, the goal is to find a point whose associated evaluation is close to \(f^{*}\) but, in this case, the human player knows \(f^{*}\) before making his/her choices. Thus, also in this case the player will optimize the simple regret: we are interested in understanding if and how knowledge about \(f^{*}\) can modify humans’ strategies with respect to the first game modality.

Maximize the cumulative value of all the evaluations at the selected points, without knowing a-priori \(f^{*}\). In this case human players tries to maximize \(\mathop \sum \nolimits_{i = 1}^{N} y_{i}\), which is equivalent to optimize the cumulative regret.

Our software collects all the choices made by each player along every game play and stores data into a database whose structure is summarized in Fig. 1. Into the “games” table, each row (i.e. record) represents a single point, and the associated function value, in a game, along with information about the player’s identifier, the test function, and the game modality. The games are univocally identified by including the timestamp relative to the end of the game.

Figure 2 shows a frame of the game.

For each player, at each iteration, GP and RF models are fitted on the observed points, and then the three acquisition functions, previously mentioned in Sect. 2.3, are used to select the next point to query. All these points are compared, via Euclidean distance, to the corresponding choice made by the human player.

Moreover, for the GP, five kernels have been used to consider different possibility of smoothness approximation of the objective function.

The choices of the human player and those of the global optimization algorithm are considered compliant, pointwise, if the distance between the point chosen by the human player and the “algorithmic player” is less than a given “threshold”, namely \(\tau\). Finally, the strategy of the human player is assimilated to the acquisition function most frequently compliant, pointwise, along a trial game. The procedures for GP-based and RF-based BO are summarized in the following pseudo-codes:

Finally, for a given kernel \(\overline{k}\), the search strategy of the participant \(\overline{p}\) is compliant to the most frequent acquisition function in the series \(s^{p,k} = \left\{ {s^{p,k,n} } \right\}_{n = m:m + N}\).

Finally, the search strategy of the participant \(\overline{p}\) is compliant to the most frequent acquisition function in the series \(s^{p} = \left\{ {s^{p,n} } \right\}_{n = m:m + N}\).

Software resources consist of two components developed in R. The first component is the procedure to compute the distance between the humans’ and global optimization choices during each game, while the second aggregates all the calculated distances and generates the related statistics. More precisely, the procedure operated by the first component is summarized in previous Algorithm 2 and Algorithm 3 for GP-based and RF-based BO, respectively. Since this study considers also other global optimization strategies—detailed in the following—the first component has been specialized for each one of the other strategies. (For ease of reading, we do not report every single implementation, but they can be easily obtained starting from Algorithm 3.)

The implementations of Algorithm 2 and Algorithm 3 are based on the R package named “mlrMBO”, which offers both GP and RF as surrogate model along with the acquisition functions adopted in this study. L-BFGS algorithm is used to optimize the acquisition function based on GP on a continuous search space; for RF the “focus-search” algorithm (Bischl et al. 2017) is adopted: it can handle with numeric, discrete and mixed search spaces, also involving conditional variables. Focus-search starts with a large set of random points where the acquisition function is evaluated. Then, the search space is shrunk around the current best point and a new random sampling is performed within the “focused space”. Shrinkage is iteratively performed until a maximum number of iterations, and the entire procedure can be restarted multiple times to mitigate the risk of convergence to a local optimum. Finally, the best point over all restarts and iterations is returned as the solution.

As already mentioned, we have also compared the humans’ strategies with other deterministic and stochastic global optimization techniques, more specifically:

We have then computed the distances, in terms of \(x\), between the best location found by the humans at the end of each game with those provided by each one of the other five global optimization techniques and BO. Let denote with \(x^{ + }\) the location found by the player (human or algorithmic) such that \(y^{ + } = f\left( {x^{ + } } \right)\) is the best value observed over a specific trial game by that user.

In this section, we further detail the features of the data collected and used for this study. Initially, around 70 volunteers were enrolled for the study; while they used the software to play and collect data, their feedbacks about the user-friendliness of the interface were also used to improve our software. Due to this work-in-progress nature of the game playing software, not all the games collected were well suited for the analysis. Thus, we have decided to restrict the analysis to the largest homogeneous set, that is:

With respect to Algorithm 2 and Algorithm 3, we declare here the values of \(\beta\) in the UCB equation, that is \(\beta = \left\{ {0.0, 0.5, 1.0} \right\}, \) and of the threshold \(\tau = \left\{ {0.10, 0.15} \right\}\).

The following figures summarize the main results related to the comparison between human players strategies and GP-based BO. We start with the case \(\beta = 1.0 \) in UCB.

From Fig. 3, EI is preferred, indicating a dominant exploitative behaviour among humans. Indeed, \(\beta = 1.0 \) in the UCB gives some chance to exploration, depending on the value of \(\sigma \left( x \right)\). Statistical significance of this result was evaluated via a Fisher’s test for each pair consisting in EI versus another acquisition function. Given a pair of acquisition functions, the test hypothesis is that there is not a more compliant one. As summarized in Table 1, the hypothesis is rejected (p value < 0.05) for exponential and Matérn kernels, while it is accepted for power and squared exponential kernels.

Results reported in Fig. 4 are coherent with those previously depicted in Fig. 3. Moreover, the number of human players whose strategy is not compliant with BO is reduced, according to the less restrictive value of the threshold \(\tau\). We have applied a Fisher’s test to evaluate the statistical significance of the obtained outcomes; results are summarized in Table 2. According to the Fisher’s test, EI is always the most compliant acquisition function, except for the squared exponential kernel.

According to the charts reported in Fig. 5, one can see that with the reduction in \(\beta\), UCB gains a larger share of participants. Again, we have applied a Fisher’s test to evaluate the statistical significance of the obtained outcomes; the results are summarized in Table 3. According to the Fisher’s test, the EI is still the most compliant acquisition function, for most of the kernels, even if the p values increases with respect to the previous cases.

Figure 6 is again a confirmation that, for human players, “greed is good”: \(\beta = 0\) means no-exploration in UCB whose fully exploitative version gets the largest share of participants. In this case we have performed a Fisher’s test for each pair related to UCB (instead of EI) versus the other acquisition functions, since UCB is now the most frequently compliant option. Results of the Fisher’s test are summarized in Table 4. Although UCB with \(\beta = 0\) is the most frequently compliant acquisition function, the number of shares does not result significantly different from that of EI. In any case this result confirms the exploitative nature of humans, who largely adopt strategies close to EI and “pure exploitative” UCB acquisition functions.

Although maximizing EI or UCB with \(\beta = 0\) should analytically lead to the same next location \(x\) to evaluate, the numerical results can be quite different, due to the different shapes of these two acquisition functions. Indeed, when \(\mu \left( x \right)\) is lower than the best value observed so far, \(y^{ + } ,\) over a large portion of the search space, then EI is almost completely flat, as depicted in the example of Fig. 7. Consequently, whichever optimization strategy is used to optimize EI could easily fail, leading to no improvement of \(y^{ + }\) over new function evaluations. On the contrary, UCB with \(\beta = 0\) coincides with \(\mu \left( x \right)\) (Fig. 7): this allows to converge towards a local optimum of \(\mu \left( x \right)\) and, in case, to improve over \(y^{ + }\).

The same analysis has been also performed by using RF as surrogate model instead of GP. Figure 8 shows that PI, a notoriously exploitative acquisition function, gets the larger share of compliant when UCB accounts for exploration (\(\beta = 1\)).

Although the exploitative nature of the human choice is confirmed also in this case, we observed a shift from EI to PI (that is even more exploitative than EI). This is basically due to the combination between the type of acquisition function and the shape of the surrogate model, that is piecewise constant for RF and continuous for GP.

The situation changes by reducing the exploration component in UCB, which with \(\beta = 0\).5 and \(\beta = 0\).0 dominates choices among the compliant. Summarizing, also in the case of RF, the human’s nature appears to be exploitative. We have performed a Fisher’s test to evaluate, for each combination of \(\tau\) and \(\beta\), if the BO algorithm associated to the larger share of compliant participants can be statistically considered the most compliant one. Results of the Fisher’s test are reported in Table 5.

In this section we consider, among all the possibilities, the BO approach that proved to be more compliant with the humans’ strategies, overall. Let BO** denote this specific approach, that is: GP surrogate with Matérn 3/2 kernel, EI as acquisition function and \(\tau = 0.15.\) Indeed, as reported in Fig. 4, this BO configuration is associated to the largest share (i.e. 43) of participants compliant to an optimization strategy.

We computed all the distances between the optimal solutions (i.e. \(x^{ + }\)) found by humans with those provided by BO** and the other 5 global optimization techniques cited in Sect. 3.3 (i.e. RS, DIRECT, GA, PSO and SA).

According to the boxplot reported in Fig. 9, optimal solutions provided by BO** are, on average, closer to the humans’ ones compared to the other techniques.

More interestingly, the density plot in Fig. 10 shows that the distributions of the distances are basically bimodal, for all the global optimization techniques but BO**. Indeed, for BO** the density associated with small values of the distance is around twice that related to other global optimization techniques, proving that BO** is closer to the strategies applied by the human players.

Beyond the visual representation in Fig. 10, a further confirmation that BO is closer to human search comes from statistical tests. Since distances do not show a normal distribution, we could not apply ANOVA and, therefore, we used nonparametric tests. According to the Friedman’s test, distance values result significantly different among all the techniques (p value < 0.001). To better investigate these differences, we have then performed a pairwise Wilcoxon test obtaining that: