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

19

Mon objectif est de résoudre le problème suivant, que j'ai décrit par son entrée et sa sortie:

Contribution:

Un graphe acyclique dirigé avec m nœuds, n sources et 1 puits ( m > n ≥ 1 ).gmn1m>n≥1

Production:

Le VC-dimension (ou une approximation de celui - ci) pour le réseau de neurones avec une topologie .g

Plus de détails :

  • Chaque nœud de est un neurone sigmoïde. La topologie est fixe, mais les poids sur les bords peuvent être modifiés par l'algorithme d'apprentissage.g
  • L'algorithme d'apprentissage est fixe (disons la propagation vers l'arrière).
  • Les nœuds sources sont les neurones d'entrée et ne peuvent prendre en entrée que des chaînes de { - 1 , 1 } n .n{-1,1}n
  • Le nœud récepteur est l'unité de sortie. Il délivre une valeur réelle de que nous arrondissons à 1 ou à - 1 s'il est supérieur à un certain seuil fixe δ éloigné de 0 .[-1,1]1-1δ0

L'approche naïve consiste simplement à essayer de casser de plus en plus de points, en tentant de former le réseau sur eux. Cependant, ce type d'approche de simulation n'est pas efficace.

Question

Existe-t-il un moyen efficace (c'est-à-dire dans lorsqu'il est changé pour le problème de décision: la dimension VC est-elle inférieure au paramètre d'entrée k ?) Pour calculer cette fonction? Sinon, y a-t-il des résultats de dureté?Pk

Existe-t-il une méthode qui fonctionne bien dans la pratique pour calculer ou approximer cette fonction? S'il s'agit d'une approximation, y a-t-il des garanties sur son exactitude?

Remarques

J'ai posé une question similaire sur stats.SE mais cela n'a suscité aucun intérêt.

algorithms complexity-theory machine-learning neural-networks vc-dimension Artem Kaznatcheev
la source
1
Cela pourrait rendre la question plus autonome si vous pouviez rendre la fonction de transfert plus explicite. C'est-à-dire spécifier les formules réelles de propagation des informations.
Suresh

Réponses:

9

Si vous êtes disposé à limiter davantage le problème en laissant le réseau se superposer, alors le "Machine Learning" de Tom Mitchell donne une limite supérieure de ( ) (section 7.4.4) où s est le nombre de nœuds internes (qui doivent être supérieurs à 2), d est la dimension VC des nœuds individuels et e est la base du logarithme naturel. Si vous souhaitez connaître le nombre d'exemples de formation, ces informations devraient suffire.2résJournal⁡(es)srée

Ce n'est pas strictement une réponse à votre question, mais cela pourrait vous aider sur le chemin. Le résultat est dû à Baum et Haussler (1989).

Peter
la source