A Context Free TAG Variant
Swanson, Ben and Yamangil, Elif and Charniak, Eugene and Shieber, Stuart

Article Structure

Abstract

We propose a new variant of Tree-Adjoining Grammar that allows adjunction of full wrapping trees but still bears only context-free expressivity.

Introduction

While it is widely accepted that natural language is not context-free, practical limitations of existing algorithms motivate Context-Free Grammars (CFGs) as a good balance between modeling power and asymptotic performance (Charniak, 1996).

TAG and Variants

Here we provide a short history of the relevant work in related grammar formalisms, leading up to a definition of OSTAG.

Transformation to CFG

To demonstrate that OSTAG has only context-free power, we provide a reduction to context-free grammar.

Applications

4.1 Compact grammars

Experiments

As a proof of concept, we investigate OSTAG in the context of the classic Penn Treebank statistical parsing setup; training on section 2-21 and testing on section 23.

Conclusion

The OSTAG variant of Tree-Adjoining Grammar is a simple weakly context-free formalism that still provides for all types of adjunction and is a bit more concise than TSG (quadratically so).

Topics

probabilistic model

Appears in 10 sentences as: probabilistic model (4) probabilistic modeling (2) probabilistic models (4)
In A Context Free TAG Variant
  1. We provide a transformation to context-free form, and a further reduction in probabilistic model size through factorization and pooling of parameters.
    Page 1, “Abstract”
  2. We perform parsing experiments the Penn Treebank and draw comparisons to Tree-Substitution Grammars and between different variations in probabilistic model design.
    Page 1, “Abstract”
  3. 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 frequency estimates in probabilistic models .
    Page 1, “Introduction”
  4. Using an automatically induced Tree-Substitution Grammar (TSG), we heuristically extract an OSTAG and estimate its parameters from data using models with various reduced probabilistic models of adjunction.
    Page 2, “Introduction”
  5. A simple probabilistic model for a TSG is a set of multinomials, one for each nonterminal in N corresponding to its possible substitutions in R. A more flexible model allows a potentially infinite number of substitution rules using a Dirichlet Process (Cohn et al., 2009; Cohn and Blunsom, 2010).
    Page 2, “TAG and Variants”
  6. As such, probabilistic modeling for TAG in its original form is uncommon.
    Page 3, “TAG and Variants”
  7. Several probabilistic models have been proposed for TIG.
    Page 3, “TAG and Variants”
  8. The following sections discuss in detail the context-free nature of OSTAG and alternative probabilistic models for its equivalent CFG form.
    Page 3, “TAG and Variants”
  9. To avoid double-counting derivations, which can adversely effect probabilistic modeling , type (3) and type (4) rules in which the side with the unapplied symbol is a nonterminal leaf can be omitted.
    Page 5, “Transformation to CFG”
  10. In this section we present a probabilistic model for an OSTAG grammar in PCFG form that can be used in such algorithms, and show that many parameters of this PCFG can be pooled or set equal to one and ignored.
    Page 5, “Applications”

See all papers in Proc. ACL 2013 that mention probabilistic model.

See all papers in Proc. ACL that mention probabilistic model.

Back to top.

grammar induction

Appears in 7 sentences as: grammar induction (7)
In A Context Free TAG Variant
  1. This model has proven effective for grammar induction via Markov Chain Monte Carlo (MCMC), in which TSG derivations of the training set are repeatedly sampled to find frequently occurring elementary trees.
    Page 2, “TAG and Variants”
  2. However, a large effort in non-probabilistic grammar induction has been performed through manual annotation with the XTAG project(Doran et al., 1994).
    Page 3, “TAG and Variants”
  3. Later approaches (Shindo et al., 2011; Yamangil and Shieber, 2012) were able to extend the nonparametric modeling of TSGs to TIG, providing methods for both modeling and grammar induction .
    Page 3, “TAG and Variants”
  4. We propose a simple but empirically effective heuristic for grammar induction for our experiments on Penn Treebank data.
    Page 3, “TAG and Variants”
  5. A compact TSG can be obtained automatically using the MCMC grammar induction technique of Cohn and Blunsom (2010), retaining all TSG rules that appear in at least one derivation in after 1000 iterations of sampling.
    Page 6, “Experiments”
  6. While our grammar induction method is a crude (but effective) heuristic, we can still highlight the qualities of the more important auxiliary trees by examining aggregate statistics over the MPD parses, shown in Figure 6.
    Page 8, “Experiments”
  7. The most important direction of future work for OSTAG is the development of a principled grammar induction model, perhaps using the same techniques that have been successfully applied to TSG and TIG.
    Page 8, “Conclusion”

See all papers in Proc. ACL 2013 that mention grammar induction.

See all papers in Proc. ACL that mention grammar induction.

Back to top.

Penn Treebank

Appears in 5 sentences as: Penn Treebank (5)
In A Context Free TAG Variant
  1. We perform parsing experiments the Penn Treebank and draw comparisons to Tree-Substitution Grammars and between different variations in probabilistic model design.
    Page 1, “Abstract”
  2. We evaluate OSTAG on the familiar task of parsing the Penn Treebank .
    Page 2, “Introduction”
  3. We propose a simple but empirically effective heuristic for grammar induction for our experiments on Penn Treebank data.
    Page 3, “TAG and Variants”
  4. As a proof of concept, we investigate OSTAG in the context of the classic Penn Treebank statistical parsing setup; training on section 2-21 and testing on section 23.
    Page 6, “Experiments”
  5. Furthermore, the various parameteri-zations of adjunction with OSTAG indicate that, at least in the case of the Penn Treebank , the finer grained modeling of a full table of adjunction probabilities for each Goodman index OSTAG3 overcomes the danger of sparse data estimates.
    Page 7, “Experiments”

See all papers in Proc. ACL 2013 that mention Penn Treebank.

See all papers in Proc. ACL that mention Penn Treebank.

Back to top.

Treebank

Appears in 5 sentences as: Treebank (5)
In A Context Free TAG Variant
  1. We perform parsing experiments the Penn Treebank and draw comparisons to Tree-Substitution Grammars and between different variations in probabilistic model design.
    Page 1, “Abstract”
  2. We evaluate OSTAG on the familiar task of parsing the Penn Treebank .
    Page 2, “Introduction”
  3. We propose a simple but empirically effective heuristic for grammar induction for our experiments on Penn Treebank data.
    Page 3, “TAG and Variants”
  4. As a proof of concept, we investigate OSTAG in the context of the classic Penn Treebank statistical parsing setup; training on section 2-21 and testing on section 23.
    Page 6, “Experiments”
  5. Furthermore, the various parameteri-zations of adjunction with OSTAG indicate that, at least in the case of the Penn Treebank , the finer grained modeling of a full table of adjunction probabilities for each Goodman index OSTAG3 overcomes the danger of sparse data estimates.
    Page 7, “Experiments”

See all papers in Proc. ACL 2013 that mention Treebank.

See all papers in Proc. ACL that mention Treebank.

Back to top.

PDF available from www.aclweb.org.
Send us an email