Hidden Markov Models

25 06 2008

Hidden Markov Models merupakan sub ilmu dari Data Mining dan Soft Computing.

Hidden Markov Models adalah perkembangan dari Markov Chain dimana keadaan yang akan datang dari suatu sequence tidak hanya ditentukan oleh keadaan saat ini, tetapi juga perpindahan dari suatu state sequence ke state sequence yang lain. State sequence inilah yang merupakan bagian hidden dari suatu hidden markov models.

Salah satu contoh dari Hidden Markov ini adalah coin tossing. Dari sequence yang ada untuk pelaksanaan coin tossing, kita hanya tahu hasilnya adalah head and tail. Tetapi mengenai berapa coin yang digunakan dan bagaimana jenis coin yang digunakan tersebut kita tidak mengetahuinya.

Dari keterangan di atas, maka elemen dari sebuah HMM adalah:
1. N, jumlah state yang ada
2. M, jumlah nilai kemungkinan (observation symbols) yang ada
3. A = {a_ij}, state transition probability distribution matrix
4. B = {b_j (k)}, observation symbols probability distribution matrix
5. PI = {pi_i}, initial state distribution
6. O = {O_i}, observasi
7. Q = {q_i}, state sequence
8. S = {S_i}, nilai state

Tiga permasalahan yang ada dalam HMM adalah:
1. Bagaimana menghitung secara efisien nilai probability dari sebuah observasi sequence setelah model diketahui?
2. Bagaimana memilih state sequence yang optimal?
3. Bagaimana melakukan adjustment terhadap parameter dari HMM sehingga bisa memaksimalkan likelihood dari model?

Solusi Permasalahan 1
Nilai probabilitas atas dasar model yang diberikan dapat dihitung dengan menjumlahkan joint probabilitas dari semua kemungkinan state sequence q yang memungkinkan seperti di bawah ini

P(O|lambda) = SUM (all Q) P(O|Q,lambda) P(Q|lambda)
= SUM (q_1,q_2,…,q_T) PI_{q1}b_{q1}(O_1)a_{q1q2}b_{q2}(O_2)…a_{q(t-1)qT}(O_t)

Penghitungan nilai probabilitas ini dapat dilakukan dengan menggunakan Forward-Backward Procedure. Untuk forward procedure dapat memanfaatkan forward variabel alpha_t(i) yang didefinisikan sebagai:

alpha_t(i) = P(O_1 O_2 … O_t, qt = Si|lambda)

yang merupakan probabilitas dari sebagian sequence observasi, O1O2…Ot (sampai waktu t) dan state Si pada waktu t, berdasarkan pada model lambda. Permasalahan ini dapat dipecahkan secara inductive sebagai berikut:
1. Initialisasi: alpha_t(i) = Pi_i b_i (O_i), 1 less than i less than N
2. Induksi:alpha_t+1(j)=[Sum(i=1 to N) alpha_t(i) a_ij] b_j (O_t+1), 1 less than t less than T-1, 1 less than j less than N
3. Terminasi: P(O|lambda) = SUM (i=1 to N) alpha_t(i)

Untuk backward, sebenarnya mempunyai fungsi yang hampir sama dengan forward procedure. Akan tetapi, karena backward varibel akan digunakan untuk memecahkan permasalahan 3, maka di sini akan diperkenalkan pemecahan permasalahan 1 dengan backward procedure.

Backward variabel didefinisikan sebagai:

beta_t(i) = P(O_t+1 O_t+2 … O_T|qt = Si, lambda)

yang merupakan probabilitas dari sebagian sequence observasi, O_t+1 (sampai terakhir) dan state Si pada waktu t, berdasarkan pada model lambda. Permasalahan ini dapat dipecahkan secara inductive sebagai berikut:
1. Initialisasi: beta_t(i) = 1, 1 less than i less than N
2. Induksi:beta_t(j)= Sum(i=1 to N) a_ij] b_j (O_t+1) beta_t+1(j), t=T-1,T-2,…,1, 1 less than j less than N

Solusi Permasalahan 2
Dalam memecahkan permasalahan kedua ini, suatu variabel gamma_t(i) yang merupakan probabilitas untuk berada pada state S_i dengan diberikan sequence observasi O dan model lambda pada waktu t, dan dirumuskan sebagai berikut:

gamma_t(i) = P(q_i=S_i|O, lambda)

Rumus ini dapat diekpresikan dengan forward-backward variabel sebagai berikut:

