Latin Hypercube Sampling Asymptotics

11

J'essaie de construire une preuve d'un problème sur lequel je travaille et l'une des hypothèses que je fais est que l'ensemble des points à partir desquels je suis échantillonné est dense sur tout l'espace. En pratique, j'utilise l'échantillonnage d'hypercube latin pour obtenir mes points sur tout l'espace d'échantillonnage. Ce que je voudrais savoir, c'est si les échantillons d'hypercube latins sont denses sur tout l'espace si vous laissez votre taille d'échantillon tendre à ? Si c'est le cas, une citation pour ce fait serait grandement appréciée.

kjetil b halvorsen
la source
4
Oui, en supposant une distribution continue, car pour tout vous pouvez définir le nombre de divisions de sorte que tous les intervalles par variable aient une largeur . Ainsi, au moins un hyperintervalle (c'est-à-dire le volume d'échantillon) est strictement contenu par un hypercube largeur autour de n'importe quel point que vous choisissez. (Commentaire, pas réponse, car tout ce que je sais sur LHS vient de Wikipedia il y a dix minutes ...)ϵ>0<ϵ/2ϵ
Creosote
C'est vrai, mais je ne pense pas que cela puisse facilement être utilisé pour montrer la densité de grands échantillons Latin Hypercube. La raison en est que les points échantillonnés dans LHS ne sont pas indépendants: l'existence d'un point d'échantillonnage à l'intérieur d'un hyperintervalle spécifique empêche tout autre point d'échantillonnage d'apparaître dans la même ligne / colonne (ou quel que soit le terme multidimensionnel pour cela) .
S.Catterall réintègre Monica
@Creosote pensez-vous pouvoir formaliser davantage votre réponse?
@RustyStatistician, veuillez développer votre message d'ouverture pour expliquer, de manière formelle, comme l'exige votre preuve, ce que vous entendez par "l'ensemble des points à partir desquels je suis échantillonné est dense sur tout l'espace". Merci.
Créosote
Si je prends un premier échantillon d'hypercube latin où est si grand, nous le considérons comme inifinty, cet échantillon est-il dense? n

Réponses:

6

Réponse courte: Oui, de manière probabiliste. Il est possible de montrer que, pour toute distance , tout sous- ensemble fini de l'espace d'échantillonnage et toute «tolérance» prescrite , pour des tailles d'échantillon convenablement grandes, nous pouvons être sûr que la probabilité qu'il y ait un point d'échantillon à une distance de est pour tout .{ x 1 , , x m } δ > 0 ϵ x i > 1 - δ i = 1 , , mϵ>0{x1,,xm}δ>0ϵxi>1δi=1,,m

Réponse longue: Je n'ai connaissance d'aucune citation directement pertinente (mais voir ci-dessous). La plupart de la littérature sur l'échantillonnage des hypercubes latins (LHS) concerne ses propriétés de réduction de la variance. L'autre problème est, qu'est-ce que cela signifie de dire que la taille de l'échantillon a tendance à ? Pour un échantillonnage aléatoire IID simple, un échantillon de taille peut être obtenu à partir d'un échantillon de taille en ajoutant un autre échantillon indépendant. Pour le LHS, je ne pense pas que vous puissiez le faire car le nombre d'échantillons est spécifié à l'avance dans le cadre de la procédure. Il semble donc que vous devez prendre une succession d' indépendants échantillons de LHS de taille .n n - 1 1 , 2 , 3 , . . .nn11,2,3,...

Il doit également y avoir un moyen d'interpréter «dense» dans la limite, car la taille de l'échantillon a tendance à . La densité ne semble pas tenir de manière déterministe pour le LHS, par exemple en deux dimensions, vous pouvez choisir une séquence d'échantillons LHS de taille sorte qu'ils collent tous à la diagonale de . Une sorte de définition probabiliste semble donc nécessaire. Soit, pour tout , un échantillon de taille généré selon un mécanisme stochastique. Supposons que, pour différents , ces échantillons soient indépendants. Ensuite, pour définir la densité asymptotique, nous pourrions exiger que, pour chaque , et pour chaque1,2,3,...[0,1)2nXn=(Xn1,Xn2,...,Xnn)nnϵ>0x dans l'espace échantillon (supposé être ), nous avons ( comme ).[0,1)dP(min1knXnkxϵ)0n

