Apakah Support Vector Machine itu ?

Di milis sc-ina ada diskusi menarik mengenai SVM. Kebetulan Philips yg presentasi, dan banyak masukan bagus. Sementara saya copy and paste saja di sini. Kalau sudah punya waktu baru akan saya edit lagi.

1. Denny :
   Apa perbedaan dan persamaan antara SVM dengan Perceptron, khususnya dalam permasalahan classifier ?
2. Anto :
   Pertama kita batasi pada model klasifikasi linier, jadi linier perceptron vs linier SVM. Proses training pada kedua classifier pada prinsipnya bertujuan mencari “batas” pemisah antara dua buah class/category di ruang vektor. Yang membedakan kedua buah model di atas adalah prinsip yang dipakai untuk menemukan batas pemisah (separating hyperplane) tersebut. Pada perceptron, fungsi klasifikasi dinyatakan dalam primal form, yhaitu persamaan yang melibatkan weights/bobot (tepatnya dot product antara data dan weight) Weights ini sebenarnya tidak lain merepresentasikan posisi hyperplane itu pada ruang vektor. Proses training pada perceptron berjalan dengan mengoreksi nilai weights secara berulang, sedemikian hingga kedua buah kelas dapat dipisahkan secara sempurna oleh hyperplane itu. Weight ini adalah hasil akhir dari proses pembelajaran pada perceptron.

   Adapun pada SVM, tujuan dari proses training adalah untuk mencari posisi optimal dari hyperplane itu di ruang vektor. Dalam hal ini parameter yang dipakai adalah “margin” yaitu jarak dari separating hyperplane ke dua buah kelas. Hasil perhitungan menunjukkan, bahwa hyperplane yang terbaik dicapai dengan memaksimalkan nilai margin. Posisi ini tercapai jika hyperplane itu terletak tepat di tengah-tengah, memisahkan kedua buah kelas. Pada SVM, fungsi klasifikasi dinyatakan dalam dual form, yaitu dinyatakan sebagai fungsi dari data training, bukan weights. Proses training SVM sebagaimana dijelaskan diatas, bertujuan mencari data mana dari training set yang “paling informatif”. Subset dari training set inilah hasil akhir dari training tsb. dan disebut dengan Support Vektor. Di ruang vektor, support vektor ini adalah data dari kedua buah kategori yang terletak paling dekat dengan separating hyperplane.

   Untuk non linear problem, perceptron harus menambahkan satu layer lagi (hidden layer) agar bisa menemukan hyperplane tersebut secara non linear. Dalam hal ini proses pembelajaran yg populer antara lain backpropagation.

   SVM pada prinsipnya adalah linear classifier. Tetapi SVM bisa juga dipakai untuk non linear problem, dengan dua tahap. Pertama-tama data diproyeksikan ke ruang vektor baru berdimensi tinggi sedemikian hingga data itu dapat terpisah secara linier. Baru selanjutnya, di “dunia baru” itu, SVM mencari hyperplane optimal dengan cara yang sama sebagaimana di atas, yaitu bekerja sebagai linear machine. Ini didukung oleh teori Cover, yang menyatakan bahwa suatu ruang vektor dapat ditransformasikan ke ruang vektor baru yang pada probabilitas tinggi dapat terpisah secara linear, jika memenuhi dua syarat :
   (i) transformasi itu non linear
   (ii) dimensi ruang vektor yang baru itu cukup tinggi.
   Fungsi klasifikasi pada SVM dinyatakan sebagai dual form, yang melibatkan dot product antara data pada training set. Dengan demikian, proses pencarian hyperplane optimal di “dunia baru” melibatkan dot product dari data yang
   sudah diproyeksikan ke “dunia” tersebut. Di sinilah muncul konsep “kernel trick”, yaitu menghitung nilai dot product dua buah data di “dunia baru” itu, secara implisit.
   Maksudnya tanpa perlu mengetahui bagaimana wujud dari fungsi tranformasi itu.

