### 8.6 Proses Training Hidden Markov Model

_Hidden Markov Model_  (HMM) adalah salah satu varian _supervised learning_,^7
diberikan sekuens _input_ dan _output_ yang bersesuaian sebagai _training data_.
Pada kasus POS _tagging_, yaitu _input_ -nya adalah sekuens kata dan _output_ -nya
adalah sekuens kelas kata (masing-masing kata/ _token_ berkorespondensi dengan
kelas kata). Saat melatih HMM, kita ingin mengestimasi parameterAdan
byaitu _transition probabilities_ dan _emission probabilities_ /lexical- _generation_
probabilities(ingat kembali definisi HMM secara formal pada subbab 8.4).
Kita melatih HMM dengan menggunakanAlgoritma Forward-Backward
(Baum-Welch Algorithm).
Cara paling sederhana untuk menghitung emission probabilities atau
_transition probabilities_ adalah dengan menghitung kemunculan pada sampel
( _training data_ ). Sebagai contoh, _emission probability_ suatu kata untuk setiap
kelas kata diberikan pada persamaan 8.14, dimanaN melambangkan
banyaknya kemunculan katawiterlepas dari kelasnya.

```
P(wi|ci) =
```
```
count(wi,ci)
∑N
j=1count(wi,cj)
```
#### (8.14)

Akan tetapi, perhitungan tersebut mengasumsikan _context-independent_, artinya
tidak mempedulikan keseluruhan sekuens. Estimasi lebih baik adalah dengan
menghitung seberapa mungkin suatu kategoricipada posisi tertentu (indeks
kata/ _token_ pada kalimat) pada semua kemungkinan sekuens, diberikan inputw
1 ,w 2 ,...,wT. Kami ambil contoh, kata _flies_ sebagai _noun_ pada kalimat
“ _The flies like flowers_ ”, dihitung sebagai penjumlahan seluruh sekuens yang
berakhir dengan _flies_ sebagai _noun_. ProbabilitasP( _flies_ /N|The flies) =
P( _flies_ /N&The flies)
P(The flies).
Agar lebih _precise_, secara formal, kita definisikan terlebih dahulu _forward_
probabilitysebagai 8.15, dimanaαi(t) adalah probabilitas untuk menghasilkan
kataw 1 ,w 2 ,...,wtdenganwtdihasilkan ( _emitted_ ) olehci.

```
αi(t) =P(wt/ci|w 1 ,w 2 ,...,wt) (8.15)
```
_Pseudo-code_ perhitungan kemunculan kelascisebagai kategori pada posisi
tertentu diberikan oleh Gambar 8.11, denganciadalah kelas kata ke-idanwi
adalah kata ke-i,aadalah _transition probability_,badalah _emission probability_,
danSmelambangkan banyaknya _states_.
Sekarang, kita definisikan juga _backward probability_ βi(t), yaitu probabilitas
untuk menghasilkan sekuenswt,...,wTdimulai dari _state_ wt/ci(ci
menghasilkanwt). Hal ini serupa dengan _forward probability_, tetapi _backward_
probabilitydihitung dari posisi ke-tsampai ujung akhir (tkeT). Anda dapat
melihat _pseudo-code_ pada Gambar 8.12, denganaadalah _transition probability_
danbadalah _emission probability_.

(^7) Walaupun ia termasuk _generative model_.tetapi komponen utama yang di _model_ kan
adalahp(y|x)


114 8 Hidden Markov Model

Initialization Step
fori= 1toSdo
αi(t)←bi(o 1 )×a 0 ,i

Comparing the Forward Probabilities
fort= 2toTdo
fori= 1toSdo
αi(t)←

```
∑S
j=1(aji×αj(t−1))×bi(ot)
```
```
Gambar 8.11: Algoritma _forward_ [38].
```
Initialization Step
fori= 1toSdo
βi(T)←P(ci) # as _sign_ ed using a particular classci

Comparing the Backward Probabilities
fort=T− 1 totdo
fori= 1toSdo
βi(t)←

