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

Tentang Anto Satriyo Nugroho

My name is Anto Satriyo Nugroho. I am working as research scientist at Center for Information & Communication Technology, Agency for the Assessment & Application of Technology (PTIK-BPPT : Pusat Teknologi Informasi & Komunikasi, Badan Pengkajian dan Penerapan Teknologi). I obtained my doctoral degree (Dr.Eng) from Nagoya Institute of Technology, Japan in 2003. My office is located in Serpong, Tangerang Selatan City. My research is on pattern recognition and image processing with applied field of interests on biometrics identification & development of computer aided diagnosis for Malaria. Should you want to know further information on my academic works, please visit my professional site at http://asnugroho.net
Pos ini dipublikasikan di kernel methods, research. Tandai permalink.

7 Balasan ke Apakah Support Vector Machine itu ?

  1. dewi berkata:

    Hallo Pak Anto,
    saya ingin menanyakan tentang SVM.

    1. Untuk menemukan atau membentuk suatu hyperplane diantara banyak data, bagaimana caranya?

    2.Nilai bias digunakan untuk apa?

    3.Apa kegunaan Lagrange multiplier dalam SVM?

    Terimakasih sekian pertanyaan saya.
    Mohon jawabannya.

  2. Untuk bu Dewi:
    1. Hyperplane itu ditemukan lewat proses training.
    2. Bias pada sebuah linear classifier itu berperan untuk meningkatkan performanya. Kalau bias=0, berarti hyperplane yang dihasilkan akan selalu melewati titik origin. Di dalam praktek hal ini kadang tidak terlalu bermasalah, tetapi keterharusan melewati titik origin ini akan membuat proses learning tidak optimal, karena ada pembatasan yang tidak diperlukan.
    3. Lagrange Multiplier dipakai untuk menyelesaikan masalah optimisasi pada SVM.

  3. yogi berkata:

    Salam kenal bt pak anto dan rekan2 sekalian

    Rasanya menarik sekali diskusi yg ada di blog ini tentang svm. Sy baru aja belajar tentang svm, krn sy lagi berkutat tentang svm pada TA sy.
    Banyak hal yang baru sy ketahui. Jujur sy masih bingung tentang SVM itu sendiri.
    Sy mohon bantuan dari rekan2 sekalian terutama pak anto buat menjawab beberapa pertanyaan saya ini yg masih mendasar tentang svm ini :

    – Bagaimana sy tahu data sy linear atau non-linear? Mhon penjelasan ttg “Pada umumnya data bersifat non-linear”
    – Output data yg dihasilkan oleh SVM dlm proses training itu brupa apa ?
    – Sama kasusnya dengan mas devid ? Bagaimana dengan proses pengklasifikasian oleh SVm pada multiclass. Apakah labelnya masih tetap 1 dgn -1 atau 1,2,3,4,5, dst. Adakah yang bisa menjelaskan tentang multiclass ini lebih lanjut .

    Terima kasih pak anto dan reka2n sekalian

  4. ikhwan berkata:

    mau nanya pak,, saya ingin menerapkan metode SVM untuk penanganan kasus imbalance class dalam TA saya.. beberapa pertanyaan saya:
    1. akurasi untuk prediksi memakai SVM apakah relatif lebih baik jika dibandingkan dengan algoritma klasifikasi lain misalkan C4.5 atau C5.0?
    2. Pada referensi yang saya dapatkan bahwa grafik SVM biasanya digambarkan dalam koordinat x dan y.terus koordinat x dan y itu mengacu pada apa pak?

    terima kasih pak anto…

  5. werty berkata:

    Salam Hormat,

    Saya seorang mahasiswa yang sementara menpuh pendidikan master di India.Saat ini saya sementara menyusun disertasi yang berhubungan dengan SVM.
    Saya mohon bantuan bapak, untuk dapat menjelaskan lebih detail mengenai kelebihan SVM.
    Jika sempat, tolong hubungi saya di alamat email saya diatas. Terima kasih.

    WERTY

  6. Bayu berkata:

    salam kenal buat pak anto dan rekan-rekan sekalian…

    mau tanya pak, apakah semua data bisa menggunakan kernel RBF kalo iya kenapa? kalo tidak untuk data yang seperti apa RBF digunakan?

    kemudian untuk kernel yang lain juga digunakan untuk data seperti apa…mohon penjelasannya…kalo ada referensi bisa disertakan juga…

    terima kasih banyak sebelumnya…

  7. Dadan Shavkat berkata:

    Pak anto saya menerapkan SVM untuk penerapan Data mining…..

    Saya perlu iterasi perhitungan bagaimana data berubah menghasilkan hyperlane dan data keluaran untuk memprediksi fluktuasi sahamnya

    saya ingin tahu bagaimana perubahan data ketika masuk dalam proses algoritmanya…..
    kalo bisa ketemu bapak lebih baik pak….. mohon balasannya

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s