Bruno Barracosa

Julien Bect

Héloïse Dutrieux Baraffe

Juliette Morin

Josselin Fournel

Emmanuel Vazquez

Bayesian multi-objective optimization with noisy evaluations

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

CONTEXT

• Multi-objective optimization of the parameters of a planning for the multi-year planning the electricity distribution grid [DUT15] • A stochastic black box provides evaluation results the objective functions 𝑓𝑓 1 , … , 𝑓𝑓 𝑞𝑞 defined on a discrete search domain

𝕏𝕏 ⊂ ℝ 𝑑𝑑 • Previous n evaluations at X (X 1 , … , X n ) assumed:  𝑍𝑍 𝑖𝑖,1 = 𝑓𝑓 1 𝑋𝑋 𝑖𝑖 + 𝜀𝜀 𝑖𝑖,1 , … , 𝑍𝑍 𝑖𝑖,𝑞𝑞 = 𝑓𝑓 𝑞𝑞 𝑋𝑋 𝑖𝑖 + 𝜀𝜀 𝑖𝑖,𝑞𝑞
where 𝜀𝜀 s are zero-mean random variables Average performance results over 100 simulations for four optimization approaches: random approach (red) and the proposed approach with batches of 1 (black), 4 (blue) or 10 (magenta) evaluations.

OBJECTIVE

𝑦𝑦 = 1 , … , 𝑦𝑦 𝑞𝑞 ≺ 𝑦𝑦′ = 𝑦𝑦′ 1 , … , 𝑦𝑦′ 𝑞𝑞 ⇔ � ∀𝑖𝑖 ≤ 𝑞𝑞, 𝑦𝑦 𝑖𝑖 ≤ 𝑦𝑦 𝑖𝑖 ′ ∃𝑗𝑗 ≤ 𝑞𝑞, 𝑦𝑦 𝑗𝑗 < 𝑦𝑦 𝑗𝑗

Illustration of the Pareto domination rule

-𝑦𝑦 1 , 𝑦𝑦 2 , 𝑦𝑦 3 are non-dominated points -𝑦𝑦 4 is only dominated by 𝑦𝑦 1 -𝑦𝑦 5 is only dominated by 𝑦𝑦 2 -𝑦𝑦 6 is dominated by all other points

•

  Compare the proposed approach (PA) with random selection of points in a bi-dimensional bi-objective problem • Compare use of batches of 1, 4 or 10 evaluations 3. BAYESIAN OPTIMIZATION • Define a probabilistic model for each 𝑓𝑓 conditional on previous observations • Use a sampling criterion to select new evaluation points 5. OPEN QUESTIONS • 'Ideal' batch of evaluations? • Performance comparison of the proposed approach to other methods in the literature? Provides estimate of 𝒇𝒇 and a measure of uncertainty of the estimation PARETO-OPTIMAL ESTIMATES Built from the estimates of 𝑓𝑓 PROPOSED APPROACH • Replace the multi-objective problem by the minimization of a single augmented Tchebycheff function [KNO06]: f𝑓 𝑥𝑥 = max 𝑗𝑗 𝜔𝜔 𝑗𝑗 𝑓𝑓 𝑗𝑗 𝑥𝑥 + 𝜌𝜌 � 𝑗𝑗 𝜔𝜔 𝑗𝑗 𝑓𝑓 𝑗𝑗 𝑥𝑥 , � 𝑗𝑗 𝜔𝜔 𝑗𝑗 = 1, 𝜌𝜌 > 0 • At each iteration, generate random weights 𝜔𝜔 𝑗𝑗 and apply this function to the n previous observations: � 𝑍𝑍 𝑖𝑖 = max 𝑗𝑗 𝜔𝜔 𝑗𝑗 𝑍𝑍 𝑖𝑖,𝑗𝑗 + 𝜌𝜌 � 𝑗𝑗 𝜔𝜔 𝑗𝑗 𝑍𝑍 𝑖𝑖,𝑗𝑗 , , 𝑖𝑖 = 1, … , 𝑛𝑛 • Assume a homoscedastic Gaussian noise model and fit to � 𝑍𝑍 = ( � 𝑍𝑍 1 , … , � 𝑍𝑍 𝑛𝑛 ) a Gaussian Process model ξ𝜉𝑛𝑛 with parameters estimated by maximum likelihood • We use the Knowledge Gradient (KG) criterion [FRA09] to select new point 𝑋𝑋 𝑛𝑛+1 based on previous observations. The idea is to identify a point that is expected to reduce the minimum of the posterior mean of ξ𝜉 : 𝑋𝑋 𝑛𝑛+1 = argmax 𝑥𝑥∈𝕏𝕏 𝐾𝐾𝐾𝐾 (𝑥𝑥) with: 𝐾𝐾𝐾𝐾 𝑥𝑥 = min 𝑥𝑥 ′ ∈𝕏𝕏 𝔼𝔼 ξ𝜉𝑛𝑛 (𝑥𝑥 ′ ) -𝔼𝔼 min 𝑥𝑥 ′ ∈𝕏𝕏 𝔼𝔼 ξ𝜉𝑛𝑛 (𝑥𝑥 ′ )| � 𝑍𝑍 𝑛𝑛,𝑥𝑥 where � 𝑍𝑍 𝑛𝑛,𝑥𝑥 denotes a new observation of ξ𝜉𝑛𝑛 at 𝑥𝑥 • Update the model with new observation and iterate until stopping criterion is met


