Elamur Research⌕
☰
home / papers / 2007 / Dependency Parsing and Domain Adaptation with LR Models and Parser Ensembles

Dependency Parsing and Domain Adaptation with LR Models and Parser Ensembles

Summary

Sagae and Tsujii present the system they entered in the two tracks of the CoNLL 2007 shared task: multilingual dependency parsing across ten treebanks, and domain adaptation from Wall Street Journal (Penn Treebank) dependencies to biomedical and chemical text. The core parser adapts the classic LR shift-reduce algorithm. Instead of an LR table derived from a grammar, a classifier chooses actions using features from the top stack items and upcoming input tokens. A best-first search over action probabilities makes it a probabilistic, GLR-like parser, and pseudo-projective transformations handle non-projective trees.

For the multilingual track, three differently built models per language are merged by maximum-spanning-tree voting. For domain adaptation, two dissimilar models parse unlabeled target-domain text, and only sentences where they produce exactly the same analysis are added to the training data before retraining.

The system ranked first in domain adaptation (LAS 81.06), beating even the open-track results, and came within 0.43 points of the best multilingual average (79.89). This shows that simple ensembles and agreement-based self-training are highly effective.

Key points

  • Multilingual ensemble. Each language gets three LR models: forward MaxEnt, backward MaxEnt (input reversed), and an SVM model with a degree-2 polynomial kernel. The SVM model ran deterministically because Platt-scaled probabilities brought no gain. The three outputs are combined by unweighted MST voting after deprojectivization.
  • Shared settings. All ten languages used identical features and meta-parameters. Non-projectivity was handled with Nivre and Nilsson's PATH scheme, chosen because it keeps the number of dependency label types from growing too much.
  • Agreement as a quality signal. On development data, sentences where the forward MaxEnt and backward SVM models agreed reached about 90+ LAS, while each model alone scored roughly 78–79.
  • Domain adaptation gains. About 200k words of agreed-upon target-domain parses were added to the training set. This raised development LAS to 82.1, and the final test scores were LAS 81.06 and UAS 83.42 (closed track). The multilingual ensemble, without any unlabeled data, reached 81.9 on the same development set.
  • Turkish and parsing direction. In Turkish, over 80% of heads lie to the right of their dependents. Backward models clearly outperformed forward ones there, and adding a backward SVM model after submission raised the development combination score from 75.8 to 77.9.

Interesting ideas

  • I1. Cheap diversity for ensembles. Variety can come from the same algorithm simply by changing the learner or reversing the input sentence. This makes ensembling practical whenever only one parser implementation is available.
  • I2. Agreement-filtered self-training. Automatically parsed sentences are kept only when two dissimilar models produce identical trees. This yields high-precision pseudo-labels for a new domain without any annotation, and the idea could transfer to low-resource languages or other structured prediction tasks.
  • I3. Matching direction to head position. Checking whether heads in a treebank tend to sit left or right of their dependents can guide the choice of parsing direction. Strongly head-final languages benefit from processing that builds structure early instead of waiting until most of the input is consumed.
  • I4. Classifier in place of an LR table. A learned classifier replaces the grammar-derived table, and a best-first heap over action-probability products upgrades a greedy shift-reduce parser to a probabilistic search with little extra machinery.
  • I5. A single ensemble for multiple goals. The same ensemble that boosts multilingual accuracy also adapted well across domains on its own. Ensembling is therefore a reasonable robustness baseline before trying dedicated adaptation methods.

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

Topics: Dependency parsing · Multilingual & cross-lingual NLP

Institutions

🎓The University of TokyoTokyo · Japan31 works · 7 442 citations

Cite

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

