Génère un bruit uniforme à partir d'une boule de norme p ( )

10

J'essaie d'écrire une fonction qui génère un bruit uniformément distribué qui provient d'une boule de norme p de dimensions:n

||x||pr

J'ai trouvé des solutions possibles pour les cercles ( ) ( http://mathworld.wolfram.com/DiskPointPicking.html ), mais j'ai du mal à étendre cela pour différentes valeurs de .p=2p

J'ai essayé de le faire en tirant simplement un échantillon aléatoire à partir d'une distribution uniforme et en le redessinant lorsqu'il ne répond pas à la contrainte donnée. Cependant, en plus d'être une solution laide, elle devient également impossible à calculer pour des dimensions élevées.

Taeke de Haan
la source
1
La réponse peut être trouvée ici pour une sphère avec n dimensions utilisant la distance euclidienne (p = 2) math.stackexchange.com/questions/87230/… Je ne suis cependant toujours pas sûr de savoir comment l'utiliser pour différentes normes p, puis-je changer simplement la distance euclidienne utilisée dans une relation différente pour la distance?
Taeke de Haan
2
Il y a beaucoup de papiers, mais la plupart sont derrière paywall: link.springer.com/article/10.1007/s00184-011-0360-x ou voir google.com/…
kjetil b halvorsen
3
"Uniforme" par rapport à quel volume métrique? Après tout, si vous utilisez un -ball, pourquoi le volume euclidien serait-il intéressant? p
whuber
@whuber Je ne suis honnêtement pas sûr, car cela n'est pas clairement indiqué dans le devoir, mais je m'attendrais à la norme p car toute autre métrique semble être arbitraire dans ce cas.
Taeke de Haan
1
Le problème vient d'une tâche d'apprentissage automatique; "Le problème est un problème de classification à deux classes dans 204 dimensions. Le petit ensemble d'apprentissage étiqueté a une taille de 50 échantillons par classe. Les données non étiquetées fournissent 20 000 échantillons supplémentaires. Ces échantillons ont cependant subi une corruption quelconque. La seules les informations supplémentaires dont nous disposons concernant cette corruption sont qu'il s'agit d'un bruit uniforme additif et que le bruit provient d'une boule de norme p fixe, , où et le rayon sont inconnus. " J'ai besoin d'obtenir le taux d'erreur le plus bas sur les données sans étiquette. p r||x||prpr
Taeke de Haan

Réponses:

5

J'ai trouvé la solution complète dans un document comme suggéré par kjetil b halvorsen ( https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215 ). Honnêtement, j'ai du mal à comprendre les mathématiques derrière, mais l'algorithme final est assez simple. si on a dimensions, un rayon et une norme que:r pnrp

1) générer scalaires réels aléatoires indépendants , où est la distribution gaussienne généralisée (avec une puissance différente dans l'exposant au lieu de juste )ε i = ˉ G ( 1 / p , p ) ˉ G ( μ , σ 2 ) e - | x | p p = 2nεi=G¯(1/p,p)G¯(μ,σ2)e|x|pp=2

2) construire le vecteur des composants , où sont des signes aléatoires indépendantss iε i s ixsiεisi

3) Générez , où est une variable aléatoire uniformément répartie dans l'intervalle [0, 1]. wz=w1/nw

4) retourney=rzx||x||p

