Jaminan teoretis untuk waktu menjalankan metode penyebaran keyakinan?

14

Perambatan keyakinan telah terbukti menjadi metode yang sangat kuat melalui penelitian dalam model grafis probabilistik.

Namun, saya tidak tahu apa-apa tentang BP yang sebanding dengan metode MCMC di mana kita dapat memiliki skema aproksimasi acak polinomial sepenuhnya (FPRAS) untuk masalah # P-complete.

Bisakah seseorang mengarahkan saya ke beberapa referensi?

cc.complexity-theory reference-request graph-algorithms machine-learning st.statistics Tianyang Li
sumber
2
Versi propagasi kepercayaan muncul dalam kode ekspander dan dalam teknik spektral Alon & Kahale untuk mewarnai grafik 3-warna acak (serta banyak makalah berikutnya yang mengeksploitasi ide-ide mereka). Sementara itu menjawab judul Anda sampai batas tertentu, itu tidak menjawab isi pertanyaan Anda.
Yuval Filmus
2
BTW, saya tidak mendapatkan kalimat terakhir Anda. Apa yang Anda maksud dengan ini? "Metode MCMC di mana kita dapat memiliki skema aproksimasi acak polinomial sepenuhnya (FPRAS) untuk masalah # P-complete." Ada petunjuk?
Daniel
@Aniel Saya sedang mencari penyelesaian masalah menggunakan BP di mana mereka memiliki jaminan teoritis yang baik untuk menjalankan waktu.
Tianyang Li
Maka saya kira Anda perlu mengubah pernyataan masalah Anda. Saya mengerti hal yang berbeda.
Daniel

Jawaban:

12

BP dan sebagian besar variannya terbukti menyatu pada grafik tanpa siklus. Ketika Anda memiliki siklus, mereka terkadang menunjukkan perilaku yang sangat aneh. Untuk kasus-kasus ini orang telah mencoba skema perkiraan yang berbeda, misalnya Sherali-Adams, Lov? Asz-Schrijver, dan Lasserre Hierarchies.

Lihat [1] untuk ulasan komprehensif dari perkiraan ini. Juga (Wainwright dan Jordan, 2008) termasuk kelas perkiraan lainnya.

[1] http://cs.nyu.edu/~dsontag/papers/sontag_phd_thesis.pdf

Daniel
sumber
3
Ini juga mengapa propagasi survei (sepupu propagasi kepercayaan) bekerja sangat baik untuk memecahkan masalah acak 3-SAT besar. Untuk grafik faktor acak, secara lokal, grafik itu tampak seperti pohon dan karenanya propagasi survei dapat membuat kemajuan.
user834
5

Berikut adalah makalah di mana penulis menggunakan BP untuk mendapatkan skema pendekatan acak waktu polinomial sepenuhnya untuk masalah aliran jaringan biaya minimum yang dikapitalisasi.

Tianyang Li
sumber