Monte Carlo échantillonnage stratifié

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Rineku
Messages: 6
Enregistré le: 06 Avr 2017, 19:19

Monte Carlo échantillonnage stratifié

par Rineku » 06 Avr 2017, 19:28

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:

I = E[f(X)] = Ji * pi
où Ji= SOMMEi( E[f(X )| X ∈ Di] ) et pi =P(X ∈ Di)

On crée une partition de l'ensemble d'intégration D (ce sont les D[small]i[/small] 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 Ji associé à son ensemble Di en utilisant MC classique. Chaque Jiest ensuite multiplié par son coefficient pi cad P(X ∈ Di).

Mes problèmes sont les suivants:

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

Pour le calcul des P(X ∈Di), 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:
-D1=[0;0.7]*[0;0.7]
-D2=[0.7;1]*[0,7;1], on aurait:
P(X ∈ D1)= ((0,7-0)+(0,7-0)) / ((1-0)+(1-0)) = 0.7
P(X ∈ D2)= ((1-0,7)+(1-0,7)) / ((1-0)+(1-0)) = 0.3

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



pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Monte Carlo échantillonnage stratifié

par pascal16 » 06 Avr 2017, 23:01

J'ai fait la méthode classique de MC en TD de seconde(pi à 0.01 près avec 10 000 000 le lancers) mais jamais la startifiée.
C'est la même chose pour l'intégrale d'une fonction vue par les aires

Comment améliorer la méthode :
0) découpage simple en n intervalles (horizontaux ou verticaux) : ne sert à rien, si on fait 1 000 tests aléatoires dans 10 intervalles identiques, on ne fait rien de mieux que 10 000 tests dans 1 intervalle.
1) découpe intelligente.
si pour 0<x<1 on a 1<f(x)<3 et pour 1<x<2 on a 2<f(x)<4
1a) on peut faire deux rectangles [0;1][0;3] et [1;2][0;4] (on s’arrête à un majorant de f).
la surface totale reste la somme des surfaces. Gain attendu assez faible.
1b) on peut faire deux rectangles [0;1][1;3] et [1;2][2;4] (on encadre f).
la surface totale reste la somme des surfaces plus [0;1][0;1] et [1;2][0;2]

la 1b revient à ce que l'on fait au bac.
-> on compte les rectangles unités pleins pour avoir une approx
-> on rajoute les 'restes' ici par la méthode de MC
On peut voir plus nettement par le principe de base de Riemann :
-> on a 2 fonctions en escalier qui encadrent la fonction
-> on choisi un découpage commun aux deux fonctions
-> on calcul les aires des rectangles minimisants à laquelle on rajoute l'air entre les rectangles minimisants et la fonction par MC (au passage, avoir les 2 fonctions en escalier permet de gérer le cas où f est négative).

Je ne connais pas la réponse, mais si je devrais améliorer la méthode de MC, je ferais comme ça : on encadre simplement la fonction et sur seulement ce qui reste, on fait une MC.

PS : Elle est où la fonction à intégrer ? Le découpage en dépend
PS2 : ça donne envie de reprendre des études math/info.

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Monte Carlo échantillonnage stratifié

par pascal16 » 07 Avr 2017, 14:30

J'ai vu que tu ne maîtrisait pas bien la base de la méthode MC.

L'exemple de base cité partout : approximation de pi.
on va partir d'un domaine D=[-1;1]*[-1;1]
un point pris au hasard dans ce carré est dans le cercle de rayon 1 et de centre O si la distance qui le sépare de O est inférieur à 1.

Algo basique
je prends un réel x entre -1 et 1 qui sera mon abscisse
je prends un réel y entre -1 et 1 qui sera mon ordonnée
je calcul r=sqrt(x²+y²)
si r <1n j'augmente mon compteur c de 1
je répète N fois cette opération.

La fréquence observée f=c/N se rapproche de la probabilité d'avoir choisi un point au hasard du carré qui soit dans le disque de rayon 1 et de centre O.
Le calcul de la fréquence n'a pas besoin de calcul de surface type.

