L'échantillonnage d'hypercube latin est-il efficace dans plusieurs dimensions?

8

J'utilise actuellement un Latin Hypercube Sampling (LHS) pour générer des nombres aléatoires uniformes bien espacés pour les procédures de Monte Carlo. Bien que la réduction de variance que j'obtiens du LHS soit excellente pour 1 dimension, elle ne semble pas être efficace dans 2 dimensions ou plus. Voyant comment le LHS est une technique bien connue de réduction de la variance, je me demande si je peux mal interpréter l'algorithme ou le mal utiliser d'une manière ou d'une autre.

En particulier, l'algorithme LHS que j'utilise pour générer variables aléatoires uniformes espacées en dimensions est:ND

  • Pour chaque dimension , générez un ensemble de nombres aléatoires uniformément distribués tels que , ...DN{uD1,uD2...uDN}uD1[0,1N+1]uD2[1N+1,2N+1]uDN[NN+1,1]

  • Pour chaque dimension , réorganisez au hasard les éléments de chaque ensemble. Le premier produit par LHS est le vecteur dimensionnel contenant le premier élément de chaque ensemble réorganisé, le second produit par LHS est le vecteur dimensionnel contenant le second élément de chaque ensemble réorganisé, et ainsi de suite ...D2U(0,1)DDU(0,1)DD

J'ai inclus quelques graphiques ci-dessous pour illustrer la réduction de variance que j'obtiens en et pour une procédure de Monte Carlo. Dans ce cas, le problème consiste à estimer la valeur attendue d'une fonction de coût où , et est une variable aléatoire de dimension répartie entre . En particulier, les graphiques montrent la moyenne et l'écart type de 100 estimations moyennes d'échantillon de pour des tailles d'échantillon de 1 000 à 10 000.D=1D=2E[c(x)]c(x)=ϕ(x)xD[5,5]E[c(x)]

LHS pour $ D = 1 $

LHS pour $ D = 2 $

J'obtiens le même type de résultats de réduction de variance, que j'utilise ma propre implémentation ou la lhsdesignfonction dans MATLAB. De plus, la réduction de variance ne change pas si je permute tous les ensembles de nombres aléatoires au lieu de seulement ceux correspondant à .D2

Les résultats sont logiques puisque l'échantillonnage stratifié en signifie que nous devrions échantillonner à partir de carrés au lieu de carrés qui sont garantis d'être bien répartis.D=2N2N

Berk U.
la source

Réponses:

3

J'ai divisé les problèmes décrits dans votre message en trois questions ci-dessous. Une bonne référence pour les résultats sur l'échantillonnage de l'hypercube latin et d'autres techniques de réduction de la variance est ce chapitre de livre . En outre, ce chapitre de livre fournit des informations sur certaines des «bases» de la réduction de la variance.

Q0. Qu'est-ce que la réduction de la variance? Avant d'entrer dans les détails, il est utile de rappeler ce que signifie réellement «réduction de la variance». Comme expliqué dans le chapitre du livre «Notions de base», la variance d'erreur associée à une procédure Monte Carlo est généralement de la forme sous échantillonnage IID. Pour réduire la variance d'erreur, nous pouvons soit augmenter la taille de l'échantillon soit trouver un moyen de réduire . La réduction de la variance concerne les moyens de réduire , de sorte que ces méthodes peuvent ne pas avoir d'effet sur la façon dont la variance d'erreur change lorsque varie.σ2/nnσσn

Q1. L'échantillonnage Latin Hypercube a-t-il été correctement mis en œuvre? Votre description écrite me semble correcte et correspond à la description du chapitre du livre. Mon seul commentaire est que les plages des variables ne semblent pas remplir tout l'intervalle unitaire; il semble que vous ayez réellement besoin de , mais j'espère que cette erreur ne s'est pas glissée dans votre implémentation. Quoi qu'il en soit, le fait que les deux implémentations aient donné des résultats similaires suggère que votre implémentation est probablement correcte.uDiuDi[i1N,iN]

Q2. Vos résultats correspondent-ils à ce que vous attendez du LHS? La proposition 10.4 du chapitre livre indique que la variance LHS ne peut jamais être (bien) pire que la variance obtenue à partir de l'échantillonnage IID. Souvent, la variance LHS est bien inférieure à la variance IID. Plus précisément, la proposition 10.1 déclare que, pour l'estimation LHS , nous avons où est le 'résiduel de l'additivité' de la fonction ie moins sa meilleure approximation additive (voir p.10 du chapitre du livre pour plus de détails, est additif si on peut écrireμ^LHS=1ni=1nf(Xi)

Var(μ^LHS)=n1e(x)2dx+o(n1)
e(x)ffff(x)=μ+j=1Dfj(xj) ).

Pour , chaque fonction est additive donc et de la proposition 10.1. En fait, pour LHS équivaut à une stratification basée sur la grille (section 10.1 dans le chapitre du livre), la variance est en fait (équation 10.2 dans le chapitre du livre; suppose que est continuellement différenciable). Cela ne semble pas incompatible avec votre premier graphique. Le point principal est que est un cas très spécial!D=1e=0Var(μ^LHS)=o(n1)D=1O(n3)fD=1

Pour , il est probable que , vous pouvez donc vous attendre à une variance d'ordre . Encore une fois, ce n'est pas incompatible avec votre deuxième graphique. La réduction réelle de la variance obtenue (par rapport à l'échantillonnage IID) dépendra de la proximité de la fonction choisie avec l'addition.D=2e0O(n1)

En résumé, le LHS peut être efficace dans des dimensions faibles à modérées et surtout pour des fonctions bien approximées par des fonctions additives.

S. Catterall réintègre Monica
la source
2

http://statweb.stanford.edu/~owen/mc/Ch-var-adv.pdf

Cet article discute de la réduction de la variance de l'échantillonnage des hypercubes latins dans plusieurs dimensions. LHS n'applique pas l'uniformité lors de l'échantillonnage dans plusieurs dimensions, car il échantillonne simplement dans chaque dimension indépendamment, puis combine les dimensions de manière aléatoire. L'échantillonnage stratifié des bacs N 2, comme vous le mentionnez, est également appelé échantillonnage orthogonal, comme indiqué sur la page Wikipédia: https://en.wikipedia.org/wiki/Latin_hypercube_sampling et renforce davantage l'uniformité multidimensionnelle en échantillonnant à partir des bacs du toutes les dimensions combinées à la place.

Avec quelques ajustements à ce style d'échantillonnage, la variance d'erreur peut être montrée à O (N -1-2 / d ) (dans la référence ci-dessus). Bien que cela offre des gains importants pour les petites dimensions, dans les plus grandes dimensions, il commence à se dégrader pour revenir aux performances du Monte Carlo ordinaire.

Bscan
la source
1

Je veux commenter "l'additivité". LHS s'assure par exemple que X1 et X2 sont bien distribués (généralement en (0,1)), donc si un plan ne dépend que d'une variable, vous obtiendrez un histogramme "parfait" et une forte réduction de variance. Pour l'intégration de f = 100 * X1 + X2, vous obtiendrez également de bons résultats, mais pas pour X1-X2! Cette différence a une distribution aléatoire presque iid, pas de caractéristiques LHS. En électronique, les conceptions exploitent souvent le fait que les influences de 2 paramètres s'annuleront la plupart du temps (paire différentielle, miroir de courant, circuits de réplique, etc.), mais l'effet du décalage X1-X2 est toujours présent et souvent dominant. Ainsi, l'analyse LHS MC ne se comporte pas mieux que rnd MC dans de nombreuses conceptions électriques.

user32038
la source
Je ne sais pas ce que cela signifie pour d'avoir une "distribution aléatoire presque iid, pas de caractéristiques LHS". Dans ce cas, est toujours additif, vous pouvez donc vous attendre à une bonne réduction de la variance en utilisant LHS, tout comme avec la fonction additive . Vous pouvez le vérifier par simulation. f=X1X2ff=100X1+X2
S.Catterall réintègre Monica