Support Vector Machines: Penjelasan Matematis dan Intuitif


Support Vector Machines (SVM) merupakan salah satu algoritma machine learning yang paling efektif, baik dari sisi praktis maupun teoretis. Pada awal tahun 90’an hingga awal 2000’an, SVM arguably mengambil alih peran Neural Networks sebagai algoritma yang most favorable dikarenakan kecepatan, keakuratan, dan garansi untuk selalu menghasilkan solusi yang global optimum — hingga sekitar tahun 2006-2007, neural networks (yang dibungkus dengan nama Deep Learning) mengambil alih kembali peran tersebut, terutama untuk large scale problem , i.e., jumlah data latih > ~10,000.

Kali ini saya akan membahas SVM dengan fokus pada masalah (linear) binary classification, baik secara perlahan-lahan (mungkin sedikit bertele-tele), intuitif, matematis, dan sekaligus implementasi sederhana dengan menggunakan library LIBSVM/LIBLINEAR untuk memecahkan masalah handwritten digit recognition.

Kekuatan sebenarnya dari SVM adalah dengan memanfaatkan kernel trick  untuk memecahkan masalah non-linear. Namun pada tulisan ini kita hanya fokus pada linear SVM tanpa kernel trick.

1. notasi

Berikut aturan notasi matematis yang saya akan coba gunakan secara konsisten. Dianjurkan untuk langsung membaca bagian berikutnya. Subbab ini digunakan sebagai referensi jika ada notasi-notasi yang kurang jelas pada bagian-bagian berikutnya.

  • Variabel/Constant: skalar ditulis dengan huruf/simbol kecil, vektor ditulis dengan huruf/simbol kecil bercetak tebal, dan matriks ditulis dengan huruf/simbol kapital bercetak tebal. Contoh: a (skalar), \mathbf{a} (vektor), \mathbf{A} (matriks).
  • Vector norm: \| \mathbf{a} \|. Contoh di ruang Euclidean: \| \mathbf{a} \|_2 = \sqrt{a_1^2 + \ldots + a_d^2}, yang bisa kita kenal sebagai panjang vektor.
  • Ruang Skalar (real): \mathbb{R}
  • Ruang Vektor (real): \mathbb{R}^d, d > 1
  • Dot Product: \langle \mathbf{a}, \mathbf{b} \rangle = \mathbf{a}^{\top} \mathbf{b} = \sum_{j=1}^{d} a_j b_j
  • Ortogonalitas: Dua buah vektor \mathbf{a}, \mathbf{b} \in \mathbb{R}^d dikatakan ortogonal (saling tegak lurus) apabila \mathbf{a}^{\top} \mathbf{b} = 0
  • Ruang Input: \mathcal{X}
  • Ruang Output/Label\mathcal{Y}
  • Loss FunctionL:\mathcal{Y}\times\mathcal{Y}\rightarrow \mathbb{R}
    • Fungsi L menerima 2 input yang berasal dari ruang \mathcal{Y} dan mengembailkan output berupa bilangan real.
  • Fungsi Indikator: \mathbf{1}_{a \neq b} (+1 apabila a \neq b, -1 apabila sebaliknya)
  • Expected Risk: \displaystyle R(f) = \mathbb{E}_{x \sim \mathbb{P}}[L(f(x), c(x))]
  • Empirical Risk: \displaystyle \hat{R}(f)= \frac{1}{n} \sum_{i=1}^{n}L(f(x_i), c(x_i)), dimana f \in \mathcal{H} merupakan hypothesis dan c \in \mathcal{C} merupakan concept, baca tulisan ini untuk penjelasan lebih detil.

2. (BInary) Classification

Problem klasifikasi merupakan problem untuk mengkategorikan suatu entitas ke kelompok tertentu. Kali ini kita fokuskan pada permasalahan binary classification: mengklasifikasi suatu entitas ke kelompok True (+1) atau False (-1). Machine learning bertujuan untuk menemukan solusi optimal dari fungsi f:\mathcal{X} \rightarrow \{+1, -1 \} diberikan n sampel \{ (x_i, y_i) \}_{i=1}^{n}, dimana x_i \in \mathcal{X} dan y_i \in \{-1, 1\}. Pada umumnya, \mathcal{X} merupakan sub-ruang vektor \mathbb{R}^{d}.

Lebih spesifiknya, algoritma machine learning mencari fungsi f: \mathcal{X} \rightarrow \{-1, +1\} yang meminimumkan empirical risk:

\displaystyle f^*:= \min_{f} \frac{1}{n} \sum_{i=1}^{n} L(f(x_i), y_i).

dimana L(a,b) = \mathbf{1}_{a \neq b} merupakan loss function.

Problem klasifikasi pada ruang 2D diilustrasikan oleh Gambar 1 di bawah ini. Dalam konteks ini, fungsi f ditentukan oleh decision boundary yang memisahkan antara sampel positif dan negatif. Dengan adanya decision boundary, kita dapat menentukan decision rule.

Definisi 1 (Decision rule for binary classification). Misalkan terdapat sebuah sampel x \in \mathcal{X} dan boundary g(x). Decision rule dari SVM untuk problem binary classification didefinisikan sebagai berikut:

\displaystyle f(x) = \begin{cases} +1, \mbox{jika } g(x) \geq 0\\ -1, \mbox{jika } g(x) < 0\end{cases}.

Ada berapakah jumlah decision boundary yang mungkin? Banyak, bisa jadi tak terhingga. Tugas dari algoritma machine learning adalah untuk menemukan fungsi f “terbaik”. SVM secara eksplisit mengkuantifikasi istilah “terbaik” ini dalam pengertian maximum margin, yang akan dibahas pada subbab 4.

Gambar 1: Binary classification

 

3. hyperplane

Tool pertama yang mesti dikuasai untuk memahami SVM adalah hyperplane. Hyperplane merupakan generalisasi dari line / garis lurus (pada ruang 2D) atau plane / bidang datar (pada ruang 3D). Gambar 2 & 3 mengilustrasikan hyperplane dalam bentuk garis dan bidang datar. Jika kita naik ke dimensi 4, maka hyperplane berupa bangun ruang, hingga seterusnya (yang mungkin sulit untuk divisualisasikan di benak kita).

line2D
Gambar 2: w_1 x_1 + w_2 x_2 + c = 0
plane3D
Gambar 3: w_1 x_1 + w_2 x_2 + w_3 x_3 + c = 0

<br/> <br/>

Pada ruang cartesius 2D, persamaan garis ax + by + c =0 tentunya sudah sangat familiar. Kita akan membuat persamaan yang lebih umum dari persamaan tersebut yang dapat mencakup ruang berdimensi banyak. Pertama-tama, kita ubah notasi variabel dan konstanta dari persamaan garis tersebut:  x menjadi x_1, y menjadi x_2,  a menjadi w_1, b menjadi w_2, sehingga menjadi

\displaystyle w_1 x_1 + w_2 x_2 + c =0.

Anggap sekarang kita berada di dimensi d>1, maka persamaan di atas menjadi

\displaystyle w_1 x_1 + \ldots + w_d x_d + c = 0

\Rightarrow \displaystyle \sum_{j=1}^{d}w_j x_j + c=0\quad\quad\quad(1)

Cara lain menuliskan persamaan di atas adalah dengan notasi vektor. Kita nyatakan variabel-variabel w_i dan x_i dengan vektor \mathbf{x}=[x_1,\ldots,x_d]^{\top} dan \mathbf{w}=[w_1,\ldots,w_d]^{\top}. Dengan demikian, persamaan (1) dapat ditulis menjadi

\displaystyle \langle \mathbf{w}, \mathbf{x} \rangle + c =0\quad\quad\quad(2),

dimana \mathbf{w}, \mathbf{x} \in \mathbb{R}^d dan \langle \mathbf{w}, \mathbf{x}\rangle = \mathbf{w}^{\top} \mathbf{x} (dot product).

Untuk menyederhanakan intuisi, secara geometris hubungan antara vektor \mathbf{w}, \mathbf{x}, dan garis pada persamaan (2) dapat diilustrasikan secara 2D seperti pada Gambar 4.

Gambar 4: Hyperplane, vektor \mathbf{w}, dan \mathbf{x}

 

Dari gambar tersebut, dapat dilihat bahwa vektor \mathbf{w} selalu tegak lurus dengan hyperplane. Mengapa? Silakan dibuktikan sendiri🙂 (hint: Geser hyperplane pada Gambar 3 ke titik (0,0), lalu gunakan definisi ortogonalitas dari sudut pandang dot product  antara \mathbf{w}, \mathbf{x}).

4. IDE

Sekarang kita akan membahas ide pokok dari SVM, yang dikenal dengan istilah maximum margin. Sebelum itu, marilah kita pahami bagaimana pengaplikasian decision rule dan pengertian margin pada konteks ini.

Decision Rule

Ingat kembali problem klasifikasi pada Gambar 2: fungsi f (garis berwarna biru) merepresentasikan decision boundary untuk menentukan apakah suatu sampel berlabel positif atau negatif. Decision boundary dari algoritma SVM adalah hyperplane. Decision boundary ini nantinya akan menentukan decision rule yang didefinisikan sebagai berikut.

Definisi 2 (SVM decision rule). Misalkan terdapat sebuah sampel \mathbf{x} \in \mathbb{R}^d dan hyperplane g(\mathbf{x}) = \langle \mathbf{w}, \mathbf{x} \rangle + c. Decision rule dari SVM untuk problem binary classification didefinisikan sebagai berikut:

\displaystyle f(\mathbf{x}) = \begin{cases} +1, \mbox{jika } g(\mathbf{x}) \geq 1\\ -1, \mbox{jika } g(\mathbf{x}) \leq -1\end{cases}\quad\quad\quad(3).

Mungkin ada yang bertanya-tanya mengapa decision rule di atas tidak sama dengan Definisi 1 — lihat batas atas/bawah fungsi g(\mathbf{x}). Ini dikarenakan wilayah -1<g(\mathbf{x}) < 1 mendefinisikan margin, yang akan dijelaskan sebentar lagi.

maximum MARGIN

Pada SVM, margin merupakan jarak antara titik-titk positif dan negatif terdekat di sekitar hyperplane. Pada Gambar 5 atau 6, margin diilustrasikan dengan jarak antara 2 garis ungu. Titik sampel yang tepat berada di garis ungu disebut sebagai support vectors dari sinilah nama Support Vector Machines berasal.

Dapat dilihat bahwa margin pada Gambar 6 lebih besar dari Gambar 5. Secara intuitif, margin yang lebih besar akan menghasilkan performa klasifikasi yang lebih baik. Dengan demikian kita membutuhkan algoritma yang mampu memaksimalkan margin dari decision boundary.

Slide2
Gambar 5 Non-maximum margin
Slide3
Gambar 6: Maximum Margin

 

 

Sebelum berbicara tentang algoritma, masalah pertama yang perlu kita hadapi adalah bagaimana caranya menyatakan margin (s) secara matematis. Pertama-tama, kita sederhanakan persamaan (3) menjadi seperti di bawah ini.

y ( \langle \mathbf{w}, \mathbf{x} \rangle + c) \geq 1\quad\quad\quad(4),

dimana y=1 apabila \mathbf{x}:=\mathbf{x}_{+} (positif), dan y=-1 apabila \mathbf{x}:=\mathbf{x}_{-} (negatif) — dianjurkan untuk mengecek sendiri apakah persamaan (3) dan (4) benar-benar ekuivalen.

Sekarang kita akan zoom in Gambar 6 agar hanya terfokus pada 2 titik positif dan negatif yang tepat berada di garis ungu, seperti yang ditampilkan pada Gambar 7.

 

Kemudian kita buat vektor baru yang menghubungkan antara sampel negatif dan positif \mathbf{x}_{+} - \mathbf{x}_{-} dan vektor satuan \bar{\mathbf{w}} = \frac{\mathbf{w}}{ \| \mathbf{w} \|} — ingat kembali bahwa vektor \mathbf{w}  merupakan vektor normal, i.e., vektor yang tegak lurus dengan hyperplane \langle \mathbf{w}, \mathbf{x} \rangle + c = 0. Secara geometris, margin s dapat dicari dengan menghitung proyeksi ortogonal dari vektor \mathbf{x}_{+} - \mathbf{x}_{-} ke vektor \bar{\mathbf{x}}.

Definisi 3 (Margin). Misalkan \mathbf{x}_{+} - \mathbf{x}_{-} merupakan vektor yang menghubungkan titik \mathbf{x}_{-} ke titik \mathbf{x}_{+}, dan \bar{\mathbf{w}}=\frac{\mathbf{w}}{ \|\mathbf{w} \|} merupakan vektor satuan, i.e., \| \bar{\mathbf{w}}\| = 1, yang searah dengan vektor normal \mathbf{w}. Margin merupakan proyeksi ortongal dari vektor \mathbf{x}_{+} - \mathbf{x}_{-} ke vektor \bar{\mathbf{w}}:

\displaystyle s = \langle \bar{\mathbf{w}}, \mathbf{x}_{+} - \mathbf{x}_{-} \rangle\quad\quad\quad(5)

Permasalahan selanjutnya adalah dapatkah kita menyederhanakan persamaan (5) ? Kita akan melihat bahwa ini dapat dilakukan dan surprisingly berakhir dengan persamaan yang sangat sederhana! Persamaan (5) dapat dijabarkan sebagai berikut:

\displaystyle s = \left \langle \frac{\mathbf{w}}{\| \mathbf{w}\|}, \mathbf{x}_{+} - \mathbf{x}_{-} \right \rangle = \left \langle \frac{\mathbf{w}}{\| \mathbf{w}\|}, \mathbf{x}_{+}\right \rangle + \left \langle \frac{\mathbf{w}}{\| \mathbf{w}\|}, - \mathbf{x}_{-}\right \rangle

\displaystyle = \frac{1-c}{\| \mathbf{w}\|} + \frac{1+c}{\| \mathbf{w} \|} = \frac{2}{\| \mathbf{w} \|}\quad\quad\quad(6)

Dari manakah datangnya 1-c dan 1+c pada persamaan (6) ? Ini dapat disimpulkan dengan mengambil kasus khusus dari persamaan (4), yaitu

\displaystyle y (\langle \mathbf{w}, \mathbf{x} \rangle + c) = 1\quad\quad\quad(7),

untuk \mathbf{x} tepat berada di ujung margin (garis ungu pada Gambar 7). Dengan aljabar sederhana kita langsung mendapatkan:

\displaystyle \langle \mathbf{w}, \mathbf{x}_{+}\rangle +c = 1 \Rightarrow \langle \mathbf{w}, \mathbf{x}_{+} \rangle= 1 - c,

\displaystyle -(\langle \mathbf{w}, \mathbf{x}_{-}\rangle + c) = 1 \Rightarrow -\langle \mathbf{w}, \mathbf{x}_{-}\rangle = 1 + c,

dimana - \langle \mathbf{w}, \mathbf{x}_{-}\rangle = \langle \mathbf{w}, -\mathbf{x}_{-}\rangle (sifat linearitas dari dot product).

Jadi, kesimpulannya adalah kita membutuhkan algoritma yang dapat memaksimalkan persamaan (6). Dan semua pernyataan di bawah ini ekuivalen dengan pernyataan tersebut.

\displaystyle \max \frac{2}{ \| \mathbf{w} \| } \Rightarrow \min \frac{\| \mathbf{w} \|}{2} \Rightarrow \min \frac{1}{2} \| \mathbf{w}\|^2\quad\quad\quad(9)

Dengan kata lain, memaksimumkan margin s pada decision boundary ekuivalen dengan meminimumkan panjang vektor normal \mathbf{w} dari hyperplane \langle \mathbf{w}, \mathbf{x} + c = 0\rangle.

Di persamaan (9) panjang vektor \mathbf{w} dinyatakan dalam bentuk kuadrat. Satu-satunya alasan mengapa demikian agar problem ini mathematically convenient sehubungan dengan pilihan algoritma optimisasi yang akan dijelaskan di bagian berikutnya.

5. algoritma

Algoritma SVM merupakan algoritma yang menyelesaikan problem optimisasi berdasarkan persamaan (4) dan (9) di atas. Lebih spefisiknya, diberikan n buah sampel \{(\mathbf{x}_i, y_i)\}_{i=1}^n, SVM mencoba menyelesaikan problem sebagai berikut:

\displaystyle (\mathbf{w}, c) := \arg \min_{\mathbf{w}, c} \frac{1}{2} \| \mathbf{w}\|^2_2

\displaystyle \mbox{ subject to }y_i ( \langle \mathbf{w}, \mathbf{x}_i \rangle + c) \geq 1, \forall i=1,...,n\quad\quad\quad(10).

Kita dapat meringkas ekspresi di atas hanya dengan 1 persamaan dalam bentuk Lagrangian :

\displaystyle \mathcal{L}(\mathbf{w}, c) = \frac{1}{2} \| \mathbf{w}\|_2^2 - \sum_{i=1}^{n} \alpha_i [y_i (\langle \mathbf{w}, \mathbf{x}_i \rangle + c) - 1]\quad\quad\quad(11),

dimana \alpha_i, \forall i=1,...,n merupakan Lagrange multipliers. Karena nantinya kita akan menggunakan tool optimisasi khusus untuk menyelesaikan problem (10), kita membutuhkan perhitungan gradien terhadap \mathbf{w} dan c dari persamaan (11): \frac{\partial \mathcal{L}}{\partial \mathbf{w}}=0 dan \frac{\partial \mathcal{L}}{\partial c} = 0 (pembaca diharapkan mencoba sendiri perhitungan gradient ini).

\displaystyle \frac{\partial \mathcal{L}}{\partial \mathbf{w}} = 0

\displaystyle \Rightarrow \mathbf{w} - \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i = 0

\displaystyle \Rightarrow \mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i\quad\quad\quad(12)

dan

\displaystyle \frac{\partial \mathcal{L}}{\partial c} = 0

\displaystyle \Rightarrow - \sum_{i=1}^{n} \alpha_i y_i = 0\quad\quad\quad(13)

Sampai di sini, apakah kita sudah berhasil menemukan \mathbf{w} dan c optimal? Sayang sekali belum dikarenakan kita tidak mengetahui nilai dari Lagrange multipliers \alpha_i ! Tapi dari pengerjaan persamaan (12) dan (13), paling tidak, kita bisa mengambil insight bahwa cukup untuk mencari sekumpulan \alpha_i untuk menyelesaikan problem (10).

Kita akan coba utak-atik sedikit dari apa yang telah kita punya. Mungkin mensubstitusi \mathbf{w} pada persamaan (11) dengan persamaan (12) merupakan ide yang bagus. Setelah melalui proses aljabar yang cukup panjang (silakan dicoba sendiri), kita akan mendapatkan:

\displaystyle \mathcal{L}(\boldsymbol{\alpha}) = \sum_{i=1}^{n}\alpha_i - \sum_{i=1, j=1}^{n,n} \alpha_i \alpha_j y_i y_j \langle \mathbf{x}_i, \mathbf{x}_j \rangle\quad\quad\quad(14).

Dengan juga mempertimbangkan fakta (13), problem optimisasi dari SVM secara lengkap dapat juga dinyatakan sebagai berikut:

\displaystyle \hat{\boldsymbol{\alpha}}:= \arg \max_{\boldsymbol{\alpha}} \mathcal{L}(\boldsymbol{\alpha}) \mbox{ subject to } \alpha_i \geq 0, \forall i=1,...,n\quad\quad\quad(15).

Problem optimisasi di atas ekuivalen dengan problem optimisasi (10), yang dikenal dengan istilah dual form — problem (10) sendiri dapat disebut sebagai primal form.

Salah satu keuntungan dari problem (15) adalah kita hanya mencari satu vektor saja: \boldsymbol{\alpha}, dimana kita mesti mencari 1 vektor dan 1 skalar pada problem (10): \mathbf{w}, c. Keuntungan yang lain adalah ternyata terdapat algoritma optimisasi efisien yang dapat menyelesaikan problem (15), yang dikenal dengan Quadratic Programming. Akan terlalu panjang ceritanya apabila quadratic programming dibahas juga di sini.

Training

Dengan demikian, dibalik cerita panjang dari SVM secara teori, di ranah praktis algoritma learning dengan SVM secara umum hanya membutuhkan beberapa langkah saja (tanpa mendetilkan quadratic programming):

  1. Kumpulkan n sampel \{ (\mathbf{x}_i, y_i)\}_{i=1}^{n} sebagai data training.
  2. Bentuk persamaan (14).
  3. Hitung vektor optimal \hat{\boldsymbol{\alpha}} dengan menggunakan quadratic programming.

Selesai !

TEST

Sekarang, bagaimanakah caranya melakukan klasifikasi? Spesifiknya, diberikan input \mathbf{u} yang tidak termasuk di himpunan data training, termasuk dikategori manakah \mathbf{u} (-1 atau +1)? Mudah saja. Kita gunakan Definisi 2, lalu ubah sedikit hyperplane g(\mathbf{x}): substitusi \mathbf{w} dengan persamaan (12) dan gunakan vektor optimal \hat{\boldsymbol{\alpha}}. Secara jelasnya, fungsi untuk melakukan klasifikasi dengan SVM berbentuk:

\displaystyle f(\mathbf{u}) = \begin{cases} +1 \mbox{ jika } y_i (\sum_{i=1}^{n} \alpha_i y_i \langle \mathbf{x}_i, \mathbf{u}\rangle + c) \geq 1 \\ -1 \mbox{ jika } y_i (\sum_{i=1}^{n} \alpha_i y_i \langle \mathbf{x}_i, \mathbf{u}\rangle + c) \leq -1\end{cases}\quad\quad\quad(16)

6. Implementasi

Sekarang kita bermain-main dengan linear SVM untuk memecahkan masalah handwritten digit recogntion: diberikan gambar angka, klasifikasikan gambar tersebut ke label yang benar \{0, 1, ..., 9\}. Kita gunakan dataset USPS yang dapat diunduh dari http://www.cad.zju.edu.cn/home/dengcai/Data/USPS/USPS.mat. USPS terdiri dari gambar 2D digit berukuran 16 \times 16 — yang masing-masing gambar akan dinyatakan dengan vektor berdimensi 256, dengan jumlah data training sebanyak 7291 dan data test sebanyak 2007.

Perangkat yang kita gunakan adalah python, dengan asumsi library numpy dan skicit-learn sudah ter-install. Implementasi SVM pada skicit-learn sendiri berdasarkan library yang lain yang disebut LIBSVM/LIBLINEAR. Tidak sampai 40-an baris kita sudah bisa mengimplementasi algoritma SVM pada problem USPS handwritten digit dataset. Jika code di bawah berhasil dijalankan, maka seharusnya didapatkan hasil

  • Training accuracy (%) : 97.805513647
  • Test accuracy (%) : 91.5794718485
from sklearn import svm # SVM library with LIBLINEAR in skicit-learn
import scipy.io as sio # used for reading MAT file
import numpy as np

def read_usps(filepath):
	# procedure to read USPS dataset in MATLAB format
	mat = sio.loadmat(filepath)
	X = np.array(mat['fea']).astype('float32')
	n = X.shape[0]
	y = np.array(mat['gnd']).astype('int64').reshape(n,)

	# Divide into training and test
	ns = 7291
	X_train = X[0:ns]
	y_train = y[0:ns]
	X_test = X[ns:]
	y_test = y[ns:]

	return X_train, y_train, X_test, y_test

if __name__ == '__main__':
	X_train, y_train, X_test, y_test = read_usps(filepath='USPS.mat')

	lin_svm = svm.LinearSVC()
	lin_svm.fit(X_train, y_train)

	y_train_hat = lin_svm.predict(X_train)
	y_test_hat = lin_svm.predict(X_test)

	print 'Training accuracy (%) : ',np.mean(y_train_hat == y_train)*100
	print 'Test accuracy (%) : ',np.mean(y_test_hat == y_test)*100

6 thoughts on “Support Vector Machines: Penjelasan Matematis dan Intuitif

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s