Taeke de Haan
la source
2
Pour être complet, pourriez-vous dire quel est dans votre réponse? G
Stéphane Laurent
Il a été mis à jour
Taeke de Haan
2
G est la distribution gaussienne généralisée (avec une puissance différente dans l'exposant au lieu de juste ). Cela rendra la distribution du vecteur , composée de plusieurs variables distribuées gaussiennes généralisées indépendantes , qui est le produit des pdfs uniques, dépendant de la norme p. p = 2 x x i f ( x ) e - | x | p pe|x|pp=2xxi
f(x)e|x|pp
Sextus Empiricus
@MartijnWeterings Merci beaucoup, il a été mis à jour.
Taeke de Haan
Merci. Pour info, il y a un échantillonneur de cette distribution dans le package R pgnorm .
Stéphane Laurent
3

Utilisation de variables multivariées réparties de manière homogène

Taeke fournit un lien vers un article que le texte ci-dessous rend plus intuitif en expliquant spécifiquement les cas à 2 normes et à 1 norme.

2 normesx2r

direction de l'échantillon

Vous pouvez utiliser ce résultat http://mathworld.wolfram.com/HyperspherePointPicking.html

Une variable distribuée gaussienne multivariée (avec matrice de covariance d'identité) ne dépend que de la distance ou de la somme des carrés.X

f(X1,X2,...,Xn)=1in12πe12xi2=12πe121inxi2

Ainsi, est uniformément distribué à la surface de l'hypersphère à n dimensions.XX2


distance d'échantillon

Pour terminer, vous n'avez qu'à échantillonner la distance, pour changer la distribution homogène sur la sphère en une distribution homogène dans une balle. (qui est plus ou moins similaire à votre exemple lié pour la sélection de points de disque)

Si vous échantillonniez simplement comme une distribution uniforme, alors vous auriez une densité relativement plus élevée près du centre (les échelles de volume comme donc une fraction des points finirait dans un volume , qui est plus dense près du centre et ne signifierait pas une distribution uniforme)rrnrrn

Si, à la place, vous utilisez la racine -ième d'une variable échantillonnée à partir d'une distribution uniforme, vous obtenez une distribution paire.n

1-normex1r

direction

Dans ce cas, vous échantillonnez partir de la distribution de Laplace au lieu de la distribution gaussienne et divisez par la norme 1. Le est uniformément réparti sur la sphère à n dimensions.XX|X|1

Je n'ai aucune preuve formelle, juste une intuition

(puisque le pdf est indépendant de la position, vous vous attendez à ce que toute zone / volume infinitésimal avec la même norme 1 ait la même probabilité et lorsque vous le réduisez à la surface de l'unité, le même )f(x)dVf(x)dA

mais les tests avec des simulations semblent bons.

simulation sélectionnant 20000 valeurs uniformément réparties

library(rmutil)
x <- abs(rlaplace(20000))
y <- abs(rlaplace(20000))
z <- abs(rlaplace(20000))
rn <- abs(x)+abs(y)+abs(z)

xi <- (x/rn)
yi <- (y/rn)
zi <- (z/rn)
plot(sqrt(0.5)*(xi-yi),
     sqrt((0.5-0.5*(xi+yi))^2+zi^2),
     pc=21,bg=rgb(0,0,0,0.02), col=rgb(0,0,0,0),cex=1)

distance

La distance est similaire à celle du cas à 2 normes (le volume est toujours égal à ).rn

norme-pxpr

Dans ce cas, si vous souhaitez suivre le même principe, vous devrez échantillonner à partir de distributions avec (je suppose). Ce sont des distributions normales généralisées et se rapportent probablement à la distribution mentionnée par Taeke.f(x)e|x|pG()

Sextus Empiricus
la source
1
Pourriez-vous expliquer comment vous concluez que les vecteurs unitaires sont uniformément distribués? BTW, je crois que vous voulez prendre la racine e. p
whuber
1
Merci pour votre aide, j'ai trouvé la solution complète ici: ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215 ). Honnêtement, j'ai du mal à comprendre les mathématiques derrière, mais l'algorithme final est assez simple. si nous avons dimensions, un rayon et une norme supérieurs à: 1) générer n scalaires réels aléatoires indépendants E_i = G (1 / p, p) 2) construire le vecteur x des composants s_i * E_i, où E_i sont des signes aléatoires indépendants 3) Générez , où est une variable aléatoire uniformément répartie dans l'intervalle [0, 1]. 4) retournernrpz=w1/nwy=rzx||x||p
Taeke de Haan