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

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 efficient 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.

• Publication year

  2016

• Venue

  SPNLP@EMNLP

• Publication date

  2016-11-01

• Fields of study

  Computer Science

• Identifiers
  DOI 10.18653/v1/W16-5901
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Speed-Accuracy Tradeoffs in Tagging with Variable-Order CRFs and Structured Sparsity

  2016cited by this paper
• Approximation-Aware Dependency Parsing by Belief Propagation

  2015cited by this paper
• Graphical Models with Structured Factors, Neural Factors, and Approximation-aware Training

  2015cited by this paper
• Theano: A CPU and GPU Math Compiler in Python

  2010cited by this paper
• An Introduction to Conditional Random Fields

  2010influential reference
• Painless Unsupervised Learning with Features

  2010cited by this paper
• First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests

  2009cited by this paper
• New Advances in Logic-Based Probabilistic Modeling by PRISM

  2008cited by this paper
• Efficient, Feature-based, Conditional Random Field Parsing

  2008cited by this paper
• Program transformations for optimization of parsing algorithms and other weighted logic programs

  2007cited by this paper
• Structured Prediction Models via the Matrix-Tree Theorem

  2007cited by this paper
• Probabilistic Models of Nonprojective Dependency Trees

  2007cited by this paper
• Solving the Problem of Cascading Errors: Approximate Bayesian Inference for Linguistic Annotation Pipelines

  2006influential reference
• Compiling Comp Ling: Weighted Dynamic Programming and the Dyna Language

  2005cited by this paper
• Probabilistic CFG with Latent Annotations

  2005influential reference
• Semi-Markov Conditional Random Fields for Information Extraction

  2004cited by this paper
• Case-factor diagrams for structured probabilistic modeling

  2004cited by this paper
• Stochastic Analysis of Structured Language Modeling

  2004cited by this paper
• Probabilistic Parsing as Intersection

  2003cited by this paper
• The estimation of stochastic context-free grammars using the Inside-Outside algorithm

  2003cited by this paper
• Optimization with EM and Expectation-Conjugate-Gradient

  2003cited by this paper
• Parameter Estimation for Probabilistic Finite-State Transducers

  2002cited by this paper
• Automatic Differentiation of Algorithms: From Simulation to Optimization

  2002cited by this paper
• Parsing and Hypergraphs

  2001cited by this paper
• The generalized distributive law

  2000cited by this paper
• Minimization algorithms for sequential transducers

  2000cited by this paper
• Exact alpha-beta computation in logarithmic space with application to MAP word graph construction

  2000cited by this paper
• Automatic differentiation of algorithms

  2000cited by this paper
• A differential approach to inference in Bayesian networks

  2000influential reference
• Estimators for Stochastic “Unification-Based” Grammars

  1999cited by this paper
• Statistical Properties of Probabilistic Context-Free Grammars

  1999influential reference
• Relating Probabilistic Grammars and Automata

  1999influential reference
• Semiring Parsing

  1999cited by this paper
• Parsing Inside-Out

  1998influential reference
• Three New Probabilistic Models for Dependency Parsing: An Exploration

  1996cited by this paper
• Efficient Algorithms for Parsing the DOP Model

  1996cited by this paper
• A Statistical Learning Method for Logic Programs with Distribution Semantics

  1995cited by this paper
• An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities

  1994cited by this paper
• Parsing Some Constrained Grammar Formalisms

  1993cited by this paper
• Inside-Outside Reestimation From Partially Bracketed Corpora

  1992cited by this paper
• Stochastic Lexicalized Tree-adjoining Grammars

  1992cited by this paper
• A Linear Algorithm For Generating Random Numbers With a Given Distribution

  1991cited by this paper
• Applications of stochastic context-free grammars using the Inside-Outside algorithm

  1990cited by this paper
• The Structure of Shared Forests in Ambiguous Parsing

  1989cited by this paper
• A Learning Algorithm for Continually Running Fully Recurrent Neural Networks

  1989cited by this paper
• Characterizing Structural Descriptions Produced by Various Grammatical Formalisms

  1987cited by this paper
• Learning internal representations by error propagation

  1986cited by this paper
• Une procedure d'apprentissage pour reseau a seuil asymmetrique (A learning scheme for asymmetric threshold networks)

  1985cited by this paper
• Trainable grammars for speech recognition

  1979cited by this paper
• Maximum likelihood from incomplete data via the EM - algorithm plus discussions on the paper

  1977cited by this paper
