Equations defining hidden markov models

Nicolas Bray, Jason Morton

Research output: Chapter in Book/Report/Conference proceedingChapter

2 Scopus citations


In this chapter, we investigate the ideal of polynomial invariants satisfied by the probabilities of observations in a hidden Markov model. Two main techniques for computing this ideal are employed. First, we describe elimination using Gröbner bases. This technique is only feasible for small models and yields invariants that may not be easy to interpret. Second, we present a technique using linear algebra refined by two gradings of the ideal of relations. Finally, we classify some of the invariants found in this way. The hidden Markov model The hidden Markov model was described in Section 1.4.3 (see also Figure 1.5) as the algebraic statistical model defined by composing the fully observed Markov model F with the marginalization ρ, giving a map, where Θ1 is the subset of Θ defined by requiring row sums equal to one. Here we will write the hidden Markov model as a composition of three maps, ρ ∘ F ∘ g, beginning in a coordinate space Θ″ ⊂ ℂd which parameterizes the d = l(l − 1) + l(l′ − 1)-dimensional linear subspace Θ1 lying in the l 2 + ll′-dimensional space Θ, so that Θ1 = g(Θ″). These maps are shown in the following diagrams: In the bottom row of the diagram, we have phrased the hidden Markov model in terms of rings by considering the ring homomorphism g*, F* and ρ*.

Original languageEnglish (US)
Title of host publicationAlgebraic Statistics for Computational Biology
PublisherCambridge University Press
Number of pages13
ISBN (Electronic)9780511610684
ISBN (Print)0521857007, 9780521857000
StatePublished - Jan 1 2005

All Science Journal Classification (ASJC) codes

  • General Mathematics


Dive into the research topics of 'Equations defining hidden markov models'. Together they form a unique fingerprint.

Cite this