gov.sandia.cognition.learning.algorithm.hmm
Class HiddenMarkovModel<ObservationType>

java.lang.Object
  extended by gov.sandia.cognition.util.AbstractCloneableSerializable
      extended by gov.sandia.cognition.learning.algorithm.hmm.MarkovChain
          extended by gov.sandia.cognition.learning.algorithm.hmm.HiddenMarkovModel<ObservationType>
Type Parameters:
ObservationType - Type of Observations handled by the HMM.
All Implemented Interfaces:
Distribution<ObservationType>, CloneableSerializable, Serializable, Cloneable
Direct Known Subclasses:
ParallelHiddenMarkovModel

@PublicationReference(author="Lawrence R. Rabiner",
                      title="A tutorial on hidden Markov models and selected applications in speech recognition",
                      type=Journal,
                      year=1989,
                      publication="Proceedings of the IEEE",
                      pages={257,286},
                      url="http://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf",
                      notes="Rabiner\'s transition matrix is transposed from mine.")
public class HiddenMarkovModel<ObservationType>
extends MarkovChain
implements Distribution<ObservationType>

A discrete-state Hidden Markov Model (HMM) with either continuous or discrete observations.

Since:
3.0
Author:
Kevin R. Dixon
See Also:
Serialized Form

Field Summary
protected  Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions
          The PDFs that emit symbols from each state.
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.hmm.MarkovChain
DEFAULT_NUM_STATES, initialProbability, transitionProbability
 
Constructor Summary
HiddenMarkovModel()
          Default constructor.
HiddenMarkovModel(int numStates)
          Creates a new instance of ContinuousDensityHiddenMarkovModel
HiddenMarkovModel(Vector initialProbability, Matrix transitionProbability, Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)
          Creates a new instance of ContinuousDensityHiddenMarkovModel
 
Method Summary
 HiddenMarkovModel<ObservationType> clone()
          This makes public the clone method on the Object class and removes the exception that it throws.
protected  ArrayList<WeightedValue<Vector>> computeBackwardProbabilities(ArrayList<Vector> b, ArrayList<WeightedValue<Vector>> alphas)
          Computes the backward-probabilities for the given observation likelihoods and the weights from the alphas.
protected  WeightedValue<Vector> computeBackwardProbabilities(Vector beta, Vector b, double weight)
          Computes the backward probability recursion.
protected  ArrayList<WeightedValue<Vector>> computeForwardProbabilities(ArrayList<Vector> b, boolean normalize)
          Computes the forward probabilities for the given observation likelihood sequence.
protected  WeightedValue<Vector> computeForwardProbabilities(Vector alpha, Vector b, boolean normalize)
          Computes the recursive solution to the forward probabilities of the HMM.
protected  double computeMultipleObservationLogLikelihood(Collection<? extends Collection<? extends ObservationType>> sequences)
          Computes the log-likelihood of the observation sequences, given the current HMM's parameterization.
protected  ArrayList<Vector> computeObservationLikelihoods(Collection<? extends ObservationType> observations)
          Computes the conditionally independent likelihoods for each state given the observation sequence.
 Vector computeObservationLikelihoods(ObservationType observation)
          Computes the conditionally independent likelihoods for each state given the observation.
protected  void computeObservationLikelihoods(ObservationType observation, Vector b)
          Computes the conditionally independent likelihoods for each state given the observation.
 double computeObservationLogLikelihood(Collection<? extends ObservationType> observations)
          Computes the log-likelihood of the observation sequence, given the current HMM's parameterization.
 double computeObservationLogLikelihood(Collection<? extends ObservationType> observations, Collection<Integer> states)
          Computes the log-likelihood that the given observation sequence was generated by the given sequence of state indices.
protected  ArrayList<Vector> computeStateObservationLikelihood(ArrayList<WeightedValue<Vector>> alphas, ArrayList<WeightedValue<Vector>> betas, double scaleFactor)
          Computes the probabilities of the various states over time given the observation sequence.
protected static Vector computeStateObservationLikelihood(Vector alpha, Vector beta, double scaleFactor)
          Computes the probability of the various states at a time instance given the observation sequence.
protected  Matrix computeTransitions(ArrayList<WeightedValue<Vector>> alphas, ArrayList<WeightedValue<Vector>> betas, ArrayList<Vector> b)
          Computes the stochastic transition-probability matrix from the given probabilities.
protected static Matrix computeTransitions(Vector alphan, Vector betanp1, Vector bnp1)
          Computes the stochastic transition-probability matrix from the given probabilities.
protected  Pair<Vector,int[]> computeViterbiRecursion(Vector delta, Vector bn)
          Computes the Viterbi recursion for a given "delta" and "b"
static
<ObservationType>
HiddenMarkovModel<ObservationType>
createRandom(Collection<? extends ProbabilityFunction<ObservationType>> distributions, Random random)
          Creates a Hidden Markov Model with the given probability function for each state, but sampling the columns of the transition matrix and the initial probability distributions from a diffuse Dirichlet.
static
<ObservationType>
HiddenMarkovModel<ObservationType>
createRandom(int numStates, BatchLearner<Collection<? extends WeightedValue<? extends ObservationType>>,? extends ComputableDistribution<ObservationType>> learner, Collection<? extends ObservationType> data, Random random)
          Creates a Hidden Markov Model with the same PMF/PDF for each state, but sampling the columns of the transition matrix and the initial probability distributions from a diffuse Dirichlet.
static
<ObservationType>
HiddenMarkovModel<ObservationType>
createRandom(int numStates, ComputableDistribution<ObservationType> distribution, Random random)
          Creates a Hidden Markov Model with the same PMF/PDF for each state, but sampling the columns of the transition matrix and the initial probability distributions from a diffuse Dirichlet.
protected  WeightedValue<Integer> findMostLikelyState(int destinationState, Vector delta)
          Finds the most-likely next state given the previous "delta" in the Viterbi algorithm.
 Collection<? extends ComputableDistribution<ObservationType>> getEmissionFunctions()
          Getter for emissionFunctions
 ObservationType sample(Random random)
          Draws a single random sample from the distribution.
 ArrayList<ObservationType> sample(Random random, int numSamples)
          Draws multiple random samples from the distribution.
 void setEmissionFunctions(Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)
          Setter for emissionFunctions.
 ArrayList<Vector> stateBeliefs(Collection<? extends ObservationType> observations)
          Computes the probability distribution over all states for each observation.
 String toString()
           
 ArrayList<Integer> viterbi(Collection<? extends ObservationType> observations)
          Viterbi algorithm for decoding the most-likely sequence of states from the HMMs underlying Markov chain for a given observation sequence.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.hmm.MarkovChain
createUniformInitialProbability, createUniformTransitionProbability, getFutureStateDistribution, getInitialProbability, getNumStates, getSteadyStateDistribution, getTransitionProbability, normalize, normalizeTransitionMatrix, normalizeTransitionMatrix, setInitialProbability, setTransitionProbability
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

emissionFunctions

protected Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions
The PDFs that emit symbols from each state.

Constructor Detail

HiddenMarkovModel

public HiddenMarkovModel()
Default constructor.


HiddenMarkovModel

public HiddenMarkovModel(int numStates)
Creates a new instance of ContinuousDensityHiddenMarkovModel

Parameters:
numStates - Number of states in the HMM.

HiddenMarkovModel

public HiddenMarkovModel(Vector initialProbability,
                         Matrix transitionProbability,
                         Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)
Creates a new instance of ContinuousDensityHiddenMarkovModel

Parameters:
initialProbability - Initial probability Vector over the states. Each entry must be nonnegative and the Vector must sum to 1.
transitionProbability - Transition probability matrix. The entry (i,j) is the probability of transition from state "j" to state "i". As a corollary, all entries in the Matrix must be nonnegative and the columns of the Matrix must sum to 1.
emissionFunctions - The PDFs that emit symbols from each state.
Method Detail

createRandom

public static <ObservationType> HiddenMarkovModel<ObservationType> createRandom(int numStates,
                                                                                BatchLearner<Collection<? extends WeightedValue<? extends ObservationType>>,? extends ComputableDistribution<ObservationType>> learner,
                                                                                Collection<? extends ObservationType> data,
                                                                                Random random)
Creates a Hidden Markov Model with the same PMF/PDF for each state, but sampling the columns of the transition matrix and the initial probability distributions from a diffuse Dirichlet.

Type Parameters:
ObservationType - Type of observations to generate.
Parameters:
numStates - Number of states to create
learner - Learner to create the distributions for each state
data - Data from which to make the distribution
random - Random number generator
Returns:
HMM with the specified states.

createRandom

public static <ObservationType> HiddenMarkovModel<ObservationType> createRandom(int numStates,
                                                                                ComputableDistribution<ObservationType> distribution,
                                                                                Random random)
Creates a Hidden Markov Model with the same PMF/PDF for each state, but sampling the columns of the transition matrix and the initial probability distributions from a diffuse Dirichlet.

Type Parameters:
ObservationType - Type of observations to generate.
Parameters:
numStates - Number of states to create
distribution - Distribution from which we will assign to each state.
random - Random number generator
Returns:
HMM with the specified states.

createRandom

public static <ObservationType> HiddenMarkovModel<ObservationType> createRandom(Collection<? extends ProbabilityFunction<ObservationType>> distributions,
                                                                                Random random)