3. Yudi :
   Bisa gak saya mendapatkan penjelasan lebih detail mengenai “menghitung
   nilai dot product secara implisit” yang dijelaskan di bagian akhir penjelasan yang diberikan.
4. Philips :
   tentang SVM vs perceptron, ini menarik. Kalo saya bisa bilang bahwa SVM lebih memiliki kemampuan generalisasi yang lebih baik daripada neural network (saya sebut NN sebagai generalisasi perceptron karena pada dasarnya perceptron hanya bisa untuk linear separable problem). Hal ini karena SVM mencari bidang pemisah yang optimal yaitu bidang yang tepat berada ditengah-tengah yang memisahkan dua kelas, berbeda dengan NN yang hanya mencari bidang yang memisahkan saja. Asal dapat memperoleh bidang yang bisa memisahkan, maka proses traning akan berakhir. Karena itu yang sangat sering terjadi pada NN adalah overfitting, baik sekali pada training tetapi tidak baik pada penggunaannya.
   Satu lagi yang menjadi kelebihan SVM dibanding parameter. SVM hanya memerlukan parameter kernel (tergantung fungsi kernel biasanya 1-2 parameter) dan satu lagi parameter bobot yang menyeimbangkan error dengan bidang pemisah. Jadi hanya perlu dua atau tiga parameter saja. Sedangkan pada NN, banyak hal yang harus dipikirkan. Jumlah hidden layer, neuron untuk hidden layer, belum lagi metode untuk training yang jelas pasti ada parameter lagi untuk itu. Search spacenya menjadi jauh lebih luas.

   Tentang “kernel trick”, yang secara implisit melakukan transformasi ke ruang berdimensi lebih tinggi. Ini maksudnya bahwa dengan menggunakan fungsi kernel, kita tidak perlu mengetahui secara detil wujud transformasi ke ruang dimensi yang lebih tinggi. Bagaimana cara mapping satu per satu suatu titik sehingga berada pada suatu titik pada dimensi yang lebih tinggi tidak perlu diketahui. Umumnya data akan diubah ke dimensi ruang yang jauh lebih tinggi daripada dimensi aslinya (beberapa puluh bahkan bisa beberapa ratus). Dan, semua itu cukup dilakukan dengan menggunakan fungsi kernel. Yg penting di sini adalah data bisa pada data dipisahkan secara linear pada dimensi ruang yang lebih tinggi.

5. Anto :
   Mengenai perhitungan implisit sudah benar seperti yg dijelaskan Philips. Saya coba untuk menambahkan dengan formulasinya. Decision function pada SVM memerlukan perhitungan dot product dari datanya : <x_i,x_j> Saat diproyeksikan ke ruang vektor berdimensi tinggi, perhitungan tsb. tentunya akan berubah menjadi < H(x_i) , H(x_j) > dimana H adalah fungsi yang mentransformasikan data awal x_i ke ruang vektor berdimensi tinggi. Biasanya untuk menyelesaikan hitungan seperti ini, kita harus menghitung terlebih dahulu nilai H(x_i) dan H(x_j), baru kemudian menghitung dot product-nya. Dengan kata lain fungsi H harus didefinisikan terlebih dahulu. Tetapi dalam SVM, hal ini tidak diperlukan. Fungsi H
   tidak perlu diketahui. Kita bisa menghitung < H(x_i) , H(x_j) > dengan tetap memakai x_i dan x_j, dimasukkan pada fungsi yg disebut fungsi Kernel. Hal itu yang disebut dengan “kernel trick”, menghitung dot product di “dunia baru”, secara implisit. Beberapa fungsi kernel yang populer, antara lain : Gaussian kernel, Polynomial kernel dan Sigmoid kernel. Proses tuning parameter di neural network (MLP-BP) dilakukan dengan memvariasi banyaknya hidden neuron, nilai learning rate, momentum, stopping criterion, dsb. Di SVM hal ini digantikan menjadi upaya memilih fungsi kernel yang optimal.

   Sebenarnya konsep kernel ini bukan hal yang baru, dan dibahas oleh Aizerman di tahun 1964. Tetapi tidak banyak yang memperhatikan konsep ini, sampai Boser, Guyon dan Vapnik memakainya dalam paper SVM mereka tahun 1992. Konsep SVM, kalau dari penjelasan yg saya baca, sebenarnya adalah kombinasi harmonis dari teori-teori di statistik jaman dulu.