@inproceedings{sagae2007dependency,
  title = {{Dependency Parsing and Domain Adaptation with LR Models and Parser Ensembles}},
  author = {Sagae, Kenji and Tsujii, Jun'ichi},
  booktitle = {Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL)},
  year = {2007},
  url = {https://aclanthology.org/D07-1111/}
}

References

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

  1. A. Abeillé, editor. 2003. Treebanks: Building and Using Parsed Corpora. Kluwer. find
  2. A. Berger, S. A. Della Pietra, and V. J. Della Pietra. 1996. A maximum entropy approach to naturallanguage processing. Computational Linguistics, 22(1):39–71. find
  3. I. Aduriz, M. J. Aranzabe, J. M. Arriola, A. Atutxa, A. Diaz de Ilarraza, A. Garmendia and M. Oronoz. 2003. Construction of a Basque Dependency Treebank. In Proc. of the 2nd Workshop on Treebanks and Linguistic Theories (TLT), pages 201–204. find
  4. A. Böhmová, J. Hajic, E. Hajicová and B. Hladká. 2003. The PDT: a 3-level annotation scenario. In Abeillé (2003), chapter 7, 103–127. find
  5. E. Briscoe and J. Carroll. 1993. Generalized Probabilistic LR Parsing of Natural Language (Corpora) with Unification-Based Grammars. In Computational Linguistics, 19(1), pages 25-59. find
  6. R. Brown. 1973. A First Language: The Early Stages. Harvard University Press. find
  7. S. Buchholz and E. Marsi. 2006. CoNLL-X Shared Task on Multilingual Dependency Parsing. In Proc. of the Tenth Conference on Computational Natural Language Learning (CoNLL-X). New York, NY. find our card
  8. K. Chen, C. Luo, M. Chang, F. Chen, C. Chen, C. Huang and Z. Gao. 2003. find
  9. Sinica Treebank: Design Criteria, Representational Issues and Implementation. In Abeillé (2003), chapter 13, pages 231–248. find
  10. D. Csendes, J. Csirik, T. Gyimóthy, and A. Kocsor. 2005. The Szeged Treebank. Springer. find
  11. W. Daelemans and A. Van den Bosch. 2005. Memory-based language processing. Cambridge University Press. find
  12. J. Hajic, O. Smrz, P. Zemánek, J. Snaidauf and E. Beska. 2004. Prague Arabic Dependency Treebank: Development in Data and Tools. In Proc. of the NEMLAR Intern. Conf. on Arabic Language Resources and Tools, pages 110–117. find
  13. Johansson and P. Nugues. 2007. Extended constituent-to-dependency conversion for English. In Proc. of the 16th Nordic Conference on Computational Linguistics (NODALIDA). find our card
  14. J. Kazama, and J. Tsujii. 2003. Evaluation and extension of maximum entropy models with inequality constraints. In Proceedings of EMNLP 2003. find
  15. D. Knuth. 1965. On the translation of languages from left to right, Information and Control 8, 607-639. find
  16. S. Kulick, A. Bies, M. Liberman, M. Mandel, R. Mc-Donald, M. Palmer, A. Schein, and L. Ungar. 2004. Integrated annotation for biomedical information extraction. In Proc. of the Human Language Technology Conference and the Annual Meeting of the North American Chapter of the Association for Computatio… find
  17. B. MacWhinney. 2000. The CHILDES Project: Tools for Analyzing Talk. Lawrence Erlbaum. find
  18. R. McDonald, K.Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. of the 43rd Annual Meeting of the Association for Computational Linguistics, 2005 find our card
  19. M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of English: the Penn Treebank. Computational Linguistics, 19(2):313–330. find our card
  20. M. A. Martí, M. Taulé, L. Màrquez and M. Bertran. 2007. CESS-ECE: A Multilingual and Multilevel Annotated Corpus. Available for download from: http://www.lsi.upc.edu/~mbertran/cess-ece/. ↗
  21. S. Montemagni, F. Barsotti, M. Battista, N. Calzolari, O. Corazzari, A. Lenci, A. Zampolli, F. Fanciulli, M. Massetani, R. Raffaelli, R. Basili, M. T. Pazienza, D. Saracino, F. Zanzotto, N. Nana, F. Pianesi, and R. Delmonte. 2003. Building the Italian Syntactic-Semantic Treebank. In Abeillé (2003),… find
  22. J. Nivre. 2003. An efficient algorithm for dependency parsing. In Proc. of the Eighth International Workshop on Parsing Technologies (IWPT’03). Nancy, France. find
  23. J. Nivre, and J. Nilsson. 2005. Pseudo-Projective Dependency Parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), 99-106. Ann Arbor, MI. find our card
  24. J. Nivre, J. Hall, S. Kübler, R. McDonald, J. Nilsson, S. Riedel, and D. Yuret. 2007. find
  25. The CoNLL 2007 shared task on dependency parsing. In Proc. of the CoNLL 2007 Shared Task. Joint Conf. on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). find our card
  26. K. Oflazer, B. Say, D. Zeynep Hakkani-Tür, and G. Tür. 2003. Building a Turkish treebank. In Abeillé (2003), chapter 15, pages 261–277. find
  27. J. Platt. 1999. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. In Advances in Large Margin Classiers, MIT Press. find
  28. P. Prokopidis, E. Desypri, M. Koutsombogera, H. Papageorgiou, and S. Piperidis. 2005. Theoretical and practical issues in the construction of a Greek depen- dency treebank. In Proc. of the 4th Workshop on Treebanks and Linguistic Theories (TLT), pages 149–160. find
  29. A. Ratnaparkhi. 1997. A linear observed time statistical parser based on maximum entropy models. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing. find
  30. Providence, RI K. Sagae, and A. Lavie. 2006. A best-first probabilistic shift-reduce parser. Proceedings of the 43rd Meeting of the Association for Computational Linguistics - posters (ACL'06). Sydney, Australia. find
  31. K. Sagae, and A. Lavie. 2006a. Parser combination by reparsing. Proceedings of the 2006 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics - short papers (HLT-NAACL'06). New York, NY. find our card
  32. M. Tomita. 1987. An efficient augmented context-free parsing algorithm. Computational Linguistics, 13:31– 46. find
  33. M. Tomita. 1990. The generalized LR parser/compiler - version 8.4. In Proceedings of the International Conference on Computational Linguistics (COLING’90), pages 59–63. Helsinki, Finland. find
  34. V. N. Vapnik. 1995. The Nature of Statistical Learning Theory. Springer-Verlag. find
  35. H. Yamada, and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the Eighth International Workshop on Parsing Technologies (IWPT’03). Nancy, France. find our card
  36. D. Zeman, Z. Žabokrtský. 2005. Improving Parsing Accuracy by Combining Diverse Dependency Parsers. In Proceedings of the International Workshop on Parsing Technologies (IWPT 2005). Vancouver, British Columbia. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/sagae-2007-dependency-parsing-domain-adaptation-lr/