Mas 2012

Arnaud Guyader
Journées MAS de la SMAI
Clermont-Ferrand, 29-31 août 2012

Session Événements Rares

1 Présentation

L’objectif de cette session est d’offrir un aperçu de la simulation et de l’estimation d’événements rares, à la fois d’un point de vue méthodologique et applicatif. L’analyse d’événements rares est d’une importance cruciale dans les systèmes hautement sécurisés complexes, tels que les réseaux de télécommunications, les centrales nucléaires, les systèmes de contrôle de vol, la propagation d’épidémie, l’analyse bactériologique, domaines où les défaillances peuvent se traduire de façon catastrophique, que ce soit en pertes humaines, matérielles ou économiques.

L’estimation précise et la prévision des probabilités dans les systèmes complexes impose des contraintes fortes, non seulement au niveau théorique mais aussi numérique. Pour des probabilités très faibles, la méthode Monte-Carlo standard (i.e. diviser le nombre d’apparitions de l’événement d’intérêt par le nombre total d’essais) devient trop imprécise et il importe donc de recourir à des méthodes de réduction de variance. On en distingue deux grandes classes : échantillonnage préférentiel d’un côté (importance sampling), méthodes multi-niveaux de l’autre (multilevel splitting ou subset simulation). Cette session proposera une vue d’ensemble de ces méthodes ainsi que quelques exemples d’applications dans des domaines variés.

2 Exposés

2.1 Approximation de l’échantillonnage préférentiel à variance nulle, avec applications en fiabilité (Bruno Tuffin, INRIA)

La complexité croissante des systèmes induit la construction de modèles mathématiques de plus en plus lourds. Les méthodes traditionnelles d’analyse deviennent rapidement inapplicables, en raison d’hypothèses nécessaires trop fortes qui ne permettent pas de représenter suffisamment le système réel et/ou parce qu’elles requièrent un temps de calcul trop important. La simulation de Monte Carlo devient alors un outil pertinent. Dans le cas du calcul de probabilités d’événements rares, la méthode de Monte Carlo standard nécessite un nombre de réplications du système très grand pour observer l’événement ne serait-ce qu’une fois, et donc bien plus pour obtenir une estimation précise. Des techniques plus efficaces doivent donc être imaginées. Les deux classes majeures de méthodes sont l’échantillonnage préférentiel (importance sampling) et la ramification des trajectoires (splitting).

Nous nous focaliserons durant cet exposé sur l’échantillonnage préférentiel et quelques applications en analyse de la fiabilité des sytèmes. L’échantillonnage préférentiel consiste à changer les probabilités des événements dirigeant le système, de telle sorte que l’événement recherché ne soit plus rare, et à multiplier l’estimateur par le quotient de vraisemblance pour conserver un estimateur sans biais. Déterminer un choix satisfaisant d’échantillonnage est une tâche difficile en général, et notre objectif est de tirer profit de l’échantillonnage préférentiel à variance nulle, qui peut être exprimé théoriquement mais ne peut être implanté car nécessitant des valeurs dont la connaissance revient également à connaître la quantité que l’on cherche à estimer. Par contre, remplacer ces paramètres dans la formule d’échantillonnage préférentiel à variance nulle par une approximation bien choisie peut conduire à une technique de simulation très efficace. Dans un premier temps, nous décrirons un telle procédure en toute généralité. Nous illustrerons ensuite comment l’appliquer sur deux modèles spécifiques de fiabilité :

- Tout d’abord les systèmes markoviens hautement fiables souvent utilisés pour représenter l’évolution de systèmes multi-composants et dont l’espace d’états croît exponentiellement avec le nombre de classes de composants. L’objectif est de calculer la probabilité que le système atteigne un état de défaillance avant de revenir à l’état totalement opérationnel. L’échantillonnage à variance nulle peut être écrit exactement grâce à une fonction de valeurs donnant cette probabilité de défaillance à partir de n’importe quel état de la chaîne. Nous remplacerons cette fonction de valeurs par une approximation du premier ordre simple à obtenir et illustrerons que cette approche est bien plus efficace que les heuristiques d’échantillonnage préférentiel utilisées jusqu’ici pour cette classe de problèmes. Nous montrerons également qu’asymptotiquement, plus précisément quand la rareté est obtenue de manière classique via des défaillances de composants de plus en plus rares, notre estimateur vérifie la propriété d’erreur relative bornée et peut même satisfaire une propriété d’erreur relative évanescente, ce qui signifie que l’erreur relative converge vers zéro quand l’événement considéré devient de plus en plus rare.

