Elamur Research⌕
☰
home / papers / 2004 / Parsing the WSJ Using CCG and Log-Linear Models

Parsing the WSJ Using CCG and Log-Linear Models

Summary

Combinatory Categorial Grammar (CCG) allows many different derivations to produce the same final structure, a phenomenon called spurious ambiguity. This makes statistical modelling and parsing harder. Clark and Curran build discriminative log-linear models for wide-coverage CCG parsing of the WSJ Penn Treebank, trained on CCGbank. They compare two designs:

  • a dependency model, which sums probability over every derivation that yields a given dependency structure;
  • a normal-form model, which scores only canonical derivations.

Both are trained by maximising conditional log-likelihood with a Gaussian prior. Expectations are computed with an inside-outside procedure over packed charts, treated as feature forests. The authors found Generalised Iterative Scaling (GIS) unsuitable at this scale and replaced it with a parallel L-BFGS running on a Beowulf cluster, so the entire treebank could be used for training. They also propose a parsing algorithm that maximises the expected recall of dependencies.

The two models reach similar accuracy. The normal-form model is cheaper to train and much faster at parsing. It clearly beats Clark et al. (2002) and matches or exceeds the state of the art for CCG parsing.

Key points

  • Test-set results (gold POS tags), for the best normal-form log-linear model:
    • labelled P/R: 86.6/86.3
    • unlabelled P/R: 92.5/92.1
    • category accuracy: 93.6
  • Comparison systems (labelled P/R): Hockenmaier 2003 reached 84.3/84.6, and Clark et al. 2002 reached 81.9/81.8.
  • Automatic POS tags: with tags from the C&C POS tagger, the log-linear model drops to 84.8/84.5 labelled P/R, because the supertagger relies heavily on POS features.
  • Parsing speed: the 2,401 sentences of section 23 take 1.6 minutes with the normal-form model and 10.5 minutes with the dependency model. The gap comes mainly from the normal-form constraints on rule application.
  • Dependency representation: each dependency is a 5-tuple of head word, lexical category, argument slot, argument head and a long-range marker.
  • Larger training charts: the best model was trained on charts with about 2.9 supertagger categories per word, estimated on 15 machines. This gave an accuracy gain.
  • Oracle experiment: with gold CCGbank lexical categories on section 00, 7% of sentences could not be parsed. On the rest, labelled F-score was almost 98%.

Interesting ideas

  • I1. Training against a structure, not a derivation. When many hidden derivations lead to the same gold output, the "empirical" side of the gradient can be an expectation over all derivations consistent with the gold structure. This applies to any task with latent structure and only partial supervision.
  • I2. Packed charts as feature forests. Grouping equivalent chart entries (same category, head and unfilled dependencies) lets estimation and decoding sum over exponentially many analyses without listing them. The features chosen decide which entries may be merged, a design trade-off worth keeping in mind for any chart-based model.
  • I3. Decode for the evaluation metric. Choosing the output that maximises expected dependency recall, rather than the single most probable derivation, aligns decoding with how the parser is scored. This idea transfers to other structured prediction tasks.
  • I4. Parallelise the optimiser, not just the data. Running L-BFGS across a cluster, and dropping GIS when it proved unsuitable, made training on the full corpus feasible. This is a reminder that the choice of optimiser can decide what data scale is reachable.
  • I5. Oracle experiments to locate bottlenecks. Feeding the parser gold lexical categories shows how much accuracy is lost upstream in supertagging. That points future effort at the right component, and the same check suits any pipeline system.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Cited by

110 papers of our library cite it (of the 140884 whose bibliographies we read); 11 of them have a page here, 99 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/1218955.1218969

@inproceedings{clark2004parsing,
  title = {{Parsing the WSJ Using CCG and Log-Linear Models}},
  author = {Clark, Stephen and Curran, James R.},
  booktitle = {Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL-04)},
  year = {2004},
  doi = {10.3115/1218955.1218969},
  url = {https://doi.org/10.3115/1218955.1218969}
}

References

19 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Adam Berger, Stephen Della Pietra, and Vincent Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71. find our card
  2. Stanley Chen and Ronald Rosenfeld. 1999. A Gaussian prior for smoothing maximum entropy models. Technical report, Carnegie Mellon University, Pittsburgh, PA. find
  3. Stephen Clark and James R. Curran. 2003. Log-linear models for wide-coverage CCG parsing. In Proceedings of the EMNLP Conference, pages 97–104, Sapporo, Japan. find
  4. Stephen Clark and James R. Curran. 2004. The importance of supertagging for wide-coverage CCG parsing. In Proceedings of COLING-04, Geneva, Switzerland. find our card
  5. Stephen Clark, Julia Hockenmaier, and Mark Steedman. 2002. Building deep dependency structures with a wide-coverage CCG parser. In Proceedings of the 40th Meeting of the ACL, pages 327–334, Philadelphia, PA. find
  6. Michael Collins. 1996. A new statistical parser based on bigram lexical dependencies. In Proceedings of the 34th Meeting of the ACL, pages 184–191, Santa Cruz, CA. find
  7. James R. Curran and Stephen Clark. 2003. Investigating GIS and smoothing for maximum entropy taggers. In Proceedings of the 10th Meeting of the EACL, pages 91–98, Budapest, Hungary. find
  8. Jason Eisner. 1996. Efficient normal-form parsing for Combinatory Categorial Grammar. In Proceedings of the 34th Meeting of the ACL, pages 79–86, Santa Cruz, CA. find
  9. Daniel Gildea. 2001. Corpus variation and parser performance. In Proceedings of the EMNLP Conference, pages 167–202, Pittsburgh, PA. find our card
  10. Joshua Goodman. 1996. Parsing algorithms and metrics. In Proceedings of the 34th Meeting of the ACL, pages 177–183, Santa Cruz, CA. find
  11. Julia Hockenmaier and Mark Steedman. 2002. Generative models for statistical parsing with Combinatory Categorial Grammar. In Proceedings of the 40th Meeting of the ACL, pages 335–342, Philadelphia, PA. find
  12. Julia Hockenmaier. 2003a. Data and Models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh. find
  13. Julia Hockenmaier. 2003b. Parsing with generative models of predicate-argument structure. In Proceedings of the 41st Meeting of the ACL, pages 359–366, Sapporo, Japan. find
  14. Yusuke Miyao and Jun’ichi Tsujii. 2002. Maximum entropy estimation for feature forests. In Proceedings of the Human Language Technology Conference, San Diego, CA. find
  15. Jorge Nocedal and Stephen J. Wright. 1999. Numerical Optimization. Springer, New York, USA. find
  16. Stefan Riezler, Tracy H. King, Ronald M. Kaplan, Richard Crouch, John T. Maxwell III, and Mark Johnson. 2002. Parsing the Wall Street Journal using a Lexical-Functional Grammar and discriminative estimation techniques. In Proceedings of the 40th Meeting of the ACL, pages 271–278, Philadelphia, PA. find our card
  17. Fei Sha and Fernando Pereira. 2003. Shallow parsing with conditional random fields. In Proceedings of the HLT/NAACL Conference, pages 213–220, Edmonton, Canada. find
  18. Mark Steedman. 2000. The Syntactic Process. The MIT Press, Cambridge, MA. find
  19. Kristina Toutanova, Christopher Manning, Stuart Shieber, Dan Flickinger, and Stephan Oepen. 2002. Parse disambiguation for a rich HPSG grammar. In Proceedings of the First Workshop on Treebanks and Linguistic Theories, pages 253–263, Sozopol, Bulgaria. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/clark-2004-parsing-wsj-ccg-log-linear/