Di mana teori grafik dalam model grafis?

29

Pengantar model grafis menggambarkan mereka sebagai "... perkawinan antara teori grafik dan teori probabilitas."

Saya mendapatkan bagian teori probabilitas tetapi saya mengalami kesulitan memahami di mana tepatnya teori grafik cocok. Wawasan apa dari teori grafik yang telah membantu memperdalam pemahaman kita tentang distribusi probabilitas dan pengambilan keputusan di bawah ketidakpastian?

Saya mencari contoh konkret, di luar penggunaan yang jelas dari terminologi teoretis grafik dalam PGM, seperti mengklasifikasikan PGM sebagai "pohon" atau "bipartit" atau "tidak diarahkan", dll.

graphical-model graph-theory distributions Vimal
sumber

33

Ada sangat sedikit teori grafik matematika yang benar dalam model-model grafis probabilistik, di mana dengan teori grafik matematika yang benar, saya maksudkan bukti-bukti tentang klik-klik, orde vertex, teorema min-cut max-flow, dan sebagainya. Bahkan sesuatu yang mendasar seperti Teorema Euler dan Handshaking Lemma tidak digunakan, meskipun saya kira orang mungkin meminta mereka untuk memeriksa beberapa properti kode komputer yang digunakan untuk memperbarui perkiraan probabilitas. Selain itu, model grafis probabilis jarang menggunakan lebih dari satu subset dari kelas grafik, seperti multi-grafik. Teorema tentang aliran dalam grafik tidak digunakan dalam model grafis probabilistik.

Jika siswa A adalah ahli dalam probabilitas tetapi tidak tahu apa-apa tentang teori grafik, dan siswa B adalah ahli dalam teori grafik tetapi tidak tahu apa-apa tentang probabilitas, maka A pasti akan belajar dan memahami model grafis probabilistik lebih cepat daripada B.

David G. Stork
sumber

8

Dalam arti yang ketat, teori grafik tampaknya secara longgar terhubung ke PGM. Namun, algoritma grafik berguna. PGM dimulai dengan inferensi penyampaian pesan, yang merupakan bagian dari kelas umum dari algoritma penyampaian pesan pada grafik (mungkin, itulah alasan untuk kata "grafis" di dalamnya). Algoritma graph-cut banyak digunakan untuk inferensi medan acak Markov dalam visi komputer; mereka didasarkan pada hasil yang mirip dengan teorema Ford-Fulkerson (max flow sama dengan min cut); kebanyakan algoritma populer mungkin Boykov – Kolmogorov dan IBFS.

Referensi. [Murphy, 2012 , §22.6.3] mencakup penggunaan pemotongan grafik untuk inferensi MAP. Lihat juga [Kolmogorom dan Zabih, 2004 ; Boykov et al., PAMI 2001] , yang mencakup optimasi daripada pemodelan.

Roman Shapovalov
sumber

Menarik untuk dicatat bahwa algoritma grafik-potong digunakan dalam MRF. Bisakah Anda menunjukkan referensi? Berdasarkan jawaban David Stork di atas, sepertinya algoritma ini muncul karena fakta bahwa teori grafik adalah alat pemodelan yang berguna, daripada beberapa hubungan mendasar antara teori grafik dan PGM.

Vimal

Saya telah menambahkan referensi saat Anda bertanya. Pada pernyataan terakhir Anda, bagaimana kami dapat memisahkan penyebabnya, yaitu mengetahui apakah penyebabnya mendasar atau tidak?

Roman Shapovalov

@overrider dapatkah Anda memberikan referensi lengkap sehingga makalah dapat dengan mudah dicari ..? Googling dapat mengarahkan orang ke referensi, tetapi bisa juga berakhir dengan membuang waktu untuk hasil yang tidak relevan. Jadi, judul, penerbit, nama jurnal, tautan, dll. Adalah hal yang baik untuk ditambahkan.

Tim

2

Algoritma pemotongan grafik berguna dalam penglihatan komputer tetapi tidak pada model grafis probabilistik. Satu masalah dalam penglihatan stereo adalah masalah korespondensi: menemukan titik mana dalam gambar A sesuai dengan titik dalam gambar B. Seseorang dapat mengatur grafik di mana simpul sesuai dengan poin fitur dalam dua gambar dan grafik mewakili semua kemungkinan korespondensi. Kemudian masalah menemukan korespondensi yang "tepat" dapat dianggap sebagai masalah pemotongan grafik. Tidak ada penggunaan seperti itu dalam model grafis generik, meskipun saya kira orang bisa mencoba memetakan masalah penglihatan komputer ini ke model grafis.

David G. Stork

2

