A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
Auli, Michael and Lopez, Adam

Article Structure

Abstract

Via an oracle experiment, we show that the upper bound on accuracy of a CCG parser is significantly lowered when its search space is pruned using a supertagger, though the supertagger also prunes many bad parses.

Introduction

Accurate and efficient parsing of Combinatorial Cat-egorial Grammar (CCG; Steedman, 2000) is a longstanding problem in computational linguistics, due to the complexities associated its mild context sensitivity.

CCG and Supertagging

CCG is a lexicalized grammar formalism encoding for each word lexical categories that are either basic (eg.

Oracle Parsing

What is the effect of these approximations?

Integrated Supertagging and Parsing

The supertagger obviously has good but not perfect predictive features.

Experiments

Parser.

Conclusion and Future Work

Our approach of combining models to avoid the pipeline problem (Felzenszwalb and McAllester, 2007) is very much in line with much recent work in NLP.

Topics

CCG

Appears in 13 sentences as: CCG (13)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. Via an oracle experiment, we show that the upper bound on accuracy of a CCG parser is significantly lowered when its search space is pruned using a supertagger, though the supertagger also prunes many bad parses.
    Page 1, “Abstract”
  2. Accurate and efficient parsing of Combinatorial Cat-egorial Grammar ( CCG ; Steedman, 2000) is a longstanding problem in computational linguistics, due to the complexities associated its mild context sensitivity.
    Page 1, “Introduction”
  3. Even for practical CCG that are strongly context-free (Fowler and Penn, 2010), parsing is much harder than with Penn Treebank—style context-free grammars, with vast numbers of nonterminal categories leading to increased grammar constants.
    Page 1, “Introduction”
  4. Where a typical Penn Treebank grammar may have fewer than 100 nonterminals (Hockenmaier and Steedman, 2002), we found that a CCG grammar derived from CCGbank contained over 1500.
    Page 1, “Introduction”
  5. The most successful approach to CCG parsing is based on a pipeline strategy (§2).
    Page 1, “Introduction”
  6. In both cases our model significantly outperforms the pipeline approach, leading to the best published results in CCG parsing (§5).
    Page 1, “Introduction”
  7. CCG is a lexicalized grammar formalism encoding for each word lexical categories that are either basic (eg.
    Page 2, “CCG and Supertagging”
  8. As can be inferred from even this small example, a key difficulty in parsing CCG is that the number of categories quickly becomes extremely large, and there are typically many ways to analyze every span of a sentence.
    Page 2, “CCG and Supertagging”
  9. Even allowing for the observation of Fowler and Penn (2010) that our practical CCG is context-free, this problem still reduces to the construction of Bar-Hillel et al.
    Page 4, “Integrated Supertagging and Parsing”
  10. We evaluated on CCGbank (Hockenmaier and Steedman, 2007), a rightmost normal-form CCG version of the Penn Treebank.
    Page 6, “Experiments”
  11. :nce our combined model represents the best CCG rsing results under any setting.
    Page 7, “Experiments”

See all papers in Proc. ACL 2011 that mention CCG.

See all papers in Proc. ACL that mention CCG.

Back to top.

F-score

Appears in 6 sentences as: F-score (6)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. To answer this question we computed oracle best and worst values for labelled dependency F-score using the algorithm of Huang (2008) on the hybrid model of Clark and Curran (2007), the best model of their C&C parser.
    Page 2, “Oracle Parsing”
  2. Labelleld F-score
    Page 3, “Oracle Parsing”
  3. Digging deeper, we compared parser model score against Viterbi F—score and oracle F-score at a va-
    Page 3, “Oracle Parsing”
  4. Labelleld F-score
    Page 3, “Oracle Parsing”
  5. The inverse relationship between model score and F-score shows that the supertagger restricts the parser to mostly good parses (under F-measure) that the model would otherwise disprefer.
    Page 3, “Oracle Parsing”
  6. Labelled F-score 00 \l 00
    Page 7, “Experiments”

See all papers in Proc. ACL 2011 that mention F-score.

See all papers in Proc. ACL that mention F-score.

Back to top.

Model score

Appears in 6 sentences as: Model score (3) model score (3)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. Model score
    Page 3, “Oracle Parsing”
  2. Digging deeper, we compared parser model score against Viterbi F—score and oracle F-score at a va-
    Page 3, “Oracle Parsing”
  3. Model score
    Page 3, “Oracle Parsing”
  4. - - - - Model score
    Page 3, “Oracle Parsing”
  5. The inverse relationship between model score and F-score shows that the supertagger restricts the parser to mostly good parses (under F-measure) that the model would otherwise disprefer.
    Page 3, “Oracle Parsing”
  6. Both show an [proved relationship between model score and F-:asure.
    Page 7, “Experiments”

See all papers in Proc. ACL 2011 that mention Model score.

See all papers in Proc. ACL that mention Model score.

Back to top.

parsing model

Appears in 5 sentences as: parser model (1) parsing model (4)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. However, the technique is inherently approximate: it will return a lower probability parse under the parsing model if a higher probability parse can only be constructed from a supertag sequence returned by a subsequent iteration.
    Page 2, “CCG and Supertagging”
  2. Digging deeper, we compared parser model score against Viterbi F—score and oracle F-score at a va-
    Page 3, “Oracle Parsing”
  3. An obvious way to exploit this without being bound by its decisions is to incorporate these features directly into the parsing model .
    Page 3, “Integrated Supertagging and Parsing”
  4. We apply both techniques to our integrated supertagging and parsing model .
    Page 4, “Integrated Supertagging and Parsing”
  5. Our parsing model is also a distribution over variables Ti, along with an additional quadratic number of span(i, j ) variables.
    Page 5, “Integrated Supertagging and Parsing”

See all papers in Proc. ACL 2011 that mention parsing model.

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

Back to top.

F-measure

Appears in 4 sentences as: F-measure (5)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. F-measure
    Page 3, “Oracle Parsing”
  2. The inverse relationship between model score and F-score shows that the supertagger restricts the parser to mostly good parses (under F-measure ) that the model would otherwise disprefer.
    Page 3, “Oracle Parsing”
  3. Overall, we improve the labelled F-measure by almost 1.1% and unlabelled F-measure by 0.6% over the baseline.
    Page 7, “Experiments”
  4. Table 6: Parsing time in seconds per sentence (vs. F-measure ) on section 00.
    Page 9, “Experiments”

See all papers in Proc. ACL 2011 that mention F-measure.

See all papers in Proc. ACL that mention F-measure.

Back to top.

development set

Appears in 3 sentences as: development set (3)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. The reason that using the gold-standard supertags doesn’t result in 100% oracle parsing accuracy is that some of the development set parses cannot be constructed by the learned grammar.
    Page 3, “Oracle Parsing”
  2. riety of fixed beam settings (Figure l), considering only the subset of our development set which could be parsed with all beam settings.
    Page 3, “Oracle Parsing”
  3. We measured the evolving accuracy of the models on the development set (Figure 4).
    Page 6, “Experiments”

See all papers in Proc. ACL 2011 that mention development set.

See all papers in Proc. ACL that mention development set.

Back to top.

lexicalized

Appears in 3 sentences as: lexicalized (3)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. CCG is a lexicalized grammar formalism encoding for each word lexical categories that are either basic (eg.
    Page 2, “CCG and Supertagging”
  2. (2010) and lexicalized CFG parsing by Rush et al.
    Page 4, “Integrated Supertagging and Parsing”
  3. Though we have focused on CCG in this work we expect these methods to be equally useful for other linguistically motivated but computationally complex formalisms such as lexicalized tree adjoining grammar.
    Page 9, “Conclusion and Future Work”

See all papers in Proc. ACL 2011 that mention lexicalized.

See all papers in Proc. ACL that mention lexicalized.

Back to top.

part-of-speech

Appears in 3 sentences as: part-of-speech (3)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. We supply gold-standard part-of-speech tags to the parsers.
    Page 6, “Experiments”
  2. Next, we evaluate performance when using automatic part-of-speech tags as input to our parser
    Page 7, “Experiments”
  3. Such diverse topics as machine translation (Dyer et al., 2008; Dyer and Resnik, 2010; Mi et al., 2008), part-of-speech tagging (Jiang et al., 2008), named entity recognition (Finkel and Manning, 2009) semantic role labelling (Sutton and McCallum, 2005; Finkel et al., 2006), and others have also been improved by combined models.
    Page 9, “Conclusion and Future Work”

See all papers in Proc. ACL 2011 that mention part-of-speech.

See all papers in Proc. ACL that mention part-of-speech.

Back to top.

part-of-speech tags

Appears in 3 sentences as: part-of-speech tagging (1) part-of-speech tags (2)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. We supply gold-standard part-of-speech tags to the parsers.
    Page 6, “Experiments”
  2. Next, we evaluate performance when using automatic part-of-speech tags as input to our parser
    Page 7, “Experiments”
  3. Such diverse topics as machine translation (Dyer et al., 2008; Dyer and Resnik, 2010; Mi et al., 2008), part-of-speech tagging (Jiang et al., 2008), named entity recognition (Finkel and Manning, 2009) semantic role labelling (Sutton and McCallum, 2005; Finkel et al., 2006), and others have also been improved by combined models.
    Page 9, “Conclusion and Future Work”

See all papers in Proc. ACL 2011 that mention part-of-speech tags.

See all papers in Proc. ACL that mention part-of-speech tags.

Back to top.

POS tags

Appears in 3 sentences as: POS tagger (1) POS tags (2)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. On CCGbank we achieve a labelled dependency F—measure of 88.8% on gold POS tags , and 86.7% on automatic part-of-speeoch tags, the best reported results for this task.
    Page 1, “Abstract”
  2. To the best of our knowledge, the results obtained with BP and DD are the best reported results on this task using gold POS tags .
    Page 7, “Experiments”
  3. In future work we plan to integrate the POS tagger , which is crucial to parsing accuracy (Clark and Curran, 2004b).
    Page 9, “Conclusion and Future Work”

See all papers in Proc. ACL 2011 that mention POS tags.

See all papers in Proc. ACL that mention POS tags.

Back to top.

Viterbi

Appears in 3 sentences as: Viterbi (3)
In A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing
  1. We can also see from the scores of the Viterbi parses that while the reverse condition has access to much better parses, the model doesn’t actually find them.
    Page 3, “Oracle Parsing”
  2. Digging deeper, we compared parser model score against Viterbi F—score and oracle F-score at a va-
    Page 3, “Oracle Parsing”
  3. Training a model using DD would require a different optimization algorithm based on Viterbi results (e. g. the perceptron) which we will pursue in future work.
    Page 9, “Experiments”

See all papers in Proc. ACL 2011 that mention Viterbi.

See all papers in Proc. ACL that mention Viterbi.

Back to top.

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