Mengapa masalah kekacauan tidak dapat dilakukan untuk ukuran sampel besar?

Misalkan kita memiliki seperangkat poin . Setiap titik dihasilkan menggunakan distribusi Untuk mendapatkan posterior untuk kita menulis Menurut kertas Minka pada Expectation Dakwah kita perlu perhitungan untuk mendapatkan posterior dan, jadi, masalah menjadi sulit dipecahkan untuk sampel besar ukuran . Namun, saya tidak tahu mengapa kita perlu perhitungan seperti ini dalam kasus ini, karena untuk tunggal $\mathbf{y} = \{y_1, y_2, \ldots, y_N \}$ $y_i$

p (y i | x) = 1 2 N (x, 1) + 1 2 N (0, 10) .

$p(y_i| x) = \frac12 \mathcal{N}(x, 1) + \frac12 \mathcal{N}(0, 10).$

x $x$

p (x | y) \propto p (y | x) p (x) = p (x) \prod i = 1 N p (y i | x) .

$p(x| \mathbf{y}) \propto p(\mathbf{y}| x) p(x) = p(x) \prod_{i = 1}^N p(y_i | x).$

2N $2^N$

p(x|y) $p(x| \mathbf{y})$

N $N$

yi $y_i$ kemungkinan memiliki bentuk

p (y i | x) = 1 2 2 π - - \sqrt (exp {- 1 2 (y i - x) 2} + 1 10 - - \sqrt exp {- 1 20 y 2 i}) .

$p(y_i| x) = \frac{1}{2 \sqrt{2 \pi}} \left( \exp \left\{-\frac12 (y_i - x)^2\right\} + \frac{1}{\sqrt{10}} \exp \left\{-\frac1{20} y_i^2\right\} \right).$

Dengan menggunakan rumus ini kita memperoleh posterior dengan perkalian sederhana $p(y_i| x)$ , jadi kita hanya perlu operasi $N$ , dan, sehingga kita dapat menyelesaikan masalah ini untuk ukuran sampel yang besar dengan tepat.

Saya membuat eksperimen numerik untuk membandingkan apakah saya benar-benar mendapatkan posterior yang sama jika saya menghitung setiap istilah secara terpisah dan jika saya menggunakan produk kepadatan untuk setiap . Posisinya sama. Lihat di mana saya salah? Adakah yang bisa menjelaskan kepada saya mengapa kita perlu operasi untuk menghitung posterior untuk diberikan dan sampel ? $y_i$ masukkan deskripsi gambar di sini $2^N$ $x$ $\mathbf{y}$

bayesian mixture posterior Alexey Zaytsev
sumber

Satu operasi per istilah dan istilah , jadi kita membutuhkan operasi . Juga, saya membaca makalah Minka dan bab Bishop tentang perkiraan inferensi lagi. Keduanya menyarankan bahwa kami ingin memperkirakan dan mendapatkan posterior untuk .

N $N$

O(N) $O(N)$

x $x$

Alexey Zaytsev

Apakah saya mengerti dengan benar bahwa Anda univariat? Jika demikian, Anda dapat menyelesaikan ini di yang dianggap dapat

yi $y_i$

O(nlog(n)) $O(n\log(n))$

n $n$

ditelusuri

@ Alexey Setelah membaca kembali paragraf ini, saya pikir penulis tidak menyebutkan operasi. Dia hanya menunjukkan bahwa "keadaan kepercayaan untuk adalah campuran Gaussians" .

2N $2^N$ $x$ $2^N$

@Prastrastator menurut kertas kami ingin menggunakan propagasi kepercayaan, tetapi tidak dapat digunakan karena kami harus melanjutkan campuran gaussians. Lalu pertanyaannya adalah mengapa kita ingin menggunakan BP? Pertanyaan lain muncul jika kita membaca bab 10.7.1 di PRML Bishop atau menonton videolecture oleh Minka . Setelah itu jawabannya tidak jelas.

2N $2^N$

Alexey Zaytsev

@ Alexey Saya pikir logika di balik ini berbeda. Penulis menjelaskan apa yang terjadi jika Anda menggunakan propagasi kepercayaan, untuk menekankan beberapa kesulitan dengan itu ketika besar, dan kemudian mempromosikan "propagasi harapan" nya. Dia menyebutkan bahwa penyebaran kepercayaan membutuhkan penggunaan campuran Gaussians untuk keadaan kepercayaan untuk yang menjadi rumit ketika besar. Tidak ada menyebutkan jumlah operasi yang diperlukan tetapi untuk kompleksitas keadaan kepercayaan untuk .

N $N$

2N $2^N$

x $x$

N $N$

x $x$

Jawaban:

Anda benar bahwa makalah itu mengatakan hal yang salah. Anda tentu dapat mengevaluasi distribusi posterior di lokasi yang diketahui menggunakan operasi . Masalahnya adalah ketika Anda ingin menghitung momen posterior. Untuk menghitung rata-rata posterior tepat, Anda membutuhkan operasiIni adalah masalah yang coba dipecahkan oleh kertas. $x$ $O(n)$ $x$ $2^N$

Tom Minka
sumber

Anda melewatkan titik bahwa distribusi adalah campuran dari Gaussians: setiap sampel didistribusikan menurut dengan probabilitas dan sebagai (distribusi kekacauan untuk , independen ) dengan probabilitas . $y_i$ $p(y_i | x)$ $1-w$ $p_c(y)$ $y$ $x$ $w$

Biarkan menjadi variabel indikator yang menunjukkan bahwa sampel diambil dari distribusi kekacauan; jadi, jika ini menunjukkan bahwa sampel diambil dari . Jelas, jika sampel diambil dari distribusi kekacauan itu nilainya tidak relevan untuk estimasi . $c_i$ $i$ $0$ $p(y|x)$ $x$

Kehadiran status gabungan yang mungkin untuk variabel indikator inilah yang menyebabkan masalah. $2^N$

Dave
sumber

Namun, kita dapat menghapus variabel tambahan , karena kita perlu mendapatkan solusi posterior maksimum masalah. Posterior untuk memiliki bentuk yang jelas, sehingga kita tidak dipaksa untuk memperhitungkan semua negara hadir. Jadi, pertanyaannya adalah "Mengapa kita perlu jumlah perhitungan ini jika kita ingin menemukan solusi posterior maksimum?"

ci $c_i$

x $x$

2N $2^N$

Alexey Zaytsev

Maksimalisasi perlu diambil alih status untuk variabel .

c $c$

Dave

Kami tidak tahu , jadi kami mengintegrasikan (meringkas) . Ini bisa dilakukan secara langsung, bukan?

ci $c_i$

Alexey Zaytsev

Langsung ya, tetapi jumlah negara (istilah) tumbuh seperti , yang dapat bermasalah secara komputasi.

2N $2^N$

Dave

Kita dapat melakukan ini untuk setiap pengamatan secara independen, jadi kita memiliki kompleksitas , bukan .

O(n) $O(n)$

O(2n) $O(2^n)$

Alexey Zaytsev