Pada tulisan sebelumnya telah dipelajari tentang Bayesian Netwok pada kasus struktur dan variabelnya lengkap. Kemudian pada kasus dimana ada variabel yang tidak lengkap, yaitu menggunakan EM (Expectation maximization). Sekarang akan dibahas tentang pembelajaran struktur bayes net, yaitu kasus dimana datanya diketahui tapi struktur graphnya tidak diketahui.

Secara umum untuk mempelajari struktur graph diperlukan data yang banyak. Bila kita tidak memiliki data yang banyak terdapat resiko terjadi overfitting. Cara lain dengan menggunakan metode tidak pasti: heuristic search, efficient. Atau menggunakan metode pasti seperti dynamic programming dan exponential time complexity. Atau bisa menggunakan metode bayesian untuk mebatasi pencarian. Karena secara default setiap node terhubung ke semua node lainnya.

Ada banyak penelitian yang telah dilakukan untuk mengatasi masalah ini. Namun ada penelitian dari Chow-Liu yang dapat digunakan untuk mencari struktur tree terbaik. Apa yang dimaksud dengan terbaik?

Yaitu bila P(X) adalah distribusi benar, T(X) adalah jaringan tree kita dimana X=<X1,…,Xn> . Chou-Lie melakukan minimisasi divergensi Kullback-Leibler:

Kenapa menggunakan struktur pohon (tree), karena pohon memenuhi struktur bayes net yaitu directed acylic graph (DAG). Tidak ada loop dalam 1 pohon. Walaupun sebenernya tidak semua bayesian network menggunakan tree.

Bila ada 2 distribusi, misalnya gaussian yang seperti lonceng. Persamaan kullback divergence ini mencoba menghitung seberapa jauh kedua distribusi ini sama atau tidak. Bila dua distribusi ini rata-rata (mean) yang sama, maka gambar kedua lonceng ini akan berhimpitan. Berarti divergencenya = 0. Bila tidak maka nilai divergencenya (berbeda) tinggi.

Cara mencari tree terbaik adalah dengan mencari T(X) yang memiliki nilai divergence minimal.

Untul meminimalkan dengan mencari T (pohon yang memiliki jumlah mutual information dari cabang2 yang memiliki nilai maksimal. Mutual information pada cabang antara variabel Adan B adalah:

Untuk node X=(X1,…,Xn) :

Yaitu KL divergene dari P dan T adalah mutual information AB ditambah dengan entropy X1 – Xn. Dengan H adalah konstan, tidak terpengaruh dengan struktur pohon, sementara I sangat tergantung dengan struktur pohon. Sehingga kita bisa fokus pada nilai I, dan mengabaikan nilai H. Semua nilai I pada A,B dijumlahkan. A, B adalah edge atau cabang. Jadi yang penting adalah memaksimalkan nilai mutual information antar simpul pada pohon. Atau mencari pasangan variabel yang memiliki mutual information tertinggi

Algoritma Chow-liu Algoritma adalah sebagai berikut:

1. Untuk setiap pasangan variabel A,B gunakan data untuk memperkirakan P(A,B), P(A) dan P(B)
2. Pada setiap pasangan variabel A,B hitung mutual information
3. Hitung maximum spanning tree dari kumpulan variabel menggunakan weight cabang I(A,B)
4. Tambah panah ke cabang untuk membentuk DAG dengan memilih sebuah node sebagai root dan arahkan panah keluar dari root.
5. Pelajari CPD dari graph

Sampai disini dulu. Penelitian lainnya tentang permasalahan struktur graph ini bisa dicari dengan kata kunci structrur learning. Semoga Bermanfaat!