Perkirakan entropi informasi melalui pengambilan sampel Monte Carlo

10

Saya mencari metode yang memungkinkan memperkirakan entropi informasi distribusi ketika satu-satunya cara praktis pengambilan sampel dari distribusi itu adalah metode Monte Carlo.

Masalah saya tidak berbeda dengan model Ising standar yang biasanya digunakan sebagai contoh pengantar untuk pengambilan sampel Metropolis – Hastings. Saya memiliki distribusi probabilitas atas satu set , yaitu saya harus untuk setiap . Unsur-unsur bersifat kombinatorial, seperti negara-negara Ising, dan jumlahnya sangat banyak. Ini berarti bahwa dalam praktiknya saya tidak pernah mendapatkan sampel yang sama dua kali ketika mengambil sampel dari distribusi ini di komputer. tidak dapat dihitung secara langsung (karena tidak mengetahui faktor normalisasi), tetapi rasio mudah untuk dihitung.p ( a ) a A a A p ( a ) p ( a 1 ) / p ( a 2 )Ap(a)aAaAp(a)p(a1)/p(a2)

Saya ingin memperkirakan entropi informasi dari distribusi ini,

S=aAp(a)lnp(a).

Atau, saya ingin memperkirakan perbedaan entropi antara distribusi ini dan yang diperoleh dengan membatasinya ke subset (dan tentu saja menormalisasi kembali).aA1A

Charles Wells
sumber

Jawaban:

3

Jika saya mengerti informasi apa yang Anda miliki, apa yang Anda inginkan tidak mungkin: informasi yang tersedia untuk Anda tidak cukup untuk menentukan entropi. Bahkan tidak cukup untuk mendekati entropi.

Kedengarannya seperti Anda memiliki cara untuk sampel dari distribusi , dan Anda memiliki cara untuk menghitung rasio p ( a 1 ) / p ( a 2 ) untuk setiap pasangan elemen yang 1 , sebuah 2 yang diperoleh melalui pengambilan sampel, tetapi Anda tidak memiliki informasi lain. Jika demikian, masalah Anda tidak dapat dipecahkan.p()p(a1)/p(a2)a1,a2

Secara khusus, kami dapat menemukan sepasang distribusi yang memiliki entropi berbeda, tetapi itu tidak dapat dibedakan menggunakan informasi yang tersedia untuk Anda. Pertimbangkan dulu distribusi seragam pada set (acak) ukuran . Pertimbangkan selanjutnya distribusi seragam pada set (acak) ukuran 2 300 . Ini memiliki entropi yang berbeda (200 bit vs 300 bit). Namun, mengingat informasi yang tersedia untuk Anda, Anda tidak memiliki cara untuk mengetahui yang mana dari dua distribusi yang Anda kerjakan. Secara khusus, dalam kedua kasus, rasio p ( a 1 ) / p ( a 2 )22002300p(a1)/p(a2)akan selalu tepat 1, sehingga rasio tidak akan membantu Anda membedakan antara dua distribusi. Dan karena paradoks ulang tahun, Anda dapat mencicipi sebanyak yang Anda suka, tetapi Anda tidak akan pernah mendapatkan nilai yang sama dua kali (tidak dalam masa hidup Anda, kecuali dengan probabilitas kecil secara eksponensial), sehingga nilai yang Anda dapatkan dari sampel akan terlihat seperti hanya poin acak dan tidak mengandung informasi berguna.

Jadi, untuk menyelesaikan masalah Anda, Anda harus tahu lebih banyak. Misalnya, jika Anda tahu sesuatu tentang struktur distribusi , itu mungkin memungkinkan untuk menyelesaikan masalah Anda.p()

DW
sumber
sebenarnya memiliki sifat khusus: seperti Gibbs, yaitu p ( a ) exp ( θ E ( a ) ) di mana E adalah "energi" dari a . Kecuali bahwa ada beberapa kuantitas "energi", masing-masing denganparameter θ yang sesuai. p(a)p(a)exp(θE(a))Eaθ
Charles Wells
1
@CharlesWells, saya tidak mengikuti apa yang Anda maksud dengan "banyak kuantitas". Kedengarannya layak untuk diposkan secara terpisah, sebagai pertanyaan terpisah, di mana Anda memberi kami informasi tentang struktur . Mungkin ada solusi untuk kasus khusus itu. p(a)
DW
2

Untuk bagian kedua dari pertanyaan Anda (estimasi entropi perbedaan antara distribusi) Anda mungkin dapat menggunakan identitas di mana E adalah energi rata-rata, T adalah suhu (itu sebanding dengan θ dalam p e θ E ), dan S adalah entropi. Untuk detailnya, lihat: Jaynes, E. (1957). Teori Informasi dan Mekanika Statistik. Ulasan Fisik, 106 (4), 620–630. http://doi.org/10.1103/PhysRev.106.620 .

F=ETS,
ETθpeθES

ΔFΔSΔFΔEA1AEA1

Berikut adalah dua referensi tambahan tentang algoritma untuk menghitung energi gratis:

Lelièvre, T., Rousset, M., & Stoltz, G. (2010). Komputasi Energi Gratis. Imperial College Press. http://doi.org/10.1142/9781848162488

Chipot, C., & Pohorille, A. (2007). Perhitungan Energi Gratis. (C. Chipot & A. Pohorille, Eds.) (Vol. 86). Berlin, Heidelberg: Springer Berlin Heidelberg. http://doi.org/10.1007/978-3-540-38448-9

Juan M. Bello-Rivas
sumber
Bisakah Anda memberikan referensi yang lebih praktis untuk menghitung perbedaan energi gratis? Wiki itu tidak terlalu jauh
Charles Wells
Selesai Saya menambahkan dua referensi lagi dan menunjuk tautan di sidebar wiki.
Juan M. Bello-Rivas