Gaussian process model selection for computer experiments

Sébastien J. Petit ➠ Given data D n = (X n , f | X n ), a Gaussian process ξ can be used to make probabilistic predictions of

f ξ(x)|D n ∼ N ( ξθ (x), σ2 θ (x)) (1)
➠ ξ is a prior over functions ➠ The choice of ξ is critical for good predictions and design-ofexperiments techniques

The prior ξ is often chosen within a parametric family.

➠ Very often: the Matérn covariance functions family is used [START_REF] Stein | Interpolation of Spatial Data: Some Theory for Kriging[END_REF] ➠ Many procedures have been proposed in the literature for selecting the parameters of a covariance function ➠ Little is known about their relative benefits What are the most useful procedures to select the parameters of a Matérn covariance function (including or not regularity) ?

1 Maximum-likelihood [START_REF] Kitanidis | Statistical estimation of polynomial generalized covariance functions and hydrologic applications[END_REF] ➠ A very popular technique ➠ Choose the parameters that yield the highest value of the probability density for the observations, or equivalently, minimize

z T K θ z + ln(det(K θ )),
where K θ is the covariance matrix of ξ at points X n = (x 1 , ..., x n ) for parameters θ and z = (z 1 , ..., z n ) T denotes the values of f at X n

Cross-validation

Leave-one-out (LOO) [START_REF] Currin | A Bayesian approach to the design and analysis of computer experiments[END_REF] is a second very popular technique ➠ Consists in averaging losses for predicting one observation using the others ➠ We suggest using negatively-oriented scoring rules [START_REF] Gneiting | Strictly proper scoring rules, prediction, and estimation[END_REF] for the loss functions ➠ A (negatively-oriented) scoring rule is a mapping S : (P, R) → R where P is a class of probability distributions, with S(P, z) representing a loss for observing z while predicting P ➠ Given a scoring rule S the corresponding LOO criterion is

L LOO S (θ) = 1 n n i=1 S(N ( ξθ,-i , σ2 θ,-i ), z i ), (2)
where N ( ξθ,-i , σ2 θ,-i ) denotes LOO predictive distributions In this work we consider the following scoring rules [START_REF] Gneiting | Strictly proper scoring rules, prediction, and estimation[END_REF]:

➠ S MSPE (P, z) = (E Z∼P (Z) -z) 2 ➠ S NLPD (P, z) = -ln(p(z)), with p the pdf of P ➠ S CRPS (P, z) = ||F -1 z≤. || 2 L 2 (R)
, with F the cdf of P We shall denote the resulting selection procedures by LOO-MSPE, LOO-NLPD and LOO-CRPS respectively.

Generalized cross-validation [1]

➠ A version of LOO-MSPE that takes the heterogeneity of the design into account 4 Kernel alignment [START_REF] Cristianini | On kernel-target alignment[END_REF] ➠ Aligns the eigenvector related to the highest eigenvalue of K θ with the data ➠ Can also be seen as a similarity between K θ and the covariance matrix obtained from the kernel (x, y) → f (x)f (y)

Numerical study

We use a set of 36 problems:

