Complexity of neural networks on Fibonacci-Cayley tree

  • Jung-Chao Ban
  • Chih-Hung Chang
Keywords: Neural networks, Learning problem, Cayley tree, Separation property, Entropy


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.


M. Anthony, P. L. Bartlett, Neural Network Learning: Theoretical Foundations, Cambridge University Press, Cambridge, 1999.

V. R. V. Assis, M. Copelli, Dynamic range of hypercubic stochastic excitable media, Phys. Rev. E 77(1) (2008) 011923.

N. Aubrun, M.-P. Béal, Tree–shifts of finite type, Theoret. Comput. Sci. 459(9) (2012) 16–25.

N. Aubrun, M.-P. Béal, Sofic tree–shifts, Theory Comput. Syst. 53(4) (2013) 621–644.

J.-C. Ban, C.-H. Chang, Realization problem of multi–layer cellular neural networks, Neural Networks 70 (2015) 9–17.

J.-C. Ban, C.-H. Chang, Characterization for entropy of shifts of finite type on Cayley trees, 2017, arXiv:1705.03138.

J.-C. Ban, C.-H. Chang, Tree-shifts: Irreducibility, mixing, and chaos of tree–shifts, Trans. Amer. Math. Soc. 369 (2017) 8389–8407.

J.-C. Ban, C.-H. Chang, Tree-shifts: The entropy of tree–shifts of finite type, Nonlinearity 30(7) (2017) 2785–2804.

J.-C. Ban, C.-H. Chang, S.-S. Lin, Y.-H Lin, Spatial complexity in multi-layer cellular neural networks, J. Differ. Equ. 246(2) (2009) 552–580.

H. Braak, K. D. Tredici, Alzheimer’s pathogenesis: Is there neuron-to-neuron propagation?, Acta Neuropathol. 121(5) (2011) 589–595.

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.

C.-H. Chang, Deep and shallow architecture of multilayer neural networks, IEEE Trans. Neural Netw. Learn. Syst. 26(10) (2015) 2477–2486.

L. O. Chua, L. Yang, Cellular neural networks: Theory, IEEE Trans. Circuits Syst. 35(10) (1988) 1257–1272.

M. Goedert, F. Clavaguera, M. Tolnay, The propagation of prion–like protein inclusions in neurodegenerative diseases, Trends Neurosci. 33(7) (2010) 317–325.

L. L. Gollo, O. Kinouchi, M. Copelli, Active dendrites enhance neuronal dynamic range, PLoS Comput. Biol. 5(6) (2009) e1000402.

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.

L. L. Gollo, O. Kinouchi, M. Copelli, Single–neuron criticality optimizes analog dendritic computation, Sci. Rep. 3 (2013) 3222.

O. Kinouchi, M. Copelli, Optimal dynamical range of excitable networks at criticality, Nat. Phys. 2 (2006) 348–351.

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.

A. Pomi, A possible neural representation of mathematical group structures, Bull. Math. Biol. 78(9) (2016) 1847–1865.