Complexity of neural networks on Fibonacci-Cayley tree

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

References

1. [1] M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge Univer- sity Press, Cambridge, 1999.
2. [2] V. R. V. Assis, M. Copelli, Dynamic range of hypercubic stochastic excitable media, Phys. Rev. E 77(1) (2008) 011923.
3. [3] N. Aubrun, M.-P. Béal, Tree–shifts of finite type, Theoret. Comput. Sci. 459(9) (2012) 16–25.
4. [4] N. Aubrun, M.-P. Béal, Sofic tree–shifts, Theory Comput. Syst. 53(4) (2013) 621–644.
5. [5] J.-C. Ban, C.-H. Chang, Realization problem of multi–layer cellular neural networks, Neural Networks 70 (2015) 9–17.
6. [6] J.-C. Ban, C.-H. Chang, Characterization for entropy of shifts of finite type on Cayley trees, 2017, arXiv:1705.03138.
7. [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. [8] J.-C. Ban, C.-H. Chang, Tree-shifts: The entropy of tree–shifts of finite type, Nonlinearity 30(7) (2017) 2785–2804.

9. [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. [10] H. Braak, K. D. Tredici, Alzheimer’s pathogenesis: Is there neuron-to-neuron propagation?, Acta Neuropathol. 121(5) (2011) 589–595.
11. [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. [12] C.-H. Chang, Deep and shallow architecture of multilayer neural networks, IEEE Trans. Neural Netw. Learn. Syst. 26(10) (2015) 2477–2486.
13. [13] L. O. Chua, L. Yang, Cellular neural networks: Theory, IEEE Trans. Circuits Syst. 35(10) (1988) 1257–1272.
14. [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. [15] L. L. Gollo, O. Kinouchi, M. Copelli, Active dendrites enhance neuronal dynamic range, PLoS Comput. Biol. 5(6) (2009) e1000402.
16. [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. [17] L. L. Gollo, O. Kinouchi, M. Copelli, Single–neuron criticality optimizes analog dendritic computa- tion, Sci. Rep. 3 (2013) 3222.
18. [18] O. Kinouchi, M. Copelli, Optimal dynamical range of excitable networks at criticality, Nat. Phys. 2 (2006) 348–351.
19. [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. [20] A. Pomi, A possible neural representation of mathematical group structures, Bull. Math. Biol. 78(9) (2016) 1847–1865.