gov.sandia.cognition.learning.algorithm.hmm

Class ParallelHiddenMarkovModel<ObservationType>

java.lang.Object

gov.sandia.cognition.util.AbstractCloneableSerializable

gov.sandia.cognition.learning.algorithm.hmm.MarkovChain

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

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, java.io.Serializable, java.lang.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

Nested Classes

Modifier and Type	Class and Description
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

Fields

Modifier and Type	Field and Description
protected java.util.ArrayList<ParallelHiddenMarkovModel.ComputeTransitionsTask>	computeTransitionTasks ComputeTransitionsTasks.
protected java.util.ArrayList<ParallelHiddenMarkovModel.NormalizeTransitionTask>	normalizeTransitionTasks NormalizeTransitionTasks.
protected java.util.ArrayList<ParallelHiddenMarkovModel.ObservationLikelihoodTask<ObservationType>>	observationLikelihoodTasks Observation likelihood tasks
protected java.util.ArrayList<ParallelHiddenMarkovModel.StateObservationLikelihoodTask>	stateObservationLikelihoodTasks StateObservationLikelihoodTasks
protected java.util.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

Constructors

Constructor and Description
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, java.util.Collection<? extends ComputableDistribution<ObservationType>> emissionFunctions) Creates a new instance of ParallelHiddenMarkovModel

Method Summary

Modifier and Type	Method and Description
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>	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 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 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.
java.util.concurrent.ThreadPoolExecutor	getThreadPool() Gets the thread pool for the algorithm to use.
protected void	normalizeTransitionMatrix(Matrix A) Normalizes the transition-probability matrix
void	setThreadPool(java.util.concurrent.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, sampleInto, 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 java.util.ArrayList<ParallelHiddenMarkovModel.ObservationLikelihoodTask<ObservationType>> observationLikelihoodTasks

Observation likelihood tasks

computeTransitionTasks

protected transient java.util.ArrayList<ParallelHiddenMarkovModel.ComputeTransitionsTask> computeTransitionTasks

ComputeTransitionsTasks.

normalizeTransitionTasks

protected transient java.util.ArrayList<ParallelHiddenMarkovModel.NormalizeTransitionTask> normalizeTransitionTasks

NormalizeTransitionTasks.

stateObservationLikelihoodTasks

protected transient java.util.ArrayList<ParallelHiddenMarkovModel.StateObservationLikelihoodTask> stateObservationLikelihoodTasks

StateObservationLikelihoodTasks

viterbiTasks

protected transient java.util.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,
                                 java.util.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 java.util.concurrent.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(java.util.concurrent.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(java.util.Collection<? extends java.util.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(java.util.ArrayList<WeightedValue<Vector>> alphas,
                                    java.util.ArrayList<WeightedValue<Vector>> betas,
                                    java.util.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 java.util.ArrayList<Vector> computeStateObservationLikelihood(java.util.ArrayList<WeightedValue<Vector>> alphas,
                                                                        java.util.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.