koszt próbkowania w wysokości

Natknąłem się na następujący problem z symulacją: biorąc pod uwagę zestaw $\{\omega_1,\ldots,\omega_d\}$ znanych liczb rzeczywistych, rozkład na $\{-1,1\}^d$ jest zdefiniowany przez

P (X = (x_{1}, \dots, x_{d})) \propto (x_{1} ω_{1} + \dots + x_{d} ω_{d})_{+}

$\mathbb{P}(X=(x_1,\ldots,x_d))\propto (x_1\omega_1+\ldots+x_d\omega_d)_+$ gdzie

(z)_{+}

$(z)_+$ oznacza pozytywną część

z

$z$ . Chociaż mogę wymyślić próbnik Metropolis-Hastings ukierunkowany na ten rozkład, zastanawiam się, czy istnieje skuteczny próbnik bezpośredni, wykorzystujący dużą liczbę zerowych prawdopodobieństw w celu zmniejszenia kolejności algorytmu od

O (2^{d})

$O(2^d)$ do

O (d)

$O(d)$ .

— Xi'an
źródło

Oto dość oczywisty rekurencyjny sampler $O(d)$ w najlepszym przypadku (pod względem ciężaru $\omega_i$ ), ale w najgorszym przypadku ma charakter wykładniczy.

Załóżmy, że już wybraliśmy $x_1, \dots, x_{i-1}$ i chcesz wybrać $x_{i}$ . Musimy obliczyć

w (x_{1}, \dots, x_{i - 1}, x_{i}) = \sum_{x_{i + 1} \in {- 1, 1}} \dots \sum_{x_{d} \in {- 1, 1}} {(\sum_{j = 1}^{d} ω_{j} x_{j})}_{+}

$w(x_1, \dots, x_{i-1}, x_i) = \sum_{x_{i+1} \in \{-1, 1\}} \cdots \sum_{x_{d} \in \{-1, 1\}} \left( \sum_{j=1}^d \omega_j x_j \right)_+$ i wybierz

x_{i} = 1

$x_i = 1$ z prawdopodobieństwem

\frac{w (x_{1}, \dots, x_{i - 1}, 1)}{w (x_{1}, \dots, x_{i - 1}, 1) + w (x_{1}, \dots, x_{i - 1}, - 1)} .

$\frac{w(x_1, \dots, x_{i-1}, 1)}{w(x_1, \dots, x_{i-1}, 1) + w(x_1, \dots, x_{i-1}, -1)}.$ Mianownik będzie niezerowy dla każdego ważnego wyboru próbek

x_{1}, \dots, x_{i - 1}

$x_1, \dots, x_{i-1}$ .

Teraz oczywiście chodzi o to, jak obliczyć $w(x_1, \dots, x_i)$ .

Jeśli mamy to $C := \sum_{j=1}^{i} \omega_j x_j \ge \sum_{j=i+1}^{d} \lvert \omega_j \rvert$ , następnie $\omega \cdot x \ge 0$ dla każdego $x$ z wiodącymi wpisami $x_{1:i}$ , a więc $w$ staje się:

\begin{aligned} \sum_{x_{i + 1}} \dots \sum_{x_{d}} ω \cdot x & = ω \cdot (\sum_{x_{i + 1}} \dots \sum_{x_{d}} x) \\ = \sum_{j = 1}^{i} ω_{j} \underset{2^{d - i} x_{j}}{\underset{⏟}{(\sum_{x_{i + 1}} \dots \sum_{x_{d}} x_{j})}} + \sum_{j = i + 1}^{d} ω_{j} \underset{0}{\underset{⏟}{(\sum_{x_{i + 1}} \dots \sum_{x_{d}} x_{j})}} \\ = 2^{d - i} C . \end{aligned}

$\begin{align} \sum_{x_{i+1}} \cdots \sum_{x_d} \omega \cdot x &= \omega \cdot \left( \sum_{x_{i+1}} \cdots \sum_{x_d} x \right) \\&= \sum_{j=1}^i \omega_j \underbrace{\left( \sum_{x_{i+1}} \cdots \sum_{x_d} x_j \right)}_{2^{d-i} x_j} + \sum_{j=i+1}^d \omega_j \underbrace{\left( \sum_{x_{i+1}} \cdots \sum_{x_d} x_j \right)}_{0} \\&= 2^{d-i} C .\end{align}$

W przeciwnym wypadku $C \le - \sum_{j=i+1}^{d} \lvert \omega_j \rvert$ mamy to $\omega \cdot x \le 0$ a więc $w(x_1, \dots, x_i) = 0$ .

W przeciwnym razie musimy powtórzyć, używając $w(x_1, \dots, x_i) = w(x_1, \dots, x_i, 1) + w(x_1, \dots, x_i, -1)$ .

Załóżmy, że pamięć nie stanowi problemu i że możemy buforować wszystkie podliczenia $w(1)$ , $w(-1)$ w drzewie - do tego stopnia, że trafiliśmy w jeden z „ładnych” przypadków, po których wszelkie połączenia wymagają stałego czasu. (Będziemy musieli obliczyć to całe drzewo, aby wybrać $x_1$ .) Potem, kiedy to drzewo $w$ obliczenia są zbudowane, sampler zajmie tylko $O(d)$ czas. Pytanie brzmi, ile czasu zajmuje zbudowanie drzewa, lub równoważnie, jak duże jest ono.

Oczywiście trafimy w „ładne” przypadki, jeśli $\omega_i$ są posortowane, $\omega_1 \ge \omega_2 \ge \dots \ge \omega_d$ .

W najlepszym przypadku, $\lvert \omega_1 \rvert > \sum_{j=2}^d \lvert \omega_j \rvert$ . Następnie natychmiast trafiliśmy w „fajną” skrzynkę $w(1)$ lub $w(-1)$ , więc $w$ budowa drzewa zajmuje cały czas, a cały sampler zajmuje $O(d)$ czas.

W najgorszym (posortowanym) przypadku $\omega_1 = \omega_2 = \dots = \omega_d$ . Zatem pytanie brzmi: jak duże jest całe drzewo?

Cóż, pierwsze ścieżki do zakończenia są oczywiście $(1, 1, \dots, 1)$ i $(-1, -1, \dots, -1)$ długości $\lceil d/2 \rceil$ . Drzewo jest zatem kompletne do tej głębokości, a zatem zawiera co najmniej $O(2^{d/2})$ węzły (Ma więcej; prawdopodobnie można go znaleźć za pomocą argumentu takiego jak te używane w problemach z ruiną hazardzisty, ale nie mogłem go znaleźć w ciągu dwóch minut Googlinga i nie obchodzi mnie to szczególnie - $2^{d/2}$ jest wystarczająco zły ....)

Jeśli twoje ustawienie ma tylko kilka bardzo dużych $\omega_i$ , jest to prawdopodobnie dość praktyczne podejście. Jeśli… $\omega_i$ są podobnej wielkości, prawdopodobnie nadal są wykładnicze i zbyt drogie dla dużych $d$ .

— Dougal
źródło

Dzięki za ten typ eliminacji Viterbi. Kiedy piszesz „W przeciwnym przypadku”,

C_{i} \leq - \sum_{j = i + 1}^{d} | ω_{j} |

$C_i\le -\sum_{j=i+1}^{d} \lvert \omega_j \rvert$ Rozumiem, że nie masz na myśli dopełnienia pierwszego przypadku

C_{i} \geq \sum_{j = i + 1}^{d} | ω_{j} |

$C_i\ge \sum_{j=i+1}^{d} \lvert \omega_j \rvert$

— Xi'an

Nie, nie uzupełnienie: gdy jest bardzo duże, wiesz, że obcięcie nie jest stosowane, gdy jest bardzo małe, zawsze jest stosowane, a pomiędzy nimi musisz się powtórzyć, aby dowiedzieć się, kiedy jest ono stosowane, czy nie.

— Dougal,