package aima.core.probability.hmm.exact;
import java.util.ArrayList;
import java.util.List;
import aima.core.probability.CategoricalDistribution;
import aima.core.probability.hmm.HiddenMarkovModel;
import aima.core.probability.proposition.AssignmentProposition;
import aima.core.util.math.Matrix;
/**
* Artificial Intelligence A Modern Approach (3rd Edition): page 579.
*
*
* Smoothing for any time slice k requires the simultaneous presence of
* both the forward and backward messages, f1:k and
* bk+1:t, according to Equation (15.8). The forward-backward
* algorithm achieves this by storing the fs computed on the forward pass
* so that they are available during the backward pass. Another way to achieve
* this is with a single pass that propagates both f and b in the
* same direction. For example, the "forward" message f can be propagated
* backward if we manipulate Equation (15.12) to work in the other direction:
*
*
* f1:t = α'(TT)-1O-1t+1f1:t+1 ** * The modified smoothing algorithm works by first running the standard forward * pass to compute ft:t (forgetting all intermediate results) * and then running the backward pass for both b and f together, * using them to compute the smoothed estimate at each step. Since only one copy * of each message is needed, the storage requirements are constant (i.e. * independent of t, the length of the sequence). There are two significant * restrictions on the algorithm: it requires that the transition matrix be * invertible and that the sensor model have no zeroes - that is, that every * observation be possible in every state. * * @author Ciaran O'Reilly */ public class HMMForwardBackwardConstantSpace extends HMMForwardBackward { public HMMForwardBackwardConstantSpace(HiddenMarkovModel hmm) { super(hmm); } // // START-ForwardBackwardInference @Override public List
* f1:t = α'(TT)-1O-1t+1f1:t+1 ** * @param O_tp1 * Ot+1 * @param f1_tp1 * f1:t+1 * @return f1:t */ public Matrix forwardRecover(Matrix O_tp1, Matrix f1_tp1) { return hmm.normalize(hmm.getTransitionModel().transpose().inverse() .times(O_tp1.inverse()).times(f1_tp1)); } }