Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 21 (2012) no. 3, pp. 557-591.

On considère l’estimation de la probabilité p=P(g(X)0)X est un vecteur aléatoire et g une fonction monotone. Premièrement, on rappelle et formalise une méthode, proposée par de Rocquigny (2009), permettant d’encadrer p par des bornes déterministes en fonction d’un plan d’expérience séquentiel. Le second et principal apport de l’article est la définition et l’étude d’un estimateur statistique de p tirant parti des bornes. Construit à partir de tirages uniformes successifs, cet estimateur présente sous de faibles conditions théoriques une variance asymptotique plus faible et une meilleure robustesse que l’estimateur classique de Monte Carlo, ce qui rend la méthode adaptée à l’emploi de codes informatiques g lourds en temps de calcul. Des expérimentations numériques sont menées sur des exemples-jouets et un cas d’étude hydraulique plus réaliste. Une heuristique de boostrap, reposant sur un réplicat de l’hypersurface {x,g(x)=0} par des réseaux de neurones, est proposée et testée avec succès pour ôter le biais non-asymptotique de l’estimateur.

The problem of estimating the probability p=P(g(X)0) is considered when X represents a multivariate stochastic input of a monotonic function g. First, a heuristic method to bound p, originally proposed by de Rocquigny (2009), is formally described, involving a specialized design of numerical experiments. Then a statistical estimation of p is considered based on a sequential stochastic exploration of the input space. A maximum likelihood estimator of p build from successive dependent Bernoulli data is defined and its theoretical convergence properties are studied. Under intuitive or mild conditions, the estimation is faster and more robust than the traditional Monte Carlo approach, therefore adapted to time-consuming computer codes g. The main result of the paper is related to the variance of the estimator. It appears as a new baseline measure of efficiency under monotonicity constraints, which could play a similar role to the usual Monte Carlo estimator variance in unconstrained frameworks. Furthermore the bias of the estimator is shown to be corrigible via bootstrap heuristics. The behavior of the method is illustrated by numerical tests conducted on a class of toy examples and a more realistic hydraulic case-study.

DOI : 10.5802/afst.1345
Bousquet, Nicolas 1

1 EDF Research & Development Dpt. of Industrial Risk Management 6 quai Watier, 78401 Chatou, France
@article{AFST_2012_6_21_3_557_0,
     author = {Bousquet, Nicolas},
     title = {Accelerated {Monte} {Carlo} estimation of exceedance probabilities under monotonicity constraints},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {557--591},
     publisher = {Universit\'e Paul Sabatier, Institut de math\'ematiques},
     address = {Toulouse},
     volume = {Ser. 6, 21},
     number = {3},
     year = {2012},
     doi = {10.5802/afst.1345},
     zbl = {1275.62058},
     mrnumber = {3076412},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/afst.1345/}
}
TY  - JOUR
AU  - Bousquet, Nicolas
TI  - Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints
JO  - Annales de la Faculté des sciences de Toulouse : Mathématiques
PY  - 2012
SP  - 557
EP  - 591
VL  - 21
IS  - 3
PB  - Université Paul Sabatier, Institut de mathématiques
PP  - Toulouse
UR  - http://archive.numdam.org/articles/10.5802/afst.1345/
DO  - 10.5802/afst.1345
LA  - en
ID  - AFST_2012_6_21_3_557_0
ER  - 
%0 Journal Article
%A Bousquet, Nicolas
%T Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints
%J Annales de la Faculté des sciences de Toulouse : Mathématiques
%D 2012
%P 557-591
%V 21
%N 3
%I Université Paul Sabatier, Institut de mathématiques
%C Toulouse
%U http://archive.numdam.org/articles/10.5802/afst.1345/
%R 10.5802/afst.1345
%G en
%F AFST_2012_6_21_3_557_0
Bousquet, Nicolas. Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 21 (2012) no. 3, pp. 557-591. doi : 10.5802/afst.1345. http://archive.numdam.org/articles/10.5802/afst.1345/

[1] Anonymous.— Open TURNS version 0.14.0 – Reference guide. Tech. rep., EDF-EADS-PhiMeca (2011).

[2] Bercu (B.).— Inégalités exponentielles pour les martingales [in french]. Journées ALEA 2008 CIRM p. 10-14 March (2008).

[3] Bester (C.), Hansen (C.).— Bias reduction for Bayesian and frequentist estimators. Working Paper. University of Chicago (2005).

[4] Cannamela (C.), Garnier (J.), Iooss (B.).— Controlled stratification for quantile estimation. Annals of Applied Statistics 2, p. 1554-1580 (2008). | MR | Zbl

[5] Chan (T.).— A (slightly) faster algorithm for Klee’s measure problem. p. 94-100, College Park, MD, USA (2008). | MR | Zbl

[6] Chen (G.).— Monotonicity of dependence concepts: from independent random vector into dependent random vector. World Academy of Science, Engineering and Technology 57, p. 399-408 (2009).

[7] Chlebus (B.).— On the Klee’s measure problem in small dimensions. Proceedings of the 25th Conference on Current Trends in Theory and Practice of Informatics (1998). | Zbl

[8] Cox (D.), Snell (E.).— A general definition of residuals. Journal of the Royal Statistical Society 30, p. 248-275 (1968). | MR | Zbl

[9] Crowder (M.).— Maximum likelihood estimation for dependent observations. Journal of the Royal Statistical Society 38, p. 43-53 (1975). | MR | Zbl

[10] Crowder (M.).— On constrained maximum likelihood estimation with non-iid. observations. Annals of the Institute of Statistical Mathematics 36, p. 239-249 (1983). | MR | Zbl

[11] Daniels (H.), Velikova (M.).— Monotone and partially monotone neural networks. IEEE Transactions in Neural Networks 21, p. 906-917 (2010).

[12] de Berg (M.), van Kreveld (M.), Overmars (M.), Schwarzkopf (O.).— Computational Geometry Algorithms and Applications. Springer-Verlag (1997). | MR | Zbl

[13] de Rocquigny (E.).— Structural reliability under monotony: A review of properties of FORM and associated simulation methods and a new class of monotonous reliability methods (MRM). Structural Safety 31, p. 363-374 (2009).

[14] Durot (C.).— Monotone nonparametric regression with random design. Mathematical Methods in Statistics 17, p. 327-341 (2008). | MR | Zbl

[15] Efron (B.), Tibshirani (R.J.).— An Introduction to the Bootstrap. New York: Chapman & Hall (1993). | MR | Zbl

[16] Erickson (J.).— Klee’s measure problem. Tech. rep., University of Illinois at Urbana-Champaign, URL: http://theory.cs.uiuc.edu/jeffe/open/klee.html (1998).

[17] Ferrari (S.), Cribari-Neto (F.).— On bootstrap and analytical bias correction. Economics Letters 58, p. 7-15 (1998). | MR | Zbl

[18] Figueira (J.), Greco (S.), Erhgott (M.).— Multiple criteria decision analysis – State of the art – Survey. Springer’s International Series (2005). | Zbl

[19] Fleischer (M.).— The measure of Pareto optima. Applications to multi-objective metaheuristics. vol. 262, p. 519-523, Faro, Portugal (2003). | Zbl

[20] Glynn (P.), Rubino (G.), Tuffin (B.).— Robustness properties and confidence interval reliability. In: Rare Event Simulation. Wiley (2009). | MR

[21] Hurtado (J.).— An examination of methods for approximating implicit limit state functions from the viewpoint of statistical learning theory. Structural Safety 26, p. 271-293 (2004).

[22] Kleijnen (J.).— Simulation optimization via bootstrapped kriging: Survey. Tech. rep., Rport from Tilburg University, Center for Economic Research (2011).

[23] Kleijnen (J.), van Beers (W.).— Monotonicity-preserving bootstrapped kriging metamodels for expensive simulations. Tech. rep., Discussion Paper 2009-75, Tilburg University, Center for Economic Research (2009).

[24] Kroese (D.), Rubinstein (R.).— Simulation and the Monte Carlo Method (2nd edition). Wiley (2007). | MR | Zbl

[25] Lemaire (M.), Pendola (M.).— PHIMECA-SOFT. Structural Safety 28, p. 130-149 (2006).

[26] Limbourg (P.), de Rocquigny (E.), Andrianov (G.).— Accelerated uncertainty propagation in two-level probabilistic studies under monotony. Reliability Engineering and System Safety 95, p. 998-1010 (2010).

[27] Lin (D.).— A new class of supersaturated design. Technometrics 35, p. 28-31 (1993).

[28] MacKay (M.), Beckman (R.), Conover (W.).— A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21, p. 239-249 (1979). | MR | Zbl

[29] Madsen (H.), Ditlevsen (O.).— Structural reliability methods. Wiley (1996).

[30] Meyer (P.A.).— Martingales and stochastic integrals. Lecture Notes in Mathematics Vol. 284. Springer-Verlag (1972). | MR | Zbl

[31] Morio (J.).— Influence of input pdf parameters of a model on a failure probability estimation. Simulation Modelling Practice and Theory 19, p. 2244-2255 (2011).

[32] Munoz-Muniga (M.), Garnier (J.), Remy (E.), de Rocquigny (E.).— Adaptive directional stratification for controlled estimation of the probability of a rare event. Reliability Engineering and System Safety (in press) (2011).

[33] Overmars (M.H.), Yap (C.K.).— New upper bounds in Klee’s measure problem. SIAM Journal of Computing 20, p. 1034-1045 (1991). | MR | Zbl

[34] Rajabalinejad (M.), Meester (L.), van Gelder (P.), Vrijling (J.).— Dynamic bounds coupled with Monte Carlo simulations. Reliability Engineering and System Safety 96, p. 278-285 (2011).

[35] Ranjan (P.), Bingham (D.), Michailidis (G.).— Sequential experiment design for contour estimation from complex computer codes. Technometrics 50, p. 527-541 (2008). | MR

[36] Rüschendorf (L.).— On the distributional transform, Sklar’s theorem, and the empirical copula process. Journal of Statistical Planning and Inference 139, p. 3921-3927. (2009) | MR | Zbl

[37] Shamos (M.I.), Hoey (D.).— Geometric intersection problems. Proceedings of the 17th IEEE Symposium about the Foundations of Computer Science (FOCS’76) p. 208-215 (1976). | MR

[38] Tsompanakis (Y.), Lagaros (N.), Papadrakakis (M.), Frangopol (D.e.).— Structural design optimization considering uncertainties. Taylor & Francis (2007).

[39] van Leeuwen (J.), Wood (D.).— The measure problem for rectangular ranges in d-space. Journal of Algorithms 2, p. 282-300 (1981). | MR | Zbl

Cité par Sources :