Calcul de la probabilité théorique
surface du carré 2*2 = 4 (on peut dire aussi )
surface du cercle pi*r²=pi (qu'on peut voir aussi comme )
la probabilité vaut pi/4
donc la valeur 4f est une approximation de pi ici, on remarquera que 4 est la surface totale, c'est là qu'entre la surface dans le calcul.

Pour les strates, tu fais l’expérience aléatoire, tu calcules chacune des fréquences fi, et pour avoir la surface totale, il faut faire la somme ded fi*Di
fi*Di te donne la partie de l'intégrale sur chaque Di
la somme des fi*Di te donne l'intégrale sur D, c'est pour ça que les Di doivent former une partition de D.

Choix de Di : ils dépendent de la fonction, et généralement, c'est bien un encadrement en escaliers de la fonction qui marche le mieux. Ca ne sert à rien de générer des nombres aléatoires là où on est sur d'être en dehors de la surface sous la courbe et ça ne sert à rien non plus de tester des points évidement en dehors.

Rineku
Messages: 6
Enregistré le: 06 Avr 2017, 19:19

Re: Monte Carlo échantillonnage stratifié

par Rineku » 07 Avr 2017, 21:04

Bonjour,
Je suis tout à fait d'accord avec ce que vous avez dit, l'exemple du calcul de pi étant l'exemple le plus typique pour aborder la notion de MC. Votre façon d'amener les choses est vrai je ne peut pas du tout vous contredire

Néanmoins je reste sur l'idée que le calcul des aires fonctionne. Je vous ai envoyé un extrait d'un cours fort intéressant à ce sujet à la fin de mon message pour appuyer ma façon de voir le sujet.

Pour résumer, on cherche à calculer l'intégrale de h sur l'ensemble D:

étant la fonction indicatrice.

et après quelques lignes (détaillées sur l'image) on arrive à la relation:



La dernière relation est très intéressante car elle nous dit que l'intégrale qu'on chercher peut être approximer par une espérance. Une espérance dont la variable est le volume de D multiplié par h(x).

Si je souhaitais intégrer une fonction h sur ,
Je devrais calculer l'espérance
est une variable aléatoire qui va varier sur l'ensemble D.

Et c'est là qu'un théorème très important entre en jeu: le théorème de la loi forte des grands nombres. Je passe certaines conditions car on y passerai toute la journée sinon, mais vulgairement dans notre cas, il signifie que l'espérance peut être approximé par une moyenne empirique si on simule un grand nombre de fois Z_1.

C'est à dire qu'on a
Si N, le nombre de test qu'on fait est très grand.

Donc cela signifie que faire la moyenne sur un grand nombre d'aires des rectangles nous rapproche de l'espérance donc de la valeur de l'intégrale.


Maintenant si je reviens sur les strates, je vous remercie pour vos explications, vous m'avez confirmé pas mal de point. Seul petit point encore flou, le choix de : Auriez vous un ou deux exemples à donner pour illustrer cette idée? Vous dites que cela dépend de la fonction, mais que voulez vous dire par là? Y a-t-il des groupes de fonctions? C'est le gros problème qui me coince pour avancer. A noter que je m'intéressent uniquement aux intégrales à plusieurs dimensions sur

J'espère ne pas avoir dit trop de bêtise. :?
Dans tous les cas merci beaucoup pour votre aide et le temps que vous me consacrez, le simple fait d'en discuter me donne vraiment l'impression d'être plus à l'aise !


(Voici l'extrait dont je vous parlais et son lien si jamais la photo est bloquée) https://image.noelshack.com/fichiers/2017/14/1491584311-extrait-cours.png
Image

pascal16
Membre Légendaire
Messages: 6663
Enregistré le: 01 Mar 2017, 14:58
Localisation: Angoulème : Ville de la BD et du FFA. gare TGV

Re: Monte Carlo échantillonnage stratifié

par pascal16 » 07 Avr 2017, 23:16

sur wiki anglais, il y a une représentation visuelle :

https://en.wikipedia.org/wiki/Monte_Carlo_integration

A ce que j'ai compris.
-> on découpe en plein de petit carrés
-> si dans un carré on est toujours dans la zone à mesurer (écrat type de 0 en fait), on génère peu de nombres
-> idem si un carré on est toujours hors de la zone à mesurer
-> si dans un carré on est parfois dedans, parfois dehors,(écart type fort) on génère plein de nombres

On fait un découpage simple, l'algo choisi lui-même les zones à explorer. Donc ici, plutôt que de choisir des zones à la main avec une méthode on/off, l'ago fait du gris clair-gris foncé tout seul.
Je pense que c'est pour ça qu'on ne parle que très peu des Di, car en fait c'est le choix du nombre de d'essais dans chaque Di qui est important.

la page 19 parle de cette technique : le choix du nombre d'essais dans chaque zone :
http://cermics.enpc.fr/~bl/PS/SIMULATIO ... arlo-x.pdf

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 72 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite