From Factorial and Hierarchical HMM to Bayesian Network: A Representation Change Algorithm

Sylvain Gelly, Nicolas Bredèche, Michèle SebagSARA 2005 · DOI

TL;DR

This paper introduces a novel algorithm to convert Factorial and Hierarchical Hidden Markov Models (FHHMMs) into Bayesian Networks (BNs). This transformation allows for more efficient inference in complex sequential models, particularly beneficial for mobile robotics where data is often scarce and noisy.

What Problem Does This Paper Address?

Autonomous mobile robots often rely on probabilistic models like Hidden Markov Models (HMMs) to build maps of their environment. While extensions like Factorial HMMs (allowing multiple causes for observations) and Hierarchical HMMs (enabling representation at different granularities) offer significant advantages, performing inference on these combined models is computationally challenging. Existing inference algorithms struggle with the complex dependencies and potential cycles introduced by these extensions. This paper addresses the gap by proposing a method to transform these complex FHHMMs into a more tractable Bayesian Network representation, enabling efficient inference.

Methods

The core contribution is a representation change algorithm that converts an FHHMM into a Flattened Bayesian Network (FBN). This process involves:

  • Handling Multiple Dependencies: Instead of directly modeling complex dependencies (e.g., P(Y|X1, X2, ..., Xn)), the algorithm breaks them down into pairwise dependencies (e.g., P(Y|X1), P(Y|X2), ...). This significantly reduces the number of parameters to learn.
  • Dealing with Directed Cycles: FHHMMs can contain directed cycles, which are not allowed in standard Bayesian Networks. The algorithm introduces additional boolean variables for each pairwise dependency. These variables act as intermediaries, effectively breaking cycles and ensuring a valid BN structure.
  • Axiomatic System for Coherence: To ensure the transformed BN accurately reflects the original dependencies, an axiomatic system is defined. This system, inspired by the Expectation-Maximization (EM) algorithm, iteratively refines the conditional probabilities of the new variables until a stable state (fixed point) is reached, satisfying "behavior" and "not adding information" axioms.
  • Strength Parameter for Convergence: A "strength" parameter is introduced to control the influence between variables, helping to manage convergence and avoid numerical issues, especially when influences tend to extreme values.

Datasets

Not discussed in the paper. The experiments use synthetic data generated by either a flattened Bayesian network or a classic Bayesian network.

Key Insights and Ideas

  • Bridging the Gap: The paper successfully bridges the gap between powerful but computationally difficult FHHMMs and the well-established, efficient inference capabilities of Bayesian Networks.
  • Pairwise Dependencies as a Solution: Decomposing complex dependencies into pairwise ones is a clever way to manage the exponential growth of parameters, making learning feasible even with limited data.
  • Auxiliary Variables for Cycle Resolution: The introduction of auxiliary variables to handle cycles is an elegant solution that maintains the expressiveness of the original model within the BN framework.
  • Learning Speed vs. Accuracy Trade-off: The research highlights that FBNs offer a significant advantage in learning speed, especially with scarce data, at the cost of potentially lower long-term accuracy compared to classic BNs when abundant data is available. This trade-off is particularly relevant for mobile robotics.
  • Structural Robustness: Flattened Bayesian networks appear to be less sensitive to the exact structure of the generator network, suggesting a more robust learning process in practice.

Key Results

The paper presents two main experimental findings:

  1. Learning from Flattened BN Data: When learning from data generated by a flattened Bayesian network, the flattened Bayesian networks consistently outperformed classic Bayesian networks in both average and best-case performance, especially with fewer examples.
  2. Learning with Few Examples: When learning from data generated by a classic Bayesian network (a more challenging scenario for FBNs), flattened Bayesian networks still showed superior performance with few examples. However, classic Bayesian networks caught up and surpassed FBNs as the number of training examples increased. This reinforces the idea that FBNs excel in low-data regimes.

Limitations and Future Work

  • Convergence Mechanism: The authors acknowledge that the convergence mechanism of their axiomatic system is based on experimental validation and may require further theoretical investigation.
  • Real-World Data: The current experiments use synthetic data. A crucial next step is to evaluate the learning behavior of FBNs using real-world data collected by robots in their environments.
  • Structure Learning: The paper focuses on representation change for a given structure. Future work should investigate learning mechanisms to find relevant structures for FBNs, especially since they seem less sensitive to ill-chosen structures than classic BNs.
  • Hybrid Representations: The authors suggest the possibility of creating hybrid representations combining flattened and classical Bayesian sub-networks, leveraging the strengths of both approaches depending on data availability.

Summary updated

BibTeX
@inproceedings{gelly2005from,
  author = {Sylvain Gelly and Nicolas Bredèche and Michèle Sebag},
  title = {{From Factorial and Hierarchical HMM to Bayesian Network: A Representation Change Algorithm}},
  booktitle = {SARA},
  year = {2005},
  doi = {10.1007/11527862\_8},
}
Figure