Support Vector Machine (SVM)¶

Pattern Recognition merupakan metode pemetaan suatu data ke dalam konsep tertentu yang disebut disebut class atau category. Berbagai metode yang dikenal dalam pattern recognition antara lain linear discrimination analysis, hidden markov model, hingga metode kecerdasan buatan seperti artificial neural network. Salah satu metode yang belakangan ini banyak mendapat perhatian sebagai state of the art dalam pattern recognition adalah Support Vector Machine (SVM) [1] [2].

Support Vector Machine (SVM) dikembangkan oleh Boser, Guyon, Vapnik, dan pertama kali dipresentasikan pada tahun 1992 di Annual Workshop on Computational Learning Theory. Konsep dasar SVM ialah kombinasi dari teori-teori komputasi yang telah ada puluhan tahun sebelumnya, seperti margin hyperplane, kernel, dan konsep-konsep pendukung yang lain. Akan tetapi hingga tahun 1992, belum pernah ada upaya merangkaikan komponen-komponen tersebut [3] [4].

Prinsip dasar SVM adalah linear classifier, dan selanjutnya dikembangkan agar dapat bekerja pada problem non-linear dengan konsep kernel trick pada ruang kerja berdimensi tinggi. Hal ini meningkatkan minat penelitian di bidang pattern recognition untuk mengetahui potensi kemampuan SVM secara teoritis maupun aplikasi. Saat ini SVM telah berhasil diaplikasikan dalam problem dunia nyata (real-world problems), dan secara umum memberikan solusi yang lebih baik dibandingkan metode konvensional seperti artificial neural network. Jadi, dengan kata lain SVM adalah metode learning machine yang bekerja atas prinsip Structural Risk Minimization (SRM) dengan tujuan menemukan hyperplane terbaik yang memisahkan dua buah class pada input space.

B. Linear Support Vector Machine (SVM)¶

1. Pattern Recognition pada SVM¶

Konsep SVM dapat dijelaskan secara sederhana sebagai usaha mencari hyperplane terbaik yang berfungsi sebagai pemisah dua buah class pada input space. Gambar 1a memperlihatkan beberapa pattern yang merupakan anggota dari dua buah class (+1 dan –1). Pattern yang tergabung pada class –1 disimbolkan dengan warna merah (kotak), sedangkan pattern pada class +1 disimbolkan dengan warna kuning(lingkaran). Problem klasifikasi dapat diterjemahkan dengan usaha menemukan hyperplane (garis) yang memisahkan antara kedua kelompok tersebut. Berbagai alternatif garis pemisah (discrimination boundaries) ditunjukkan pada gambar 1a.

Hyperplane pemisah terbaik antara kedua class dapat ditemukan dengan mengukur margin dari hyperplane dan mencari titik maksimalnya. Margin adalah jarak antara hyperplane tersebut dengan pattern terdekat dari masing-masing class. Pattern yang paling dekat ini disebut sebagai support vector. Garis solid pada gambar 1b menunjukkan hyperplane terbaik, yang terletak tepat pada tengah-tengah kedua class, sedangkan titik merah dan kuning yang berada dalam lingkaran hitam adalah support vector. Usaha untuk menentukan hyperplane ini merupakan inti dari proses pembelajaran pada SVM.

Gambar 1. a. garis pemisah(Discriminatio boundaries) b. hyperplane terbaik

Data yang tersedia dinotasikan sebagai $∈ℜ^d$ sedangkan label masing-masing dinotasikan $y_i ∈\{-1,+1\}$ untuk $i=1,2,....,l$, yang mana $l$ adalah banyaknya data. Diasumsikan kedua class -1 dan +1 dapat terpisah secara sempurna oleh hyperplane berdimensi d yang didefinisikan:

$$+b=0.......(1)$$

Pattern $$ yang termasuk class -1 (sampel negatif) dapat dirumuskan sebagai pattern yang memenuhi pertidaksamaan:

