HiddenMarkovModel (Cognitive Foundry)

java.lang.Object
- gov.sandia.cognition.util.AbstractCloneableSerializable
- - gov.sandia.cognition.learning.algorithm.hmm.MarkovChain
  - - gov.sandia.cognition.learning.algorithm.hmm.HiddenMarkovModel<ObservationType>

Type Parameters:: ObservationType - Type of Observations handled by the HMM.

All Implemented Interfaces:: Distribution<ObservationType>, CloneableSerializable, java.io.Serializable, java.lang.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

Fields
Modifier and Type Field and Description

protected java.util.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

Fields
Modifier and Type	Field and Description
`protected java.util.Collection<? extends ComputableDistribution<ObservationType>>`	`emissionFunctions` The PDFs that emit symbols from each state.

Constructor Summary

Constructors
Constructor and Description
`HiddenMarkovModel()` Default constructor.
`HiddenMarkovModel(int numStates)` Creates a new instance of ContinuousDensityHiddenMarkovModel
`HiddenMarkovModel(Vector initialProbability, Matrix transitionProbability, java.util.Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)` Creates a new instance of ContinuousDensityHiddenMarkovModel

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`HiddenMarkovModel<ObservationType>`	`clone()` This makes public the clone method on the `Object` class and removes the exception that it throws.
`protected java.util.ArrayList<WeightedValue<Vector>>`	`computeBackwardProbabilities(java.util.ArrayList<Vector> b, java.util.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 java.util.ArrayList<WeightedValue<Vector>>`	`computeForwardProbabilities(java.util.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(java.util.Collection<? extends java.util.Collection<? extends ObservationType>> sequences)` Computes the log-likelihood of the observation sequences, given the current HMM's parameterization.
`protected java.util.ArrayList<Vector>`	`computeObservationLikelihoods(java.util.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(java.util.Collection<? extends ObservationType> observations)` Computes the log-likelihood of the observation sequence, given the current HMM's parameterization.
`double`	`computeObservationLogLikelihood(java.util.Collection<? extends ObservationType> observations, java.util.Collection<java.lang.Integer> states)` Computes the log-likelihood that the given observation sequence was generated by the given sequence of state indices.
`protected java.util.ArrayList<Vector>`	`computeStateObservationLikelihood(java.util.ArrayList<WeightedValue<Vector>> alphas, java.util.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(java.util.ArrayList<WeightedValue<Vector>> alphas, java.util.ArrayList<WeightedValue<Vector>> betas, java.util.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(java.util.Collection<? extends ProbabilityFunction<ObservationType>> distributions, java.util.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<java.util.Collection<? extends WeightedValue<? extends ObservationType>>,? extends ComputableDistribution<ObservationType>> learner, java.util.Collection<? extends ObservationType> data, java.util.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, java.util.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<java.lang.Integer>`	`findMostLikelyState(int destinationState, Vector delta)` Finds the most-likely next state given the previous "delta" in the Viterbi algorithm.
`java.util.Collection<? extends ComputableDistribution<ObservationType>>`	`getEmissionFunctions()` Getter for emissionFunctions
`ObservationType`	`sample(java.util.Random random)` Draws a single random sample from the distribution.
`java.util.ArrayList<ObservationType>`	`sample(java.util.Random random, int numSamples)` Draws multiple random samples from the distribution.
`void`	`sampleInto(java.util.Random random, int sampleCount, java.util.Collection<? super ObservationType> output)` Draws multiple random samples from the distribution and puts the result into the given collection.
`void`	`setEmissionFunctions(java.util.Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)` Setter for emissionFunctions.
`java.util.ArrayList<Vector>`	`stateBeliefs(java.util.Collection<? extends ObservationType> observations)` Computes the probability distribution over all states for each observation.
`java.lang.String`	`toString()`
`java.util.ArrayList<java.lang.Integer>`	`viterbi(java.util.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 java.util.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,
                         java.util.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<java.util.Collection<? extends WeightedValue<? extends ObservationType>>,? extends ComputableDistribution<ObservationType>> learner,
                                                                                java.util.Collection<? extends ObservationType> data,
                                                                                java.util.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,
                                                                                java.util.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(java.util.Collection<? extends ProbabilityFunction<ObservationType>> distributions,
                                                                                java.util.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(java.util.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(java.util.Collection<? extends java.util.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(java.util.Collection<? extends ObservationType> observations,
                                              java.util.Collection<java.lang.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(java.util.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 java.util.ArrayList<ObservationType> sample(java.util.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.
  - sampleInto
```
public void sampleInto(java.util.Random random,
                       int sampleCount,
                       java.util.Collection<? super ObservationType> output)
```
    Description copied from interface: Distribution
    
    Draws multiple random samples from the distribution and puts the result into the given collection.
    
    Specified by:
    
    sampleInto in interface Distribution<ObservationType>
    
    Parameters:
    
    random - Random number generator to use.
    
    sampleCount - The number of samples to draw. Cannot be negative.
    
    output - The collection to add the samples into.
  - getEmissionFunctions
```
public java.util.Collection<? extends ComputableDistribution<ObservationType>> getEmissionFunctions()
```
    Getter for emissionFunctions
    
    Returns:
    
    The PDFs that emit symbols from each state.
  - setEmissionFunctions
```
public void setEmissionFunctions(java.util.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 java.util.ArrayList<WeightedValue<Vector>> computeForwardProbabilities(java.util.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 java.util.ArrayList<Vector> computeObservationLikelihoods(java.util.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 java.util.ArrayList<WeightedValue<Vector>> computeBackwardProbabilities(java.util.ArrayList<Vector> b,
                                                                                  java.util.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 java.util.ArrayList<Vector> computeStateObservationLikelihood(java.util.ArrayList<WeightedValue<Vector>> alphas,
                                                                        java.util.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(java.util.ArrayList<WeightedValue<Vector>> alphas,
                                    java.util.ArrayList<WeightedValue<Vector>> betas,
                                    java.util.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 java.lang.String toString()
```
    Overrides:
    
    toString in class MarkovChain
  - findMostLikelyState
```
protected WeightedValue<java.lang.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 java.util.ArrayList<java.lang.Integer> viterbi(java.util.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 java.util.ArrayList<Vector> stateBeliefs(java.util.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.

Class HiddenMarkovModel<ObservationType>

Field Summary

Fields inherited from class gov.sandia.cognition.learning.algorithm.hmm.MarkovChain

Constructor Summary

Method Summary

Methods inherited from class gov.sandia.cognition.learning.algorithm.hmm.MarkovChain

Methods inherited from class java.lang.Object

Field Detail

emissionFunctions

Constructor Detail

HiddenMarkovModel

HiddenMarkovModel

HiddenMarkovModel

Method Detail

createRandom

createRandom

createRandom

clone

computeObservationLogLikelihood

computeMultipleObservationLogLikelihood

computeObservationLogLikelihood

sample

sample

sampleInto

getEmissionFunctions

setEmissionFunctions

computeForwardProbabilities

computeForwardProbabilities

computeObservationLikelihoods

computeObservationLikelihoods

computeObservationLikelihoods

computeBackwardProbabilities

computeBackwardProbabilities

computeStateObservationLikelihood

computeStateObservationLikelihood

computeTransitions

computeTransitions

toString

findMostLikelyState

computeViterbiRecursion

viterbi

stateBeliefs