Collapsed Variational Bayesian Inference for PCFGs
Published 1 August 2013
Pengyu Wang, Phil Blunsom
Citations10
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A collapsed variational Bayesian inference algorithm for PCFGs that has the advantages of two dominant Bayesian training algorithms, namely variationalBayesian inference and Markov chain Monte Carlo is presented.
Abstract
This paper presents a collapsed variational Bayesian inference algorithm for PCFGs that has the advantages of two dominant Bayesian training algorithms for PCFGs, namely variational Bayesian inference and Markov chain Monte Carlo. In three kinds of experiments, we illustrate that our algorithm achieves close performance to the Hastings sampling algorithm while using an order of magnitude less training time; and outperforms the standard variational Bayesian inference and the EM algorithms with similar training time. 1
Keywords
Computer Science
Journal of the Royal Statistical Society Series B (Statistical Methodology)Maximum Likelihood from Incomplete Data Via the <i>EM</i> Algorithm
49,657 Citations1977A. P. Dempster, N. M. Laird +1 more
Building a Large Annotated Corpus of English: The Penn Treebank
7,528 Citations1993Mitchell P. Marcus
Accurate unlexicalized parsing
3,055 Citations2003Dan Klein, Christopher D. Manning
It is demonstrated that an unlexicalized PCFG can parse much more accurately than previously shown, by making use of simple, linguistically motivated state splits, which break down false independence assumptions latent in a vanilla treebank grammar.
A View of the Em Algorithm that Justifies Incremental, Sparse, and other Variants
2,187 Citations1998Radford M. Neal, Geoffrey E. Hinton
An incremental variant of the EM algorithm in which the distribution for only one of the unobserved variables is recalculated in each E step is shown empirically to give faster convergence in a mixture estimation problem.
Computational LinguisticsHead-Driven Statistical Models for Natural Language Parsing
1,860 Citations2003Michael Collins
Three statistical models for natural language parsing are described, leading to approaches in which a parse tree is represented as the sequence of decisions corresponding to a head-centered, top-down derivation of the tree.
Variational Algorithms for Approximate Bayesian Inference
1,731 Citations2003Matthew J. Beal
A variational Bayesian framework which approximates computations in models with latent variables using a lower bound on the marginal likelihood to pave the road for automated VB derivation procedures in both directed and undirected graphs.
Journal of Child LanguageThe child language data exchange system
872 Citations1985Brian MacWhinney, Catherine E. Snow
The formation of the CHILDES, the governance of the system, the nature of the database, the shape of the coding conventions, and the types of computer programs being developed are detailed.
Learning accurate, compact, and interpretable tree annotation
812 Citations2006Slav Petrov, Leon Barrett +2 more
An automatic approach to tree annotation in which basic nonterminal symbols are alternately split and merged to maximize the likelihood of a training treebank is presented.
Improved Inference for Unlexicalized Parsing
610 Citations2007Slav Petrov, Dan Klein
A novel coarse-to-fine method in which a grammar’s own hierarchical projections are used for incremental pruning, including a method for efficiently computing projections of a grammar without a treebank is presented.
The Journal of the Acoustical Society of AmericaTrainable grammars for speech recognition
538 Citations1979James K. Baker
This paper presents a generalization of these algorithms to certain denumerable‐state, hidden Markov processes that permits automatic training of the stochastic analog of an arbitrary context free grammar.
Statistical parsing with a context-free grammar and word statistics
535 Citations1997Eugene Charniak
A parsing system based upon a language model for English that is, in turn, based upon assigning probabilities to possible parses for a sentence that outperforms previous schemes is described.
A Collapsed Variational Bayesian Inference Algorithm for Latent Dirichlet Allocation
516 Citations2007Yee Whye Teh, David Newman +1 more
Corpus-based induction of syntactic structure
453 Citations2004Dan Klein, Christopher D. Manning
This work presents a generative model for the unsupervised learning of dependency structures and describes the multiplicative combination of this dependency model with a model of linear constituency that works and is robust cross-linguistically.
PCFG models of linguistic tree representations
367 Citations1998Mark Johnson
A simple node relabeling transformation is described that improves a treebank PCFG-based parser's average precision and recall by around 8%, or approximately half of the performance difference between a simple PCFG model and the best broad-coverage parsers available today.
Edinburgh Research Explorer (University of Edinburgh)Bayesian Inference for PCFGs via Markov Chain Monte Carlo
280 Citations2007Mark Johnson, Thomas L. Griffiths +1 more
The MIT Press eBooksAdaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models
274 Citations2007Mark Johnson, Thomas L. Griffiths +1 more
This paper presents a general-purpose inference algorithm for adaptor grammars, making it easy to define and use such models, and illustrates how several existing nonparametric Bayesian models can be expressed within this framework.
Probabilistic CFG with latent annotations
256 Citations2005Takuya Matsuzaki, Yusuke Miyao +1 more
This paper defines a generative probabilistic model of parse trees, which is an extension of PCFG in which non-terminal symbols are augmented with latent variables, and automatically induced fine-grained CFG rules are automatically induced from a parsed corpus by training a PCFG-LA model using an EM-algorithm.
Online EM for unsupervised models
210 Citations2009Percy Liang, Dan Klein
It is shown that online variants provide significant speedups and can even find better solutions than those found by batch EM on four unsupervised tasks: part-of-speech tagging, document classification, word segmentation, and word alignment.
The Infinite PCFG Using Hierarchical Dirichlet Processes
164 Citations2007Percy Liang, Slav Petrov +2 more
This work presents a nonparametric Bayesian model of tree structures based on the hierarchical Dirichlet process (HDP) and develops an efficient variational inference procedure that can be applied to full-scale parsing applications.
Parsing inside-out
134 Citations1998Stuart M. Shieber, Joshua Goodman
The Probabilistic Feature Grammar formalism is presented, which achieves state of the art accuracy, and can compute inside and outside probabilities of probabilistic Context-Free Grammars.
Improving unsupervised dependency parsing with richer contexts and smoothing
128 Citations2009William Headden, Mark Johnson +1 more
This paper introduces basic valence frames and lexical information into an unsupervised dependency grammar inducer and shows how this additional information can be leveraged via smoothing to produce state-of-the-art results.
Shared logistic normal distributions for soft parameter tying in unsupervised grammar induction
124 Citations2009Shay B. Cohen, Noah A. Smith
A family of priors over probabilistic grammar weights is presented, called the shared logistic normal distribution, enabling factored covariance between the probabilities of different derivation events in the probabilism grammar, providing a new way to encode prior knowledge about an unknown grammar.
Unsupervised Induction of Tree Substitution Grammars for Dependency Parsing
76 Citations2010Phil Blunsom, Trevor Cohn
This paper defines a hierarchical non-parametric Pitman-Yor Process prior which biases towards a small grammar with simple productions and significantly improves the state-of-the-art, when measured by head attachment accuracy.
Lecture notes in computer scienceVariational Bayesian Grammar Induction for Natural Language
57 Citations2006Kenichi Kurihara, Taisuke Sato
A new grammar induction algorithm for probabilistic context-free grammars (PCFGs) that applies the variational Bayes to PCFGs and achieves better parsing results than those of other PCFG induction algorithms.
IEEE Transactions on Pattern Analysis and Machine IntelligenceLatent-Space Variational Bayes
35 Citations2008Jaemo Sung, Zoubin Ghahramani +1 more
This paper introduces a more general approximate inference framework for conjugate-exponential family models, which it is shown that the LSVB approach gives better estimates of the model evidence as well as the distribution over latent variables than the VBEM approach, but in practice, the distributionover latent variables has to be approximated.
Truncation-free stochastic variational inference for Bayesian nonparametric models
34 Citations2012Chong Wang, David M. Blei
This work presents a truncation-free stochastic variational inference algorithm for Bayesian nonparametric models that adapts model complexity on the fly and performs better than previous stochastically variational inferred inference algorithms.
Practical collapsed variational bayes inference for hierarchical dirichlet process
26 Citations2012Issei Sato, Kenichi Kurihara +1 more
A novel collapsed variational Bayes (CVB) inference for the hierarchical Dirichlet process (HDP) is proposed, which is simple to implement, does not require variance counts to be maintained,does not need to set hyper-parameters, and has good predictive performance.
Three Dependency-and-Boundary Models for Grammar Induction
23 Citations2012Valentin I. Spitkovsky, Hiyan Alshawi +1 more
A new family of models for unsupervised parsing, Dependency and Boundary models, that use cues at constituent boundaries to inform head-outward dependency tree generation and induce state-of-the-art dependency grammars for many languages without special knowledge of optimal input sentence lengths or biased, manually-tuned initializers.
arXiv (Cornell University)Rethinking Collapsed Variational Bayes Inference for LDA
16 Citations2012Issei Sato, Hiroshi Nakagawa