$$+b\leq-1.......(2)$$

sedangkan pattern $$ yang termasuk class +1 (sampel positif):

$$+b\geq+1.......(3)$$

Margin terbesar dapat ditemukan dengan memaksimalkan nilai jarak antara hyperplane dan titik terdekatnya, yaitu $1/‖‖$. Hal ini dapat dirumuskan sebagai Quadratic Programming (QP) problem, yaitu mencari titik minimal persamaan (4), dengan memperhatikan constraint persamaan (5).

$$\min \limits_{} τ(w)= {2} \left \Vert \right \Vert ^2.......(4)$$

$$y_i(.+b)-1\geq0, ∀i.......(5)$$

Problem ini dapat dipecahkan dengan berbagai teknik komputasi, di antaranya Lagrange Multiplier.

$$L(,b,α)={2}\left \vert \right \vert ^2-\sum \limits^{l}_{i=l}α_i(y_i((.+b)-1))$$$$(i=1,2,...,l).......(6)\ $$

$α_i$ adalah Lagrange multipliers, yang bernilai nol atau positif $(α_i\geq 0)$ . Nilai optimal dari persamaan (6) dapat dihitung dengan meminimalkan $L$ terhadap $$ dan b , dan memaksimalkan $L$ terhadap $α_i$. Dengan memperhatikan sifat bahwa pada titik optimal gradient $L$ =0, persamaan (6) dapat dimodifikasi sebagai maksimalisasi problem yang hanya mengandung saja $α_i$, sebagaimana persamaan (7) di bawah.

Maximize: $$\sum \limits^{l}_{i=l}α_i-{2}\sum \limits^{l}_{i,j=l}α_iα_jy_iy_j.......(7)$$

Subject to: $$α_i≥0(i=1,2,...,l) \sum \limits^{l}_{i=l}α_iy_i=0.......(8)$$

Dari hasil dari perhitungan ini diperoleh $α_i$ yang kebanyakan bernilai positif. Data yang berkorelasi dengan $α_i$ yang positif inilah yang disebut sebagai support vector.

2. SVM dengan Soft Margin¶

Penjelasan di atas berdasarkan asumsi bahwa kedua belah class dapat terpisah secara sempurna oleh hyperplane. Akan tetapi, umumnya dua buah class pada input space tidak dapat terpisah secara sempurna. Hal ini menyebabkan constraint pada persamaan (5) tidak dapat terpenuhi, sehingga optimisasi tidak dapat dilakukan. Untuk mengatasi masalah ini, SVM dirumuskan ulang dengan memperkenalkan teknik softmargin. Dalam softmargin, persamaan (5) dimodifikasi dengan memasukkan slack variabel $ξ_i ( > 0) ξ_i$ sebagai berikut:

$$y_i(.+b)-ξ_i, ∀i.......(9)$$

Dengan demikian persamaan (4) diubah menjadi:

$$\min \limits_{}τ(,ξ)={2}\left \Vert \right \Vert^2+C\sum \limits^{l}_{i=l}ξ_i.......(10)$$

Paramater $C$ dipilih untuk mengontrol tradeoff antara margin dan error klasifikasi ξ . Nilai $C$ yang besar berarti akan memberikan penalti yang lebih besar terhadap error klasifikasi tsb.

C. Non-Linear Support Vector Machine(SVM)¶

1. Model Kernel¶

Pada umumnya masalah dalam domain dunia nyata (real world problem) jarang yang bersifat linear separable. Kebanyakan bersifat non linear. Untuk menyelesaikan problem non linear, SVM dimodifikasi dengan memasukkan fungsi Kernel. Dalam non linear SVM, pertama-tama data $$ dipetakan oleh fungsi $Φ()$ ke ruang vektor yang berdimensi lebih tinggi. Pada ruang vektor yang baru ini, hyperplane yang memisahkan kedua class tersebut dapat dikonstruksikan. Hal ini sejalan dengan teori Cover yang menyatakan “Jika suatu transformasi bersifat non linear dan dimensi dari feature space cukup tinggi, maka data pada input space dapat dipetakan ke feature space yang baru, dimana pattern-pattern tersebut pada probabilitas tinggi dapat dipisahkan secara linear”.

