Corpus-Based Induction of Syntactic Structure: Models of Dependency and Constituency

By Daniel Klein, Christopher D. Manning. 2004

585 citations recorded by the source corpus.

We present a generative model for the unsupervised learning of dependency structures. We also describe the multiplicative combination of this dependency model with a model of linear constituency. The product model outperforms both components on their respective evaluation metrics, giving the best published figures for unsupervised dependency parsing and unsupervised constituency parsing. We also demonstrate that the combined model works and is robust cross-linguistically, being able to exploit either attachment or distributional regularities that are salient in the data.

Subfields: Artificial Intelligence, Cultural Studies

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 Cultural Studies

Citations in the corpus

Alignment by Agreement (2006, background): “In general, if both posterior distributions over the latent variables z decompose in the same tractable manner, as in the context-free grammar induction work of Klein and Manning (2004), the summation could be carried out efﬁciently, for example using dynamic programming.”
Phrase Dependency Machine Translation with Quasi-Synchronous Tree-to-Tree Features (2014, background): “Several researchers have studied divergence between languages in corpora and found it to be considerable, even for closely related languages (Dorr 1994; Fox 2002; Wellington, Waxmonsky, and Melamed 2006; Søgaard and Kuhn 2009).”
Perturbed Masking: Parameter-free Probing for Analyzing and Interpreting BERT (2020, methodology): “Note that the DMV parser utilizes POS tags for training while ours start with the gold root.”
Bootstrapping language acquisition. (2017, background): “…as an explanation for how this could be done—see Elman et al. (1996) for examples—while others in both cognitive science and computer science have proposed methods using structured probabilistic models (Cohn, Blunsom, & Goldwater, 2010; Klein & Manning, 2004; Perfors, Tenenbaum, & Regier, 2011).”
Learning syntactic structure (2007, methodology): “These algorithms use either a constituency (bracketing) representation of syntactic structure (Klein and Manning 2002; Bod 2006a; Bod 2006b; Bod 2007a) or a dependency (link) representation of syntactic structure (Yuret 1998; Paskin 2002; Klein and Manning 2004; Smith and Eisner 2005; Smith and Eisn”
Probing the Linguistic Strengths and Limitations of Unsupervised Grammar Induction (2015, background): “Despite signiﬁcant progress in the last decade (Klein and Manning, 2004; Head-den III et al., 2009; Blunsom and Cohn, 2010; Spitkovsky et al., 2013; Mareˇcek and Straka, 2013), there has been little analysis performed on the types of errors these induction systems make, and our understanding of…”
Measuring Compositionality in Representation Learning (2019, background): “The most immediate is how to generalize TRE to the setting where oracle derivations are not available; in this case Equation 2 must be solved jointly with an unsupervised grammar induction problem (Klein & Manning, 2004).”
Probabilistic grammars and hierarchical Dirichlet processes (2018, background): “As these early experiments were discouraging, people turned to alternative algorithms (Stolcke and Omohundro, 1994) and models (Klein and Manning, 2004; Smith and Eisner, 2005).”
Compound Probabilistic Context-Free Grammars for Grammar Induction (2019, methodology): “(2009) and Cohen and Smith (2009), who also sample local rule probabilities from a logistic normal prior for training dependency models with valence (DMV) (Klein and Manning, 2004).”
Unsupervised Latent Tree Induction with Deep Inside-Outside Recursive Auto-Encoders (2019, background): “Others have shown that dependency parsing can be used for un-supervised constituency parsing (Spitkovsky et al., 2013; Klein and Manning, 2004), or that it’s effective to prune a random subset of possible trees (Bod, 2006).”
A Bayesian Model for Generative Transition-based Dependency Parsing (2015, methodology): “The first successful model was the dependency model with valence (DMV) (Klein and Manning, 2004).”
Are Pre-trained Language Models Aware of Phrases? Simple but Strong Baselines for Grammar Induction (2020, background): “Grammar induction is a task whose goal is to infer from sequential data grammars which generalize, and are able to account for unseen data (Lari & Young (1990); Clark (2001); Klein & Manning (2002; 2004), to name a few).”
From Baby Steps to Leapfrog: How “Less is More” in Unsupervised Dependency Parsing (2010, methodology): “The DMV (Klein and Manning, 2004) is a singlestate head automata model (Alshawi, 1996) over lexical word classes {cw} — POS tags.”
Universal Dependency Annotation for Multilingual Parsing (2013, background): “Second, consistent syntactic representations are desirable in the evaluation of unsupervised (Klein and Manning, 2004) or cross-lingual syntactic parsers (Hwa et al., 2005).”
Using Universal Linguistic Knowledge to Guide Grammar Induction (2010, methodology): “Table 4: Directed dependency accuracy using our model with universal dependency rules (No-Split and HDPDEP), compared to DMV (Klein and Manning, 2004) and PGI (Berg-Kirkpatrick and Klein, 2010).”