Markov Chain

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.