gamma_t(i) = alpha_t(i) x beta_t(i) / P(O|lambda)
= alpha_t(i) x beta_t(i) / (SUM (j=1 to N) alpha_t(j) x beta_t(j)

Untuk mendapatkan solusi permasalahan kedua dapat dilakukan dengan memilih nilai observasi yang mempunyai nilai gamma_t(i) tertinggi. Tetapi hal ini mempunyai permasalahan, apabila sequence seharusnya berpindah dari suatu state ke state yang lain, karena ada kemungkinan untuk state selanjutnya nilai observasi yang bersangkutan mempunyai probabilitas untuk muncul sama dengan 0.0. Salah satu solusi untuk mengatasi ini adalah dengan memikirkan tidak hanya satu sequence ke depan, tetapi beberapa sequence. Salah satu algoritma yang digunakan untuk mencari probabilitas tertinggi untuk kemungkinan munculnya deretan sequence tambahan dari sequence yang sudah ada adalah Viterbi Algorithm.

Dalam algoritma ini, kita harus menghitung suatu variabel delta_t(i) yang merupakan probabilitas tertinggi yang dimiliki oleh suatu sequence dengan panjang t setelah diberikan observasi sequence sepanjang t dan dapat dirumuskan menjadi:

delta_t(i) = max (q1 … qt) P[q1q2…qt,O1O2…Ot|lambda]

Dengan sistem induksi kita bisa mendapatkan sequence dengan probability tertinggi sebagai berikut:
1. Initialisasi: delta_t(i) = PI_i b_i(O_i), 1 less than i less than N dan psi_1(i) = 0
2. Recursion: delta_t(j) max (1 less than i less than N) [delta_t-1(i)a_ij]b_j(Ot), 2 less than t less than T, 1 less than j less than N dan psi_t(j) = argmax (1 less than i less then N) [delta_t-1(i)a_ij], 2 less than t less than T, 1 less than j less than N
3. Termination: P* = max (1 less than i less than N) [delta_t(i)] dan q_T^* = argmax (1 less than i less than N) [delta_t(i)]
4. Path (state sequence) backtracking: q_t^* = psi_t+1 (q_t+1^*), t=T-1,T-2,…,1

dimana psi_t(j) merupakan array yang menyimpan state sequence dengan probabilitas tertinggi.

Solusi Permasalahan 3
Untuk melaksanakan proses update dan reestimation dari parameter HMM, kita perlu untuk mendefinisikan suatu variabel epsilon_t(i,j) yang merupakan probabilitas untuk berada pada state S_i pada waktu t dan di state S_j pada waktu t+1 dan dirumuskan sebagai berikut:

epsilon_t(i,j) = P(q_t=S_i,q_t+1=S_j|O,lambda)

Dengan memanfaatkan variabel forward dan backward, rumus di atas dapat dituliskan sebagai berikut:

epsilon_t(i,j) = alpha_t(i) a_ij b_j(O_t+1) beta_t+1(j) / P(O|lambda)
= alpha_t(i) a_ij b_j(O_t+1) beta_t+1(j) / (SUM (k=1 to N) SUM (l=1 to N) alpha_t(k) a_kl b_j(O_t+1) beta_t+1(l))

Pembaginya berfungsi sebagai normalisasi probabilitas. Kita juga bisa merumuskan delta_t(i) dari solusi permasalahan 2 dalam bentuk epsilon_t(i,j) menjadi:

delta_t(i) = (SUM j=1 to N) epsilon_t(i,j)

Selain itu dengan memperhitungkan suatu time period sampai T-1 maka (SUM t=1 to T-1) delta_t(i) merupakan expected number of transitions from S_i dan (SUM t=1 to T-1) epsilon_t(i,j) merupakan expected number of transitions from S_i to S_j. Sehingga cara untuk melakukan estimasi nilai parameter HMM dapat dirumuskan sebagai berikut:

PI_i = expected frequency (number of times) in state S_i at time (t=1) = delta_1(i)

a_ij = expected number of transitions from state S_i to state S_ j /
expected number of transitions from state S_i
= (SUM t=1 to T-1) epsilon_t(i,j) / (SUM t=1 to T-1) delta_t(i)

b_j(k) = expected number of times in state j and observing symbol v_k /
expected number of times in state j
= (SUM t=1 to T where O_t = v_k) delta_t(i) / (SUM t=1 to T) delta_t(i)

Pencarian estimasi parameter yang merupakan solusi maximum likelihood dapat dilakukan dengan mencari estimasi parameter dari sequence dengan panjang satu sampai dengan panjang N. Estimasi yang mempunyai nilai likelihood keseluruhan yang tertinggi merupakan solusi maximum likelihood dari sequence tersebut.

Catatan:
Untuk mencari solusi continuous dari HMM, bisa didapat dengan mengasumsikan bahwa nilai probabilitas dari satu nilai observasi ke observasi lainnya (b_j(k)) berbentuk distribusi continuous (umumnya Gaussian) dan menganggap distribusi probabilitas dari setiap nilai observasi merupakan penjumlahan berproporsi atau mixture modelling.

Referensi:
Rabiner L. R. (1999). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of The IEEE, Vol. 77, No 2, pp. 257 – 286.


Actions

Information

10 responses

13 05 2016
tangguh

mas ada contoh penerepan langsung ke angka/studi kasusnya ga? soalnya bingung klau rumus aja.. terima kasih sebelumnya

29 05 2016
Yudi Agusta

Maaf blm sempat nulis contohnya. Tks

24 01 2016
davidprasetyo.com

bingung euy.. :v
tp thx sebelumnya

20 03 2016
Yudi Agusta

Sama-sama

14 08 2014
adek

mas, bisa tolong dijelaskan tentang cara mendapatkan parameter HMM dg menggunakan kmeans sbg pengelompokannya

8 11 2012
irfan

mas minta referensi jurnal yang diatas donk

19 06 2014
Yudi Agusta

Mungkin bisa dicari melalui internet, atau library campus dik

14 04 2011
aldila

oiya mas HMM saya ttg prediksi..trims,,

14 04 2011
aldila

mas, saya lg skripsi ttg HMM ni..tp bingung gmn cara ngitungnya..mungkn mas ada contoh studi kasus yg bs saya pelajari???mkasih mas sebelumnya🙂

6 10 2011
Yudi Agusta

Mmmm, penjelasan di tulisan saya di atas seharusnya sudah bisa dipakai panduan untuk melakukan penghitungan. Coba diteliti lagi tulisan di atas.

Salam

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: