Note on Support Vector Machine

30 04 2008

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?

Referensi:
N. Cristianini, J.S.Taylor (2000), An Introduction to Support Vector Machine and Other Kernel-Based Learning Methods, Cambridge Press University.
V.N. Vapnik (1999), The Nature of Statistical Learning Theory (Second Edition), Springer-Verlag, New York, Berlin, Heidelberg.

Advertisements




100 Tahun Puputan Klungkung

28 04 2008

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.





Bali’s Southern Beaches

24 04 2008

Petunjuk menuju Nusa Dua ada di bagian bawah tulisan ini.

Sekitar bulan Oktober 2007, kami sekeluarga memutuskan untuk bertamasya pantai ke daerah bagian selatan Pulau Bali, yaitu wilayah Nusa Dua. Kami berangkat pagi tanpa begitu banyak persiapan kecuali tikar, beberapa makanan kecil dan makanan seadanya untuk santap siang. Kami memulai kunjungan ke Pantai Tanjung. Langit cukup cerah saat itu dan ombakpun tidak begitu tinggi. Awalnya kami bermaksud hanya duduk-duduk santai di tepi pantai, sambil menikmati pemandangan laut. Tetapi, melihat begitu banyaknya permainan yang tersedia, dan wajah-wajah ceria pengunjung yang menikmati permainan-permainan tersebut, akhirnya kamipun tergoda untuk mencobanya. Banana Boat, Parasailing, Flying Fish, Jet Ski, Kano, dan Tamasya Ke Pulau Penyu adalah beberapa di antara banyak permainan yang ada.

Pantai - BananaKami memutuskan untuk bermain Banana Boat, karena Banana Boat bisa dilakukan oleh lebih dari empat orang, sehingga kami bisa melakukannya sekeluarga bersamaan. Melihat tawa ria pengunjung yang telah menyelesaikan permainan Banana Boat, kami pikir kami akan bisa duduk bersantai-santai di atas banana boat tersebut. Tapi kami salah perkiraan. Naik Banana Boat ternyata cukup memerlukan tenaga untuk berpegangan. Kalau tidak, kita bisa terpental jatuh ke dalam laut. Saya was-was saja anak saya yang kedua, Kiya (6 tahun), akan tidak kuat memegangnya, karena saya sendiri harus berpegangan cukup kuat untuk menjaga keseimbangan. Tapi ternyata Kiya cukup kuat menyelesaikan permainan itu. Kami sangat sangat bangga pada Kiya saat itu.

Pantai - ParasailingPermainan lain yang kami (saya) mainkan adalah parasailing. Sayangnya parasailing hanya bisa dinikmati oleh satu orang dan anak-anak tidak diperbolehkan. Kalaupun boleh, harus bareng dengan orang tua. Tapi entah kenapa, saya tidak diijinkan untuk naik berdua, mungkin karena keberatan kali ya. Jadilah hanya saya yang memainkannya. Cukup menyenangkan juga naik ke udara bebas sambil melihat garis pantai yang putih dan laut yang saat itu berwarna biru muda. Untuk bisa menyelesaikan permainan itu, sebelum memulai permainan, saya diberikan pelajaran kecil bagaimana caranya agar sailing bisa belok ke kiri dan kanan, dengan sarung tangan biru dan merah, masing-masing di tangan kanan dan kiri. Dari garis pantai, petugas akan memberikan aba-aba dengan bendera biru dan merah, dan menaikkannya sesuai keperluan, sehingga kita tidak terbawa angin, tidak tercebur ke laut dan bisa mendarat dengan baik di garis pantai. Cukup menegangkan tapi sangat menyenangkan.

Pantai - MengiatSetelah puas melakukan permainan di Pantai Tanjung, kami berpindah mencari pantai yang lain, dan kamipun pergi ke Pantai Mengiat. Pantai Mengiat merupakan pantai yang ada di kompleks hotel Nusa Dua. Walaupun begitu, tidak ada biaya yang dikenakan untuk masuk ke pantai ini. Kami sengaja meluangkan waktu di pantai tersebut untuk menikmati makan siang kami. Setelah menikmati santap siang, saya dan istri beristirahat di bawah pohon-pohon yang cukup rindang sebagai peneduh. Aya dan Kiya, seperti biasa, tidak bisa diam kalau sudah melihat pantai dan air. Mereka berdua bermain pasir di tepi pantai. Matahari sangat menyengat saat itu. Saya tidak bisa membayangkan, mereka bisa tahan duduk di pasir yang memang cukup panas, tapi masih bisa bermain sambil tertawa-tawa (Foto di samping tidak begitu bisa memperlihatkan, tapi pasirnya memang sangat-sangat panas sekali saat itu). Disela-sela waktu mereka, mereka juga memanfaatkan waktu mereka untuk menggambar pantai yang sedang mereka kunjungi.

Pantai - DreamlandSetelah secukupnya beristirahat, kami mencari-cari lagi pantai yang bisa dikunjungi. Kami akhirnya memutuskan untuk pergi ke Dreamland, karena pantai ini cukup banyak dibicarakan orang, sebagai pantai baru yang belum banyak pengunjungnya. Pantai tersebut kalau dilihat dari posisinya ada di bagian barat ujung selatan Pulau Bali. Pantai itu memang pantai yang baru, tetapi ternyata pengunjungnya saat itu sangat banyak sekali. Pasir putih dan pemandangan tebing merupakan ciri khas pantai itu. Setelah melihat-lihat, kami akhirnya tahu bahwa pantai itu tidak cocok untuk anak-anak bermain-main pasir dan berenang. Ombaknya terlalu tinggi. Mungkin peminatnya lebih banyak para surfer yang biasanya akan lebih senang kalau ombaknya makin tinggi. Kami tidak begitu lama tinggal di sana, dengan tidak lupa mengambil beberapa foto untuk kenangan. Dan ternyata memang, hari sudah mulai sore. Kamipun memutuskan untuk pulang, supaya bisa istirahat lebih cepat. Begitulah sedikit cerita tamasya pantai kami di daerah selatan Pulau Bali.

Travelling Bali Part 1 Direction: Untuk mencapai daerah Nusa Dua, kalau anda berangkat dari arah bandara Ngurah Rai, anda hanya perlu menyusuri ByPass I Gusti Ngurah Rai menuju arah Bukit. Nusa Dua terletak kira-kira 20 km dari Bandara. Ketiga pantai yang kami kunjungi ada di sekitar daerah Nusa Dua. Letak absolut daerah Nusa Dua dapat dilihat dengan membuka peta Pulau Bali melalui thumbnail peta di samping. Letak daerah tersebut tersebut ditandai dengan angka nomor [3].





阿波おどり (Awa Odori: Tari Awa)

22 04 2008

Kemarin malam, nyoba-nyoba printer, yang ada fasilitas fotokopi dan scannernya, untuk fotokopikan tugas Aya dari sekolahnya. Eh saya jadi kelanjutan nyoba-nyoba fasilitas scannernya. Keterusan, akhirnya buka-buka foto album, dan ketemu beberapa foto lama, foto-foto yang diambil sebelum adanya digital camera. Foto-foto waktu di Tokushima dulu, lagi senang-senang di pesta musim panasnya Tokushima, menari Tari Awa (阿波おどり).

