Convergence Monte-Carlo

[invite6f25a1fe]

Bonjour,

En regardant les articles/documents sur les méthodes de Monte-Carlo basiques, on voit que sa vitesse de convergence est en , où N est le nombre d'échantillon.

Une phrase suit en générale disant que cette vitesse de convergence est indépendante du nombre de dimension mais que la convergence est lente... bon OK ca me va bien.

Ma question est : intuitivement j'imagine qu'avec une méthode MC donnée, il sera pourtant plus long de converger un problème de dimension 3 par exemple qu'un problème de dimension 1. Mais si ce n'est pas la vitesse de convergence qui change, où est ce que cette différence selon le nombre de dimension intervient ? Est ce le point de départ qui est différent : typiquement on partirait de "plus loin" en grande dimension qu'en petite dimension, donc à vitesse de convergence égale on mettrait plus de temps à atteindre une erreur donnée ?

Je n'arrive pas à exprimer cette différence de façon mathématique, histoire de me clarifier les idées. Quelqu'un pourrait m'aider ?

Merci à tous, en espérant avoir été assez clair sur ma question...
-----

[Médiat]

Bonjour,

Est-ce que vous ne faites pas une confusion entre vitesse de convergence et nombre de calculs à effectuer ?

[invite6f25a1fe]

Hmmm non je ne pense pas... la vitesse de convergence ne change pas en fonction de la dimension alors que le nombre de calculs oui, donc je conçois bien que les 2 sont différents !
Intuitivement je dirais que mon erreur après N calculs c'est :
, la vitesse de convergence étant de (avec une constante devant bien sûr) indépendant du nombre de dimension. Donc le seul autre endroit où la dimension du problème peut jouer, c'est dans le , non ? Mais je ne vois pas bien pourquoi il évoluerait avec la dimension... ou alors je suis à côté de la plaque complètement :S

[invite6f25a1fe]

Personne n'est capable de m'expliquer cette différence ? Je n'arrive pas à trouver des documents claires sur cette question ...

Ma question posée autrement c'est : à erreur finale donnée, quel est le nombre de calculs nécessaires pour faire un Monte-Carlo pour le même problème en 1D, 2D, 3D etc... ?

[A voir en vidéo sur Futura]

[invite9dc7b526]

Je pense que personne ne te répond parce que ta question n'est pas assez précise. Par "methode de Monte Carlo" on entend beaucoup de choses différentes. Tu penses peut-être à l'estimation d'une espérance? Dans ce cas, le théorème de la limite centrale donne une vitesse de convergence qui ne dépend pas de la dimension du problème, c'est un fait (attention toutefois aux constantes). En estimation fonctionnelle par contre, on peut avoir des vitesses de convergence qui dépendent de la dimension.

[invite6f25a1fe]

Merci pour ta réponse, mais effectivement je ne me fais pas comprendre :S J'essaye de reformuler ma question par un problème simple :

Je considère du Monte-Carlo classique pour estimer une espérance. Monte-Carlo a une vitesse de convergence qui ne dépend pas de la dimension. Mais qu'en est-il du nombre de tirage nécessaire (sous-entendu pour espérer avoir une erreur finale donnée, disons 1%). Dis très simplement :

"Est-il aussi facile (entendre par là "coûteux" au sens du nombre de tirages à réaliser) d'estimer une aire (2D) qu'un volume (3D) par du Monte-Carlo ?"

- Si c'est "oui", alors pas de soucis
- Si c'est "non", comme on le dirait intuitivement, alors pourquoi ? La différence entre les deux (2D vs 3D) ne vient pas de la "vitesse de convergence" je suis bien d'accord avec ça, mais la différence viendrait d'où alors ?

Merci encore à vous

[invite9dc7b526]

La vitesse de convergence est donnée comme fonction du nombre de tirages. Je ne comprends pas ton interrogation.

[invite6f25a1fe]

Donc pour toi je peux espérer la même précision (ou erreur) sur l'approximation de mon aire que sur l'approximation de mon volume, à nombre de tirage fixé ? J'ai du mal à le croire...

