Jika saya memiliki beberapa topologi non-berulang (DAG) tetap (set node dan tepi tetap, tetapi algoritma pembelajaran dapat memvariasikan berat pada tepi) dari sigmoid neuron dengan input neuron yang hanya dapat mengambil string di sebagai input dan mengarah ke satu output (yang menampilkan nilai nyata yang kami bulatkan hingga 1 atau turun menjadi -1 jika itu merupakan ambang tetap tertentu dari 0). Apakah ada cara cepat untuk menghitung (atau memperkirakan) dimensi VC dari jaringan ini?
Catatan
Saya bertanya reformulasi algoritmik yang sedikit lebih tepat pada CS.SE:
Secara efisien menghitung atau mendekati dimensi VC dari jaringan saraf
machine-learning
neural-networks
algorithms
vc-dimension
Artem Kaznatcheev
sumber
sumber
Jawaban:
Saya sengaja menemukan posting Anda saat mencari formula umum untuk menghitung dimensi VC pada jaring saraf, tetapi ternyata tidak ada. Rupanya kita hanya memiliki campur aduk persamaan VC yang berbeda yang hanya berlaku dalam kasus-kasus sempit tertentu. Perhatian: Saya mendasarkan ini pada penelitian lama yang hampir tidak saya mengerti, pada konsep VC Dimensions, yang baru saya pelajari sekarang. Namun demikian, mungkin bermanfaat untuk membaca makalah ini oleh Peter L. Bartlett dan Wolfgang Maass 1pada perhitungan dimensi VC. Perhatikan bagaimana mereka berusaha keras untuk mendapatkan formula VC dalam 13 teorema, tetapi seberapa beragam dan beragam kondisi yang diperlukan untuk masing-masing. Prasyarat ini berkisar dari jumlah operator dalam fungsi aktivasi hingga jenis lompatan yang diizinkan, jumlah neuron dan posisinya, kedalaman bit input, dll .; ada begitu banyak "gotcha" yang tersebar ini sehingga mereka membuat formula yang berguna hanya untuk kelas masalah tertentu yang sempit. Lebih buruk lagi, mereka menunjukkan dalam Teorema 5 dan 8 bahwa fungsi aktivasi sigmoidal sangat sulit untuk menghitung angka VC. Pada halaman 6-7 mereka menulis:
Saya juga membaca makalah ini dengan judul yang menggembirakan "Bounding VC-Dimension for Neural Networks: Progress and Prospects." 2Banyak matematika di atas kepala saya dan saya tidak skim cukup lama untuk mengatasi kurangnya keterampilan terjemahan saya, tetapi saya curiga itu tidak menawarkan solusi yang menghancurkan bumi, karena itu mendahului edisi kedua buku Bartlett dan Maass, yang mengutip karya selanjutnya dari penulis yang sama. Mungkin penelitian selanjutnya selama 20 tahun terakhir telah meningkatkan kalkulasi dimensi VC untuk jaring saraf, tetapi sebagian besar referensi yang saya temukan tampaknya berasal dari pertengahan tahun 90-an; rupanya ada kesibukan pada subjek saat itu yang sudah mereda. Jika kemampuan belum diperpanjang oleh beasiswa yang lebih baru jauh melampaui apa yang mereka di tahun 90-an, maka saya berharap seseorang datang dengan solusi yang lebih luas yang berlaku segera sehingga saya dapat mulai menghitung dimensi VC pada jaring saraf saya juga. Maaf saya tidak bisa
1 Bartlett, Peter L. dan Maass, Wolfgang, 2003, "Vapnik-Chervonenkis Dimensi Neural Nets," hlm. 1188-1192 dalam Buku Pegangan Teori Otak dan Jaringan Syaraf Tiruan, Arbib, Michael A. ed. MIT Press: Cambridge, Mass.
2 Karpinski, Marek dan Macintyre, Angus, 1995, "Mengikat Dimensi VC untuk Jaringan Saraf Tiruan: Kemajuan dan Prospek," hlm. 337–341 dalam Prosiding Konferensi Eropa ke-2 tentang Teori Pembelajaran Komputasi, Barcelona, Spanyol. Vitanyi, P. ed. Catatan Kuliah di Inteligensi Buatan, No. 904. Springer: Berlin.
sumber
Ini karya terbaru: http://jmlr.org/papers/v20/17-612.html .
Mengingat keabsahan pekerjaan, saya pikir itu memberi batas berguna. Saya tidak yakin, bagaimanapun, ketatnya batas (dan terutama konstanta dan ) karena saya belum sepenuhnya membacanya.c C
sumber