Fourier Transform

30 05 2008

Catatan singkat tentang Fourier Transform.

Fourier Transform adalah suatu metode melakukan transformasi signal periodik menjadi variabel dalam bentuk frekuensi (Hz = cycles/second). Transformasi dilakukan dengan rumus berikut ini:

X(f) = INTEGRAL (-infty to infty) x(t) * e^(-2*j*PI*f*t) dt

dimana:
t : waktu
f : frekuensi
x : signal.

Perlu diperhatikan di sini bahwa x adalah signal dengan domain waktu dan X adalah signal dengan domain frekuensi. Rumus di atas mempunyai arti bahwa signal x(t) dikalikan dengan suatu term exponential, pada suatu titik frekuensi f, dan diintegrasikan untuk ‘semua waktu’ yang ada. Term exponential pada rumus di atas dapat ditulis juga seperti rumus berikut ini:

e^(-2*j*PI*f*t) = cos(2*j*PI*f*t) + j * sin(2*j*PI*f*t)

Pertanyaan: Kenapa kita memerlukan informasi frekuensi?
Banyak signal biologi seperti ECG (electrocardiograph), EEG (electroencepalograph) dan EMG (electromyograph) mempunyai pola khusus secara teratur yang mencerminkan keadaan organ yang sehat. Deviasi terhadap pola tersebut sangat sulit dilihat kalau hanya memanfaatkan domain waktu. Domain frekuensi dalam hal ini sangat bermanfaat untuk keperluan itu.

Akan tetapi, Fourier Transform mempunyai sedikit kelemahan dalam mentransformasi non-stationary signal. Non-stationary signal merupakan signal yang berubah-ubah frekuensinya seiring dengan perjalanan waktu. Untuk keperluan tersebut, diusulkan untuk menggunakan Short Term Fourier Transform.

Sebagai informasi tambahan, signal dalam domain frekuensi dapat ditransformasikan kembali ke signal dalam domain waktu menggunakan Inverse Fourier Transform dengan rumus seperti berikut ini:

x(t) = INTEGRAL (-infty to infty) X(f) * e^(2*j*PI*f*t) df

Advertisements




Voronoi Based Coverage Control

21 05 2008

Di milis sc-ina, sedang dilaksanakan e-kolokium, dimana e-kolokium pertama yang diisi oleh Mas Azwirman Gusrialdi (Mas Iman) tanggal 1-15 Mei 2008 dengan tema Voronoi Based Coverage Control with Anisotropic Sensor. Tema yang diangkat sangat menarik dan merupakan pembelajaran baru bagi saya. Thanks to Mas Iman dan Mas Anto atas e-kolokium yang telah dilaksanakan. Saya buat catatan sedikit untuk mengingatkan beberapa diskusi yang muncul.

Q : Dari latar belakang yang diceritakan, tidak ada satupun referensi yang terkait dengan penggunaan anisotropic sensor. Apa memang belum ada yang mengerjakan, atau belum ada hasil yang signifikan mengenai itu?
A : Memang untuk coverage control dengan menggunakan anisotropic sensor ini, setahu pengetahuan saya saya yang pertama kali mengerjakan. Ada sih yang juga menggunakan anisotropic sensor, cuman definisi anisotropicnya beda, yaitu jika sensornya hanya bisa mensense sampai besaran sudut alpha saja (tidak 360 derajat). Tetapi dia tetap mengasumsikan sensing performance sebagai fungsi dari jarak saja.

Q : Apakah ada bentuk fisik dari anisotropic sensor? Misalnya kalau di mobile robot sangat umum dipakai laser range finder, ultrasonic sonar dsb. IMHO: kalau misalnya laser range finder disusun menjadi array secara merata di badan mobile robot maka hasilnya adalah isotropic sensors, kalau anisotropic?
A : Pertanyaan yang bagus sekali. Sebenarnya anisotropic sensor itu contohnya seperti radar, kamera, directional microphone dll. Cuman model saya disini tidak bisa mewakili semuanya secara precise. Saya sengaja mengambil model ellipse karena ini yang paling “gampang” dianalisanya. Alasannya karena saya ingin menyelidiki dulu ke applicabily-an dari Voronoi method ini untuk anisotropic sensor model ini dan ternyata sayang sekali tidak cukup baik untuk dipakai. Saya juga telah mempublish paper untuk model sensor anisotropic kamera dengan model yang cukup precise, tapi dengan menggunakan method lain. Kalau tertarik bisa saya kirim japri papernya.