- La seconde classe de problèmes concerne l’estimation de la fiabilité statique des réseaux, où l’on cherche à calculer la probabilité qu’un ensemble de nœuds restent connectés quand les liens peuvent aléatoirement être défaillants. Cette classe de problèmes appartient à la famille NP-difficile et la simulation de Monte Carlo est nécessaire pour fournir une estimation pour les problèmes de grande taille. Ici aussi, nous montrerons comment nous pouvons procéder avec l’échantillonnage préférentiel à variance nulle en échantillonnant l’état des liens un à un. La fonction de valeurs inconnue est ici la défiabilité du système étant donné l’état des liens déjà échantillonnés, et sera remplacée par la probabilité de la coupe minimale la plus probable. Nous montrerons que ici encore, sous certaines conditions, le système vérifie la propriété d’erreur relative bornée quand la fiabilité des liens tend vers 1 et que la propriété d’erreur relative évanescente peut être vérifiée. Si le temps le permet, nous expliquerons également comment la méthode peut être combinée avec d’autres techniques de réduction de variance, pour une efficacité accrue.

Cet exposé est basé sur des travaux avec Pierre L’Ecuyer (Université de Montréal), Gerardo Rubino et Samira Saggadi.

2.2 Bornes de probabilités d’événements rares dans le contexte d’une étude de sécurité en aéronautique (Yves Auffray, Dassault Aviation)

Lorsqu’une charge aéroportée est larguée, un point critique est le risque de collision avec l’avion porteur. La trajectoire de l’emport après séparation est fonction de variables de deux types. L’un est constitué par les paramètres pilotés par l’équipage : altitude, vitesse, facteur de charge etc. L’autre regroupe les variables qui échappent à son contrôle : turbulence, centrages etc. Pour l’usage de ces systèmes, il est crucial de fournir aux utilisateurs des contraintes sur les variables pilotées qui assurent des largages en sécurité. Dans cet exposé, nous présenterons une approche statistique de type Monte Carlo, exploitant un simulateur de trajectoires, qui fait l’hypothèse que les variables non contrôlées constituent un vecteur aléatoire simulable facilement. Le coût d’utilisation de ce simulateur rapporté au niveau de probabilité de collision spécifiant la sécurité du largage, interdit une simulation Monte Carlo massive. A la place, on procède par un échantillonnage préférentiel qui utilise comme loi d’importance un modèle réduit d’un score de dangerosité estimé sur la base d’une partie d’un budget maximal d’appels au simulateur.

2.3 A conditional limit theorem for random walks with application to Importance Sampling for rare events (Virgile Caron, UPMC)

Improving Importance Sampling estimators for rare event probabilities requires sharp approximations of conditional densities. This is achieved for events defined through large exceedances of the empirical mean of summands of a random walk, in the domain of large or moderate deviations. The approximation of conditional density of the trajectory of the random walk is handled on long runs. The length of those runs which is compatible with a given accuracy is discussed ; simulated results are presented, which enlight the gain of the present approach over classical Importance Sampling schemes. When the conditioning event is in the zone of the central limit theorem it provides a tool for statistical inference in the sense that it produces an effective way to implement the Rao-Blackwell theorem for the improvement of estimators.

2.4 Couplage des méthodes de stratification et de simulation directionnelle adaptative pour l’estimation de faibles probabilités sur des modèles à temps de calculs élevés (Miguel Munoz Zuniga, IRSN)

Dans le domaine de la fiabilité des structures, il est de coutume d’utiliser comme indicateur de fiabilité d’un matériel donnée la probabilité de défaillance de ce dernier. Dans ce contexte, de nombreuses méthodes ont été développées pour estimer cette probabilité. Cependant, il reste encore des circonstances dans lesquelles l’estimation n’est pas fiable et/ou réalisable en un temps raisonnable. Nous supposons être en présence des contraintes industrielles suivantes : la fonction de défaillance représentant le comportement de la structure étudiée est complexe et lourde en temps de calculs, aucune hypothèse de régularité n’est supposée sur la fonction de défaillance, la défaillance est un évènement rare et enfin l’estimation doit être robuste, c’est-à-dire accompagnée d’un contrôle sur l’erreur d’estimation. Nous proposons et analysons une méthode originale de Monte-Carlo accélérée satisfaisant au mieux les contraintes introduites précédemment. Cette méthode couple les techniques de simulation directionnelle et de stratification en une stratégie adaptative partiellement parallélisable. Sous certaines hypothèses, nous présentons également un certain nombre d’améliorations de notre nouvelle méthode, afin d’atteindre de plus grandes dimensions en entrée (< 10) et de minimiser les temps de calculs. En particulier la méthode est comparée à la méthode Subset Simulation. Pour terminer, des prolongements de la méthode dans le cadre de l’analyse de sensibilité sont proposés via l’introduction et l’analyse de plusieurs indicateurs permettant la hiérarchisation des paramètres aléatoires d’entrée selon leurs contributions à la défaillance.