BAB 5 ENTROPI PADA MATRIKS EMISI MODEL MARKOV TERSEMBUNYI

BAB 5 ENTROPI PADA MATRIKS EMISI MODEL MARKOV TERSEMBUNYI Model Markov Tersembunyi (Hidden Markov Model, MMT) telah banyak diaplikasikan dalam berbagai bidang seperti pelafalan bahasa (speech recognition) dan klasifikasi (clustering). Teori dasar mengenai MMT diperkenalkan oleh Baum dan kawan-kawan

pada tahun 1960 an. Kemudian ketika era komputer mulai

berkembang pada awal 1980 an, Rabiner, Juang dan kawan-kawan menerbitkan jurnal mengenai MMT pada pelafalan bahasa berbasiskan MMT. Pada model mereka, setiap saat ketika sebuah kata diucapkan, pada dasarnya akan membentuk barisan state. Setiap orang tentu memiliki pelafalan yang berbeda-beda sehingga sangat mungkin untuk mengenalinya melalui MMT.

Selanjutnya dari hasil penelitian-penelitian mereka, MMT menjadi semakin populer dan telah diaplikasikan dalam bidang seperti ekonomi, psikologi, dan ilmu politik. Dalam 10 tahun terakhir ini, MMT banyak dikembangkan untuk mempelajari susunan DNA. Data DNA sudah dapat didownload di Gen Bank.

Sebagai contoh dari MMT dapat dilihat pada kasus perubahan cuaca. Setiap hari mempunyai kemungkinan cuaca yaitu cerah atau tidak cerah. Kemudian diberikan hasil pengamatan cuaca sebanyak 30 data. Akan tetapi, orang tidak mengetahui apakah informasi ini berasal dari 30 hari pengamatan yang dilakukan setiap hari atau

46

BAB 5 ENTROPI PADA MATRIKS EMISI HIDDEN MARKOV MODEL

47

pengamatan yang dilakukan selama 30 minggu. Hasil observasi dari pengamatan adalah cuaca cerah (disimbolkan dengan C) atau tidak cerah (disimbolkan T). Hasil observasinya ini (misal CTTTCCTCTCC..) dinamakan barisan observasi atau barisan data. Dalam MMT, tiap observasi secara parsial ditentukan oleh state saat ini. Barisan state ini tidak terlihat sehingga disebut hidden atau tersembunyi. Barisan state ini diasumsikan mengikuti rantai Markov yaitu state saat ini hanya bergantung pada state sebelumnya, seperti dijelaskan pada bab 2.

5.1

Definisi Model Markov Tersembunyi

MMT merupakan model yang melibatkan dua atau lebih barisan proses stokastik, yaitu barisan yang tidak terobservasi, {St} dan barisan yang terobservasi, O={Ot}, dengan t=1,2,..T dan T adalah banyaknya observasi. Barisan {St} mengikuti sifat rantai Markov dengan matriks transisi A NxN = ( aij ) , aij = P ( St +1 = j | St = i ) dan N adalah banyaknya keadaan (tersembunyi). Keterkaitan antara {St} dan O dinyatakan secara fungsional melalui peluang bersyarat Ot, jika St ditetapkan, dan dinotasikan sebagai matriks emisi B= bi ( Ok ) = P ( Ot = k St = i ) , dengan bi (ok ) ≥ 0 dan

K

∑b m =1

ik

=1,

untuk semua i.

Dari definisi di atas, spesifikasi MMT melibatkan tiga parameter yaitu N, M, dan T dan tiga peluang parameter yaitu A, B, dan π, dengan π adalah distribusi peluang awal. Untuk menyederhanakan, digunakan notasi λ = ( A, B, π ) . Tiga masalah utama yang dihadapi pada MMT menurut Rabiner [8] adalah: 1. Diberikan barisan observasi

O = o1o2 … oT

dan model

λ = ( A, B, π ) .

Bagaimana menghitung P ( O | λ ) , peluang observasi jika diberikan model? 2. Diberikan barisan observasi

O = o1o2 … oT

dan model

λ = ( A, B, π ) .

