Fixed-Lag-Smoothing.md

FIXED-LAG-SMOOTHING

AIMA3e

function FIXED-LAG-SMOOTHING(e_t, hmm, d) returns a distribution over X_t−d
 inputs: e_t, the current evidence for 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(X_t | e_1:t), initially hmm.PRIOR
      B, the d-step backward transformation matrix, initially the identity matrix
      e_t−d:t, double-ended list of evidence from t − d to t, initially empty
 local variables: O_t−d, O_t, diagonal matrices containing the sensor model information

 add e_t to the end of e_t−d:t
 O_t ← diagonal matrix containing P(e_t | X_t)
 if t > d then
   f ← FORWARD(f, e_t)
    remove e_t−d−1 from the beginning of e_t−d:t
   O_t−d ← diagonal matrix containing P(e_t−d | X_t−d)
   B ← O_t−d⁻¹T⁻¹ BTO_t
 else B ← BTO_t
 t ← t + 1
 if t > d then return NORMALIZE(f × B1) else return null

---

Figure ?? An algorithm for smoothing with a fixed time lag of d steps, implemented as an oline 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 (??).