Expectation Maximisation Algorithm

7 05 2008

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.


Actions

Information

29 responses

24 11 2016
Riza

Trus misalkan fistribusi weibul ada masukan untuk menggunakan algoritma apa pak??
Dan knapa EM hanya di pakai distribusi normal dan poisson saja??

22 11 2016
Riza

pak yudi tulisannya sangat istimewa
Pak mohon pencerahan apakah distribusi yang lainnya dalam pelung bisa di pakai dalam k-means, setau saya dalam jurnal hanya dipakai, dist normal, binomial, poisson, hyper geometrik ???

29 07 2014
ika

Pak yudi Yth,

Mohon bantuannya, sekiranya bapak juga dapat menjelaskan tentang Probabilistic Latent Semantic Analysis (PLSA). Saya butuh pencerahannya mengenai metode ini, saya lihat di dalamnya juga melibatkan EM step untuk optimasi varibelnya.

Mohon Bantuannya, Pak Yudi.
Terimakasih.

9 09 2012
Listyagorjes

pak saya mau tanya,kalau data saya itu berupa nominal (dan itu bersifat kontinu) saya ingin mendiskritkan data ini menggunakan algoritma EM,bisa ga pak?

26 02 2014
Yudi Agusta

Bisa, tapi bukan dengan algoritma EM, karena EM mempunyai tujuan yang berbeda.

Regards,

17 03 2011
caca

pak, algoritma EM untuk data kategori, langkah awalnya kan mulai dari prior secara acak, acak tuh gmana ? terserah mau bilangan apa aja?

5 10 2011
Yudi Agusta

Proses acak artinya bahwa pengalokasian data dapat dilakukan secara random di awal. Karena untuk keadaan awal, kita tidak mengetahui masing-masing data ada di kelompok yang mana, sehingga perlu untuk melaksanakan pengalokasian secara acak ini.

Semoga menjawab.

4 05 2015
andres

nah itu gimana mengalokasikan datanya pak, pake iml sas bisa ga pak

7 05 2015
Yudi Agusta

Iml sas itu apa ya?

24 02 2011
okfan rizal ferdiansyah

salam kenal.

saya cuman pengen tanya, bagaimana kah langah step demi step jika Gausssian Mixture model digunakan untuk melakukan tracking pada video..

terimakasih

wassalam wr wb

24 02 2011
Yudi Agusta

Dik Okfan,

Untuk mixture model selengkapnya bisa dibaca di tulisan saya di https://yudiagusta.wordpress.com/mixture-modelling/. Mudah-mudahan itu bisa memberikan keterangan step by stepnya.

Sedangkan untuk permasalahan tracking video, saya sendiri tidak mendalami masalah itu. Yang mungkin perlu diperhatikan adalah variabel apa saja yang perlu di-ekstrak dari permasalahan tracking video ini, apakah pewarnaan, perubahan gambar atau yang lainnya. Yang pasti, harus ada variabel yang di-ekstrak dari permasalahan tersebut.

Demikian semoga membantu.

28 12 2010
ferry

salam kenal pak yudi….
saya mau nanya nih…
kebetulan lagi tesis tp bingung nih

btw, type data apa aja yg bisa diolah dengan
menggunakan EM pak…
klo data2 asuransi atau reasuransi bisa gak pak….
mohon pencerahannya….
nb: saya masi blank dengan EM,
mohon pencerahan & tutorial yg mudah dipahami dowk pak
makasi banyak

16 02 2011
Yudi Agusta

Bisa….
Misalnya untuk segmentasi pelanggan asuransi berdasarkan karakteristiknya atau mungkin berdasarkan produk yang diikuti….

Demikian semoga membantu.

28 09 2010
merry

pak, saya belum terlalu mengerti.. saya boleh bertanya kan pak??
kebetulan sekarang saya lagi tugas akhir..
data latent yg saya pakai itu skala pengukurannya ordinal.. apakah berpengaruh terhadap estimasi parameter?? apakah pakai EM algorithm atau Maximum Likelihood???
apakah ada perbedaan pemakaian EM algorithm dengan Maximum Likelihood??
kapan kita pakai Maximum Like lihood, dan kapan kita pakai EM Algorithm??

atas jawabannya makasih banyak ya pak..

10 02 2011
Yudi Agusta

Data ordinal bisa menggunakan distribusi Binomial atau Multinomial, metode estimasi parameternya tentu berbeda dengan distribusi Normal
Maximum Likelihood bisa dipecahkan dengan EM algorithm…. Jadi kedua istilah ini, kalau dikatakan secara general adalah hal yang sama

Demikian semoga menjawab

12 04 2010
citra

bapak, selama ini saya belum mendapatkan alur algoritma jalannya algoritma EM ini..
maksud saya alur jalannya lgoritma ini sampai dapat menghasilkan parameter..

mohon bantuannya..
terimakasih

