Bisakah SVM melakukan streaming belajar satu contoh pada satu waktu?

33

Saya memiliki kumpulan data streaming, contoh tersedia satu per satu. Saya perlu melakukan klasifikasi multi-kelas pada mereka. Segera setelah saya memberi contoh pelatihan untuk proses pembelajaran, saya harus membuang contohnya. Bersamaan, saya juga menggunakan model terbaru untuk melakukan prediksi pada data tidak berlabel.

Sejauh yang saya tahu, jaringan saraf mampu melakukan stream learning dengan memberi contoh satu per satu dan melakukan propagasi maju dan propagasi mundur pada contoh.

Bisakah SVM melakukan stream learning satu contoh pada satu waktu dan langsung membuang contoh itu?

siamii
sumber
2
Jawaban yang diterima harus diperbarui. Tampaknya ada saat ini beberapa perpustakaan yang mendukung algoritma pembelajaran online SVM. Vowpal wabbit memiliki pengurangan untuk svm , alternatif lain adalah: scikit-learn, sofia-ml dan paket kernlab R memiliki beberapa opsi untuk pembelajaran online.
marbel

Jawaban:

22

Pengaturan streaming dalam pembelajaran mesin disebut "pembelajaran online". Tidak ada mesin vektor dukungan yang tepat dalam pengaturan online (karena definisi fungsi tujuan secara inheren untuk pengaturan batch). Mungkin generalisasi paling langsung dari SVM ke pengaturan online adalah algoritma pasif-agresif. Kode ada di sini http://webee.technion.ac.il/people/koby/code-index.html dan makalah terkait ada di sini http://eprints.pascal-network.org/archive/00002147/01/CrammerDeKeShSi06. pdf

Ide dasarnya adalah bahwa seseorang menerima data sebagai berpasangan dengan titik kueri xR di mana k adalah jumlah label. Algoritma mempertahankan matriks bobot W tR k × d pada iterasi t algoritma recieves sebuah titik data x t dan skor kemudian memberi diprediksi y t = W x t(x,y)Rd×[k]xRkWtRk×dtxty^t=Wxtuntuk masing-masing label dan memprediksi label skor tertinggi sebagai label yang sebenarnya. Jika prediksi salah maka algoritma membuat perubahan terkecil untuk sedemikian rupa sehingga akan menghindari kesalahan di masa depan. Perubahan terkecil di sini didefinisikan berdasarkan norma Frobenius.Wt

Tanda
sumber
1
(+1) Selamat datang di situs, Tandai.
kardinal
11

Saya selalu menemukan kerangka pembaruan implisit (yang mencakup algoritma pasif-agresif yang disebutkan dalam jawaban lain di sini) tidak perlu lebih kompleks daripada kerangka pembaruan eksplisit (belum lagi bahwa pembaruan implisit dapat jauh lebih lambat daripada yang eksplisit kecuali jika solusi bentuk tertutup untuk pembaruan implisit tersedia).

Pembaruan Sadar Pentingnya Online adalah contoh dari algoritma pembaruan eksplisit canggih yang lebih sederhana, lebih cepat, dan lebih fleksibel (mendukung berbagai fungsi kehilangan, hukuman ganda, pembelajaran sensitif biaya, dll.) Daripada rekan implisitnya. Makalah ini hanya membahas model linear (svm linier sesuai dengan kasus fungsi kehilangan engsel dengan penalti kuadratik)

Karena Anda memerlukan klasifikasi multi-kelas, salah satu pendekatan adalah menggunakan fungsionalitas "reduksi" dari vowpal wabbit (dibuat di atas pendekatan dari kertas) yang sayangnya tidak didokumentasikan dengan baik.

Yevgeny
sumber
8

LASVM adalah salah satu varian pembelajaran online paling populer dari SVM.

SVM linear juga dapat dilatih menggunakan penurunan gradien stokastik, sama seperti model linear lainnya.

Fred Foo
sumber
Hanya untuk memperjelas, tidak ada model linier yang dapat dilatih menggunakan SGD, kita perlu mengasumsikan setidaknya satu bentuk tertentu dari tujuan (fungsi kerugian aditif)
lejlot
6

Silakan merujuk ke makalah SVM Incremental Learning, Adaptation, dan Optimization , yang mengusulkan SVM online untuk klasifikasi biner.

Kode kertas di atas dapat ditemukan di sini . Dalam kode tersebut, dua cara pelatihan online diperkenalkan:

  1. latih SVM secara bertahap pada satu contoh sekaligus dengan menelepon svmtrain(), dan
  2. melakukan pelatihan batch, menambah semua contoh pelatihan ke dalam solusi secara bersamaan dengan menelepon svmtrain2().

Kembali ke pertanyaan Anda, jawabannya jelas YA untuk streaming mempelajari satu contoh pada satu waktu. Dan kode tersebut juga dapat menangani menghapus contoh (membuang) contoh, yaitu estimasi kesalahan LOO (perkiraan satu-keluar) - perkiraan kesalahan LOO yang tepat dapat dihitung secara efisien dengan tidak mempelajari satu contoh secara bersamaan dan menguji pengelompokan pada Contoh.

herohuyongtao
sumber
(+1) Selamat datang di situs kami!
whuber
0

Pembelajaran Online dengan kernel membahas pembelajaran online dalam pengaturan kernel umum.

Kutipan dari abstrak -

" Algoritma berbasis kernel seperti mesin vektor dukungan telah mencapai kesuksesan besar dalam berbagai masalah dalam pengaturan batch di mana semua data pelatihan tersedia di muka. Mesin vektor dukungan menggabungkan apa yang disebut trik kernel dengan ide margin besar. Telah ada sedikit penggunaan metode ini dalam pengaturan online yang cocok untuk aplikasi real-time. Dalam makalah ini kami mempertimbangkan pembelajaran online dalam Ruang Kernel Reproducing. Dengan mempertimbangkan penurunan gradien stokastik klasik dalam ruang fitur, dan penggunaan beberapa trik lurus ke depan , kami mengembangkan algoritma sederhana dan efisien secara komputasi untuk berbagai masalah seperti klasifikasi, regresi, dan deteksi kebaruan. "

TenaliRaman
sumber