Creates a Hidden Markov Model with the given probability function for each state, but sampling the columns of the transition matrix and the initial probability distributions from a diffuse Dirichlet.

Type Parameters:
ObservationType - Type of observations to generate.
Parameters:
distributions - The distribution for each state. The size of the collection is the number of states to create.
random - Random number generator
Returns:
HMM with the specified states.

clone

public HiddenMarkovModel<ObservationType> clone()
Description copied from class: AbstractCloneableSerializable
This makes public the clone method on the Object class and removes the exception that it throws. Its default behavior is to automatically create a clone of the exact type of object that the clone is called on and to copy all primitives but to keep all references, which means it is a shallow copy. Extensions of this class may want to override this method (but call super.clone() to implement a "smart copy". That is, to target the most common use case for creating a copy of the object. Because of the default behavior being a shallow copy, extending classes only need to handle fields that need to have a deeper copy (or those that need to be reset). Some of the methods in ObjectUtil may be helpful in implementing a custom clone method. Note: The contract of this method is that you must use super.clone() as the basis for your implementation.

Specified by:
clone in interface CloneableSerializable
Overrides:
clone in class MarkovChain
Returns:
A clone of this object.

computeObservationLogLikelihood

public double computeObservationLogLikelihood(Collection<? extends ObservationType> observations)
Computes the log-likelihood of the observation sequence, given the current HMM's parameterization. This is the answer to Rabiner's "Three Basic Problems for HMMs, Problem 1: Probability Evaluation".

Parameters:
observations - Observations to consider.
Returns:
Log-likelihood of the given observation sequence.

computeMultipleObservationLogLikelihood

protected double computeMultipleObservationLogLikelihood(Collection<? extends Collection<? extends ObservationType>> sequences)
Computes the log-likelihood of the observation sequences, given the current HMM's parameterization. This is the answer to Rabiner's "Three Basic Problems for HMMs, Problem 1: Probability Evaluation".

Parameters:
sequences - Observations sequences to consider
Returns:
Log-likelihood of the given observation sequence.

computeObservationLogLikelihood

public double computeObservationLogLikelihood(Collection<? extends ObservationType> observations,
                                              Collection<Integer> states)
Computes the log-likelihood that the given observation sequence was generated by the given sequence of state indices.

Parameters:
observations - Observations to consider.
states - Indices of states hypothesized to have generated the observation sequence.
Returns:
Log-likelihood of the given observation sequence.

sample

public ObservationType sample(Random random)
Description copied from interface: Distribution
Draws a single random sample from the distribution.

Specified by:
sample in interface Distribution<ObservationType>
Parameters:
random - Random-number generator to use in order to generate random numbers.
Returns:
Sample drawn according to this distribution.

sample

public ArrayList<ObservationType> sample(Random random,
                                         int numSamples)
Description copied from interface: Distribution
Draws multiple random samples from the distribution. It is generally more efficient to use this multiple-sample method than multiple calls of the single-sample method. (But not always.)

Specified by:
sample in interface Distribution<ObservationType>
Parameters:
random - Random-number generator to use in order to generate random numbers.
numSamples - Number of samples to draw from the distribution.
Returns:
Samples drawn according to this distribution.

getEmissionFunctions

public Collection<? extends ComputableDistribution<ObservationType>> getEmissionFunctions()
Getter for emissionFunctions

Returns:
The PDFs that emit symbols from each state.

setEmissionFunctions

public void setEmissionFunctions(Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)
Setter for emissionFunctions.

Parameters:
emissionFunctions - The PDFs that emit symbols from each state.

computeForwardProbabilities

protected WeightedValue<Vector> computeForwardProbabilities(Vector alpha,
                                                            Vector b,
                                                            boolean normalize)
Computes the recursive solution to the forward probabilities of the HMM.

Parameters:
alpha - Previous alpha value.
b - Current observation-emission likelihood.
normalize - True to normalize the alphas, false to leave them unnormalized.
Returns:
Alpha with the associated weighting (will be 1 if unnormalized).

computeForwardProbabilities

protected ArrayList<WeightedValue<Vector>> computeForwardProbabilities(ArrayList<Vector> b,
                                                                       boolean normalize)
Computes the forward probabilities for the given observation likelihood sequence.

Parameters:
b - Observation likelihood sequence.
normalize - True to normalize the alphas, false to leave them unnormalized.
Returns:
Forward probability alphas, with their associated weights.

computeObservationLikelihoods

public Vector computeObservationLikelihoods(ObservationType observation)
Computes the conditionally independent likelihoods for each state given the observation.

Parameters:
observation - Observation to consider
Returns:
Likelihood of each state generating the given observation.

computeObservationLikelihoods

protected void computeObservationLikelihoods(ObservationType observation,
                                             Vector b)
Computes the conditionally independent likelihoods for each state given the observation.

Parameters:
observation - Observation to consider
b - Likelihood of each state generating the given observation. This is where the result of the computation is stored.

computeObservationLikelihoods

protected ArrayList<Vector> computeObservationLikelihoods(Collection<? extends ObservationType> observations)
Computes the conditionally independent likelihoods for each state given the observation sequence.

Parameters:
observations - Observation sequence to consider
Returns:
Likelihood of each state generating the given observation sequence.

computeBackwardProbabilities

protected WeightedValue<Vector> computeBackwardProbabilities(Vector beta,
                                                             Vector b,
                                                             double weight)
Computes the backward probability recursion.

Parameters:
beta - Beta from the "next" time step.
b - Observation likelihood from the "next" time step.
weight - Weight to use for the current time step.
Returns:
Beta for the previous time step, weighted by "weight".

computeBackwardProbabilities

protected ArrayList<WeightedValue<Vector>> computeBackwardProbabilities(ArrayList<Vector> b,
                                                                        ArrayList<WeightedValue<Vector>> alphas)
Computes the backward-probabilities for the given observation likelihoods and the weights from the alphas.

Parameters:
b - Observation likelihoods.
alphas - Forward probabilities from which we will use the weights.
Returns:
Backward probabilities.

computeStateObservationLikelihood

protected static Vector computeStateObservationLikelihood(Vector alpha,
                                                          Vector beta,
                                                          double scaleFactor)
Computes the probability of the various states at a time instance given the observation sequence. Rabiner calls this the "gamma".

Parameters:
alpha - Forward probability at time n.
beta - Backward probability at time n.
scaleFactor - Amount to scale the gamma by
Returns:
Gamma at time n.

computeStateObservationLikelihood

protected ArrayList<Vector> computeStateObservationLikelihood(ArrayList<WeightedValue<Vector>> alphas,
                                                              ArrayList<WeightedValue<Vector>> betas,
                                                              double scaleFactor)
Computes the probabilities of the various states over time given the observation sequence. Rabiner calls these the "gammas".

Parameters:
alphas - Forward probabilities.
betas - Backward probabilities.
scaleFactor - Amount to scale the gamma by
Returns:
Gammas.

computeTransitions

protected static Matrix computeTransitions(Vector alphan,
                                           Vector betanp1,
                                           Vector bnp1)
Computes the stochastic transition-probability matrix from the given probabilities.

Parameters:
alphan - Result of the forward pass through the HMM at time n
betanp1 - Result of the backward pass through the HMM at time n+1
bnp1 - Conditionally independent likelihoods of each observation at time n+1
Returns:
Transition probabilities at time n

computeTransitions

protected Matrix computeTransitions(ArrayList<WeightedValue<Vector>> alphas,
                                    ArrayList<WeightedValue<Vector>> betas,
                                    ArrayList<Vector> b)
Computes the stochastic transition-probability matrix from the given probabilities.

Parameters:
alphas - Result of the forward pass through the HMM.
betas - Result of the backward pass through the HMM.
b - Conditionally independent likelihoods of each observation.
Returns:
ML estimate of the transition probability Matrix over all time steps.

toString

public String toString()
Overrides:
toString in class MarkovChain

findMostLikelyState

protected WeightedValue<Integer> findMostLikelyState(int destinationState,
                                                     Vector delta)
Finds the most-likely next state given the previous "delta" in the Viterbi algorithm.

Parameters:
destinationState - Destination state index to consider.
delta - Previous value of the "delta".
Returns:
Most-likely previous state, weighted by its likelihood.

computeViterbiRecursion

protected Pair<Vector,int[]> computeViterbiRecursion(Vector delta,
                                                     Vector bn)
Computes the Viterbi recursion for a given "delta" and "b"

Parameters:
delta - Previous value of the Viterbi recursion.
bn - Current observation likelihood.
Returns:
Updated "delta" and state backpointers.

viterbi

@PublicationReference(author="Wikipedia",
                      title="Viterbi algorithm",
                      year=2010,
                      type=WebPage,
                      url="http://en.wikipedia.org/wiki/Viterbi_algorithm")
public ArrayList<Integer> viterbi(Collection<? extends ObservationType> observations)
Viterbi algorithm for decoding the most-likely sequence of states from the HMMs underlying Markov chain for a given observation sequence.

Parameters:
observations - Observation sequence to consider
Returns:
Indices of the most-likely state sequence that generated the given observations.

stateBeliefs

public ArrayList<Vector> stateBeliefs(Collection<? extends ObservationType> observations)
Computes the probability distribution over all states for each observation.

Parameters:
observations -
Returns:
The list of state belief probabilities for each observation.