Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints

Nicolas Bousquet[1]

  • [1] EDF Research & Development Dpt. of Industrial Risk Management 6 quai Watier, 78401 Chatou, France

Annales de la faculté des sciences de Toulouse Mathématiques (2012)

  • Volume: 21, Issue: 3, page 557-591
  • ISSN: 0240-2963

Abstract

top
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.

How to cite

top

Bousquet, Nicolas. "Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints." Annales de la faculté des sciences de Toulouse Mathématiques 21.3 (2012): 557-591. <http://eudml.org/doc/250992>.

@article{Bousquet2012,
abstract = {The problem of estimating the probability $\{p\}=P(g(\{\bf X\})\le 0)$ is considered when $\{\bf 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.},
affiliation = {EDF Research & Development Dpt. of Industrial Risk Management 6 quai Watier, 78401 Chatou, France},
author = {Bousquet, Nicolas},
journal = {Annales de la faculté des sciences de Toulouse Mathématiques},
keywords = {maximum likelihood},
language = {eng},
month = {4},
number = {3},
pages = {557-591},
publisher = {Université Paul Sabatier, Toulouse},
title = {Accelerated Monte Carlo estimation of exceedance probabilities under monotonicity constraints},
url = {http://eudml.org/doc/250992},
volume = {21},
year = {2012},
}

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
DA - 2012/4//
PB - Université Paul Sabatier, Toulouse
VL - 21
IS - 3
SP - 557
EP - 591
AB - The problem of estimating the probability ${p}=P(g({\bf X})\le 0)$ is considered when ${\bf 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.
LA - eng
KW - maximum likelihood
UR - http://eudml.org/doc/250992
ER -

References

top
  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). Zbl1156.62023MR2655671
  5. Chan (T.).— A (slightly) faster algorithm for Klee’s measure problem. p. 94-100, College Park, MD, USA (2008). Zbl1221.65059MR2504275
  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). Zbl0936.68055
  8. Cox (D.), Snell (E.).— A general definition of residuals. Journal of the Royal Statistical Society 30, p. 248-275 (1968). Zbl0164.48903MR237052
  9. Crowder (M.).— Maximum likelihood estimation for dependent observations. Journal of the Royal Statistical Society 38, p. 43-53 (1975). Zbl0324.62023MR403035
  10. Crowder (M.).— On constrained maximum likelihood estimation with non-iid. observations. Annals of the Institute of Statistical Mathematics 36, p. 239-249 (1983). Zbl0553.62027MR758500
  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). Zbl0939.68134MR1470713
  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). Zbl1231.62066MR2483461
  15. Efron (B.), Tibshirani (R.J.).— An Introduction to the Bootstrap. New York: Chapman & Hall (1993). Zbl0835.62038MR1270903
  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). Zbl0899.90043MR1608586
  18. Figueira (J.), Greco (S.), Erhgott (M.).— Multiple criteria decision analysis – State of the art – Survey. Springer’s International Series (2005). Zbl1060.90002
  19. Fleischer (M.).— The measure of Pareto optima. Applications to multi-objective metaheuristics. vol. 262, p. 519-523, Faro, Portugal (2003). Zbl1036.90530
  20. Glynn (P.), Rubino (G.), Tuffin (B.).— Robustness properties and confidence interval reliability. In: Rare Event Simulation. Wiley (2009). Zbl1165.62026MR2730762
  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). Zbl1147.68831MR2365210
  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). Zbl0415.62011MR533252
  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). Zbl0239.60001MR426145
  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). Zbl1237.57029
  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). Zbl0737.68045MR1135747
  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). MR2655651
  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) Zbl1171.60313MR2553778
  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). MR455532
  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). Zbl0487.68032MR632450

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.