Bayesian Network – Expectation Maximization


Pada tulisan sebelumnya telah dipaparkan tentang proses pembelajaran pada Bayesian Network, contohnya pada kasus dimana struktur graph diketahui dan datanya fully observed yaitu dengan menggunakan perhitungan MLE (maximum likelihood estimate). Namun bagaimana bila ada nilai variabel yang tidak diketahui?

Contohnya pada graph berikut, nilai Sinus tidak diketahui, nilai variabel lainnya diketahui.

dari slide tom mitchell- machine learning

Untuk memudahkan perhitungan kita mengubah semua variabel yang diketahui menjadi X. Dan semua variabel yang tidak diketahui menjadi Z. Dalam kasus ini F,A,H,N menjadi X. Sementara S menjadi Z. Kemudian kita menggunakan EM (Expectation maximization) berikut:

Walaupun nilai Z ini diprediksi, namun karena perhitungannya dilakukan berulang dengan beberapa iterasi, diharapkan nantinya akan konvergen mendapatkan nilai S yang stabil. Sehingga EM ini menjamin kita akan mendapatkan nilai maksimum lokal (local maximum). Perhitungannya untuk kasus ini dimana X={F,A,H,N} dan Z={S} adalah

EM digunakan untuk pembelajaran pada kasus partially observed data (ada data yang tidak diketahui. Dari variabel X yang diketahui dan Z yang tidak diketahui maka dapat didefinisikan:

Kemudian lakukan interasi sampai konvergen :

langkah E (ekspektasi): menggunakan X dan nilai theta untuk menghitung P(Z|X,theta)

Langkah M (maksimisasi): mengganti nilai theta saat ini menjadi:

. Setiap Iterasi akan meningkatkan nilai:

Bila E dan theta perubahannya semakin kecil dan nilainya menjadi stabil maka dapat dikatakan konvergen. Contoh penghitung pada kasus sinus ini:

Langkah estimasinya menjadi:

Nilai S pertama bisa dipilih dulu secara random. Kemudian lakukan maksimisasi parameter sebagai berikut:

Bandingkan nilai diatas dengan nilai MLE bila semua nilai variabel diketahui:

Hasil perhitungan E(estimasi) digunakan untuk mengupdate semua paramater di perhitungan M. Kemudian theta dari M kemudian digunakan lagi untuk perhitungan E estimasi. Kemudian hasilnya dilakukan maksimisasi lagi. Prosesnya dilakukan berulang (iterativ) sampai terjadi konvergen.

Langkah E (estimasi) lakukan perhitungan untuk setiap data training. Hasil perhitungan ini akan mendapat nilai prediksi dari variabel yang tidak diketahui.

Langkah M dihitung untuk melakukan estimasi, mirip seperti MLE, tapi mengganti nilai variabel count (kemunculan) dengan nilai prediksi (expetcted count)

Sampai disini dulu, pada tulisan berikutnya insyaallah akan dibahas tentang tentang contoh perhitungan data yang tidak diketahui untuk training Naive Bayes Classifier. Semoga Bermanfaat!

Referensi:

Mitchell, Tom. “Machine learning.” (1997): 870-877.


Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *