Support Vector Machines & Kernel Trick: Matematika di Balik Maximum Margin Classifier

Support Vector Machine (SVM) adalah salah satu algoritma paling elegan dalam machine learning. Ia mencari hyperplane optimal yang memisahkan dua kelas dengan margin maksimum.

Artikel ini mengupas SVM dari dasar matematis — functional margin, geometric margin, primal & dual optimization, hingga kernel trick.

Margin: Functional vs Geometric

Setup

Binary classification: y ∈ {-1, +1}, classifier: h(x) = sign(wᵀx + b)

Functional Margin

Untuk satu training example:

1
γ̂(i) = y(i) · (wᵀx(i) + b)

γ̂ > 0 → klasifikasi benar
γ̂ besar → confidence tinggi

Masalah: functional margin bisa diskalakan seenaknya (kalikan w dan b dengan 2 → margin jadi 2× tanpa mengubah decision boundary).

Geometric Margin

Jarak Euclidean dari data point ke decision boundary:

1
γ(i) = y(i) · (wᵀx(i) + b) / ||w||

Ini adalah jarak geometris sesungguhnya — tidak berubah jika w dan b diskalakan.

Maximum Margin Classifier

Tujuan: cari hyperplane yang memaksimalkan geometric margin:

1
max_γ,w,b  γ
2
s.t.       y(i)(wᵀx(i) + b) ≥ γ,  i=1,...,m
3
           ||w|| = 1

Optimisasi: Primal Problem

Dengan manipulasi matematis, ini ekuivalen dengan:

1
min_w,b  ½||w||²
2
s.t.     y(i)(wᵀx(i) + b) ≥ 1,  i=1,...,m

Ini adalah convex optimization problem — ada solusi global tunggal!

Lagrange Duality

Lagrangian

1
L(w, b, α) = ½||w||² - ∑αᵢ[y(i)(wᵀx(i) + b) - 1]

Dimana αᵢ ≥ 0 adalah Lagrange multipliers.

Dual Problem

Setelah menyelesaikan kondisi KKT:

1
max_α  ∑αᵢ - ½∑∑αᵢαⱼy(i)y(j)(x(i))ᵀx(j)
2
s.t.   αᵢ ≥ 0
3
       ∑αᵢy(i) = 0

Mengapa dual?

Dimensi: N variabel (αᵢ) vs n+1 (w,b)
Kernel trick: hanya butuh inner product (x(i))ᵀx(j)

Support Vectors

Setelah optimasi, hanya data points dengan αᵢ > 0 yang mempengaruhi decision boundary — inilah support vectors:

1
w = ∑αᵢy(i)x(i)   (hanya untuk αᵢ > 0)

Mayoritas αᵢ = 0! Hanya beberapa titik — yang paling sulit diklasifikasi — menjadi support vectors.

Soft-Margin SVM (Outlier Handling)

Untuk data yang tidak perfectly separable, kita izinkan beberapa kesalahan:

1
min  ½||w||² + C·∑ξᵢ
2
s.t. y(i)(wᵀx(i) + b) ≥ 1 - ξᵢ,  ξᵢ ≥ 0

C kecil → toleransi tinggi, margin lebar, high bias
C besar → toleransi rendah, margin sempit, high variance

C adalah regularization parameter — mengontrol trade-off antara margin lebar dan kesalahan klasifikasi.

The Kernel Trick

Ide

Ketika data tidak linearly separable, kita bisa memetakan ke higher-dimensional space:

1
x → φ(x)

Tapi menghitung φ(x) untuk dimensi tinggi mahal. Solusi: kernel trick.

Kernel Function

1
K(x, z) = ⟨φ(x), φ(z)⟩

Kita tidak perlu menghitung φ(x) secara eksplisit — cukup evaluasi K(x,z)!

Kernel Populer

Kernel	Formula	Parameter
Linear	K(x,z) = xᵀz	-
Polynomial	K(x,z) = (xᵀz + c)ᵈ	d=degree, c=constant
Gaussian/RBF	K(x,z) = exp(-γ
Sigmoid	K(x,z) = tanh(κxᵀz + c)	κ, c

Gaussian Kernel: Implisit Infinite-Dimensional

Gaussian kernel bisa diekspansi:

1
exp(-||x-z||²/2σ²) = exp(-xᵀx/2σ²) · exp(-zᵀz/2σ²) · ∑(xᵀz/k!σ²ᵏ)

Ini ekuivalen dengan infinite-dimensional feature space! Inilah kekuatan kernel trick.

SVM dengan Kernel dalam Praktik

1
from sklearn.svm import SVC
2

3
# Linear SVM
4
model = SVC(kernel='linear', C=1.0)
5

6
# RBF SVM
7
model = SVC(kernel='rbf', C=1.0, gamma='scale')
8

9
# Polynomial SVM
10
model = SVC(kernel='poly', degree=3, C=1.0)
11

12
model.fit(X_train, y_train)
13
accuracy = model.score(X_test, y_test)

SVM vs Logistic Regression vs Neural Networks

	SVM	Logistic Reg.	Neural Net
Interpretasi	Geometris	Probabilistik	Black-box
Non-linear	Via kernel	Via feature engineering	Via architecture
Data efficiency	Baik	Sangat baik	Butuh banyak data
Training speed	O(m²) - O(m³)	O(mn)	O(epochs·m·params)
Multi-class	One-vs-all/rest	Softmax (native)	Native

Kesimpulan

SVM adalah masterpiece matematis — dari geometric intuition tentang margin, dual optimization yang elegan, sampai kernel trick yang membuka dimensi tak terbatas. Meskipun deep learning mendominasi, SVM tetap relevan untuk dataset kecil-menengah, terutama ketika interpretabilitas geometris penting.

Di artikel selanjutnya: Decision Trees, Random Forest, dan Ensemble Methods.

Referensi: Ng, A. & Ma, T. (2023). CS229 Lecture Notes. Stanford University.

Thanks for reading!

Support Vector Machines & Kernel Trick: Matematika di Balik Maximum Margin Classifier

Wed Jun 24 2026

488 words · 3 minutes

Teknologi MachineLearning SVM Kernel SupportVectorMachine Optimasi CS229 Matematika DataScience