Komputasi atau perkiraan dimensi VC jaringan saraf secara efisien

Tujuan saya adalah untuk memecahkan masalah berikut ini, yang telah saya jelaskan dengan input dan outputnya:

Memasukkan:

Grafik asiklik diarahkan dengan node, sumber, dan sink ( ).$G$$m$$n$$1$$m > n \geq 1$

Keluaran:

The VC-dimensi (atau perkiraan itu) untuk jaringan saraf dengan topologi .$G$

Lebih spesifik :

• Setiap node dalam adalah neuron sigmoid. Topologi sudah diperbaiki, tetapi bobot pada tepian dapat bervariasi dengan algoritma pembelajaran.$G$
• Algoritma pembelajaran sudah diperbaiki (katakanlah backward-propagation).
• The node sumber adalah neuron masukan dan hanya dapat mengambil string dari sebagai input.$n$$\{-1,1\}^n$
• Node wastafel adalah unit output. Ini menghasilkan nilai nyata dari yang kita bulatkan hingga atau turun menjadi jika lebih dari ambang batas tetap tertentu dari .$[-1,1]$$1$$-1$$\delta$$0$

Pendekatan naif hanya mencoba untuk memecahkan lebih banyak poin, dengan mencoba untuk melatih jaringan pada mereka. Namun, pendekatan simulasi semacam ini tidak efisien.

Pertanyaan

Apakah ada cara yang efisien (yaitu dalam ketika diubah ke masalah-keputusan: apakah dimensi-VC kurang dari parameter input ?) Untuk menghitung fungsi ini? Jika tidak, apakah ada hasil kekerasan?$\mathsf{P}$$k$

Apakah ada cara yang berfungsi dengan baik dalam praktik untuk menghitung atau memperkirakan fungsi ini? Jika perkiraan, apakah ada jaminan keakuratannya?

Catatan

Saya mengajukan pertanyaan serupa di stats.SE tetapi tidak menghasilkan minat.

Jika Anda ingin membatasi masalah lebih lanjut dengan membiarkan jaringan berlapis, "Pembelajaran Mesin" Tom Mitchell memberikan batas atas ( ) (bagian 7.4.4) di mana adalah jumlah node internal (yang harus lebih tinggi dari 2), adalah dimensi VC dari masing-masing node, dan adalah basis dari logaritma natural. Jika Anda setelah terikat pada jumlah contoh pelatihan maka informasi ini harus cukup.s d $2ds \log(es)$$s$$d$$e$

Ini bukan jawaban untuk pertanyaan Anda, tetapi mungkin bisa membantu Anda dalam perjalanan. Hasilnya adalah karena Baum dan Haussler (1989).