Как мне сделать выборку из дискретного (категориального) распределения в пространстве журнала?

12

Предположим, у меня есть дискретное распределение, определенное вектором такое, что категория будет нарисована с вероятностью и так далее. Затем я обнаружил, что некоторые из значений в распределении настолько малы, что не соответствуют представлению чисел с плавающей запятой моего компьютера, поэтому для компенсации я делаю все свои вычисления в лог-пространстве. Теперь у меня есть журнал пространства векторного . $\theta_0, \theta_1, ..., \theta_N$ $0$ $\theta_0$ $log(\theta_0), log(\theta_1), ..., log(\theta_N)$

Можно ли сделать выборку из распределения так, чтобы исходные вероятности (категория рисуется с вероятностью ), но не выходя из лог-пространства? Другими словами, как мне сделать выборку из этого дистрибутива без недостатков? $i$ $\theta_i$

random-generation Джош Хансен
источник

15

С помощью трюка Гамбеля-Макса можно выбрать из категориального распределения данные логарифмических вероятностей, не выходя из логарифмического пространства . Идея состоит в том, что если вам заданы ненормализованные логарифмические вероятности , которые можно преобразовать в правильные вероятности с помощью функции 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)}$

затем для выборки из такого распределения вы можете использовать тот факт, что если являются независимыми выборками, взятыми из стандартного распределения Гумбеля, параметризованного местоположением , $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))$

тогда можно показать (см. ссылки ниже), что

\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}$

и мы можем взять

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

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

как выборка из категориального распределения, параметризованного вероятностями . Этот подход был более подробно описан в записях блога Райаном Адамсом и Лораном Динхом , более того, Крис Дж. Мэддисон, Дэниел Тарлоу и Том Минка выступили с речью ( слайдами ) на конференции Neural Information Processing Systems (2014) и написали статью под названием A * Выборка, которая обобщала эти идеи (см. Также Maddison, 2016; Maddison, Mnih and Teh, 2016; Jang and Poole, 2016), которые ссылаются на Yellott (1977), упоминая его как одного из тех, кто впервые описал это свойство. $p_1,\dots,p_k$

Это довольно легко реализовать, используя выборку с обратным преобразованием , взяв где - отрисовки из равномерного распределения по . Это, конечно, не самые эффективные по времени алгоритмы для выборки из категориального распределения, но это позволяет вам оставаться в лог-пространстве, что может быть преимуществом в некоторых сценариях. $g_i=-\log(-\log u_i)$ $u_i$ $(0,1)$

Maddison, CJ, Tarlow, D. & Minka, T. (2014). A * выборка. [В:] Достижения в нейронных системах обработки информации (стр. 3086-3094).

Йеллотт, JI (1977). Связь между аксиомой выбора Люси, теорией сравнительного суждения Терстоуна и двойным экспоненциальным распределением. Журнал математической психологии, 15 (2), 109-144.

Maddison, CJ, Mnih, A. & Teh, YW (2016). Конкретное распределение: непрерывная релаксация дискретных случайных величин. Препринт arXiv arXiv: 1611.00712.

Jang E., Gu, S. & Poole, B. (2016). Категориальная репараметризация с помощью Gumbel-Softmax. Препринт arXiv arXiv: 1611.01144.

Мэддисон, CJ (2016). Модель пуассоновского процесса для Монте-Карло. Препринт arXiv arXiv: 1602.05986.

Тим
источник

5

Вот один из распространенных способов избежать переполнения / переполнения.

Пусть . $m = \max_i \log(\theta_i)$

Пусть . $\theta_i' = \exp( \log(\theta_i) - m )$

Вы можете из . $\theta' = [\theta_1' , \theta_2',...]$

Сиддхарт Гопал
источник

1

Это работает до тех пор, пока разница между каким-либо одним значением и максимальным не слишком велика - когда это происходит, expможет потерять точность, что приводит к таким распределениям, как [1.0, 3.45e-66, 0.0, 7.54e-121] , Я хотел бы выждать какой-то ответ, который является надежным даже в этом случае. Но пока я голосую за ваш ответ.

Джош Хансен

Как мне сделать выборку из дискретного (категориального) распределения в пространстве журнала?

Ответы: