A Context Free TAG Variant

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 302–310, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics A Context Free TAG Variant Ben Swanson Brown University Providence, RI chonger@cs.brown.edu Eugene Charniak Brown University Providence, RI ec@cs.brown.edu Elif Yamangil Harvard University Cambridge, MA elif@eecs.harvard.edu Stuart Shieber Harvard University Cambridge, MA shieber@eecs.harvard.edu Abstract We propose a new variant of Tree- Adjoining Grammar that allows adjunc- tion of full wrapping trees but still bears only context-free expressivity. We provide a transformation to context-free form, and a further reduction in probabilistic model size through factorization and pooling of parameters. This collapsed context-free form is used to implement efficient gram- mar estimation and parsing algorithms. We perform parsing experiments the Penn Treebank and draw comparisons to Tree- Substitution Grammars and between dif- ferent variations in probabilistic model de- sign. Examination of the most probable derivations reveals examples of the lin- guistically relevant structure that our vari- ant makes possible. 1 Introduction While it is widely accepted that natural language is not context-free, practical limitations of ex- isting algorithms motivate Context-Free Gram- mars (CFGs) as a good balance between model- ing power and asymptotic performance (Charniak, 1996). In constituent-based parsing work, the pre- vailing technique to combat this divide between efficient models and real world data has been to selectively strengthen the dependencies in a CFG by increasing the grammar size through methods such as symbol refinement (Petrov et al., 2006). Another approach is to employ a more power- ful grammatical formalism and devise constraints and transformations that allow use of essential ef- ficient algorithms such as the Inside-Outside al- gorithm (Lari and Young, 1990) and CYK pars- ing. Tree-Adjoining Grammar (TAG) is a natural starting point for such methods as it is the canoni- cal member of the mildly context-sensitive family, falling just above CFGs in the hierarchy of for- mal grammars. TAG has a crucial advantage over CFGs in its ability to represent long distance in- teractions in the face of the interposing variations that commonly manifest in natural language (Joshi and Schabes, 1997). Consider, for example, the sentences These pretzels are making me thirsty. These pretzels are not making me thirsty. These pretzels that I ate are making me thirsty. Using a context-free language model with proper phrase bracketing, the connection between the words pretzels and thirsty must be recorded with three separate patterns, which can lead to poor generalizability and unreliable sparse fre- quency estimates in probabilistic models. While these problems can be overcome to some extent with large amounts of data, redundant representa- tion of patterns is particularly undesirable for sys- tems that seek to extract coherent and concise in- formation from text. TAG allows a linguistically motivated treatment of the example sentences above by generating the last two sentences through modification of the first, applying operations corresponding to nega- tion and the use of a subordinate clause. Un- fortunately, the added expressive power of TAG comes with O(n6) time complexity for essential algorithms …

Content truncated to 500 words