SVM: the Geometry of the Hyperplane

Pada tulisan ini gw akan membahas sekilas mengenai vector kemudian bagaimana geometri hyperplane pada SVM.

The Dot Product of Vector

Jika ada dua buah vector $x$ dan $y$ maka dot product dari kedua vector tersebut ialah:

$$x \cdot y=  \Vert x \Vert \Vert y \Vert cos(\theta) = x_1y_1+x_2y_2$$

Lalu apa maksud dari dot product itu sendiri?

Dot product merupakan perkalian antara dua vector yang menghasilkan suatu besaran skalar. Contoh penerapan dot product yang umum ialah dalam menyelesaikan masalah dinamika di fisika. Contohnya jika kita menarik sebuah benda dengan gaya $F=50N$ yang membentuk sudut $\theta=60^0$ sejauh $s=5m$ ke kanan berapa besar usaha yang kita keluarkan?

Cara yang paling mudah ialah dengan menguraikan vector gaya $F$ menjadi vector pada sumbu-x $F_x$ dan sumbu-y $F_y$.

Kemudian usaha dihitung dengan mengalikan $F_x$ dengan jarak perpindahan.

$$\text{Usaha}=F cos(\theta) s = 50 cos(60^0) 5 = 125J$$

Jika dua vector tersebut searah maka hasil dot product nya bernilai positif dan jika berlawanan arah maka negatif. Namun ketika vector tersebut saling tegak lurus, maka resultan yang dihasilkan ialah nol. Masing-masing tidak saling memberikan kontribusi.

Geometry of hyperplane

Sekarang kita akan mengenal geometri pada SVM. Misalnya kita mempunyai hyperplane sebagai berikut:

Lo pasti familiar dengan persamaan garis lurus $y=mx+b$. Hyperplane diatas tidak lain merupakan sebuah garis lurus yang juga memiliki persamaan $y=mx+b$, atau jika ditulis ulang akan menjadi $mx-y+b=0$. Namun persamaan ini akan menjadi lebih ribet kalo hyperplane tersebut berdimensi lebih dari 2. Untuk itu, kita gunakan notasi vector sebagai berikut:

$$\mathbf{w} \cdot \mathbf{x} + \mathbf{b} = 0$$

Dimana $\mathbf{w}$ atau weight merupakan sebuah vector normal yang tegak lurus dengan hyperplane dan $\mathbf{b}$ atau bias menunjukkan seberapa jauh weight dari titik origin $(0, 0)$. Sedangkan $\mathbf{x}$ merupakan data point yang berupa vector yang memiliki koordinat $(x, y)$ pada persamaan garis lurus. Jadi bedakan $x$ pada persamaan garis lurus dengan $\mathbf{x}$ jika menggunakan notasi vector. $\mathbf{w} \cdot \mathbf{x}$ merupakan dot product antara vector $\mathbf{w}$ dan $\mathbf{x}$.

Misalnya hyperplane tadi memiliki persamaan $y=x$ atau $x-y=0$ (Note: $\frac{1}{2}x-\frac{1}{2}y=0$ juga bisa, $\frac{35}{36}x-\frac{35}{36}y=0$ juga bisa, yang penting kemiringannya sama!). Jika kita gunanakan notasi vector maka $\mathbf{w}=(1, -1)$ atau $\mathbf{w}=(-1, 1)$ (keduanya sama-sama tegak lurus dengan hyperplane) dan $\mathbf{b}=0$ (hyperplane melewati titik $(0, 0)$).

$$\mathbf{w} \cdot \mathbf{x} + \mathbf{b} = (1, -1) \cdot (x, y) + 0 = x-y = 0$$

$$\text{atau}$$

$$\mathbf{w} \cdot \mathbf{x} + \mathbf{b} = (-1, 1) \cdot (x, y) + 0 = -x+y = x-y=0$$

Sebetulnya ada banyak kemungkinan weight, karena sepanjang vector tersebut tegak lurus dengan hyperplane. Contoh diatas gw berikan 2 saja. Lalu bagaimana jika hyperplane nya digeser sedikit seperti ini? Dimana hyperplane tidak melewati titik $(0, 0)$.

Sama saja! $\mathbf{w}$ tetap harus tegak lurus dengan hyperplane, berapapun koordinatnya. Yang membedakan ialah karena tidak melewati titik $(0, 0)$ maka nilai $\mathbf{b}$ menjadi tidak nol lagi. Pada hyperplane diatas persamaan garis lurusnya ialah $x-y+2=0$. Jika kita gunakan notasi vector maka $\mathbf{w}=(1, -1)$ dan $\mathbf{b}=2$ atau $\mathbf{w}=(-1, 1)$ dan $\mathbf{b}=-2$.

$$\mathbf{w} \cdot \mathbf{x} + \mathbf{b} = (1, -1) \cdot (x, y) + 2 = x-y+2 = 0$$

$$text{atau}$$

$$\mathbf{w} \cdot \mathbf{x} + \mathbf{b} = (-1, 1) \cdot (x, y) – 2 = -x+y-2 = x-y+2=0$$

SVM: What is Support Vector Machine?

Support Vector Machine (SVM) merupakan salah satu algoritma machine learning yang berguna untuk menyelesaikan masalah klasifikasi.

Misalnya kita punya data seperti pada gambar dibawah ini. Ada dua atribut input Tinggi dan Berat Badan dan sebuah atribut output Jenis Kelamin(Laki-laki/Perempuan). Kita ingin mengklafisikasikan data baru apakah Laki-laki/Perempuan.

Kalo ada sebuah data baru seperti ini, kira-kira output Laki-laki atau Perempuan?

Kalo ini?

Dan kalo ini?

 

Bingung kan lo yang terakhir? Kenapa bingung, karena data baru tersebut berapa pada daerah peralihan antara Laki-laki dan Perempuan. Semakin jauh suatu data baru dari daerah peralihan ini maka kita akan semakin yakin terkait klasifikasi yang kita buat, begitu pula sebaliknya. Lalu seperti apa bentuk daerah peralihan tersebut?

Sebenarnya kita bisa saja membuat sebuah garis yang membagi dua area seperti pada gambar berikut. Garis tersebut membagi dua kelas sehingga semua instance yang kelasnya Laki-laki berada pada sisi kanan dan semua instance yang kelasnya Perempuan berada pada sisi kiri. Jika ada data baru pada area sebelah kanan maka outputnya Laki-laki, dan jika pada area sebelah kiri maka outputnya Perempuan.

Tapi masalahnya, ada banyak kemungkinan untuk membuat garis  tersebut. Garis tersebut bisa digeser sedikit keatas atau kebawah, atau dirotasi, tanpa mengubah hasil klasifikasi. Lalu mana yang harus kita pilih?

Oke, kita coba satu-satu. Bagaimana jika hyperplane yang ini?

Ups, ternyata ketika ada data baru klasifikasi yang dihasilkan pada salah.

Oleh karena itu, hyperplane yang kita pilih ialah yang paling jauh dari kedua kelas, tidak condong ke salah satu kelas, baik kelas Laki-laki maupun Perempuan. Hal ini akan menghasilkan generalisasi yang lebih baik.

Maximal Margin Classifier

Dari sebuah hyperplane, kita bisa mengukur jarak antara hyperplane tersebut dengan data yang paling dekat. Nah yang disebut dengan margin merupakan dua kali jarak antara hyperplane dengan titik terdekatnya.

Semakin condong suatu hyperplane terhadap suatu titik terdekat maka semakin kecil pula marginnya. Terlihat pada gambar di bawah ini, margin hyperplane yang Dan satu catatan bahwa tidak ada instances yang terletak dalam margin.

Tujuan dari SVM ini ialah bagaimana menemukan hyperplane yang optimal, yang memiliki margin yang paling besar. Dengan margin yang besar ini diharapkan hasil generalisasi akan lebih baik sehingga dapat meningkatkan akurasi classifier. Dan titik-titik yang terdekat dengan hyperplane disebut support vector, karena perubahan yang terjadi pada titik-titik ini maka dapat pula mengubah hyperplane.