Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper)

By Jason Eisner. 2016

89 citations recorded by the source corpus.

A probabilistic or weighted grammar implies a posterior probability distribution over possible parses of a given input sentence. One often needs to extract information from this distribution, by computing the expected counts (in the unknown parse) of various grammar rules, constituents, transitions, or states. This requires an algorithm such as inside-outside or forward-backward that is tailored to the grammar formalism. Conveniently, each such al-gorithm can be obtained by automatically differentiating an “inside” algorithm that merely computes the log-probability of the evidence (the sentence). This mechanical procedure produces correct and efﬁcient code. As for any other instance of back-propagation, it can be carried out manually or by software. This pedagogical paper carefully spells out the construction and relates it to traditional and non-traditional views of these algorithms.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Benchmarking Hierarchical Script Knowledge (2019, methodology): “The gradients are computed with automatic differentiation; as this is is equivalent to using the forward-backward algorithm to estimate the gradients (Eisner, 2016), only the forward al-gorithm has to be implemented.”
Compound Probabilistic Context-Free Grammars for Grammar Induction (2019, unknown): “∇θ log pθ(x) = Epθ(t |x)[∇θ log pθ(t)] (Salakhutdinov et al., 2003; Berg-Kirkpatrick et al., 2010; Eisner, 2016).”
Initial investigation of an encoder-decoder end-to-end TTS framework using marginalization of monotonic hard latent alignments (2019, methodology): “…the gradient can be computed with the following form: Then the back-propagation can be combined via back-ward operation of the forward-backward algorithms by introducing a backward variable β ( i, j ) and utilizing the relation ∂p ( y 1: J | x 1: I ; θ ) ∂α ( i, j ) = β ( i, j ) [12, 21].”
Neural Data-to-Text Generation via Jointly Learning the Segmentation and Correspondence (2020, methodology): “The process is essentially equivalent to the generalized EM algorithm (Eisner, 2016).”
Visually Grounded Compound PCFGs (2020, methodology): “It can be efﬁ-ciently computed with the inside algorithm and automatic differentiation (Eisner, 2016).”