Q : Apakah ada interpretasi/penjelasan secara teknis dari cost function equation (3)?
A : Ini juga pertanyaan yang bagus sekali. Untuk menjelaskan arti dari cost function ini saya ingin sedikit memberikan keterangan. Pertama di cost function itu ada function f yang merupakan fungsi dari jarak. f ini menggambarkan sensing performance dari sensornya. Artinya semakin jauh jarak titik yang mau disense dengan sensornya, nilai f semakin kecil i.e. sensing performancenya semakin jelek. Kemudian ada phi yang merupakan fungsi yang menggambarkan pentingnya suatu daerah. Kalau phi tinggi artinya daerah itu penting. Kita tentunya ingin sensor2 kita lebih mendekat ke daerah yang penting maka kita meminimalkan perkalian dari f dan juga phi. Jadi intinya, kita pengen nyuruh sensor2 kita pergi ke daerah yang penting. Kira2 begitu artinya Pak Imam.

Q : Cost function H eq (3), non-negative bounded from below kan mas Iman? Maksudnya there exists a positive real number x such that H >= x? dan min H = x? :d Kalau f kecil dikalikan \phi besar jadinya gmn? Misalnya f=0 dan H=10000, maka nilai optimalnya tidak unik, karena semua f(q_i-p_i)=0 merupakan solusi?
A : Maaf mas,saya agak kurang mengerti. Memang solusinya tidak unik, karena tergantung kita mulainya dimana, tergantung initial positionnya. Tapi yang jelas dengan meminimalkan H, kita akan mencapai suatu (local) optimal configuration. Hal ini juga lumrah karena kita hanya mempunyai local informasi, bukan global informasi.

Q : Dari objective function yang diberikan, ada continuous density distribution function theta(q). Kira-kira continuous density distribution function apa yang digunakan? dan Kenapa?
A : Contoh density functionnya mis : e^-(x^2 + y^2) dengan x, y adalah posisi point yang mau disense. Sengaja dipilih continuous agar collision avoidance bisa terjamin (agar centroid berada di dalam Voronoinya)

Q (Comment) : Untuk mengkonfirmasi saja, berarti pointnya di sini ada pada ‘contiunuous’-nya ya Mas Iman? Sedangkan bentuk distribusinya tidak berpengaruh pada masalah optimasi yang muncul.
A (Comment) : Iya, menurut saya begitu Pak Yudi. Karena density function itu hanya menggambarkan/memodelkan penting tidaknya suatu point yang hendak di sense sama sensor kita.

Q : Sekalian juga kalau bisa dapat penjelasan mengenai objective function (overall sensing cost function) yang digunakan. Apakah ini yang ‘umum’ digunakan? Apakah mungkin ada variasi yang bisa diaplikasikan?
A : Sebenarnya pendefinisian dari cost functionnya tergantung dari approach (asumsi etc) dan juga tujuan yang hendak dicapai (common behaviournya). Berhubung saya memakai Voronoi approach i.e. setiap sensor diasumsikan mempunyai daerah kekuasaannya sendiri, maka cost function itu yang dipakai. Cost function ini juga sebenarnya modifikasi sedikit dari kasus yang isotropic yang sudah pernah ada sebelumnya. Jadi tergantung asumsi2 yang kita buat dan juga approachnya. Untuk selain Voronoi approach tentu saja beda cost functionnya.