➠ Goldstein-Price (d ∈ {1, 2}) ➠ Mystery (d = 2) ➠ Toms 829 C k (k ∈ {0, 1, 2}, d ∈ {2, 5}) ➠ Rotated Rosenbrock (d ∈ {2, 5}) ➠ Borehole (d =
1.17 Table : Average MSPE on the validation sets for the different selection procedures and regularity choices.

Influence of the regularity

We focus on two subsets of problems with different smoothness. Fig. 1: 5-dimensional Toms 829 problems; Fig. 2: 5-dimensional Rosenbrock and Borehole.

We compare log S MSPE normalized by "Best" values both with automatically selected or fixed-p ∈ {0, 1, 2, 3, 4, d, 2d, +∞}. Fig. 2: Influence of the regularity on the loss for smooth problems.

Influence of the selection criteria

We compare the selection procedures with automatically selected ps.

S IS α (l, u, x) = (u -l) + 2 α (l -x)1 x≤l + 2 α (x -u)1 x>u . (3)
6 Conclusions

➠ The regularity parameter has a strong impact on the goodness of fit ➠ We recommend selecting the regularity from data instead of fixing it to a "standard" value ➠ The choice of a reasonable selection procedure has second-order impact but ML and LOO CRPS seem to give the best performances ➠ All procedures have the same numerical complexity, using appropriate computations of the selection criteria and their gradients [START_REF] Petit | Towards new cross-validation-based estimators for Gaussian process regression: efficient adjoint computation of gradients[END_REF] ML LOO-CRPS MSE-LOO LOO-NLPD GCV KA

  • 10 -5 1.23 • 10 -5 1.29 • 10 -5 1.14 • 10 -5 1.59 • 10 -1 1.66 • 10 -5 8.68 • 10 -6 3 1.54 • 10 -5 1.80 • 10 -5 1.81 • 10 -5 1.62 • 10 -5 1.36 • 10 -1 2.32 • 10 -5 1.26 • 10 -5 4 1.90 • 10 -5 2.32 • 10 -5 2.30 • 10 -5 2.11 • 10 -5 1.23 • 10 -1 3.13 • 10 -5 1.60 • 10 -5 6 2.36 • 10 -5 3.07 • 10 -5 2.90 • 10 -5 2.68 • 10 -5 1.12 • 10 -1 4.00 • 10 -5 1.99 • 10 -5 12 2.60 • 10 -5 3.30 • 10 -5 3.04 • 10 -5 2.97 • 10 -5 1.03 • 10 -1 4.11 • 10 -5 2.16 • 10 -5 +∞ 2.94 • 10 -5 3.77 • 10 -5 3.33 • 10 -5 3.18 • 10 -5 9.23 • 10 -2 4.31 • 10 -5 2.43 • 10 -5 p 1.17 • 10 -5 1.27 • 10 -5 1.29 • 10 -5 1.15 • 10 -5 9.23 • 10 -2 1.74 • 10 -5 8.68 • 10 -6

Fig. 1 :

 1 Fig.1: Influence of the regularity on the loss for non-smooth problems.

Fig. 3 :

 3 log(S MSPE ) normalized by "Best" values; Fig. 4: interval score [4] defined by

Fig. 3 :Fig. 4 :

 34 Fig. 3: Influence of the selection criteria on the MSPE.

  1,2 & Julien Bect 1 & Paul Feliot 2 & Emmanuel Vazquez 1 Safran Aircraft Engines, Moissy-Cramayel, France email: sebastien.petit@centralesupelec.fr Context ➠ Exploration of black-box numerical simulators f : X ⊂ R d → R with Gaussian processes

1 Université Paris-Saclay, CentraleSupélec, Laboratoire des Signaux et Systèmes, Gif-sur-Yvette, France.

2

  8)with space-filing designs X n , n ∈ {10d, 20d, 50d}. For each case: 10 -2 1.12 • 10 -2 1.07 • 10 -2 1.06 • 10 -2 2.16 • 10 -1 1.04 • 10 -2 9.74 • 10 -3 1 3.27 • 10 -5 3.11 • 10 -5 2.78 • 10 -5 2.85 • 10 -5 1.71 • 10 -1 2.79 • 10 -5 2.45 • 10 -5

	➠ We compare model selection procedures using predictions evaluated on
	a dense test grid
	➠ In particular, we study the influence of the regularity parameter p of
	a Matérn covariance function, by setting p ∈ {0, 1, 2, 3, 4, d, 2d, +∞}
	or automatically selecting its value using the selection criteria
	➠ We present averaged results through repetitions (using random X n for
	instance)
	An example
	Observe that
	➠ Procedures ML, LOO-MSPE, LOO-NLPD and LOO-CRPS give simi-
	lar accuracies
	➠ The influence of p on the accuracy is strong
	MSPE	ML	LOO MSPE LOO NLPD LOO CRPS	KA	GCV	"Best"
	0	1.08 •