Algoritma: Support Vector Machine (SVM)

Support Vector Machine (SVM) adalah salah satu algoritme pembelajaran mesin terawasi yang digunakan untuk klasifikasi dan regresi. Metode ini bekerja dengan mencari hyperplane terbaik yang memisahkan data dari dua kelas atau lebih dengan margin maksimum. SVM dikembangkan berdasarkan konsep teori pembelajaran statistik oleh Vladimir Vapnik dan koleganya pada tahun 1960-an hingga 1990-an. Algoritme ini banyak digunakan dalam berbagai bidang seperti pengolahan citra digital, pengolahan bahasa alami, dan sistem rekomendasi karena kemampuannya menangani data berdimensi tinggi dan bekerja efektif pada dataset yang relatif kecil.

Konsep Dasar

SVM memproyeksikan data ke ruang berdimensi lebih tinggi untuk menemukan pemisah linier yang memaksimalkan jarak (margin) antara kelas. Margin yang besar diharapkan dapat meningkatkan kemampuan generalisasi model. Pada kasus dua dimensi, pemisah ini dapat divisualisasikan sebagai sebuah garis, sedangkan pada dimensi lebih tinggi disebut sebagai hyperplane. Hyperplane optimal memenuhi kriteria: $\mathbf{w}\cdot \mathbf{x}+b=0$ di mana $\mathbf{w}$ adalah vektor bobot, $\mathbf{x}$ adalah vektor fitur, dan $b$ adalah bias.

Margin dan Support Vector

Support vector adalah titik-titik data yang terletak pada batas margin dan menjadi penentu posisi hyperplane. Margin didefinisikan sebagai jarak antara hyperplane dengan support vector terdekat dari masing-masing kelas. Secara matematis, margin dapat dihitung dengan: $\frac{2}{\Vert \mathbf{w}\Vert }$ Semakin besar margin, semakin baik kemampuan model dalam memisahkan data pada data yang belum pernah dilihat sebelumnya.

Kernel Trick

Salah satu kekuatan utama SVM adalah penggunaan metode kernel trick. Dengan kernel, data yang awalnya tidak dapat dipisahkan secara linier dapat dipetakan ke ruang fitur berdimensi lebih tinggi sehingga menjadi linier separable. Beberapa fungsi kernel yang umum digunakan antara lain:

1. Kernel linear: $K({\mathbf{x}}_i,{\mathbf{x}}_j)={\mathbf{x}}_i\cdot {\mathbf{x}}_j$
2. Kernel polinomial: $K({\mathbf{x}}_i,{\mathbf{x}}_j)=(\gamma {\mathbf{x}}_i\cdot {\mathbf{x}}_j+r{)}^d$
3. Kernel RBF: $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\exp (-\gamma \Vert {\mathbf{x}}_i-{\mathbf{x}}_j{\Vert }^2)$
4. Kernel sigmoid: $K({\mathbf{x}}_i,{\mathbf{x}}_j)=\tanh (\gamma {\mathbf{x}}_i\cdot {\mathbf{x}}_j+r)$

Formulasi Matematis

Permasalahan optimisasi SVM dapat dinyatakan sebagai: $\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$ dengan syarat $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)\ge 1$ untuk semua pasangan data $({\mathbf{x}}_i,y_i)$. Dalam kasus data tidak sepenuhnya dapat dipisahkan, parameter pelonggaran (slack variable) ${\xi }_i$ digunakan untuk mengizinkan adanya pelanggaran margin.

SVM Linier dan Non-Linier

SVM linier digunakan ketika data dapat dipisahkan secara linier. Pada kasus yang lebih kompleks di mana data tidak linier separable, digunakan SVM non-linier dengan kernel trick. Pemilihan jenis kernel sangat mempengaruhi kinerja model, dan sering kali dilakukan melalui proses validasi silang.

Parameter dan Tuning

Kinerja SVM dipengaruhi oleh beberapa parameter penting, di antaranya:

1. C: parameter regulasi yang mengendalikan trade-off antara margin besar dan kesalahan klasifikasi.
2. γ (gamma): parameter kernel RBF yang mengatur jarak pengaruh sebuah titik data.
3. d: derajat polinomial untuk kernel polinomial.

Pemilihan parameter optimal biasanya dilakukan melalui pencarian grid (grid search) atau algoritme optimisasi lainnya.

Kelebihan

SVM memiliki sejumlah keunggulan, antara lain:

1. Efektif pada ruang fitur berdimensi tinggi.
2. Tetap bekerja baik ketika jumlah fitur lebih besar daripada jumlah sampel.
3. Memori efisien karena hanya menggunakan support vector pada proses prediksi.
4. Mampu menangani kasus non-linier melalui kernel.

Keterbatasan

Meski memiliki banyak keunggulan, SVM juga memiliki keterbatasan, seperti:

1. Kurang efisien pada dataset yang sangat besar.
2. Pemilihan kernel dan parameter yang tidak tepat dapat menurunkan performa.
3. Tidak secara langsung memberikan probabilitas prediksi, meskipun dapat diestimasi melalui metode kalibrasi.

Aplikasi

SVM digunakan dalam berbagai bidang, antara lain:

1. Pengenalan wajah
2. Klasifikasi teks
3. Bioinformatika untuk klasifikasi sekuens gen
4. Pengolahan citra untuk deteksi objek
5. Sistem rekomendasi berbasis konten

Varian SVM

Beberapa varian dari SVM telah dikembangkan untuk menangani berbagai jenis masalah, seperti:

1. ν-SVM: menggunakan parameter ν untuk mengontrol jumlah support vector.
2. One-class SVM: digunakan untuk deteksi anomali.
3. Least Squares SVM: memformulasikan masalah sebagai persamaan kuadrat.

Kompleksitas Komputasi

Kompleksitas pelatihan SVM bergantung pada jumlah sampel ($n$) dan jumlah fitur ($d$). Pada implementasi klasik, kompleksitasnya dapat mencapai $O(n^3)$, meskipun berbagai optimisasi seperti SMO telah dikembangkan untuk mempercepat proses pelatihan.

Perkembangan dan Penelitian

Penelitian mengenai SVM terus berkembang, termasuk integrasinya dengan deep learning, pengembangan kernel adaptif, dan optimisasi untuk komputasi paralel serta komputasi awan. SVM tetap relevan meskipun model-model pembelajaran mesin lain seperti random forest dan jaringan saraf tiruan semakin populer.

Apabila digunakan dengan pemilihan parameter dan kernel yang tepat, SVM masih menjadi salah satu algoritme yang kompetitif untuk berbagai permasalahan klasifikasi modern.