Perkenalan
Pada tulisan kali ini saya akan membahas tentang Support Vector Machine (SVM) yang merupakan algoritma supervisored learning untuk mengklasifikasikan data. Umumnya SVM digunakan untuk memisahkan titik data multidimensi menjadi dua kelas berbeda. Untuk mempermudah, kita hanya akan mempertimbangkan kasus dua dimensi (ide untuk dimensi yang lebih tinggi adalah sama). Pertama, kita akan mendefinisikan fungsi tujuan yang tunduk pada batasan dan kemudian mempertimbangkan fungsi ganda Lagrangian untuk menyelesaikan masalah optimasi ini. Selain itu, saya akan membuktikan bahwa menyelesaikan masalah ganda sama dengan menyelesaikan masalah utama.
Mendukung Mesin Vektor
Misalkan kita memiliki kumpulan data berikut, dan kita diminta untuk menemukan garis terbaik yang memisahkan data menjadi dua kelas:
Seperti yang ditunjukkan pada Gambar 1, ada banyak jalur yang dapat melakukan pekerjaan ini. Namun, kriteria kami untuk lini terbaik adalah sebagai berikut:
Jarak dari garisL1 ke L2 sama dengan jarak dari L2 ke L3. Vektor W tegak lurus terhadap semua garis, yaitu L1, L2, dan L3. Tujuannya di sini adalah untuk memaksimalkan margin antara garis L1 dan L3. Selain itu, perlu diperhatikan bahwa baris L1 dan L3 harus berisi setidaknya satu titik dari kelas yang sesuai. Setelah memperoleh persamaan garis L2, maka mudah untuk mengklasifikasikan titik data baru.
Seperti terlihat jelas pada gambar, terdapat ketergantungan fungsional antara vektor W dan margin. Secara sistematis, kami akan membangun ketergantungan ini dan kemudian mencoba menyelesaikan masalahnya.
Beberapa kesimpulan dapat diambil dari Gambar 2. Pertama, hasil kali titik vektor W dengan vektor X yang terletak pada garis L2 tidak bergantung pada posisi titik pada garis dan dapat dilambangkan dengan konstanta C
Dengan asumsi konstanta B =-C, kita dapat menulis ulang rumus di atas menjadi:
Ini sebenarnya adalah persamaan L2.
Kita dapat menganggap Persamaan 1.1 sebagai kurva tingkat
ketika fungsinya diatur sama dengan nol
Rupanya, vektor W adalah gradien dari F (X), yang menyiratkan bahwa fungsi tersebut meningkat ke arah W. Sekarang kita dapat menyimpulkan bahwa untuk titik di atas L2, nilai fungsinya akan positif dan untuk titik di bawahnya akan negatif. Kita ingin F (X) menjadi fungsi yang kurva levelnya berada di F (X) = 1danF (X) =-1 menghasilkan garis L1 dan L3, masing-masing.
Mirip dengan L2, untuk garis L1dan L3, hasil kali titik dari W dengan vektor apa pun X yang terletak pada masing-masing baris dapat ditampilkan sebagai:
Dengan memanfaatkan fakta bahwa fungsi tersebut meningkat sepanjang gradien, kita dapat mengatakan bahwa, untuk titik di atas L1, pertidaksamaan berikut berlaku:
Dan untuk baris di bawah L3:
Seperti yang ditunjukkan pada Gambar 1, kita sebenarnya mengetahui kelas mana yang termasuk dalam poin yang kita berikan. (ditunjukkan dengan warna hitam dan oranye). Mari kita definisikan variabel skalar yi untuk titik 2D xi . Untuk titik-titik yang memenuhi pertidaksamaan 1.1, misalkan variabel yi bernilai +1, yang menunjukkan satu kelas, dan untuk titik-titik yang memenuhi pertidaksamaan 1.2 , yi adalah -1, yang menunjukkan kelas lain .
Dalam kedua kasus tersebut, ketimpangan berikut berlaku:
Mulai saat ini, ketimpangan 1.3, yang berlaku di semua titik, akan menjadi kendala kita.
Sekarang mari kita perhatikan gambar berikut untuk mendapatkan rumus margin kita:
Margin dapat dihitung sebagai perkalian titik X1-X3 dengan vektor satuan searah W.
Dari persamaan untukL1 dan L3:
Oleh karena itu, marginnya akan menjadi
Pada akhirnya kita dapat menyatakan permasalahan seperti memaksimalkan margin ini dengan batasan pada ketimpangan 1.3
Untuk kenyamanan matematis, kami akan meminimalkan
tunduk pada pertidaksamaan 1.3, yang dapat ditulis ulang sebagai:
Untuk saat ini, mari kita tinggalkan masalah ini dan memperkenalkan fungsi ganda Lagrangian untuk menyelesaikan masalah optimasi dengan batasan pertidaksamaan.
Dualitas Lagrangian
Untuk memahami gagasan dualitas, pertama-tama mari kita menggeneralisasi masalahnya dengan menyatakannya kembali seperti ini:
Memperkecil
Tunduk pada batasan ketimpangan berikut:
Dimana x adalah sebuah titik dalam ruang multidimensi
Ini adalah masalah utama kami. Izinkan saya menyatakan masalah ini dengan P1. Mulai sekarang, saya akan menyebutnya sebagai P1. Sekarang mari kita perkenalkan fungsi ganda Lagrangian, yang mentransformasikan P1 sebagai berikut:
Masalah ganda ditulis sebagai berikut:
Mulai sekarang, kita akan menyebut masalah ini dengan nama “masalah ganda”. Pertama, kita akan menunjukkan bahwa penyelesaian permasalahan ganda kurang dari atau sama dengan penyelesaian permasalahan primal. Hal ini disebut “dualitas lemah' dan dapat dinyatakan secara matematis sebagai berikut:
Bukti Dualitas yang Lemah
Di P1, jika untuk beberapa x, setidaknya salah satu batasan dilanggar, maka supremum dari L sehubungan dengan lambda akan bernilai positif ketakterbatasan. Dalam bentuk matematika dapat ditampilkan sebagai berikut:
Di P1, jika x melanggar setidaknya salah satu batasan
Sebaliknya (jika tidak ada batasan yang dilanggar):
Kita dapat menarik kesimpulan berikut, dengan asumsi bahwa P* adalah solusi untuk P1, dan x* adalah titik dimana F(x*) = P*
Oleh karena itu, kita dapat menulis ulang dualitas lemah sebagai:
(Perhatikan bahwa maksimum atau minimum suatu fungsi adalah bilangan berhingga, sedangkan supremum dan infimum bisa tak terhingga).
Untuk membuktikan ketidaksetaraan pada dualitas lemah, pertama-tama mari kita tunjukkan bahwa ketidaksetaraan berikut ini berlaku
Dalam bentuk yang diperluas:
Hanya dengan mensubstitusi x* ke kiri, kita dapat membuktikan bahwa:
Pertidaksamaan ini berlaku untuk x* karena kondisi berikut:
Karena ketimpangan berlaku untuk x*,infimumnya pasti lebih kecil dari P*.
Saat mengevaluasi nilai minimum L untuk x , kami berasumsi bahwa lambda adalah tetap dan x bervariasi. Oleh karena itu, untuk semua lambda nonnegatif, dualitas lemah terpenuhi, termasuk nilai lambda yang memaksimalkan infimum ini. Hal ini dapat dirumuskan sebagai berikut:
Dualitas yang Kuat
Dalam kasus khusus, ketika fungsi tujuan dan semua batasannya cembung(seperti dalam masalah SVM kita), dualitas yang kuat mungkin berlaku, yang menyatakan bahwa:
Kita dapat menulis ulang dualitas yang kuat sebagai berikut dengan menyatakan nilai terkecil dari L untuk xdengan fungsi lambda:
Sekarang mari kita nyatakan solusi di sisi kiri dengan D*, yang fungsi q evaluasi pada lambda star.
Kami juga tahu itu
karena dari definisi infimum adalah nilai minimum yang mungkin dan paling banyak sama dengan ruas kanan pertidaksamaan di atas. Mengingat fakta ini,
Hanya dengan menyederhanakan pertidaksamaan di atas, kita mendapatkan:
Dan itu hanya mungkin jika:
Saya ingin menekankan bahwa setiap suku penjumlahan bisa berupa angka negatif atau nol. Oleh karena itu, syarat yang diperlukan (disebut kelonggaran komplementer) agar seluruh jumlah menjadi nol adalah, pada kenyataannya, semua suku harus nol, seperti yang ditunjukkan di bawah ini:
Kita dapat menyimpulkan bahwa nilai lambda yang terkait dengan batasan bernilai negatif harus sama dengan nol. Dalam SVM, nilai lambda yang terkait dengan titik yang tidak terletak pada garis L1 dan L3 harus nol. Secara intuitif, penambahan atau penghapusan poin-poin ini tidak akan mengubah margin.
masalah SVM
Sekarang mari kita kembali ke masalah awal kita dan mencoba menyelesaikannya dengan memperkenalkan masalah ganda.
Memperkecil
Tunduk pada batasan berikut
Perpanjangan Lagrangian akan menjadi
Dan masalah ganda:
Kita harus mulai dengan mencari nilai terkecil, yang dilakukan dengan mencari turunan parsial terhadap W dan B dan menetapkannya sama dengan nol:
Mengganti persamaan ini kembali ke soal ganda, maka soal gandanya akan menjadi:
dengan batasan sebagai berikut:
Kesimpulan
Dalam makalah ini, saya menjelaskan bagaimana masalah optimasi terbatas dapat diubah menjadi masalah ganda dengan diperkenalkannya ekstensi Lagrangian. Kami juga memperoleh kondisi penting yang disebut “kelambanan komplementer,”dengan asumsi bahwa dualitas yang kuat berlaku. Terakhir, kita dapat mengatakan bahwa jika kita mempunyai solusi optimal untuk permasalahan ganda, kita juga mempunyai solusi optimal untuk permasalahan utama, atau sebaliknya. Solusi optimal untuk salah satu masalah membuktikan bahwa asumsi kami benar (dualitas kuat berlaku). Dengan kata lain, kesenjangan dualitas antara masalah primal dan masalah ganda adalah nol. Saya berharap contoh SVM adalah contoh yang baik untuk menunjukkan bagaimana masalah ganda dapat diterapkan untuk memecahkan masalah klasifikasi yang sebenarnya. Pada akhirnya, saya ingin menekankan bahwa pendekatan yang sama dapat diterapkan untuk mencari persamaan hyperplane untuk memisahkan titik data multidimensi menjadi dua kelas.