Q : Apakah secara teknis dynamic equation (\dot{p}_i=u_i) di equation (4) cukup untuk mewakili dynamics dari mobile sensors? IMHO: misalnya pesawat terbang, mobil, mobile robots dll yang membawa sensor adalah sistem yang nonholonomic dan paling tidak dynamicsnya adalah 4-th order dan nonlinear. Apakah perlu feedback linerization supaya eq (4) bisa menjadi reasonable?
A : Bener sekali pak. Sebenarnya sengaja dipilih model (4) biar gampang analisisnya (sebenarnya dengan model (4) aja udah jatuh bangun ngerjainnya). Tetapi menurut saya untuk model yang lebih rumit juga bisa saja. Intinya setiap agent pergi menuju ke centroid dari daerah kekuasaannya. Sepertinya ada beberapa orang yang mengerjakan untuk kasus non-holonomic atau dynamic yang lebih rumit.

Q (Comment) : Iya betul mas, saya kira tidak mungkin bagi kita untuk mengerjakan semuanya. Tapi saya kira ada model yang juga linear tapi lebih reasonable dari $\dot{p}_i=u_i$ di persamaan (4) yaitu $\ddot{p}_i=u_i$ (dot di ganti ddot). Banyak kasus di mobile robot yang nonholonomic bisa di feedback linearization-kan sehingga menjadi persamaan ini. Tapi $\ddot{p}_i=u_i$ pun masih sangat mungkin untuk di ubah ke bentuk $\dot{p}_i=u_1$ dengan mendefinisikan: u_i=u_1+u_2, dengan u_2=-\dot{p}_i+\ddot{p}_i.
A (Comment) : Bener sekali mas Imam. Model dengan double integrator tentunya lebih reasonable. Cuman saya waktu ngeriset ini lebih tertarik ke pengaruh anisotropic sensor modelnya ke Voronoi approach ini. Tentunya bisa diextend ke double integrator untuk dynamicnya. Ini hanya masalah selera mas 🙂 .

Q : Untuk ‘Mobile Sensors Dynamic’ p_i = u_i yang digunakan, seperti diskusi yang sudah muncul, kelihatannya ada beberapa variasi yang bisa digunakan. CMIIW. Bisa gak diceritakan lebih detail Mas Iman, apa kelebihan dan kekurangan variasi yang ada.
A : Benar sekali Pak Yudi. Seperti dijelaskan Mas Imam, model saya masih terlalu sederhana untuk robot/vehicle yang sebenarnya. Selain model saya masih banyak model dynamics yang lain seperti double integrator, non-holonomic (kalau misalnya agentnya non-holonomic) sampai model2 rumit lainnya. Kelebihannya tentu saja modelnya lebih detail dan lebih menggambarkan sistem kita yang sebenarnya. Kekurangannya analisisnya lebih rumit 🙂 . Dan juga, suatu cara yang alamiah untuk meng-extend kerjaan kita adalah dengan melihat model2 yang lebih detail/rumit. Ini kebanyakan saya liat dari paper2 di bidang cooperative control ini. Cuman saya kurang tertarik mengutak atik lebih detail di modelnya. Tapi sebenarnya model yang single integrator (yang saya pakai di paper) juga tidak terlalu jelek. Karena saya sudah memakainya untuk eksperimen.

