dev.nm.stat.hmm

Class ForwardBackwardProcedure

java.lang.Object

dev.nm.stat.hmm.ForwardBackwardProcedure

public class ForwardBackwardProcedure
extends Object

The forward-backward procedure is an inference algorithm for hidden Markov models which computes the posterior marginals of all hidden state variables given a sequence of observations. This inference task is usually called smoothing. The algorithm makes use of the principle of dynamic programming to efficiently compute the values that are required to obtain the posterior marginal distributions in two passes. The first pass goes forward in time while the second goes backward in time; hence the name forward-backward procedure.

The forward probability, α, is the probability of the partial observation sequence until time t and the system in state \(s_{i}\) and time t. \[ \alpha _{t}(i) = p(\omega _{1}, \omega _{2}, \ldots \omega _{t}, q_{t} = s_{i} | \lambda ) \] The backward probability, β, is the probability of the system in state \(s_{i}\) at time t, and the partial observations from then onward till time t. \[ \beta _{t}(i) = p(\omega _{t+1}, \omega _{t+2}, \ldots \omega _{T} | q_{t} = s_{i}, \lambda ) \] Our implementation computes a scaled version of the probabilities as discussed in Rabiner.

See Also:

• L. R. Rabiner, "A tutorial on hidden Markov models and selected applications in speech recognition," Proceedings of the IEEE, Volume: 77, Issue:2, 257 - 286, Feb 1989."
• W. Zucchini and I. L. MacDonald, "Hidden Markov Models for Time Series: An Introduction Using R," Boca Raton, Florida, CRC Press, 2009.
• Wikipedia: Forward-backward algorithm
• ref/hmm/hmm-scaling-implementation

Constructor Summary

Constructors

Constructor and Description
ForwardBackwardProcedure(HiddenMarkovModel model, double[] observations) Constructs the forward and backward probability matrix calculator for an HMM model.
ForwardBackwardProcedure(HiddenMarkovModel model, int[] observations) Constructs the forward and backward probability matrix calculator for an HMM model.

Method Summary

Modifier and Type	Method and Description
double	c(int t)
double	logLikelihood() Gets the likelihood of the given observations.
Vector	scaledAlpha(int t) Gets the scaled forward probabilities at time t.
Vector	scaledBeta(int t) Gets the scaled backward probabilities at time t.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ForwardBackwardProcedure

public ForwardBackwardProcedure(HiddenMarkovModel model,
                                double[] observations)

Constructs the forward and backward probability matrix calculator for an HMM model.

Parameters:

model - a (discrete) hidden Markov model

observations - an array of observations (length = T).

ForwardBackwardProcedure

public ForwardBackwardProcedure(HiddenMarkovModel model,
                                int[] observations)

Constructs the forward and backward probability matrix calculator for an HMM model.

Parameters:

model - a (discrete) hidden Markov model

observations - an array of observations (length = T).

Method Detail

scaledAlpha

public Vector scaledAlpha(int t)

Gets the scaled forward probabilities at time t.

Parameters:

t - a time

Returns:

the scaled forward probability in each state at time t

scaledBeta

public Vector scaledBeta(int t)

Gets the scaled backward probabilities at time t.

Parameters:

t - a time

Returns:

the scaled backward probability in each state at time t

logLikelihood

public double logLikelihood()

Gets the likelihood of the given observations.

Returns:

the likelihood of the given observations

c

public double c(int t)