Dapatkah mesin vektor dukungan digunakan dalam data besar?

Dengan pengetahuan terbatas yang saya miliki tentang SVM, itu baik untuk data pendek dan gemuk matriks , (banyak fitur, dan tidak terlalu banyak contoh), tetapi tidak untuk data besar.$X$

Saya mengerti salah satu alasannya adalah Kernel Matrix adalah matriks mana, adalah jumlah instance dalam data. Jika kita mengatakan, 100K data, matriks kernel akan memiliki elemen, dan dapat mengambil ~ 80G memori.$K$$n \times n$$n$$K$$10^{10}$

Apakah ada modifikasi SVM yang dapat digunakan dalam data besar? (Katakan pada skala 100K ke 1M titik data?)

Seperti yang Anda sebutkan, menyimpan matriks kernel membutuhkan memori yang berskala kuadratik dengan jumlah titik data. Waktu pelatihan untuk algoritma SVM tradisional juga berskala superlinear dengan jumlah titik data. Jadi, algoritma ini tidak layak untuk kumpulan data besar.

Salah satu trik yang mungkin adalah merumuskan ulang SVM yang ter-kernelisasi sebagai SVM linier. Setiap elemen dari matriks kernel mewakili produk titik antara titik data dan setelah memetakannya (mungkin nonlinier) ke dalam ruang fitur: . Pemetaan ruang fitur$K_{ij}$$x_i$$x_j$$K_{ij} = \Phi(x_i) \cdot \Phi(x_j)$$\Phi$didefinisikan secara implisit oleh fungsi kernel, dan SVM kernel tidak secara eksplisit menghitung representasi fitur fitur. Ini efisien secara komputasi untuk dataset ukuran kecil hingga sedang, karena ruang fitur dapat sangat tinggi, atau bahkan tak terbatas. Tetapi, seperti di atas, ini menjadi tidak layak untuk dataset besar. Sebagai gantinya, kami dapat secara eksplisit memetakan data secara nonlinier ke dalam ruang fitur, kemudian secara efisien melatih SVM linier pada representasi ruang fitur. Pemetaan ruang fitur dapat dibangun untuk memperkirakan fungsi kernel yang diberikan, tetapi menggunakan dimensi lebih sedikit daripada pemetaan ruang fitur 'penuh'. Untuk dataset besar, ini masih bisa memberi kita representasi ruang fitur yang kaya, tetapi dengan banyak dimensi lebih sedikit daripada titik data.

Salah satu pendekatan untuk pendekatan kernel menggunakan pendekatan Nyström (Williams dan Seeger 2001). Ini adalah cara untuk memperkirakan nilai eigen / vektor eigen dari matriks besar menggunakan submatrix yang lebih kecil. Pendekatan lain menggunakan fitur acak, dan kadang-kadang disebut 'kitchen sink acak' (Rahimi dan Recht 2007).

Trik lain untuk melatih SVM pada dataset besar adalah memperkirakan masalah optimasi dengan satu set subproblem yang lebih kecil. Sebagai contoh, menggunakan keturunan gradien stokastik pada masalah primal adalah salah satu pendekatan (di antara banyak lainnya). Banyak pekerjaan telah dilakukan di bagian optimasi. Menon (2009) memberikan survei yang bagus.

Referensi

Williams dan Seeger (2001). Menggunakan metode Nystroem untuk mempercepat mesin kernel.

Rahimi dan Recht (2007). Fitur acak untuk mesin kernel skala besar.

Menon (2009) . Mesin vektor dukungan berskala besar: Algoritma dan teori.