Circumstellar habitable zone

The forward algorithm, in the context of a hidden Markov model, is used to calculate a 'belief state': the probability of a state at a certain time, given the history of evidence. The process is also known as filtering. The forward algorithm is closely related to, but distinct from, the Viterbi algorithm.

For an HMM such as this one:

Temporal evolution of a hidden Markov model

this probability is written as $P(x_{t}|y_{1:t})$. (abbreviating $x(t)$ as $x_{t}$.) A belief state can be calculated at each time step, but doing this does not, in a strict sense, produce the most likely state sequence, but rather the most likely state at each time step, given the previous history.

Algorithm

The goal of the forward algorithm is to compute the joint probability $p(x_{t},y_{1:t})$, where for notational convenience we have abbreviated $x(t)$ as $x_{t}$ and $(y(1),y(2),...,y(t))$ as $y_{1:t}$. Computing $p(x_{t},y_{1:t})$ directly would require marginalizing over all possible state sequences $\{x_{1:t-1}\}$, the number of which grows exponentially with $t$. Instead, the forward algorithm takes advantage of the conditional independence rules of the hidden Markov model (HMM) to perform the calculation recursively.

To demonstrate the recursion, let

$\alpha _{t}(x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})$.

Using the chain rule to expand $p(x_{t},x_{t-1},y_{1:t})$, we can then write

$\alpha _{t}(x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})$.

Because $y_{t}$ is conditionally independent of everything but $x_{t}$, and $x_{t}$ is conditionally independent of everything but $x_{t-1}$, this simplifies to

$\alpha _{t}(x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha _{t-1}(x_{t-1})$.

Thus, since $p(y_{t}|x_{t})$ and $p(x_{t}|x_{t-1})$ are given by the model's emission distributions and transition probabilities, one can quickly calculate $\alpha _{t}(x_{t})$ from $\alpha _{t-1}(x_{t-1})$ and avoid incurring exponential computation time.

The forward algorithm is easily modified to account for observations from variants of the hidden Markov model as well, such as the Markov jump linear system.

Smoothing

In order to take into account future history (i.e., if one wanted to improve the estimate for past times), you can run the Backward algorithm, a complement of the Forward. This is called smoothing. Mathematically, it would be said that the forward/backward algorithm computes $P(x_{k}|y_{1:t})$ for $1<k<t$. So the use of the full F/B algorithm takes into account all evidence.

Decoding

In order to achieve the most likely sequence, the Viterbi algorithm is required. It computes the most likely state sequence given the history of observations, that is, the state sequence that maximizes $P(x_{0:t}|y_{0:t})$.

The difference between the state sequence that the Viterbi algorithm estimate generates and the state sequence that the Forward algorithm generates is that the Viterbi algorithm recalculates the entire sequence with each new data point whereas the Forward Algorithm only appends the new current value to the previous sequence computed.

See also

• Viterbi algorithm
• Forward-backward algorithm

Further reading

• Russel and Norvig's Artificial Intelligence, a Modern Approach, starting on page 541 of the 2003 edition, provides a succinct exposition of this and related topics

Template:Algorithm-stub