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.
)
Recent Comments