Generuj jednolity hałas z kulki p-normalnej ( )

Próbuję napisać funkcję, która generuje równomiernie rozłożony hałas pochodzący z kuli p-norm o wymiarach : $n$

| | x | |_{p} \leq r

$\begin{equation} ||x||_p \leq r \end{equation}$

Znalazłem możliwe rozwiązania dla kręgów ( ) ( http://mathworld.wolfram.com/DiskPointPicking.html ), jednak mam problem z rozszerzeniem tego dla różnych wartości . $p = 2$ $p$

Próbowałem to zrobić, po prostu losując próbkę z jednolitego rozkładu i przerysowując, gdy nie spełnia ona określonego ograniczenia. Jednak oprócz tego, że jest to brzydkie rozwiązanie, staje się również niewykonalne obliczeniowo w przypadku dużych wymiarów.

simulation noise

— Taeke de Haan
źródło

Tutaj można znaleźć odpowiedź dla kuli o wymiarach n przy użyciu odległości euklidesowej (p = 2) math.stackexchange.com/questions/87230/ ... Jednak wciąż nie jestem pewien, jak użyć tego dla różnych norm p, czy mogę po prostu zmienić używaną odległość euklidesową w innej relacji dla odległości?

— Taeke de Haan

Istnieje wiele dokumentów, ale większość jest za paywall: link.springer.com/article/10.1007/s00184-011-0360-x lub odwiedź google.com/…

— kjetil b halvorsen

„Jednolity” w odniesieniu do jakiej miary objętości? W końcu, jeśli używasz kulki, dlaczego objętość euklidesowa byłaby tak interesująca?

p

$p$

— whuber

@ whuber Szczerze mówiąc, nie jestem pewien, ponieważ nie jest to wyraźnie określone w zadaniu, ale oczekiwałbym w p-normie, ponieważ wszelkie inne wskaźniki wydają się w tym przypadku arbitralne.

— Taeke de Haan

Problem pochodzi z zadania uczenia maszynowego; „Problemem jest problem klasyfikacji dwóch klas w 204 wymiarach. Mały zestaw szkoleniowy z etykietą ma rozmiar 50 próbek na klasę. Nieoznakowane dane dostarczają 20 000 dodatkowych próbek. Próbki te jednak uległy pewnego rodzaju uszkodzeniu. jedyne dodatkowe informacje, które posiadamy na temat tego uszkodzenia, to to, że jest to addytywny jednolity hałas i że hałas pochodzi ze stałej kuli p-normalnej,

, gdzie zarówno

jak i promień

są nieznane. Muszę uzyskać najniższy poziom błędu dla nieznakowanych danych.

| | x | |_{p} \leq r

$||x||_p \leq r$

p

$p$

r

$r$

— Taeke de Haan

Odpowiedzi:

Pełne rozwiązanie znalazłem w dokumencie sugerowanym przez kjetil b halvorsen ( https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=758215 ). Naprawdę mam problem ze zrozumieniem matematyki, ale ostateczny algorytm jest dość prosty. jeśli mamy wymiarów, promień norma niż: $n$ $r$ $p$

1) generuj niezależnych losowych rzeczywistych skalarów , gdzie jest uogólnionym rozkładem Gaussa (o innej mocy zamiast wykładnika zamiast tego po prostu ) $n$ $\varepsilon_i = \bar{G}(1/p, p)$ $\bar{G}(\mu, \sigma^2)$ $e^{−|x|^p}$ $p=2$

2) konstruować wektor składników , gdzie są niezależnymi losowymi znakami $x$ $s_i * \varepsilon_i$ $s_i$

3) Wygeneruj , gdzie jest zmienną losową równomiernie rozmieszczoną w przedziale [0, 1]. $z = w^{1/n}$ $w$

4) return $y = r z \frac{x}{||x||_p}$

— Taeke de Haan
źródło

Dla kompletności, czy możesz powiedzieć, co jest w twojej odpowiedzi?

G

$G$

— Stéphane Laurent,

Został zaktualizowany

— Taeke de Haan

G jest uogólnionym rozkładem Gaussa (o innej potędze w wykładniku zamiast tylko ). Spowoduje to, że rozkład wektora , złożony z wielu niezależnych uogólnionych zmiennych rozproszonych gaussowskich , które są iloczynem pojedynczych plików pdf, zależy od normy p.

e^{- | x |^{p}}

$e^{-|x|^p}$

p = 2

$p=2$

x

$\mathbf{x}$

x_{i}

$x_i$

fa (x) \propto {mi}^{- | x |_{p}^{p}}

$f(\mathbf{x}) \propto e^{-\vert \mathbf{x} \vert_p^p}$

— Sextus Empiricus

@MartijnWeterings Dzięki bardzo, został zaktualizowany.

— Taeke de Haan

