Mova0.5 pre-release⌕
☰
home / docs / papers / English / Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models

Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models

What it is about

The article gives a full log-linear parsing model for a CCG grammar extracted automatically from CCGbank. Discriminative training needs the incorrect parses of every training sentence, which is feasible only because a Maximum Entropy supertagger keeps the charts small. Estimation needs up to 25 GB of memory and runs in under three hours on a parallel BFGS implementation. The parser covers 99.63% of section 23 with the hybrid dependency model, and it reaches over 81% labelled F-score on a cross-formalism comparison (upper bound 84.8%). The supertagger is 92.6% accurate on section 00. With a single supertagging level the parser processes over 30 sentences per second.

Ideas

For Mova

The chapter is 21. The simple clause; the code is en/src/parse.rs and en/src/ptag.rs. The paper's accuracy is on CCG dependencies, so its numbers are not comparable with LAS. Its data are CCGbank (WSJ-derived), outside our licence list; test on EWT only.

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/coli.2007.33.4.493

@article{clark2007wide,
  title = {{Wide-Coverage Efficient Statistical Parsing with CCG and Log-Linear Models}},
  author = {Clark, Stephen and Curran, James R.},
  journal = {Computational Linguistics},
  year = {2007},
  doi = {10.1162/coli.2007.33.4.493},
  url = {https://doi.org/10.1162/coli.2007.33.4.493}
}

References

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

  1. Abney, Steven. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23(4):597–618. find
  2. Baldridge, Jason. 2002. Lexically Specified Derivational Control in Combinatory Categorial Grammar. Ph.D. thesis, Edinburgh University, Edinburgh, UK. find
  3. Baldridge, Jason and Geert-Jan Kruijff. 2003. Multi-modal Combinatory Categorial Grammar. In Proceedings of the 10th Meeting of the EACL, pages 211–218, Budapest, Hungary. find
  4. Bangalore, Srinivas and Aravind Joshi. 1999. Supertagging: An approach to almost parsing. Computational Linguistics, 25(2):237–265. find
  5. Bar-Hillel, Yehoshua. 1953. A quasi-arithmetical notation for syntactic description. Language, 29:47–58. find
  6. Borthwick, Andrew. 1999. A Maximum Entropy Approach to Named Entity Recognition. Ph.D. thesis, New York University, New York. find
  7. Bos, Johan, Stephen Clark, Mark Steedman, James R. Curran, and Julia Hockenmaier. 2004. Wide-coverage semantic representations from a CCG parser. In Proceedings of COLING-04, pages 1240–1246, Geneva, Switzerland. find
  8. Briscoe, Ted. 2006. An introduction to tag sequence grammars and the RASP system parser. Technical Report UCAM-CL-TR-662, University of Cambridge Computer Laboratory. find
  9. Briscoe, Ted and John Carroll. 2002. Robust accurate statistical annotation of general text. In Proceedings of the 3rd LREC Conference, pages 1499–1504, Las Palmas, Gran Canaria. find
  10. Briscoe, Ted and John Carroll. 2006. Evaluating the accuracy of an unlexicalized statistical parser on the PARC DepBank. In Proceedings of the Poster Session of the Joint Conference of the International Committee on Computational Linguistics and the Association for Computational Linguistics (COLING/… find
  11. Briscoe, Ted, John Carroll, and Rebecca Watson. 2006. The second release of the RASP system. In Proceedings of the Interactive Demo Session of the Joint Conference of the International Committee on Computational Linguistics and the Association for Computational Linguistics (COLING/ACL-06), pages 77–… find
  12. Buchholz, Sabine, Jorn Veenstra, and Walter Daelemans. 1999. Cascaded grammatical relation assignment. In Proceedings of EMNLP/VLC-99, pages 239–246, University of Maryland, College Park, MD. find
  13. Burke, Michael, Aoife Cahill, Ruth O’Donovan, Josef van Genabith, and Andy Way. 2004. Large-scale induction and evaluation of lexical resources from the Penn-II Treebank. In Proceedings of the 42nd Meeting of the ACL, pages 367–374, Barcelona, Spain. find
  14. Cahill, Aoife, Michael Burke, Ruth O’Donovan, Josef van Genabith, and Andy Way. 2004. Long-distance dependency resolution in automatically acquired wide-coverage PCFG-based LFG approximations. In Proceedings of the 42nd Meeting of the ACL, pages 320–327, Barcelona, Spain. find
  15. Carroll, John, Ted Briscoe, and Antonio Sanfilippo. 1998. Parser evaluation: A survey and a new proposal. In Proceedings of the 1st LREC Conference, pages 447–454, Granada, Spain. find
  16. Charniak, Eugene. 1997. Statistical parsing with a context-free grammar and word statistics. In Proceedings of the 14th National Conference on Artificial Intelligence, pages 598–603, Menlo Park, CA. find
  17. Charniak, Eugene. 2000. A maximum-entropy-inspired parser. In Proceedings of the 1st Meeting of the NAACL, pages 132–139, Seattle, WA. find
  18. Chen, John, Srinivas Bangalore, Michael Collins, and Owen Rambow. 2002. Reranking an N-gram supertagger. In Proceedings of the TAG+ Workshop, pages 259–268, Venice, Italy. find
  19. Chen, John and K. Vijay-Shanker. 2000. Automated extraction of TAGS from the Penn Treebank. In Proceedings of IWPT 2000, Trento, Italy. find
  20. Chen, Stanley and Ronald Rosenfeld. 1999. A Gaussian prior for smoothing maximum entropy models. Technical Report CMU-CS-99-108, Carnegie Mellon University, Pittsburgh, PA. find
  21. Chiang, David. 2000. Statistical parsing with an automatically-extracted Tree Adjoining Grammar. In Proceedings of the 38th Meeting of the ACL, pages 456–463, Hong Kong. find
  22. Chiang, David. 2003. Mildly context sensitive grammars for estimating maximum entropy models. In Proceedings of the 8th Conference on Formal Grammar, Vienna, Austria. find
  23. Clark, Stephen. 2002. A supertagger for Combinatory Categorial Grammar. In Proceedings of the TAG+ Workshop, pages 19–24, Venice, Italy. find
  24. Clark, Stephen 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
  25. Clark, Stephen and James R. Curran. 2004a. The importance of supertagging for wide-coverage CCG parsing. In Proceedings of COLING-04, pages 282–288, Geneva, Switzerland. find our card
  26. Clark, Stephen and James R. Curran. 2004b. Parsing the WSJ using CCG and log-linear models. In Proceedings of the 42nd Meeting of the ACL, pages 104–111, Barcelona, Spain. find
  27. Clark, Stephen and James R. Curran. 2006. Partial training for a lexicalized-grammar parser. In Proceedings of the Human Language Technology Conference and the Annual Meeting of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL’06), pages 144–151, New York. find
  28. Clark, Stephen and James R. Curran. 2007. Formalism-independent parser evaluation with CCG and DepBank. In Proceedings of the 45th Meeting of the ACL, Prague, Czech Republic. find our card
  29. Clark, Stephen, 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
  30. Clark, Stephen, Mark Steedman, and James R. Curran. 2004. Object-extraction and question-parsing using CCG. In Proceedings of the EMNLP Conference, pages 111–118, Barcelona, Spain. find
  31. Collins, Michael. 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
  32. Collins, Michael. 2003. Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4):589–637. find our card
  33. Collins, Michael and James Brooks. 1995. Prepositional phrase attachment through a backed-off model. In Proceedings of the 3rd Workshop on Very Large Corpora, pages 27–38, Cambridge, MA. find our card
  34. Collins, Michael and Terry Koo. 2005. Discriminative reranking for natural language parsing. Computational Linguistics, 31(1):25–69. find our card
  35. Collins, Michael and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of the 42nd Meeting of the ACL, pages 111–118, Barcelona, Spain. find our card
  36. Crouch, Richard, Ronald M. Kaplan, Tracy H. King, and Stefan Riezler. 2002. A comparison of evaluation metrics for a broad-coverage stochastic parser. In Proceedings of the LREC Beyond PARSEVAL workshop, pages 67–74, Las Palmas, Spain. find
  37. Curran, James R. 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
  38. Curran, James R., Stephen Clark, and David Vadas. 2006. Multi-tagging for lexicalized-grammar parsing. In Proceedings of the Joint Conference of the International Committee on Computational Linguistics and the Association for Computational Linguistics (COLING/ACL-06), pages 697–704, Sydney, Australi… find
  39. Curry, Haskell B. and Robert Feys. 1958. Combinatory Logic: Vol. I. Amsterdam, The Netherlands. find
  40. Darroch, J. N. and D. Ratcliff. 1972. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5):1470–1480. find
  41. Della Pietra, Stephen, Vincent Della Pietra, and John Lafferty. 1997. Inducing features of random fields. IEEE Transactions Pattern Analysis and Machine Intelligence, 19(4):380–393. find
  42. Dienes, Peter and Amit Dubey. 2003. Deep syntactic processing by combining shallow methods. In Proceedings of the 41st Meeting of the ACL, pages 431–438, Sapporo, Japan. find
  43. Eisner, Jason. 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
  44. Geman, Stuart and Mark Johnson. 2002. Dynamic programming for parsing and estimation of stochastic unification-based grammars. In Proceedings of the 40th Meeting of the ACL, pages 279–286, Philadelphia, PA. find
  45. Gildea, Daniel. 2001. Corpus variation and parser performance. In 2001 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 167–172, Pittsburgh, PA. find our card
  46. Goodman, Joshua. 1996. Parsing algorithms and metrics. In Proceedings of the 34th Meeting of the ACL, pages 177–183, Santa Cruz, CA. find
  47. Goodman, Joshua. 1997. Probabilistic feature grammars. In Proceedings of the International Workshop on Parsing Technologies, Cambridge, MA. find
  48. Gropp, W., E. Lusk, N. Doss, and A. Skjellum. 1996. A high-performance, portable implementation of the MPI message passing interface standard. Parallel Computing, 22(6):789–828. find
  49. Hockenmaier, Julia. 2003a. Data and Models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, University of Edinburgh, Edinburgh, UK. find
  50. Hockenmaier, Julia. 2003b. Parsing with generative models of predicate-argument structure. In Proceedings of the 41st Meeting of the ACL, pages 359–366, Sapporo, Japan. find
  51. Hockenmaier, Julia and Mark Steedman. 2002a. Acquiring compact lexicalized grammars from a cleaner treebank. In Proceedings of the Third LREC Conference, pages 1974–1981, Las Palmas, Spain. find
  52. Hockenmaier, Julia and Mark Steedman. 2002b. Generative models for statistical parsing with Combinatory Categorial Grammar. In Proceedings of the 40th Meeting of the ACL, pages 335–342, Philadelphia, PA. find
  53. Johnson, Mark. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):613–632. find
  54. Johnson, Mark. 2002. A simple pattern-matching algorithm for recovering empty nodes and their antecedents. In Proceedings of the 40th Meeting of the ACL, pages 136–143, Philadelphia, PA. find
  55. Johnson, Mark, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic ‘unification-based’ grammars. In Proceedings of the 37th Meeting of the ACL, pages 535–541, University of Maryland, College Park, MD. find
  56. Johnson, Mark and Stefan Riezler. 2000. Exploiting auxiliary distributions in stochastic unification-based grammars. In Proceedings of the 1st Meeting of the NAACL, Seattle, WA. find
  57. Kaplan, Ron, Stefan Riezler, Tracy H. King, John T. Maxwell, III, Alexander Vasserman, and Richard Crouch. 2004. Speed and accuracy in shallow and deep stochastic parsing. In Proceedings of the Human Language Technology Conference and the 4th Meeting of the North American Chapter of the Association… find
  58. Kasami, J. 1965. An efficient recognition and syntax analysis algorithm for context-free languages. Technical Report AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA. find
  59. King, Tracy H., Richard Crouch, Stefan Riezler, Mary Dalrymple, and Ronald M. Kaplan. 2003. The PARC 700 Dependency Bank. In Proceedings of the 4th International Workshop on Linguistically Interpreted Corpora, Budapest, Hungary. find
  60. Koeling, Rob. 2000. Chunking with maximum entropy models. In Proceedings of the CoNLL Workshop 2000, pages 139–141, Lisbon, Portugal. find
  61. Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18th International Conference on Machine Learning, pages 282–289, Williams College, Williamstown, MA. find
  62. Lari, K. and S. J. Young. 1990. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 4(1):35–56. find
  63. Lease, Matthew and Eugene Charniak. 2005. Parsing biomedical literature. In Proceedings of the Second International Joint Conference on Natural Language Processing (IJCNLP-05), Jeju Island, Korea. find
  64. Levy, Roger and Christopher Manning. 2004. Deep dependencies from context-free statistical parsers: Correcting the surface dependency approximation. In Proceedings of the 41st Meeting of the ACL, pages 328–335, Barcelona, Spain. find
  65. Malouf, Robert. 2002. A comparison of algorithms for maximum entropy parameter estimation. In Proceedings of the Sixth Workshop on Natural Language Learning, pages 49–55, Taipei, Taiwan. find
  66. Malouf, Robert and Gertjan van Noord. 2004. Wide coverage parsing with stochastic attribute value grammars. In Proceedings of the IJCNLP-04 Workshop: Beyond Shallow Analyses—Formalisms and Statistical Modeling for Deep Analyses, Hainan Island, China. find
  67. Marcus, Mitchell, Beatrice Santorini, and Mary Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
  68. Miyao, Yusuke, Takashi Ninomiya, and Jun’ichi Tsujii. 2004. Corpus-oriented grammar development for acquiring a head-driven phrase structure grammar from the Penn Treebank. In Proceedings of the First International Joint Conference on Natural Language Processing (IJCNLP-04), pages 684–693, Hainan Is… find
  69. Miyao, Yusuke and Jun’ichi Tsujii. 2002. Maximum entropy estimation for feature forests. In Proceedings of the Human Language Technology Conference, San Diego, CA. find
  70. Miyao, Yusuke and Jun’ichi Tsujii. 2003a. A model of syntactic disambiguation based on lexicalized grammars. In Proceedings of the Seventh Conference on Natural Language Learning (CoNLL), pages 1–8, Edmonton, Canada. find
  71. Miyao, Yusuke and Jun’ichi Tsujii. 2003b. Probabilistic modeling of argument structures including non-local dependencies. In Proceedings of the Conference on Recent Advances in Natural Language Processing (RANLP), pages 285–291, Borovets, Bulgaria. find
  72. Miyao, Yusuke and Jun’ichi Tsujii. 2004. Deep linguistic analysis for the accurate identification of predicate-argument relations. In Proceedings of COLING-2004, pages 1392–1397, Geneva, Switzerland. find
  73. Miyao, Yusuke and Jun’ichi Tsujii. 2005. Probabilistic disambiguation models for wide-coverage HPSG parsing. In Proceedings of the 43rd meeting of the ACL, pages 83–90, University of Michigan, Ann Arbor. find our card
  74. Moortgat, Michael. 1997. Categorial type logics. In Johan van Benthem and Alice ter Meulen, editors, Handbook of Logic and Language. Elsevier, Amsterdam, and The MIT Press, Cambridge, MA, pages 93–177. find
  75. Nasr, Alexis and Owen Rambow. 2004. Supertagging and full parsing. In Proceedings of the TAG+7 Workshop, Vancouver, Canada. find
  76. Nocedal, Jorge and Stephen J. Wright. 1999. Numerical Optimization. Springer, New York, NY. find
  77. Osborne, Miles. 2000. Estimation of stochastic attribute-value grammars using an informative sample. In Proceedings of the 18th International Conference on Computational Linguistics, pages 586–592, Saarbrücken, Germany. find
  78. Osborne, Miles and Ted Briscoe. 1997. Learning stochastic categorial grammars. In Proceedings of the ACL CoNLL Workshop, pages 80–87, Madrid, Spain. find
  79. Palmer, Martha, Dan Gildea, and Paul Kingsbury. 2005. The Proposition Bank: A corpus annotated with semantic roles. Computational Linguistics, 31(1):71–105. find
  80. Preiss, Judita. 2003. Using grammatical relations to compare parsers. In Proceedings of the 10th Meeting of the EACL, pages 291–298, Budapest, Hungary. find
  81. Prins, Robbert and Gertjan van Noord. 2003. Reinforcing parser preferences through tagging. Traitement Automatique des Langues, 44(3):121–139. find
  82. Ratnaparkhi, Adwait. 1996. A maximum entropy part-of-speech tagger. In Proceedings of the EMNLP Conference, pages 133–142, Philadelphia, PA. find
  83. Ratnaparkhi, Adwait. 1998. Maximum Entropy Models for Natural Language Ambiguity Resolution. Ph.D. thesis, University of Pennsylvania. find
  84. Ratnaparkhi, Adwait. 1999. Learning to parse natural language with maximum entropy models. Machine Learning, 34(1–3):151–175. find
  85. Ratnaparkhi, Adwait, Salim Roukos, and Todd Ward. 1994. A maximum entropy model for parsing. In Proceedings of the International Conference on Spoken Language Processing, pages 803–806, Yokohama, Japan. find
  86. Riezler, Stefan, 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
  87. Sagae, Kenji and Alon Lavie. 2005. A classifier-based parser with linear run-time complexity. In Proceedings of the 9th International Workshop on Parsing Technologies, pages 125–132, Vancouver, Canada. find
  88. Sarkar, Anoop and Aravind Joshi. 2003. Tree-adjoining grammars and its application to statistical parsing. In Rens Bod, Remko Scha, and Khalil Sima’an, editors, Data-oriented parsing. CSLI Publications, Stanford, CA. find
  89. Sha, Fei and Fernando Pereira. 2003. Shallow parsing with conditional random fields. In Proceedings of the HLT/NAACL conference, pages 213–220, Edmonton, Canada. find
  90. Steedman, Mark. 1996. Surface Structure and Interpretation. The MIT Press, Cambridge, MA. find
  91. Steedman, Mark. 2000. The Syntactic Process. The MIT Press, Cambridge, MA. find
  92. Steedman, Mark, Steven Baker, Stephen Clark, Jeremiah Crim, Julia Hockenmaier, Rebecca Hwa, Miles Osborne, Paul Ruhlen, and Anoop Sarkar. 2002. Semi-supervised training for statistical parsing: Final report. Technical Report CLSP WS-02, Center for Language and Speech Processing, Johns Hopkins Univer… find
  93. Taskar, B., D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proceedings of the EMNLP Conference, pages 1–8, Barcelona, Spain. find
  94. Toutanova, Kristina, 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
  95. Toutanova, Kristina, Penka Markova, and Christopher Manning. 2004. The leaf projection path view of parse trees: Exploring string kernels for HPSG parse selection. In Proceedings of the EMNLP conference, pages 166–173, Barcelona, Spain. find
  96. Watkinson, Stephen and Suresh Manandhar. 2001. Acquisition of large categorial grammar lexicons. In Proceedings of the Conference of the Pacific Association for Computational Linguistics (PACLING-01), Kitakyushu, Japan. find
  97. Watson, Rebecca, John Carroll, and E. J. Briscoe. 2005. Efficient extraction of grammatical relations. In Proceedings of the 9th International Workshop on Parsing Technologies, pages 160–170, Vancouver, Canada. find
  98. Wood, Mary McGee. 1993. Categorial Grammars. Routledge, London. find
  99. Xia, Fei, Martha Palmer, and Aravind Joshi. 2000. A uniform method of grammar extraction and its applications. In Proceedings of the EMNLP Conference, pages 53–62, Hong Kong. find
  100. Younger, D. 1967. Recognition and parsing of context-free languages in time n 3 . Information and Control, 10(2):189–208. find
  101. Zettlemoyer, Luke S. and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, pages 658–666, Edinburgh, UK. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/nlpgap-2007-clark-wide-coverage-efficient-statistical-parsing/