Calcul de la dimension VC d'un réseau de neurones

Si j'ai une topologie fixe non récurrente (DAG) (ensemble fixe de nœuds et de bords, mais l'algorithme d'apprentissage peut faire varier le poids sur les bords) de neurones sigmoïdes avec neurones d'entrée qui ne peuvent prendre que des chaînes dans en entrée et conduit à une sortie (qui génère une valeur réelle que nous arrondissons à 1 ou à -1 s'il s'agit d'un certain seuil fixe éloigné de 0). Existe-t-il un moyen rapide de calculer (ou approximer) la dimension VC de ce réseau?{ - 1 , 1 } $n$$\{-1,1\}^n$

Remarques

J'ai demandé une reformulation algorithmique légèrement plus précise sur CS.SE:

Calcul ou approximation efficace de la dimension VC d'un réseau de neurones

Je suis tombé sur votre message en cherchant une formule générale pour calculer les dimensions VC sur les réseaux neuronaux, mais apparemment il n'y en a pas. Apparemment, nous n'avons qu'un méli-mélo d'équations VC disparates qui ne s'appliquent que dans certains cas étroits. Attention: je fonde cela sur de vieilles recherches que je comprends à peine, sur le concept de VC Dimensions, que je ne connais que maintenant. Néanmoins, il peut être utile de parcourir ce document de Peter L. Bartlett et Wolfgang Maass 1sur la calculabilité des dimensions VC. Notez comment ils vont très loin pour dériver des formules VC dans 13 théorèmes, mais combien diverses et nombreuses sont les conditions nécessaires pour chacun. Ces conditions préalables vont du nombre d'opérateurs dans les fonctions d'activation aux types de sauts autorisés, au nombre de neurones et à leurs positions, à la profondeur de bits de l'entrée, etc .; il y a tellement de ces "pièges" dispersés qu'ils rendent les formules utiles seulement pour certaines classes étroites de problèmes. Pour aggraver les choses, ils soulignent dans les théorèmes 5 et 8 que les fonctions d'activation sigmoïde sont particulièrement difficiles à calculer pour les valeurs VC. Aux pages 6-7, ils écrivent:

"Alors que la dimension VC des réseaux avec des fonctions d'activation polynomiales par morceaux est bien comprise, la plupart des applications des réseaux de neurones utilisent la fonction sigmoïde logistique, ou fonction de base radiale gaussienne. Malheureusement, il n'est pas possible de calculer de telles fonctions en utilisant un nombre fini de opérations arithmétiques énumérées dans le théorème 5. Cependant, Karpinski et Macintyre [Karpinski et Macintyre, 1997] ont étendu le théorème 5 pour permettre le calcul des exponentielles. La preuve utilise les mêmes idées, mais la limite sur le nombre de solutions d'un système d'équations est beaucoup plus difficile. "

J'ai également parcouru ce document avec le titre encourageant de «Bounding VC-Dimension for Neural Networks: Progress and Prospects». 2Beaucoup de maths sont au-dessus de ma tête et je ne l'ai pas survolé assez longtemps pour surmonter mon manque de compétences en traduction, mais je soupçonne qu'il n'offre aucune solution bouleversante, car il est antérieur à la deuxième édition du livre Bartlett et Maass, qui citent un travail ultérieur des mêmes auteurs. Peut-être que des recherches ultérieures au cours des 20 dernières années ont amélioré la calculabilité des dimensions VC pour les réseaux neuronaux, mais la plupart des références que j'ai trouvées semblent dater du milieu des années 90; apparemment, il y avait une avalanche de travaux sur le sujet à l'époque qui s'est depuis éteint. Si les capacités n'ont pas été étendues par des études plus récentes bien au-delà de ce qu'elles étaient dans les années 90, alors j'espère que quelqu'un trouvera bientôt une solution plus largement applicable afin que je puisse commencer à calculer les dimensions VC sur mes réseaux neuronaux également. Désolé je n'ai pas pu

1 Bartlett, Peter L. et Maass, Wolfgang, 2003, «Vapnik-Chervonenkis Dimension of Neural Nets», pp. 1188-1192 dans The Handbook of Brain Theory and Neural Networks, Arbib, Michael A. ed. MIT Press: Cambridge, Mass.

2 Karpinski, Marek et Macintyre, Angus, 1995, «Bounding VC-Dimension for Neural Networks: Progress and Prospects», pp. 337–341 dans Actes de la 2e Conférence européenne sur la théorie de l'apprentissage computationnel, Barcelone, Espagne. Vitanyi, P. éd. Notes de cours en intelligence artificielle, n ° 904. Springer: Berlin.

Voici les derniers travaux: http://jmlr.org/papers/v20/17-612.html .

Fondamentalement, un réseau avec poids, couches, et les activations de RELU suit: pour des constantes et .$W$$L$

Étant donné la validité de l'œuvre, je pense qu'elle donne des limites pratiques. Je ne suis pas sûr, cependant, de l'étroitesse des bornes (et surtout des constantes et ) car je ne l'ai pas entièrement lu.$c$$C$