Research Article
BibTex RIS Cite

Complexity of neural networks on Fibonacci-Cayley tree

Year 2019, Volume: 6 Issue: 2, 105 - 122, 07.05.2019
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.

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.
Year 2019, Volume: 6 Issue: 2, 105 - 122, 07.05.2019
https://doi.org/10.13069/jacodesmath.560410

Abstract

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.
There are 20 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Jung-chao Ban This is me 0000-0002-4920-6945

Chih-hung Chang This is me 0000-0001-7352-5148

Publication Date May 7, 2019
Published in Issue Year 2019 Volume: 6 Issue: 2

Cite

APA Ban, J.-c., & Chang, C.-h. (2019). Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications, 6(2), 105-122. https://doi.org/10.13069/jacodesmath.560410
AMA Ban Jc, Chang Ch. Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications. May 2019;6(2):105-122. doi:10.13069/jacodesmath.560410
Chicago Ban, Jung-chao, and Chih-hung Chang. “Complexity of Neural Networks on Fibonacci-Cayley Tree”. Journal of Algebra Combinatorics Discrete Structures and Applications 6, no. 2 (May 2019): 105-22. https://doi.org/10.13069/jacodesmath.560410.
EndNote Ban J-c, Chang C-h (May 1, 2019) Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications 6 2 105–122.
IEEE J.-c. Ban and C.-h. Chang, “Complexity of neural networks on Fibonacci-Cayley tree”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 6, no. 2, pp. 105–122, 2019, doi: 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.
JAMA Ban J-c, Chang C-h. Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019;6:105–122.
MLA Ban, Jung-chao and Chih-hung Chang. “Complexity of Neural Networks on Fibonacci-Cayley Tree”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 6, no. 2, 2019, pp. 105-22, doi:10.13069/jacodesmath.560410.
Vancouver Ban J-c, Chang C-h. Complexity of neural networks on Fibonacci-Cayley tree. Journal of Algebra Combinatorics Discrete Structures and Applications. 2019;6(2):105-22.