Catatan Kecil EM-Algorithm [PDF]

Citation preview

Catatan Expectation Maximization Algorithm



oleh : Hendri Karisma (23512060)



Program Studi Magister Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung 2013



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



2



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



3



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 𝑚



𝑚 𝑖=1(𝑥𝑖



− 𝜇)2 ……………………………………...(3)



Dan setiap data 𝑥𝑖 akan dilakukan komputasi untuk setiap probabilitas terhadap kluster 𝑧𝑗 .



𝑝(𝑥) =



𝑛 2 𝑗 −1 𝑝(𝑥𝑗 ; 𝜇𝑗 , 𝜎𝑗 )



1 𝑛 𝑗 −1 2𝜋𝜎 𝑗



=



𝑒



(𝑥 𝑗 −𝜇 𝑗 )2 2𝜎 2 𝑗



……………………(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. 𝑥 𝑥 0 𝜇= 𝑦 = (𝑑𝑒𝑓𝑎𝑢𝑙𝑡); Σ = 𝑥 0



𝑦 0.5 0 𝑦 = (𝑐𝑜𝑛𝑡𝑜ℎ) 0 0.5 ………………………(5)



Sehingga persamaan nilai 𝑥𝑖 menjadi: 1



𝑝(𝑥; 𝜇, Σ) = 2𝜋



𝑛 1 2 |Σ|2



𝑒



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



……………………………(6)



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



4



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.



5



Repeat{ Expectation Step



(𝒊)



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



𝑚 𝑖=1



𝑇 1 − 𝑥 (𝑖) −𝜇 𝑗 Σ−1 (𝑥 (𝑖) −𝜇 𝑗 ) 1 2 𝑒 𝑛 1 2𝜋 2 |Σj |2



𝑘 𝑗 =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)



6



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



7