🛡️ Support Vector Machine (SVM)

Batas keputusan dengan margin TERLEBAR — dan segelintir titik yang menentukan segalanya.

🎬 Animasi: SVM: Margin Terlebar

SVM mencari garis keputusan dengan margin (jarak) TERLEBAR. Hanya support vector (titik di tepi, berlingkaran) yang menentukan garis.

📌 1. Konsep: Margin Maksimal

Banyak garis bisa memisahkan dua kelas. SVM memilih garis yang paling jauh dari titik-titik terdekat kedua kelas — margin maksimal = paling "aman" terhadap data baru yang mirip.

        o o
       o  o      ← garis mana pun di antara dua kelas
   ════════════════════  ← garis tengah (margin maksimal)
       x  x
        x x

Titik yang "menyentuh" batas margin = SUPPORT VECTOR.
Fakta penting: HAPUS semua titik selain support vector →
garis SVM TIDAK BERUBAH. Model SVM ditentukan oleh segelintir titik!

Fungsi tujuan (yang di-minimize):
    (1/n)·Σ max(0, 1 - yᵢ·(w·xᵢ + b))  +  λ·||w||²
     └──────── HINGE LOSS ────────┘      └─ L2 REGULARISASI ─┘

• Hinge loss: menghukum titik di dalam margin / salah sisi
• λ (atau C = 1/λ): seberapa keras kita menuntut margin
  C besar  → margin dipaksakan (rawan overfit)
  C kecil  → toleran, boundary lebih "lentur"

📌 2. Contoh: Linear SVM + Menemukan Support Vector

print("=== LINEAR SVM (SUBGRADIENT DESCENT) ===\n")
random_seed(42)
X, y = make_classification(80, n_features=2, sep=2.0)
Xb = add_bias(X)
ys = [1.0 if v == 1 else -1.0 for v in y]   # SVM memakai label ±1

def train_svm(Xb, ys, lr=0.05, lam=0.0001, epochs=200):
    w = [0.0] * len(Xb[0])
    n = len(Xb)
    for epoch in range(epochs):
        for i in range(n):
            margin = ys[i] * dot(w, Xb[i])
            if margin < 1.0:
                # subgradien hinge loss
                w = vec_add(w, vec_scale(Xb[i], lr * ys[i] / n))
            # subgradien L2: w *= (1 - 2·lr·λ)
            w = vec_scale(w, 1.0 - 2.0 * lr * lam)
    return w

w = train_svm(Xb, ys)
pred = [1 if dot(w, xb) >= 0 else 0 for xb in Xb]
print("Akurasi = %.1f%%" % (accuracy(y, pred) * 100))
print("Boundary: %.2f + %.2f·x1 + %.2f·x2 = 0" % (w[0], w[1], w[2]))

# ── Support vector: titik dengan margin < 1 ──
sv = [x for x, xb, yi in zip(X, Xb, ys) if yi * dot(w, xb) < 1.0]
print("\nSupport vector: %d dari %d titik!" % (len(sv), len(X)))
for p in sv[:8]:
    print("   (%.2f, %.2f)" % (p[0], p[1]))
print("   → model TIDAK berubah jika titik lain dihapus.")

# ── Visualisasi ──
pts = [(x[0], x[1], "o" if l == 0 else "x") for x, l in zip(X, y)]
for p in sv:
    pts.append((p[0], p[1], "*"))
xg = -2.0
while xg <= 2.0:
    pts.append((xg, -(w[0] + w[1] * xg) / w[2], "+"))
    xg += 0.15
scatter2d(pts, title="o/x = data, + = boundary, * = support vector")

Output:

📌 3. Contoh: Efek Parameter C (Regularisasi)

C = 1/λ mengatur kompromi: memaksakan margin lebar (C besar) vs toleran terhadap titik yang "membandel" (C kecil).

print("=== EFEK PARAMETER C PADA SVM ===\n")
random_seed(42)
X, y = make_classification(100, n_features=2, sep=1.2)  # agak overlap
Xb = add_bias(X)
ys = [1.0 if v == 1 else -1.0 for v in y]

def train_svm(Xb, ys, lr=0.05, lam=0.001, epochs=300):
    w = [0.0] * len(Xb[0])
    n = len(Xb)
    for epoch in range(epochs):
        for i in range(n):
            margin = ys[i] * dot(w, Xb[i])
            if margin < 1.0:
                w = vec_add(w, vec_scale(Xb[i], lr * ys[i] / n))
            w = vec_scale(w, 1.0 - 2.0 * lr * lam)
    return w

print("C      │ akurasi │ #support vector │ ||w||")
print("-" * 52)
for C in [0.01, 0.1, 1.0, 10.0, 100.0]:
    w = train_svm(Xb, ys, lam=1.0 / C)
    pred = [1 if dot(w, xb) >= 0 else 0 for xb in Xb]
    n_sv = sum(1 for xb, yi in zip(Xb, ys) if yi * dot(w, xb) < 1.0)
    norm = math.sqrt(sum(v * v for v in w))
    print("%6.2f │  %5.1f%% │        %3d        │ %.3f"
          % (C, accuracy(y, pred) * 100, n_sv, norm))

print("""
Pola yang terlihat:
• C kecil  → ||w|| besar (margin "tipis"), banyak titik di dalam margin,
             model lebih toleran → generalisasi sering lebih baik.
• C besar → margin dipaksakan lebar, sedikit support vector,
             tapi titik noise bisa "menggeser" boundary (overfit).
• Pilih C dengan validasi (bukan tebak!).""")

Output:

💡 Kernel trick: jika data tidak bisa dipisah garis lurus, SVM "memetakan" data ke dimensi lebih tinggi (polinomial, RBF/Gaussian) sehingga jadi linearly separable di sana. Itulah kenapa SVM kuat di data non-linear — tanpa perlu menulis fitur baru manual.

🧠 Latihan

Di contoh 1, hapus semua titik BUKAN support vector dari training, latih ulang, dan bandingkan garis boundary-nya. Sama persis?
Jelaskan dengan kata-katamu: kenapa margin lebar = lebih robust? (Petunjuk: data baru yang mirip training.)
Buat data make_circles(). Apakah linear SVM bisa mengklasifikasinya dengan baik? Kenapa? (Petunjuk: kernel trick.)
Hitung margin satu titik: margin = y·(w·x + b). Berapa margin titik support vector yang paling "pelanggar"?