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.


Actions

Information

10 responses

19 06 2014
maya

pak saya boleh minta ebook : N. Cristianini, J.S.Taylor (2000), An Introduction to Support Vector Machine and Other Kernel-Based Learning Methods, Cambridge Press University. ? maya.sridamanik@gmail.com

19 06 2014
Yudi Agusta

Maaf saya tidak punya softcopynya. Mungkin bisa dicari lewat internet atau e-library campusnya. Tks

6 08 2010
willy

terimakasih pak atas penjelasannya..
saya mau sedikit bertanya pak…
bagaimana y pak cara pencarian nilai alpha pada quadratic programming?
kan ada beberpaa metode yang digunakan,salah satunya Sequetial minimal optimization,,,kira2 bapak bisa menjelaskan tentang algoritma tersebut?
terimakasih sebelumnya…:)

31 08 2010
Yudi Agusta

Sequential Minimal Optimization merupakan salah satu metode optimasi untuk SVM yang memecah bentuk Quadratic Programming (QP) yang ada menjadi QP yang lebih kecil agar bisa dicarikan solusi secara analytical. Kelebihan dari metode ini adalah penggunaan memory yang jauh lebih kecil dibanding metode lainnya dan berbanding linier terhadap jumlah data yang dianalisa. Untuk lebih jelasnya paper Platt, J.C. (1999), Fast training of support vector machines using sequential minimal optimization menjelaskannya dengan lebih detail. Di sana juga dimuat perbandingan dengan metode lainnya.

Demikian dan semoga bisa membantu

12 07 2010
windupurnomo

Terimakasih pak… Tugas akhir saya tentang klasifikasi menggunakan SVM, Setelah berpusing2 membaca literatur english :D… Akhirnya dapat disimpulkan dengan membaca poting bapak ini.. Terimakasih..

12 07 2010
Yudi Agusta

Senang, tulisan ini bisa membantu. Tx

11 11 2008
Yudi Agusta

Nanti kalau ada waktu akan saya coba menuliskan. Sementara akhir tahun seperti ini sayanya benar-benar sedang sibuk. Ditunggu saja ya.

6 11 2008
dewi

pak publikasikan tentang svr dunk…
cos TA saya tentang svr..
tapi lieur pisan kpingin baca yang bhs. indo

2 05 2008
Yudi Agusta

Untung sama ya🙂 ……
Ah korban internet, gak tahu siapa yang diajak ngomong …..

2 05 2008
nanda

Capek ngebaca rumus, mendingan nikmatin senyumnya pak yudi, dari pagi sampe sore gak ngebosenin. Kok senyumnya ama Kian Agusta, Jr sama persis, gimana nyetaknya…??? He…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: