A Hierarchical Classification of First-Order Recurrent Neural Networks

10.4077/CJP.2010.AMM037

Jérémie Cabessa；Alessandro E.P. Villa

neural networks ； attractors ； Büchi automata ； Wadge hierarchy

The Chinese Journal of Physiology

53卷6期（2010 / 12 / 01）

407 - 416

英文

We provide a decidable hierarchical classification of first-order recurrent neural networks made up of McCulloch and Pitts cells. This classification is achieved by proving an equivalence result between such neural networks and deterministic Büuchi automata, and then translating the Wadge classification theory from the abstract machine to the neural network context. The obtained hierarchy of neural networks is proved to have width 2 and height ω+1, and a decidability procedure of this hierarchy is provided. Notably, this classification is shown to be intimately related to the attractive properties of the considered networks.

1. McCulloch, W.S. and Pitts, W. A logical calculus of the ideas immanent in nervous activity. Bull. Math. Biophys. 5: 115-133, 1943.
2. Duparc, J.(2003).A hierarchy of deterministic context-free ω-languages.Theor. Comput. Sci.,290,1253-1300.
3. Duparc, J.(2001).Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank.J. Symb. Log.,66,56-86.
4. Duparc, J.,Finkel, O.,Ressayre, J.-P.(2001).Computer science and the fine structure of Borel sets.Theor. Comput. Sci.,257,85-105.
5. Finkel, O.(2001).An effective extension of the Wagner hierarchy to blind counter automata.Lect. Notes Comput. Sci.,2142,369-383.
6. Kaneko, K.,Tsuda, I.(2003).Chaotic itinerancy.Chaos,13,926-936.
7. Kilian, J.,Siegelmann, H. T.(1996).The dynamic universality of sigmoidal neural networks.Inf. Comput.,128,48-56.
8. Kleene, S. C.(1956).Automata Studies, volume 34 of Annals of Mathematics Studies.Princeton, N. J.:Princeton University Press.
9. Kremer, S. C.(1995).On the computational power of elman-style recurrent networks.Neural Networks, IEEE Transactions on,6,1000-1004.
10. Minsky, M. L.(1967).Computation: finite and infinite machines.Upper Saddle River, NJ, USA:Prentice-Hall, Inc..
11. Perrin, D.,Pin, J.-E.(2004).Infinite Words, volume 141 of Pure and Applied Mathematics.Elsevier.
12. Selivanov, V.(2003).Wadge degrees of ω-languages of deterministic Turing machines.Theor. Inform. Appl.,37,67-83.
13. Siegelmann, H. T.(1995).Computation beyond the Turing limit.Science,268,545-548.
14. Siegelmann, H. T.(2003).Neural and super-Turing computing.Minds Mach.,13,103-114.
15. Siegelmann, H. T.,Sontag, E. D.(1991).Turing computability with neural nets.Appl. Math. Lett.,4,77-80.
16. Siegelmann, H. T.,Sontag, E. D.(1995).On the computational power of neural nets.J. Comput. Syst. Sci.,50,132-150.
17. Siegelmann, H. T.,Sontag, E. D.(1994).Analog computation via neural networks.Theor. Comput. Sci.,131,331-360.
18. Sperduti, A.(1997).On the computational power of recurrent neural networks for structures.Neural Netw.,10,395-400.
19. Tsuda, I.(1991).Chaotic itinerancy as a dynamical basis of hermeneutics of brain and mind.World Futures,32,167-185.
20. Tsuda, I.,Koerner, E.,Shimizu, H.(1987).Memory dynamics in asynchronous neural networks.Prog. Theor. Phys.,78,51-71.
21. Wadge, W. W.(1983).Berkeley,University of California.
22. Wagner, K.(1979).On ω-regular sets.Inform. Control,43,123-177.