Adaptive processing of structural data: from sequences to trees and beyond

Abstract

In computer science, structural (e.g. causal, topological, or hierarchical) relationships between parts of an object are commonly represented by symbolic formalisms such as graphs, terms or diagrams. Symbolic machine learning approaches can deal with these representations, but fail if the range of the intended mapping is of continuous nature. On the other hand, existing analog models of computation and learning are tailored to the processing of continuous information. However, these models assume that data are organized according relatively poor structures, by and large, arrays and sequences.

This work contributes in bridging this gap. We propose tree-recursive dynamical systems, a new class of deterministic state machines that operate in a continuous state space. Adaptivity is incorporated by parameterizing the state transition map and the output map. Classification and regression of rooted labeled ordered trees (whose vertices can be labeled by continuous feature vectors) are re-formulated as optimization tasks. We develop and analyse backpropagation through structure, an efficient algorithm for the calculation of gradient information. Thus, a variety of well-established gradient-based optimization methods can be applied.

The adequacy of this framework is demonstrated with the help of the neural folding architecture, an appealing artificial neural network implementation of tree-recursive dynamical systems. In order to get an initial understanding of the computational power of the neural folding architecture, we relate several variations to finite deterministic bottom-up tree automata, their discrete counterpart.

The presented results, techniques and algorithms provide a solid foundation and a new toolkit for building machine learning devices that directly operate on structural data. We survey some fascinating application areas, ranging from document processing and computational chemistry to the adaptive control of symbolic deduction systems.