Kombinasi apa dari struktur data yang secara efisien menyimpan jaringan Bayesian yang terpisah?

22

Saya memahami teori di balik jaringan Bayesian, dan saya bertanya-tanya apa yang diperlukan untuk membangun satu dalam praktik. Katakanlah untuk contoh ini, bahwa saya memiliki jaringan Bayesian (diarahkan) dengan 100 variabel acak diskrit; setiap variabel dapat mengambil satu hingga 10 nilai.

Apakah saya menyimpan semua node dalam DAG, dan untuk setiap node menyimpan Tabel Kemungkinan Bersyarat (CPT)? Apakah ada struktur data lain yang harus saya gunakan untuk memastikan perhitungan nilai yang efisien ketika beberapa CPT berubah (selain dari yang digunakan oleh DAG)?

data-structures machine-learning Abu
sumber
Saya menggunakan dalam database sqlite memori untuk menyimpan tabel CP, karena DB diharapkan memiliki algoritma dan struktur data yang efisien untuk menangani tabel. Bekerja dengan baik! :)
Pratik Deoghare
Silakan tentukan apa yang Anda maksud dengan efisien (memori, kinerja, dll) dan sertakan kendala Anda. Tanpa itu semua ini bisa dengan mudah berakhir menjadi kontes untuk yang paling efisien yang akan menurunkan kode samar saya tidak pernah mau harus berurusan dengan dalam pekerjaan sehari-hari.
Justin Bozonier
1
@JustinBozonier membutuhkan lebih sedikit memori dan cepat?
Pratik Deoghare

Jawaban:

12

Struktur data "terbaik" mungkin tergantung pada masalah khusus apa yang Anda coba selesaikan. Inilah salah satu pendekatan yang pernah saya lihat (dan telah digunakan sendiri), yang hanya menyimpan semua informasi dan menyerahkannya kepada algoritma apa yang harus dilakukan dengannya.

  1. Pertama, Anda mengindeks node dengan bilangan bulat unik, 0 hingga n-1. Kemudian Anda cukup menyimpan, untuk setiap node, daftar orang tuanya sebagai array integer --- dalam C ++, misalnya, Anda dapat memiliki std::vector<std::vector<int> >: vektor pertama di atas node, vektor kedua mencantumkan orang tua masing-masing). Itu menangkap seluruh struktur DAG.

  2. Selain itu, karena setiap node memiliki tepat satu tabel probabilitas bersyarat yang terkait dengannya, Anda bisa mengindeks mereka dengan ID integer yang sama. Untuk setiap tabel probabilitas Anda perlu menyimpan ruang lingkupnya, yaitu himpunan variabel acak yang didefinisikan. Kedua, Anda mungkin memiliki satu daftar besar angka floating point yang berisi probabilitas kondisional aktual (dan Anda ingin memastikan Anda mendapatkan pengindeksan yang benar). Untuk memberikan contoh C ++ lagi, sesuatu seperti ini bisa dilakukan:

    struct CondProbTable {
    std::vector<int> scope;    // list of random variables the CPT is defined over
    std::vector<double> table; // appropriately sized and indexed table of
                               // conditional probabilities
};

    Dengan itu, Anda bisa menggunakan a std::vector<CondProbTable>untuk menyimpan semua CPT Anda.

Sekali lagi, ini pada dasarnya hanya menyimpan jaring Bayes, itu tidak menganggap apa pun tentang apa yang ingin Anda lakukan dengannya. Termasuk ruang lingkup CPT di CondProbTable agak berlebihan, karena bisa disimpulkan dari daftar node induk yang dijelaskan pada poin 1.

banyak
sumber
0

Pada dasarnya CPT diskrit adalah hypermatrix, dan Anda harus melihatnya dengan cara ini.

Cara yang cukup umum untuk merepresentasikan hypermatrix adalah dengan menggunakan hashtable using string index. misal dalam 2 dimensi t [1] [2] adalah t.get ("1_2")

Lebih banyak solusi efisien memori yang mungkin: Jika hypermatrix jarang, Anda dapat menggunakan representasi jarang (misalnya Fuchs 72), jika memiliki struktur Anda dapat menggunakan ADD (diagram keputusan aljabar), atau aturan berbasis logika.

Pertanyaan terakhir Anda tidak terlalu jelas, namun jika Anda mengharapkan CPT Anda sering berubah, mungkin Anda akan lebih baik dengan representasi datar CPT dengan tabel atau hashtable.

Nicolas
sumber