The expressive power of analog recurrent neural networks on infinite input streams

Jérémie Cabessa 1, * Alessandro Villa 2, *
* Auteur correspondant
1 Inserm U836, équipe 7, Nanomédecine et cerveau
GIN - Grenoble Institut des Neurosciences
2 INSERM U836, équipe 7, Nanomédecine et cerveau
GIN - Grenoble Institut des Neurosciences, Department of Information Systems
Abstract : We consider analog recurrent neural networks working on in nite input streams, provide a complete topological characterization of their expressive power, and compare it to the expressive power of classical in nite word reading abstract machines. More precisely, we consider analog recurrent neural networks as language recognizers over the Cantor space, and prove that the classes of !-languages recognized by deterministic and non-deterministic analog networks correspond precisely to the respective classes of 02 -sets and 11 -sets of the Cantor space. Furthermore, we show that the result can be generalized to more expressive analog networks equipped with any kind of Borel accepting condition. Therefore, in the deterministic case, the expressive power of analog neural nets turns out to be comparable to the expressive power of any kind of Buchi abstract machine, whereas in the non-deterministic case, analog recurrent networks turn out to be strictly more expressive than any other kind of Buchi or Muller abstract machine, including the main cases of classical automata, 1-counter automata, k-counter automata, pushdown automata, and Turing machines.
Type de document :
Article dans une revue
Theor Compt Sci, 2012, 436, pp.23-34. 〈10.1016/j.tcs.2012.01.042〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

http://www.hal.inserm.fr/inserm-00851237
Contributeur : Jean-Paul Issartel <>
Soumis le : mardi 13 août 2013 - 10:03:07
Dernière modification le : jeudi 1 février 2018 - 01:11:45
Document(s) archivé(s) le : mercredi 5 avril 2017 - 20:40:16

Fichiers

Cabessa-2012_The_expressive_AE...
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

UGA | U836

Citation

Jérémie Cabessa, Alessandro Villa. The expressive power of analog recurrent neural networks on infinite input streams. Theor Compt Sci, 2012, 436, pp.23-34. 〈10.1016/j.tcs.2012.01.042〉. 〈inserm-00851237〉

Partager

Métriques

Consultations de la notice

172

Téléchargements de fichiers

252