```
∑S
j=1(aji×βi(t+ 1))×bj(oj+1)
```
```
Gambar 8.12: Algoritma _backward_ [38].
```
Gabungan _forward_ dan _backward probability_ dapat digunakan untuk mengestimasiγj(t)
yaitu probabilitas berada pada _state_ cjpada waktu ke-tdengan
persamaan 8.16.

```
γj(t) =
αi(t)×βi(t)
∑S
j=1αj(t)×βj(t)
```
#### (8.16)

Kita mengestimasi probabilitas keberadaan pada _state_ tertentu, berdasarkan
pengaruh probabilitas keseluruhan sekuens.
Dengan menggunakan _forward probability_ dan _backward probability_ sekaligus,
kita definisikanξt(i,j) yaitu probabilitas berada di _state-i_ pada waktu
ketdan _state_ -jpada waktu ke-(t+ 1) dengan persamaan 8.17.

```
ξt(i,j) =
αi(t)×aij×bj(ot+1)×βj(t+ 1))
αS(T)
```
#### (8.17)

Denganaijadalah _transition probability_ danbj(ot+1) adalah _emission probability_ (ingat
kembali definisi formal HMM pada subbab 8.4). Pada setiap iterasi,
kita ingin memperbaharui kembali parameter HMM yaituAdanb. Kita
hitung kembali _transition probability_ (nilai yang lama di- _update_ ), diberikan
oleh persamaan 8.18.


```
8.6 Proses Training Hidden Markov Model 115
```
```
aij′=
```
#### ∑T− 1

```
∑ t=1 ξt(i,j)
T− 1
t=1
```
#### ∑S

```
j=1ξt(i,j)
```
#### (8.18)

Kita juga menghitung kembali _emission probability_ (nilai yang lama di _update_ ),
diberikan oleh persamaan 8.19.

```
bj(ok)′=
```
#### ∑T

```
t=1,ok=wkγj(t)
∑T
t=1γj(t)
```
#### (8.19)

#### ∑T

```
t=1,ok=wkberarti jumlah observasiwkpada waktut.
```
Initialize A and b
Ite _rate_ until convergence
E-step
γj(t) =∑Sαi(t)×βi(t)
j=1αj(t)×βj(t)

```
ξt(i,j) =
αi(t)×aij×bj(ot+1)×βj(t+1))
αS(T)
```
```
M-step
_update_ aij′=
```
```
∑T− 1
∑T− 1 t=1ξt(i,j)
t=1
```
```
∑S
j=1ξt(i,j)
```
```
_update_ bj(ok)′=
```
```
∑T
t=1∑,ok=wkγj(t)
Tt=1γj(t)
```
```
Gambar 8.13: Algoritma _forward-backward_ (EM) [12].
```
Keseluruhan proses ini adalah cara melatih HMM dengan menggunakan
kerangka berpikir _Expectation Maximization_ : terdiri dariE-stepdanMstep[12].
Pada E-step, kita mengestimasi probabilitas berada di suatu _state_
cjmenggunakanγj(t) dan mengestimasi transisiξt(i,j) berdasarkan parameterAdanbyang
sudah diberikan pada tahap iterasi _training_ ( _epoch_ ) sebelumnya.
Pada M-step, kita menggunakanγdanξuntuk mengestimasi kembali
parameterAdanb. Hal ini dijelaskan secara formal pada Gambar 8.13.
Walaupun HMM menggunakan _independence assumption_, tetapi kita dapat
mengikutsertakanpengaruh probabilitas keseluruhan sekuens untuk
perhitungan probabilitas keberadaan kita pada suatu _state_ ipada
saat ( _time_ t) tertentu. Metode ini dapat dianggap sebagai suatu cara optimalisasi
menggunakan _smoothing_ ^8 terhadap nilai parameter (Adanb). Kita
mencapai titik _local optimal_ apabila tidak ada perubahan parameter.

(^8) https://en.wikipedia.org/wiki/Smoothing


116 8 Hidden Markov Model

Kami ingin mengakui bahwa penjelasan pada subbab 8.6 mungkin kurang
baik (kurang memuaskan). Kami harap kamu mencari referensi lain yang lebih
baik untuk subbab ini.