• Determination of Probabilistic Grammars for Functionally Specified Probability-Measure Languages

  1974cited by this paper
• Beyond Regression : "New Tools for Prediction and Analysis in the Behavioral Sciences

  1974cited by this paper
• An inequality and associated maximization technique in statistical estimation of probabilistic functions of a Markov process

  1972cited by this paper
• An efficient context-free parsing algorithm

  1970cited by this paper
• An efficient context-free parsing algorithm

  1970cited by this paper
• Recognition and Parsing of Context-Free Languages in Time n^3

  1967cited by this paper
• An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages

  1965influential reference
• Synchronous Tree Adjoining Grammars Then, If the Pair Operates on the Np 1 -np 0 in 1 , the following Pair 2 Is Generated. 2 *

  year unknowncited by this paper

• What does it take to learn the rules of RNA base pairing? A lot less than you may think

  2025cites this paper
• Efficient design of rna sequences with desired properties, structure, and motifs using a grammar variational autoencoder

  2025cites this paper
• EnsembleDesign: messenger RNA design minimizing ensemble free energy via probabilistic lattice parsing

  2025cites this paper
• On Eliciting Syntax from Language Models via Hashing

  2024cites this paper
• Improving Unsupervised Constituency Parsing via Maximizing Semantic Information

  2024influential citation
• To be Continuous, or to be Discrete, Those are Bits of Questions

  2024cites this paper
• Encoding and Decoding Graph Representations of Natural Language

  2024cites this paper
• Character-Level Chinese Dependency Parsing via Modeling Latent Intra-Word Structure

  2024cites this paper
• A Neural Syntax Parser for Coronary Artery Anatomical Labeling in Coronary CT Angiography

  2024cites this paper
• Last: Scalable Lattice-Based Speech Modelling in Jax

  2023cites this paper
• Approximating CKY with Transformers

  2023cites this paper
• Messenger RNA Design via Expected Partition Function and Continuous Optimization

  2023cites this paper
• Simple Hardware-Efficient PCFGs with Independent Left and Right Productions

  2023cites this paper
• Attention sur les spans pour l’analyse syntaxique en constituants

  2023cites this paper
• SynJax: Structured Probability Distributions for JAX

  2023cites this paper
• Interpreting Sentiment Composition with Latent Semantic Tree

  2023cites this paper
• Structured Mean-Field Variational Inference for Higher-Order Span-Based Semantic Role

  2023cites this paper
• Revisiting the Entropy Semiring for Neural Speech Recognition

  2023cites this paper
• Efficient Semiring-Weighted Earley Parsing

  2023cites this paper
• Unsupervised Vision-Language Parsing: Seamlessly Bridging Visual Scene Graphs with Language Structures via Dependency Relationships

  2022cites this paper
• Unsupervised Discontinuous Constituency Parsing with Mildly Context-Sensitive Grammars

  2022cites this paper
• Learning Dependencies of Discrete Speech Representations with Neural Hidden Markov Models

  2022cites this paper
• Higher-Order Dependency Parsing for Arc-Polynomial Score Functions via Gradient-Based Methods and Genetic Algorithm

  2022cites this paper
• Hidden 1-Counter Markov Models and How to Learn Them

  2022cites this paper
• Unbiased and Efficient Sampling of Dependency Trees

  2022cites this paper
• Unsupervised Dependency Graph Network

  2022cites this paper
• A Structured Span Selector

  2022cites this paper
• Dynamic Programming in Rank Space: Scaling Structured Inference with Low-Rank HMMs and PCFGs

  2022cites this paper
• Nested Named Entity Recognition as Latent Lexicalized Constituency Parsing

  2022cites this paper
• Beyond Chomsky Normal Form: Extending Strong Learning Algorithms for PCFGs

  2021cites this paper
• VLGrammar: Grounded Grammar Induction of Vision and Language

  2021cites this paper
• PCFGs Can Do Better: Inducing Probabilistic Context-Free Grammars with Many Symbols

  2021cites this paper
• Neural Bi-Lexicalized PCFG Induction

  2021cites this paper
• Learning compositional structures for semantic graph parsing

  2021cites this paper
• DeepStochLog: Neural Stochastic Logic Programming

  2021cites this paper
• Transformer-Based Direct Hidden Markov Model for Machine Translation

  2021cites this paper
• Structured Refinement for Sequential Labeling

  2021cites this paper
• Strength in Numbers: Averaging and Clustering Effects in Mixture of Experts for Graph-Based Dependency Parsing

  2021cites this paper
