Échantillonnage préférentiel - Définition

Introduction

L'échantillonnage préférentiel, en anglais importance sampling, est une méthode de réduction de la variance qui peut être utilisée dans la méthode de Monte-Carlo. L'idée sous-jacente à l'échantillonnage préférentiel, EP dans la suite, est que certaines valeurs prises par une variable aléatoire dans une simulation ont plus d'effet que d'autres sur l'estimateur recherché. Si ces valeurs importantes se réalisent plus souvent, la variance de notre estimateur peut être réduite.

Par conséquent la méthode de l'EP est de choisir une distribution qui « encourage » les valeurs importantes. L'utilisation d'une distribution biaisée conduira à un estimateur biaisé si nous l'appliquons directement aux simulations. Cependant, les différentes simulations sont pondérées afin de corriger ce biais ; l'estimateur EP est alors sans biais. Le poids qui est donné à chaque simulation est le ratio de vraisemblance, qui est la densité de Radon-Nikodym de la vraie distribution par rapport à la distribution biaisée.

Le point fondamental dans l'implémentation d'une simulation utilisant l'EP est le choix de la distribution biaisée. Choisir ou créer une bonne distribution biaisée est l'art des EP. L'avantage peut alors être une énorme économie de temps de calculs alors que l'inconvénient pour une mauvaise distribution peut être des calculs plus longs qu'une simple simulation de Monte-Carlo.

Théorie

En Monte-Carlo

On souhaite estimer une quantité G, qui s'exprime sous la forme d'une intégrale :

On considère ici une intégration en dimension 1, mais on peut généraliser à une dimension quelconque.

Le principe de base des méthodes de Monte-Carlo est de voir l'intégrale précédente comme

où X est une variable aléatoire uniformément distribuée sur [a;b] et sa densité.

Si on dispose d'un échantillon , identiquement et indépendamment distribué (i.i.d.) selon U([a;b]), on peut estimer G par :

Il s'agit, d'après la loi des grands nombres, d'un estimateur de G non-biaisé (c'est-à-dire que ). Sa variance est :

avec la variance de la variable aléatoire g(X)

L'échantillonnage préférentiel

L'idée principale de l'échantillonnage préférentiel est de remplacer dans la simulation la densité uniforme sur [a;b] par une densité alternative (ou densité biaisée), disons , qui tente d'imiter la fonction g. Ce faisant, on remplace les tirages uniformes, qui n'avantagent aucune région, par des tirages plus « fidèles ». Ainsi, l'échantillonnage est fait suivant l'importance de la fonction g: il est inutile de tirer dans les régions où g prend des valeurs non-significatives, pour, au contraire, se concentrer sur les régions de haute importance. On espère ainsi diminuer la variance . Autrement dit, si on se fixe un niveau d'erreur donné, l'EP permet de diminuer théoriquement le nombre de simulations N par rapport à une méthode de Monte-Carlo classique.

L'intégrale à estimer est ré-écrite comme:

ce qui revient à:

où on a posé (appelé ratio de vraisemblance) et où X est simulé selon la densité . Il est facile de généraliser les résultats précédents: l'estimateur de G est

où est un échantillon i.i.d. selon la densité . La variance de l'estimateur est donnée par

avec enfin

Dès lors, le problème est de se concentrer sur l'obtention d'une densité biaisée telle que la variance de l'estimateur EP soit moindre que celle de la méthode de Monte-Carlo classique. La densité minimisant la variance (qui la rend nulle sous certaines conditions) est appelée densité biaisée optimale. Cette dernière est égale à

mais ce choix est inopérant, car on recherche justement le dénominateur. Mais, on peut s'attendre à réduire la variance en choisissant une densité reproduisant la fonction g.

En quasi Monte Carlo

Pour estimer l'intégrale on peut également se passer de tout le formalisme probabiliste précédent. Au lieu d'utiliser des variables aléatoires, on se sert de suites à faible discrépance (suites de Sobol par exemple). En dimension 1 l'approche la plus simple est

De même qu'en Monte Carlo usuel, cette approximation de l'intégrale converge d'autant plus vite que la fonction g est proche d'une constante. Si g est rigoureusement constante il suffit de prendre N = 1 pour avoir l'intégrale exacte. Réduire la variance de g est par conséquent crucial ici aussi ; dans ce but, l'échantillonnage préférentiel s'utilise comme suit :

où l'on a fait le changement de variable y = F(x) avec . Il apparaît clairement que si alors la fonction à intégrer à droite est proche de la constante 1 (de faible variance donc).

Pour faire le lien avec l'interprétation probabiliste de la section précédente, on remarque que f^* est définie à un facteur K près qui disparaît dans le quotient. On peut donc imposer que , ce qui en fait une densité de probabilité sur [a, b]. Le changement de variable s'interprète alors naturellement comme un changement de probabilité et on a la simplification :

Cette technique se généralise immédiatement en dimension quelconque.