6. Yudi :
   Terimakasih banyak atas penjelasannya. Lebih cerah sekarang di pikiran
   saya tentang konsep SVM ini. Dulu pernah baca-baca, tapi begitu masalah optimasinya, banyak kabutnya. Saya ingin menanyakan satu hal lagi. Dalam menyelesaikan suatu permasalahan dengan SVM, dari apa yang telah dijelaskan (kalau saya tidak salah mengerti), ada suatu tahapan pemilihan kernel. Saya ingin menanyakan, bagaimana cara memilih kernel yang paling sesuai dengan permasalahan yang sedang dianalisa? Ada gak kriteria khusus yang bisa dijadikan alat evaluasi kesesuaian kernel yang dipilih?
7. Budi :
   Saya mau menambahkan sedikit saja tentang perceptron vs SVM. Kalau Pak Anto dan Philips menjelaskan perbedaannya. Saya tambahkan ada juga persamaannya. Perceptron (multi layer) akan menggunakan fungsi aktivasi (transfer function) yang bisa linear ataupun nonlinear dalam angka mendapatkan bobot dari classifier yang mampu memisahkan data ke dalam kelas yg sesuai. Ini mirip dengan pemakaian kernel function dlm SVM yg tujuannya membuat data menjadi linearly seprable di “feature space”.

   Untuk perbedaan ada tambahan lagi. Dalam perceptron (ANN), solusi untuk w(bobot) dan b(bias) merupakan local minimum dari cost function(biasanya nonlinear) yg cukup utk memisahkan data ke dalam kelas yg sesuai dengan cara iterative. Sedangkan dlm SVM solusi w dan b (yg dinyatakan dengan lagrange multiplier dalam alpha) adalah global optimal dari quadratic programming yg merupakan formulasi matematik dr SVM. Dlm ANN setiap kali running, bisa mencapai local mimimum yg berbeda (w dan b berbeda), dalm SVM selalu converge ke solusi yg sama. Shg dalam ANN kita hrs running desain kita beberapa kali untuk mendapatkan solusi terbaik atau diambil w dan b rata-rata. Sedangkan dlm svm sekali running sdh cukup karena solusi yg didapat akan selalu sama utk pilihan kernel dan parameter yg sama.

   Utk Pak Yudi, Sampai skrng blm ada pedoman utk memilih kernel terbaik. Tapi kalau kita tahu anatomi datanya mungkin bisa membantu. Misalnya datanya linearly, kita pilih saja kernel linear, atau kalu bentuknya spt bel kita pilih rbf, dst.Walaupun SVM sangat populer dan menjadi primadona, masih ada hal-hal yg hrs dilakukan dgn mencoba-coba, spt pilihan kernel, constanta cost C dan parameter kernelnya.

8. Yudi :
   Saya tidak bisa membayangkan bahwa sebelum kita bisa melakukan proses
   pengklasifikasian dengan SVM, kita harus mengamati anatomi datanya terlebih dahulu. Kalau memang seperti ini, istilahnya kita melakukan dua kali penganalisaan: melihat anatomi data dan pemodelan dengan SVM. Benar begitu gak Mas Budi?
   Untuk parameter kernelnya, apakah kita juga harus mencoba-cobanya? Sepanjang yang saya tahu Gaussian sudah punya parameter yang tetap. Mungkin yang direfer ke sini kernel-kernel seperti yang menggunakan fungsi polynomial ya?