Ilustrasi dari konsep ini dapat dilihat pada gambar 2. Gambar 2a ditampilkan data pada class kuning dan data pada class merah yang berada pada input space berdimensi dua tidak dapat dipisahkan secara linear. Selanjutnya gambar 2b menunjukkan bahwa fungsi $Φ$ memetakan tiap data pada input space tersebut ke ruang vektor baru yang berdimensi lebih tinggi (3 dimensi), dimana kedua class dapat dipisahkan secara linear oleh sebuah hyperplane. Notasi matematika dari mapping ini adalah sebagai berikut.

$$Φ:ℜ^d →ℜ^q , d < q.......(11)$$

Gambar 2. Fungsi $Φ$ memetakan data ke ruang vektor yang berdimensi lebih tinggi, sehingga kedua class dapat dipisahkan secara linear oleh sebuah hyperplane

Tabel 1. Kernel yang umum dipakai dalam SVM

$$Jenis Kernel$$	$$Definisi$$
Polynomial	$K(,)=(.+1)^p$
Gaussian	$K(,)=exp(- \frac{\left \Vert - \right \Vert^2}{2\sigma^2})$
Sigmoid	$K(,)=tanh(\alpha.+\beta)$

Pemetaan ini dilakukan dengan menjaga topologi data, dalam artian dua data yang berjarak dekat pada input space akan berjarak dekat juga pada feature space, sebaliknya dua data yang berjarak jauh pada input space akan berjarak jauh juga pada feature space. Pembelajaran selanjutnya pada SVM yakni untuk menemukan titik-titik support vector hanya bergantung pada dot product dari data yang sudah ditransformasikan pada ruang baru yang berdimensi lebih tinggi, yaitu $Φ().Φ()$.

Karena umumnya transformasi $Φ$ ini tidak diketahui, dan sangat sulit untuk difahami secara mudah, maka perhitungan dot product tersebut sesuai teori Mercer dapat digantikan dengan fungsi kernel $K(,)$ yang mendefinisikan secara implisit transformasi $Φ$.

Hal ini disebut sebagai Kernel Trick, yang dirumuskan:

$$K(,)=Φ().Φ().......(12)$$

Kernel trick memberikan berbagai kemudahan, karena dalam proses pembelajaran SVM, untuk menentukan support vector, kita hanya cukup mengetahui fungsi kernel yang dipakai, dan tidak perlu mengetahui wujud dari fungsi non linear $Φ$ . Berbagai jenis fungsi kernel dikenal, sebagaimana dirangkumkan pada tabel 1.

Selanjutnya hasil klasifikasi dari data $$ diperoleh dari persamaan berikut:

$$f(Φ())= .Φ()+b.......(13)$$

$$=\sum \limits^{n}_{i=l,∈SV}α_iy_iΦ().Φ()+b.......(14)$$

$$=\sum \limits^{n}_{i=l,∈SV}α_iy_iK(,)+b.......(15)$$

Support vector pada persamaan di atas dimaksudkan dengan subset dari training set yang terpilih sebagai support vector, dengan kata lain data $$ yang berkorespondensi pada $α_i ≥ 0$.

2. Model Sekuensial¶

Hyperplane yang optimal dalam SVM dapat ditemukan dengan merumuskannya ke dalam QP problem dan diselesaikan dengan library yang banyak tersedia dalam analisa numerik. Alternatif lain yang cukup sederhana adalah metode sekuensial yang dikembangkan oleh Vijayakumar [5] sebagai berikut:

1. Initialization $α_i$=0, Hitung matriks $D_{ij}=y_iy_j(K(x_i,x_j)+λ^2)$
2. Lakukan step (a), (b) dan (c) dibawah untuk $i=1,2,...,l$

