biaya pengambilan sampel

Saya menemukan masalah simulasi berikut: diberi satu set dari bilangan real yang diketahui, distribusi pada didefinisikan oleh mana $\{\omega_1,\ldots,\omega_d\}$ $\{-1,1\}^d$

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

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

menunjukkan bagian positif dari

. Sementara saya bisa memikirkan sampler Metropolis-Hastings menargetkan distribusi ini, saya bertanya-tanya apakah ada sampler langsung yang efisien, mengambil keuntungan dari sejumlah besar probabilitas nol untuk mengurangi urutan algoritma dari

(z)_{+}

$(z)_+$

z

$z$

O (2^{d})

$O(2^d)$

O (d)

$O(d)$

simulation algorithms random-generation computational-statistics metropolis-hastings Xi'an
sumber

Berikut adalah sampler rekursif yang cukup jelas yaitu dalam kasus terbaik (dalam hal bobot ), tetapi eksponensial dalam kasus terburuk. $O(d)$ $\omega_i$

Misalkan kita sudah memilih , dan ingin memilih . Kita perlu menghitung $x_1, \dots, x_{i-1}$ $x_{i}$ dan pilihdengan probabilitas

w (x_{1}, ..., x_{saya - 1}, x_{saya}) = \sum_{x_{saya + 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)_+$

x_{i} = 1

$x_i = 1$

Penyebut akan menjadi nol untuk setiap pilihan sampel yang valid

\frac{w (x_{1}, ..., x_{saya - 1}, 1)}{w (x_{1}, ..., x_{saya - 1}, 1) + w (x_{1}, ..., x_{saya - 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)}.$

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

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

Sekarang, tentu saja, pertanyaannya adalah bagaimana cara menghitung . $w(x_1, \dots, x_i)$

Jika kita memiliki , lalu untuk setiap dengan entri terkemuka , dan jadi menjadi: $C := \sum_{j=1}^{i} \omega_j x_j \ge \sum_{j=i+1}^{d} \lvert \omega_j \rvert$ $\omega \cdot x \ge 0$ $x$ $x_{1:i}$ $w$

\begin{aligned} \sum_{x_{saya + 1}} \dots \sum_{x_{d}} ω \cdot x & = ω \cdot (\sum_{x_{saya + 1}} \dots \sum_{x_{d}} x) \\ = \sum_{j = 1}^{saya} ω_{j} \underset{2^{d - saya} x_{j}}{\underset{⏟}{(\sum_{x_{saya + 1}} \dots \sum_{x_{d}} x_{j})}} + \sum_{j = saya + 1}^{d} ω_{j} \underset{0}{\underset{⏟}{(\sum_{x_{saya + 1}} \dots \sum_{x_{d}} x_{j})}} \\ = 2^{d - saya} 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}$

Dalam kasus sebaliknya, $C \le - \sum_{j=i+1}^{d} \lvert \omega_j \rvert$ $\omega \cdot x \le 0$ $w(x_1, \dots, x_i) = 0$

$w(x_1, \dots, x_i) = w(x_1, \dots, x_i, 1) + w(x_1, \dots, x_i, -1)$

$w(1)$ $w(-1)$ $x_1$ $w$ $O(d)$

$\omega_i$ $\omega_1 \ge \omega_2 \ge \dots \ge \omega_d$

Dalam kasus terbaik, $\lvert \omega_1 \rvert > \sum_{j=2}^d \lvert \omega_j \rvert$ $w(1)$ $w(-1)$ $w$ $O(d)$

$\omega_1 = \omega_2 = \dots = \omega_d$

Nah, jalur pertama untuk mengakhiri tentu saja $(1, 1, \dots, 1)$ $(-1, -1, \dots, -1)$ $\lceil d/2 \rceil$ $O(2^{d/2})$ $2^{d/2}$

$\omega_i$ $\omega_i$ $d$

Dougal
sumber

Terima kasih untuk jenis eliminasi Viterbi ini. Ketika Anda menulis "Dalam kasus sebaliknya",

Saya menganggap Anda tidak bermaksud melengkapi kasus pertama

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

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

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

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

Tidak, bukan komplemen: ketika sangat besar Anda tahu pemotongan tidak diterapkan, ketika sangat kecil itu selalu diterapkan, dan di antara Anda harus berulang kali mencari tahu kapan itu diterapkan atau tidak diterapkan.

Dougal

biaya pengambilan sampel

Jawaban: