Mova0.5 pre-release⌕
☰
home / docs / papers / Modern Hebrew / A Graph-based Lattice Dependency Parser for Joint Morphological Segmentation and Syntactic Analysis

A Graph-based Lattice Dependency Parser for Joint Morphological Segmentation and Syntactic Analysis

What it is about

Turkish and Hebrew words are ambiguous in their segmentation, and a pipeline (segment, tag, parse) loses information that syntax could resolve. The authors parse over a morphological lattice, so the path (the segmentation) and the dependency tree are chosen together. Two models are coupled by dual decomposition (AD3): a bigram model over segments and a graph-based arc model. An agreement constraint forces tokens off the path to attach to ROOT with a special NOREL label, so the output stays a tree. Second-order sibling and grandparent features are added. Evaluation uses Turkish (METU-Sabancı treebank) and Hebrew (SPMRL 2014), with strict token-level precision and recall: a token must match its gold segmentation and its head. The joint parser beats three pipeline systems on both languages. On Hebrew the joint model's gain is mostly in recall, and the bigram disambiguator is still ahead in precision.

Ideas

For Mova

I1 goes into tools/hbo (segmenter to gparse) and 13. Biblical Hebrew in Mova: the tools. I2 is a baseline in tools/hbo. I3 is the evaluation in tools/hbo, and it applies to 11. Modern Hebrew in Universal Dependencies as well. The paper is NC: only the ideas are used, and no code or data are carried.

Topics: Dependency parsing

Cite

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

@article{seeker2015graph,
  title = {{A Graph-based Lattice Dependency Parser for Joint Morphological Segmentation and Syntactic Analysis}},
  author = {Seeker, Wolfgang and Çetinoğlu, Özlem},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.1162/tacl\_a\_00144},
  url = {https://doi.org/10.1162/tacl_a_00144}
}

References

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

  1. Miguel Almeida and Andre Martins. 2013. Fast and Robust Compressive Summarization with Dual Decomposition and Multi-Task Learning. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 196–206, Sofia, Bulgaria, August. Association for Computational Linguistics. find
  2. Mariana S. C. Almeida, Miguel B. Almeida, and André F. T. Martins. 2014. A Joint Model for Quotation Attribution and Coreference Resolution. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 39– 48, Gothenburg, Sweden, April. Association for Computational Linguistics. find
  3. Bernd Bohnet and Joakim Nivre. 2012. A Transition-Based System for Joint Part-of-Speech Tagging and Labeled Non-Projective Dependency Parsing. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1455– 1465, Jeju, South Korea. Association for Computational Linguistics. find
  4. Bernd Bohnet, Joakim Nivre, Igor Boguslavsky, Richrd Farkas, Filip Ginter, and Jan Haji. 2013. Joint Morphological and Syntactic Analysis for Richly Inflected Languages. Transactions of the Association for Computational Linguistics, 1:415–428. find
  5. Bernd Bohnet. 2009. Efficient Parsing of Syntactic and Semantic Dependency Structures. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL 2009): Shared Task, pages 67–72, Boulder, Colorado, June. Association for Computational Linguistics. find
  6. Bernd Bohnet. 2010. Very high accuracy and fast dependency parsing is not a contradiction. In Proceedings of the 23rd International Conference on Computational Linguistics, pages 89–97, Beijing, China. International Committee on Computational Linguistics. find
  7. Xavier Carreras. 2007. Experiments with a Higher-Order Projective Dependency Parser. In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, pages 957–961, Prague, Czech Republic, June. Association for Computational Linguistics. find
  8. Özlem Çetinoğlu and Jonas Kuhn. 2013. Towards Joint Morphological Analysis and Dependency Parsing of Turkish. In Proceedings of the Second International Conference on Dependency Linguistics (DepLing 2013), pages 23–32, Prague, Czech Republic, August. Charles University in Prague, Matfyzpress, Prague, Czech Republic. find
  9. Özlem Çetinoğlu. 2014. Turkish Treebank as a Gold Standard for Morphological Disambiguation and Its Influence on Parsing. In Nicoletta Calzolari (Conference Chair), Khalid Choukri, Thierry Declerck, Hrafn Loftsson, Bente Maegaard, Joseph Mariani, Asuncion Moreno, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Ninth International Conference on Language Resources and Evaluation (LREC’14), Reykjavik, Iceland, may. European Language Resources Association (ELRA). find
  10. Yoeng-Jin Chu and Tseng-Hong Liu. 1965. On the Shortest Arborescence of a Directed Graph. Scientia Sinica, 14(10):1396–1400. find
  11. Shay B. Cohen and Noah A. Smith. 2007. Joint morphological and syntactic disambiguation. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 208–217, Prague, Czech Republic. Association for Computational Linguistics. find
  12. Koby Crammer, Ofer Dekel, Shai Shalev-Shwartz, and Yoram Singer. 2003. Online passive-aggressive algorithms. In Proceedings of the 16th Annual Conference on Neural Information Processing Systems, volume 7, pages 1217–1224, Cambridge, Massachusetts, USA. MIT Press. find
  13. Dipanjan Das, André F. T. Martins, and Noah A. Smith. 2012. An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing with Constraints. In *SEM 2012: The First Joint Conference on Lexical and Computational Semantics – Volume 1: Proceedings of the main conference and the shared task, and Volume 2: Proceedings of the Sixth International Workshop on Semantic Evaluation (SemEval 2012), pages 209–217, Montréal, Canada, 7-8 June. Association for Computational Linguistics. find
  14. Jack Edmonds. 1967. Optimum Branchings. Journal of Research of the National Bureau of Standards, 71B(4):233–240. find
  15. Jason Eisner. 1997. Bilexical Grammars and a Cubic-Time Probabilistic Parser. In Proceedings of the 5th International Workshop on Parsing Technologies (IWPT), pages 54–65, MIT, Cambridge, MA, sep. find
  16. Gülşen Eryiğit and Kemal Oflazer. 2006. Statistical dependency parsing of Turkish. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics, pages 89–96, Trento, Italy. Association for Computational Linguistics. find
  17. Gülşen Eryiğit, Joakim Nivre, and Kemal Oflazer. 2008. Dependency Parsing of Turkish. Computational Linguistics, 34(3):357–389. find
  18. Gülşen Eryiğit, Tugay Ilbay, and Ozan Arkan Can. 2011. Multiword Expressions in Statistical Dependency Parsing. In Proc. of the SPMRL Workshop of IWPT, pages 45–55, Dublin, Ireland. find
  19. Gülşen Eryiğit. 2012. The Impact of Automatic Morphological Analysis & Disambiguation on Dependency Parsing of Turkish. In Nicoletta Calzolari, Khalid Choukri, Thierry Declerck, Mehmet Uğur Doğan, Bente Maegaard, Joseph Mariani, Jan Odijk, and Stelios Piperidis, editors, Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC-2012), pages 1960–1965, Istanbul, Turkey, May. European Language Resources Association (ELRA). ACL Anthology Identifier: L12-1056. ↗
  20. Yoav Freund and Robert E. Schapire. 1999. Large margin classification using the perceptron algorithm. Machine Learning, 37(3):277–296. find
  21. Yoav Goldberg and Michael Elhadad. 2009. Hebrew Dependency Parsing: Initial Results. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09), pages 129–133, Paris, France, October. Association for Computational Linguistics. find our card
  22. Yoav Goldberg and Michael Elhadad. 2010a. An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742–750, Los Angeles, California, June. Association for Computational Linguistics. find
  23. Yoav Goldberg and Michael Elhadad. 2010b. Easy-First Dependency Parsing of Modern Hebrew. In Proceedings of the NAACL HLT 2010 First Workshop on Statistical Parsing of Morphologically-Rich Languages, pages 103–107, Los Angeles, CA, USA, June. Association for Computational Linguistics. find our card
  24. Yoav Goldberg and Michael Elhadad. 2013. Word segmentation, unknown-word resolution, and morphological agreement in a hebrew parsing system. Computational Linguistics, 39(1):121–160. find our card
  25. Yoav Goldberg and Reut Tsarfaty. 2008. A single generative model for joint morphological segmentation and syntactic parsing. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics, pages 371–379, Columbus, Ohio. Association for Computational Linguistics. find
  26. Yoav Goldberg. 2011. Automatic Syntactic Processing of Modern Hebrew. Ph.D. thesis, Ben Gurion University, Beer Sheva, Israel. find
  27. Spence Green and Christopher D. Manning. 2010. Better Arabic Parsing: Baselines, Evaluations, and Analysis. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 394–402, Beijing, China, August. Coling 2010 Organizing Committee. find our card
  28. Jun Hatori, Takuya Matsuzaki, Yusuke Miyao, and Jun’ichi Tsujii. 2011. Incremental Joint POS Tagging and Dependency Parsing in Chinese. In Proceedings of 5th International Joint Conference on Natural Language Processing, pages 1216–1224, Chiang Mai, Thailand, November. Asian Federation of Natural Language Processing. find
  29. Jun Hatori, Takuya Matsuzaki, Yusuke Miyao, and Jun’ichi Tsujii. 2012. Incremental Joint Approach to Word Segmentation, POS Tagging, and Dependency Parsing in Chinese. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1045– 1053, Jeju Island, Korea, July. Association for Computational Linguistics. find
  30. Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag. 2010. Dual Decomposition for Parsing with Non-Projective Head Automata. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1288–1298, Cambridge, MA, October. Association for Computational Linguistics. find
  31. Zhongguo Li and Guodong Zhou. 2012. Unified Dependency Parsing of Chinese Morphological and Syntactic Structures. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 1445–1454, Jeju Island, Korea, July. Association for Computational Linguistics. find
  32. Zhenghua Li, Min Zhang, Wanxiang Che, Ting Liu, Wenliang Chen, and Haizhou Li. 2011. Joint Models for Chinese POS Tagging and Dependency Parsing. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1180–1191, Edinburgh, Scotland, UK, July. Association for Computational Linguistics. find
  33. Ji Ma, Tong Xiao, Jingbo Zhu, and Feiliang Ren. 2012. Easy-First Chinese POS Tagging and Dependency Parsing. In Proceedings of COLING 2012, pages 1731–1746, Mumbai, India, December. find
  34. The COLING 2012 Organizing Committee. find
  35. Andre Martins, Noah Smith, and Eric Xing. 2009. Concise Integer Linear Programming Formulations for Dependency Parsing. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 342–350, Suntec, Singapore, August. Association for Computational Linguistics. find
  36. Andre Martins, Noah Smith, Eric Xing, Pedro Aguiar, and Mario Figueiredo. 2010. Turbo Parsers: Dependency Parsing by Approximate Variational Inference. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 34– 44, Cambridge, MA, October. Association for Computational Linguistics. find
  37. Andre Martins, Mario Figueiredo, Pedro Aguiar, Noah Smith, and Eric Xing. 2011a. An Augmented Lagrangian Approach to Constrained MAP Inference. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference on Machine Learning (ICML-11), ICML ’11, pages 169–176, New York, NY, USA, June. ACM. find
  38. Andre Martins, Noah Smith, Mario Figueiredo, and Pedro Aguiar. 2011b. Dual Decomposition with Many Overlapping Components. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 238–249, Edinburgh, Scotland, UK., July. Association for Computational Linguistics. find
  39. Andre Martins, Miguel Almeida, and Noah A. Smith. 2013. Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 617–622, Sofia, Bulgaria, August. Association for Computational Linguistics. find our card
  40. André F. T. Martins, Mário A. T. Figueiredo, Pedro M. Q. Aguiar, Noah A. Smith, and Eric P. Xing. 2015. AD3: Alternating Directions Dual Decomposition for MAP Inference in Graphical Models. Journal of Machine Learning Research, 16:495–545. find
  41. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics, pages 81–88, Trento, Italy. Association for Computational Linguistics. find our card
  42. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajic. 2005. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523–530, Vancouver, British Columbia, Canada, October. Association for Computational Linguistics. find our card
  43. Saul B. Needleman and Christian D. Wunsch. 1970. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of molecular biology, 48(3):443–453. find
  44. Kemal Oflazer, Bilge Say, Dilek Zeynep Hakkani-Tür, and Gökhan Tür. 2003. Building a Turkish Treebank. In Anne Abeille, editor, Building and Exploiting Syntactically-annotated Corpora. Kluwer Academic Publishers, Dordrecht. find
  45. Kemal Oflazer. 1994. Two-level Description of Turkish Morphology. Literary and Linguistic Computing, 9(2):137–148. find
  46. Alexander M. Rush, David Sontag, Michael Collins, and Tommi Jaakkola. 2010. On Dual Decomposition and Linear Programming Relaxations for Natural Language Processing. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1–11, Cambridge, MA, October. Association for Computational Linguistics. find
  47. Haşim Sak, Tunga Güngör, and Murat Saraçlar. 2008. Turkish Language Resources: Morphological Parser, Morphological Disambiguator and Web Corpus. In Proc. of GoTAL 2008, pages 417–427. find
  48. Djamé Seddah, Reut Tsarfaty, Sandra Kübler, Marie Candito, Jinho D. Choi, Richárd Farkas, Jennifer Foster, Iakes Goenaga, Koldo Gojenola Galletebeitia, Yoav Goldberg, Spence Green, Nizar Habash, Marco Kuhlmann, Wolfgang Maier, Joakim Nivre, Adam Przepiórkowski, Ryan Roth, Wolfgang Seeker, Yannick Versley, Veronika Vincze, Marcin Woliński, Alina Wróblewska, and Eric Villemonte de la Clergerie. 2013. Overview of the SPMRL 2013 Shared Task: A Cross-Framework Evaluation of Parsing Morphologically Rich Languages. In Proceedings of the Fourth Workshop on Statistical Parsing of Morphologically-Rich Languages, pages 146–182, Seattle, Washington, USA, October. Association for Computational Linguistics. find
  49. Djamé Seddah, Sandra Kübler, and Reut Tsarfaty. 2014. Introducing the SPMRL 2014 Shared Task on Parsing Morphologically-rich Languages. In Proceedings of the First Joint Workshop on Statistical Parsing of Morphologically Rich Languages and Syntactic Analysis of Non-Canonical Languages, pages 103–109, Dublin, Ireland, August. Dublin City University. find
  50. Khalil Sima’an, Alon Itai, Yoad Winter, Alon Altman, and Noa Nativ. 2001. Building a tree-bank of modern Hebrew text. Traitement Automatique des Langues, 42(2):247–380. find
  51. Ben Taskar, Vassil Chatalbashev, Daphne Koller, and Carlos Guestrin. 2005. Learning Structured Prediction Models: A Large Margin Approach. In Proceedings of the 22th Annual International Conference on Machine Learning, pages 896–903, Bonn, Germany. ACM. find
  52. Stephen Tratz. 2013. A Cross-Task Flexible Transition Model for Arabic Tokenization, Affix Detection, Affix Labeling, POS Tagging, and Dependency Parsing. In Proceedings of the Fourth Workshop on Statistical Parsing of Morphologically-Rich Languages, pages 34–45, Seattle, Washington, USA, October. Association for Computational Linguistics. find our card
  53. Reut Tsarfaty, Djamé Seddah, Yoav Goldberg, Sandra Kuebler, Yannick Versley, Marie Candito, Jennifer Foster, Ines Rehbein, and Lamia Tounsi. 2010. Statistical Parsing of Morphologically Rich Languages (SPMRL) What, How and Whither. In Proceedings of the NAACL HLT 2010 First Workshop on Statistical Parsing of Morphologically-Rich Languages, pages 1– 12, Los Angeles, CA, USA, June. Association for Computational Linguistics. find
  54. Reut Tsarfaty, Joakim Nivre, and Evelina Andersson. 2012. Joint Evaluation of Morphological Segmentation and Syntactic Parsing. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 6–10, Jeju Island, Korea, July. Association for Computational Linguistics. find
  55. Reut Tsarfaty. 2006. Integrated Morphological and Syntactic Disambiguation for Modern Hebrew. In Proceedings of the COLING/ACL 2006 Student Research Workshop, pages 49–54, Sydney, Australia, July. Association for Computational Linguistics. find our card
  56. Meishan Zhang, Yue Zhang, Wanxiang Che, and Ting Liu. 2014. Character-Level Chinese Dependency Parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1326–1336, Baltimore, Maryland, June. Association for Computational Linguistics. find
  57. Yuan Zhang, Chengtao Li, Regina Barzilay, and Kareem Darwish. 2015. Randomized Greedy Inference for Joint Segmentation, POS Tagging and Dependency Parsing. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 42–52, Denver, Colorado, May–June. Association for Computational Linguistics. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/tacl-2015-seeker-graph-based-lattice-dependency-parser/