Menghitung koefisien Lagrange untuk SVM dengan Python

10

Saya mencoba untuk menulis implementasi SVM penuh dalam Python dan saya punya beberapa masalah menghitung koefisien Lagrange.

Pertama biarkan saya ulangi apa yang saya mengerti dari algoritma untuk memastikan saya berada di jalan yang benar.

Jika adalah dataset dan y i{ - 1 , 1 } adalah label kelas x i , kemudian i , y i ( w T x i + b ) 1x1,x2,...,xnyi{1,1}xi

i,yi(wTxi+b)1

Jadi kita hanya perlu menyelesaikan masalah optimasi

w2

tunduk padayi(wTxi+b)1

Dalam hal koefisien Lagrange, ini diterjemahkan menjadi menemukan , dan dan meminimalkan:wbα=(α1,α2,...αn)00

L(α,w,b)=12w2αi(yi(wTx+b)1)

Sekarang karena dan kita dapat menulis ulang sebagai dengan batasan

Lw=0w=αiyixi
Lb=0yiαi=0
L(α,w,b)=Q(α)=αi12αiαjyiyjxiTxj
αi0 and αiyi=0

Jadi saya mencoba menyelesaikan masalah optimasi menggunakan Python, dan satu-satunya paket gratis yang bisa saya temukan disebut cvxopt .

Saya ingin bantuan untuk menyelesaikan ini, saya tidak dapat menemukan contoh yang baik tentang ini, dan sementara saya mengerti teorinya, saya kesulitan menerjemahkannya ke dalam kode (saya akan berharap sebaliknya karena saya lebih banyak dari latar belakang pemrograman).

Perhatikan bahwa pada titik tertentu saya ingin menyelesaikannya menggunakan kernel tapi saya tidak yakin apa implikasinya untuk memecahkan masalah ini dalam kode.

L(α,w,b)=Q(α)=αi12αiαjyiyjK(xi,xj)

Setiap bantuan akan sangat dihargai, saya benar-benar bingung tentang cara mengimplementasikan ini dengan Python. Jika Anda memiliki modul yang lebih baik untuk menyelesaikan masalah optimisasi, saya juga ingin membacanya.

Charles Menguy
sumber

Jawaban:

4

Saya telah menggunakan cvxopt untuk mengimplementasikan SVM sebelumnya, namun dalam matlab bukan python. Ini pasti akan melayani tujuan Anda, apakah cukup efisien akan tergantung pada apa yang Anda gunakan. SVM paling efisien tidak menggunakan paket solver QP, mereka mengambil keuntungan dari beberapa optimasi unik untuk SVM. Banyak yang menggunakan algoritma gaya SMO untuk menyelesaikannya.

LibSVM adalah paket SVM yang menggunakan algoritme dalam Pemilihan Perangkat Kerja dengan Menggunakan Informasi Orde Kedua untuk Pelatihan Mesin Vector Support . Kode ini open source, jika Anda tertarik untuk melihat bagaimana penerapannya. Ini juga memiliki antarmuka python.

SVMLight adalah paket lain, mereka menggunakan algoritma yang berbeda (lihat situs mereka untuk referensi). Ini juga open source dan memiliki antarmuka python.

karenu
sumber
Terima kasih atas jawaban informatif (yang menurut saya menggantikan milik saya), dan selamat datang di scicomp!
Aron Ahmadia
+1 jawaban yang menarik dan saya mulai melihat tautan hebat Anda yang sangat membantu saya!
Charles Menguy
2

Bentuk umum masalah pengoptimalan Anda adalah Program Quadratic , terlepas dari apakah Anda menggunakan trik kernel atau kernel linier. Kedengarannya cvxoptakan cukup untuk apa yang Anda coba lakukan, tetapi pythonauts lain di sini juga beruntung dengan OpenOpt .

Aron Ahmadia
sumber
Aron, apakah Anda tahu jika pembungkus Ipopt Python pernah diperbaiki?
Geoff Oxberry
Salah satu siswa David Ketcheson membuatnya bekerja dengan OpenOpt (yang dapat menggunakannya dengan algoritma kuasi-Newton), tetapi telah mengalami beberapa kesulitan dengan mendapatkan tumpukan OpenOpt pada OS X.
Aron Ahmadia