Markov Chain

24 06 2008

Markov chain merupakan sub ilmu dari Data Mining dan Soft Computing.

Markov chain adalah suatu proses random (proses stochastic) dengan Markov Property dimana dengan keadaan saat ini, keadaan yang akan datang bersifat independent terhadap keadaan yang lampau. Property ini dapat dirumuskan sebagai berikut:

P(q_(n+1) = S_j | q_n = S_i, … , q_1 = S_k) = P(q_(n+1) = S_j | q_n = S_i)

dimana nilai yang memungkinkan dari S_i adalah suatu set S yang terbatas yang sering disebut sebagai state space. Probability di atas umumnya disebut dengan nama state transition probability yang sering dilambangkan dengan simbol a_ij dimana nilai a_ij lebih dari atau sama dengan 0 dan total nilai a_ij untuk semua j sama dengan 1.0.

Untuk melakukan estimasi terhadap nilai probabilitas dapat dilakukan dengan melaksanakan training terhadap data (sequence) yang ada dan melihat tingkat kemunculan nilai state yang satu berubah menjadi nilai state yang lain. Misalnya untuk data sequence seperti di bawah ini:

1 2 2 1 2 3 2 3 3 2 3 1

Maka nilai probabilitas dari suatu nilai berubah menjadi nilai yang lain adalah sebagai berikut:

1 2 3
1 0.00 1.00 0.00
2 0.20 0.20 0.60
3 0.25 0.50 0.25

Markov chain dikatakan memiliki order m apabila keadaan saat ini yang menentukan keadaan yang akan datang terdiri dari keadaan sebanyak m ke belakang. Hal ini dapat dirumuskan sebagai berikut:

P(X_(n+1) = x | X_n = x_n, … , X_1 = x_1) =
P(X_(n+1) = x | X_n = x_n, X_(n-1) = x_(n-1), …, X_(n-m) = x_(n-m))

Model Markov chain untuk data sequence continuous (bukan categorical seperti di atas) didapat dengan mengasumsikan bahwa nilai probabilitas dari satu nilai observasi ke observasi lainnya berbentuk distribusi continuous (umumnya Gaussian) dan menganggap distribusi probabilitas dari setiap nilai observasi merupakan penjumlahan berproporsi atau mixture modelling.

Referensi:
Rabiner L. R. (1999). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of The IEEE, Vol. 77, No 2, pp. 257 – 286.


Actions

Information

6 responses

14 08 2014
adek

ini kan buat matrik transisinya?? kalau matrik emisinya gimana ya cara mencarinya??

30 03 2009
Yudi Agusta

Sdr/i Swamp, tentu saja bisa untuk diskusi. Saya sendiri belum pernah melakukan riset speech to text.

27 02 2009
swamp

terima kasih infonya…sekarang saya sedang mencoba riset speech to text dalam Bahasa Indonesia…bisa minta bantuan?

26 02 2014
Yudi Agusta

Bisa, tentunya sebisa saya ya

13 03 2014
swamp

wah, setelah beberapa tahun! ;D
kebetulan dulu saya cari info ini untuk skripsi… tapi akhirnya nggak jadi pakai hidden markov, hehe. terima kasih😉

25 07 2008
mwaaa « move on..

[…] matriks transision probability (mpt), nah matriks ini bisa dsebut intiny markov chain, lbh jelasny ini. Selanjutnya itu dilakukan perhitungan similarity content, trs dtuangkan k dalam matriks […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: