Learning Graph Weighted Models on Pictures
This work addresses the challenge of extending automata learning to 2D data for researchers in formal languages and machine learning, but it is incremental as it builds on existing GWM theory with limited experimental scope.
The paper tackled the problem of learning Graph Weighted Models (GWMs) for pictures, a generalization of weighted automata to 2D structures, by testing gradient-based methods on regression and classification tasks for Bars & Stripes and Shifting Bits picture languages. The results showed that these languages can be learned from examples using GWMs, suggesting feasibility for broader applications.
Graph Weighted Models (GWMs) have recently been proposed as a natural generalization of weighted automata over strings and trees to arbitrary families of labeled graphs (and hypergraphs). A GWM generically associates a labeled graph with a tensor network and computes a value by successive contractions directed by its edges. In this paper, we consider the problem of learning GWMs defined over the graph family of pictures (or 2-dimensional words). As a proof of concept, we consider regression and classification tasks over the simple Bars & Stripes and Shifting Bits picture languages and provide an experimental study investigating whether these languages can be learned in the form of a GWM from positive and negative examples using gradient-based methods. Our results suggest that this is indeed possible and that investigating the use of gradient-based methods to learn picture series and functions computed by GWMs over other families of graphs could be a fruitful direction.