• Semantic Role Labeling as Dependency Parsing: Exploring Latent Tree Structures inside Arguments

  2021cites this paper
• Recursive Bayesian Networks: Generalising and Unifying Probabilistic Context-Free Grammars and Dynamic Bayesian Networks

  2021cites this paper
• Scaling Structured Inference with Randomization

  2021cites this paper
• Strong Learning of some Probabilistic Multiple Context-Free Grammars

  2021cites this paper
• Nested Named Entity Recognition with Partially-Observed TreeCRFs

  2020cites this paper
• Efficient Second-Order TreeCRF for Neural Dependency Parsing

  2020cites this paper
• Consistent unsupervised estimators for anchored PCFGs

  2020cites this paper
• Torch-Struct: Deep Structured Prediction Library

  2020cites this paper
• Efficient Outside Computation

  2020cites this paper
• Unsupervised Parsing with S-DIORA: Single Tree Encoding for Deep Inside-Outside Recursive Autoencoders

  2020cites this paper
• Visually Grounded Compound PCFGs

  2020cites this paper
• Efficient Computation of Expectations under Spanning Tree Distributions

  2020cites this paper
• Second-Order Unsupervised Neural Dependency Parsing

  2020cites this paper
• Fast and Accurate Neural CRF Constituency Parsing

  2020cites this paper
• Neural Data-to-Text Generation via Jointly Learning the Segmentation and Correspondence

  2020cites this paper
• Learning to Segment Actions from Observation and Narration

  2020cites this paper
• Compound Probabilistic Context-Free Grammars for Grammar Induction

  2019cites this paper
• Tensor Variable Elimination for Plated Factor Graphs

  2019cites this paper
• Learning with Fenchel-Young Losses

  2019cites this paper
• Supervised Training on Synthetic Languages: A Novel Framework for Unsupervised Parsing

  2019cites this paper
• Differentiable Algorithm for Marginalising Changepoints

  2019cites this paper
• Initial investigation of an encoder-decoder end-to-end TTS framework using marginalization of monotonic hard latent alignments

  2019cites this paper
• A Neural Graph-based Approach to Verbal MWE Identification

  2019cites this paper
• Benchmarking Hierarchical Script Knowledge

  2019cites this paper
• A Tutorial on Deep Latent Variable Models of Natural Language

  2018cites this paper
• Backpropagating through Structured Argmax using a SPIGOT

  2018cites this paper
• Neural Syntactic Generative Models with Exact Marginalization

  2018cites this paper
• Bridging CNNs, RNNs, and Weighted Finite-State Machines

  2018cites this paper
• Monte Carlo Syntax Marginals for Exploring and Using Dependency Parses

  2018cites this paper
• Handling Ties Correctly and Efficiently in Viterbi Training Using the Viterbi Semiring

  2018influential citation
• Differentiable Dynamic Programming for Structured Prediction and Attention

  2018cites this paper
• Relational Attention Networks via Fully-Connected Conditional Random Fields

  2018cites this paper
• Learning representations from functional MRI data

  2018cites this paper
• Coarse Lexical Frame Acquisition at the Syntax–Semantics Interface Using a Latent-Variable PCFG Model

  2018cites this paper
• Bridging HMMs and RNNs through Architectural Transformations

  2018cites this paper
• Embedded-State Latent Conditional Random Fields for Sequence Labeling

  2018cites this paper
• Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder

  2018cites this paper
• Deep Latent Variable Models of Natural Language

  2018cites this paper
• Forward-Backward with Failure Arcs: Faster Inference for Variable-Order Conditional Random Fields

  2018cites this paper
• Structured Set Matching Networks for One-Shot Part Labeling

  2017cites this paper
• Modeling Exclusion with a Differentiable Factor Graph Constraint

  2017cites this paper
• Learning to Prune: Exploring the Frontier of Fast and Accurate Parsing

  2017cites this paper
• Incremental generative models for syntactic and semantic natural language processing

  2017cites this paper
• Structured Attention Networks

  2017cites this paper
• An Algebraic Formalization of Forward and Forward-backward Algorithms

  2017influential citation
• Speed-Accuracy Tradeoffs in Tagging with Variable-Order CRFs and Structured Sparsity

  2016cites this paper
• UvA-DARE (Digital Academic Repository) Differentiable Perturb-and-Parse: Semi-Supervised Parsing with a Structured Variational Autoencoder

  year unknowncites this paper