Pour moi la vitesse de convergence me dit uniquement à quelle "vitesse" je me rapproche de ma solution selon le nombre de tirage, et non pas qu'elle est l'erreur elle même (on ne part forcément de la même erreur initiale dans un problème à 2 dim. qu'à 20000 dim., si ?). Si on ne part pas avec la même erreur, la vitesse de convergence étant la même, ca voudrait dire qu'à erreur finale donnée il me faudra plus de tirages dans un cas que dans l'autre...

Typiquement j'aurais dit qu'il m'aurait fallu plus de tirages pour approximer une intégrale en dimension 20000 qu'en dimension 2.

Mais je dois être vraiment à côté de la plaque en fait, désolé.

[gg0]

Finalement,

tu sembles bien confondre "vitesse de convergence" et "nombre de calculs à effectuer pour obtenir un certain résultat". La notion "d'erreur initiale" me semble d'ailleurs dangereuse, dans une méthode probabiliste.
Il serait peut-être bon que tu revoies ce qu'est la "vitesse de convergence", qui n'a pas de rapport direct avec la qualité du résultat. Qualité qui dépend bien entendu du problème à traiter, donc en particulier pour une intégration par cette méthode, de la dimension.
Je n'ai d'ailleurs pas compris, dans ton message #3, pourquoi tu refuses que puisse dépendre des conditions du problème, en particulier de la dimension. Ta problématique est d'ailleurs malsaine dans ce message #3, l'idée intuitive est plutôt :
pour n suffisamment grand, avec A qui dépend des conditions du problème.

Cordialement.

[invite9dc7b526]

Mais je dois être vraiment à côté de la plaque en fait, désolé.

c'est peut-être moi qui emploie la terminologie à tort et à travers. Quand je parle de vitesse de convergence je pense en fait à l'anglais "rate" mais je crois qu'en français on dit plutôt "ordre" de convergence. L'ordre de convergence c'est la puissance (ici -1/2) à laquelle il faut élever le nombre de v.a. pour avoir un équivalent asymptotique de l'erreur. Si tu veux estimer l'erreur plus précisément, il faut calculer une constante multiplicative, laquelle dépend de la fonction à intégrer, et partant de la dimension de ton problème. Il ne faut pas oublier non plus que les résultats sont asymptotiques. A distance finie il peut se passer des choses.

[invite6f25a1fe]

OK d'accord et merci pour votre patience, on a effectivement pas tous le même vocabulaire (bon comme tout physicien j'ai une sale tendance à ne pas être précis sur le vocabulaire matheux :S). Du coup gg0 semble assez d'accord avec ce que je pensais, sauf que mon vocabulaire n'était pas correcte du tout, d'où certains mal-entendus.

Il faut effectivement que je revoie ma définition de "vitesse de convergence". Est ce que c'est le "-1/2", le "1/sqrt(N)", le "A/sqrt(N)", ou autre chose ...

Donc si je reprends la notation de gg0, on est d'accord que dans l'erreur , on a une partie indépendante de la dimension pour un Monte Carlo (le 1/sqrt(N)), et la constante A qui elle dépend du problème et de la dimension, mais pas du nombre de tirages..

Finalement on en vient à la vrai question que je me pose. Dans l'expression de gg0 pour reprendre sa notation, le "1/sqrt(N)" ne dépend que du nombre de tirages. Donc le problème et notamment sa dimension impacte uniquement le terme "A". (C'est ce que j'essaye de dire depuis le début, mais surement très mal ... ). Mais est ce qu'il est facile de connaitre la dépendance de ce "A" avec le nombre de dimension ? Est ce que "A" augemente toujours (ou au pire reste constant) avec le nombre de dimension, quel que soit le problème considéré ? Ou faut-il faire du cas par cas ?

Car pour le moment je ne suis pas encore capable de répondre à ma question qui est finalement très simpliste : Est ce qu'il est plus difficile ou non de faire un Monte-Carlo en dimension 10 qu'en dimension 1 ? Ou finalement est ce qu'avec un Monte-Carlo, on s'en fiche de la dimension du problème ...

[gg0]

C'est plus compliqué que ça. Ce n'est que asymptotiquement que l'on peut considérer que A ne dépend pas de N, pour N "tendant vers l'infini". Dans la pratique, comme on ne va pas faire une infinité de calculs, ni même 1000000000000000000000000 calculs, faute de temps, le A est sensible à tout !

