Forum de mathématiques - Bibm@th.net

Dédé4

Invité

Monte carlo avec échantillonnage stratifié

Bonjour,
       
       Je ne suis pas sur d'être au bon endroit dans ce cas je m'excuse...

Je suis étudiant en bac+3 en mathématiques et info et j'ai quelques recherches à faire sur l'approximation d'intégrales multidimensionnelles à l'aide des méthodes de Monte Carlo: La "classique" à comparé avec celle basée sur l'échantillonnage stratifié.

La méthode de monte Carlo (MC) classique est très simple à comprendre et à mettre en place algorithmiquement: Si j'ai bien compris, grossièrement on choisit une valeur x au hasard dans le/les intervalles d'intégration, noté D, et on calcule l'aire du rectangle:  x*f(x).
On répète le processus n fois pour faire la moyenne des résultats. Par la loi des grands nombres, pour n assez grand, cette moyenne empirique se rapproche de l'espérance qu'on cherche à calculer. Cette espérance correspondant à la valeur de l'intégrale.
Si une erreur a été dite je suis prêt à vous écouter mais normalement je suis ok sur ce point.

On cherche ensuite à minimiser l'erreur d'approximation de cette méthode en réduisant la variance. On cherche alors de nouvelles méthode dont la méthode de MC par l'échantillonnage stratifié. Le principe est d'approximer notre intégrale I par:

\begin{equation} I =  E[f(X)] = \sum_{i=1}^{n}E[f(X )| X ∈ D_i]*P(X  \in    D_i)
\end{equation} on notera
\begin{equation}
J_i= E[f(X )| X \in Di] \end{equation}et\begin{equation}
p_i =P(X  \in    D_i)  \end{equation}

On crée une partition de l'ensemble d'intégration D (ce sont les D_i qu'on appelle strate) et on applique la méthode de MC classique pour chacune de ces strates. C'est à dire que l'on va approximer chaque J_i associé à son ensemble D_i en utilisant MC classique. Chaque J_i est ensuite multiplié par son coefficient p_i cad P(X ∈ D_i).

Mes problèmes sont les suivants:

1) Comment choisit on les strates D_i? Car le but étant bien sûr d'optimiser le résultat cad de rendre l'approximation le plus précis possible. Je dois avouer qu'ici je n'ai absolument aucune idée de ce qu'il faut faire....

2) Une fois les D_i trouvés, comment fait-on pour calculer P(X  ∈ D_i)? Après de nombreuses recherches sur internet aucune explication n'a été donnée sur ce point non plus.
Excepté un point: P(X ∈ UD_i)=1. Cette relation est assez logique à comprendre: X est forcément dans l'intervalle D d'intégration et UD_i=D. Je n'ai pas les mots pour l'expliquer mais je comprends parfaitement la signification de P(X ∈D_i).

Pour le calcul des P(X ∈ D_i), l'idée qui me vient est de calculer la somme de la longueur de chacun des intervalles de ma strate et de le diviser par la somme des intervalles d'intégration. Voici un exemple simple pour illustrer mon idée:

Si mon intervalle est [0,1]*[0,1] et que je décide de créer 2 strate:
-D₁=[0;0.7]*[0;0.7]
-D₂=[0.7;1]*[0,7;1], on aurait:
P(X ∈ D₁)= ((0,7-0)+(0,7-0)) / ((1-0)+(1-0)) = 0.7
P(X ∈ D₂)= ((1-0,7)+(1-0,7)) / ((1-0)+(1-0)) = 0.3
On obtient bien 0.7+0.3=1

3) Est ce que quelqu'un parmi vous aurait un exemple concret à donner ? Je suis quelqu'un qui comprend assez vite dès lors que j'ai un ou deux exemple sous la main mais le problème étant que je n'ai rien trouvé sur internet....Par des exemples, j'entends dire des exemples d'intégrales où je pourrais éventuellement travailler dessus à l'aide de programme.

Je vous remercie d'avance pour votre réponse et le temps que vous m'apportez, je ne sais pas si j'ai été clair mais si vous avez des questions/ des critiques je suis prêt à les écouter :-D

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Monte carlo avec échantillonnage stratifié

Bonsoir,
D'un point de vue strictement mathématique, n'importe quelle partition de l'ensemble d'intégration initial marche ($D = \bigcup D_i$ et $D_i \cap D_j = \emptyset$ pour $i \neq j$). Le choix va beaucoup dépendre de la fonction à intégrer. L'idée est que dans les zones où la fonction ne présente pas beaucoup de variabilité, on utilisera peu de points, et on tirera plus de points là où la fonction présente de l'information. Il n'y pas de recette générale (ou du moins je n'en connais pas).

Pour le calcul concret des $P(X \in D_i)$, la définition est précisément $\displaystyle P(X \in D_i) =   \int_{D_i} d\pi(x)$ où $\pi$ est la loi de probabilité du problème considéré (à savoir, l'approximation de $\displaystyle \int_D f d\pi(x)$). Dans le cas d'une loi uniforme sur $D$ (calcul de $\displaystyle \dfrac{1}{\mu(D)}\int_D f(x)d\mu(x)$ où $\mu$ est la mesure de Lebesgue), le calcul que tu présentes est correct : $P(X \in D_i) = \dfrac{\mu(D_i)}{\mu(D)}$  ($\mu([a,b])=b-a$ et $\mu([a,b]\times[c,d])=(b-a)(d-c)$, etc).

Je n'ai pas vraiment d'exemple à te proposer.

Dernière modification par Yassine (06-04-2017 21:22:11)

Dédé4

Invité

Re : Monte carlo avec échantillonnage stratifié

Merci beaucoup pour vos précisions! Certains points deviennent plus limpides! Le dernier petit soucis étant ces fameuses strates \(D_i\)

Que voulez vous dire par les endroits qui présentent peu de variabilités? Le fait est que je cherche à approximer des intégrales multidimensionnelles . Dois-je donc étudier les variations de ma fonction? Monte Carlo etant sensé être utilisé pour des intégrales à très très grandes dimensions cela me semble être un peu compliqué à faire non?

Dans tout les cas merci pour votre aide et pour le temps que vous m'avez consacré!

Yassine

Membre

Inscription : 09-04-2013

Messages : 1 090

Re : Monte carlo avec échantillonnage stratifié

Bonjour,
La détermination de ces fameuses strates est plus de l'art que de la science !
Il faut tirer profit de la connaissance particulière qu'on a de la fonction à intégrer.
Dans mon cas, j'ai appliqué le MC au domaine de la finance, pour évaluer l'espérance d'instruments financier en fonction de paramètres de marché (Taux, volatilité, etc.). La connaissance du contrat (type : si le taux dépasse tel niveau, il se passe tel événement) permet d'identifier les zones où la fonction va beaucoup varier. A l'inverse, je pouvait également identifier les zones où la fonction avait un comportement très stable. Si on ne peut faire q'un million de tirages par exemple (pour des raisons de temps de calcul) en grande dimension, il vaut mieux concentrer les tirages dans les zones où il y a de l'information. 

Si maintenant on n'a aucune connaissance de la fonction à intégrer, cette technique n'est pas forcément très adaptée et il faut chercher d'autres techniques de réduction de variance (variables antithétiques, variable de contrôle ("control variates" en anglais), ...)