(1.8 hours to learn)
The forward-backward algorithm is an algorithm for computing posterior marginals in a hidden Markov model (HMM). It is based on dynamic programming, and has linear complexity in the length of the sequence. It is used as a component of several other algorithms, such as the Baum_Welch algorithm and block Gibbs sampling in factorial HMMs.
This concept has the prerequisites:
- hidden Markov models (Forward-backward is an algorithm for inference in HMMs.)
- multivariate distributions (The forward-backward algorithm is an algorithm for marginalization.)
- conditional independence (The justification of the algorithm uses the conditional independence properties.)
Core resources (read/watch one of the following)
→ Mathematical Monk: Machine Learning (2011)
→ Artificial Intelligence: a Modern Approach
A textbook giving a broad overview of all of AI.
Location: Sections 15.2, up to "Finding the most likely sequence" (pages 541-547) and 15.3 (pages 549-551)
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location: Sections 17.4-17.4.3, pages 606-612
Supplemental resources (the following are optional, but you may find them useful)
→ Bayesian Reasoning and Machine Learning
A textbook for a graudate machine learning course.
Location: Sections 23.2-23.2.4, pages 458-462
→ Pattern Recognition and Machine Learning
A textbook for a graduate machine learning course, with a focus on Bayesian methods.
Location: Sections 13.2.2 (pages 618-625) and 13.2.4 (pages 627-629)
- The forward-backward algorithm can be interpreted as a special case of belief propagation .
- Kalman smoothing can be viewed as a special case of forward-backward, where the variables are all jointly Gaussian.
- This algorithm is part of the Baum-Welch algorithm for learning HMM parameters.
- The forward-backward algorithm is an example of dynamic programming .
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation