Lake Beratan and Kebun Raya

Petunjuk menuju daerah Bedugul ada di bagian bawah tulisan ini.

Beberapa waktu lalu, kami bertamasya ke Danau Beratan dan Kebun Raya yang ada di dekatnya. Berikut ini sedikit cerita dan beberapa gambar yang kami sempat ambil di sana.

Danau Beratan adalah merupakan salah satu dari tiga danau yang terletak di daerah Bedugul, suatu daerah yang membatasi dua kabupaten yaitu Kabupaten Tabanan di selatan dan Kabupaten Buleleng di utara. Bedugul sendiri merupakan daerah pegunungan yang sangat sejuk dan biasanya didatangi oleh para pengunjung yang ingin mendapatkan suasana lain dari biasanya yang lebih sejuk dan pemandangan fresh yang hijau. Bedugul sendiri identik dengan pegunungan, bunga, dan buah-buahan. Mungkin karena sejuknya tersebut, bunga dan buah-buahan begitu mudah untuk ditemukan di sana.

Di samping mengunjungi Danau Beratan ada suatu tempat yang sangat nyaman untuk dikunjungi untuk sekedar duduk-duduk sambil memakan makanan ringan maupun makan siang. Tempat tersebut disebut dengan Kebun Raya Bedugul. Banyak pepohonan yang bisa ditemukan di sana dan banyak lapangan luas yang terbentang yang mengijinkan anak-anak untuk berlari-lari dan bagi orang tua untuk bersantai duduk sambil melihat pemandangan. Salah satu bagian yang menjadi tempat favorit kami kalau berkunjung ke sana adalah suatu lapangan rumput yang cukup luas yang letaknya agak ke dalam di dalam kebun raya tersebut. Lapangan tersebut menghadap ke Danau Beratan di bagian bawahnya. Kami sering duduk di sana untuk bersantai sambil menyantap snack atau makan siang dan mendengarkan lagu-lagi dari radio yang sengaja kami bawa.

Danau Beratan sendiri sangat terkenal dengan suatu pura yang disebut dengan Pura Ulun Danu Danau Beratan. Gambar Pura Ulun Danu ini banyak dan sering sekali terpampang di beberapa brosur yang mempromosikan pariwisata Pulau Bali. Keunikan dari pura ini adalah letaknya yang ada sedikit di tengah danau. Pada saat air danau tinggi, kita bahkan tidak bisa melihat jalan atau daratan yang menghubungkan pura tersebut dengan tepi danau. Dari pura tersebut kita juga dapat menyewa perahu kecil untuk bisa berkeliling di tengah danau. Saat kami berkunjung mendung atau mungkin kabut lumayan pekat, sehingga kami memutuskan hanya duduk-duduk saja menikmati pemandangan danau. Saat itu, Nicolas, salah satu internship asal Perancis yang sedang melakukan magang di Bali di bawah bimbingan saya, juga ikut bertamasya. Di sana, saya sempat mengabadikan Nicolas di depan Pura Ulun Danu tersebut sebagai kenangan.

Direction: Untuk mencapai daerah Bedugul, kalau anda berangkat dari arah Denpasar, anda perlu untuk menuju ke arah Terminal Bis Ubung terlebih dahulu. Dari sana, anda terus menyusuri jalan utama menuju arah utara, dan sampai di pertigaan Bringkit, anda berbelok ke kanan. Dari pertigaan tersebut, anda hanya perlu menyusuri jalan utama, sekitar 20-25 km dan anda akan sampai di Danau Beratan tersebut. Pintu masuk ke Kebun Raya Bedugul ada sebelum Danau Beratan. Letak absolut daerah Bedugul dapat dilihat dengan membuka peta Pulau Bali melalui thumbnail peta di samping. Letak daerah tersebut tersebut ditandai dengan angka nomor [4].

Expectation Maximisation Algorithm

Expectation Maximisation Algorithm (EM Algorithm) adalah algoritma yang sering digunakan untuk menemukan nilai estimasi Maximum Likelihood (ML) dari parameter dalam sebuah model probabilistic, dimana model juga tergantung pada latent variabel yang belum diketahui. Dalam algoritma ini, ada dua hal yang dilakukan secara bergantian yaitu E step yang menghitung nilai ekspektasi dari likelihood termasuk laten variabel seolah-olah seperti mereka ada, dan M step menghitung nilai estimasi ML dari parameter dengan memaksimalkan nilai ekspektasi dari likelihood yang ditemukan pada E step.

Latent variabel adalah variabel yang tidak terobservasi, yang dapat juga disamakan dengan missing data, missing measurements, dan hidden variabel. Dalam kasus mixture model, latent variabel juga mengacu pada jumlah komponen dari suatu mixture model.

Kalau y dianggap incomplete data dan terdiri dari nilai variabel yang sudah terobservasi dan z adalah missing data, maka y dan z akan membentuk complete data. Kalau p(y,z|theta) adalah joint probability density (mass) function, maka p(y,z|theta) bisa dianggap sebagai likelihood dari suatu complete data. Mengikuti teori Bayesian, selanjutnya conditional distribution dari missing data dengan berbasis pada data yang sudah terobservasi dapat diekspresikan sebagai:

p(z|y,theta) = p(y,z|theta)/p(y|theta)
= p(y|z,theta)*p(z|theta)/(INT p(y|z_est,theta)*p(z_est|theta)dz_est

Selanjutnya, EM algorithm secara iterative memperbaiki nilai estimasi dengan mengikuti proses estimasi seperti di bawah ini:

theta_(n+1) = arg max_theta Q(theta)

dimana Q(theta) = SUM(z) p(z|y,theta_n) log p(y,z|theta) atau dengan bentuk yang lebih umum Q(theta) = E_z[log p(y,z|theta)|y] merupakan nilai ekspektasi dari likelihood yang berbasis pada variabel yang sudah diobservasi (yang juga tergantung pada nilai estimasi sebelumnya).

Di sini, log likelihood digunakan sebagai ganti likelihood karena akan mempermudah formula. Perubahan ini tetap akan menghasilkan suatu nilai maksimum pada suatu bagian dari likelihood. Yang perlu diperhatikan di sini adalah nilai z tergantung pada nilai theta_n bukan theta_(n+1).

Berdasarkan pada persamaan di atas, nilai estimasi yang baru, theta_(n+1), akan didapatkan dengan mencari nilai estimasi yang memaksimalkan (M Step) nilai conditional expectation (E Step) dari log likelihood dari complete data yang berbasis pada variabel yang sudah terobservasi dan nilai paremeter terdahulu.

Sebagai catatan, bentuk continuous dari expectation Q(theta) adalah :

Q(theta) = INT(-infty to infty) p(z|y,theta_n) log p(y,z|theta) dz

Referensi:
Dempster A., Laird N., and Rubin D. (1977). Maximum Likelihood From Incomplete Data Via the EM Algorithm. Journal of the Royal Statistical Society, Series B, 39(1): 1-38.

Sensor Pendeteksi Uang

Beberapa bulan ini saya membiasakan diri untuk menyimpan uang di beberapa bagian dari dompet saya, sebagai tempat persembunyian. Karena kadang-kadang uang yang saya simpan di dompet tiba-tiba sudah habis, padahal ada waktunya saya harus mengeluarkan uang untuk membayar barang yang sudah terlanjur saya beli. Kebiasaan saya ini mulai diketahui pasangan (baca: istri) saya. Dan sekarang ini, kalau di bagian penyimpan uang utama di dompet saya tidak ada uangnya, dia pasti mencari di bagian lain, untuk memastikan apakah ada uang yang tersembunyi di tempat lain. Makin hari kelihatannya ‘Sensor Pendeteksi Keberadaan Uang’ ini semakin intens saja. Karena beberapa kali uang cadangan yang saya simpan, sudah tidak ada pada tempatnya lagi. Mungkin suatu titik nanti saya akan menghentikan kebiasaan saya ini, karena fungsi utama menyimpan uang cadangan ini sudah tidak ada lagi .

Note on Support Vector Machine

Support Vector Machine adalah metode pengklasifikasian dengan supervisi yang mencari hyperplane terbaik yang memisahkan data-data dengan kelas-kelas yang berbeda. Support Vector Machine (SVM) diperkenalkan pertama kali oleh Boser, Guyon and Vapnik pada Annual Workshop on Computational Learning Theory (COLT) pada tahun 1992. Diistilahkan juga sebagai Maximum Margin Classifier karena secara simultan meminimalisasikan classification error dan memaksimalkan margin geometrinya.

Permasalahan klasifikasi yang ada umumnya berusaha memisahkan sekelompok data yang berada pada kelas yang satu dengan sekelompok data yang ada di kelas yang lain. Karena SVM merupakan metode pengklasifikasian dengan supervisi, maka data yang menjadi dasar training harus selalu mempunyai informasi tentang kelas di mana data itu berada. Adapun formulasi data training adalah sebagai berikut:

{(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}

dimana y_i bernilai 1 atau -1 yang mengindikasikan ke kelas yang mana data itu dikelompokkan. Pada saat data-data terpisahkan secara ’sempurna’, formulasi hyperplane yang digunakan adalah:

w*x_i + b = 0

Dalam hal ini, data yang berada di kelas positif akan memenuhi persamaan w*x_i + b >= 1, dan data yang berada di kelas negatif akan memenuhi persamaan w*x_i + b <= 1. Kedua persyaratan ini dapat ditulis ulang menjadi:

y_i(w*x_i + b) >= 1, untuk semua i

Sehingga masalah optimasi ini dapat dirumuskan sebagai:
* Memilih w dan b yang meminimimalisasikan |w|
* Dengan batasan y_i(w*x_i + b) >= 1, untuk semua i

Primal Form

Permasalahan optimasi yang dijelaskan di atas sangat sulit untuk dioptimasikan, karena sangat tergantung pada nilai absolut dari |w|. Dalam istilah matematikanya, permasalahan di atas merupakan permasalahan optimasi non-convex. Ada beberapa alternatif pendekatan yang bisa digunakan seperti Gradient Descent, Simulated Annealing, EM dan lain-lain. Yang paling umum digunakan adalah pendekatan dengan mengubah representasi permasalahan menjadi permasalahan optimasi Quadratic Programming (QP). Beruntungnya, permasalahan di atas memang bisa dipecahkan dengan mensubstitusi |w| dengan ||w||^2 tanpa mengubah solusinya (nilai minimum dari persamaan awal dan persamaan yang diubah mempunyai nilai w dan b yang sama).

Dengan demikian masalah optimasi ini diubah menjadi:
* Memilih w dan b yang meminimimalisasikan ||w||^2
* Dengan batasan y_i(w*x_i + b) >= 1, untuk semua i

Permasalahan di atas kemudian dapat dibentuk menjadi permasalahan optimasi Quadratic Programming (QP) yang dirumuskan seperti berikut ini:

L(w,b) = 1/2 * ||w||^2 - SUM (i=1 to N) y_i*(w*x_i+b-1)

Nilai 1/2 nantinya digunakan untuk tujuan kemudahan secara matematika.

Dual From

Sesuai dengan Lagrangian Theory, maka persamaan QP di atas dapat direprenstasikan menjadi:

L(w,b,alpha) = 1/2 * ||w||^2 - SUM (i=1 to N) alpha_i*y_i*(w*x_i+b-1)

dimana alpha_i adalah sebuah term yang menunjuk kepada bentuk dual dari vektor weight terhadap data training:

w = SUM(i) alpha_i*c_i*x_i

dan bernilai 0 atau positif.

Persamaan Quadtratic Programming L(w,b,alpha) di atas dapat dioptimasikan dengan pendekatan fungsi bentuk dual (Dual Form Function) sebagai berikut:

W(alpha) = inf (w) L(w,b,alpha)

Infimum dari L(w,alpha) dapat ditemukan dengan mendiferensiasikan L terhadap w dan b. Sehingga fungsi dual form dari persamaan QP di atas menjadi:

W(alpha) = SUM (i=1 to N) alpha_i -
1/2 * SUM(i=1 to N and j=1 to N) alpha_i*alpha_j*y_i*y_j*x_i*x_j

dengan kondisi alpha_i >= 0 dan SUM (i=1 to N) alpha_i*y_i = 0.

Mencari Maximum Margin Dengan Noise

Permasalahan real yang ada di lapangan umumnya tidak memisahkan kelas yang ada dengan sempurna. Data training umumnya dipisahkan ke dalam kelas-kelas yang ada dengan noise (error). Untuk keperluan tersebut, pendekatan persamaan yang digunakan di atas perlu untuk dimodifikasi. Modifikasi dilaksanakan dengan memperhitungkan nilai error dari data yang tidak pada tempatnya. Adapun persamaan hyperplane yang digunakan adalah sebagai berikut:

y_i(w*x_i + b) >= 1 - E_i, untuk semua i

dimana E_i adalah error dari data ke-i yang dihitung menggunakan jarak error data ke-i ke margin yang seharusnya. Persamaan optimasi QP di atas kemudian dapat diubah menjadi:

L(w,C,E) = 1/2 * ||w||^2 - C * SUM (i=1 to N) E_i

dimana C adalah parameter trade-off sebagai constraint tambahan terhadap parameter alpha_i. C berguna untuk mengontrol trade-off antara margin yang ditemukan dengan besar error pengklasifikasian yang muncul terhadap margin yang ditemukan tersebut. Makin besar nilai C, makin besar penalty yang dikenakan terhadap error pengklasifikasian tersebut.

Permasalahan pengklasifikasian data dengan noise ini dengan persamaan QP di atas mempunyai keuntungan, karena dalam bentuk fungsi dual form, variabel error E_i akan menghilang, sehingga pemecahan yang dilakukan sama dengan data tanpa error dengan tambahan parameter trade-off C.

Pengklasifikasian Non Linear

Untuk kasus-kasus non-linier, dimana data tidak dipisahkan secara non-linier, perlu untuk menggunakan suatu trik sehingga data-data yang terpisah secara non-linier ini dapat direpresentasikan ke bentuk data-data yang terpisah secara linier. Hal ini dapat dilakukan dengan memetakan data ke ruang dimensi yang lebih tinggi:

THETA: R^D to R^Q dimana D<Q

Tetapi untuk mengubah secara langsung data dari satu dimensi ke dimensi yang lain tidaklah mudah. Di sini lah trik yang disebut dengan Kernel Trick bisa digunakan. Dengan trik ini dimensi dari data tidak secara langsung dipetakan, tetapi dengan memetakan dot product dari dua sampel yang ingin dipetakan:

K(x_i,x_j) = THETA(x_i)*THETA(x_j)

Dengan Kernel Trick ini, persamaan QP di atas dengan nilai data pada dimensi yang lebih tinggi, dapat diubah dari:

W(alpha) = SUM (i=1 to N) alpha_i -
1/2 * SUM(i=1 to N and j=1 to N) alpha_i*alpha_j*y_i*y_j*THETA(x_i)*THETA(x_j)

menjadi:

W(alpha) = SUM (i=1 to N) alpha_i -
1/2 * SUM(i=1 to N and j=1 to N) alpha_i*alpha_j*y_i*y_j*K(x_i,x_j)

Dimana kernel yang digunakan dapat bermacam-macam. Adapun pilihan yang sering dipakai adalah:
Polynomial Kernel : K(x_i,x_j) = (x_i*x_j+1)^p
Gaussian Kernel : K(x_i,x_j) = exp(-||x_i-x_j||^2/(2*sigma^2)
Sigmoid Kernel : K(x_i,x_j) = tanh(alpha*x_i*x_j+beta)

Pertanyaan Yang Ada:
1. Bagaimana menentukan nilai parameter kernel yang dipilih?
2. Bagaimana proses pengklasifikasian dengan lebih dari dua kelas?

100 Tahun Puputan Klungkung

Tanggal 28 April 2008 ini tepat 100 tahun peristiwa perang puputan (perang mati-matian) yang terjadi di kota Klungkung, kota kelahiran saya. Cerita Puputan Klungkung tidak seterkenal cerita Puputan Badung ataupun Puputan Margarana. Ini mungkin berawal dari cerita bahwa perang tersebut dilakukan dengan tempo yang sangat singkat, karena dengan bantuan pasukan dari beberapa daerah dan peralatan yang modern, pasukan Belanda begitu mudahnya menguasai kerajaan Klungkung, yang saat itu tidak begitu banyak mempunyai pasukan dan itupun hanya bersenjatakan tombak. Tetapi membaca bagaimana raja Klungkung beserta pasukannya dengan hanya bersenjatakan tombak tersebut (dibandingkan dengan pasukan Belanda yang bersenjatakan meriam), tidak gentar menghadapi situasi perselisihan saat itu, membuat saya berpikir, kenapa semangat mempertahankan wilayah dan keadaan saat itu bisa begitu besar dan begitu “murni” sampai nyawapun rela untuk dikorbankan.

Kembali ke diri sendiri, saya akhirnya bertanya, apakah saya sebagai seseorang yang tinggal di Indonesia, masih mempunyai semangat itu, terutama dalam keadaan dunia sekarang ini yang ukuran utamanya adalah uang, material dan kekuasaan? Mudah-mudahan keyakinan saya untuk menjawab ‘ya’ terus ada, walaupun mungkin tidak dengan nyawa, melainkan dengan ide-ide pemikiran saya .

Selamat Ulang Tahun ke-100 Kota Klungkung. Semoga Klungkung makin semarak, dan begitu juga Indonesia secara keseluruhan nantinya.