forward-backward algorithm
E880218
The forward-backward algorithm is a dynamic programming method for computing posterior state probabilities in hidden Markov models, widely used in tasks like sequence labeling and speech recognition.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
algorithm
ⓘ
probabilistic graphical model algorithm ⓘ |
| appliesTo |
continuous-output hidden Markov models
ⓘ
discrete hidden Markov models ⓘ discrete-time sequences ⓘ |
| assumes |
conditional independence of observations given states
ⓘ
first-order Markov chain over hidden states ⓘ |
| backwardVariableName | beta ⓘ |
| basedOn |
Bayes rule
NERFINISHED
ⓘ
Markov property ⓘ |
| canBeImplementedWith |
log-space computations
ⓘ
scaling factors ⓘ |
| computes |
marginal state probabilities
ⓘ
posterior state probabilities ⓘ smoothed state probabilities ⓘ |
| field |
computational linguistics
ⓘ
machine learning ⓘ statistical signal processing ⓘ |
| forwardVariableName | alpha ⓘ |
| goal | avoid numerical underflow in probability products ⓘ |
| hasComponent |
backward pass
ⓘ
forward pass ⓘ |
| introducedInContextOf | hidden Markov models ⓘ |
| isSpecialCaseOf |
belief propagation
ⓘ
sum-product algorithm ⓘ |
| operatesOn |
hidden state sequence
ⓘ
observation sequence ⓘ |
| produces |
gamma probabilities
ⓘ
xi probabilities ⓘ |
| relatedTo |
Baum-Welch algorithm
NERFINISHED
ⓘ
Viterbi algorithm NERFINISHED ⓘ |
| spaceComplexity | O(T·N) ⓘ |
| timeComplexity | O(T·N²) ⓘ |
| timeComplexityInWords | linear in sequence length and quadratic in number of states ⓘ |
| usedFor |
biosequence analysis
ⓘ
expectation step in Baum-Welch ⓘ handwriting recognition ⓘ named entity recognition ⓘ part-of-speech tagging ⓘ posterior decoding ⓘ sequence labeling ⓘ smoothing in time series ⓘ speech recognition ⓘ |
| usedIn | hidden Markov model NERFINISHED ⓘ |
| uses |
emission probabilities
ⓘ
initial state distribution ⓘ transition probabilities ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.