Puissance de calcul des réseaux de neurones?

13

Supposons que nous ayons un réseau de neurones à rétroaction simple couche avec k entrées et une sortie. Il calcule une fonction à partir de , il est assez facile de voir que cela a au moins la même puissance de calcul que A C 0 . Juste pour le plaisir, nous appellerons l'ensemble des fonctions calculables par une seule couche réseau de neurones « N e u r un l ».{0,1}n{0,1}AC0Neural

Il semble cependant qu'il pourrait avoir plus de puissance de calcul que seul.AC0

Alors ... est ou N e u r a l = A C 0 ? Ce type de classe de complexité a-t-il également été étudié auparavant?UNEC0NeurunelNeurunel=UNEC0

gabgoh
la source
1
Remarque sur la terminologie - les informations importantes sont le nombre de couches cachées . Le réseau neuronal à couche cachée zéro avec une sortie n'est qu'une fonction de seuil linéaire et est souvent (confusément) appelé réseau neuronal / perceptron à une ou deux couches, selon que les entrées / sorties sont considérées comme des couches. De plus, dans la littérature sur l'IA, les réseaux de neurones sont généralement définis en termes de fonctions sigmoïdes, ce qui signifie que les entrées / sorties sont réellement valorisées. Les réseaux à une couche cachée sont connus pour être des approximateurs universels dans le sens où toute fonction continue peut être approximée de façon arbitrairement proche
Yaroslav Bulatov

Réponses:

16

Il y a quelques références que j'ai pu trouver: Calcul à usage général avec des réseaux de neurones: Une étude des résultats théoriques de la complexité, 2003 et Hiérarchies de comptage: circuits polynomiaux de temps et de profondeur constante, 1993 .

Il semble que les réseaux de neurones soient considérés comme des circuits à seuil; c'est-à-dire les circuits utilisant des portes MAJORITY. Dans (2), il est le cas qu'un réseau de neurones de profondeur a une complexité T C 0 d (voici un lien pour un lien vers une entrée de zoo de complexité sur T C 0 ).dTCd0TC0

TC0ACC0AC0AC0TC0

d

M. Alaggan
la source
Intéressant, merci. C'est ce que je cherchais. Plus intéressant encore est queTC0a un problème complet ... hmm ...
gabgoh