9. Budi :
   Mas Yudi, Ya pada kenyataanya kita tidak pernah melihat bagaimana pola datanya, kecuali masalah regresi yg outputnya mudah diplot dlm dua dimensi. Pokoknya tersedia data input dan output, kita masukkan pilihan kernel dan kita mainkan nilai parameternya utk mendapatkan misclassification error terbaik.

   Dalam kernel rbf (gaussian) kita puya parameter spread yg nilainya juga kita “tune” untuk mendapatkan performansi classifer yg terbaik. Dr Lin memberi cara otomatsi utk mendapatkan spread terbaik. Begitu juga least squares SVM (LS-SVM,Suykens), memberikan code utk mendapatkan spread terbaik. Tetapi saya pernah mencoba spread yg dihasilkan tdk selalu memberi misclassification error terkecil.

   Jadi bisa saya simpulkan kernel dan parameter dipilih dgn metoda trial and error alias coba2. Mungkin ada teman-teman di sini yg membuktikan bahwa spread yg terpilih dr LIBSVM-nya Dr Lin atau LS-SVM(Suykens) adalah terbaik?

10. Yudi :
    Misalnya kalau Gaussian, nilai parameternya kita estimasi dulu atau langsung dicoba-coba dengan memberikan nilai tertentu. Estimasi dalam artian mencari nilai yang paling cocok dari data yang tersedia. Kalau untuk yang estimasi, saya bisa mengusulkan untuk menggunakan metode Minimum Message Length sebagai dasar estimasi. Karena dari apa yang saya tahu, metode ini superior terhadap metode lainnya.
11. Anto :
    Ada beberapa paper yang membahas bagaimana kita melakukan parameter
    tuning untuk SVM. Di antaranya :
    1) http://www.hpl.hp.com/techreports/2002/HPL-2002-354R1.pdf
    2) O. Chapelle, V. Vapnik, O. Bousquet, and S. Mukherjee. Choosing
    multiple parameters for support vector machines. Machine Learning,
    Vol.46, No.1-3, pp.131-159, 2002 (Paper dapat didownload dari
    http://citeseer.ist.psu.edu/chapelle01choosing.html )
12. Anto :
    Rekan-rekan yth.
    Kolokium Philips kali ini menarik sekali dan dapat memancing semua rekan untuk turut nimbrung diskusi dan belajar bersama –> thanks to Philips.
    Masih dalam “suasana” membandingkan SVM dan Perceptron, ternyata ada salah satu paper yang “mendebat” anggapan yang berlaku bahwa SVM senantiasa lebih superior daripada perceptron. Papernya tidak terlalu panjang, 2 halaman lebih sedikit.

    S. Raudys, “How good are Support Vector Machines ?”, Neural Networks
    Vol.13, No.11, pp.17-19, Elsevier Science, 2000
    [Abstract]
    Support vector (SV) machines are useful tools to classify populations characterized by abrupt decreases in density functions. At least for one class of Gaussian data model the SV classifier is not an optimal one according to a mean generalization error criterion. In real world problems, we have neither Gaussian populations nor data with sharp linear boundaries. Thus, the SV (maximal margin) classifiers can lose
    against other methods where more than a fixed number of supporting vectors contribute in determining the final weights of the classification and prediction rules. A good alternative to the linear SV machine is a specially trained and optimally stopped SLP in a transformed feature space obtained after decorrelating and scaling the multivariate data.

13. Budi :
    Kok saya tidak menemukan dlm teks apa itu slp ya pak?
    Saya setuju bahwa SVM tdk selalu outperforms ANN. Karena bbrp percobaan
    telah membuktikan itu, termasuk saya sendiri.
14. Anto :
    Wah, iya. Reviewer dan author paper ini nggak teliti ya…hehehe. Mestinya singkatan yg tidak lazim, harus ditulis kepanjangannya saat muncul pertama kali. Di halaman kedua ada penjelasannya : SLP yg dimaksud adalah Single Layer Perceptron. Author-nya merefer ke papernya th.98 di Neural Networks. Raudys, S (1998). Evolution and generalization of a single neurone. I. SLP as seven statistical classifiers. Neural Networks, 11 (2)

Iklan