Si l'échantillon est obtenu en prenant échantillons indépendants de la distribution ('échantillonnage aléatoire IID') alors où est le volume de la boule dimensionnelle de rayon . Il est donc certain que l'échantillonnage aléatoire IID est asymptotiquement dense.XnnU([0,1)d)

P(min1knXnkxϵ)=k=1nP(Xnkxϵ)(1vϵ2d)n0
vϵdϵ

Considérons maintenant le cas où les échantillons sont obtenus par LHS. Le théorème 10.1 dans ces notes stipule que les membres de l'échantillon sont tous distribués comme . Cependant, les permutations utilisées dans la définition de LHS (bien qu'indépendantes pour différentes dimensions) induisent une certaine dépendance entre les membres de l'échantillon ( ), il est donc moins évident que la propriété de densité asymptotique est vraie.XnXnU([0,1)d)Xnk,kn

Fixez et . Définissez . Nous voulons montrer que . Pour ce faire, nous pouvons utiliser la proposition 10.3 dans ces notes , qui est une sorte de théorème central limite pour l'échantillonnage en hypercube latin. Définissez par si est dans la boule de rayon autour de , sinon. Alors la proposition 10.3 nous dit que où etϵ>0x[0,1)dPn=P(min1knXnkxϵ)Pn0f:[0,1]dRf(z)=1zϵxf(z)=0Yn:=n(μ^LHSμ)dN(0,Σ)μ=[0,1]df(z)dzμ^LHS=1ni=1nf(Xni) .

Prenez . Finalement, pour assez grand , nous aurons . Donc, finalement, nous aurons . Par conséquent , où est le cdf normal standard. Puisque était arbitraire, il s'ensuit que comme requis.L>0nnμ<LPn=P(Yn=nμ)P(Yn<L)lim supPnlim supP(Yn<L)=Φ(LΣ)ΦLPn0

Cela prouve la densité asymptotique (telle que définie ci-dessus) à la fois pour l'échantillonnage aléatoire iid et le LHS. De manière informelle, cela signifie que compte tenu de tout et de tout dans l'espace d'échantillonnage, la probabilité que l'échantillon atteigne de peut être rendue aussi proche de 1 que vous le souhaitez en choisissant la taille de l'échantillon suffisamment grande. Il est facile d'étendre le concept de densité asymptotique afin de l'appliquer à des sous-ensembles finis de l'espace d'échantillonnage - en appliquant ce que nous savons déjà à chaque point du sous-ensemble fini. Plus formellement, cela signifie que nous pouvons montrer: pour tout et tout sous-ensemble fini de l'espace échantillon,ϵxϵxϵ>0{x1,...,xm}min1jmP(min1knXnkxj<ϵ)1 (comme ).n

