Catatan kecil EM-Algorithm

Catatan Expectation Maximization Algorithm

oleh : Hendri Karisma (23512060)

Program Studi Magister Informatika

Sekolah Teknik Elektro dan Informatika

Institut Teknologi Bandung

2013

2

Machine Learning

Pada dasarnya pembelajaran mesin dibagi menjadi beberapa tiga jenis, yaitu

supervised, unsupervised, dan reinforcement learning. Dari masing-masing jenis

pembelajaran mesin ini memiliki berbagai metode yang memiliki spesifikasi berbeda dan

dapat menyelesaikan masalah dengan kondisi yang berbeda satu sama lainnya, sehingga

berbagai kasus belum tentu dapat diselesaikan dengan algoritma yang sama, ataupun

dengan jenis pembelajaran mesin yang sama. Masing-masing jenis machine learning

memiliki karakteristik yang berbeda. Supervised Learning memiliki karakteristik masalah

yang diselesaikan biasanya berupa klasifikasi, dataset yang dimiliki oleh kasus yang

berbentuk klasifikasi biasanya selain memiliki atribut untuk setiap instances-nya namun

juga sudah memiliki kelas yang jelas, sehingga task selanjutnya dari hipotesis atau model

yang ditemukan adalah melakukan klasifikasi terhadap instance yang baru dan belum

memiliki label (belum diklasifikasi). Unsupervised Learning biasanya memiliki kata kunci

clustering atau melakukan peng-klusteran terhadap sekelompok data atau sekelompok

instances yang tidak memiliki label, sehingga memiliki informasi bahwa terdapat

sekumpulan data yang membentuk cluster, namun kita belum tahu apa pengetahuan atau

hipotesis yang membuat instances tersebut saling berkumpul (membuat kelompok)

menjadi satu cluster atau lebih. Sedang reinforcement learning biasanya berupa

permasalah yang membutuhkan aktifitas eksplorasi, sehingga cukup sesusai jika

digunakan untuk membangun suatu intelijen pada suatau game (terutama puzzle).

Dalam artikel ini akan sedikit dijelaskan mengenai Expectation Maximization

Algorithm dengan. Maximization Algorithm dengan menggunakan model probabilitas

pada distribusi gaussian.

Expectation Maximization Algortihm

Expectation maximization algorithm merupakan algoritma unsupservised

learningyang memiliki kemampuan untuk melakukan pencarian knowledge dari

sekumpulan data yang tidak memiliki label atau target class tertentu, dengan cara melihat

3

nilai setiap instances yang didistribusikan kedalam Gaussian distribution, lebih tepatnya

adalah mixture Gaussian, lalu dilakukan iterasi menaik untuk mencari nilai likehood

tertenggi untuk setiap instance (melihat kedekatan instances terhadap setiap kluster).

Expectation Maximization Algorithm (EM Algorithm) merupakan

sendirimerupakan adalah suatu algoritma yang memanfaatkan mixture dari Gaussian

mixture. Pada dasarnya E-M Algorithm terdiri dari dua langkah yaitu, expectation dan

maximization. Melakukan perhitungan expektasi terhadap suatu nilai probabilitas

likelihood, lalu langkah kedua memperbaiki nilai probabilitas terebut dengan merubah

parameter pada mixture Gaussian sehingga mencapai maximum likelihood.

Terdapat beberapa hal yang perlu ditekankan dalam algoritma EM Algorithm yaitu:

1. Maximum Likelihood Estimation (MLE)

2. Mixtures of Gaussians

3. Estimation-Maximization (EM)

Maximum likelihood sendiri pada dasarnya merupkan teori probabilitas pada suatu

instances (misalkan 𝑥𝑖 ∈ 𝑋)terhadapsuatu target class𝑧𝑗 {j=1,2…n}. Dataset X

didistribusikan kedalam Gaussian Distribution seperti pada gambar 3.

Gambar 1sample distribusi normal

4

Persamaan yang digunakan untuk Gaussian distribution adalah :

𝑃 𝑥; 𝜇,𝜎2 =1

2𝜋 .𝜇𝑒 −

𝑥−𝜇 2

2𝜎2 ……………………………..(1)

