Abstract
We propose the use of hyperedge replacement graph grammars for factor graphs, or factor graph grammars (FGGs) for short. FGGs generate sets of factor graphs and can describe a more general class of models than plate notation, dynamic graphical models, case-factor diagrams, and sum-product networks can. Moreover, inference can be done on FGGs without enumerating all the generated factor graphs. For finite variable domains (but possibly infinite sets of graphs), a generalization of variable elimination to FGGs allows exact and tractable inference in many situations. For finite sets of graphs (but possibly infinite variable domains), a FGG can be converted to a single factor graph amenable to standard inference techniques.
1. Introduction
In fields such as natural language processing (NLP) and robotics, probabilistic models must often account for data with variable or alternative structures. A standard Hidden Markov Model (HMM), for instance, must "unroll" to match the length of an input sequence, while a Probabilistic Context-Free Grammar (PCFG) might represent a multitude of possible parse trees for a single sentence.
Traditional formalisms like plate notation are adept at handling repetition but struggle with structural alternatives. Conversely, Sum-Product Networks (SPNs) excel at representing alternatives but are typically restricted to fixed-length inputs. While general-purpose probabilistic programming languages can handle both, they often sacrifice the possibility of exact, efficient inference. Factor Graph Grammars (FGGs) are introduced to bridge this gap, offering a formalism that is more expressive than plates or SPNs while remaining constrained enough to support efficient, exact inference algorithms.
2. Methodology
The core of the FGG framework is the application of Hyperedge Replacement Grammars (HRGs) to factor graphs. An FGG consists of a set of production rules that define how to replace a "nonterminal" hyperedge—a placeholder for a substructure—with a fragment of a factor graph. This fragment may contain variables, factors, and additional nonterminal edges, allowing for recursive generation of potentially infinite sets of factor graphs.
A pivotal operation in this framework is conjunction. In practice, one often has a general model (e.g., a grammar for all possible HMMs) and a specific observation (e.g., a specific sequence of words). The conjunction operation allows these two grammars to be combined into a new FGG that represents the model constrained by the evidence. This modularity allows researchers to define complex models independently of the specific queries they wish to run.
Inference in FGGs is performed without enumerating the generated graphs. For models with finite variable domains, the authors generalize the Variable Elimination (VE) algorithm to work directly on the grammar rules. This process involves setting up and solving a system of polynomial equations where each variable represents the sum-product of a nonterminal. By solving these equations, the algorithm captures the aggregate behavior of the entire language of graphs generated by the grammar.
3. Key Insights and Theoretical Boundaries
FGGs serve as a unifying "super-formalism." The paper proves that FGGs can simulate several major frameworks, including plated factor graphs, dynamic graphical models, case-factor diagrams, and valid sum-product networks. Any model constructible in these frameworks can be represented, often more elegantly, as an FGG.
The authors also identify a fundamental complexity hierarchy within the grammar. Inference is generally tractable for "linearly recursive" grammars, such as those representing HMMs. However, it becomes significantly more complex for "non-linearly recursive" grammars, such as those for PCFGs. This distinction mirrors the jump in computational complexity from the Viterbi algorithm to the CKY algorithm in NLP.
Furthermore, the paper establishes the limits of computation for FGGs. If a model involves both an infinite set of graphs and infinite variable domains (e.g., continuous values), inference becomes undecidable. The authors demonstrate this by showing that an FGG can simulate the tape and transitions of a Turing Machine, proving that no general algorithm can solve all such inference problems.
4. Results and Empirical Simulation
The theoretical results demonstrate the efficiency of FGG-based inference. For nonrecursive FGGs with finite domains, the complexity is $O(|G|m^{k+1})$, where $|G|$ is the number of rules, $m$ is the domain size, and $k$ is related to the treewidth of the rules. This matches the performance of standard Variable Elimination on equivalent fixed graphs.
When applied to PCFGs, the FGG inference algorithm naturally recovers the $O(n^3)$ complexity of the classic CKY algorithm, where $n$ is the sentence length. This confirms that FGGs are not just a theoretical curiosity but a practical tool capable of matching the performance of specialized algorithms while providing a much broader modeling scope.
5. Limitations and Future Directions
Despite their power, FGGs face certain challenges. When converting an FGG to a single factor graph for models with infinite domains, the "treewidth" of the resulting graph can blow up, making standard inference techniques prohibitively slow.
Future work will focus on developing approximate inference techniques for non-linearly recursive models where exact solutions are currently too slow for real-world applications. Additionally, the authors plan to release a software library that implements these algorithms as differentiable operations, making FGGs accessible to the broader machine learning and deep learning communities.
Summary updated