Q : Btw, saya ada sedikit pertanyaan/komentar tentang control law di persamaan (10). Mohon dijelaskan kalau salah. Berdasarkan persamaan (4) -> \dot{p}_i=u_i , maka sekilas kita tahu (karena sistemnya linear, dari fundamental control theory: necessary and sufficient condition) untuk membuat sistemnya assymptotically stable ke c_i adalah dengan men-set u_i= -f(p_i-c_i), dengan f(.,.) > 0. Intinya dengan control law ini maka pole dari persamaan (4) akan berada di left-half plane. Tapi Proof untuk Proposisiton 4.1 Mas Iman sampai harus men-invoke la-Salle invariant principle? apakah perlu? Bukankah f(.,.)=k(p_i-C_{v*i}), dengan k positive maka f(.,.) akan non negative (dan polenya pasti akan berada di left half plane) yang artinya sistemnya pasti assymptotically and exponentially stable? Maksudnya kita tidak harus membunuh nyamuk dengan bom kan?
A : Mungkin belum saya jelaskan kalau control law-nya itu adalah continuous time version Lloyd algorithm. Biasanya di dunia computer science kita menjumpai Lloyd algorithm yang discrete yaitu pertama kita buat Voronoi, hitung centroid lalu pergi ke centroid, lalu hitung lagi Voronoi … diulang2 sampai berhenti algoritmanya. Nah di sini saya membuat versi continuousnya. Seperti dijelaskan di papernya, kalau Voronoi ini tergantung pada posisi. Jadi sebenarnya waktu agentnya bergerak ke centroid dia akan langsung membuat Voronoi yang baru, menghitung centroidnya dan pergi ke centroid yang baru i.e. agentnya belum sampai ke centroid waktu Voronoi yang baru dibentuk (ini mungkin bisa dilihat di video eksperimentnya). Ini dilakukan terus menerus dan finally akan converge ke suatu critical point (satu lagi yang belum saya sampaikan, di cooperative control, kita tidak menggunakan term stable, tapi lebih ke converge to critical points/convergence). Nah ini yang saya tidak bisa lihat di analisis yang Mas Imam berikan karena kelihatannya itu hanya untuk discrete versionnya saja. Dan juga sebenarnya pernghitungan dV/dt (penurunan Lyapunov functionnya) tidak bisa langsung dihitung dengan mudah. Karena Voronoi depends on the position of the agent. Jadi harus melalui beberapa tahap perhitungan.

Q : Tentang asumsi ke-1 yang digunakan, kenapa harus memilih jarak non-Euclidean?
A : Sebenarnya ini trik saya. Alasannya sangat sederhana, saya ingin menganalisis dari sensor model yang sangat sederhana. Karena isotropic sensor bisa dimodelkan dengan lingkaran, maka secara alamiah, extensionnya adalah sebuah ellipse yang menggambarkan anisotropic sensor. kebetulan ellipse ini bisa dirumuskan dengan asumsi-1 (kalau dijabarkan maka persamaan di asumsi satu akan menjadi persamaan ellipse). Selain itu dengan memilih asumsi 1 ditambah fixed and equal orientation, maka masalahnya bisa ditransfer ke isotropic case. Jadi kira2 itu alasannya pak.

Q : Tentang asumsi ke-2, dikatakan bahwa parameter oritentationnya diset statis. Tetapi di Remark ke-3 dikatakan kalau orientationnya diset tidak statis akan memberikan hasil yang lebih baik. Kenapa tidak sekalian menjelaskan tentang optimisasi dengan orientasi yang tidak statis?
A : Jadi salah satu key point dalam mendesign algorihma control-nya adalah agar bagaimana control law-nya itu distributed. Nah dengan anisotropic model ini, Voronoi diagramnya akan kehilangan sifat local information ini, maksudnya untuk membentuk Voronoi diagram yang anisotropic case, diperlukan informasi semua agent. Jadi saya mengasumsusikan orientasinya harus fixed dan sama. meskipun orientasinya tidak sama, saya telah membuktikan (meskipun tidak ditulis di paper buktinya, karena lumayan panjang) kalau control law yang sama akan didapat, hanya saja control law ini tidak distributed. Sedangkan untuk orientasi yang sama tapi tidak statis, tidak logis untuk mengoptimisasi terhadap orientasi, karena control lawnya tidak terdistribusi juga jadinya. Jadi intinya ada di distributed control law-nya pak.

Q : Apakah ini mengimplikasikan bahwa pemodelan dengan orientasi tidak fixed, tidak bisa diaplikasikan (inapplicable)?
A : Sebenarnya bisa saja diaplikasikan Pak Yudi. Hanya saja algoritmanya menjadi tidak terdistribusi. Kita jadi membutuhkan semacam kamera di langit untuk mengetahui posisi ataupun orientasi dari setiap agent. Salah satu jalan lain adalah dengan memodifikasi anisotropic voronoi dengan beberapa asumsi pada sensor modelnya (saya sudah punya beberapa ide, cuman belum pernah dicoba, jadi tidak bisa memberitahu lebih detail).