$$(a) E_i=\sum \limits^{l}_{j=l}\alpha_jD_ij$$

\ $$(b) \delta\alpha_i=min\rbrace$$\ $$(c) \alpha_i=\alpha_i+\delta\alpha_i$$

1. Kembali ke step 2 sampai nilai (b) $α$ mencapai konvergen

Pada algoritma di atas, $γ$ adalah parameter untuk mengkontrol kecepatan proses learning. Konvergensi dapat didefinisikan dari tingkat perubahan nilai $α$.

D. Karakteristik SVM¶

1. Secara prinsip SVM adalah linear classifier
2. Pattern recognition dilakukan dengan mentransformasikan data pada input space ke ruang yang berdimensi lebih tinggi, dan optimisasi dilakukan pada ruang vector yang baru tersebut. Hal ini membedakan SVM dari solusi pattern recognition pada umumnya, yang melakukan optimisasi parameter pada ruang hasil transformasi yang berdimensi lebih rendah daripada dimensi input space.
3. Menerapkan strategi Structural Risk Minimization (SRM)
4. Prinsip kerja SVM pada dasarnya hanya mampu menangani klasifikasi dua class.

E. Kelebihan dan Kekurangan SVM¶

1. Kelebihan SVM¶

Kelebihan SVM antara lain:

1. Generalisasi Generalisasi didefinisikan sebagai kemampuan suatu metode (SVM, neural network, dsb.) untuk mengklasifikasikan suatu pattern, yang tidak termasuk data yang dipakai dalam fase pembelajaran metode itu. Vapnik menjelaskan bahwa generalization error dipengaruhi oleh dua faktor: error terhadap training set, dan satu faktor lagi yang dipengaruhi oleh dimensi VC (Vapnik-Chervokinensis). Strategi pembelajaran pada neural network dan umumnya metode learning machine difokuskan pada usaha untuk meminimimalkan error pada training-set. Strategi ini disebut Empirical Risk Minimization (ERM). Adapun SVM selain meminimalkan error pada training-set, juga meminimalkan faktor kedua. Strategi ini disebut Structural Risk Minimization (SRM), dan dalam SVM diwujudkan dengan memilih hyperplane dengan margin terbesar. Berbagai studi empiris menunjukkan bahwa pendekatan SRM pada SVM memberikan error generalisasi yang lebih kecil daripada yang diperoleh dari strategi ERM pada neural network maupun metode yang lain.
2. Curse of dimensionality Curse of dimensionality didefinisikan sebagai masalah yang dihadapi suatu metode pattern recognition dalam mengestimasikan parameter (misalnya jumlah hidden neuron pada neural network, stopping criteria dalam proses pembelajaran dsb.) dikarenakan jumlah sampel data yang relatif sedikit dibandingkan dimensional ruang vektor data tersebut. Semakin tinggi dimensi dari ruang vektor informasi yang diolah, membawa konsekuensi dibutuhkannya jumlah data dalam proses pembelajaran. Pada kenyataannya seringkali terjadi, data yang diolah berjumlah terbatas, dan untuk mengumpulkan data yang lebih banyak tidak mungkin dilakukan karena kendala biaya dan kesulitan teknis. Dalam kondisi tersebut, jika metode itu “terpaksa” harus bekerja pada data yang berjumlah relatif sedikit dibandingkan dimensinya, akan membuat proses estimasi parameter metode menjadi sangat sulit. Curse of dimensionality sering dialami dalam aplikasi di bidang biomedical engineering, karena biasanya data biologi yang tersedia sangat terbatas, dan penyediaannya memerlukan biaya tinggi. Vapnik membuktikan bahwa tingkat generalisasi yang diperoleh oleh SVM tidak dipengaruhi oleh dimensi dari input vector [3]. Hal ini merupakan alasan mengapa SVM merupakan salah satu metode yang tepat dipakai untuk memecahkan masalah berdimensi tinggi, dalam keterbatasan sampel data yang ada.
3. Landasan teori Sebagai metode yang berbasis statistik, SVM memiliki landasan teori yang dapat dianalisa dengan jelas, dan tidak bersifat black box.
4. Feasibility SVM dapat diimplementasikan relatif mudah, karena proses penentuan support vector dapat dirumuskan dalam QP problem. Dengan demikian jika kita memiliki library untuk menyelesaikan QP problem, dengan sendirinya SVM dapat diimplementasikan dengan mudah. Selain itu dapat diselesaikan dengan metode sekuensial sebagaimana penjelasan sebelumnya

3. Kekurangan SVM¶

1. Sulit dipakai dalam problem berskala besar. Skala besar dalam hal ini dimaksudkan dengan jumlah sample yang diolah.
2. SVM secara teoritik dikembangkan untuk problem klasifikasi dengan dua class. Dewasa ini SVM telah dimodifikasi agar dapat menyelesaikan masalah dengan class lebih dari dua, antara lain strategi One versus rest dan strategi Tree Structure. Namun demikian, masing-masing strategi ini memiliki kelemahan, sehingga dapat dikatakan penelitian dan pengembangan SVM pada multiclass-problem masih merupakan tema penelitian yang masih terbuka

F. Aplikasi SVM¶

SVM banyak digunakan diaplikasikan dalam bidang kelimuan bioinformatika. Beberapa contoh aplkasinya antara lain:

1. Analisa ekspresi gen
2. Deteksi homologi protein
3. Prediksi struktur protein

selain itu, SVM juga dapat dikembangkan untuk aplikasi di bidang kimia dan kesehatan. beberapa contohnya antara lain:

1. prediksi senyawa kimia dalam campuran
2. prediksi senyawa obat dalam obat komersial
3. prediksi penyandang tumor

SUPPORT VECTOR REGRESSION(SVR)

A. Algoritma SVR¶

Seperti yang telah disebutkan sebelumnya bahwa algoritma SVM cukup fleksibel. Algoritma SVM tidak hanya mendukung klasifikasi linier dan nonlinear, tetapi juga mendukung regresi linier dan nonlinear. Triknya dengan membalikkan tujuannya: alih-alih mencoba menemukan hyperplane yang mungkin ada di antara dua kelas sambil membatasi margin violation, SVM Regression mencoba menyesuaikan sebanyak mungkin contoh hyperplane yang membatasi margin violation. Lebar margin dikontrol oleh hyperparameter $ϵ$. Gambar 3 menunjukkan dua model Regresi SVM linier yang dicoba pada beberapa data linear acak, satu dengan margin besar $(ϵ = 1,5)$ dan yang lainnya dengan margin kecil $(ϵ = 0,5)$.

SVM adalah sebuah metode yang digunakan untuk kasus klasifikasi, namun prinsip metode tersebut dapat dikembangkan ke dalam regresi dan metode peramalan (Time series). Metode tersebut dinamakan support vector regression (SVR). misalkan terdapat $l$ data training, $(x_i,y_i), i=1,...,l$ dengan data input $x=\lbrace x_i,...,x_l\rbrace \subseteq ℜ^N$ dan $y=\lbrace y_i,...,y_l\rbrace \subseteq ℜ$ dan $l$ adalah banyaknya data training. dengan metode SVR didapat fungsi regresi sebagai berikut:

$$f(x)=w^T\varphi (x)+b.......(1) $$

dengan:

$w$ = vektor bobot

$\varphi (x)$ = fungsi yang memetakan $x$ dalam suatu dimensi

$b$= bias

Agar mendapatkan generalisasi yang baik untuk fungsi regresi $f(x)$, dapat dilakukan dengan cara meminimalkan norm dari $w$. Oleh karena itu perlu adanya penyelesaian problem optimasi:

$$min \lbrace \frac {1}{2} \left \Vert x \right \Vert ^2 \rbrace.......(2)$$

Diasumsikan bahwa ada suatu fungsi $f(x)$ yang dapat mengaproksimasi semua titik $(x_i,y_i)$ dengan presisi $ε$. Dalam kasus ini diasumsikan bahwa semua titik ada dalam rentang $f(x) \pm ε$(feasible). Dalam hal ketidaklayakan (infeasible), dimana ada beberapa titik yang mungkin keluar dari rentang $f(x) \pm ε$, sehingga dapat ditambahkan variabel slack $t,t^*$, untuk mengatasi masalah pembatas yang tidak layak dalam problem optimasi.

Gambar 3. Ilurtrasi SVR

Gambar 1 memperlihatkan situasi ini secara grafis, hanya titik-titik di luar area yang mempunyai kontribusi terhadap pinalti. Selanjutnya problem optimasi di atas dapat diformulasikan sebagai berikut:

$$min \lbrace \frac {1}{2}\left \Vert w \right \Vert^2 + C\sum \limits^{l}_{i=l} (t_i+t_i^*) \rbrace .......(3)$$

persamaan diatas kemudian diturunkan sehingga dihasilkan $w=\sum \limits^{l}_{i=l} (\alpha_i- \alpha_i^*) \varphi (x_i)$, sehingga fungsi regresi secara eksplisit dirumuskan sebagai berikut:

$$f(x)= \sum \limits^{l}_{i=l} (\alpha_i- \alpha_i^*) K(x_i,x) + b .......(5)$$

Dimana $K(x_i,x)$ merupakan fungsi kernel yang memiliki nilai inner produk dari dua vektor dan $x$. Dimana selisih antara $\alpha_i$ dan $\alpha_i^*$ dan menghasilkan nilai beta dan $b$ adalah bias.

B. Loss Function¶

Loss function merupakan fungsi yang menunjukkan hubungan antara error dengan bagaimana error ini dikenai pinalti. Perbedaan loss function akan menghasilkan formulasi SVR yang berbeda. Loss function yang paling sederhana $ε-insensitive$ loss function. Formulasi $ε-insensitive$ loss function sebagai berikut:

$$L_\varepsilon (y)= \Big \{^{0, untuk \vert f(x)-y \vert <\varepsilon }_{\vert f(x)-y \vert - \epsilon, untuk yang lain} $$

C. Fungsi Kernel dalam SVR¶

permasalahan yang ada di dunia nyata merupakan permasalahan yang memiliki pola nonlinier sehingga untuk mengatasi masalah ketidaklinieran dapat menggunakan fungsi kernel. fungsi kernel yang digunakan pada metode SVR sebagai berikut:

Tabel 1. Kernel yang umum dipakai dalam SVR

$$Jenis Kernel$$	$$Definisi$$
Linier	$$K(x,x')=xx^T$$
Polynomial	$$K(x,x')=(xx^T+1)^p, p=1,2,....$$
RBF (Radial Basis Function)	$$K(x,x')=exp(-\frac {1}{2 \sigma^2}\left \Vert x-x^T \right \Vert^2)$$

Daftar Pustaka¶

1. Byun H., Lee S.W., “A Survey on Patter Recognition Applications of Support Vector Machines”, International Journal of Pattern Recognition and Artificial Intelligence, Vol.17, No.3, 2003, pp.459-486.
2. Tsuda K., “Overview of Support Vector Machine”, Journal of IEICE, Vol.83, No.6, 2000, pp.460-466 (in Japanese).
3. Vapnik V.N., “The Nature of Statistical Learning Theory”, 2nd edition, Springer-Verlag, New York Berlin Heidelberg, 1999.
4. Cristianini N., Taylor J.S., “An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods”, Cambridge Press University, 2000.
5. Vijayakumar S, Wu S, “Sequential Support Vector Classifiers and Regression”, Proc. International Conference on Soft Computing (SOCO'99),Genoa, Italy, pp.610-619, 1999.