Mova0.5 pre-release⌕
☰
home / docs / papers / English / Feature Forest Models for Probabilistic HPSG Parsing

Feature Forest Models for Probabilistic HPSG Parsing

What it is about

Probabilistic models for lexicalized grammars are hard because their structures are typed feature structures, not trees or lattices. The paper proposes feature forest models: maximum entropy models over packed forests, estimated by dynamic programming without unpacking the forest and without an independence assumption. It also shows how HPSG syntax and predicate-argument structure are encoded as forests. On Penn Treebank section 23 (sentences under 40 words) the parser covers 99.7% of the sentences, with labelled precision and recall of 87.69% and 87.16% and sentence accuracy of 39.2%. Covered sentences score about 2.5 points higher than the overall F-score, and uncovered ones more than 10 points lower.

Ideas

For Mova

The code is en/src/parse.rs and the dictionary in en/src/lexgen.rs; the chapters are 10. Word classes and 13-verbs.md. The paper is HPSG with predicate-argument output, not UD, and its data are PTB-based, 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.2008.34.1.35

@article{miyao2008feature,
  title = {{Feature Forest Models for Probabilistic HPSG Parsing}},
  author = {Miyao, Yusuke and Tsujii, Jun'ichi},
  journal = {Computational Linguistics},
  year = {2008},
  doi = {10.1162/coli.2008.34.1.35},
  url = {https://doi.org/10.1162/coli.2008.34.1.35}
}

References

83 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 P. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23(4):597–618. find
  2. Baker, James K. 1979. Trainable grammars for speech recognition. In Jared J. Wolf and Dennis H. Klatt, editors, Speech Communication Papers Presented at the 97th Meeting of the Acoustical Society of America. MIT Press, Cambridge, MA, pages 547–550. find
  3. Baldridge, Jason and Miles Osborne. 2003. Active learning for HPSG parse selection. In Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003, pages 17–24, Edmonton, Canada. find
  4. Berger, Adam L., Stephen A. Della Pietra, and Vincent J. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22(1):39–71. find
  5. Burke, Michael, Aoife Cahill, Ruth O’Donovan, Josef van Genabith, and Andy Way. 2004. Treebank-based acquisition of wide-coverage, probabilistic LFG resources: Project overview, results and evaluation. In Proceedings of the IJCNLP-04 Workshop “Beyond Shallow Analyses”, Hainan Island. Available at ww… find
  6. Carpenter, Bob. 1992. The Logic of Typed Feature Structures. Cambridge University Press, Cambridge, England. find
  7. Carroll, John and Stephan Oepen. 2005. High efficiency realization for a wide-coverage unification grammar. In Proceedings of the 2nd International Joint Conference on Natural Language Processing (IJCNLP-05), pages 165–176, Jeju Island. find
  8. Charniak, Eugene. 2000. A maximum-entropy-inspired parser. In Proceedings of the First Conference on North American Chapter of the Association for Computational Linguistics (NAACL 2000), pages 132–139, Seattle, WA. find
  9. Charniak, Eugene and Mark Johnson. 2005. Coarse-to-fine n-best parsing and MaxEnt discriminative reranking. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL 2005), pages 173–180, Ann Arbor, MI. find our card
  10. Chen, Stanley and Ronald Rosenfeld. 1999a. A Gaussian prior for smoothing maximum entropy models. Technical Report CMUCS-99-108, Carnegie Mellon University. find
  11. Chen, Stanley F. and Ronald Rosenfeld. 1999b. Efficient sampling and feature selection in whole sentence maximum entropy language models. In Proceedings of the 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing, pages 549–552, Phoenix, AZ. find
  12. Chiang, David. 2003. Mildly context sensitive grammars for estimating maximum entropy parsing models. In Proceedings of the 8th Conference on Formal Grammar, pages 19–31, Vienna. find
  13. Chun, Hong-Woo. 2007. Mining Literature for Disease-Gene Relations. Ph.D. thesis, University of Tokyo. find
  14. Clark, Stephen and James R. Curran. 2003. Log-linear models for wide-coverage CCG parsing. In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing (EMNLP 2003), pages 97–104, Sapporo. find
  15. Clark, Stephen and James R. Curran. 2004a. The importance of supertagging for wide-coverage CCG parsing. In Proceedings of the 20th International Conference on Computational Linguistics (COLING 2004), pages 282–288, Geneva. find our card
  16. Clark, Stephen and James R. Curran. 2004b. Parsing the WSJ using CCG and log-linear models. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL 2004), pages 104–111, Barcelona. find
  17. Clark, Stephen, Julia Hockenmaier, and Mark Steedman. 2002. Building deep dependency structures with a wide-coverage CCG parser. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL 2002), pages 327–334, Philadephia. find
  18. Cohen, Paul R. 1995. Empirical Methods for Artificial Intelligence. The MIT Press, Cambridge, MA. find
  19. Collins, Michael. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics (ACL’97), pages 16–23, Madrid. find
  20. Collins, Michael. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  21. Collins, Michael. 2000. Discriminative reranking for natural language parsing. In Proceedings of the Seventeenth International Conference on Machine Learning, pages 175–182, Palo Alto, CA. find our card
  22. Collins, Michael. 2003. Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4):589–637. find our card
  23. Copestake, Ann, Dan Flickinger, Rob Malouf, Susanne Riehemann, and Ivan Sag. 1995. Translation using minimal recursion semantics. In Proceedings of the Sixth International Conference on Theoretical and Methodological Issues in Machine Translation (TMI95), pages 15–32, Leuven. find our card
  24. Copestake, Ann, Dan Flickinger, Ivan A. Sag, and Carl Pollard. 2006. Minimal recursion semantics: An introduction. Research on Language and Computation, 3(4):281–332. find
  25. Darroch, J. N. and D. Ratcliff. 1972. Generalized iterative scaling for log-linear models. The Annals of Mathematical Statistics, 43(5):1470–1480. find
  26. Della Pietra, Stephen, Vincent Della Pietra, and John Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(4):380–393. find
  27. Geman, Stuart and Mark Johnson. 2002. Dynamic programming for parsing and estimation of stochastic unification-based grammars. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL 2002), pages 279–286, Philadelphia, PA. find
  28. Gildea, Daniel. 2001. Corpus variation and parser performance. In Proceedings of the 2001 Conference on Empirical Methods in Natural Language Processing (EMNLP 2001), pages 167–202, Pittsburgh, PA. find our card
  29. Hockenmaier, Julia. 2003. Parsing with generative models of predicate-argument structure. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics (ACL 2003), pages 359–366, Sapporo. find
  30. Hockenmaier, Julia and Mark Steedman. 2002. Acquiring compact lexicalized grammars from a cleaner treebank. In Proceedings of the Third International Conference on Language Resources and Evaluation (LREC-2002), pages 1974–1981, Las Palmas. find
  31. Johnson, Mark, Stuart Geman, Stephen Canon, Zhiyi Chi, and Stefan Riezler. 1999. Estimators for stochastic “unification-based” grammars. In Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (ACL’99), pages 535–541, College Park, Maryland. find
  32. Johnson, Mark and Stefan Riezler. 2000. Exploiting auxiliary distributions in stochastic unification-based grammars. In Proceedings of the First Conference on North American Chapter of the Association for Computational Linguistics, pages 154–161, Seattle, WA. find
  33. Kameya, Yoshitaka and Taisuke Sato. 2000. Efficient EM learning with tabulation for parameterized logic programs. In Proceedings of the 1st International Conference on Computational Logic (CL2000), volume 1861 of Lecture Notes in Artificial Intelligence (LNAI), pages 269–294, Imperial College, Londo… find
  34. Kaplan, Ronald M., 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 North American Chapter of the Association for Computati… find
  35. Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning 2001, pages 282–289, Williams College, Williamstown, MA. find
  36. Makino, Takaki, Yusuke Miyao, Kentaro Torisawa, and Jun’ichi Tsujii. 2002. Native-code compilation of feature structures. In Stephen Oepen, Dan Flickinger, Jun’ichi Tsujii, and Hans Uszkoreit, editors, Collaborative Language Engineering: A Case Study in Efficient Grammar-based Parsing. CSLI Publicat… find
  37. Malouf, Robert. 2002. A comparison of algorithms for maximum entropy parameter estimation. In Proceedings of the Sixth Conference on Natural Language Learning (CoNLL-2002), pages 1–7, Taipei. find
  38. 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”, Hainan Island. find
  39. Marcus, Mitchell, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. 1994. The Penn Treebank: Annotating predicate argument structure. In Proceedings of the Workshop on Human Language Technology, pages 114–119, Plainsboro, NJ. find our card
  40. Maxwell John T., III and Ronald M. Kaplan. 1995. A method for disjunctive constraint satisfaction. In Mary Dalrymple, Ronald M. Kaplan, John T. Maxwell, III, and Annie Zaenen, editors, Formal Issues in Lexical-Functional Grammar, number 47 in CSLI Lecture Notes Series. CSLI Publications, Palo Alto,… find
  41. McCallum, Andrew and Wei Li. 2003. Early results for named entity recognition with conditional random fields, feature induction and web-enhanced lexicons. In Proceedings of the 7th Conference on Natural Language Learning (CoNLL), pages 188–191, Edmonton. find
  42. McCallum, Andrew, Khashayar Rohanimanesh, and Charles Sutton. 2003. Dynamic conditional random fields for jointly labeling multiple sequences. In Proceedings of the Workshop on Syntax, Semantics, Statistics at the 16th Annual Conference on Neural Information Processing Systems, Vancouver. Available… find
  43. Miyao, Yusuke, Takashi Ninomiya, and Jun’ichi Tsujii. 2003. Probabilistic modeling of argument structures including non-local dependencies. In Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP 2003), pages 285–291, Borovets. find
  44. Miyao, Yusuke, Takashi Ninomiya, and Jun’ichi Tsujii. 2005. Corpus-oriented grammar development for acquiring a head-driven phrase structure grammar from the Penn Treebank. In Natural Language Processing - IJCNLP 2004, pages 684–693, Hainan Island. find
  45. Miyao, Yusuke, Tomoko Ohta, Katsuya Masuda, Yoshimasa Tsuruoka, Kazuhiro Yoshida, Takashi Ninomiya, and Jun’ichi Tsujii. 2006. Semantic retrieval for the accurate identification of relational concepts in massive textbases. In Proceedings of the Joint Conference of the 21st International Conference o… find
  46. Miyao, Yusuke and Jun’ichi Tsujii. 2002. Maximum entropy estimation for feature forests. In Proceedings of the Human Language Technology Conference (HLT-2002), pages 292–297, San Diego, CA. find
  47. Miyao, Yusuke and Jun’ichi Tsujii. 2003. A model of syntactic disambiguation based on lexicalized grammars. In Proceedings of the Seventh Conference on Computational Natural Language Learning (CoNLL-2003), pages 1–8, Edmonton. find
  48. Miyao, Yusuke and Jun’ichi Tsujii. 2005. Probabilistic disambiguation models for wide-coverage HPSG parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL 2005), pages 83–90, Ann Arbor, MI. find our card
  49. Nakanishi, Hiroko, Yusuke Miyao, and Jun’ichi Tsujii. 2005. Probabilistic models for disambiguation of an HPSG-based chart generator. In Proceedings of the 9th International Workshop on Parsing Technologies (IWPT 2005), pages 93–102, Vancouver. find
  50. Ninomiya, Takashi, Yoshimasa Tsuruoka, Yusuke Miyao, and Jun’ichi Tsujii. 2005. Efficacy of beam thresholding, unification filtering and hybrid parsing in probabilistic HPSG parsing. In Proceedings of the 9th International Workshop on Parsing Technologies, pages 103–114, Vancouver. find
  51. Nocedal, Jorge. 1980. Updating quasi-Newton matrices with limited storage. Mathematics of Computation, 35:773–782. find
  52. Nocedal, Jorge and Stephen J. Wright. 1999. Numerical Optimization. Springer, New York. find
  53. Oepen, Stephan and John Carroll. 2000. Ambiguity packing in constraint-based parsing: practical results. In Proceedings of the First Conference of the North American Chapter of the Association for Computational Linguistics (NAACL 2000), pages 162–169, Seattle, WA. find
  54. Oepen, Stephan, Dan Flickinger, Jun’ichi Tsujii, and Hans Uszkoreit, editors. 2002. Collaborative Language Engineering: A Case Study in Efficient Grammar-Based Processing. CSLI Publications, Palo Alto, CA. find
  55. Oepen, Stephan, Kristina Toutanova, Stuart Shieber, Christopher Manning, Dan Flickinger, and Thorsten Brants. 2002. The LinGO Redwoods treebank motivation and preliminary applications. In Proceedings of the 19th International Conference on Computational Linguistics (COLING 2002), volume 2, pages 1–5… find our card
  56. Osborne, Miles. 2000. Estimation of stochastic attribute-value grammar using an informative sample. In Proceedings of the 18th International Conference on Computational Linguistics (COLING 2000), volume 1, pages 586–592, Saarbrücken. find
  57. Peng, Fuchun and Andrew McCallum. 2004. Accurate information extraction from research papers using conditional random fields. In Proceedings of Human Language Technology Conference and North American Chapter of the Association for Computational Linguistics (HLT/ NAACL-04), pages 329–336, Boston, MA. find
  58. Pinto, David, Andrew McCallum, Xen Lee, and W. Bruce Croft. 2003. Table extraction using conditional random fields. In Proceedings of the 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2003), pages 235–242, Toronto. find
  59. Pollard, Carl and Ivan A. Sag. 1994. Head-Driven Phrase Structure Grammar. University of Chicago Press, Chicago, IL. find
  60. 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 Annual Meeting of the Association for Computational… find
  61. Riezler, Stefan, Detlef Prescher, Jonas Kuhn, and Mark Johnson. 2000. Lexicalized stochastic modeling of constraint-based grammars using log-linear measures and EM training. In Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics (ACL 2000), pages 480–487, Hong Kon… find
  62. Riezler, Stefan and Alexander Vasserman. 2004. Incremental feature selection and l 1 regularization for relaxed maximum-entropy modeling. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP 2004), pages 174–181, Barcelona. find
  63. Roark, Brian, Murat Saraclar, Michael Collins, and Mark Johnson. 2004. Discriminative language modeling with conditional random fields and the perceptron algorithm. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL 2004), pages 47–54, Barcelona. find
  64. Rosenfeld, Ronald. 1997. A whole sentence maximum entropy language model. In Proceedings of the IEEE Workshop on Automatic Speech Recognition and Understanding, pages 230–237, Santa Barbara, CA. find
  65. Sag, Ivan A., Thomas Wasow, and Emily M. Bender. 2003. Syntactic Theory: A Formal Introduction. Number 152 in CSLI Lecture Notes. CSLI Publications, Standford, CA. find
  66. Sarawagi, Sunita and William W. Cohen. 2004. Semi-Markov conditional random fields for information extraction. In Proceedings of the 18th Annual Conference on Neural Information Processing Systems, pages 1185–1192, Vancouver. find
  67. Sato, Taisuke. 2005. A generic approach to em learning for symbolic-statistical models. In Proceedings of the 4th Learning Language in Logic Workshop (LLL05), pages 21–28, Bonn. find
  68. Sato, Taisuke and Yoshitaka Kameya. 1997. PRISM: a language for symbolic-statistical modeling. In Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI ’97), pages 1330–1335, Nagoya. find
  69. Sato, Taisuke and Yoshitaka Kameya. 2001. Parameter learning of logic programs for symbolic-statistical modeling. Journal of Artificial Intelligence Research, 15:391–454. find
  70. Settles, Burr. 2004. Biomedical named entity recognition using conditional random fields and rich feature sets. In Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications (NLPBA), pages 104–107, Geneva. find
  71. Sha, Fei and Fernando Pereira. 2003. Shallow parsing with conditional random fields. In Proceedings of the 2003 Human Language Technology Conference and North American Chapter of the Association for Computational Linguistics (HLT-NAACL 2003), pages 213–220, Edmonton. find
  72. Shieber, Stuart M. 1985. Using restriction to extend parsing algorithms for complex-feature-based formalisms. In Proceedings of the 23rd Annual Meeting on Association for Computational Linguistics, pages 145–152, Chicago, IL. find
  73. Sutton, Charles, Khashayar Rohanimanesh, and Andrew McCallum. 2004. Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence data. In Proceedings of the 21st International Conference on Machine Learning (ICML 2004), pages 783–790, Alberta. find
  74. Taskar, Ben, Dan Klein, Michael Collins, Daphne Koller, and Chris Manning. 2004. Max-margin parsing. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP 2004), pages 1–8, Barcelona. find
  75. Toutanova, Kristina and Christopher Manning. 2002. Feature selection for a rich HPSG grammar using decision trees. In Proceedings of the Sixth Conference on Natural Language Lerning (CoNLL-2002), pages 77–83, Taipei. find
  76. 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 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP 2004), pages 166–173, Barcelona. find
  77. Tsujii Laboratory. 2004. Enju—A practical HPSG parser. Available at http://www. tsujii.is.s.u-tokyo.ac.jp/enju/. find
  78. Tsuruoka, Yoshimasa, Yusuke Miyao, and Jun’ichi Tsujii. 2004. Towards efficient probabilistic HPSG parsing: Integrating semantic and syntatic preference to guide the parsing. In Proceedings of the IJCNLP-04 Workshop “Beyond Shallow Analyses”, Hainan Island. Available at www.tsujii.is.s.u-tokyo.ac.jp… find
  79. Tsuruoka, Yoshimasa and Jun’ichi Tsujii. 2005. Bidirectional inference with the easiest-first strategy for tagging sequence data. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP 2005), pages 467–474, Vancouver. find
  80. Vapnik, Vladimir N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York. find
  81. Vijay-Shanker, K., David J. Weir, and Aravind K. Joshi. 1987. Characterizing structural descriptions produced by various grammatical formalisms. In Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics, pages 104–111, Palo Alto, CA. find
  82. Weir, David J. 1988. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylvania. find
  83. Yakushiji, Akane, Yusuke Miyao, Tomoko Ohta, Yuka Tateisi, and Jun’ichi Tsujii. 2006. Automatic construction of predicate-argument structure patterns for biomedical information extraction. In Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 2… find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/cl-2008-miyao-feature-forest-models-probabilistic-hpsg/