Logical Hidden Markov Models

Kristian Kersting, Luc De Raedt, 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, widely applied in fields ranging from speech recognition to bioinformatics. However, traditional HMMs suffer from a "flatness" problem: they treat every observation as an unstructured, atomic symbol. In complex domains like UNIX command sequences or protein folding, this lack of structure is a significant limitation.

Consider modeling UNIX command sequences. A traditional HMM treats emacs paper.tex and emacs thesis.tex as two entirely distinct symbols. To capture their relationship, a modeler must either ignore the parameters (treating both as just emacs and losing vital context) or create a unique state for every possible command-file pair. The latter approach leads to a combinatorial explosion of states and parameters, making the model impossible to train effectively. Logical Hidden Markov Models (LOHMMs) address this by merging HMMs with concepts from Inductive Logic Programming (ILP) to handle structured data efficiently.

The LOHMM Framework

The core innovation of LOHMMs is the replacement of simple state labels with Logical Atoms. Instead of a state being an opaque identifier like "State A," it is a logical expression such as edit(User, File). This allows the model to represent complex relationships through variables and unification.

A LOHMM transition diagram where states are logical atoms, allowing for variable binding and structured sequences.

Key components of the framework include:

  • Abstract Transitions: Transitions are defined via logical rules. For instance, a rule can specify that if a user edits a file, they are likely to run a compiler on that same file in the next step.
  • Unification: This mechanism allows the model to bind variables across time steps. If the model observes emacs(X) followed by latex(X), unification ensures that X refers to the same entity, allowing the model to "remember" objects over time.
  • Selection Distributions: Because an abstract atom like edit(User, File) can represent many real-world groundings, LOHMMs use a selection mechanism (often a Naïve Bayes approach) to assign probabilities to specific variable assignments.

Inference and Learning

The authors successfully adapted the three classic HMM algorithms to the logical domain. The Forward algorithm (for evaluation), the Viterbi algorithm (for finding the most likely state sequence), and the Baum-Welch algorithm (for parameter estimation) were all upgraded to handle logical unification and abstract states.

The trellis structure of a LOHMM, illustrating the alternation between abstract transitions and the selection of specific groundings.

This architecture allows the model to maintain a compact representation while still being able to unfold into a complex state space during inference. By explicitly modeling the reuse of identifiers, the model captures the underlying logic of a sequence rather than just the statistics of flat strings.

Experimental Evaluation

LOHMMs were evaluated across three distinct domains to test their versatility and efficiency:

  1. UNIX Shell Logs: Using a dataset of ~300,000 commands, models utilizing unification (sharing variables between commands) significantly outperformed those that did not. This proved that modeling the structure of command parameters leads to better generalization on unseen data.
  2. Protein Fold Recognition: LOHMMs were used to classify sequences of secondary structure elements from the SCOP database. A LOHMM with only 295 parameters was able to cover a state space that would require over 65,000 parameters in a traditional HMM. The model achieved ~75% accuracy, maintaining performance even on datasets with low sequence similarity.
  3. mRNA Signal Structure: On mRNA secondary structure detection, LOHMMs reached 99% accuracy. This demonstrated their ability to capture tree-like dependencies, moving beyond the regular language limitations of traditional HMMs.

Conclusion

LOHMMs provide a powerful "first-order upgrade" to traditional HMMs, offering a massive increase in representational efficiency through abstraction. By using logical variables as a compression mechanism, they can model complex, structured sequences with a fraction of the parameters required by flat models.

Future work remains in the area of structure learning—automatically discovering the logical rules from data—and improving the variable selection process. While the grounding and unification process adds computational overhead, the gains in generalization and parameter efficiency make LOHMMs a compelling choice for structured sequential analysis.

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{kersting2006logical,
  author = {Kristian Kersting and Luc De Raedt and Tapani Raiko},
  title = {{Logical Hidden Markov Models}},
  journal = {J. Artif. Intell. Res.},
  year = {2006},
  url = {https://openreview.net/forum?id=-sdwzbM6xtn},
}
Figure