Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks

Robert Lieck, Martin RohrmeierNeurIPS 2021

The Modeling Dilemma: Hierarchy vs. Continuity

When modeling complex sequential data, researchers have traditionally been forced to choose between two powerful but fundamentally limited paradigms. On one hand, Probabilistic Context-Free Grammars (PCFGs) excel at representing nested, hierarchical dependencies—such as the syntax of a sentence—but they typically require discrete latent variables. On the other hand, Dynamic Bayesian Networks (DBNs), which include Hidden Markov Models and Kalman Filters, handle continuous latent variables beautifully but are restricted to linear, chain-like structures.

This creates a significant gap: how do we model data that is both hierarchical and continuous? For instance, a piece of music has a clear nested structure (notes form motives, which form phrases, which form sections), yet the underlying harmonic state is often better represented as a continuous vector of pitch distributions rather than a single discrete category.

RBNs fill the gap between linear/continuous models and hierarchical/discrete models.

Recursive Bayesian Networks (RBNs) are introduced to bridge this exact gap, providing a unified framework that combines the hierarchical power of PCFGs with the continuous latent variable capabilities of DBNs.

Methods: Unifying the Paradigms

The authors introduce RBNs as template-based graphical models, defining them such that both PCFGs and DBNs emerge naturally as special cases. To keep the mathematics manageable, they utilize a "Chomsky Normal Form" for RBNs.

Generalized Inside-Outside Algorithm

To perform inference, the classic Inside-Outside algorithm (widely used in Natural Language Processing) is extended to handle mixed discrete-continuous cases. This generalization allows for Maximum a Posteriori (MAP) estimates of continuous variables via gradient descent, all while marginalizing over an exponential number of possible tree structures.

Gaussian RBNs and Adaptive Approximation

For the specific case where transitions are linear Gaussians, the authors derive an analytic approximation known as Gaussian RBNs (GRBNs). Marginalizing over all possible tree structures creates an intractable "mixture of exponentially many Gaussians." To solve this, the authors employ an adaptive approximation (moment matching) to collapse these complex mixtures into a single Gaussian at each step of the recursion, maintaining computational tractability.

Adaptive approximation collapsing a complex mixture of Gaussians into a single tractable Gaussian component.

Crucially, RBNs feature structural control: the latent variables can dictate the structure itself. The probability of a specific branching structure depends directly on the value of the parent latent variable.

Experiments and Key Insights

The paper evaluates the RBN model on two distinct fronts: synthetic data and classical music.

1. Synthetic Tree Induction: Using 500 generated sequences with varying noise levels, the model was benchmarked on its ability to reconstruct hierarchies and segment data. RBNs consistently outperformed the baseline—a combination of Change Point Detection (CPD) and Hierarchical Clustering (HC)—in both precision and recall across all noise levels.

2. Emergent Music Theory from Bach: The model was tasked with performing hierarchical music analysis on the 24 major preludes from J.S. Bach’s The Well-Tempered Clavier, starting from raw note counts. Remarkably, the model "discovered" fundamental principles of Western music theory without explicit instruction.

  • Pitch Profiles: The model's learned "prior mean" perfectly matched the standard major pitch profile found in musicology literature.
  • Transposition Weights: The model identified that only two transpositions were significant in Bach's preludes: the identity (78%) and the fifth (22%). This provides empirical, data-driven validation of the "cadential dominant-tonic" progression that defines the Baroque era.

Precision vs. Uncertainty

The authors noted an interesting trade-off during inference. While marginal probabilities are excellent for precision (if the model predicts a boundary, it is usually correct), a fully Bayesian treatment tends to spread probability mass thin. This uncertainty can sometimes hurt recall compared to simpler "best-guess" estimates.

Limitations and Future Work

While RBNs offer a powerful new modeling paradigm, several challenges remain:

  • Non-Convexity: Because the model marginalizes over vast numbers of structures, the likelihood surface is highly non-convex. Gradient descent is not guaranteed to find the global optimum, making initialization critical.
  • Musical Complexity: The current musical application is limited to chromatic transpositions. Future iterations should incorporate "diatonic" transpositions (staying within a specific key) and handle different musical modes (major vs. minor).
  • Tree Balancing: The model currently lacks a mechanism to prefer "balanced" trees, which could be beneficial for certain data types.
  • Scalability: While the Gaussian approximation is efficient, extending RBNs to more complex, non-Gaussian continuous distributions remains a significant computational hurdle.

Summary updated

BibTeX
@inproceedings{lieck2021recursive,
  author = {Robert Lieck and Martin Rohrmeier},
  title = {{Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
}
Figure