Japan - Awa OdoriSedikit cerita, tari Awa (阿波おどり) ini merupakan ciri khas tarian musim panas Tokushima, yang pestanya diadakan setiap tahun selama empat hari sekitar pertengahan bulan Agustus. Biasanya antara tanggal 10-15 Agustus. Tarian ini biasanya dilakukan secara bergrup yang jumlah penarinya bisa mencapai ratusan orang. Cowoknya didandani sedikit ‘macho’ istilahnya, dan yang cewek benar-benar feminim. Beberapa ruas jalan sengaja ditutup untuk memberikan tempat bagi para penari memperlihatkan kebolehannya. Yang paling mengenakkan kalau pesta musim panas sudah mulai mendekat adalah suara musik yang datang dari berbagai penjuru arah, dimana berbagai grup melatih diri untuk mempersiapkan hari H tersebut. Saya sebagai international student waktu itu sering berpartisipasi dengan bergabung pada grup organisasi internasional ataupun grup universitas. Kalau melihat foto-foto yang saya temukan ini, kelihatannya saya sangat menikmati masa-masa itu ya. Sudah cukup lama juga, dan memori itu hampir-hampir hilang rasanya. Tapi melihat foto-foto ini, rasanya terkenang kembali bagaimana saya berinteraksi dengan teman-teman Jepang, dan kalau dilihat di foto yang nari, saya itu kalau gak salah ingat narinya ‘paling depan’ deh. Semangat banget dah waktu itu. Nyoba-nyoba alat musik juga. Foto rame-rame sama teman uni – almamater yang nun jauh di sana. Ah memori yang membuat sedih dan gembira. Gimana ya teman-teman di Jepang sekarang ini.

Japan - Awa OdoriJapan - Awa Odori





CFP: KNS&I2008

21 04 2008

Call For Papers: Konferensi Nasional Sistem & Informatika 2008

Website: http://knsi.stikom-bali.ac.id/(Sudah diperbaiki 😉 )

Email: knsi at stikom-bali dot ac dot id

Invited Speaker: Anto Satriyo Nugroho, DR.Eng (Peneliti BPPT)

Tanggal Penting

* Batas Akhir Penyerahan Full Paper : 26 Juli 2008
* Pengumuman Penerimaan : 30 Agustus 2008
* Batas Akhir Registrasi : 27 September 2008
* Pelaksanaan Seminar : 15 November 2008





Registrasi Penduduk Online Part 2

16 04 2008

Tulisan terdahulu: Registrasi Penduduk Online Part 1.

Kemarin, setelah pulang kantor, saya sempat menonton berita di TV acara The Election Channel yang memberitakan perkembangan persiapan pemilihan kepala daerah provinsi Sumatera Utara. Padahal pemilihan kepada daerah sudah akan dilaksanakan besoknya (hari ini, jadinya ya), penduduk yang mempunyai hak pilih masih bingung dengan tidak adanya kartu pemilih atas nama mereka. Diberitakan di sana bahwa mereka yang tidak ada kartu pemilihnya, tidak pernah terdaftar sebagai penduduk di daerah tersebut. Kelanjutan dari berita tersebut, disebutkan juga, bahwa banyak penduduk yang memiliki kartu pemilih ganda yang mengijinkan mereka untuk melakukan pemilihan di dua tempat yang berbeda atau bahkan mungkin di dua tempat yang sama (kemungkinan ini ada juga). Inilah suatu akibat dari tidak adanya sistem registrasi penduduk yang bersifat online tersebut. Daerah yang satu membuat sistem pencatatan sendiri, begitu juga daerah yang lainnya tanpa ada rasa care terhadap sistem pencatatan yang dilaksanakan di tempat yang lain. Orang bisa tidak mendaftarkan diri sebagai penduduk sama sekali dan orang bisa mendaftarkan diri di dua tempat yang berbeda atau lebih.

Dilihat dari segi biaya, dengan tidak adanya sistem registrasi penduduk online ini, Komisi Pemilihan Umum, dalam tugasnya mempersiapkan kegiatan pemilihan, harus membuat sendiri sistem database pemilih, yang dijadikan dasar untuk menentukan penduduk yang berhak memilih dan penduduk yang tidak. Hitungan kasar saja, biaya yang dikeluarkan bisa dua kali lipat dari biaya yang dikeluarkan kalau sistem registrasi penduduk online ini dibangun. Bukankah ini suatu pemborosan yang bisa dibilang sungguh-sungguh tidak masuk akal?





My K-Means Clustering Page

15 04 2008

I have started a page for k-means clustering algorithm and its variances. Hope it is of any use.