Toya Bungkah – Danau Batur

Petunjuk menuju Toya Bungkah ada di bagian bawah tulisan ini.

Akhir minggu kemarin, kami sekeluarga meluangkan waktu untuk menginap di tempat camping Toya Davasya, yang terletak di antara Gunung Batur dan Danau Batur. Kami memilih tempat itu karena Toya Davasya merupakan tempat yang sangat nyaman, luas dan mempunyai beberapa fasilitas yang sangat bagus untuk bisa meluangkan waktu dengan nyaman dan santai. Fasilitas yang disediakan oleh resort tersebut adalah camping ground lengkap dengan fasilitas api unggun, tenda yang bisa disewa, kolam renang yang berukuran besar serta kolam air panas, yang airnya sendiri diambil dari sumber air panas Toya Bungkah.

Toya Bungkah sendiri terletak di Kabupaten Bangli, dan untuk mencapai tempat itu kita harus pergi ke Penelokan, Kintamani, tempat dimana biasanya para wisatawan biasanya berkunjung untuk melihat pemandangan Gunung Batur dan Danau Batur dari ketinggian. Dari Penelokan tersebut kita harus turun ke arah Danau Batur, dan Toya Bungkah sendiri terletak tepat di antara Gunung Batur dan Danau Batur.

Kami sampai di sana pukul 12 siang pada tanggal 28 Juni 2008. Sampai di sana, kami check in, sambil menunggu pemasangan tenda yang disediakan oleh pihak resort. Sambil menunggu pemasangan tenda dan karena Aya n Kiya sudah tidak sabar untuk bermain di kolam renang, kami akhirnya mempersiapkan diri untuk mandi kolam air panas yang tersedia di resort tersebut. Setelah tenda siap, kami membawa berbagai perlengkapan kami dan menyimpannya di dalam tenda. Setelah itu, langsunglah kami menuju kolam renang untuk menikmati air panas Toya Bungkah yang disediakan resort tersebut.

Waktu yang kami luangkan di sana memang sebagian besar kami isi dengan berenang di kolam renang yang berukuran olimpic yang mereka miliki dan berendam air panas. Kami berada di kolam renang tersebut hampir 6 jam dari 24 jam yang kami spent di sana. Yang mengenakkan, kami bisa berolah raga renang dan kami bisa merelax-kan badan kami di kolam air panas.

Selain kegiatan tersebut, kami juga ber-happy birthday untuk mum, memainkan musik dari pianica dan biola yang dibawa Aya n Kiya, kami juga menikmati bersantai di bawah langit biru sambil memandang air danau yang kelihatan sangat luas.

Malam harinya, kami bersiap-siap untuk makan malam, yang disediakan di camping ground dengan api unggun yang dihidupkan khusus untuk kami yang menginap untuk menghangatkan suasana yang sedikit mulai dingin malam itu. Malam itu juga, Aya n Kiya, mempertunjukkan kebolehan mereka sekali lagi untuk memainkan pianica dan biola, mamanya yang sedikit riang malam itu berdansa ke sana ke mari diiringi permainan musik mereka.

Setelah selesai makan malam dan bermusik, kami mempersiapkan diri untuk tidur, sambil tidak lupa story telling buat Aya n Kiya sebelum tidur. Suasana di dalam tenda cukup nyaman dan luas untuk kita berempat. Mungkin kalau bisa dicatat sedikit kekurangannya adalah matras yang dipakai untuk tidur tidak cukup empuk untuk menahan berat badan kami, sehingga kami yang biasanya tidur di spring bed harus merasakan ketidak nyamanan akibat kurang pasnya matras tempat tidur. Yang lain yang terjadi juga saat kami tidur bermalam di sana, udara malam hari khususnya setelah lewat tengah malam, terasa dingin sekali. Kami berempat bergantian terbangun karena selimut kami sedikit terlepas dari badan kami. Secara bergantian, kami juga pulang pergi ke toilet karena tidak kuat menahan kencing. Pada saat pulang pergi toilet tersebut, kami juga melihat bagaimana air kolam renang mengeluarkan asap menguap karena mungkin udara di atasnya jauh lebih dingin dari air di kolam tersebut. Padahal air kolam renang berukuran olimpic jauh lebih dingin dari air air panas.

Besoknya setelah bangun, kami menyantap makan pagi yang disediakan pihak resort dan seperti yang telah sedikit diceritakan di atas, kami kembali ke kolam renang untuk berenang dan berendam air panas. Ada yang lucu dari perjalanan kami ini. Sebagai persiapan camping, kami membawa begitu banyak perlengkapan untuk dipermainkan di sana, mulai dari board game, buku bacaan yang jumlahnya seabrek, game boy untuk Aya n Kiya, layang-layang yang rencanakan kami terbangkan, pianica dan biola, dan lain-lain. Ternyata, dari sekian banyak permainan yang kami siapkan, hanya sebagian kecil yang bisa kami laksanakan. Bahkan Game Boy yang biasanya menjadi peneman waktu luangnya Aya n Kiya, tidak tersentuh sama sekali.

Direction: Untuk mencapai Toya Bungkah, anda perlu untuk berkendaraan dari Denpasar menuju daerah Kintamani, Bangli. Setelah sampai di Penelokan, Kintamani, Bangli, cari jalan turun ke Danau Batur. Ikuti jalan turun tersebut sampai bertemu pertigaan, dan belok ke kiri di pertigaan tersebut. Setelah melewati jalan yang dikelilingi batu lava kering karena letusan Gunung Batur, yang cukup panjang, anda akan sampai di Desa Toya Bungkah, dan Toya Davasya, saat ini adalah satu-satunya resort yang menyediakan fasilitas kolam renang dan kolam air panas. Letak absolut Toya Bungkah dapat dilihat dengan membuka peta Pulau Bali melalui thumbnail peta di samping. Letak daerah tersebut tersebut ditandai dengan angka nomor [5]

Mum’s Birthday

Tanggal 28 Juni ini, ulang tahun mamanya anak-anak. Mum tepatnya berumur 3X tahun (he he he … maunya sih disembunyikan, tapi di birthday cakenya tertulis dengan jelas rupanya). Kebetulan hari tersebut jatuh pada hari Sabtu dan juga masa liburan sekolah Aya n Kiya, akhirnya kami memutuskan untuk merayakan hari ulang tahun mum sambil melakukan camping di Toya Bungkah. Berikut ini beberapa foto kami saat ber-Happy Birthday dan memotong kue kecil yang kami bawa ke tempat camping. Happy Birthday Mum, Love You, From: Dad, Aya n Kiya.

PS: Kalau mau tahu tentang tempat camping Toya Devasya tempat kami melakukan camping di Toya Bungkah, baca posting saya yang selanjutnya.

Hidden Markov Models

Hidden Markov Models merupakan sub ilmu dari Data Mining dan Soft Computing.

Hidden Markov Models adalah perkembangan dari Markov Chain dimana keadaan yang akan datang dari suatu sequence tidak hanya ditentukan oleh keadaan saat ini, tetapi juga perpindahan dari suatu state sequence ke state sequence yang lain. State sequence inilah yang merupakan bagian hidden dari suatu hidden markov models.

Salah satu contoh dari Hidden Markov ini adalah coin tossing. Dari sequence yang ada untuk pelaksanaan coin tossing, kita hanya tahu hasilnya adalah head and tail. Tetapi mengenai berapa coin yang digunakan dan bagaimana jenis coin yang digunakan tersebut kita tidak mengetahuinya.

Dari keterangan di atas, maka elemen dari sebuah HMM adalah:
1. N, jumlah state yang ada
2. M, jumlah nilai kemungkinan (observation symbols) yang ada
3. A = {a_ij}, state transition probability distribution matrix
4. B = {b_j (k)}, observation symbols probability distribution matrix
5. PI = {pi_i}, initial state distribution
6. O = {O_i}, observasi
7. Q = {q_i}, state sequence
8. S = {S_i}, nilai state

Tiga permasalahan yang ada dalam HMM adalah:
1. Bagaimana menghitung secara efisien nilai probability dari sebuah observasi sequence setelah model diketahui?
2. Bagaimana memilih state sequence yang optimal?
3. Bagaimana melakukan adjustment terhadap parameter dari HMM sehingga bisa memaksimalkan likelihood dari model?

Solusi Permasalahan 1
Nilai probabilitas atas dasar model yang diberikan dapat dihitung dengan menjumlahkan joint probabilitas dari semua kemungkinan state sequence q yang memungkinkan seperti di bawah ini

P(O|lambda) = SUM (all Q) P(O|Q,lambda) P(Q|lambda)
= SUM (q_1,q_2,…,q_T) PI_{q1}b_{q1}(O_1)a_{q1q2}b_{q2}(O_2)…a_{q(t-1)qT}(O_t)

Penghitungan nilai probabilitas ini dapat dilakukan dengan menggunakan Forward-Backward Procedure. Untuk forward procedure dapat memanfaatkan forward variabel alpha_t(i) yang didefinisikan sebagai:

alpha_t(i) = P(O_1 O_2 … O_t, qt = Si|lambda)

yang merupakan probabilitas dari sebagian sequence observasi, O1O2…Ot (sampai waktu t) dan state Si pada waktu t, berdasarkan pada model lambda. Permasalahan ini dapat dipecahkan secara inductive sebagai berikut:
1. Initialisasi: alpha_t(i) = Pi_i b_i (O_i), 1 less than i less than N
2. Induksi:alpha_t+1(j)=[Sum(i=1 to N) alpha_t(i) a_ij] b_j (O_t+1), 1 less than t less than T-1, 1 less than j less than N
3. Terminasi: P(O|lambda) = SUM (i=1 to N) alpha_t(i)

