Tree substitution grammars ( TSGs ) are a compelling alternative to context-free grammars for modelling syntax . However , many popular techniques for estimating weighted TSGs ( under the moniker of Data Oriented Parsing ) suffer from the problems of inconsistency and over-fitting . We present a theoretically principled model which solves these problems using a Bayesian non-parametric formulation . Our model learns compact and simple grammars , uncovering latent linguistic structures ( e.g. , verb subcategorisation ) , and in doing so far out-performs a standard PCFG . Many successful models of syntax are based on Probabilistic Context Free Grammars ( PCFGs ) ( e.g. , Collins ( 1999 ) ) . However , directly learning a PCFG from a treebank results in poor parsing performance , due largely to the unrealistic independence assumptions imposed by the context-free assumption . Considerable effort is required to coax good results from a PCFG , in the form of grammar engineering , feature selection and clever smoothing ( Collins , 1999 ; Charniak , 2000 ; Charniak and Johnson , 2005 ; Johnson , 1998 ) . This effort must be repeated when moving to different languages , grammar formalisms or treebanks . We propose that much of this hand-coded knowledge can be obtained automatically as an emergent property of the treebanked data , thereby reducing the need for human input in crafting the grammar . We present a model for automatically learning a Probabilistic Tree Substitution Grammar ( PTSG ) , an extension to the PCFG in which non-terminals can rewrite as entire tree fragments ( elementary trees ) , not just immediate children . These large fragments can be used to encode non-local context , such as head-lexicalisation and verb sub-categorisation . Since no annotated data is available providing TSG derivations we must induce the PTSG productions and their probabilities in an unsupervised way from an ordinary treebank . This is the same problem addressed by Data Oriented Parsing ( DOP , Bod et al . ( 2003 ) ) , a method which uses as productions all subtrees of the training corpus . However , many of the DOP estimation methods have serious shortcomings ( Johnson , 2002 ) , namely inconsistency for DOP1 ( Bod , 2003 ) and overfitting of the maximum likelihood estimate ( Prescher et al . , 2004 ) . In this paper we develop an alternative means of learning a PTSG from a treebanked corpus , with the twin objectives of a ) finding a grammar which accurately models the data and b ) keeping the grammar as simple as possible , with few , compact , elementary trees . This is achieved using a prior to encourage sparsity and simplicity in a Bayesian nonparametric formulation . The framework allows us to perform inference over an infinite space of grammar productions in an elegant and efficient manner . The net result is a grammar which only uses the increased context afforded by the TSG when necessary to model the data , and otherwise uses context-free rules . 1 That is , our model learns to use larger rules when the CFG 's independence assumptions do not hold . This contrasts with DOP , which seeks to use all elementary trees from the training set . While our model is able , in theory , to use all such trees , in practice the data does not justify such a large grammar . Grammars that are only about twice the size of a treebank PCFG provide large gains in accuracy . We obtain additional improvements with grammars that are somewhat larger , but still much smaller than the DOP all-subtrees grammar . The rules in these grammars are intuitive , potentially offering insights into grammatical structure which could be used in , e.g. , the development of syntactic ontologies and guidelines for future treebanking projects . In this work we have presented a non-parametric Bayesian model for inducing tree substitution grammars . By incorporating a structured prior over elementary rules our model is able to reason over the infinite space of all such rules , producing compact and simple grammars . In doing so our model learns local structures for latent linguistic phenomena , such as verb subcategorisation and lexical agreement . Our experimental results show that the induced grammars strongly out-perform standard PCFGs , and are comparable to a state-of-the-art parser on small data samples . While our results on the full treebank are well shy of the best available parsers , we have proposed a number of improvements to the model and the parsing algorithm that could lead to state-of-theart performance in the future .
Although Probabilistic Context Free Grammers-based models are currently successful, they suffer from inconsistency and over-fitting when learning from a treebank.
They propose a Probabilistic Tree Substitution Grammer model with a Bayesian-based algorithm for training to accurately model the data and to keep the grammar simple.
The proposed model learns local structures for latent linguistic phenomena outperforms standard methods and is comparable to state-of-the-art methods on small data.