Importance sampling

Un article de Wikipédia, l'encyclopédie libre.

L'Importance sampling (IS) 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'IS est que certaines valeurs prises par une variable aléatoire dans une simulation ont plus d'impact 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éthodologie de l'IS 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 IS 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 vrai distribution par rapport à la distribution biaisée.

Le point fondamental dans l'implémentation d'une simulation utilisant l'IS est le choix de la distribution biaisée. Choisir ou créer une bonne distribution biaisée est l'art des IS. 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.

[modifier] Approche Mathématique

Considérons que nous voulons estimer par simulation la probabilité $p_t\,$ d'une événement ${ X \ge t\ }$ où $X$ est une variable aléatoire de fonction de distribution $F$ et de densité $f(x)= F'(x)\,$ . Un $\left(X_i\right)_{i \in\{1,\dots,K\}}$ échantillon identiquement et indépendamment distribué (i.i.d.) est tiré dans cette loi. On note $k t$ le nombre de réalisation supérieures à $t$ . $k t$ est une variable aléatoire suivant une loi binomiale.

$P(k_t = k)={K\choose k}p_t^k(1-p_t)^{K-k},\,\quad \quad k=0,1,\dots,K.$

L'importance sampling entre en jeu par la détermination et l'utilisation d'une autre densité $f_*\,$ (pour X), nommée densité biaisée, pour les simulations. Cette densité permet à l'événement ${ X \ge t\ }$ de se produire plus souvent, alors le nombre de simulation $K$ diminue pour une variance de l'estimateur fixée. D'une manière parallèle, pour un nombre $K$ donné de simulations, l'utilisation d'une densité biaisée donnera un résultat dont la variance est moindre que celle d'une méthode de Monte Carlo classique. À partir de la définition de $p_t\,$ , nous pouvons définir $f_*\,$ comme il suit.

$p_t = {E} [X \ge t]$

$= \int (x \ge t) \frac{f(x)}{f_*(x)} f_*(x) \,dx$

$= {E_*} [(X \ge t) W(X)]$

où

$W(\cdot) \equiv \frac{f(\cdot)}{f_*(\cdot)}$

est le ratio de vraisemblance et est utilisé comme fonction pondératrice. La dernière égalité de l'équation précédente suggère l'estimateur de $p t$ suivant :

$\hat p_t = \frac{1}{K}\,\sum_{i=1}^K (X_i \ge t) W(X_i),\,\quad \quad X_i \sim f_*$

C'est un estimateur de $p_t\,$ par la méthode IS et il est sans biais. Ceci étant définit, la procédure d'estimation est de générer un échantillon i.i.d. à partir de la densité $f_*\,$ et pour chaque réalisation dépassant $t\,$ de calculer son poids $W\,$ . Le résultat sera la moyenne obtenue avec $K\,$ tirages. La variance de cet estimateur est :

$var_*\hat p_t = \frac{1}{K} var_* [(X \ge t)W(X)]$

$= \frac{1}{K}\Big[{E_*}[(X \ge t)^2 W^2(X)] - p_t^2 \Big]$

$= \frac{1}{K}\Big[{E}[(X \ge t)^2 W(X)] - p_t^2 \Big]$

Dès lors, le problème est de se concentrer sur l'obtention d'une densité biaisée $f_*\,$ telle que la variance de l'estimateur IS 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.