Q : Apakah algoritma ini sudah diujicoba pada masalah aplikasi riil (misalnya manipulation in hazardous env., seperti pada introduction)? Kalau sudah pernah dicoba barangkali bisa diceritakan mengenai hal tsb. Kalau belum, kira-kira hal apa saja yang perlu dikerjakan sebelum algoritma ini bisa diterapkan pada aplikasi praktis?
A : Mengenai aplikasi algoritma ini, khusus untuk masalah coverage control saya belum menemukan group yang mencoba pada masalah yang sebenarnya, seperti benar2 pada lingkungan beracun etc. semuanya hanya sebatas eksperimen saja. Sedangkan beberapa group e.g. dari Caltech (Richard Murray), University of Pennsylvania (George Pappas) dan juga group Mark Spong sudah pernah menerapkan cooperative control selain coverage control dengan menggunakan UAV. Untuk lebih lengkapnya bisa disearch di website mereka. Menurut pendapat saya, algoritma ini bisa diterapkan pada masalah yang sebenarnya dengan memakai sensor beneran (selama ini eksperimen saya hanya mengasumsikan bahwa di robotnya ada sensor), tentunya kalau beberapa masalah di bawah bisa diselesaikan :
1. Localization. Seperti tersirat di algoritmanya, setiap sensor harus mengetahui posisinya masing2 agar bisa mengkomunikasikannya dengan sensor yang lain. Selama ini saya menggunakan kamera yang ditaruh di atap dan dengan sedikit image processing untuk menentukan posisi suatu agent. Tentunya di dunia real ini tidak mungkin. Salah satu kemungkinan adalah dengan gps.
2. Density function harus diketahui secara lebih dahulu. Namun sekarang sudah ada algoritma yang mengasumsikan kalau kita tidak tahu density functionnya.
3. Region of interestnya harus convex. Algoritma ini tidak bisa diterapkan untuk non-convex region e.g. suatu museum dengan banyak ruang.
4. Telah ada hardware (komunikasi, robot yang dapat memproses data yang diterima untuk menentukan langkah selanjutnya) yang memenuhi. Tapi ini juga tidak ada masalah.

Semoga bermanfaat dan maaf kalau ada salah edit.





Burung Camar by Vina Panduwinata

16 05 2008

Burung Camar oh Burung Camar, an everlasting song that makes us relax and feel happy. Thanks to Jeng Vina Panduwinata for her wonderful voice.

Lyrics:

Burung camar, tinggi melayang
Bersahutan, di balik awan
Membawa angan-anganku jauh meniti buih
Lalu hilang larut di lautan

Oh bahagia tiada terperi
Indah nian derap jiwaku
Tak kenal duka derita tak kenal nestapa
Ceria penuh pesona

Tiba-tiba ‘ku tertegun lubuk hatiku tersentuh
Perahu kecil terayun nelayan tua di sana
Tiga malam bulan t’lah menghilang
Langit sepi walau tak bermega

Tiba-tiba kusadari lagu burung camar tadi
Cuma kisah sedih nada duka, hati yang terluka
Tiada teman, berbagi derita,
bahkan untuk berbagi cerita

Burung camar, tinggi melayang
bersahutan di balik awan
Kini membawa anganku yang tadi melayang
Jatuh dia dekat di kakiku

Tiba-tiba kusadari lagu burung camar tadi
Cuma kisah sedih nada duka, hati yang terluka
Tiada teman, berbagi derita,
bahkan untuk berbagi cerita

Burung camar, tinggi melayang
bersahutan di balik awan
Kini membawa anganku yang tadi melayang
Jatuh dia dekat
Jatuh dia dekat
Jatuh dia dekat di kakiku

Burung camar, tinggi melayang
bersahutan di balik awan
Kini membawa anganku yang tadi melayang
Jatuh dia dekat
Jatuh dia dekat di kakiku





Clustering Untuk Categorical Data

14 05 2008

Dalam sebuah diskusi di suatu milis, ada yang menanyakan tentang metode untuk melakukan clustering terhadap categorical data. Dari beberapa masukan yang ada, ada beberapa metode yang bisa digunakan untuk melakukan clustering jenis ini, termasuk di antaranya metode K-Modes clustering yang algoritmanya mirip dengan k-means (penjelasan tentang k-modes ada di dalam k-means page ini), ada yang mengusulkan tree models (CART) yang dapat didownload free, ada yang mengusulkan sebuah paket program yang disebut Party, Algoritma TWOSTEP, PREFSCAL dari SPSS yang dokumentasinya ada di sini, dan Latent Class Analysis.

Penanya awal dari diskusi ini ingin menggunakan K-Modes untuk melakukan analisa, tetapi dari diskusi yang muncul, ternyata banyak juga algoritma yang bisa digunakan untuk ini. Dan dari beberapa sumber di internet, ternyata K-Modes banyak mempunyai kelemahan. Beberapa kelemahan k-modes antara lain hasil clustering yang berbeda-beda tergantung pada proses initialisasi, dan juga error rate yang tinggi. Mungkin ada satu lagi metode yang secara prinsip sama dengan algoritma yang diusulkan terakhir (Latent Class Analysis) yang bisa digunakan untuk clustering jenis ini. Metode tersebut adalah Mixture Modelling. Metode ini merepresentasikan data categorical menjadi suatu bentuk distribusi Binomial atau Multinomial sebagai pengganti distribusi continuous seperti Gaussian. Penjelasan tentang mixture model dapat dilihat di My Mixture Model Page untuk lebih jelasnya.





Similarity Measure

13 05 2008

Dalam melakukan pattern matching ataupun untuk melakukan berbagai jenis pengklasifikasian, similarity measure merupakan bagian penting yang harus diperhatikan. Ada beberapa jenis similarity measure yang bisa digunakan termasuk di antaranya:

Distance-Based Similarity Measure

Distance-Based Similarity Measure mengukur tingkat kesamaan dua buah objek dari segi jarak geometris dari variabel-variabel yang tercakup di dalam kedua objek tersebut. Yang termasuk sebagai distance-based similarity measure antara lain:

  • Manhattan Distance (L1 Norm) : mengukur jarak dua buah objek dengan rumus sebagai berikut:

    d_L1 (x1, x2) = SUM (i=0 to n) |x1i – x2i|

  • Euclidean Distance (L2 Norm) : menguruk jarak dua buah objek dengan rumus sebagai berikut:

    d_L2 (x1, x2) = SQRT ( SUM (i=0 to n) (x1i – x2i)^2 )

  • Minkowski Distance (Lp Norm) : menguruk jarak dua buah objek dengan rumus sebagai berikut:

    d_Lp (x1, x2) = ROOT_p ( SUM (i=0 to n) (x1i – x2i)^p )

  • Chebyshev Distance (Chessboard Distance, L_Infinity Norm) : menguruk jarak dua buah objek dengan rumus sebagai berikut:

    d_Chebyshev (x1, x2) = max_i {x1i – x2i}

  • Mahalanobis Distance : mengukur jarak dua buah objek seperti L2 Norm dengan memikirkan korelasi antar objek dalam bentuk vector variabel dari objek dan matrik covariance dari kedua objek tersebut dengan rumus sebagai berikut:

    d_Mahalanobis (x1, x2) = SQRT ((x1 – x2)^T COV^(-1) (x1 – x2))

    Apabila matrik covariance adalah matrik identity maka Mahalanobis distance adalah Euclidean distance, dan apabila matrik covariance adalah matrik diagonal maka Mahalanobis distance adalah Normalised Euclidean distance dimana korelasi antara objek dianggap tidak ada. Dalam hal ini Mahalanobis distance dihitung dengan rumus sebagai berikut:

    d_Mahalanobis (x1, x2) = SQRT ( SUM (i=0 to n) (x1i – x2i)^2/SIGMA_i^2)

  • Hamming Distance : mengukur jarak antara dua string yang ukurannya sama dengan membandingkan simbol-simbol yang terdapat pada kedua string pada posisi yang sama. Hamming distance dari dua string adalah jumlah simbol dari kedua string yang berbeda. Sebagai contoh Hamming distance antara string ‘toned’ dan ‘roses’ adalah 3. Hamming Distance juga digunakan untuk mengukur jarak antar dua string binary misalnya jarak antara 10011101 dengan 10001001 adalah 2.
  • Levenshtein Distance : mengukur jarak antara dua string yang ukurannya tidak sama dengan menghitung jumlah pengoperasian yang perlu dilakukan untuk mengubah string yang satu menjadi string yang kedua yang diperbandingkan. Pengoperasian yang dilakukan termasuk operasi insert, delete dan substitusi. Sebagai contoh Levenshtein distance antara string ‘kitten’ dan ‘sitting’ adalah 3 dengan pengoperasian substitusi k dengan s, substitusi e dengan i, dan insert g.
  • Hausdorff Distance : mengukur jarak berbasis nilai infimum/greatest lower bound dan supremum/greatest upper bound dari kedua objek, dimana semua variabel dari kedua objek tersebut mempunyai nilai compact/closed. Hausdorff distance dihitung dengan rumus sebagai berikut:

    d_Hausdorff (x1, x2) = max {sup (x1i in x1) inf (x2i in x2) d_L2 (x1i, x2i), sup (x2i in x2) inf (x1i in x1) d_L2 (x1i, x2i)}

