Jump to content

Talk:Forward algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

I am sad

[edit]

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

Filtering

[edit]

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:

Temporal evolution of a hidden Markov model
Temporal evolution of a hidden Markov model

this probability is written as . (here I'm using subscripts to abbreviate as .) 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

[edit]

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 for all . So you use the full F/B algorithm to take into account all evidence.

Decoding

[edit]

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 .

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]

Contradiction

[edit]

Excuse my english level but I don't speak english very well.

So, in this article, I think there is a contradiction:

The forward algorithm[...] is used to calculate a 'belief state': the probability of a state at a certain time, given the history of evidence, [...] this probability is written as

or

The goal of the forward algorithm is to compute the joint probability

Which definition is the correct?

Thank you.

Faror91 (talk) 19:14, 17 April 2014 (UTC)[reply]

The algorithm as such is meant to calculate which is the belief state of the HMM. However, the proof in the wiki page calculates the joint probability. HMMs are generative models, and the conditional probability is calculated from the joint probability. You can see the difference is the language, where the first statement mentions about used to calculate and the second statement mentions compute. I don't think this requires a change in the wiki page. But the reader needs to keep in mind about the properties of HMMs.

LokeshRavindranathan 00:17, 6 July 2014 (UTC)[reply]

[edit]

Roger Boyle, A Tutorial on Hidden Markov Models. 24 April 2016.

This reference is dead. Does another reference to this tutorial exist somewhere? I did a quick google and have not found a replacement yet. — Preceding unsigned comment added by Bradybray (talkcontribs) 18:10, 4 October 2018 (UTC)[reply]

Should notation be changed?

[edit]

In ML literature, x is commonly referred to as the data and z as the hidden state, whereas in this article y is the observation and x is the hidden state.

Since I'm assuming the majority of readers are coming from an ML perspective, should the notation of this article be changed? 138.51.94.0 (talk) 22:51, 12 February 2023 (UTC)[reply]