Mengapa masalah kekacauan tidak dapat dilakukan untuk ukuran sampel besar?

13

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 p (x | \ mathbf {y}) dan, jadi, masalah menjadi sulit dipecahkan untuk sampel besar ukuran N . Namun, saya tidak tahu mengapa kita perlu perhitungan seperti ini dalam kasus ini, karena untuk y_i tunggaly = { y 1 , y 2 , ... , y N } y={y1,y2,,yN}y iyi p ( y i | x ) = 12 N(x,1)+12 N(0,10).

p(yi|x)=12N(x,1)+12N(0,10).
xxp(x|y)p(y|x)p(x)=p(x) N i=1p(yi|x).
p(x|y)p(y|x)p(x)=p(x)i=1Np(yi|x).
2 N2N p ( x | y ) p(x|y)N Ny iyikemungkinan memiliki bentuk p ( y i | x ) = 12 2 π (exp{-12 (yi-x)2}+110 exp{-120 y 2 i }).
p(yi|x)=122π(exp{12(yix)2}+110exp{120y2i}).

Dengan menggunakan rumus ini kita memperoleh posterior dengan perkalian sederhana p ( y i | x )p(yi|x) , jadi kita hanya perlu operasi NN , 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 2 N x yyimasukkan deskripsi gambar di sini2Nxy

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 O ( N ) xNO(N)x
Alexey Zaytsev
Apakah saya mengerti dengan benar bahwa Anda univariat? Jika demikian, Anda dapat menyelesaikan ini di yang dianggap dapat y i O ( n log ( n ) ) nyiO(nlog(n))n
ditelusuri
1
@ Alexey Setelah membaca kembali paragraf ini, saya pikir penulis tidak menyebutkan operasi. Dia hanya menunjukkan bahwa "keadaan kepercayaan untuk adalah campuran Gaussians" . 2 N x 2 N2Nx2N
1
@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. 2 N2N
Alexey Zaytsev
1
@ 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 . NN2N2NxxNNxx

Jawaban:

4

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.xxO(n)O(n)xx2N2N

Tom Minka
sumber
2

Anda melewatkan titik bahwa distribusi adalah campuran dari Gaussians: setiap sampel didistribusikan menurut dengan probabilitas dan sebagai (distribusi kekacauan untuk , independen ) dengan probabilitas .yiyip(yi|x)p(yi|x)1w1wpc(y)pc(y)yyxxww

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 .ciciii00p(y|x)p(y|x)xx

Kehadiran status gabungan yang mungkin untuk variabel indikator inilah yang menyebabkan masalah.2N2N

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?" cicixx2N2N
Alexey Zaytsev
Maksimalisasi perlu diambil alih status untuk variabel . cc
Dave
Kami tidak tahu , jadi kami mengintegrasikan (meringkas) . Ini bisa dilakukan secara langsung, bukan? cicicici
Alexey Zaytsev
Langsung ya, tetapi jumlah negara (istilah) tumbuh seperti , yang dapat bermasalah secara komputasi. 2N2N
Dave
Kita dapat melakukan ini untuk setiap pengamatan secara independen, jadi kita memiliki kompleksitas , bukan . O(n)O(n)O(2n)O(2n)
Alexey Zaytsev