Probabilistic-Based Similarity Measure

Probabilistic-Based Similarity Measure menghitung tingkat kemiripan dua objek dengan merepresentasikan dua set objek yang diperbandingkan tersebut dalam bentuk probability. Beberapa metode probabilistic-based similarity measure termasuk:

  • Kullback Leibler Distance : mengukur tingkat kemiripan variabel objek yang direpresentasikan dalam bentuk probabilita dua distribusi statistik. Sering disebut juga information distance, information gain, atau relative entropy. Jarak antara dua objek yang bernilai diskrit dalam Kullback Leibler distance dihitung dengan rumus sebagai berikut:

    D_KL (P,Q) = SUM (i) P(i) log (P(i)/Q(i))

    Sedang untuk objek yang bernilai continuous dihitung dengan rumus sebagai berikut:

    D_KL (P,Q) = INTEGRAL (i) P(i) log (P(i)/Q(i))

  • Posterior Probability : mengukur tingkat kemiripan dengan mempertimbangkan nilai posterior probability terhadap nilai perbedaan variabel dari kedua objek yang diperbandingkan. Untuk menentukan posterior probability dari perbedaan variabel tersebut diperlukan data nilai-nilai perbedaan yang independent sebagai bahan training untuk pembentukan fungsi likelihood dari perbedaan-perbedaan tersebut.

Set-Based Similarity Measure

Jaccard Index adalah indeks yang menunjukkan tingkat kesamaan antara suatu himpunan (set) data dengan himpunan (set) data yang lain. Jaccard Index dihitung menggunakan rumus sebagai berikut:

J(A,B) = (A INTERSECT B)/(A UNION B)

Sebagai kebalikannya, tingkat ketidak samaan antara dua himpunan dihitung dengan:

J_delta(A,B) = ((A UNION B) – (A INTERSECT B))/(A UNION B)

Feature-Based Similarity Measure

Feature-based similarity measure melakukan penghitungan tingkat kemiripan dengan merepresentasikan objek ke dalam bentuk feature-feature yang ingin diperbandingkan. Feature-based similarity measure banyak digunakan dalam melakukan pengklasifikasian atau pattern maching untuk gambar dan text.

Context-Based Similarity Measure

Context-based similarity measure melakukan penghitungan tingkat kemiripan objek-objek yang mempunyai struktur yang tidak biasa seperti objek yang harus direpresentasikan dengan tree structure atau struktur yang lainnya.





Lake Beratan and Kebun Raya

9 05 2008

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.

Bedugul - Pura Ulun DanuDanau 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.

Bedugul - Kebun RayaDi 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.

Bedugul - Aya dan Kiya

Bedugul - NicolasDanau 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.

Travelling Bali Part 1 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

7 05 2008

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.