Mais il est évident qu'en dimension 10 le calcul sera plus complexe(*) qu'en dimension 1, ne serait-ce que pour la taille des données. Ce qui ne veut pas dire plus difficile (cette expression a de très nombreuses acceptions). par exemple en Matlab, on programme de la même façon (ou presque) en dimension 1 ou en dimension 10, et de la même façon en dimension 10 et en dimension 100. Mais en dimension 100, le calcul prendra plus de temps qu'en dimension 10 ou 1.
Quant à l'analyse de précision, elle dépend tellement de la façon de calculer qu'il est difficile de répondre de façon générale. Mais si on a construit correctement le procédé, on montre (pour N suffisamment grand) que l'incertitude diminue comme 1/sqrt(N), ce qui est généralement lent, mais a l'avantage de ne pas dépendre de la dimension; mais pour une très grande dimension le temps de calcul peut être prohibitif ! Ne rêvons pas, il n'y a pas de méthode miracle, seulement des méthodes intéressantes pour certains problèmes.

Finalement, quel est l'intérêt de ta question finale posée ainsi, avec une réponse évidente ? Probablement es-tu au bout d'une incompréhension de choses lues sans faire suffisamment attention au contexte (**).

Cordialement.

(*) voir le sens de ce mot
(**) Les notions asymptotiques des mathématiciens, les notions de complexité d'algorithmes des informaticiens, ont toutes deux l'inconvénient de ne rien dire des cas pratiques où les tailles de données, les temps d'exécution, les tailles de mémoires, ... sont faibles.

[invite6f25a1fe]

Merci pour tes efforts gg0.

Ce que tu écris ici, c'est généralement ce que je lis partout :
"Mais si on a construit correctement le procédé, on montre (pour N suffisamment grand) que l'incertitude diminue comme 1/sqrt(N), ce qui est généralement lent, mais a l'avantage de ne pas dépendre de la dimension; mais pour une très grande dimension le temps de calcul peut être prohibitif !"

Franchement pour quelqu'un qui n'est pas dans les méthodes proba, c'est une phrase très très étrange : on se demande forcément pourquoi "en grande dimension le calcul est prohibitif" alors qu'on lui a dit une phrase avant que "l'incertitude diminue en 1/sqrt(N), ce qui a l'avantage de ne pas dépendre de la dimension". C'est surement évident pour quelqu'un qui fait ca toute la journée, mais hors contexte et hors cas pratique comme tu dis, c'est très difficile de comprendre. Ton message m'apporte un début de réponse qu'il faut que j'approfondisse.

Merci encore

[invite9dc7b526]

salut,

en fait il faut voir que souvent quand on pense précision on pense au coefficient de variation, et non à l'écart-type. Suppose que tu veuilles estimer une proportion p. Et supposons que tu saches tirer des variables aléatoires de Bernoulli de paramètre p (je prendrai un exemple plus loin). Si X est la moyenne empirique de telles variables, on a EX = p VarX = p(1-p)/n et CX = sqrt(VarX)/EX = 1/sqrt(n)sqrt((1-p)/p). CX est le coefficient de variation. Suppose maintenant que p est très petit. Alors CX ~ 1/sqrt(n)1/sqrt(p).

considères maintenant l'estimation du volume de la sphère à d dimensions : on tire des variables uniformes dans le cube à d dimensions [0,1]^d et on garde la proportion des tirages qui tombent dans la portion de sphere S(0,1) (cette portion représente 1/2^d du volume de la sphère). Tu vois que le volume de cette portion de sphère tend vers 0 quand d tend vers l'infini. Autrement dit, quand d augmente la plupart des tirages tombent en-dehors de la portion de sphère, on est dans le cas de p petit. Alors pour un nombre n de tirages donné, le coefficient de variation de l'estimateur tend vers l'infini avec d.

[gg0]

Scorp,

ce qui ne dépend pas de la dimension, c'est la vitesse de diminution de l'incertitude. Mais si l'incertitude pour N=100 est énorme, une lente vitesse de diminution ne donnera pas un résultat utilisable pour N=10 000 !
Problème connu : Même avec d'excellents freins, si on roule très vite il faut pas mal de temps pour s'arrêter, parfois trop.