Metode apa yang ada untuk tuning graph kernel SVM hyperparameters?

10

Saya memiliki beberapa data yang ada pada grafik . milik salah satu dari dua kelas , dan saya tertarik untuk melatih SVM untuk membedakan antara dua kelas. Salah satu kernel yang sesuai untuk ini adalah difusi kernel , mana adalah Laplacian dari dan adalah parameter tuning.G=(V,E)yi{1,1}K=exp(βL),LGβ

Tuning SVM membutuhkan pemilihan hyperparameters, jadi saya harus menyetelSecara konvensional, kami menggunakan validasi silang untuk masalah ini, tetapi itu tampaknya tidak sesuai di sini, karena menghilangkan simpul dari mengubah seluruh grafik, bahkan mungkin meningkatkan jumlah komponen yang terhubung! Jika jumlah komponen yang terhubung berubah, beberapa simpul menjadi tidak dapat dijangkau dari yang lain, dan kami dihadapkan dengan serangkaian data yang sangat berbeda dari yang kami mulai. Artinya, tidak hanya kita hilang simpul yang dihapus , tapi kami juga hilang informasi tentang semua simpul lainnya di grafik yang berdekatan dengan titik itu.θ=(β,C).iGij

Gagasan dasar validasi silang adalah bahwa kami ingin memperkirakan bagaimana kinerja model ketika disajikan dengan data baru. Dalam masalah standar, kelalaian beberapa data Anda untuk pengujian tidak mengubah nilai data pelatihan yang tersisa. Namun, dalam kasus data grafik, tidak jelas apa artinya bagi model untuk melihat data "baru" dalam pengaturan CV. Menghilangkan simpul atau tepi memiliki potensi untuk sepenuhnya mengubah data. Sebagai contoh, bayangkan sebuah grafik yang merupakan Bintang grafik, di mana salah satu simpul memiliki tepi untuk simpul, dan semua simpul lainnya memiliki 1 tepi. Menghilangkan titik pusat untuk membangun data pelatihanS=(VS,ES)kkkSsepenuhnya akan memutuskan grafik, dan matriks kernel akan menjadi diagonal! Tetapi tentu saja, akan mungkin untuk melatih model tentang data pelatihan ini yang disediakan dalam . Yang kurang jelas adalah apa artinya menguji kinerja out-of-sample dari model yang dihasilkan. Apakah seseorang menghitung ulang matriks kernel untuk , dan menyediakannya untuk membuat prediksi?SS

Atau, sebagai alternatif, apakah seseorang memulai dengan menghitung matriks kernel secara keseluruhan dan menghilangkan baris dan kolom yang diperlukan untuk menghasilkan matriks kernel yang digunakan untuk memperkirakan SVM? Ini menyajikan masalah konseptualnya sendiri, karena dimasukkannya simpul pusat dalam berarti bahwa setiap simpul dapat dijangkau dari setiap simpul lainnya, dan matriks kernel padat. Apakah penyertaan ini berarti bahwa ada kebocoran informasi lintas lipatan, dan bias menghasilkan validasi silang? Di satu sisi, data tentang node tengah yang dihilangkan masih ada, karena simpul sentral yang dihilangkan membuat grafik terhubung. Di sisi lain, kita tidak tahu apa-apa tentang labelSS y dari node yang dihilangkan, jadi kami mungkin merasa nyaman karena kami mendapatkan estimasi out-of-sample yang cukup objektif dari melakukan CV dengan cara ini.

Bagaimana seseorang memilih hiperparameter untuk masalah jenis ini? Apakah CV tidak sempurna-tetapi-dapat diterima, atau apakah kita memerlukan metode khusus? Apakah penyetelan hyperparameter bahkan mungkin dalam konteks saya?

Sycorax berkata Reinstate Monica
sumber
Cari ekstensi out-of-sample untuk metode spektral. Saya menerapkan beberapa teknik untuk klasifikasi gambar dalam tesis saya (melihat ke belakang sekarang, saya akan melakukannya secara berbeda). Hasilnya memang menarik tetapi modelnya sendiri cukup rapuh dan tidak mudah disetel.
Vladislavs Dovgalecs
@xeon Adakah rekomendasi tempat untuk mulai melihat literatur ini?
Sycorax berkata Reinstate Monica

Jawaban:

3

Penafian: Saya tidak terlalu terbiasa dengan kernel grafik, jadi jawaban ini mungkin didasarkan pada asumsi yang salah. Saya setuju bahwa menghilangkan simpul saat menghitung matriks kernel adalah suboptimal. Yang mengatakan, saya tidak yakin bahwa validasi silang tentu bermasalah. Apakah konteks pembelajaran Anda transduksi atau induksi?

β

βCβC

Marc Claesen
sumber
Marc, terima kasih atas perhatiannya. Masalah saya induktif. Naluri saya adalah Anda benar, dan kami menghitung matriks kernel lengkap untuk semua data dan kemudian menghilangkan baris dan kolom yang diperlukan untuk menghasilkan kernel CV'd. Apakah Anda mengetahui adanya referensi untuk efek ini?
Sycorax mengatakan Reinstate Monica
Tidak segera, tetapi saya memiliki beberapa rekan kerja yang mengerjakan masalah yang sebanding (kernel spectral clustering) yang bisa saya tanyakan. Mungkin mereka punya referensi dan / atau ide yang lebih baik. Akan diperbarui ketika saya tahu lebih banyak.
Marc Claesen