Probabilistic CFG with Latent Annotations

By Takuya Matsuzaki, Yusuke Miyao, Junichi Tsujii. Annual Meeting of the Association for Computational Linguistics, 2005

304 citations recorded by the source corpus.

This paper defines a generative probabilistic model of parse trees, which we call PCFG-LA. This model is an extension of PCFG in which non-terminal symbols are augmented with latent variables. Fine-grained CFG rules are automatically induced from a parsed corpus by training a PCFG-LA model using an EM-algorithm. Because exact parsing with a PCFG-LA is NP-hard, several approximations are described and empirically compared. In experiments using the Penn WSJ corpus, our automatically trained model gave a performance of 86.6% (F1, sentences ≤ 40 words), which is comparable to that of an unlexicalized PCFG parser created using extensive manual feature selection.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/713a4825ea09801ebc24ce207ca9ae5fbc97ac65

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

Citations in the corpus

Self-Training with Products of Latent Variable Grammars (2010, methodology): “They showed that the EM-algorithm that is typically used to ﬁt a latent variable grammar (Matsuzaki et al., 2005; Petrov et al., 2006) to a tree-bank can also be used for self-training on automatically parsed sentences.”
Improved Inference for Unlexicalized Parsing (2007, methodology): “For comparison, the Feb. 2006 release of the Charniak and Johnson (2005) parser runs in 1150 seconds on the same machine with an F 1 of 90.7%.”
Unsupervised Recurrent Neural Network Grammars (2019, unknown): “e the generative model p (x;z)) in order to sample parse forests for perplexity evaluation (i.e. importance sampling). This discriminative parser has the same ar13We use right branching binarization—Matsuzaki et al. (2005) ﬁnd that differences between various binarization schemes have marginal impac”
A Latent Variable Model for Generative Dependency Parsing (2007, background): “While the model of (Matsuzaki et al., 2005) significantly outperforms the constrained model of (Prescher, 2005), they both are well below the state-of-the-art in constituent parsing.”
Products of Random Latent Variable Grammars (2010, methodology): “We focus on the randomness introduced by the EM algorithm and refer the reader to Matsuzaki et al. (2005) and Petrov et al. (2006) for a more general introduction.”
Modeling Latent-Dynamic in Shallow Parsing: A Latent Conditional Model with Improved Inference (2008, background): “When the data has distinct sub-structures, models that exploit hidden state variables are advantageous in learning (Matsuzaki et al. 2005; Petrov et al. 2007).”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, methodology): “The ˆ T that maximizes this sum 4 can be selected by a Viterbi-style algorithm, once all the anchored probabilities have been computed (Good-man, 1996; Matsuzaki et al., 2005).”
Structured Generative Models of Natural Source Code (2014, background): “For example, Charniak (1997) and Klein and Manning (2003) consider annotating internal nodes, and Matsuzaki et al. (2005) has explored latent annotations.”
Compound Probabilistic Context-Free Grammars for Grammar Induction (2019, background): “Our work is also related to latent variable PCFGs (Matsuzaki et al., 2005; Petrov et al., 2006; Cohen et al., 2012), which extend PCFGs to the latent variable setting by splitting nonterminal symbols into latent subsymbols.”
Learning Accurate, Compact, and Interpretable Tree Annotation (2006, methodology): “Rather than experiment with head-outward binarization as in Klein and Manning (2003), we simply used a left branching binarization; Matsuzaki et al. (2005) contains a comparison showing that the differences between binariza-tions are small.”
Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing (2012, methodology): “On the other hand, current state-of-the-art parsers use symbol reﬁnement techniques (Johnson, 1998; Collins, 2003; Matsuzaki et al., 2005).”
Sparser, Better, Faster GPU Parsing (2014, background): “However, many authors have noted that parsers beneﬁt substantially from minimum Bayes risk decoding (Goodman, 1996; Simaan, 2003; Matsuzaki et al., 2005; Titov and Henderson, 2006; Petrov and Klein, 2007).”
A Multi-Teraflop Constituency Parser using GPUs (2013, background): “Instead, an unlexicalized approach like that of Johnson (2011) or Klein and Manning (2003), or a latent variable approach like that of Matsuzaki et al. (2005) or Petrov et al. (2006) are more appropriate.”
Dependency Parsing by Belief Propagation (2008, background): “We could also introduce new variables, e.g., nonterminal reﬁnements (Matsuzaki et al., 2005), or secondary links M ij (not constrained by T REE /PT REE ) that augment the parse with representations of control, binding, etc. (Sleator and Tem-perley, 1993; Buch-Kromann, 2006).”
Word Segmentation, Unknown-word Resolution, and Morphological Agreement in a Hebrew Parsing System (2013, methodology): “Their work triggered investigations in automatic grammar reﬁnement and state-splitting (Matsuzaki, Miyao, and Tsujii 2005; Prescher 2005), which was then perfected in work by Petrov and colleagues (Petrov et al. 2006; Petrov and Klein 2007; Petrov 2009).”
The Infinite PCFG Using Hierarchical Dirichlet Processes (2007, methodology): “Unlexicalized methods reﬁne the grammar in a more conservative fashion, splitting each non-terminal or pre-terminal symbol into a much smaller number of subsymbols (Klein and Manning, 2003; Matsuzaki et al., 2005; Petrov et al., 2006).”
A Provably Correct Learning Algorithm for Latent-Variable PCFGs (2014, methodology): “The trees are bina-rized (Petrov et al., 2006) and for the EM algo-rithm we use the initialization method described in Matsuzaki et al. (2005).”
Approximate PCFG Parsing Using Tensor Decomposition (2013, methodology): “See Matsuzaki et al. (2005) for more details about the binarization scheme we used.”
Constituent Parsing with Incremental Sigmoid Belief Networks (2007, background): “There has not been much previous work on graphical models for full parsing, although recently several latent variable models for parsing have been proposed (Koo and Collins, 2005; Matsuzaki et al., 2005; Riezler et al., 2002).”