### 8.5 Algoritma Viterbi

Pada subbab sebelumnya, telah didefinisikan permasalahan POS _tagging_ dan
_Hidden Markov Model_ untuk menyelesaikan permasalahan tersebut. Pada bab
ini, kamu akan mempelajari cara mencari sekuens _syntactical categories_ terbaik
diberikan suatu observasi kalimat menggunakanalgoritma Viterbi. Hal
ini disebut proses _decoding_ pada HMM. Algoritma Viterbi adalah salah satu
algoritma _dynamic programming_ yang prinsip kerjanya mirip denganminimum
edit distance.^6 Ide utama algoritma Viterbi adalah mengingat sekuens
untuk setiap posisi tertentu (setiap iterasi, setiap panjang kalimat). Apabila
kita telah sampai pada kata terakhir, kita lakukan _backtrace_ untuk mendapatkan
sekuens terbaik.

_function_ VITERBI( _observations_ of lenT, _state-graphs_ of lenS)

```
Initialization Step
create a path of probability matrix viterbi[S,T]
foreach statesfrom 1 toSdo
viterbi[s,1]←a 0 ,s×bs(o 1 )
_backpointer_ [s,1]← 0
```
```
Ite _ratio_ n Step
foreach time steptfrom 2 toTdo
foreach statesfrom 1 toSdo
viterbi[s,t]←arg maxj=1,Sviterbi[j,t−1]×as,j×bs(ot)
_backpointer_ [s,t]←index ofjthat gave the max above
```
```
Sequence Identification Step
cT←ithat maximizes viterbi[i,T]
fori=T− 1 to 1 do
ci← _backpointer_ [ci+1,i+ 1]
```
```
Gambar 8.8: Algoritma Viterbi [12, 38].
```
Perhatikan Gambar 8.8 yang menunjukkan _pseudo-code_ untuk algoritma
Viterbi. Variabelcberarti kelas kata,aadalah _transition probability_, danb
adalah _lexical-generation probability_. Pertama-tama, algoritma tersebut membuat
suatu matriks berukuranSxTdenganSadalah banyaknya _states_ (tidak

(^6) https://en.wikipedia.org/wiki/Edit_distance


112 8 Hidden Markov Model

_term_ asuk _start state_ ) danT( _time_ ) adalah panjang sekuens. Pada setiap iterasi,
kita pindah ke observasi kata lainnya. Gambar 8.9 adalah ilustrasi algoritma
Viterbi untuk kalimat _input_ ( _observed sequence_ ) “ _flies like a flower_ ”
dengan _lexical generation probability_ pada Tabel 8.3 dan _transition probabilities_ pada
Tabel 8.2 (bigram) [38]. Panah berwarna merah melambangkan
_backpointer_ yaitu _state_ mana yang memberikan nilai tertinggi untuk ekspansi
ke _state_ berikutnya. Setelah _iteration step_ selesai, kita lakukan _backtrace_ terhadap _state_ terakhir
yang memiliki nilai probabilitas tertinggi dan mendapat
hasil seperti pada Gambar 8.10. Dengan itu, kita mendapatkan sekuens
“ _flies_ /N like/V a/ART flower/N”.

Gambar 8.9: Ilustrasi algoritma Viterbi per iterasi. Panah berwarna merah
melambangkan _backpointer_ – _state_ mana yang memberikan nilai tertinggi untuk
ekspansi.

```
Gambar 8.10: Viterbi _backtrace_.
```
Apabila kamu hanya ingin mengetahui HMM tanpa variabel yang perlu
dilatih/diestimasi, kamu dapat berhenti membaca sampai subbab ini. Apabila
kamu ingin mengetahui bagaimana HMM dapat mengestimasi parameter,
kamu dapat melanjutkan membaca subbab berikutnya.


```
8.6 Proses Training Hidden Markov Model 113
```
