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.
. 
Kami 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.
Permainan 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.
Setelah 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.
Setelah 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.
Sedikit 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.
)
Recent Comments