S. Catterall réintègre Monica
la source
J'ai deux questions: 1) Si vous avez juste un échantillon de taille où est grand, cela change-t-il l'argument? Et 2) les échantillons d'hypercubes latins peuvent être sur n'importe quelle plage de valeurs (pas nécessairement seulement (0,1)), est-ce que cela change également la réponse? nn
De plus, seriez-vous prêt à expliquer pourquoi pour suffisamment grand , nous aurons ? Je suppose que cela signifie que pour un grand , va à zéro, car dans la distribution, c'est un ? nnμnμ^LHSN(0,Σ)
@RustyStatistician Tout est défini en termes d'échantillons finis, c'est-à-dire mais grand. J'ai ajouté quelques explications supplémentaires à la fin pour expliquer ce qui se passe. D'autres plages de valeurs peuvent facilement être prises en compte ((0,1) n'est pas spécial), tant que le volume de l'espace d'échantillonnage est fini. n<
S.Catterall réintègre Monica
Pouvez-vous développer votre réponse courte?
@RustyStatistician La réponse courte est un résumé informel de ma réponse longue qui, je pense que vous serez d'accord, est déjà assez élaborée! Ainsi, comme suggéré ci-dessus, il serait bon que vous puissiez réécrire votre question en termes plus formels afin que je sache si ma tentative de réponse est sur la bonne voie (en termes de réponse à votre question) ou non.
S.Catterall réintègre Monica
3

Je ne sais pas si c'est tout à fait ce que vous voulez, mais voilà.

Vous échantillonnez LHS points de , disons. Nous dirons de manière très informelle que, pour tout , le nombre attendu de (hyper) cuboïdes vides de taille dans chaque dimension va à zéro comme .n[0,1)dϵ>0ϵn

Soit sorte que si nous divisons uniformément en minuscules cuboïdes - microcuboïdes , disons - de largeur alors chaque largeur- cuboid contient au moins un microcuboïde. Donc, si nous pouvons montrer que le nombre attendu de microcuboïdes non échantillonnés est nul, dans la limite , alors nous avons terminé. (Notez que nos microcuboïdes sont disposés sur une grille régulière, mais les -cuboïdes peuvent être dans n'importe quelle position.)m=2/ϵ[0,1)dmd1/mϵnϵ

Le risque de manquer complètement un microcuboïde donné avec le premier point d'échantillonnage est de , indépendant de , car le premier ensemble de coordonnées d'échantillon (premier point d'échantillonnage) peut être choisi librement. Étant donné que les premiers points d'échantillonnage ont tous raté ce microcuboïde, les points d'échantillonnage suivants auront plus de mal à manquer (en moyenne), de sorte que la probabilité que tous les points manquent est inférieur à .1mdndn(1md)n

Il y a microcuboïdes dans , donc le nombre attendu qui est manqué est limité au-dessus par - parce que les attentes s'ajoutent - qui est zéro dans la limite comme .md[0,1)dmd(1md)nn


Mises à jour ...

(1) Voici une image montrant comment, pour un donné , vous pouvez choisir assez grand pour qu'une grille de "microcuboïdes" (carrés dans cette illustration en 2 dimensions) soit garantie d'avoir au moins un microcuboïde à l'intérieur toute région de taille . J'ai montré deux régions "choisies au hasard" et j'ai coloré en violet les deux microcuboïdes qu'elles contiennent.ϵmm×m ϵ×ϵϵ×ϵ

entrez la description de l'image ici

(2) Considérons tout microcuboïde particulier. Il a un volume , une fraction de tout l'espace. Le premier échantillon LHS - qui est le seul choisi entièrement librement - le manquera donc avec une probabilité de . Le seul fait important est qu'il s'agit d'une valeur fixe (nous laisserons , mais gardons constant) qui est inférieure à .(1/m)dmd1mdnm1

(3) Pensez maintenant au nombre de points d'échantillonnage . J'ai illustré sur la photo. LHS fonctionne dans un maillage fin de ces "nanocuboïdes" de taille super minuscules (si vous voulez), pas le plus grand "microcuboïdes" de taille, mais en réalité ce n'est pas important dans la preuve. La preuve n'a besoin que de l'énoncé légèrement agitant la main selon lequel il devient de plus en plus difficile, en moyenne, de continuer à manquer un microcuboïde donné lorsque vous jetez plus de points. Il s'agissait donc d'une probabilité de pour le premier point LHS manquant, mais inférieure à pour tous les manquants: c'est zéro dans la limite commen>mn=6mn1×n1m1×m11md(1md)n nn .

(4) Tous ces epsilons sont parfaits pour une preuve mais ne sont pas bons pour votre intuition. Voici donc quelques images illustrant et points d'échantillonnage, avec la plus grande zone rectangulaire vide mise en évidence. (La grille est la grille d'échantillonnage du LHS - les "nanocuboïdes" mentionnés plus haut.) Il devrait être "évident" (dans un certain sens intuitif vague) que la plus grande zone vide se rétrécira à une taille arbitrairement petite comme le nombre de points d'échantillonnage .n=10n=50n

entrez la description de l'image ici

Créosote
la source
Cet argument est-il valable pour un intervalle général? Au lieu de ? [0,1)
Oui, pour toutes dimensions finies. Il devrait être plus clair maintenant que j'ai corrigé la preuve.
Creosote
est-il possible de donner une image 1-d voire 2-d de cette preuve? J'y suis plutôt perdu.
Terminé. Heureux de répondre à d'autres questions si besoin est.
Creosote
Super merci! Cela aide certainement maintenant avec l'intuition.