Bagaimana menentukan barisan state Q = q1q2 ...qT yang optimal?


48

3. Diberikan barisan observasi O = o1o2 … oT Bagaimana menaksir parameter

λ = ( A, B, π ) dari MMT?

Asumsi yang digunakan pada MMT memenuhi : 1. Rantai Markov orde 1, dengan peluang transisi dari satu keadaan ke keadaan lain hanya bergantung pada dua state dan saling bebas terhadap observasi yaitu

(

)

P Qt +1 = s j | Qt = si , Qt −1 = sit −1 ,..., Q1 = si1 = P ( Qt +1 = s j | Qt = si )

(5.1)

untuk semua i, j, t. 2. Emisi yang saling bebas, peluang emisi pada saat t hanya bergantung pada keadaan saat t. T

P ( O|Q,λ ) = ∏ P ( Ot | qt , )

(5.2)

t =1

3. Waktu yang homogen, peluang transisi saling bebas terhadap waktu dengan P ( Qt +1 = s j | Qt = si ) = P ( Qu +1 = s j | Qu = si ) untuk t , u ≥ 1

(5.3)

Permasalahan pertama dapat diselesaikan dengan algoritma Forward dan algoritma Backward. Sedangkan algorimta Viterbi dapat digunakan untuk menyelesaikan permasalahan kedua. Untuk permasalahan ketiga, diselesaikan dengan Ekspektasi Maksimum dan algoritma Baum-Welch. Pada tugas akhir ini tidak dibahas mengenai metoda-metoda tersebut. Penjelasan lebih dalam dapat dilihat pada tesis Haryono [6].

5.2

Entropi pada Model Markov Tersembunyi

Setelah mengetahui definisi entropi dan MMT, pada sub bab ini akan dibahas mengenai penggunaan entropi dalam MMT. Entropi pada MMT digunakan untuk mencari barisan state yang optimal (permasalahan kedua pada MMT).


49

Untuk mempelajari lebih lanjut maka definisikan variabel-variabel berikut:

(

)

1. H t ( j ) = H S t −1 St = j , O t = ot , entropi dari barisan state menuju state j pada waktu t, diberikan observasi hingga waktu t. 2. ct ( j ) = P ( St = j | O t = o t ) , peluang berada di state j pada waktu t, diberikan observasi hingga waktu t.

Ht ( j ) dapat dihitung secara rekursif menggunakan nilai yang diperoleh dari Ht −1 ( i ) ,

1 ≤ i ≤ N . Diasumsikan berada di state j pada waktu t, maka barisan state (path) dapat dibagi menjadi dua, yaitu 1. Barisan state hingga waktu t-2, misal dinamakan X2. 2. Barisan state hingga waktu t-1, misal dinamakan X1. Sehingga H ( X 1 , X 2 ) = H ( X 1 ) + H ( X 2 X 1 ) .

(5.4)

1. Entropi dari X1, H(X1) berkaitan dengan P ( St −1 = i St = j ) dapat dihitung melalui ct ( k ) , 1 ≤ k ≤ N dan ct ( l ) , 1 ≤ l ≤ N 2. Entropi H ( X 2 X 1 ) dihitung dari Ht −1 ( k ) , 1 ≤ k ≤ N , menggunakan persamaan H ( X 2 X 1 ) =

∑ P(x )H(X 1

x1∈χ

X 1 = x1 ) .

2

Bentuk rekursi ini dapat ditinjau sebagai berikut N

(

)

ct ( j ) = P St = j | O = o = t

t

∑ c (i ) a b (o )

i =1 N N

t −1

ij

j

t

∑∑ c ( i ) a b ( o ) k =1 i =1

Untuk mendapatkan Ht ( j ) , diuraikan

t −1

ik k

t

(5.5)


