Logical Hidden Markov Models

Luc De Raedt, Kristian Kersting, Tapani Raiko

Abstract: Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters. This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics.

Introduction

Hidden Markov Models (HMMs) are fundamental tools for sequential data analysis, yet they struggle with structured data. Standard HMMs assume symbols are "flat" (e.g., A, B, C), which leads to a combinatorial explosion of parameters when dealing with complex inputs like UNIX commands or biological sequences. For instance, modeling mkdir(directory_name) as a flat symbol requires a unique parameter for every possible directory. Logical Hidden Markov Models (LOHMMs) bridge this gap by incorporating first-order logic, allowing the model to handle structured symbols and shared variables efficiently.

Methods: Logical Atoms and Unification

LOHMMs replace the flat states and observations of traditional HMMs with logical atoms (e.g., emacs(File, User)). This shift enables two powerful mechanisms:

  1. Abstraction: By using variables, a single abstract state can represent a vast number of concrete ("ground") states. This allows a single abstract transition to model thousands of specific transitions simultaneously.
  2. Unification (Variable Binding): Unification allows the model to maintain context across time steps. If a variable File is bound to a specific value in one step, the model can "remember" this binding in the next, effectively acting as a form of relational memory.
An example of a Logical Hidden Markov Model transition diagram, illustrating abstract states and transitions with associated probabilities.

To bridge the gap between abstract variables and concrete data, LOHMMs use a selection distribution (typically a Naive Bayes approach) to instantiate specific terms.

Inference and Algorithms

The authors successfully adapted the core HMM algorithms—Forward/Backward, Viterbi, and Baum-Welch—to the logical domain. These algorithms operate over a trellis of reachable states, where transitions are determined by logical subsumption and unification. This approach allows for efficient computation even in large or infinite state spaces by focusing only on states reachable through the given sequence of observations.

The trellis of reachable states (S0, S1, S2) in a LOHMM, illustrating how abstract transitions and selections evolve over discrete time steps.

Experimental Results

The LOHMM framework was evaluated on three distinct domains, demonstrating significant parameter compression and improved accuracy:

  • UNIX Command Sequences: A LOHMM designed to track directory names covered over 451,000 concrete states using only 542 parameters. It outperformed a baseline model that lacked variable sharing in 81.6% of test cases.
  • Protein Fold Recognition: The model achieved 76% accuracy using just 295 parameters. In contrast, a traditional HMM would require over 65,200 parameters to capture the same structural nuances.
  • mRNA Signal Structure: LOHMMs successfully parsed tree-structured RNA data with 99% accuracy, vastly outperforming relational learning baselines like RIBL (77.2%).

Conclusion and Future Work

LOHMMs represent a significant advancement in sequential modeling, offering a strictly more expressive framework than standard HMMs. By using unification as memory, they capture relational patterns that are invisible to propositional models. Future work aims to replace the Naive Bayes assumption in variable instantiation with more sophisticated dependency models, such as Bayesian Networks, to better handle complex real-world data dependencies.

Summary updated

Abstract

Logical hidden Markov models (LOHMMs) upgrade traditional hidden Markov models to deal with sequences of structured symbols in the form of logical atoms, rather than flat characters. This note formally introduces LOHMMs and presents solutions to the three central inference problems for LOHMMs: evaluation, most likely hidden state sequence and parameter estimation. The resulting representation and algorithms are experimentally evaluated on problems from the domain of bioinformatics.
BibTeX
@article{raedt2006logical,
  author = {Luc De Raedt and Kristian Kersting and Tapani Raiko},
  title = {{Logical Hidden Markov Models}},
  journal = {J. Artif. Intell. Res.},
  year = {2006},
  url = {https://openreview.net/forum?id=-sdwzbM6xtn},
}

Loading related content...

Figure