Difference between revisions of "Forward-Backward"
From Cohen Courses
Jump to navigationJump to search| Line 1: | Line 1: | ||
== Summary == | == Summary == | ||
| − | This is a dynamic programming [[Category::method | algorithm]], used in [[AddressesProblem::Hidden Markov Model | Hidden Markov Models]] to efficiently compute the | + | This is a dynamic programming [[Category::method | algorithm]], used in [[AddressesProblem::Hidden Markov Model | Hidden Markov Models]] to efficiently compute the state posteriors over all the hidden state variables. |
These values are then used in Posterior Decoding, which simply chooses the state with the highest posterior marginal for each position in the sequence. | These values are then used in Posterior Decoding, which simply chooses the state with the highest posterior marginal for each position in the sequence. | ||
| Line 9: | Line 9: | ||
== Posterior Decoding == | == Posterior Decoding == | ||
| − | Posterior decoding consists | + | Posterior decoding consists in picking the highest state posterior for each position in the sequence: |
| − | in picking the highest state posterior for each position in the sequence: | ||
<math> | <math> | ||
| − | + | \hat{y} = argmax_{y_1,\dots,y_N} \gamma_i(y_i) | |
| + | </math> | ||
| + | |||
| + | <math> | ||
| + | P_{\theta}(\bar{y},\bar{x}) = \frac{P_{\theta}()}{} | ||
<math> | <math> | ||
Revision as of 16:44, 28 September 2011
Summary
This is a dynamic programming algorithm, used in Hidden Markov Models to efficiently compute the state posteriors over all the hidden state variables.
These values are then used in Posterior Decoding, which simply chooses the state with the highest posterior marginal for each position in the sequence.
The forward-backward algorithm can be computed in linear time, where as, a brute force algorithm that checks all possible state sequences would be exponential over the length of the sequence.
Posterior Decoding
Posterior decoding consists in picking the highest state posterior for each position in the sequence:
<math> P_{\theta}(\bar{y},\bar{x}) = \frac{P_{\theta}()}{} <math>
