Tree-recursive computation of gradient information for structures.
Andreas Küchler · 1999
Abstract. Recently, the so-called Backpropagation Through Structure (BPTS) gradient calculation algorithm has been developed to capture learning scenarios where data is adequately represented by hybrid continuous-discrete structures (e.g. labeled ordered trees, nodes augmented by continuous information). BPTS can be viewed as an extension of the well-known Backpropagation Through Time (BPTT) algorithm for discrete-time dynamical systems and sequence processing. The well-known (functionally equivalent) Real-time Recurrent Learning (RTRL) algorithm has to be favored to BPTT if long sequences are processed. This paper investigates whether and how RTRL can be generalized { while conserving its appealing algorithmic properties { to calculate the gradient information for models operating on the domain of rooted labeled ordered trees. The answer is partly negative. It turns out that a postorder traversal of the tree has to be obeyed in order to keep the space consumption independent from the size of the input structures. By processing vertices in an inverse topological ordering the algorithm can also be applied on labeled directed ordered acyclic graphs. However, we show that on this graph domain the memory consumption grows (in the worst case) linearly with the size of the input structure. 1