gov.sandia.cognition.learning.algorithm.hmm
Class ParallelHiddenMarkovModel<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>
              extended by gov.sandia.cognition.learning.algorithm.hmm.ParallelHiddenMarkovModel<ObservationType>
Type Parameters:
ObservationType - Type of Observations handled by the HMM.
All Implemented Interfaces:
ParallelAlgorithm, Distribution<ObservationType>, CloneableSerializable, Serializable, Cloneable

@PublicationReference(author="William Turin",
                      title="Unidirectional and Parallel Baum\u2013Welch Algorithms",
                      type=Journal,
                      publication="IEEE Transactions on Speech and Audio Processing",
                      year=1998,
                      url="http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=00725318")
public class ParallelHiddenMarkovModel<ObservationType>
extends HiddenMarkovModel<ObservationType>
implements ParallelAlgorithm

A Hidden Markov Model with parallelized processing.

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

Nested Class Summary
protected static class ParallelHiddenMarkovModel.ComputeTransitionsTask
          Calls the computeTransitions method.
protected  class ParallelHiddenMarkovModel.LogLikelihoodTask
          Computes the log-likelihood of a particular data sequence
protected static class ParallelHiddenMarkovModel.NormalizeTransitionTask
          Calls the normalizeTransitionMatrix method.
protected static class ParallelHiddenMarkovModel.ObservationLikelihoodTask<ObservationType>
          Calls the computeObservationLikelihoods() method.
protected static class ParallelHiddenMarkovModel.StateObservationLikelihoodTask
          Calls the computeStateObservationLikelihood() method.
protected  class ParallelHiddenMarkovModel.ViterbiTask
          Computes the most-likely "from state" for the given "destination state" and the given deltas.
 
Field Summary
protected  ArrayList<ParallelHiddenMarkovModel.ComputeTransitionsTask> computeTransitionTasks
          ComputeTransitionsTasks.
protected  ArrayList<ParallelHiddenMarkovModel.NormalizeTransitionTask> normalizeTransitionTasks
          NormalizeTransitionTasks.
protected  ArrayList<ParallelHiddenMarkovModel.ObservationLikelihoodTask<ObservationType>> observationLikelihoodTasks
          Observation likelihood tasks
protected  ArrayList<ParallelHiddenMarkovModel.StateObservationLikelihoodTask> stateObservationLikelihoodTasks
          StateObservationLikelihoodTasks
protected  ArrayList<ParallelHiddenMarkovModel.ViterbiTask> viterbiTasks
          Viterbi tasks.
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.hmm.HiddenMarkovModel
emissionFunctions
 
Fields inherited from class gov.sandia.cognition.learning.algorithm.hmm.MarkovChain
DEFAULT_NUM_STATES, initialProbability, transitionProbability
 
Constructor Summary
ParallelHiddenMarkovModel()
          Creates a new instance of ParallelHiddenMarkovModel
ParallelHiddenMarkovModel(HiddenMarkovModel<ObservationType> other)
          \ Creates a new ParallelHiddenMarkovModel from another HiddenMarkovModel.
ParallelHiddenMarkovModel(int numStates)
          Creates a new instance of ParallelHiddenMarkovModel
ParallelHiddenMarkovModel(Vector initialProbability, Matrix transitionProbability, Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions)
          Creates a new instance of ParallelHiddenMarkovModel
 
Method Summary
 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> 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  Matrix computeTransitions(ArrayList<WeightedValue<Vector>> alphas, ArrayList<WeightedValue<Vector>> betas, ArrayList<Vector> b)
          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"
 int getNumThreads()
          Gets the number of threads in the thread pool.
 ThreadPoolExecutor getThreadPool()
          Gets the thread pool for the algorithm to use.
protected  void normalizeTransitionMatrix(Matrix A)
          Normalizes the transition-probability matrix
 void setThreadPool(ThreadPoolExecutor threadPool)
          Sets the thread pool for the algorithm to use.
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.hmm.HiddenMarkovModel
clone, computeBackwardProbabilities, computeBackwardProbabilities, computeForwardProbabilities, computeForwardProbabilities, computeObservationLikelihoods, computeObservationLikelihoods, computeObservationLikelihoods, computeObservationLogLikelihood, computeObservationLogLikelihood, computeStateObservationLikelihood, computeTransitions, createRandom, createRandom, createRandom, findMostLikelyState, getEmissionFunctions, sample, sample, setEmissionFunctions, stateBeliefs, toString, viterbi
 
Methods inherited from class gov.sandia.cognition.learning.algorithm.hmm.MarkovChain
createUniformInitialProbability, createUniformTransitionProbability, getFutureStateDistribution, getInitialProbability, getNumStates, getSteadyStateDistribution, getTransitionProbability, normalize, normalizeTransitionMatrix, setInitialProbability, setTransitionProbability
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface gov.sandia.cognition.util.CloneableSerializable
clone
 

Field Detail

observationLikelihoodTasks

protected transient ArrayList<ParallelHiddenMarkovModel.ObservationLikelihoodTask<ObservationType>> observationLikelihoodTasks
Observation likelihood tasks


computeTransitionTasks

protected transient ArrayList<ParallelHiddenMarkovModel.ComputeTransitionsTask> computeTransitionTasks
ComputeTransitionsTasks.


normalizeTransitionTasks

protected transient ArrayList<ParallelHiddenMarkovModel.NormalizeTransitionTask> normalizeTransitionTasks
NormalizeTransitionTasks.


stateObservationLikelihoodTasks

protected transient ArrayList<ParallelHiddenMarkovModel.StateObservationLikelihoodTask> stateObservationLikelihoodTasks
StateObservationLikelihoodTasks


viterbiTasks

protected transient ArrayList<ParallelHiddenMarkovModel.ViterbiTask> viterbiTasks
Viterbi tasks.

Constructor Detail

ParallelHiddenMarkovModel

public ParallelHiddenMarkovModel()
Creates a new instance of ParallelHiddenMarkovModel


ParallelHiddenMarkovModel

public ParallelHiddenMarkovModel(int numStates)
Creates a new instance of ParallelHiddenMarkovModel

Parameters:
numStates - Number of states in the HMM.

ParallelHiddenMarkovModel

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

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.

ParallelHiddenMarkovModel

public ParallelHiddenMarkovModel(HiddenMarkovModel<ObservationType> other)
\ Creates a new ParallelHiddenMarkovModel from another HiddenMarkovModel.

Parameters:
other - The other hidden Markov model to copy.
Method Detail

getThreadPool

public ThreadPoolExecutor getThreadPool()
Description copied from interface: ParallelAlgorithm
Gets the thread pool for the algorithm to use.

Specified by:
getThreadPool in interface ParallelAlgorithm
Returns:
Thread pool used for parallelization.

setThreadPool

public void setThreadPool(ThreadPoolExecutor threadPool)
Description copied from interface: ParallelAlgorithm
Sets the thread pool for the algorithm to use.

Specified by:
setThreadPool in interface ParallelAlgorithm
Parameters:
threadPool - Thread pool used for parallelization.

getNumThreads

public int getNumThreads()
Description copied from interface: ParallelAlgorithm
Gets the number of threads in the thread pool.

Specified by:
getNumThreads in interface ParallelAlgorithm
Returns:
Number of threads in the thread pool

computeMultipleObservationLogLikelihood

public double computeMultipleObservationLogLikelihood(Collection<? extends Collection<? extends ObservationType>> sequences)
Description copied from class: HiddenMarkovModel
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".

Overrides:
computeMultipleObservationLogLikelihood in class HiddenMarkovModel<ObservationType>
Parameters:
sequences - Observations sequences to consider
Returns:
Log-likelihood of the given observation sequence.

computeTransitions

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

Overrides:
computeTransitions in class HiddenMarkovModel<ObservationType>
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.

normalizeTransitionMatrix

protected void normalizeTransitionMatrix(Matrix A)
Description copied from class: MarkovChain
Normalizes the transition-probability matrix

Overrides:
normalizeTransitionMatrix in class MarkovChain
Parameters:
A - Transition probability matrix to normalize, modified by side effect

computeStateObservationLikelihood

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

Overrides:
computeStateObservationLikelihood in class HiddenMarkovModel<ObservationType>
Parameters:
alphas - Forward probabilities.
betas - Backward probabilities.
scaleFactor - Amount to scale the gamma by
Returns:
Gammas.

computeViterbiRecursion

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

Overrides:
computeViterbiRecursion in class HiddenMarkovModel<ObservationType>
Parameters:
delta - Previous value of the Viterbi recursion.
bn - Current observation likelihood.
Returns:
Updated "delta" and state backpointers.