(

) ( P(S =

P St −1 = i St = j , Ot = ot = P St −1 = i St = j , Ot = ot , Ot −1 = ot −1 t

= j , Ot = ot St −1 = i, Ot −1 = ot −1

(

P St = j , Ot = ot O t −1 = ot −1

=

=

P ( Ot = ot St = j ) P ( St = j St −1 = i )

(

P ( Ot = ot St = j ) P St = j Ot −1 = ot −1

(

)

(S

N

∑ P(S

t

t −1

= i O t −1 = ot −1

)

(

.P St −1 = i O t −1 = ot −1

P ( St = j St −1 = i ) P St −1 = i O t −1 = ot −1 k =1

=

)

) ) .P

50

(

)

)

= j St −1 = k ) P St −1 = k Ot −1 = ot −1

)

aij ct −1 ( i )

N

∑a

c

kj t −1

k =1

(k )

(5.6)

Kemudian entropi dari

( = H(S = H(S

H t ( j ) = H S t −1 St = j , O t = ot t −2

t −1

)

) = o ) + H(S

, St −1 St = j , O t = ot St = j , O t

t

(5.7) t −2

St −1 , St = j , O t = ot

)

dengan

(

)

) ( (

(

N

))

H St −1 St = j , O t = ot = −∑ ⎡⎢ P St −1 St = j , O t = ot .log P St −1 St = j , O t = ot ⎤⎥ ⎦ i =1 ⎣

(5.8)

dan

(

)

N

(

N

(

) (

)

H S t − 2 St −1 , St = j , O t = ot = ∑ ⎡ P St −1 = i St = j , O t = ot .H S t − 2 St −1 , St = j , O t = ot ⎤ ⎣ ⎦ i =1

)

(5.9)

= ∑ ⎡ P St −1 = i St = j , O = o .H t −1 ( i ) ⎤ ⎣ ⎦ i =1 t

t

Jadi, entropi dari barisan state hingga t-2, diberkan state hingga t-1 dan observasi sampai t-1, saling bebas secara bersyarat dengan state dan observasi hingga t,

(

)

H S t − 2 St −1 = i, St = j , Ot = ot = H t -1 ( i ) .

(5.10)


51

Dengan menggunakan sifat dasar dari entropi dapat dihitung,

(

)

(

) (

H S T OT = oT = H S T −1 ST , OT = oT + H ST OT = oT N

N

i =1

i =1

) (5.11)

= ∑ HT ( i ) cT ( i ) − ∑ cT ( i ) log ( cT ( i ) ) Algoritma secara umum 1. Inisiasi. Untuk 1 ≤ j ≤ N ,

H1 ( j ) = 0 c1 ( j ) =

π ( j ) b j ( o1 )

(5.12)

N

∑ π (i ) b (o ) i

i =1

1

Pada tahap insiasi, entropi awal dan peluang berada di state j pada t=1 ditetapkan nol, agar langkah selanjutnya

yaitu

rekursi

dapat

berjalan

karena algoritma ini bergerak maju (forward). 2. Rekursi. Untuk 1 ≤ j ≤ N ; 2 ≤ t ≤ T , N

(

)

ct ( j ) = P St = j | O = o = t

t

∑ c (i ) a b (o ) t −1

i =1 N N

)

P St −1 = i St = j , O t = ot =

t −1

ik k

∑a

c

kj t −1

(

H t ( j ) = ∑ H t −1 ( i ) P St −1 = i St = j , O t = ot i =1 N

t

t

(5.14)

(k )

)

) ( (

(

(5.13)

aij ct −1 ( i ) N

k =1

N

j

∑∑ c ( i ) a b ( o ) k =1 i =1

(

ij

))

−∑ ⎡⎢ P St −1 St = j , O t = ot .log P St −1 St = j , O t = ot ⎤⎥ ⎦ i =1 ⎣

(5.15)

3. Penghentian.

(

)

N

N

i =1

i =1

H S T OT = oT = ∑ HT ( i ) cT ( i ) − ∑ cT ( i ) log ( cT ( i ) )

(5.16)


52

Contoh 5.1 Agar dapat memahami lebih lanjut, ditinjau contoh kasus sebagai berikut yang merupakan modifikasi contoh dari Hernando dan Crespi [7]. Misalkan terdapat lima keadaan yang masing-masing dilambangkan dengan angka 1, 2, 3, 4, dan 5. Pada kasus ini, matriks transisi, matriks emisi dan distribusi peluang awal ditetapkan yaitu ⎛ 0 0.5 0 0.5 0 ⎞ ⎜ ⎟ 0 ⎟ ⎜ 0 0.5 0.5 0 ⎜ 0 0.5 0.5 0 0 ⎟, ⎜ ⎟ 0 0.5 0.5 ⎟ ⎜0 0 ⎜0 0 0 0 1.0 ⎟⎠ ⎝

0 0 0 ⎞ ⎛ 1.0 0 ⎜ ⎟ 0 0 ⎟ ⎜ 0.5 0.5 0 ⎜ 0 0.5 0.5 0 0 ⎟ , (1.0 0 0 0 0 ) ⎜ ⎟ ⎜ 0 0.5 0 0.5 0 ⎟ ⎜ 0 0 0 0 1.0 ⎟⎠ ⎝

dengan diagram transisinya dapat digambarkan sebagai :

Gambar 5.1 : Diagram transisi contoh 5.1 Gambar diagram transisi di atas dapat dibaca sebagai berikut. Misalkan berada di keadaan 1 maka peluang pindah ke keadaan ke 2 atau 3 setelah satu langkah adalah 0,5. Begitu pula apabila berada di keadaan 2 maka peluang untuk pindah ke keadaan 3 atau tetap berada di keadaan 2 adalah 0,5. Demikian pula jika berada di keadaan 3, 4 atau 5.


53

Untuk kasus di atas, penulis menetapkan A0 dan B0. Tetapi dalam kenyataan, tidak semudah ini. Ada dua alternatif yang digunakan dalam menentukan A0 dan B0 yaitu 1.

Jika ada penelitian sebelumnya yang serupa maka hasil perhitungan A dan B bisa dijadikan A0 dan B0,

2.

Jika tidak ada informasi apa pun, tentukan nilai peluang dari A0 dan B0 sama.

Kembali ke contoh 5.1, akan digunakan tahap-tahap dalam algoritma yaitu 1.

Inisiasi. Untuk 1 ≤ j ≤ 5 , maka persamaan (5.12) menjadi c1 (1) =

π (1) b1 (1) 5

∑ π ( i ) b (1) i =1

c1 ( 2 ) =

c1 ( 3) =

5

∑ π ( i ) b (1)

c1 ( 4 ) =

π ( 3) b3 (1)

∑ π ( i ) b (1)

c1 ( 5 ) =

5

∑ π ( i ) b (1)

=

0× 0 =0 (1×1) + ( 0 × 0,5) + ( 0 × 0 ) + ( 0 × 0 ) + ( 0 × 0 )

=

0× 0 =0 (1×1) + ( 0 × 0,5) + ( 0 × 0 ) + ( 0 × 0 ) + ( 0 × 0 )

=

0× 0 =0 (1×1) + ( 0 × 0,5) + ( 0 × 0 ) + ( 0 × 0 ) + ( 0 × 0 )

i

π ( 5 ) b5 (1) 5

∑ π ( i ) b (1) i =1

0 × 0,5 =0 (1×1) + ( 0 × 0,5) + ( 0 × 0 ) + ( 0 × 0 ) + ( 0 × 0 )

i

π ( 4 ) b4 (1) i =1

=

i

5

i =1

1× 1 = 1, 0 (1×1) + ( 0 × 0,5) + ( 0 × 0 ) + ( 0 × 0 ) + ( 0 × 0 )

i

π ( 2 ) b2 (1) i =1

=

i

state (j)

H1(j)

c1(j)

1

0

1,0

2

0

0

3

0

0

4

0

0

5

0

0

Tabel 5.2 : Tahap inisiasi entropi pada MMT


2.

54

Rekursi. Untuk 1 ≤ j ≤ 5 ; 2 ≤ t ≤ 5 , Untuk t=2 maka bentuk persamaan (5.13) menjadi 5

(

)

c2 (1) = P S 2 = 1| O 2 = o 2 =

∑ c (i ) a b ( 2) 5

i =1 5

∑∑ c ( i ) a b ( 2 ) k =1 i =1

=

i1 1

1

1

ik k

(1× 0 × 0 ) + ( 0 × 0 × 0 ) + ( 0 × 0 × 0 ) + ( 0 × 0 × 0 ) + ( 0 × 0 × 0 ) {(1× 0 × 0 ) + ... + ( 0 × 0 × 0 )} + {(1× 0, 5 × 0, 5) + ... + ( 0 × 0 × 0, 5)} + ... + {(1× 0 × 0 ) + ... + ( 0 × 1× 0 )}

=0 Demikian pula untuk c2 ( 2 ) , c2 ( 3) , c2 ( 4 ) , dan c2 ( 5) . Sedangkan untuk menghitung entropi pada t=2 di setiap state, dihitung terlebih dahulu persamaan (5.14) lalu menghitung entropi di persamaan (5.15) yaitu Untuk state 1,

(

5

H 2 (1) = ∑ H1 ( i ) P S1 = i S 2 = 1, O 2 = o 2 i =1 5

)

) ( (

(

))

−∑ ⎡⎢ P S1 S 2 = 1, O 2 = o 2 .log P S1 S 2 = 1, O 2 = o 2 ⎤⎥ ⎦ i =1 ⎣ ⎡ ⎛ ⎞⎤ ⎢ ⎜ aij c1 ( i ) aij c1 ( i ) aij c1 ( i ) ⎟ ⎥ ⎟⎥ = ∑ H1 ( i ) 5 −∑⎢ 5 .log ⎜ 5 ⎜ ⎟⎥ i =1 i =1 ⎢ akj c1 ( k ) ∑ ⎜ ∑ akj c1 ( k ) ⎟ ⎥ ⎢ ∑ akj c1 ( k ) k =1 ⎝ k =1 ⎠⎦ ⎣ k =1 5

5

=0 Cara yang sama dipakai untuk state 2, 3, 4, dan 5 sehingga state (j)

c2(j)

H2(j)

state (j)

c3(j)

H3(j)

1

0

0

1

0

0

2

0,5

0

2

1/3

0

3

0

0

3

1/3

0

4

0,5

0

4

1/3

0

5

0

0

5

0

0

Tabel 5.3 : Tahap rekursi untuk t=2



55

state (j)

c4(j)

H4(j)

state (j)

c5(j)

H5(j)

1

0

0

1

0

0

2

0,4

1

2

0

2

3

0,4

1

3

0

2

4

0,2

0

4

0

0

5

0

0

5

1

0



Keempat tabel di atas dapat disederhanakan menjadi tabel 5.6. Sedangkan proses penghentian dari algoritma ini adalah

(

)

5

5

i =1

i =1

H S 5 O 5 = o5 = ∑ H 5 ( i ) c5 ( i ) − ∑ c5 ( i ) log ( c5 ( i ) )

Obs

O1=1

O2=2

O3=2

O4=2

O5=5

H1(1)=0

H2(1)=0

H3(1)=0

H4(1)=0

H5(1)=0

c1(1)=1

c2(1)=0

c3(1)=0

c4(1)=0

c5(1)=0

H1(2)=0

H2(2)=0

H3(2)=0

H4(2)=1

H5(2)=2

c1(2)=0

c2(2)=0,5

c3(2)=1/3

c4(2)=0.4

c5(2)=0

H1(3)=0

H2(3)=0

H3(3)=0

H4(3)=1

H5(3)=2

c1(3)=0

c2(3)=0

c3(3)=1/3

c4(3)=0,4

c5(3)=0

H1(4)=0

H2(4)=0

H3(4)=0

H4(4)=0

H5(4)=0

c1(4)=0

c2(4)=0,5

c3(4)=1/3

c4(4)=0,2

c5(4)=0

H1(5)=0

H2(5)=0

H3(5)=0

H4(5)=0

H5(5)=0

c1(5)=0

c2(5)=0

c3(5)=0

c4(5)=0

c5(5)=1

H1=0

H2=1

State 1

2

3

4

5

Entropi

H3=1,59

H4=2,32

Tabel 5.7 : Hasil Perhitungan Entropi

H5=0


56

Untuk menghitung entropi dalam MMT ini, dipakai basis 2. Lalu, dalam menjalankan iterasi diperlukan entropi total untuk setiap Ot=i, i=1,2,3.4.5. Untuk kasus ini, entropi total tersebut dicantumkan pada baris terakhir di tabel 5.6. Entropi total dari tiap langkah observasi ditampilkan pada baris terakhir dari tabel di atas, dengan mengambil 2 sebagai basis logartimanya. Sebagai contoh, setelah menerima observasi ke dua, terdapat dua kemungkinan barisan state yang menghasilkan o2=(1,2) yaitu s2=(1,2) dan s2=(1,4), masing-masing dengan peluang 0,5 sehingga entropi total observasi kedua adalah H2=1. Selanjutnya, setelah semua observaasi diterima, dapat dilihat bahwa barisan state yang mungkin untuk observasi di atas adalah s5=(1,4,4,4,5), karena tidak ada barisan lain yang menghasilkan o5. Oleh karena itu, barisan state tersebut mempunyai peluang 1 ketika t=5 dan entropi H5=0.

Contoh 5.2 Sebagai contoh lain, dimisalkan seseorang ingin memperkirakan keadaan cuaca dari perilaku ganggang laut (sumber: Applications of Hidden Markov Models (HMMs) to Computational Biology problems, dengan perbaikan)

Gambar 5.8 : Diagram transisi dan emisi pada contoh 5.2


57

Pada kasus ini, state yang terobservasi adalah keadaan dari ganggang laut, sedangkan state yang tersembunyi (hidden) adalah keadaan cuaca. Matriks peluang transisi, emisi, dan distribusi peluang awal dari keadaan ini direpresentasikan oleh

cuaca hari ini ⎛ cerah berawan hujan ⎞ ⎜ ⎟ cerah ⎜ 0,5 0,25 0,25 ⎟ cuaca kemarin berawan ⎜ 0,375 0,125 0,5 ⎟ ⎜ ⎟ hujan ⎝ 0,125 0,625 0,25 ⎠ ganggang laut ⎛ kering agak kering lembab basah ⎞ ⎜ ⎟ cerah ⎜ 0,60 0,20 0,15 0,05 ⎟ cuaca berawan ⎜ 0,25 0,25 0,25 0,25 ⎟ ⎜ ⎟ hujan ⎝ 0,05 0,10 0,35 0,50 ⎠

π=

cerah berawan hujan 0 0 ) ( 1, 0

Kemudian ingin dicari barisan cuaca yang paling optimal yang terjadi, maka dengan menggunakan algoritma untuk mencari entropi yang telah dijelaskan di atas, diperoleh

Obs

O1=1

O2=2

O3=3

O4=2

O5=4

State 1

2

3

H1(1)=0

H2(1)=0

H3(1)=0

H4(1)=0

H5(1)=0

C1(1)= 0,66667

C2(1)= 0,51918

C3(1)=0,2573

C4(1)= 0,35832

C51)= 0,0729

H1(2)=0

H2(2)=0

H3(2)=0

H4(2)=0

H5(2)=0

C1(2)= 0,13889

C2(2)= 0,31964

C3(2)= 0,24703

C4(2)= 0,44448

C5(2)= 0,2158

H1(3)=0

H2(3)=0

H3(3)=0

H4(3)=0

H5(3)=0

C1(3)= 0,01852

C2(3)= 0,16118

C3(3)= 0,49567

C4(3)= 0,1972

C5(3)= 0,7113

Tabel 5.9 : Perhitungan entropi untuk contoh cuaca


58

Dari tabel 5.2 dapat diambil kesimpulan sementara bahwa barisan yang optimal dari Model Markov Tersembunyi di atas adalah s=(1,1,3,2,3). Akan tetapi perlu untuk didalami lebih lanjut serta perbandingannya dengan algoritma Viterbi yang telah dikenal dalam menyelesaikan permasalahan ini.

BAB 5 ENTROPI PADA MATRIKS EMISI MODEL MARKOV TERSEMBUNYI

Recommend Documents