Markov Chain

Sebelum mendefinisikan HMM, perlu dibahas terlebih dulu mengenai Markov Chain. Markov Chain merupakan perluasan dari finite automaton. Finite automaton sendiri adalah kumpulan state yang transisi antar state-nya dilakukan berdasarkan masukan observasi. Pada Markov Chain, setiap busur antar state berisi probabilitas yang mengindikasikan kemungkinan jalur tersebut akan diambil. Jumlah probabilitas semua busur yang keluar dari sebuah simpul adalah satu.

Markov Chain bermanfaat untuk menghitung probabilitas urutan kejadian yang dapat diamati. Masalahnya, terkadang ada urutan kejadian yang ingin diketahui tetapi tidak dapat diamati. Contohnya pada kasus part-of-speech tagging (POS tagging). POS tagging adalah pemberian tag kepada kata: kata benda, kata kerja, kata sifat dan lainlain. Pada POS tagging, urutan tag tidak dapat diamati secara langsung. Pengamatan secara langsung hanya dapat dilakukan terhadap urutan kata. Dari urutan kata tersebut harus dicari urutan tag yang paling tepat. Untuk contoh ini, tag adalah bagian yang tersembunyi.

Hidden Markov Model

Dalam HMM, bagian yang dapat diamati disebut observed state sedangkan bagian yang tersembunyi disebut hidden state. HMM memungkinkan pemodelan sistem yang mengandung observed state dan hidden state yang saling terkait. Pada kasus POS tagging, observed state adalah urutan kata sedangkan hidden state adalah urutan tag. Selain itu, HMM dapat digunakan dalam pengenalan suara, parsing/chunking, ekstraksi informasi, dan peringkasan teks.

Menurut Rabiner [RAB89], salah satu masalah yang dapat diselesaikan oleh HMM adalah masalah optimasi urutan hidden state berdasarkan urutan kejadian yang dapat diamati. Urutan hidden state optimal adalah urutan yang paling tepat yang “menjelaskan” kejadian yang dapat diamati. Masalah ini disebut juga masalah decoding.