The Computational Power of Neural Networks and Representations of Numbers in Non-Integer Bases
Abstract
We briefly survey the basic concepts and results concerning the computational power of neural net-orks which basically depends on the information content of eight parameters. In particular, recurrent neural networks with integer, rational, and arbitrary real weights are classi ed within the Chomsky and finer complexity hierarchies. Then we re ne the analysis between integer and rational weights by investigating an intermediate model of integer-weight neural networks with an extra analog rational-weight neuron (1ANN). We show a representation theorem which characterizes the classification problems solvable by 1ANNs, by using so-called cut languages. Our analysis reveals an interesting link to an active research field on non-standard positional numeral systems with non-integer bases. Within this framework, we introduce a new concept of quasi-periodic numbers which is used to classify the computational power of 1ANNs within the Chomsky hierarchy.
References
Allouche, J.P., Clarke, M., Sidorov, N.: Periodic unique beta-expansions: The Sharkovskii ordering. Ergodic Theory and Dynamical Systems 29(4), 1055–1074 (2009)
Alon, N., Dewdney, A.K., Ott, T.J.: Efficient simulation of finite automata by neural nets. Journal of the ACM 38(2), 495–514 (1991)
Baker, S.: Generalized golden ratios over integer alphabet. Integers 14(A15) (2014)
Baker, S.: On small bases which admit countably many expansions. Journal of Number Theory 147, 515–532 (2015)
Baker, S., Masakova, Z., Pelantova, E., Vavra, T.: On periodic representations in non-Pisot bases. arXiv:1604.03354v1 [math.NT] (2016)
Balc´azar, J.L., Gavald`a, R., Siegelmann, H.T.: Computational power of neural networks: A characterization in terms of Kolmogorov complexity. IEEE Transactions on Information Theory 43(4), 1175–1183 (1997)
Dombek, D., Mas´akov´a, Z., Pelantov´a, E.: Number representation using generalized (−β)-transformation. Theoretical Computer Science 412(48), 6653–6665 (2011)
Erdos, P., Joo, I., Komornik, V.: Characterization of the unique expansions 1 = P∞ i=1 q −ni and related problems. Bulletin de la Societe Mathematique de France 118(3), 377–390 (1990)
Frougny, C., Lai, A.C.: Negative bases and automata. Discrete Mathematics & Theoretical Computer Science 13(1), 75–94 (2011)
Glendinning, P., Sidorov, N.: Unique representations of real numbers in non-integer bases. Mathematical Research Letters 8(4), 535–543 (2001)
Goodfellow, I.J., Bengio, Y., Courville, A.C.: Deep Learning. Adaptive computation and machine learning. MIT Press (2016)
Hare, K.G.: Beta-expansions of Pisot and Salem numbers. In: Proceedings of the Waterloo Workshop in Computer Algebra 2006: Latest Advances in Symbolic Algorithms, pp. 67–84. World Scientific (2007)
Haykin, S.: Neural Networks: A Comprehensive Foundation, 2 edn. Prentice Hall (1998)
Horne, B.G., Hush, D.R.: Bounds on the complexity of recurrent neural network implementations of finite state machines. Neural Networks 9(2), 243–252 (1996)
Indyk, P.: Optimal simulation of automata by neural nets. In: Proceedings of the STACS 1995 Twelfth Annual Symposium on Theoretical Aspects of Computer Science, LNCS, vol. 900, pp. 337–348 (1995)
Kilian, J., Siegelmann, H.T.: The dynamic universality of sigmoidal neural networks. Information and Computation 128(1), 48–56 (1996)
Koiran, P.: A family of universal recurrent networks. Theoretical Computer Science 168(2), 473–480 (1996)
Komornik, V., Lai, A.C., Pedicini, M.: Generalized golden ratios of ternary alphabets. Journal of the European Mathematical Society 13(4), 1113–1146 (2011)
Komornik, V., Pedicini, M.: Critical bases for ternary alphabets. Acta Mathematica Hungarica 152(1), 25–57 (2017)
Kong, D., Li, W., Dekking, F.M.: Intersections of homogeneous cantor sets and beta-expansions. Nonlinearity 23(11), 2815–2834 (2010)
Maass, W.: Lower bounds for the computational power of networks of spiking neurons. Neural Computation 8(1), 1–40 (1996)
Minsky, M.: Computations: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs (1967)
Parry, W.: On the β-expansions of real numbers. Acta Mathematica Hungarica 11(3), 401–416 (1960)
Pedicini, M.: Greedy expansions and sets with deleted digits. Theoretical Computer Science 332(1-3), 313–336 (2005)
Renyi, A.: Representations for real numbers and their ergodic properties. Acta Mathematica Academiae Scientiarum Hungaricae 8(3-4), 477–493 (1957)
Schmidt, K.: On periodic expansions of Pisot numbers and Salem numbers. Bulletin of the London Mathematical Society 12(4), 269–278 (1980)
Sidorov, N.: Almost every number has a continuum of β-expansions. The American Mathematical Monthly 110(9), 838–842 (2003)
Sidorov, N.: Expansions in non-integer bases: Lower, middle and top orders. Journal of Number Theory 129(4), 741–754 (2009)
Siegelmann, H.T.: Recurrent neural networks and finite automata. Journal of Computational Intelligence 12(4), 567–574 (1996)
Siegelmann, H.T.: Neural Networks and Analog Computation: Beyond the Turing Limit. Birkh¨auser, Boston (1999)
Siegelmann, H.T., Sontag, E.D.: Analog computation via neural networks. Theoretical Computer Science 131(2), 331–360 (1994)
Siegelmann, H.T., Sontag, E.D.: On the computational power of neural nets. Journal of Computer System Science 50(1), 132–150 (1995)
Sıma, J.: Analog stable simulation of discrete neural networks. Neural Network World 7(6), 679–686 (1997)
Sıma, J.: Energy complexity of recurrent neural networks. Neural Computation 26(5), 953–973 (2014)
Sıma, J.: The power of extra analog neuron. In: Proceedings of the TPNC 2014 Third International Conference on Theory and Practice of Natural Computing, LNCS, vol. 8890, pp. 243–254. Springer (2014)
Sıma, J.: Neural networks between integer and rational weights. In: Proceedings of the IJCNN 2017 Thirties International Joint Conference on Neural Networks, pp. 154–161. IEEE (2017)
Sıma, J., Orponen, P.: Continuous-time symmetric Hopfield nets are computationally universal. Neural Computation 15(3), 693–733 (2003)
Sıma, J., Orponen, P.: General-purpose computation with neural networks: A survey of complexity theoretic results. Neural Computation 15(12), 2727–2778 (2003)
Sıma, J., Savicky, P.: Cut languages in rational bases. In: Proceedings of the LATA 2017 Eleventh International Conference on Language and Automata Theory and Applications, LNCS, vol. 10168, pp. 311–322. Springer (2017)
Sima, J., Wiedermann, J.: Theory of neuromata. Journal of the ACM 45(1), 155–178 (1998)
Sorel, M., Sıma, J.: Robust RBF finite automata. Neurocomputing 62, 93–110 (2004)
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