Dengan 𝜇 adalah mean dan 𝜎 merupakan variance atau standar deviasi.

𝜇 =1

𝑚 𝑥𝑖𝑚𝑖=1 ………………………………………………(2)

𝜎2 =1

𝑚 (𝑥𝑖 − 𝜇)2𝑚𝑖=1 ……………………………………...(3)

Dan setiap data 𝑥𝑖 akan dilakukan komputasi untuk setiap probabilitas terhadap

kluster 𝑧𝑗 .

𝑝(𝑥) = 𝑝(𝑥𝑗 ; 𝜇𝑗 ,𝜎𝑗2) =

1

2𝜋𝜎𝑗𝑒

(𝑥𝑗−𝜇 𝑗 )2

2𝜎𝑗2

𝑛𝑗−1

𝑛𝑗−1 ……………………(4)

Guna meningkat fitness dari distribusi cluster yang dibangun maka dilakukan

matriks covariance dan juga vector mean untuk meningkatkan akurasi dari Gaussian

distribution (Multivariate) yang dibuat.

𝜇 = 𝑥𝑦 =

00 (𝑑𝑒𝑓𝑎𝑢𝑙𝑡); Σ =

𝑥 𝑦𝑥 𝑦 = (𝑐𝑜𝑛𝑡𝑜ℎ)

0.5 00 0.5

………………………(5)

Sehingga persamaan nilai 𝑥𝑖 menjadi:

𝑝(𝑥; 𝜇, Σ) =1

2𝜋 𝑛2 |Σ|

12

𝑒 −1

2 𝑥−𝜋 𝑇Σ−1(𝑥−𝜋) ……………………………(6)

Dan visualisasi dalam bentuk tiga dimensinya adalah seperti pada contoh berikut :

5

Gambar 2 Contoh kondisi grafik dengan mean dan varian tertentu (multivariate)

Namun pada EM Algorithm menggunakan mixture Gaussian atau dengan kata lain

lebih dari satu Gaussian yang digunakan atau mencari mixture dari distribusi yang

didapatkan. EM Algorithm memiliki tugas untuk menemukan setiap Gaussian yang

terdapat pada distribusi mixture Gaussian dan mengembangkan setiap Gaussian yang

ditemukan pada kondisi optimum (sehingga model lebih fit) itulah yang disebut dengan

maximization, dan merupakan proses clustering.

Sehingga berikut adalah algoritma secara penuh E-M Algorithm.

6

Repeat{

Expectation Step

𝒘𝒋(𝒊)

= 𝒑(𝒛(𝒊) = 𝒋|𝒙(𝒊);𝝓,𝝁,𝚺) =

1

2𝜋 𝑛2 |Σj |

12

𝑒 −

12 𝑥(𝑖)−𝜇 𝑗

𝑇Σ−1(𝑥(𝑖)−𝜇 𝑗 )

.𝜙

𝑤𝑗(𝑖)

𝑘𝑗=1

𝑚𝑖=1

Maximization

𝜙𝑗 =1

𝑚 𝑤𝑗

(𝑖)

𝑚

𝑖=1

𝜇𝑗 = 𝑤𝑗

(𝑖)𝑥(𝑖)𝑚

𝑖=1

𝑤𝑗(𝑖)𝑚

𝑖=1

Σ𝑗 = 𝑤𝑗

(𝑖) 𝑥(𝑖) − 𝜇𝑗 𝑥

(𝑖) − 𝜇𝑗 𝑇𝑚

𝑖=1

𝑤𝑗(𝑖)𝑚

𝑖=1

}

Contoh visualisasi expectation maximization ketika Gaussian didapatkan dan

proses EM-Algorithm telah dieksekusi.

Gambar 3 Contoh distribusi norma mixture gaussian (multivariate)

7

Gambar 4 Contoh visualisasi hasil akhir E-M Algorithm

Referensi

1. Arthur, Samuel. (1959): Some Studies in Machine Learning Using the Game of Checkers,

IBM Journal of Research and Development Vol:44, 06 April 2010.

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5389202

2. Mitchell, Tom M. (1997) : Machine Learning,McGraw-Hill Science, Portland.

3. Andrew Ng, Lecture Notes: Machine Learning, Standford