Complexity of neural networks on Fibonacci-Cayley tree

Year 2019, , 105 - 122, 07.05.2019

Jung-chao Ban Chih-hung Chang

https://doi.org/10.13069/jacodesmath.560410

Abstract

This paper investigates the coloring problem on Fibonacci-Cayley tree, which is a Cayley graph whose vertex set is the Fibonacci sequence. More precisely, we elucidate the complexity of shifts of finite type defined on Fibonacci-Cayley tree via an invariant called entropy. We demonstrate that computing the entropy of a Fibonacci tree-shift of finite type is equivalent to studying a nonlinear recursive system and reveal an algorithm for the computation. What is more, the entropy of a Fibonacci tree-shift of finite type is the logarithm of the spectral radius of its corresponding matrix. We apply the result to neural networks defined on Fibonacci-Cayley tree, which reflect those neural systems with neuronal dysfunction. Aside from demonstrating a surprising phenomenon that there are only two possibilities of entropy for neural networks on Fibonacci-Cayley tree, we address the formula of the boundary in the parameter space.

Keywords

Neural networks, Learning problem, Cayley tree, Separation property, Entropy

Thanks

This work is partially supported by the Ministry of Science and Technology, ROC (Contract No MOST 107- 2115-M-259-004-MY2 and 107-2115-M-390-002-MY2).

References

• [1] M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge Univer- sity Press, Cambridge, 1999.
• [2] V. R. V. Assis, M. Copelli, Dynamic range of hypercubic stochastic excitable media, Phys. Rev. E 77(1) (2008) 011923.
• [3] N. Aubrun, M.-P. Béal, Tree–shifts of finite type, Theoret. Comput. Sci. 459(9) (2012) 16–25.
• [4] N. Aubrun, M.-P. Béal, Sofic tree–shifts, Theory Comput. Syst. 53(4) (2013) 621–644.
• [5] J.-C. Ban, C.-H. Chang, Realization problem of multi–layer cellular neural networks, Neural Networks 70 (2015) 9–17.
• [6] J.-C. Ban, C.-H. Chang, Characterization for entropy of shifts of finite type on Cayley trees, 2017, arXiv:1705.03138.
• [7] J.-C. Ban, C.-H. Chang, Tree-shifts: Irreducibility, mixing, and chaos of tree–shifts, Trans. Amer. Math. Soc. 369 (2017) 8389–8407.
• [8] J.-C. Ban, C.-H. Chang, Tree-shifts: The entropy of tree–shifts of finite type, Nonlinearity 30(7) (2017) 2785–2804.
• [9] J.-C. Ban, C.-H. Chang, S.-S. Lin, Y.-H Lin, Spatial complexity in multi-layer cellular neural net- works, J. Differ. Equ. 246(2) (2009) 552–580.
• [10] H. Braak, K. D. Tredici, Alzheimer’s pathogenesis: Is there neuron-to-neuron propagation?, Acta Neuropathol. 121(5) (2011) 589–595.
• [11] P. Brundin, R. Melki, R. Kopito, Prion–like transmission of protein aggregates in neurodegenerative diseases, Nat. Rev. Mol. Cell Biol. 11(4) (2010) 301–307.
• [12] C.-H. Chang, Deep and shallow architecture of multilayer neural networks, IEEE Trans. Neural Netw. Learn. Syst. 26(10) (2015) 2477–2486.
• [13] L. O. Chua, L. Yang, Cellular neural networks: Theory, IEEE Trans. Circuits Syst. 35(10) (1988) 1257–1272.
• [14] M. Goedert, F. Clavaguera, M. Tolnay, The propagation of prion–like protein inclusions in neurode- generative diseases, Trends Neurosci. 33(7) (2010) 317–325.
• [15] L. L. Gollo, O. Kinouchi, M. Copelli, Active dendrites enhance neuronal dynamic range, PLoS Comput. Biol. 5(6) (2009) e1000402.
• [16] L. L. Gollo, O. Kinouchi, M. Copelli, Statistical physics approach to dendritic computation: The excitable–wave mean–field approximation, Phys. Rev. E 85 (2012) 011911.
• [17] L. L. Gollo, O. Kinouchi, M. Copelli, Single–neuron criticality optimizes analog dendritic computa- tion, Sci. Rep. 3 (2013) 3222.
• [18] O. Kinouchi, M. Copelli, Optimal dynamical range of excitable networks at criticality, Nat. Phys. 2 (2006) 348–351.
• [19] D. B. Larremore, W. L. Shew, J. G. Restrepo, Predicting criticality and dynamic range in complex networks: Effects of topology, Phys. Rev. Lett. 106 (2011) 058101.
• [20] A. Pomi, A possible neural representation of mathematical group structures, Bull. Math. Biol. 78(9) (2016) 1847–1865.