Year 2019, Volume 6 , Issue 2, Pages 105 - 122 2019-05-07

Complexity of neural networks on Fibonacci-Cayley tree

Jung-chao BAN [1] , Chih-hung CHANG [2]


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.
Neural networks, Learning problem, Cayley tree, Separation property, Entropy
  • [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.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0002-4920-6945
Author: Jung-chao BAN

Orcid: 0000-0001-7352-5148
Author: Chih-hung CHANG (Primary Author)

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).
Dates

Publication Date : May 7, 2019

Bibtex @research article { jacodesmath560410, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {}, publisher = {Yildiz Technical University}, year = {2019}, volume = {6}, pages = {105 - 122}, doi = {10.13069/jacodesmath.560410}, title = {Complexity of neural networks on Fibonacci-Cayley tree}, key = {cite}, author = {Ban, Jung-chao and Chang, Chih-hung} }
APA Ban, J , Chang, C . (2019). Complexity of neural networks on Fibonacci-Cayley tree . Journal of Algebra Combinatorics Discrete Structures and Applications , 6 (2) , 105-122 . DOI: 10.13069/jacodesmath.560410
MLA Ban, J , Chang, C . "Complexity of neural networks on Fibonacci-Cayley tree" . Journal of Algebra Combinatorics Discrete Structures and Applications 6 (2019 ): 105-122 <https://dergipark.org.tr/en/pub/jacodesmath/issue/45030/560410>
Chicago Ban, J , Chang, C . "Complexity of neural networks on Fibonacci-Cayley tree". Journal of Algebra Combinatorics Discrete Structures and Applications 6 (2019 ): 105-122
RIS TY - JOUR T1 - Complexity of neural networks on Fibonacci-Cayley tree AU - Jung-chao Ban , Chih-hung Chang Y1 - 2019 PY - 2019 N1 - doi: 10.13069/jacodesmath.560410 DO - 10.13069/jacodesmath.560410 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 105 EP - 122 VL - 6 IS - 2 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.560410 UR - https://doi.org/10.13069/jacodesmath.560410 Y2 - 2019 ER -
EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Complexity of neural networks on Fibonacci-Cayley tree %A Jung-chao Ban , Chih-hung Chang %T Complexity of neural networks on Fibonacci-Cayley tree %D 2019 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 6 %N 2 %R doi: 10.13069/jacodesmath.560410 %U 10.13069/jacodesmath.560410
ISNAD Ban, Jung-chao , Chang, Chih-hung . "Complexity of neural networks on Fibonacci-Cayley tree". Journal of Algebra Combinatorics Discrete Structures and Applications 6 / 2 (May 2019): 105-122 . https://doi.org/10.13069/jacodesmath.560410
AMA Ban J , Chang C . Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019; 6(2): 105-122.
Vancouver Ban J , Chang C . Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019; 6(2): 105-122.