Untuk backward, sebenarnya mempunyai fungsi yang hampir sama dengan forward procedure. Akan tetapi, karena backward varibel akan digunakan untuk memecahkan permasalahan 3, maka di sini akan diperkenalkan pemecahan permasalahan 1 dengan backward procedure.

Backward variabel didefinisikan sebagai:

beta_t(i) = P(O_t+1 O_t+2 … O_T|qt = Si, lambda)

yang merupakan probabilitas dari sebagian sequence observasi, O_t+1 (sampai terakhir) dan state Si pada waktu t, berdasarkan pada model lambda. Permasalahan ini dapat dipecahkan secara inductive sebagai berikut:
1. Initialisasi: beta_t(i) = 1, 1 less than i less than N
2. Induksi:beta_t(j)= Sum(i=1 to N) a_ij] b_j (O_t+1) beta_t+1(j), t=T-1,T-2,…,1, 1 less than j less than N

Solusi Permasalahan 2
Dalam memecahkan permasalahan kedua ini, suatu variabel gamma_t(i) yang merupakan probabilitas untuk berada pada state S_i dengan diberikan sequence observasi O dan model lambda pada waktu t, dan dirumuskan sebagai berikut:

gamma_t(i) = P(q_i=S_i|O, lambda)

Rumus ini dapat diekpresikan dengan forward-backward variabel sebagai berikut:

gamma_t(i) = alpha_t(i) x beta_t(i) / P(O|lambda)
= alpha_t(i) x beta_t(i) / (SUM (j=1 to N) alpha_t(j) x beta_t(j)

Untuk mendapatkan solusi permasalahan kedua dapat dilakukan dengan memilih nilai observasi yang mempunyai nilai gamma_t(i) tertinggi. Tetapi hal ini mempunyai permasalahan, apabila sequence seharusnya berpindah dari suatu state ke state yang lain, karena ada kemungkinan untuk state selanjutnya nilai observasi yang bersangkutan mempunyai probabilitas untuk muncul sama dengan 0.0. Salah satu solusi untuk mengatasi ini adalah dengan memikirkan tidak hanya satu sequence ke depan, tetapi beberapa sequence. Salah satu algoritma yang digunakan untuk mencari probabilitas tertinggi untuk kemungkinan munculnya deretan sequence tambahan dari sequence yang sudah ada adalah Viterbi Algorithm.

Dalam algoritma ini, kita harus menghitung suatu variabel delta_t(i) yang merupakan probabilitas tertinggi yang dimiliki oleh suatu sequence dengan panjang t setelah diberikan observasi sequence sepanjang t dan dapat dirumuskan menjadi:

delta_t(i) = max (q1 … qt) P[q1q2...qt,O1O2...Ot|lambda]

Dengan sistem induksi kita bisa mendapatkan sequence dengan probability tertinggi sebagai berikut:
1. Initialisasi: delta_t(i) = PI_i b_i(O_i), 1 less than i less than N dan psi_1(i) = 0
2. Recursion: delta_t(j) max (1 less than i less than N) [delta_t-1(i)a_ij]b_j(Ot), 2 less than t less than T, 1 less than j less than N dan psi_t(j) = argmax (1 less than i less then N) [delta_t-1(i)a_ij], 2 less than t less than T, 1 less than j less than N
3. Termination: P* = max (1 less than i less than N) [delta_t(i)] dan q_T^* = argmax (1 less than i less than N) [delta_t(i)]
4. Path (state sequence) backtracking: q_t^* = psi_t+1 (q_t+1^*), t=T-1,T-2,…,1

dimana psi_t(j) merupakan array yang menyimpan state sequence dengan probabilitas tertinggi.

Solusi Permasalahan 3
Untuk melaksanakan proses update dan reestimation dari parameter HMM, kita perlu untuk mendefinisikan suatu variabel epsilon_t(i,j) yang merupakan probabilitas untuk berada pada state S_i pada waktu t dan di state S_j pada waktu t+1 dan dirumuskan sebagai berikut:

epsilon_t(i,j) = P(q_t=S_i,q_t+1=S_j|O,lambda)

Dengan memanfaatkan variabel forward dan backward, rumus di atas dapat dituliskan sebagai berikut:

epsilon_t(i,j) = alpha_t(i) a_ij b_j(O_t+1) beta_t+1(j) / P(O|lambda)
= alpha_t(i) a_ij b_j(O_t+1) beta_t+1(j) / (SUM (k=1 to N) SUM (l=1 to N) alpha_t(k) a_kl b_j(O_t+1) beta_t+1(l))

Pembaginya berfungsi sebagai normalisasi probabilitas. Kita juga bisa merumuskan delta_t(i) dari solusi permasalahan 2 dalam bentuk epsilon_t(i,j) menjadi:

delta_t(i) = (SUM j=1 to N) epsilon_t(i,j)

Selain itu dengan memperhitungkan suatu time period sampai T-1 maka (SUM t=1 to T-1) delta_t(i) merupakan expected number of transitions from S_i dan (SUM t=1 to T-1) epsilon_t(i,j) merupakan expected number of transitions from S_i to S_j. Sehingga cara untuk melakukan estimasi nilai parameter HMM dapat dirumuskan sebagai berikut:

PI_i = expected frequency (number of times) in state S_i at time (t=1) = delta_1(i)

a_ij = expected number of transitions from state S_i to state S_ j /
expected number of transitions from state S_i
= (SUM t=1 to T-1) epsilon_t(i,j) / (SUM t=1 to T-1) delta_t(i)

b_j(k) = expected number of times in state j and observing symbol v_k /
expected number of times in state j
= (SUM t=1 to T where O_t = v_k) delta_t(i) / (SUM t=1 to T) delta_t(i)

Pencarian estimasi parameter yang merupakan solusi maximum likelihood dapat dilakukan dengan mencari estimasi parameter dari sequence dengan panjang satu sampai dengan panjang N. Estimasi yang mempunyai nilai likelihood keseluruhan yang tertinggi merupakan solusi maximum likelihood dari sequence tersebut.

Catatan:
Untuk mencari solusi continuous dari HMM, bisa didapat dengan mengasumsikan bahwa nilai probabilitas dari satu nilai observasi ke observasi lainnya (b_j(k)) 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.

Sequence Clustering

Clustering on Sequential Pattern merupakan sub ilmu dari Data Mining dan Soft Computing.

Clustering on Sequential Pattern adalah suatu proses pengelompokan data, dimana data yang dikelompokkan merupakan suatu pola berurut dan feature dalam data yang muncul sebelumnya menentukan probabilitas dari kemunculan feature berikutnya. Clustering on Sequential Pattern bisa dilakukan dengan memanfaatkan berbagai jenis metode clustering yang salah satunya adalah metode mixture modelling.

Memodel data sequence dalam bentuk cluster dengan memanfaatkan teori probabilitas dapat dilakukan dengan dua cara yaitu:
1. Menganggap data sequence yang ada sebagai model Markov Chain
2. Dengan memanfaatkan metode Hidden Markov Model sebagai model dari data sequence yang ada

Untuk kasus yang pertama, sequential pattern dapat dimodel dengan Markov Chain, dimana order dari Markov Chain ini menentukan berapa banyak feature yang akan menentukan nilai dari feature yang akan datang. Umumnya Markov Chain yang digunakan adalah Markov Chain dengan order satu, dimana satu feature sebelumnya saja yang menentukan nilai feature yang akan datang beserta probabilitasnya. Markov Chain dengan order n, berarti bahwa sebanyak n feature sebelumnya yang menentukan nilai feature yang akan datang dan probabilitasnya.

Untuk kasus yang kedua, sequential pattern dapat dimodel menggunakan Hidden Markov Model yang merupakan perkembangan dari Markov Chain model. Hidden Markov Model mempunyai suatu variabel tambahan dibandingkan dengan Markov Chain yaitu berupa hidden variabel yang berfungsi untuk memodel jumlah dan jenis sumber darimana bagian-bagian dari sequence tersebut berasal.

Mixture modelling terhadap data sequence dilakukan dengan memodel Markov Chain model atau Hidden Markov Model yang didapatkan dari data sequence yang bersangkutan. Distance measure yang digunakan adalah log-likelihood dari sequence yang bersangkutan ke model sequence representasi dari cluster yang terbentuk. Dari pemodelan ini, akan didapatkan jumlah cluster yang paling sesuai, jenis data yang masuk di dalam masing-masing cluster dan juga proporsi (relative size) dari masing-masing cluster.

Beberapa variasi dari sequence analisis juga didapatkan dalam bioinformatics dimana proses sequence alignment juga perlu untuk dilaksanakan, untuk memastikan ada tidaknya mutasi dari suatu gen ke gen yang lain. Dalam penganalisaan web sequence juga sering didapatkan bahwa suatu sequence adalah mirip dengan sequence yang lain dimana satu bagian dari salah satu sequence tidak terdapat pada sequence lainnya.

Referensi:
Smyth P (1997). Clustering Sequences with Hidden Markov Models, Moser M. C. et al eds, Advances in Neural Information Processing Systems, vol 9, The MIT Press, page 648.
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.

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.