### 8.4 Hidden Markov Model Tagger

Pada subbab sebelumnya, POS _tagging_ telah didefinisikan secara matematis.
Kita sudah mengetahui permasalahan yang ingin kita selesaikan. Subbab ini
adalah formalisasi _hidden markov model tagger_.
Ingat kembali persamaan 8.12 untuk POS tagging.P(wi|ci) disebut _likelihood_ danP(ci|ci−
1 ) disebut _prior_, _multiplication of probabilities_ (

#### ∏

) melambangkanmarkov
chain. _Markov chain_ adalah kasus spesial _weighted automaton_ ^5
yang mana sekuens _input_ menentukan _states_ yang akan dilewati
oleh automaton. Sederhananya, automaton mencapai _goal state_ setelah mengunjungi
berbagai _states_. Total bobot _outgoing edges_ untuk masing-masing
_state_ pada automaton haruslah bernilai satu apabila dijumlahkan. Kasus spesial
yang dimaksud adalah _emission_ (dijelaskan kemudian).
Sebagai contoh, perhatikan Tabel 8.2.ARTadalah _article_,Nadalah _noun_,
V adalah _verb_ danP adalah _preposition_. Mereka adalah contoh kelas kata
yang disederhanakan demi membuat contoh yang mudah. Tabel 8.2 yang
merepresentasikan probabilitas transisi kelas kata, ketika dikonversi menjadi
_weighted automaton_, akan menjadi Gambar 8.5.

```
NULL
```
```
ART V
```
```
N P
```
```
START
```
```
0.71
```
```
0.29
```
```
1
```
```
0.65
```
```
0.43
0.35
```
```
0.26
```
```
0.44
0.13
```
```
0.74
```
```
Gambar 8.5:Weighted automaton[38].
```
(^5) Kami berasumsi kamu sudah mempelajari automata sebelum membaca buku ini.


```
8.4 Hidden Markov Model Tagger 109
```
```
Bigram Estimate
P(ART|null) 0.71
P(N|null) 0.29
P(N|ART) 1
P(V|N) 0.43
P(N|N) 0.13
P(P|N) 0.44
P(N|V) 0.35
P(ART|V) 0.65
P(ART|P) 0.74
P(N|P) 0.26
```
```
Tabel 8.2: Probabilitas bigram [38].
```
Tabel 8.2 dan Gambar 8.5 telah merepresentasikan probabilitas _prior_,
sekarang kita ingin model yang kita punya juga mencakuplexical emission
probabilities, yaitu _likelihood_ pada persamaan 8.12.

```
P(the|ART) 0.54 P(a|ART) 0.360
P( _flies_ |N) 0.025 P(a|N) 0.001
P( _flies_ |V) 0.076 P(flower|N) 0.063
P(like|V) 0.1 P(flower|V) 0.05
P(like|P) 0.068 P(birds|N) 0.076
P(like|N) 0.012
```
Tabel 8.3:Lexical emission probabilities[38]. Tabel ini hanya memuat informasi
yang dibutuhkan untuk ilustrasi cerita (penyederhanaan).

Seumpama kita mempunyai _lexical emission probabilities_ seperti pada
Tabel 8.3. Setiap _state_ pada automaton, dapat menghasilkan/meng- _output_ kan
suatu kata ( _word_ ) dengan probabilitas pada Tabel 8.3. Kita kembangkan
lagi Gambar 8.5 dengan tambahan informasi _lexical emission probabilities_
menjadi Gambar 8.6. Automaton ini disebut _hidden markov model_ (HMM).
Kata _hidden_ berarti, untuk setiap kata pada sekuens, kita tidak mengetahui
kata tersebut dihasilkan oleh _state_ mana secara model (baru diketahui saat
_running_ ). Misalkan, kata _flies_ dapat dihasilkan oleh _state_ N( _noun_ ) atauV
( _verb_ ) [38].
Diberikan kalimat “ _flies like a flower_ ”, untuk menghitung sekuens kelas
kata untuk kalimat tersebut, kita menyelusuri automaton Gambar 8.6. Hasil
penelusuran memberikan kita kombinasi sekuens yang mungkin seperti pada
Gambar 8.7. Pekerjaan berikutnya adalah, dari seluruh kombinasi sekuens
yang mungkin, yaitu

#### ∏T

```
i=1P(wi|ci)P(ci|ci−^1 ). Bagaimana cara kita menen-
```

110 8 Hidden Markov Model

```
NULL
```
```
ART V
```
```
N P
```
```
START
```
```
0.71
```
```
0.29
```
```
1
```
```
0.65
```
```
0.43
0.35
```
```
0.26
```
```
0.44
0.13
```
```
0.74
```
```
P(the|ART)	=	0.54
P(a|ART)	 =	0.360
```
```
P( _flies_ |V) =	0.76
P(flower|V)=	0.05
P(like|V) =	0.1
```
```
P(P( _flies_ |Na|N) ) =	0.25=	0.001 P(like|P) =	0.068
P(flower|N)=	0.063
P(like|N) =	0.012
P(birds|N) =	0.076
```
```
Gambar 8.6: _Hidden Markov Model_.
```
```
Gambar 8.7: Sekuens yang mungkin ( _brute force_ ).
```
tukan sekuens terbaik (paling optimal), yaitu sekuens dengan probabilitas
tertinggi, diberikan pada subbab berikutnya.
Secara formal, _hidden markov model tagger_ didefinisikan oleh beberapa
komponen [12]:

```
1.Q={q 1 ,q 2 ,...,qS}yaitu himpunan _states_ ;Smenunjukkan banyaknya
_states_.
2.A=a 0 , 0 ,a 1 , 1 ,a 2 , 2 ,...,aS,Syaitu _transition probability_ matrixdari
suatu _state_ imenuju _state_ j; dimana
```
#### ∑S

```
j=0ai,j= 1. Indeks 0 merepresentasikanstart
_state_ ( _null state_ ).Smelambangkan banyaknya _states_.
3.o=o 1 ,o 2 ,...,oTyaitu sekuensobservasi(kata/ _input_ );Tadalah panjang
_input_.
4.b=bi(ow) yaitu sekuens dari _observation likelihood_, atau disebut dengan _emission_
probabilities, merepresentasikan sebuah observasi kataow
dihasilkan oleh suatu _state-i_.
```

```
8.5 Algoritma Viterbi 111
```
```
5.q 0 ,qFyaitu kumpulan _states_ pesial yang terdiri dari _start state_ danfinal
_state_ (s).
```
