Parsing low-resource languages using Gibbs sampling for PCFGs with latent annotations
Published 1 January 2014Open access
Liang Sun, Jason D. Mielens, Jason Baldridge
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
It is shown that a Gibbs sampling technique is capable of parsing sentences in a wide variety of languages and producing results that are on-par with or surpass previous approaches.
Abstract
PCFGs with latent annotations have been shown to be a very effective model for phrase structure parsing. We present a Bayesian model and algorithms based on a Gibbs sam-pler for parsing with a grammar with latent an-notations. For PCFG-LA, we present an ad-ditional Gibbs sampler algorithm to learn an-notations from training data, which are parse trees with coarse (unannotated) symbols. We show that a Gibbs sampling technique is ca-pable of parsing sentences in a wide variety of languages and producing results that are on-par with or surpass previous approaches. Our results for Kinyarwanda and Malagasy in particular demonstrate that low-resource lan-guage parsing can benefit substantially from a Bayesian approach. 1
Keywords
Computer Science
IEEE Transactions on Pattern Analysis and Machine IntelligenceStochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
17,980 Citations1984Stuart Geman, Donald Geman
The analogy between images and statistical mechanics systems is made and the analogous operation under the posterior distribution yields the maximum a posteriori (MAP) estimate of the image given the degraded observations, creating a highly parallel ``relaxation'' algorithm for MAP estimation.
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.
IEEE Transactions on Information TheoryThree models for the description of language
2,749 Citations1956Noam Chomsky
It is found that no finite-state Markov process that produces symbols with transition from state to state can serve as an English grammar and the particular subclass of such processes that produce n -order statistical approximations to English do not come closer to matching the output of an English grammar.
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.
A maximum-entropy-inspired parser
1,496 Citations2000Eugene Charniak
A new parser for parsing down to Penn tree-bank style parse trees that achieves 90.1% average precision/recall for sentences of length 40 and less and 89.5% when trained and tested on the previously established sections of the Wall Street Journal treebank is presented.
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.
Three generative, lexicalised models for statistical parsing
749 Citations1997Michael Collins
A new statistical parsing model is proposed, which is a generative model of lexicalised context-free grammar and extended to include a probabilistic treatment of both subcategorisation and wh-movement.
Natural Language EngineeringThe Penn Chinese TreeBank: Phrase structure annotation of a large corpus
694 Citations2005Nianwen Xue, Fei Xia +2 more
Several Chinese linguistic issues and their implications for treebanking efforts are discussed and how to address these issues when developing annotation guidelines are addressed, and engineering strategies to improve speed while ensuring annotation quality are described.
Computer Speech & LanguageApplications of stochastic context-free grammars using the Inside-Outside algorithm
666 Citations1991Kimia Bazargan Lari, S. Young
Two applications in speech recognition of the use of stochastic context-free grammars trained automatically via the Inside-Outside Algorithm, used to model VQ encoded speech for isolated word recognition and compared directly to HMMs used for the same task are described.
A new statistical parser based on bigram lexical dependencies
619 Citations1996Michael Collins
A new statistical parser which is based on probabilities of dependencies between head-words in the parse tree, which trains on 40,000 sentences in under 15 minutes and can be improved to over 200 sentences a minute with negligible loss in accuracy.
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.
Statistical decision-tree models for parsing
533 Citations1995David M. Magerman
SPATTER is described, a statistical parser based on decision-tree learning techniques which constructs a complete parse for every sentence and achieves accuracy rates far better than any published result.
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
National Conference on Artificial IntelligenceTree-bank Grammars
268 Citations1996Eugene Charniak
This paper presents results on a tree-bank grammar based on the Penn WaII Street Journal tree bank that outperforms other non-word-based statistical parsers/grammars on this corpus and outperforms parsers that consider the input as a string of tags and ignore the actual words of the corpus.
Computational LinguisticsIntricacies of Collins' Parsing Model
265 Citations2004Daniel M. Bikel
A large set of heretofore unpublished details Collins used in his parser are documents, such that, along with Collins' (1999) thesis, this article contains all information necessary to duplicate Collins' benchmark results.
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.
IEEE Transactions on ComputersApplying Probability Measures to Abstract Languages
232 Citations1973Taylor L. Booth, Richard A. Thompson
The problem of assigning a probability to each word of a language is considered and two methods are discussed.
The grammar matrix
173 Citations2002Emily M. Bender, Dan Flickinger +1 more
The grammar matrix is an open-source starter-kit for the development of broad-coverage HPSGs that facilitates not only quick start-up but also rapid growth towards the wide coverage necessary for robust natural language processing and the precision parses and semantic representations necessary for natural language understanding.
Two Experiments on Learning Probabilistic Dependency Grammars from Corpora
164 Citations1992Glenn R. Carroll, Eugene Charniak
This work presents a scheme for learning probabilistic dependency grammars from positive training examples plus constraints on rules plus results of two experiments, in which the constraints were minimal and the first experiment was unsuccessful.
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.
ScholarlyCommons (University of Pennsylvania)On the parameter space of generative lexicalized statistical parsing models
126 Citations2004Daniel M. Bikel, Mitchell P. Marcus
The argument is that lexicalized statistical parsing models have become increasingly complex, and therefore require thorough scrutiny, both to achieve the scientific aim of understanding what has been built thus far, and to achieve both the scientific and engineering goal of using that understanding for progress.
Solving the problem of cascading errors
115 Citations2006Jenny Rose Finkel, Christopher D. Manning +1 more
A novel architecture is presented, which models these pipelines as Bayesian networks, with each low level task corresponding to a variable in the network, and then it is performed approximate inference to find the best labeling.
Building a Treebank for Italian: a Data-driven Annotation Schema
98 Citations2000Cristina Bosco, Vincenzo Lombardo +2 more
This paper presents a data-driven annotation schema developed for an Italian treebank ensuring data coverage and consistency between annotation of linguistic phenomena and describes the cyclical development of the annotation schema highlighting the richness and flexibility of the format.
Learning a Part-of-Speech Tagger from Two Hours of Annotation
96 Citations2013Dan Garrette, Jason Baldridge
This paper attempts to create true low-resource scenarios by allowing a linguist just two hours to annotate data and evaluating on the languages Kinyarwanda and Malagasy through a method of automatically generalizing the annotations, reducing noise, and inducing word-tag frequency information.
Towards history-based grammars
91 Citations1992Ezra Black, Fred Jelinek +4 more
HBG incorporates lexical, syntactic, semantic, and structural information from the parse tree into the disambiguation process in a novel way, and significantly outperforms P-CFG, increasing the parsing accuracy rate from 60% to 75%, a 37% reduction in error.
Self-training PCFG grammars with latent annotations across languages
87 Citations2009Zhongqiang Huang, Mary P. Harper
It is shown for the first time that self-training is able to significantly improve the performance of the PCFG-LA parser, a single generative parser, on both small and large amounts of labeled training data.
ScholarlyCommons (University of Pennsylvania)Experiments with Spectral Learning of Latent-Variable PCFGs
57 Citations2013Shay B. Cohen, Karl Stratos +3 more
Experiments in parallel-text based grammar induction
52 Citations2004Jonas Kuhn
This paper discusses the use of statistical word alignment over multiple parallel texts for the identification of string spans that cannot be constituents in one of the languages, and presents experimental results with an evaluation against the Penn Tree-bank.
Simple Unsupervised Grammar Induction from Raw Text with Cascaded Finite State Models
48 Citations2011Elias Ponvert, Jason Baldridge +1 more
It is shown that addressing this task directly, using probabilistic finite-state methods, produces better results than relying on the local predictions of a current best unsu-pervised parser, Seginer's (2007) CCL.
Real-World Semi-Supervised Learning of POS-Taggers for Low-Resource Languages
48 Citations2013Dan Garrette, Jason D. Mielens +1 more
The results show that annotation of word types is the most important, provided a sufficiently capable semi-supervised learning infrastructure is in place to project type information onto a raw corpus and that finitestate morphological analyzers are effective sources of type information when few labeled examples are available.
Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
42 Citations2012Hiroyuki Shindo, Yusuke Miyao +2 more
This work presents a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR- TSG to simpler CFG rules, and develops an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling.
Sparse multi-scale grammars for discriminative latent variable parsing
38 Citations2008Slav Petrov, Dan Klein
This work presents a discriminative, latent variable approach to syntactic parsing in which rules exist at multiple scales of refinement, and produces the best published parsing accuracies with the smallest reported grammars.
Oxford University Press eBooksProbabilistic grammars and hierarchical Dirichlet processes
25 Citations2018Percy Liang, Michael I. Jordan +1 more
An overview of the formal probabilistic specification of the HDP-PCFG, algorithms for posterior inference under the HDP-PCFG, and experiments on grammar learning run on the Wall Street Journal portion of the Penn Treebank are provided.
Breaking the Resource Bottleneck for Multilingual Parsing
24 Citations2005Rebecca Hwa, Philip Resnik +1 more
A large-scale experiment is presented showing that Chinese dependency trees can be induced by using an English parser, a word alignment package, and a large corpus of sentence-aligned bilingual text, and it is found that a parser trained in this manner out-performs some simple baselines inspite of the noise in the induced treebank.
Collapsed Variational Bayesian Inference for PCFGs
10 Citations2013Pengyu Wang, Phil Blunsom
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.