30 04 2010
Yudi Agusta

Mungkin bisa dibaca dari tulisan saya di https://yudiagusta.wordpress.com/mixture-modelling/.

Semoga membantu.

20 03 2010
Ardyna Wahyu Hapsari

bapak kebetulan saya lagi tugas akhir dan EM ada didalamnya,
sampek sekarang saya belum pernah menemukan contoh dataset dari awal belum tercluster hingga tercluster dengan EM
Apa bapak kira-kira bisa bantu saya dengan memberi contoh yang jelas dan runut yang sudah bapak miliki
Jika berkenan mohon untuk dikirimkan ke email saya
Mohon bantuannya bapak untuk tugas akhir saya
Terimakasih sebelumnya

30 03 2010
Yudi Agusta

Saya tidak punya data khusus sekarang ini. Mungkin sebagai contoh umum, anda bisa mencari data Iris atau Diabetes di internet yang cukup bisa digunakan dalam menjelaskan fungsi algoritma EM dan hasil clusteringnya. Data tersebut banyak tersedia di internet.

Demikian semoga membantu

13 04 2010
Ardyna Wahyu Hapsari

klo data iris saja ada namun bagaimana prosesnya itu tidak terlihat
saya menggunakan WEKA untuk memperoleh hasilnya kebetulan di WEKA ada namun step by step-nya saya tidak bisa telusuri

mungkin bapak ada paper yang bisa membantu saya

30 04 2010
Yudi Agusta

Mungkin bisa dibaca tulisan saya di https://yudiagusta.wordpress.com/mixture-modelling/

Semoga membantu.

10 03 2010
citra

pak, tapi parameter yang saya estimasi itu parameter regresi linier . .
saya masih bingung dengan implementasinya..
terima kasih..

30 03 2010
Yudi Agusta

Prinsipnya sama saja. Misalnya dalam regresi linier ada variabel A dan B. Kedua variabel dapat juga dicari nilainya dengan algoritma Expectation Maximisation ini, dengan mencari nilai optimal A dan B secara bergantian.

Demikian semoga membantu

7 03 2010
citra

pak,,
saya tanya..
ada contoh konkritnya gt pak??
maksudnya contoh soal penggunaan algoritma ini..

skripsi saya membuat program aplikasi statistik,& untuk estimasi parameternya saya pakai algoritma EM . .

mohon bantuannya pak, trimakasih . .

8 03 2010
Yudi Agusta

Yang sederhana mungkin untuk memecahkan masalah estimasi nilai rata-rata (means) dan standar deviasi dari distribusi Normal (Gaussian). Kedua parameter perlu diturunkan dari fungsi distribusi probabilitas Gaussian sehingga mereka perlu untuk diestimasi secara bergantian sesuai dengan konsep EM.

Semoga membantu.

21 01 2010
Duant

Pak, saya mau nanya nih…

ada gak contoh data yang telah di kelompokkan dengan algoritm EM,
apakah itu data Text atau Numeric
agar lebih mudah dimengerti kak,
kemudian kalau boleh Pak, bapak punya gak sample data yang dikelompokkan dengan dengan EM yang murni…. tidak dengan EM yang menggunakan naive Baysiean…..

28 01 2010
Yudi Agusta

Mmm, dataset saya ada beberapa. Tapi kalau mau cari di internet juga banyak ada. Karena EM itu adalah metode unsupervised classification, data apa saja yang tidak mempunyai label kelas bisa digunakan untuk menjadi dasar pemodelan.

Saran saya untuk mencari di internet sesuai dengan keinginan.

Semoga bisa membantu.

21 01 2010
Yudi Agusta

Mmm, kalau ditanya kelebihan dan kekurangan susah juga ya. Tetapi mungkin satu hal tentang penggunaan probabilitas ataupun statistik didalam penerapan umum algoritma EM ini merupakan sudah kelebihan yang mencolok, karena data yang dimiliki akan berusaha untuk dimodel berbasis pada probabilitas tidak hanya berbasis pada jarak kesamaan yang sederhana seperti Eucledian, Manhattan, Hamming dll.

Mmmm pertanyaan kedua susah untuk dijawab ya. Sederhananya mungkin begini: algoritma ini melakukan optimasi secara bergantian terhadap beberapa variabel yang dibutuhkan dalam model. Misalnya untuk model distribusi normal ada variabel means dan standar deviasi. Algoritma EM ini akan secara bergantian berusaha mengestimasi kedua parameter itu sampai kedua parameter itu mencapai titik optimal.

Mungkin begitu yang bisa saya gambarkan dan semoga menjawab.

20 01 2010
indra

pak, saya mau nanya nih.

apa kelebihan dan kekurangan dari algoritma EM ini?

dan kalau bisa pak tolong di jelaskan secara detail bagaimana algoritma ini mengelompokkan data. kalau bisa juga pak di jelaskannya pake contoh.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: