Support Vector MachineRandy C. Wihandika

Teknik InformatikaInstitut Teknologi Sepuluh NopemberSurabaya

Support Vector Machine● Dikembangkan oleh B. E. Boser, I. M. Guyon, dan V. N. Vapnik

pada 1992 dan dipresentasikan di Fifth Annual Workshop of Computational Learning Theory

● Digunakan untuk pengenalan tulisan tangan

Decision Boundary● Pemisah antara dua kelas● Banyak decision boundary

yang dapat dibuat antara dua kelas

● Dapat dicari menggunakan algoritma perceptron, e.g. neural network

● SVM Mencari hyperplane yang paling optimal

Support Vector Machine● Decision boundary harus

sejauh mungkin dari kedua kelas

● Harus memaksimalkan margin

Support Vector Machine

Optimasi:

Data:

(constrained optimization problem)

Constrained OptimizationMisal: minimalkan f(x) dengan constrain g(x) = 0

α: Lagrange multiplier

Untuk banyak constrain:Lagrangian

Support Vector MachineOptimasi:

Minimalkan w dan b, maksimalkan α (Lagrangian):

Support Vector MachineDiferensialkan:

Maksimalkan:

Support Vector MachineDapatkan b:

Soft-margin SVM● Memperbolehkan "error" pada klasifikasi● Menggunakan variabel slack ξ

Soft-margin SVM

Minimalkan:

Minimalkan w, b, dan ξ, maksimalkan α:

C: tradeoff antara error dan margin

Soft-margin SVMDiferensialkan:

Selanjutnya sama dengan proses hard-margin SVM

Non-linear SVM● Memisahkan dua kelas secara non-linier● Ide:

○ Petakan data ke ruang yang berdimensi lebih tinggi○ Klasifikasi secara linier

● Fungsi yang memetakan: kernel function Ф○ Input space: ruang asal data○ Feature space: ruang data setelah transformasi

● Contoh:

Ф

Feature Space (2D)Ф(xi

2)

Input Space (1D)

xi

Non-linear SVM

Kernel Functions● Polynomial

● Radial basis function (RBF)

● Sigmoidal

Overfitting● Terjadi jika data dipetakan ke dimensi yang sangat tinggi

Support Vector Machine● Kelebihan:

○ Tidak terjebak pada local optima○ Dapat mengklasifikasi data berdimensi tinggi

● Kekurangan:○ Harus memilih kernel function yang cocok

Conclusion● SVM adalah alternatif yang baik dari neural network● Konsep penting dalam SVM:

○ Memaksimalkan margin○ Penggunaan kernel function

Selesai.