Mengapa orang menggunakan teknik Pemrograman Quadratic (seperti SMO) ketika berhadapan dengan SVM kernel? Apa yang salah dengan Keturunan Gradien? Apakah tidak mungkin digunakan dengan kernel atau itu terlalu lambat (dan mengapa?).
Berikut adalah konteks yang lebih sedikit: mencoba memahami SVM sedikit lebih baik, saya menggunakan Gradient Descent untuk melatih classifier SVM linier menggunakan fungsi biaya berikut:
Saya menggunakan notasi berikut:
- adalah bobot fitur model dan adalah parameter biasnya.
- adalah vektor fitur contoh pelatihan .
- adalah kelas target (-1 atau 1) untuk instance .
- adalah jumlah instance pelatihan.
- adalah hiperparameter regularisasi.
Saya mendapatkan vektor gradien (sub) (berkaitan dengan dan ) dari persamaan ini, dan Gradient Descent bekerja dengan baik.
Sekarang saya ingin mengatasi masalah non-linear. Dapatkah saya mengganti semua produk dot dengan dalam fungsi biaya, di mana adalah fungsi kernel (misalnya Gaussian RBF, ), lalu gunakan kalkulus untuk menurunkan a (sub) gradien vektor dan teruskan dengan Gradient Descent? K( u , v )KK( u , v )= e - γ ‖ u - v ‖ 2
Jika terlalu lambat, mengapa begitu? Apakah fungsi biaya tidak cembung? Atau apakah itu karena perubahan gradien terlalu cepat (itu bukan Lipschitz kontinu) sehingga algoritme terus melompat melintasi lembah selama penurunan, sehingga konvergen sangat lambat? Tetapi meskipun begitu, bagaimana bisa lebih buruk daripada kompleksitas waktu Pemrograman Quadratic, yaitu ? Jika itu masalah minimum lokal, tidak bisakah Stochastic GD dengan simulasi anil mengatasi mereka?
sumber
Jika kami menerapkan transformasi ke semua vektor bobot input ( ), kami mendapatkan fungsi biaya berikut:x ( i )ϕ x(i)
Trik kernel menggantikan oleh . Karena vektor bobot adalah tidak berubah, trik kernel tidak dapat diterapkan dengan biaya fungsi di atas .K ( u , v ) wϕ(u)t⋅ϕ(v) K(u,v) w
Fungsi biaya di atas sesuai dengan bentuk dasar dari tujuan SVM:
tunduk pada dan untukζ ( i ) ≥ 0 i = 1 , ⋯ , my(i)(wt⋅ϕ(x(i))+b)≥1−ζ(i)) ζ(i)≥0 i=1,⋯,m
The Bentuk ganda adalah:
tunduk pada dan untukyt⋅α=0 0≤αi≤C i=1,2,⋯,m
di mana adalah vektor penuh 1s dan adalah matriks dengan elemen .1 Q m×m Qij=y(i)y(j)ϕ(x(i))t⋅ϕ(x(j))
Sekarang kita dapat menggunakan trik kernel dengan menghitung seperti:Qij
Jadi trik kernel hanya dapat digunakan pada bentuk ganda dari masalah SVM (ditambah beberapa algoritma lain seperti regresi logistik).
Sekarang Anda dapat menggunakan pustaka Pemrograman Kuadratik yang tidak tersedia untuk menyelesaikan masalah ini, atau menggunakan pengganda Lagrangian untuk mendapatkan fungsi yang tidak dibatasi (fungsi biaya ganda), kemudian mencari minimum menggunakan Gradient Descent atau teknik pengoptimalan lainnya. Salah satu pendekatan yang paling efisien tampaknya adalah algoritma SMO yang diterapkan oleh
libsvm
perpustakaan (untuk kernel SVM).sumber
Saya mungkin salah, tapi saya tidak melihat bagaimana kita bisa mengganti produk dot dengan kernel tanpa mengubahnya menjadi masalah ganda.
Kernel memetakan input secara implisit ke beberapa ruang fitur di mana menjadi , fungsi loss kemudian menjadi Jika kernel Gaussian diterapkan, akan memiliki ifinite dimensi, begitu juga .x ϕ(x)
J(w,b)=C∑i=1mmax(0,1−y(i)(wt⋅ϕ(x(i))+b))+12wt⋅w
ϕ(x(i)) w
Tampaknya sulit untuk mengoptimalkan vektor dimensi tak terbatas menggunakan gradient descent secara langsung.
Perbarui
jawaban Firebug memberi cara untuk mengganti produk dot dengan kernel dalam formulasi primal.
sumber