aima.core.probability.hmm.exact

Class FixedLagSmoothing

java.lang.Object

aima.core.probability.hmm.exact.FixedLagSmoothing

public class FixedLagSmoothing
extends java.lang.Object

Artificial Intelligence A Modern Approach (3rd Edition): page 580.

 function FIXED-LAG-SMOOTHING(et, hmm, d) returns a distribution over Xt-d
   inputs: et, the current evidence from time step t
           hmm, a hidden Markov model with S * S transition matrix T
           d, the length of the lag for smoothing
   persistent: t, the current time, initially 1
               f, the forward message P(Xt | e1:t), initially hmm.PRIOR
               B, the d-step backward transformation matrix, initially the identity matrix
               et-d:t, double-ended list of evidence from t-d to t, initially empty
   local variables: Ot-d, Ot, diagonal matrices containing the sensor model information
   
   add et to the end of et-d:t
   Ot <- diagonal matrix containing P(et | Xt)
   if t > d then
        f <- FORWARD(f, et)
        remove et-d-1 from the beginning of et-d:t
        Ot-d <- diagonal matrix containing P(et-d | Xt-d)
        B <- O-1t-dBTOt
   else B <- BTOt
   t <- t + 1
   if t > d then return NORMALIZE(f * B1) else return null
 

Figure 15.6 An algorithm for smoothing with a fixed time lag of d steps, implemented as an online algorithm that outputs the new smoothed estimate given the observation for a new time step. Notice that the final output NORMALIZE(f * B1) is just αf*b, by Equation (15.14).

Note: There appears to be two minor defects in the algorithm outlined in the book:
f <- FORWARD(f, e_t)
should be:
f <- FORWARD(f, e_t-d)
as we are returning a smoothed step for t-d and not the current time t.

The update of:
t <- t + 1
should occur after the return value is calculated. Otherwise when t == d the value returned is based on HMM.prior in the calculation as opposed to a correctly calculated forward message. Comments welcome.

Author:

Ciaran O'Reilly, Ravi Mohan

Constructor Summary

Constructors

Constructor and Description
FixedLagSmoothing(HiddenMarkovModel hmm, int d) Create a Fixed-Lag-Smoothing implementation, that sets up the required persistent values.

Method Summary

Modifier and Type	Method and Description
CategoricalDistribution	fixedLagSmoothing(java.util.List<AssignmentProposition> et) Algorithm for smoothing with a fixed time lag of d steps, implemented as an online algorithm that outputs the new smoothed estimate given the observation for a new time step.
Matrix	forward(Matrix f1_t, Matrix O_tp1) The forward equation (15.5) in Matrix form becomes (15.12):

Methods inherited from class java.lang.Object

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

Constructor Detail

FixedLagSmoothing

public FixedLagSmoothing(HiddenMarkovModel hmm,
                         int d)

Create a Fixed-Lag-Smoothing implementation, that sets up the required persistent values.

Parameters:

hmm - a hidden Markov model with S * S transition matrix T

d - d, the length of the lag for smoothing

Method Detail

fixedLagSmoothing

public CategoricalDistribution fixedLagSmoothing(java.util.List<AssignmentProposition> et)

Algorithm for smoothing with a fixed time lag of d steps, implemented as an online algorithm that outputs the new smoothed estimate given the observation for a new time step.

Parameters:

et - the current evidence from time step t

Returns:

a distribution over X_t-d

forward

public Matrix forward(Matrix f1_t,
                      Matrix O_tp1)

The forward equation (15.5) in Matrix form becomes (15.12):

 f1:t+1 = αOt+1TTf1:t
 

Parameters:

f1_t - f_1:t

O_tp1 - O_t+1

Returns:

f_1:t+1