Jak próbkować z dyskretnego (kategorycznego) rozkładu w przestrzeni dziennika?

12

Załóżmy, że mam rozkład dyskretny zdefiniowany przez wektor tak, że kategoria zostanie narysowana z prawdopodobieństwem i tak dalej. Następnie odkrywam, że niektóre wartości w rozkładzie są tak małe, że nie odpowiadają one liczbom zmiennoprzecinkowym mojego komputera, więc aby to zrekompensować, wykonuję wszystkie obliczenia w przestrzeni dziennika. Teraz mam dziennik wektorowy log-space . $\theta_0, \theta_1, ..., \theta_N$ $0$ $\theta_0$ $log(\theta_0), log(\theta_1), ..., log(\theta_N)$

Czy możliwe jest próbkowanie z rozkładu w taki sposób, aby się pierwotne prawdopodobieństwa (kategoria jest rysowana z prawdopodobieństwem ), ale bez opuszczania przestrzeni logów? Innymi słowy, jak mogę próbkować z tej dystrybucji bez niedomiarów? $i$ $\theta_i$

random-generation

— Josh Hansen
źródło

15

Możliwe jest próbkowanie z rozkładu kategorycznego przy określonych prawdopodobieństwach logów bez opuszczania przestrzeni logów przy użyciu sztuczki Gumbela-maxa . Chodzi o to, że jeśli otrzymujesz nietypowe prawdopodobieństwa dziennika , które można przełożyć na odpowiednie prawdopodobieństwa za pomocą funkcji softmax $\alpha_1,\dots,\alpha_k$

p_{i} = \frac{\exp (α_{i})}{\sum_{j} \exp (α_{j})}

$p_i = \frac{\exp(\alpha_i)}{\sum_j \exp(\alpha_j)}$

następnie do próbki z takiego rozkładu można użyć faktu, że jeśli są niezależnymi próbkami pobranymi ze standardowego rozkładu Gumbela sparametryzowanego przez lokalizację , $g_1,\dots,g_k \sim \mathcal{G}(0)$ $m$

F (G \leq g) = \exp (- \exp (- g + m))

$F(G \le g) = \exp(-\exp(-g+m))$

wtedy można to wykazać (patrz odnośniki poniżej), że

\begin{aligned} \underset{i}{a r g m a x} {g_{i} + α_{i}} & \sim \frac{\exp (α_{i})}{\sum_{j} \exp (α_{j})} \\ max_{i} {g_{i} + α_{i}} & \sim G (\log \sum_{i} \exp {α_{i}}) \end{aligned}

$\DeclareMathOperator*{\argmax}{arg\,max} \begin{align} \argmax_i \,\{\, g_i + \alpha_i \,\} &\sim \frac{\exp(\alpha_i)}{\sum_j \exp(\alpha_j)} \\ \max_i\,\{\, g_i + \alpha_i \,\} &\sim \mathcal{G}(\; \log\sum_i\exp\{\alpha_i\}\;) \end{align}$

i możemy wziąć

z = \underset{i}{a r g m a x} {g_{i} + α_{i}}

$z = \argmax_i \,\{\, g_i + \alpha_i \,\}$

jako próbka z rozkładu kategorycznego sparametryzowanego prawdopodobieństwem . To podejście zostało bardziej szczegółowo opisane we wpisach na blogu przez Ryana Adamsa i Laurenta Dinha , a ponadto Chris J. Maddison, Daniel Tarlow i Tom Minka wygłosili przemówienie ( slajdy ) na konferencji Neural Information Processing Systems (2014) i napisali artykuł zatytułowany A * Pobieranie próbek, które uogólniły te idee (patrz także Maddison, 2016; Maddison, Mnih and Teh, 2016; Jang i Poole, 2016), którzy odnoszą się do Yellott (1977), wymieniając jego jako jednego z tych, którzy jako pierwsi opisali tę właściwość. $p_1,\dots,p_k$

Całkiem łatwo go zaimplementować przy użyciu odwrotnego próbkowania transformacji , biorąc gdzie czerpie z rozkładu równomiernego na . Z pewnością nie jest to najbardziej efektywny czasowo algorytm do próbkowania z rozkładu kategorycznego, ale pozwala ci pozostać w przestrzeni logów, co może być zaletą w niektórych scenariuszach. $g_i=-\log(-\log u_i)$ $u_i$ $(0,1)$

Maddison, CJ, Tarlow, D., i Minka, T. (2014). A * pobieranie próbek. [W:] Postępy w systemach przetwarzania informacji neuronowych (str. 3086-3094).

Yellott, JI (1977). Zależność między aksjomatem wyboru Luce, teorią sądu porównawczego Thurstone'a i podwójnym rozkładem wykładniczym. Journal of Mathematical Psychology, 15 (2), 109-144.

Maddison, CJ, Mnih, A., i Teh, YW (2016). Konkretny rozkład: ciągła relaksacja dyskretnych zmiennych losowych. nadruk arXiv arXiv: 1611.00712.

Jang, E., Gu, S. i Poole, B. (2016). Kategoryczna ponowna parametryzacja za pomocą Gumbel-Softmax. nadruk arXiv arXiv: 1611.01144.

Maddison, CJ (2016). Model procesu Poissona dla Monte Carlo. nadruk arXiv arXiv: 1602.05986.

— Tim
źródło

5

Oto jeden z powszechnych sposobów uniknięcia niedopełnienia / przepełnienia.

Niech . $m = \max_i \log(\theta_i)$

Niech . $\theta_i' = \exp( \log(\theta_i) - m )$

Możesz próbkować z . $\theta' = [\theta_1' , \theta_2',...]$

— Siddharth Gopal
źródło

1

Działa to tak długo, jak różnica między dowolną wartością a wartością maksymalną nie jest zbyt duża --- kiedy tak się dzieje, expmoże stracić precyzję, co prowadzi do dystrybucji takich jak [1.0, 3.45e-66, 0.0, 7.54e-121] . Chciałbym znaleźć odpowiedź, która jest solidna nawet w takim przypadku. Ale na razie oceniam twoją odpowiedź.

— Josh Hansen