Dzięki. Aby uzyskać informacje, w pakiecie R pgnorm znajduje się próbnik tej dystrybucji .

— Stéphane Laurent,

Korzystanie z jednorodnie rozmieszczonych zmiennych wielowymiarowych

Taeke zapewnia link do artykułu, który w poniższym tekście jest bardziej intuicyjny, wyjaśniając w szczególności przypadki 2-normalne i 1-normowe.

$\Vert x \Vert_2 \leq r$

przykładowy kierunek

Możesz użyć tego wyniku http://mathworld.wolfram.com/HyperspherePointPicking.html

Wielowymiarowa zmienna rozkładowa Gaussa (z macierzą kowariancji tożsamości) zależy tylko od odległości lub sumy kwadratów. $X$

fa (X_{1}, X_{2)}, . . ., X_{n}) = \prod_{1 \leq ja \leq n} \frac{1}{\sqrt{2) π}} {mi}^{\frac{1}{2)} x_{ja}^{2)}} = \frac{1}{\sqrt{2) π}} {mi}^{\frac{1}{2)} \sum_{1 \leq ja \leq n} x_{ja}^{2)}}

$f(X_1,X_2,...,X_n) = \prod_{1\leq i \leq n} \frac{1}{\sqrt{2\pi}}e^{\frac{1}{2}x_i^2} = \frac{1}{\sqrt{2\pi}}e^{\frac{1}{2}\sum_{1 \leq i \leq n} x_i^2}$

Zatem jest równomiernie rozmieszczony na powierzchni n-wymiarowej hipersfery. $\frac{X}{\Vert X \Vert_2}$

odległość próbki

Aby ukończyć, wystarczy próbkować odległość, aby zmienić jednorodny rozkład na kuli na jednorodny rozkład w kuli. (który jest mniej więcej podobny do połączonego przykładu wybierania punktów na dysku)

Jeśli po prostu spróbujesz jako rozkład równomierny, będziesz mieć stosunkowo większą gęstość w pobliżu środka (objętość skaluje się jako więc ułamek punktów kończy się na objętości , która jest bardziej gęsta blisko centrum i nie oznaczałoby równomiernego rozkładu) $r$ $r^n$ $r$ $r^n$

Jeśli zamiast tego użyjesz pierwiastka zmiennej próbkowanej z rozkładu jednolitego, otrzymasz rozkład parzysty. $n$

1-norm $\Vert x \Vert_1 \leq r$

kierunek

W tym przypadku próbkujesz z rozkładu Laplace'a zamiast rozkładu Gaussa i dzielisz przez 1-normę. równomiernie rozmieszczone na n-wymiarowej norma 1 kuli. $X$ $\frac{X}{\vert X \vert_1}$

Nie mam formalnego dowodu, tylko intuicję

^{(ponieważ plik pdf jest niezależny od położenia, można oczekiwać, że każdy nieskończenie mały obszar / objętość o tej samej 1-normie będzie miał takie samo prawdopodobieństwo a gdy zwiniesz go na powierzchnię jednostki, to samo ) $f(x) dV$ $f(x) dA$}

ale testowanie za pomocą symulacji wygląda dobrze.

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)

dystans

Odległość jest podobna jak w przypadku 2-normowym (głośność nadal skaluje się jako ). $r^n$

p-norm $\Vert x \Vert_p \leq r$

W takim przypadku, jeśli chcesz zastosować tę samą zasadę, musisz próbkować z dystrybucji za pomocą ( ). Są to uogólnione rozkłady normalne i prawdopodobnie odnoszą się do rozkładu wspomnianego przez Taeke. $f(x) \propto e^{\vert x \vert^p}$ $G()$

— Sextus Empiricus
źródło

Czy możesz wyjaśnić, w jaki sposób wnioskujesz, że wektory jednostkowe są równomiernie rozmieszczone? BTW, wierzę, że chcesz wziąć

p

$p$

n

$n$

r

$r$

p

$p$

z = w^{1 / n}

$z = w^{1/n}$

w

$w$

y = r z \frac{x}{| | x | |_{p}}

$y = r z \frac{x}{||x||_p}$

Generuj jednolity hałas z kulki p-normalnej ( )

Korzystanie z jednorodnie rozmieszczonych zmiennych wielowymiarowych

∥ x ∥2)≤ r‖x‖2)≤r\Vert x \Vert_2 \leq r

przykładowy kierunek

odległość próbki

1-norm∥ x ∥1≤ r‖x‖1≤r\Vert x \Vert_1 \leq r

kierunek

dystans

p-norm∥x∥p≤r‖x‖p≤r\Vert x \Vert_p \leq r

$\Vert x \Vert_2 \leq r$

1-norm $\Vert x \Vert_1 \leq r$

p-norm $\Vert x \Vert_p \leq r$