Pemahaman Mendalam tentang Mesin Pendukung Vektor (SVM) dalam Pembelajaran Mesin

Dipublikasikan oleh Muhammad Ilham Maulana

02 April 2024, 09.26

Sumber: en.wikipedia.org

Mesin Pendukung Vektor (SVM) atau juga dikenal sebagai jaringan pendukung vektor, merupakan model-model terarah berbasis margin maksimum yang menggunakan algoritma pembelajaran terkait untuk menganalisis data dalam klasifikasi dan analisis regresi. Dikembangkan di Laboratorium Bell AT&T oleh Vladimir Vapnik bersama rekan-rekannya, SVM menjadi salah satu model yang paling banyak dipelajari, didasarkan pada kerangka pembelajaran statistik atau teori VC yang diusulkan oleh Vapnik dan Chervonenkis.

Selain melakukan klasifikasi linear, SVM dapat secara efisien melakukan klasifikasi non-linear menggunakan apa yang disebut trik kernel, dengan secara implisit memetakan inputnya ke dalam ruang fitur berdimensi tinggi. SVM juga dapat digunakan untuk tugas regresi, di mana tujuannya adalah menjadi {\displaystyle \epsilon }-sensitive.

Algoritma pengelompokan vektor pendukung, yang dibuat oleh Hava Siegelmann dan Vladimir Vapnik, menerapkan statistik vektor pendukung yang dikembangkan dalam algoritma mesin pendukung vektor untuk mengategorikan data tanpa label. Dataset ini memerlukan pendekatan pembelajaran tanpa pengawasan, yang mencoba untuk menemukan pengelompokan alami dari data ke dalam kelompok-kelompok, dan kemudian memetakan data baru sesuai dengan kelompok-kelompok ini.

Populeritas SVM mungkin disebabkan oleh kemampuannya untuk analisis teoritis, fleksibilitasnya dalam diterapkan pada berbagai macam tugas, termasuk masalah prediksi terstruktur. Namun, belum jelas apakah SVM memiliki kinerja prediksi yang lebih baik daripada model linear lainnya, seperti regresi logistik dan regresi linear.

Motivasi

Klasifikasi data adalah tugas umum dalam pembelajaran mesin. Anggaplah beberapa titik data yang diberikan masing-masing termasuk ke dalam salah satu dari dua kelas, dan tujuannya adalah untuk menentukan kelas mana titik data baru akan berada. Dalam kasus mesin pendukung vektor, sebuah titik data dilihat sebagai vektor berdimensi-p (sebuah daftar dari p angka), dan kita ingin tahu apakah kita dapat memisahkan titik-titik tersebut dengan sebuah hiperplan berdimensi-(p-1). Ini disebut sebagai klasifikasi linear. Ada banyak hiperplan yang dapat mengklasifikasikan data. Salah satu pilihan yang masuk akal sebagai hiperplan terbaik adalah yang mewakili pemisahan terbesar, atau margin, antara dua kelas. Jadi kita memilih hiperplan sehingga jarak dari hiperplan tersebut ke titik data terdekat di setiap sisi maksimum. Jika hiperplan semacam itu ada, dikenal sebagai hiperplan margin maksimum dan klasifikasi linear yang didefinisikan olehnya dikenal sebagai klasifikasi margin maksimum; atau setara, perceptron kestabilan optimal.

Secara lebih formal, sebuah mesin pendukung vektor membangun sebuah hiperplan atau serangkaian hiperplan dalam ruang berdimensi tinggi atau tak terbatas, yang dapat digunakan untuk klasifikasi, regresi, atau tugas lain seperti deteksi outliers. Secara intuitif, pemisahan yang baik dicapai oleh hiperplan yang memiliki jarak terbesar ke titik data pelatihan terdekat dari setiap kelas (yang disebut margin fungsional), karena pada umumnya semakin besar margin, semakin rendah kesalahan generalisasi klasifier. Kesalahan generalisasi yang lebih rendah berarti bahwa pengimplementasi kurang mungkin mengalami overfitting.

Sementara masalah asli mungkin dinyatakan dalam ruang berdimensi terbatas, sering kali terjadi bahwa set yang akan dipisahkan tidak dapat dipisahkan secara linear dalam ruang tersebut. Oleh karena itu, diusulkan bahwa ruang berdimensi terbatas asli tersebut dipetakan ke dalam ruang berdimensi yang jauh lebih tinggi, dengan harapan membuat pemisahan lebih mudah dalam ruang tersebut. Untuk menjaga beban komputasi yang wajar, pemetaan yang digunakan oleh skema SVM dirancang untuk memastikan bahwa perkalian dot dari pasangan vektor data input dapat dengan mudah dihitung dalam hal variabel-variabel dalam ruang asli, dengan mendefinisikan mereka dalam hal sebuah fungsi kernel k(x, y) yang dipilih sesuai dengan masalah. Hiperplan dalam ruang berdimensi tinggi tersebut didefinisikan sebagai set titik-titik yang perkalian dot-nya dengan sebuah vektor di ruang tersebut konstan, di mana sebuah set vektor tersebut adalah set vektor ortogonal (dan oleh karena itu minimal) yang mendefinisikan sebuah hiperplan. Vektor-vektor yang mendefinisikan hiperplan dapat dipilih sebagai kombinasi linear dengan parameter ai dari gambar vektor fitur {\displaystyle x_{i}}yang terjadi dalam basis data. Dengan pemilihan hiperplan seperti ini, titik-titik x di ruang fitur yang dipetakan ke dalam hiperplan didefinisikan oleh relasi {\displaystyle \textstyle \sum _{i}\alpha _{i}k(x_{i},x)={\text{constant}}.}. Perlu diperhatikan bahwa jika k(x, y) menjadi kecil saat y semakin jauh dari x, setiap term dalam jumlah tersebut mengukur tingkat kedekatan titik uji x ke titik basis data {\displaystyle x_{i}} yang sesuai. Dengan cara ini, jumlah kernel di atas dapat digunakan untuk mengukur kedekatan relatif setiap titik uji ke titik data yang berasal dari salah satu dari dua set yang akan dipisahkan. Perhatikan fakta bahwa set titik x yang dipetakan ke dalam hiperplan apa pun dapat sangat bercabang sebagai hasilnya, memungkinkan pemisahan yang jauh lebih kompleks antara set yang sama sekali tidak konveks dalam ruang asli.

Aplikasi Algoritma SVM

SVM dapat digunakan untuk menyelesaikan berbagai masalah dunia nyata:

  1. SVM membantu dalam kategorisasi teks dan hiperteks, karena aplikasinya dapat secara signifikan mengurangi kebutuhan akan contoh pelatihan yang diberi label dalam kedua pengaturan induktif dan transduktif. Beberapa metode untuk parsing semantik dangkal didasarkan pada mesin pendukung vektor.

  2. Klasifikasi gambar juga dapat dilakukan menggunakan SVM. Hasil eksperimental menunjukkan bahwa SVM mencapai akurasi pencarian yang jauh lebih tinggi daripada skema penyempurnaan kueri tradisional setelah hanya tiga hingga empat putaran umpan balik relevansi. Hal ini juga berlaku untuk sistem segmentasi gambar, termasuk yang menggunakan versi SVM yang dimodifikasi dengan pendekatan istimewa seperti yang disarankan oleh Vapnik.

  3. Klasifikasi data satelit seperti data SAR menggunakan SVM yang diawasi.

  4. Karakter tulisan tangan dapat dikenali menggunakan SVM.

  5. Algoritma SVM telah banyak diterapkan dalam bidang biologi dan ilmu lainnya. Mereka telah digunakan untuk mengklasifikasikan protein dengan hingga 90% senyawa diklasifikasikan dengan benar. Uji permutasi berdasarkan bobot SVM telah disarankan sebagai mekanisme untuk interpretasi model SVM. Bobot mesin pendukung vektor juga telah digunakan untuk menginterpretasikan model SVM di masa lalu. Interpretasi pasca hoc dari model mesin pendukung vektor untuk mengidentifikasi fitur-fitur yang digunakan oleh model untuk membuat prediksi adalah area penelitian yang relatif baru namun memiliki signifikansi khusus dalam ilmu biologi.

