{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T12:02:21Z","timestamp":1742385741936},"reference-count":52,"publisher":"MIT Press - Journals","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Neural Computation"],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p> Any function can be constructed using a hierarchy of simpler functions through compositions. Such a hierarchy can be characterized by a binary rooted tree. Each node of this tree is associated with a function that takes as inputs two numbers from its children and produces one output. Since thinking about functions in terms of computation graphs is becoming popular, we may want to know which functions can be implemented on a given tree. Here, we describe a set of necessary constraints in the form of a system of nonlinear partial differential equations that must be satisfied. Moreover, we prove that these conditions are sufficient in contexts of analytic and bit-valued functions. In the latter case, we explicitly enumerate discrete functions and observe that there are relatively few. Our point of view allows us to compare different neural network architectures in regard to their function spaces. Our work connects the structure of computation graphs with the functions they can implement and has potential applications to neuroscience and computer science. <\/jats:p>","DOI":"10.1162\/neco_a_01231","type":"journal-article","created":{"date-parts":[[2019,9,16]],"date-time":"2019-09-16T21:19:26Z","timestamp":1568668766000},"page":"2075-2137","source":"Crossref","is-referenced-by-count":2,"title":["On Functions Computed on Trees"],"prefix":"10.1162","volume":"31","author":[{"given":"Roozbeh","family":"Farhoodi","sequence":"first","affiliation":[{"name":"Departments of Bioengineering and Neuroscience, University of Pennsylvania, Philadelphia, PA 19104, U.S.A."}]},{"given":"Khashayar","family":"Filom","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Northwestern University, Evanston, IL 60208, U.S.A."}]},{"given":"Ilenna Simone","family":"Jones","sequence":"additional","affiliation":[{"name":"Departments of Bioengineering and Neuroscience, University of Pennsylvania, Philadelphia, PA 19104, U.S.A."}]},{"given":"Konrad Paul","family":"Kording","sequence":"additional","affiliation":[{"name":"Departments of Bioengineering and Neuroscience, University of Pennsylvania, Philadelphia, PA 19104, U.S.A."}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01742-1_5"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01742-1_6"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1523\/JNEUROSCI.2055-07.2007"},{"key":"B5","author":"Barron A. R.","year":"2018","journal-title":"Approximation and estimation for high-dimensional deep learning networks"},{"key":"B6","volume-title":"The curse of dimensionality for local kernel machines","author":"Bengio Y.","year":"2005"},{"key":"B7","first-page":"107","volume-title":"Advances in neural information processing systems, 16","author":"Bengio Y.","year":"2006"},{"key":"B8","author":"Benjamin A.","year":"2019","journal-title":"Proceedings of the International Conference on Learning Representations"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2013.2293637"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-015-0604-2"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1989.1.4.465"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200426"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6420\/aa9a90"},{"key":"B14","author":"Hanin B.","year":"2019","journal-title":"Complexity of linear regions in deep networks"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-79711-3"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3849-0"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01272517"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1902-00923-3"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.6.1179"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9861(19971006)386:4<661::AID-CNE11>3.0.CO;2-N"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-30873-3_2"},{"key":"B22","first-page":"953","volume":"114","author":"Kolmogorov A. N.","year":"1957","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1991.3.4.617"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2015.07.014"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2017.04.003"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-017-1836-5"},{"key":"B27","volume-title":"Approximation of functions","author":"Lorentz G. G.","year":"1966"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1806579115"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.6.1031"},{"key":"B30","volume-title":"Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence","author":"Mhaskar H.","year":"2017"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/11301.001.0001"},{"key":"B32","first-page":"2924","volume-title":"Advances in neural information processing systems","volume":"14","author":"Montufar G. F.","year":"2014"},{"key":"B33","volume-title":"Analysis on real and complex manifolds","author":"Narasimhan R.","year":"1968"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206530"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/s11633-017-1054-2"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/S0896-6273(03)00149-1"},{"key":"B37","volume-title":"The retina.","author":"Polyak S. L.","year":"1941"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-21684-3"},{"key":"B39","author":"Ramaswamy V.","year":"2019","journal-title":"Hierarchies and lower bounds in theoretical connectomics"},{"key":"B40","doi-asserted-by":"publisher","DOI":"10.1007\/s10827-014-0497-5"},{"key":"B41","volume-title":"Histology of the nervous system of man and vertebrates","author":"Ram\u00f3n y Cajal S.","year":"1995"},{"key":"B42","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9002(99)00114-X"},{"key":"B43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1634-6_5"},{"key":"B44","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2017.09.015"},{"key":"B45","volume-title":"Introduction to the theory of computation","author":"Sipser M.","year":"2006"},{"key":"B46","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-2236(96)10075-8"},{"key":"B47","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1994.6.5.851"},{"key":"B48","first-page":"701","volume":"95","author":"Vitu\u0161kin A. G.","year":"1954","journal-title":"Doklady Akad. Nauk SSSR (N.S.)"},{"key":"B49","first-page":"1258","volume":"156","author":"Vitu\u0161kin A. G.","year":"1964","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"B50","doi-asserted-by":"publisher","DOI":"10.1070\/RM2004v059n01ABEH000698"},{"issue":"1","key":"B51","first-page":"77","volume":"22","author":"Vitu\u0161kin A. G.","year":"1967","journal-title":"Uspehi Mat. Nauk"},{"key":"B52","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1996.8.3.611"}],"container-title":["Neural Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/neco_a_01231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:43:20Z","timestamp":1615585400000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/neco\/article\/31\/11\/2075-2137\/95669"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":52,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.1162\/neco_a_01231"],"URL":"https:\/\/doi.org\/10.1162\/neco_a_01231","relation":{},"ISSN":["0899-7667","1530-888X"],"issn-type":[{"value":"0899-7667","type":"print"},{"value":"1530-888X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}