Talk:Forward algorithm

Why does this page forward to Viterbi?? The Forward algorithm and Viterbi are different algorithms with different purposes.

Filtering

The Forward algorithm (in the context of a Hidden Markov Model) is used to calculate a belief state, which is the probability of a state at a certain time, given the history of evidence. This process is also known as filtering. For an HMM such as this one:

this probability is written as $P(x_{t}|y_{1:t})$ . (here I'm using subscripts to abbreviate $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.

Smoothing

In order to take into account future history (say if you want to improve your estimate for past times), you then run the Backward algorithm, a complement of the Forward. This is called smoothing. Mathematically, we would say that the Forward/Backward algorithm computes $P(x_{k}|y_{1:t})$ for all $0<k<t$ . So you use the full F/B algorithm to take into account all evidence.

Decoding

What if we want the most likely sequence? Enter Viterbi. This algorithm 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})$ .

While it may be conceptually difficult to understand the difference between the state sequence that Viterbi estimates versus the evolving estimate that you get from the Forward algorithm, the bottom line is that they are different.

If you want to learn more about this I recommend Russel and Norvig's Artificial Intelligence, a Modern Approach. No, it's not free online anywhere, but it's worth owning a copy if you are a computer science/autonomy student, or have a research interest in artificial intelligence. They explain this stuff succinctly and completely starting on page 541 of the 2003 edition. Avidelego (talk) 18:45, 14 April 2010 (UTC)[reply]