KAL
Menu

Support Vector Machine dan Kernel

Support vector machine dengan margin maksimum serta kernel trick di scikit-learn.

Daftar isi

Support vector machine, disingkat SVM, adalah model klasifikasi yang memilih pemisah antar kelas dari titik-titik tepi, bukan dari rata-rata kelasnya. Topik ini membahas ide margin maksimum sebagai inti model, peran support vector sebagai penentu batas keputusan, hyperparameter C sebagai toleransi pelanggaran margin, dan kernel trick yang memperluas model ke batas pemisah melengkung. Praktiknya membandingkan tiga varian SVC dari scikit-learn pada dataset dua bulan yang saling menjulur, lalu membaca gejala overfitting dari skor dan jumlah support vector.

Margin maksimum dan support vectors#

Untuk data dua kelas yang terpisah oleh garis, terdapat banyak pemisah yang benar. SVM memilih yang paling aman, yaitu hyperplane atau bidang pemisah yang berjarak paling jauh dari titik terdekat setiap kelas. Jarak dari hyperplane ke titik terdekat pada kedua sisinya disebut margin. Pada fungsi keputusan f(x)=w⊤x+bf(x) = w^\top x + b, lebar margin sebanding dengan 1∥w∥\frac{1}{\lVert w \rVert}. Memaksimalkan margin berarti mengecilkan ∥w∥\lVert w \rVert, dan pemisah dengan margin terlebar cenderung menggeneralisasi lebih baik karena tidak menempel pada salah satu kelas.

Titik-titik terdekat yang letaknya tepat pada tepi margin inilah yang disebut support vectors, dan hanya titik-titik tersebut yang menentukan solusi akhir. Memindahkan sampel lain yang jauh dari margin sama sekali tidak mengubah batas keputusan. Sifat ini membedakan SVM dari model yang menyesuaikan diri terhadap seluruh sampel, karena solusi SVM tidak dipengaruhi oleh keseluruhan sebaran data. Margin yang lebar juga memberi ruang aman bagi sampel baru, karena sampel yang bergeser sedikit dari posisi latihnya tidak serta-merta menyeberang ke kelas lain.

Hyperparameter C sebagai toleransi pelanggaran margin#

Data nyata jarang terpisah sempurna karena dua sebaran kelas saling menjulur, sehingga margin yang ketat sering kali tidak mungkin dibangun. SVM mengatasinya melalui soft margin, yaitu margin yang boleh dilanggar oleh beberapa sampel dengan menanggung penalti sebesar C. Hyperparameter C mengatur harga setiap pelanggaran, sehingga nilainya menentukan ketegangan antara margin yang lebar dan kesalahan data latih yang kecil.

Nilai C yang kecil membuat pelanggaran murah, sehingga margin menjadi lebar dan model lebih tahan terhadap derau, dengan konsekuensi beberapa titik latih sengaja dibiarkan salah. Nilai C yang besar membuat pelanggaran mahal, sehingga model mengejar kebenaran pada hampir semua titik latih dengan margin yang sempit, dan kepekaan terhadap derau ikut naik. Pola ini mengikuti pertukaran bias-variance yang sama seperti pada regularisasi. C kecil menahan variance, sedangkan C besar menahan bias, dan nilainya disetel melalui cross-validation.

Kernel trick dan peran gamma#

Batas keputusan berupa garis hanya cukup apabila kelasnya memang terpisah secara linear. Cara umum memperluasnya adalah memetakan fitur ke ruang berdimensi lebih tinggi, agar kelas yang saling melingkar menjadi terpisah oleh garis di ruang baru. Kernel trick menghindari pemetaan itu secara eksplisit. Perhitungan SVM hanya membutuhkan hasil kali dalam (inner product) antar pasangan sampel, dan hasil kali tersebut dapat digantikan oleh fungsi kernel yang menghitung kesamaannya langsung di ruang asal.

scikit-learn menyediakan beberapa kernel, dan dua yang paling sering digunakan adalah linear serta rbf. Kernel linear berarti tanpa pemetaan, sehingga batasnya tetap hyperplane. Kernel rbf, singkatan dari radial basis function, memberi setiap titik pengaruh yang paling kuat di sekitar posisinya, lalu melemah secara Gaussian seiring jarak. Hyperparameter gamma mengatur radius pengaruh itu. Gamma yang kecil membuat pengaruh tiap titik lebar sehingga batas keputusan mulus, sedangkan gamma yang besar membuat pengaruhnya sempit sehingga batas menjadi bergerigi dan mengikuti tiap sampel latih. Gamma yang terlalu besar bersama C yang besar adalah kombinasi yang paling sering memicu overfitting.

Kekuatan pemetaan tersebut dibayar dengan biaya komputasi. Waktu pelatihan SVC tumbuh sekurang-kurangnya sebanding dengan kuadrat jumlah sampel, sehingga model ini masih memadai pada ribuan sampel tetapi lambat pada data berjuta baris. Untuk data sedemikian besar, varian linear seperti SGDClassifier atau model berbasis pohon menjadi pilihan yang lebih realistis, dan batas garisnya dapat diperkaya dengan rekayasa fitur alih-alih kernel.

Membandingkan tiga varian pada dataset dua bulan#

Praktik berikut menggunakan make_moons dengan 300 sampel dan derau 0.25, yaitu dua kelas berbentuk bulan sabit yang saling menjulur sehingga tidak mungkin dipisahkan oleh satu garis. Tiga varian dibandingkan, yaitu kernel linear, kernel RBF dengan gamma bawaan, dan kernel RBF dengan gamma 50. Karena akurasi data uji saja bisa menyamarkan perbedaan, skor data latih dan jumlah support vector turut dicetak.

python svm-moons.py 
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_moons(n_samples=300, noise=0.25, random_state=42)
X_latih, X_uji, y_latih, y_uji = train_test_split(
    X, y, test_size=0.2, random_state=42
)

varian = (
    ("kernel linear", dict(kernel="linear")),
    ("rbf gamma default", dict(kernel="rbf")),
    ("rbf gamma=50", dict(kernel="rbf", gamma=50)),
)
for nama, pilihan in varian:
    model = make_pipeline(StandardScaler(), SVC(random_state=42, **pilihan))
    model.fit(X_latih, y_latih)
    n_sv = int(model.named_steps["svc"].n_support_.sum())
    print(
        f"{nama:>18}: akurasi latih = {model.score(X_latih, y_latih):.4f}, "
        f"akurasi data uji = {model.score(X_uji, y_uji):.4f}, "
        f"support vector = {n_sv} dari {len(y_latih)}"
    )
text Keluaran 
     kernel linear: akurasi latih = 0.8625, akurasi data uji = 0.8833, support vector = 82 dari 240
 rbf gamma default: akurasi latih = 0.9125, akurasi data uji = 0.8833, support vector = 80 dari 240
      rbf gamma=50: akurasi latih = 0.9833, akurasi data uji = 0.8833, support vector = 214 dari 240

Ketiga varian kebetulan berakhir pada akurasi data uji yang sama, yaitu 0.8833, karena sampel uji yang keliru sebagian besar berada di zona pertemuan dua lengkungan yang memang tidak terpisahkan. Perbedaan karakternya justru terbaca dari dua ukuran lain, yaitu akurasi data latih dan jumlah support vector. Kernel linear memperoleh akurasi latih 0.8625 yang bahkan berada di bawah akurasi ujinya. Tanda itu menunjukkan batas berupa garis kurang mampu mengikuti bentuk lengkungan, sehingga model sedikit underfitting. Kernel RBF bawaan menyeimbangkan keduanya dengan skor latih 0.9125 dan skor uji 0.8833, karena batas melengkungnya sesuai dengan bentuk data tanpa mengejar setiap titik.

Varian gamma 50 memperlihatkan overfitting dalam bentuk paling jelas. Skor latihnya melonjak ke 0.9833, sementara skor ujinya tidak naik sama sekali. Sebanyak 214 dari 240 titik latih menjadi support vector, artinya hampir seluruh data latih digunakan sebagai penentu batas. Batas keputusan seperti ini bergerigi pada wilayah kosong antar kelas dan hanya tampak baik pada data latihnya. Pemilihan gamma dan C akhirnya dikembalikan ke cross-validation, karena keduanya saling menentukan dan tidak dapat disetel sendiri-sendiri.

Kesalahan umum#

  • Melatih SVC dengan kernel RBF tanpa menskalakan fitur. Kernel mengukur jarak antar sampel, sehingga satu fitur bersatuan besar cukup untuk mendominasi seluruh kesamaan. Penyebabnya adalah lupa memasangkan StandardScaler sebelum SVC. Perbaikannya, bungkus penskalaan dan model dalam satu Pipeline, sebagaimana praktik di atas.
  • Menyetel gamma dan C secara terpisah. Keduanya mengatur ketegangan bias-variance pada model yang sama, sehingga gamma yang dipilih lebih dahulu bisa tampak baik hanya karena nilai C yang menemani belum tepat. Perbaikannya, sediakan jajaran nilai gamma dan C sekaligus, lalu cari pasangan terbaiknya dalam satu kali cross-validation.
  • Menggunakan SVC sebagai pilihan pertama pada dataset sangat besar. Waktu pelatihannya tumbuh sekurang-kurangnya sebanding dengan kuadrat jumlah sampel, sehingga alternatif linear lebih sesuai pada data berjuta baris. Perbaikannya, mulai dari model linear atau SGDClassifier, dan naik ke kernel apabila jumlah datanya masih memadai untuk dilatih.
  • Memilih kernel RBF sebagai pilihan bawaan pada data berdimensi sangat tinggi. Pada data dengan puluhan ribu fitur, misalnya matriks dokumen teks, jarak antar pasangan sampel menjadi hampir seragam sehingga keunggulan pemetaan RBF hilang, sedangkan biaya komputasinya tetap mahal. Penyebabnya adalah anggapan bahwa batas melengkung selalu lebih unggul daripada batas garis. Perbaikannya, mulai dari kernel linear pada fitur berdimensi tinggi, lalu gunakan RBF apabila jumlah fiturnya sedang dan batas pemisah yang diharapkan memang melengkung.

Ringkasan#

  • SVM memilih hyperplane dengan margin maksimum, dan support vector berupa titik-titik tepi itulah satu-satunya penentu batas keputusannya.
  • Hyperparameter C mengatur toleransi pelanggaran margin, dengan nilai kecil yang memberi margin lebar dan tahan derau, sedangkan nilai besar memberi margin sempit yang mengejar semua titik latih.
  • Kernel trick menghitung kesamaan antar sampel di ruang berdimensi lebih tinggi tanpa membangun ruang itu, dengan linear untuk batas garis dan rbf yang radius pengaruhnya dikendalikan gamma.
  • Gamma terlalu besar bersama C yang besar memicu overfitting yang terbaca dari skor latih tinggi, skor uji yang diam, dan jumlah support vector yang membengkak.

Referensi#