Apa keterbatasan metode Kernel dan kapan harus menggunakan metode kernel?

10

Metode kernel sangat efektif dalam banyak tugas klasifikasi yang diawasi. Jadi apa saja batasan metode kernel dan kapan harus menggunakan metode kernel? Terutama di era data skala besar, apa kemajuan metode kernel? Apa perbedaan antara metode kernel dan pembelajaran banyak instance? Jika datanya 500x10000, 500apakah jumlah sampel, dan 10000apakah dimensi dari masing-masing fitur, maka dalam keadaan ini, dapatkah kita menggunakan metode kernel?

pertambangan
sumber

Jawaban:

16

Metode kernel dapat digunakan untuk masalah yang diawasi dan tidak terawasi. Contoh-contoh yang terkenal adalah mesin vektor dukungan dan clustering kernel kernel , masing-masing.

Metode kernel menyediakan cara terstruktur untuk menggunakan algoritma linier dalam ruang fitur yang ditransformasikan, yang transformasi biasanya nonlinier (dan ke ruang dimensi yang lebih tinggi). Keuntungan utama yang disebut oleh trik kernel ini adalah bahwa pola nonlinier dapat ditemukan dengan biaya komputasi yang masuk akal .

Perhatikan bahwa saya mengatakan biaya komputasi itu wajar, tetapi tidak dapat diabaikan. Metode kernel biasanya membangun matriks kernel dengan jumlah instance pelatihan. Kompleksitas metode kernel karena itu merupakan fungsi dari jumlah instance pelatihan, bukan jumlah dimensi input. Mesin pendukung vektor, misalnya, memiliki kompleksitas pelatihan antara dan . Untuk masalah dengan sangat besar , kompleksitas ini saat ini menjadi penghalang. N O ( N 2 ) O ( N 3 ) NKRN×NNHAI(N2)HAI(N3)N

Ini membuat metode kernel sangat menarik dari perspektif komputasi ketika jumlah dimensi besar dan jumlah sampel relatif rendah (katakanlah, kurang dari 1 juta).

Terkait: Kernel linear dan kernel non-linear untuk mesin vektor dukungan?

SVM untuk Masalah Skala Besar

Untuk masalah dimensi yang sangat tinggi, seperti 10000dimensi yang Anda sebutkan dalam pertanyaan, seringkali tidak perlu memetakan ke ruang fitur dimensi yang lebih tinggi. Ruang input sudah cukup baik. Untuk masalah seperti itu, metode linier adalah urutan besarnya lebih cepat dengan kinerja prediksi yang hampir sama. Contoh metode ini dapat ditemukan di LIBLINEAR atau Vowpal Wabbit .

Metode linear sangat menarik ketika Anda memiliki banyak sampel dalam ruang input dimensi tinggi. Bila Anda hanya memiliki sampel, menggunakan metode kernel nonlinier juga akan murah (karena kecil). Jika Anda memiliki, katakanlah, sampel dalam dimensi, metode kernel tidak mungkin dilakukan.N 5.000.000 10.000500N5.000.00010.000

Untuk masalah dimensi rendah dengan banyak contoh pelatihan (disebut masalah besar kecil ), metode linier dapat menghasilkan akurasi prediksi yang buruk. Untuk masalah seperti itu, metode ensemble seperti EnsembleSVM memberikan batas keputusan nonlinier dengan biaya komputasi yang berkurang secara signifikan dibandingkan dengan SVM standar.pNhal

Marc Claesen
sumber
Terima kasih banyak atas jawaban detailnya, tuan. Saya menemukan dalam keadaan dimensi tinggi, jika saya menggunakan RBFkernel libsvm, itu selalu overfitting, classifier mencapai akurasi tinggi tetapi akurasi rendah di set pengujian. Dan jika saya melakukan pengurangan dimensi sebelum pengklasifikasi, dan dimensi yang dikurangi mendekati jumlah sampel pelatihan, pengklasifikasi mungkin mencapai keuntungan yang baik antara pelatihan dan set pengujian. Apakah hasilnya sesuai dengan sebagian besar hasil empiris? Terima kasih.
pertambangan
Metode kernel cukup kuat terhadap dimensi input tinggi. Biasanya, Anda tidak perlu melakukan pengurangan dimensionalitas sebelum menggunakannya. Sangat penting untuk mengatur semua parameter, terutama gammauntuk kernel RBF. Nilai optimal untuk gammaterkait dengan jumlah dimensi input. Pendekatan tuning yang paling umum adalah cross-validation. Jika Anda menggunakan nilai yang sama untuk gammadengan dan tanpa pengurangan dimensi Anda mungkin membuat kesalahan.
Marc Claesen
Ya pak. Saya biasanya menggunakan paket grid.pydalam libsvmuntuk melakukan cross-validation. Dan di sebagian besar keadaan, untuk data dimensi tinggi, gammaselalu sangat kecil, seperti 0.00001, level ini.
pertambangan
Hai, Pak, saya telah memeriksa proyek open source Anda EnsembleSVM, apakah perlu membuat prosedur cross-validasi multithreading? Dan saya pikir pada tahap prediksi, akan baik jika memprediksi data besar dalam batch dan multithreading atau multi mesin?
pertambangan
Menggunakan multithreading adalah opsional di EnsembleSVM, tetapi diaktifkan secara default di esvm-traindan esvm-predict. Untuk multithreading menonaktifkan, menggunakan bendera berikut dalam alat tersebut: -threads 1.
Marc Claesen