Expectation Maximisation Algorithm

Expectation Maximisation Algorithm (EM Algorithm) adalah algoritma yang sering digunakan untuk menemukan nilai estimasi Maximum Likelihood (ML) dari parameter dalam sebuah model probabilistic, dimana model juga tergantung pada latent variabel yang belum diketahui. Dalam algoritma ini, ada dua hal yang dilakukan secara bergantian yaitu E step yang menghitung nilai ekspektasi dari likelihood termasuk laten variabel seolah-olah seperti mereka ada, dan M step menghitung nilai estimasi ML dari parameter dengan memaksimalkan nilai ekspektasi dari likelihood yang ditemukan pada E step.

Latent variabel adalah variabel yang tidak terobservasi, yang dapat juga disamakan dengan missing data, missing measurements, dan hidden variabel. Dalam kasus mixture model, latent variabel juga mengacu pada jumlah komponen dari suatu mixture model.

Kalau y dianggap incomplete data dan terdiri dari nilai variabel yang sudah terobservasi dan z adalah missing data, maka y dan z akan membentuk complete data. Kalau p(y,z|theta) adalah joint probability density (mass) function, maka p(y,z|theta) bisa dianggap sebagai likelihood dari suatu complete data. Mengikuti teori Bayesian, selanjutnya conditional distribution dari missing data dengan berbasis pada data yang sudah terobservasi dapat diekspresikan sebagai:

p(z|y,theta) = p(y,z|theta)/p(y|theta)
= p(y|z,theta)*p(z|theta)/(INT p(y|z_est,theta)*p(z_est|theta)dz_est

Selanjutnya, EM algorithm secara iterative memperbaiki nilai estimasi dengan mengikuti proses estimasi seperti di bawah ini:

theta_(n+1) = arg max_theta Q(theta)

dimana Q(theta) = SUM(z) p(z|y,theta_n) log p(y,z|theta) atau dengan bentuk yang lebih umum Q(theta) = E_z[log p(y,z|theta)|y] merupakan nilai ekspektasi dari likelihood yang berbasis pada variabel yang sudah diobservasi (yang juga tergantung pada nilai estimasi sebelumnya).

Di sini, log likelihood digunakan sebagai ganti likelihood karena akan mempermudah formula. Perubahan ini tetap akan menghasilkan suatu nilai maksimum pada suatu bagian dari likelihood. Yang perlu diperhatikan di sini adalah nilai z tergantung pada nilai theta_n bukan theta_(n+1).

Berdasarkan pada persamaan di atas, nilai estimasi yang baru, theta_(n+1), akan didapatkan dengan mencari nilai estimasi yang memaksimalkan (M Step) nilai conditional expectation (E Step) dari log likelihood dari complete data yang berbasis pada variabel yang sudah terobservasi dan nilai paremeter terdahulu.

Sebagai catatan, bentuk continuous dari expectation Q(theta) adalah :

Q(theta) = INT(-infty to infty) p(z|y,theta_n) log p(y,z|theta) dz

Referensi:
Dempster A., Laird N., and Rubin D. (1977). Maximum Likelihood From Incomplete Data Via the EM Algorithm. Journal of the Royal Statistical Society, Series B, 39(1): 1-38.