On functions computed on trees

  • 2019-04-04 02:15:35
  • Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, Konrad Paul Kording
  • 55


Any function can be constructed using a hierarchy of simpler functionsthrough compositions. Such a hierarchy can be characterized by a binary rootedtree. Each node of this tree is associated with a function which takes asinputs two numbers from its children and produces one output. Since thinkingabout functions in terms of computation graphs is getting popular we may wantto know which functions can be implemented on a given tree. Here, we describe aset of necessary constraints in the form of a system of non-linear partialdifferential equations that must be satisfied. Moreover, we prove that theseconditions are sufficient in both contexts of analytic and bit-value functions.In the latter case, we explicitly enumerate discrete functions and observe thatthere are relatively few. Our point of view allows us to compare differentneural network architectures in regard to their function spaces. Our workconnects the structure of computation graphs with the functions they canimplement and has potential applications to neuroscience and computer science.


Introduction (beta)



Conclusion (beta)