Parsing Inside-Out

1998/05/19 by Joshua Goodman, Goodman, Joshua · 1 citation
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Machine Learning and Algorithms #Natural Language Processing Techniques #Topic Modeling #cmp-lg #cs.CL

paper · pdf · doi:10.48550/arxiv.cmp-lg/9805007

Ph.D. Thesis, 257 pages, 40 postscript figures

arxiv created 1998/05/19 · openalex publication_date 1998/05/19 · arxiv updated 2009/11/30 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28

Abstract

The inside-outside probabilities are typically used for reestimating Probabilistic Context Free Grammars (PCFGs), just as the forward-backward probabilities are typically used for reestimating HMMs. I show several novel uses, including improving parser accuracy by matching parsing algorithms to evaluation criteria; speeding up DOP parsing by 500 times; and 30 times faster PCFG thresholding at a given accuracy level. I also give an elegant, state-of-the-art grammar formalism, which can be used to compute inside-outside probabilities; and a parser description formalism, which makes it easy to derive inside-outside formulas and many others.

Cited by

• Branch-and-bound method for calculating Viterbi path in triplet Markov models

Related

• Robust stochastic parsing using the inside-outside algorithm
• An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities
• Inside-Outside Estimation Meets Dynamic EM
• Probabilistic Parsing Using Left Corner Language Models
• A probabilistic top-down parser for minimalist grammars