@ DavidG.Stork Ada masalah penglihatan komputer lainnya yang menerapkan pemotongan grafik dengan cara yang serupa: segmentasi gambar, membuat kolase, dll., Sehingga pendekatannya cukup umum. Masalah-masalah tersebut dapat diekspresikan secara alami dalam hal model grafis yang tidak diarahkan (meskipun makalah tidak selalu melakukan itu). Itu memungkinkan menggunakan algoritma inferensi MRF yang berbeda, serta pemasangan model. Di sisi lain, pemotongan grafik dapat mengoptimalkan subset MRF yang cukup besar, sehingga dapat diterapkan di luar visi, misalnya untuk analisis jejaring sosial (walaupun saya tidak dapat mengingat makalah spesifik sekarang).

Roman Shapovalov

4

Ada beberapa pekerjaan yang menyelidiki hubungan antara kemudahan decoding kode Cek Paritas Rendah (yang mendapatkan hasil yang sangat baik ketika Anda menganggapnya sebagai grafik probablistik dan menerapkan Loopy Belief Propagation), dan ketebalan grafik yang dibentuk oleh matriks pemeriksaan paritas . Tautan ke ketebalan ini kembali ke masa ketika LDPC ditemukan [1] tetapi ada pekerjaan lebih lanjut dalam dekade terakhir ini [2] [3] setelah secara terpisah ditemukan kembali oleh Mackay et al [4] dan sifat-sifatnya memperhatikan .

Saya sering melihat komentar mutiara tentang waktu konvergensi penyebaran kepercayaan tergantung pada diameter grafik yang dikutip. Tapi saya tidak tahu ada pekerjaan yang melihat diameter grafik di grafik non-pohon dan apa efeknya.

RG Gallager. Kode Cek Paritas Rendah Densitas. MIT Press, 1963
IE Bocharova, F. Hug, R. Johannesson, BD Kudryashov, dan RV Satyukov. Kode cek paritas rendah kepadatan baru dengan ketebalan besar berdasarkan hypergraphs. Dalam Informasi Teori Prosiding (ISIT), Simposium Internasional IEEE 2010 pada, halaman 819 -823, 2010.
SC Tatikonda. Konvergensi dari algoritma penjumlahan-produk. Dalam Lokakarya Teori Informasi, 2003. Prosiding. IEEE 2003, halaman 222 - 225, 2003
David JC MacKay dan RM Neal. Near Shannon membatasi kinerja kode cek paritas kepadatan rendah. Electronics Letters, 33 (6): 457–458, 1997.

Menepuk
sumber

3

Salah satu aplikasi yang sukses dari algoritma grafik untuk model grafis probabilistik adalah algoritma Chow-Liu . Ini memecahkan masalah menemukan struktur grafik (pohon) yang optimal dan didasarkan pada algoritma pohon spanning maksimum (MST).

hal (x | T) = \prod_{t \in V} hal (x_{t}) \prod_{(s, t) \in E} \frac{hal (x_{s}, x_{t})}{hal (x_{s}) hal (x_{t})}

$\begin{equation} p(x|T) = \prod_{t\in V} p(x_t) \prod_{(s,t) \in E} \frac{p(x_s, x_t)}{p(x_s)p(x_t)} \end{equation}$

\frac{1}{N} \log P (D | θ, T) = \sum_{t \in V} \sum_{k} {hal}_{M. L.} (x_{t} = k) \log {hal}_{M. L.} (x_{t} = k) + \sum_{(s, t) \in E} saya (x_{s}; x_{t} | θ_{s t})

$\begin{equation} \frac{1}{N}\log P(D|\theta, T) = \sum_{t\in V}\sum_k p_{ML}(x_t=k) \log p_{ML}(x_t=k) + \sum_{(s,t)\in E} I(x_s; x_t|\theta_{st}) \end{equation}$

I (x_{s}; x_{t} | θ_{s t})

$I(x_s;x_t|\theta_{st})$

x_{s}

$x_s$

x_{t}

$x_t$

x

$x$

k

$k$

T

$T$

$I(x_s;x_t|\theta_{st})$

Vadim Smolyakov
sumber

Hai Vadim. Terimakasih atas tanggapan Anda. Sebagai rumusan dalam istilah-istilah teoretis grafik, itu masuk akal. Tetapi orang bisa melihatnya sebagai masalah optimasi juga. Semangat pertanyaan itu adalah untuk menanyakan hubungan yang lebih mendasar. Sebagai contoh, seseorang dapat merumuskan masalah pengurutan sebagai pengurutan topologis pada grafik, di mana node adalah angka, dan panah menunjukkan <= hubungan. Tapi itu tidak membuat koneksi mendasar antara pengurutan dan algoritma grafik, kan?

Vimal

Di mana teori grafik dalam model grafis?

Jawaban: