Sistem "persamaan stokastik"

11

Pertimbangkan grafik dengan simpul dan tepi m . Verteks diberi label dengan variabel nyata x i , di mana x 1 = 0 adalah tetap. Setiap tepi mewakili "pengukuran": untuk tepi ( u , v ) , saya mendapatkan pengukuran z ≈ x u - x v . Lebih tepatnya, z adalah jumlah yang benar-benar acak dalam ( x u - x v ) ± 1 , terdistribusi secara seragam dan tidak tergantung pada semua pengukuran lainnya (tepi).nmxix1=0(u,v)z≈xu−xvz(xu−xv)±1

Saya diberi grafik dan pengukuran, dengan janji distribusi untuk di atas. Saya ingin "menyelesaikan" sistem dan mendapatkan vektor 's. Apakah ada beberapa badan yang menangani masalah jenis ini?xi

Sebenarnya, saya ingin menyelesaikan masalah yang lebih sederhana: seseorang menunjuk saya ke simpul dan t , dan saya harus menghitung x s - x t . Ada banyak hal untuk dicoba, seperti menemukan jalur terpendek, atau menemukan sebanyak mungkin jalur terpisah dan rata-rata (dibobot oleh kebalikan dari akar kuadrat panjang). Apakah ada jawaban "optimal"?stxs−xt

Masalah komputasi itu sendiri tidak sepenuhnya didefinisikan (misalnya harus saya mengasumsikan sebelumnya pada variabel?)xs−xt

ds.algorithms graph-algorithms Mihai
sumber
sementara ini bukan jawaban, menggunakan filter Kalman di sepanjang jalan dari s ke t muncul di pikiran sebagai cara untuk mendapatkan pegangan yang layak pada panjang jalan.
Suresh Venkat
Ini mungkin tidak membantu, atau mungkin jauh lebih banyak teknologi daripada yang dibutuhkan, tetapi ada teori pengembangan topologi aljabar stokastik untuk menjawab pertanyaan dalam robotika dan biologi molekuler tentang kompleks yang ujung-ujungnya diukur secara tidak tepat. Ada teorema tentang asimptotik hubungan acak (tautan = grafik dengan bobot tepi). Sebagai contoh, saya pikir hasil dalam makalah ini akan memungkinkan Anda untuk mendapatkan angka Betti yang diharapkan dari grafik Anda: arxiv.org/abs/0708.2997
Aaron Sterling
Apakah fakta bahwa kesalahan didistribusikan secara seragam dalam [-1,1] daripada beberapa distribusi lain yang melekat pada masalah Anda atau keputusan pemodelan sewenang-wenang? Jika yang terakhir Anda mungkin bisa membuat banyak hal lebih sederhana dengan menggunakan Gaussians sebagai gantinya.
Warren Schudy
±1

Jawaban:

3

Area yang ingin Anda lihat jawabannya adalah pembelajaran mesin. Anda telah menggambarkan model grafis. Saya pikir dalam hal ini metode semudah Propagasi Percaya sudah cukup.

Raphael
sumber
Perbanyakan keyakinan tidak tepat dalam grafik umum. Masalah Mihai tampaknya dipecahkan dengan metode yang lebih berprinsip daripada penyebaran keyakinan.
Warren Schudy
3

x

Warren Schudy
sumber
st
xxs−xtxs−xtxs−xt=c
Warren Schudy
Tentu saja menghitung volume polytope tertentu yang bersangkutan berpotensi menjadi jauh lebih mudah. Saya harus memikirkannya.
Warren Schudy
Saya memiliki kecurigaan bahwa Gaussians berperilaku lebih baik karena MLE dari distribusi bersama juga memberikan MLE dari setiap variabel. Tetapi saya harus berpikir lebih banyak dan / atau mencarinya untuk memastikan.
Warren Schudy
Contoh seri / paralel Anda menunjukkan bahwa meminimalkan jumlah residu kuadrat mungkin merupakan heuristik yang efektif untuk beberapa grafik bahkan ketika kesalahan Anda bukan Gaussian.
Warren Schudy