FindHiddenMarkovStates

FindHiddenMarkovStates[data,hmm]

finds the most likely hidden states of the HiddenMarkovProcess hmm corresponding to the emissions data.

FindHiddenMarkovStates[data,hmm,crit]

uses the given criterion crit to find the hidden states.

Details

  • FindHiddenMarkovStates is also known as hidden state decoding and Viterbi decoding.
  • The emissions data can be either a list or a TemporalData object.
  • FindHiddenMarkovStates returns the hidden state path in the same form as the emissions data. If there are multiple paths in data, there will be multiple state paths returned.
  • Possible values for criterion crit include:
  • "ViterbiDecoding"maximize likelihood for hidden state sequence (default)
    "PosteriorDecoding"maximize likelihood for hidden state at each time
  • Given an emission sequence , "ViterbiDecoding" maximizes the probability of a state sequence as a whole TemplateBox[{Probability, paclet:ref/Probability}, RefLink, BaseStyle -> {InlineFormula}][x(0)=i_0∧...∧x(n)=i_(n){y(0)=y_0,...,y(n)=y_(n)},...], whereas "PosteriorDecoding" maximizes the probability of a state value at each time TemplateBox[{Probability, paclet:ref/Probability}, RefLink, BaseStyle -> {InlineFormula}][x(t)=i{y(0)=y_0,...,y(n)=y_(n)},...].

Examples

open allclose all

Basic Examples  (1)

Suppose we observe the outputs from a fair (state 1) and unfair (state 2) coin:

Find the most likely sequence of coin changes from the observations:

Scope  (7)

With list input, FindHiddenMarkovStates outputs the hidden state sequence as a list:

For TemporalData input, the output is a time series object of the same type as the input:

FindHiddenMarkovStates maps over individual paths:

Each hidden state path is found individually:

Decode state sequence when some emissions are unknown:

Decode the hidden states for the given sequence of observations:

Use Viterbi decoding to find the most probable sequence:

Use posterior decoding to find the sequence of individually most-likely states:

Define a hidden Markov process with continuous emissions:

Simulate the process, including values of the hidden states:

Find the most likely state sequence for the given emissions:

Compare the decoded states to the actual states:

Find the most likely state sequence given multivariate emissions:

Simulate it:

Decode the most likely state sequence:

Compare the result against the actual state sequence:

Define joint loglikelihood of hidden states and emissions:

Viterbidecoded state sequence has equal or higher loglikelihood than the actual sequence:

Decode state sequence for a process with silent states:

Find the most likely state sequence:

Highlight emitting states in the sequence:

Applications  (3)

An occasionally dishonest casino offers a coin betting game and uses an unfair practice of using a biased coin for which the head is three times more likely than the tail. The casino dealer is known to secretly switch between the fair and biased coins with probability 10%:

The probabilities of getting heads or tails:

The resulting hidden Markov process, assuming equal probabilities of starting with either coin:

Given a sequence of tossings, guess on which occasions the dealer used the biased coin:

Visualize emissions and use color coding to show the hidden state sequence:

Define the process and decode hidden states underlying the given observations:

Group timeannotated emissions according to the decoded state value:

A toy robot travels on a 4×4 grid with walls represented by gray squares and cannot leave the map. The robot chooses randomly among four directions and attempts the move. If the move is disallowed it remains on the previous square:

Find tiles the robot can visit:

Compute allowed transitions:

Encode the robot's move in a graph and overlay it on the map:

Build the DiscreteMarkovProcess for the underlying hidden states:

The robot's optical sensor is rated 90% accurate, uniformly picking from used colors when faulting:

Model readings of the robot's optical sensor by hidden Markov process:

Given a sequence of sensor readings, use the model to find the robot's most likely movements on the map:

Visualize paths decoded using "ViterbiDecoding" and "PosteriorDecoding" criteria:

Properties & Relations  (3)

"ViterbiDecoding" maximizes the joint log-likelihood of the states and emissions:

Define the joint state and emission log-likelihood:

Compute all possible state paths:

Compute the joint log-likelihood for all the path combinations:

FindHiddenMarkovStates returns the state path with the maximum joint log-likelihood:

"PosteriorDecoding" finds the sequence of most likely states at each time individually:

Define distributions for hidden state values at times 0, 1, and 2:

Define distributions for emissions given the value of the hidden state:

Conditional emissions at times 0, 1, and 2 are independent of each other:

Define emissions at times 0, 1, and 2 as function of state values and conditional emission values:

Define the condition that emission random variables are equal to the observed values:

Find the sequence of the most probable states for each individual time instance:

Compare with the result of posterior decoding:

FindHiddenMarkovStates returns hard output, i.e. only one path:

In this case there are two equally probable paths:

A complete search shows that these are the only two:

Possible Issues  (2)

FindHiddenMarkovStates returns unevaluated if a path is inconsistent with the given HMM:

The likelihood of this emission sequence equals zero:

"PosteriorDecoding" may result in state sequences inconsistent with state topology:

The following sequence of emissions is consistent with the hidden Markov process:

Find hidden states using posterior decoding:

The state sequence found is inconsistent with the model for state transitions:

Introduced in 2014
 (10.0)