Menghitung koefisien Lagrange untuk SVM dengan Python

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 ) ≥ $x_1, x_2, ..., x_n$$y_i \in \{-1, 1\}$$x_i$

$$\forall i, y_i(w^Tx_i + b) \geq 1$$

Jadi kita hanya perlu menyelesaikan masalah optimasi

$\|w\|^2$

tunduk pada$y_i(w^Tx_i + b) \geq 1$

Dalam hal koefisien Lagrange, ini diterjemahkan menjadi menemukan , dan dan meminimalkan:$w$$b$$\alpha=(\alpha_1, \alpha_2, ... \alpha_n) \neq0$$\geq0$

$$L(\alpha, w, b) = \frac12 \|w\|^2 - \sum \alpha_i(y_i(w^Tx + b)-1)$$

Sekarang karena dan kita dapat menulis ulang sebagai dengan batasan

$$\frac{\partial L}{\partial w}=0 \implies w=\sum \alpha_i y_i x_i$$ $$\frac{\partial L}{\partial b}=0 \implies \sum y_i \alpha_i = 0$$ $$L(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j x_i^T x_j$$ $$\alpha_i \geq 0 \ \text{and} \ \sum \alpha_i y_i = 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(\alpha, w, b) = Q(\alpha)=\sum \alpha_i - \frac12\sum \sum \alpha_i \alpha_j y_i y_j K(x_i,x_j)$$

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.

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.

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 .