10 - support-vector-machine

Support Vector Machine

Ringkasan

Support Vector Machine (SVM) adalah algoritma supervised learning untuk klasifikasi (dan regresi) yang dikembangkan Guyon, Boser, Vapnik dan diperkenalkan 1992. Prinsipnya: Structural Risk Minimization (SRM) — cari hyperplane terbaik (margin terbesar) yang memisahkan dua kelas; berupa linear classifier yang diperluas lewat kernel trick agar mampu menangani data non-linear. SVM dirancang untuk klasifikasi biner ($y_i\in \{+1,-1\}$); untuk multi-kelas dipakai strategi One-vs-One atau One-vs-Rest.

---

Konsep Kunci

1. SRM dan hyperplane

• Teori berangkat dari kasus linear separable: data $\{x_1,\dots ,x_n\}$ dengan label $y_i\in \{+1,-1\}$; kelas data uji $x$ ditentukan lewat fungsi keputusan.
• Tujuan SRM: hyperplane yang memisahkan ruang input dua kelas dengan generalisasi terbaik (margin maksimal, bukan sekadar memisahkan).
• Persamaan hyperplane: $w\cdot x+b=0$
• Fungsi keputusan: $f(x)={\sum }_{i=1,x_i\in SV}^n{\alpha }_i{y}_{i}K(x,x_i)+b$
• Optimasi (kasus linear): minimalkan $\min \frac{1}{2}\Vert w{\Vert }^2=\frac{1}{2}(w_1^2+w_2^2)$ dengan syarat $y_i(w\cdot x_i+b)\ge 1$ untuk semua data latih.

2. Kernel trick

• Bila data tak separable linear, petakan $x$ ke ruang berdimensi lebih tinggi via $\Phi (x)$ sehingga hyperplane bisa dibangun di sana; perhitungan hanya butuh dot product di ruang baru.
• Karena $\Phi$ sulit dicari eksplisit, menurut Mercer dot product diganti fungsi kernel: $K(x_i,x_j)=\Phi (x_i)\cdot \Phi (x_j)$
• Tabel BKPM menyebut 7 kernel beserta penjelasan parameternya, tetapi baris rumus kosong di ekstraksi teks (hilang saat pdftotext). Rumus di bawah dilengkapi dari sumber web tepercaya [web1][web2][web3] untuk melengkapi materi kampus:

No	Kernel	Rumus
1	Linear	$K(x_i,x_j)=⟨x_i,x_j⟩=x_i^T{x}_j$ — untuk data separable linear [web1]
2	Polinomial derajat $d$	$K(x_i,x_j)=(\gamma ⟨x_i,x_j⟩+r{)}^d$ dengan $d$ = derajat, $r$ ($c$ di BKPM) = bias [web1][web3]
3	Polinomial hingga derajat $d$	$K(x_i,x_j)={\sum }_{k=0}^d(⟨x_i,x_j⟩+c{)}^k$ — memuat semua suku sampai derajat maksimum $d$
4	RBF / Gaussian	$K(x_i,x_j)=\exp (-\gamma \Vert x_i-x_j{\Vert }^2)=\exp (-\Vert x_i-x_j{\Vert }^2/(2{\sigma }^2))$ dengan $\Vert x_i-x_j{\Vert }^2$ jarak Euclidean, $\sigma$ lebar Gaussian ($\gamma =1/(2{\sigma }^2)>0$) [web1][web3]
5	Sigmoid	$K(x_i,x_j)=\tanh (\gamma ⟨x_i,x_j⟩+r)$ dengan $\gamma$ ($\alpha$ di BKPM) skala, $r$ ($c$) bias — mirip aktivasi jaringan saraf [web1][web3]
6	Inverse Multiquadratic	$K(x_i,x_j)=1/\sqrt{\Vert x_i-x_j{\Vert }^2+c^2}$ dengan $c$ konstanta bebas pengontrol kelengkungan [web2]
7	Additive	$K(u,v)={\sum }_{k=1}^n{K}_k(u_k,v_k)$ dengan $n$ jumlah fitur, $K_k$ kernel untuk fitur $k$ [web2]

3. Multi-kelas: OvO vs OvR

• One-vs-One (OvO): untuk kelas A, B, C buat 3 model biner (A–B, A–C, B–C); tiap model hanya tangani 2 kelas → biasanya lebih efisien untuk dataset besar.
• One-vs-Rest (OvR / One-vs-All): tiap kelas dilawan gabungan semua kelas lain (A vs BC, B vs AC, C vs AB); lebih sederhana diimplementasikan, kadang kurang akurat dibanding OvO.

4. Alur praktikum BKPM

• Diberi dataset 2 fitur ($x_1,x_2$) → tulis program Python yang menggambar hyperplane → hyperplane awal program dinyatakan SALAH (arah maupun posisi) → hitung manual $w_1,w_2,b$ lewat formulasi optimasi + syarat, lalu perbaiki program dan gambar ulang dengan support vector ditandai (data merah (3,4), data biru (2,3)).

---

Contoh (dengan perhitungan)

Hitung $w_1=w_2=1$, $b=-6$ → garis $x_2=6-x_1$

Misal $w_1=1$, $w_2=1$. Ambil persamaan support vector (4): $3w_1+4w_2+b\ge 1$:

$3(1)+4(1)+b\ge 1⟹7+b\ge 1⟹b\ge -6$

Ambil persamaan (7): $-2w_1-3w_2-b\ge 1$:

$-2(1)-3(1)-b\ge 1⟹-5-b\ge 1⟹b\ge -6$

Dengan support vector data ke-(4)/(7): $b=-6$. Persamaan hyperplane:

$w_1{x}_1+w_2{x}_2+b=0⟹x_1+x_2-6=0⟹x_2=6-x_1$

Tugas Python (dari BKPM)

Jalankan program SVM yang diberikan; bila kode benar, luaran awal muncul (dengan hyperplane yang salah). Lanjutkan menggambar grafik: support vector merah (3,4) dan biru (2,3), lalu betulkan garis sesuai $x_2=6-x_1$ dan dokumentasikan hasil latihan.

---

Sources

[web1] https://scikit-learn.org/stable/modules/svm.html — Kernel functions (linear, polynomial, RBF, sigmoid) [web2] https://cse.msu.edu/~cse802/S17/slides/Lec_17_Mar27_SVM.pdf — Support Vector Machine and Kernel Methods (MSU) [web3] https://apple.github.io/coremltools/mlmodel/Format/SVM.html — SVM kernel formulas (linear, RBF, poly, sigmoid)

---

Keterkaitan

• Prasyarat klasifikasi: K-Means Clustering (pengelompokan tak terawasi sebagai pembanding paradigma klasifikasi).
• Terkait representasi: Representasi Pengetahuan.
• Mandiri terhadap: Decision Tree ID3 & C4.5 (satu sumber, topik klasifikasi berbeda).