Sejarah Algoritma SVM

Algoritma SVM asli ditemukan oleh Vladimir N. Vapnik dan Alexey Ya. Chervonenkis pada tahun 1964. Pada tahun 1992, Bernhard Boser, Isabelle Guyon, dan Vladimir Vapnik mengusulkan cara untuk membuat klasifikasi non-linear dengan menerapkan trik kernel pada hiperplan margin maksimum. Versi "marginal lembut", seperti yang umum digunakan dalam paket perangkat lunak, diusulkan oleh Corinna Cortes dan Vapnik pada tahun 1993 dan diterbitkan pada tahun 1995.

Implementasi

Parameter dari hiperplan margin maksimum diperoleh dengan memecahkan optimasi. Ada beberapa algoritma khusus untuk dengan cepat memecahkan masalah pemrograman kuadrat (QP) yang muncul dari SVM, sebagian besar mengandalkan heuristik untuk memecah masalah menjadi bagian-bagian yang lebih kecil dan lebih mudah dikelola.

Pendekatan lain adalah menggunakan metode titik dalam yang menggunakan iterasi mirip Newton untuk menemukan solusi dari kondisi Karush–Kuhn–Tucker dari masalah primer dan dual. Alih-alih memecahkan rangkaian masalah yang dipecahkan, pendekatan ini langsung memecahkan masalah secara keseluruhan. Untuk menghindari memecahkan sistem linear yang melibatkan matriks kernel besar, pendekatan ini sering menggunakan aproksimasi peringkat rendah untuk matriks dalam trik kernel.

Metode umum lainnya adalah algoritma optimasi minimal sekuen Platt (SMO), yang memecah masalah menjadi sub-masalah 2 dimensi yang dipecahkan secara analitis, menghilangkan kebutuhan akan algoritma optimasi numerik dan penyimpanan matriks. Algoritma ini secara konseptual sederhana, mudah diimplementasikan, umumnya lebih cepat, dan memiliki sifat scaling yang lebih baik untuk masalah SVM yang sulit.

Kasus khusus dari mesin pendukung vektor linier dapat dipecahkan secara lebih efisien dengan jenis algoritma yang sama yang digunakan untuk mengoptimalkan kerabat dekatnya, regresi logistik; kelas algoritma ini termasuk gradien sub-descent (misalnya, PEGASOS) dan desent koordinat (misalnya, LIBLINEAR). LIBLINEAR memiliki beberapa sifat menarik saat pelatihan. Setiap iterasi konvergensi membutuhkan waktu linear dalam waktu yang dibutuhkan untuk membaca data latih, dan iterasi juga memiliki sifat konvergensi Q-linear, membuat algoritma sangat cepat.

SVM kernel umum juga dapat dipecahkan secara lebih efisien menggunakan gradien sub-descent (misalnya, P-packSVM), terutama ketika paralelisasi diizinkan.

SVM kernel tersedia dalam banyak toolkit pembelajaran mesin, termasuk LIBSVM, MATLAB, SAS, SVMlight, kernlab, scikit-learn, Shogun, Weka, Shark, JKernelMachines, OpenCV, dan lainnya.

Pra-pemrosesan data (standarisasi) sangat dianjurkan untuk meningkatkan akurasi klasifikasi. Ada beberapa metode standarisasi, seperti min-max, normalisasi dengan skala desimal, Z-score. Pengurangan rata-rata dan pembagian dengan varians setiap fitur biasanya digunakan untuk SVM.


Disadur dari: en.wikipedia.org/wiki/Support_vector_machine