{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T07:17:35Z","timestamp":1768547855349,"version":"3.49.0"},"reference-count":64,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p> Derivations under different grammar formalisms allow extraction of various dependency structures. Particularly, bilexical deep dependency structures beyond surface tree representation can be derived from linguistic analysis grounded by CCG, LFG, and HPSG. Traditionally, these dependency structures are obtained as a by-product of grammar-guided parsers. In this article, we study the alternative data-driven, transition-based approach, which has achieved great success for tree parsing, to build general dependency graphs. We integrate existing tree parsing techniques and present two new transition systems that can generate arbitrary directed graphs in an incremental manner. Statistical parsers that are competitive in both accuracy and efficiency can be built upon these transition systems. Furthermore, the heterogeneous design of transition systems yields diversity of the corresponding parsing models and thus greatly benefits parser ensemble. Concerning the disambiguation problem, we introduce two new techniques, namely, transition combination and tree approximation, to improve parsing quality. Transition combination makes every action performed by a parser significantly change configurations. Therefore, more distinct features can be extracted for statistical disambiguation. With the same goal of extracting informative features, tree approximation induces tree backbones from dependency graphs and re-uses tree parsing techniques to produce tree-related features. We conduct experiments on CCG-grounded functor\u2013argument analysis, LFG-grounded grammatical relation analysis, and HPSG-grounded semantic dependency analysis for English and Chinese. Experiments demonstrate that data-driven models with appropriate transition systems can produce high-quality deep dependency analysis, comparable to more complex grammar-driven models. Experiments also indicate the effectiveness of the heterogeneous design of transition systems for parser ensemble, transition combination, as well as tree approximation for statistical disambiguation. <\/jats:p>","DOI":"10.1162\/coli_a_00252","type":"journal-article","created":{"date-parts":[[2016,6,17]],"date-time":"2016-06-17T19:28:59Z","timestamp":1466191739000},"page":"353-389","source":"Crossref","is-referenced-by-count":11,"title":["Transition-Based Parsing for Deep Dependency Structures"],"prefix":"10.1162","volume":"42","author":[{"given":"Xun","family":"Zhang","sequence":"first","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yantao","family":"Du","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weiwei","family":"Sun","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaojun","family":"Wan","sequence":"additional","affiliation":[{"name":"Peking University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/N15-1006"},{"key":"R3","unstructured":"Auli, Michael and Adam Lopez. 2011b. Training a log-linear parser with loss functions via softmax-margin. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 333\u2013343, Edinburgh."},{"key":"R4","unstructured":"Bohnet, Bernd. 2010. Top accuracy and fast dependency parsing is not a contradiction. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 89\u201397, Beijing."},{"key":"R6","unstructured":"Choi, Jinho D. and Martha Palmer. 2011. Getting the most out of transition-based dependency parsing. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 687\u2013692, Portland, OR."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.4.493"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Clark, Stephen, Julia Hockenmaier, and Mark Steedman. 2002. Building deep dependency structures using a wide-coverage CCG parser. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 327\u2013334. Philadelphia, PA.","DOI":"10.3115\/1073083.1073138"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Collins, Michael. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, pages 1\u20138. Philadelphia, PA.","DOI":"10.3115\/1118693.1118694"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.3115\/1218955.1218970"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-006-6327-9"},{"key":"R12","unstructured":"Covington, Michael A. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pages 95\u2013102. Athens, GA."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P15-1149"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/S14-2080"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.18653\/v1\/S15-2154"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324900002370"},{"key":"R17","unstructured":"Flickinger, Daniel, Yi Zhang, and Valia Kordoni. 2012. Deepbank: A dynamically annotated treebank of the Wall Street journal. In Proceedings of the Eleventh International Workshop on Treebanks and Linguistic Theories, pages 85\u201396, Lisbon."},{"key":"R18","unstructured":"G\u00f3mez-Rodr\u00edguez, Carlos and Joakim Nivre. 2010. A transition-based parser for 2-planar dependency structures. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1492\u20131501, Uppsala."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00150"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.3115\/1596409.1596411"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1162\/COLI_a_00158"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.3.355"},{"key":"R23","unstructured":"Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1077\u20131086, Uppsala."},{"key":"R24","unstructured":"Huang, Zhongqiang, Mary Harper, and Slav Petrov. 2010. Self-training with products of latent variable grammars. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 12\u201322, Cambridge, MA."},{"key":"R25","unstructured":"Ivanova, Angelina, Stephan Oepen, Lilja \u00d8vrelid, and Dan Flickinger. 2012. Who did what to whom? A contrastive study of syntacto-semantic dependencies. In Proceedings of the Sixth Linguistic Annotation Workshop, pages 2\u201311, Jeju Island."},{"key":"R26","unstructured":"Koo, Terry and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1\u201311, Uppsala."},{"key":"R27","unstructured":"Li, Qi, Heng Ji, and Liang Huang. 2013. Joint event extraction via structured prediction with global features. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 73\u201382, Sofia."},{"key":"R28","unstructured":"Manshadi, Mehdi, Daniel Gildea, and James Allen. 2013. Plurality, negation, and quantification: Towards comprehensive quantifier scope disambiguation. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 64\u201372, Sofia."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/S14-2082"},{"key":"R30","unstructured":"Matsuzaki, Takuya, Yusuke Miyao, and Jun'ichi Tsujii. 2007. Efficient HPSG parsing with supertagging and CFG-filtering. In Proceedings of the 20th International Joint Conference on Artificial intelligence, pages 1671\u20131676, San Francisco, CA."},{"key":"R31","unstructured":"McDonald, Ryan. 2006. Discriminative Learning and Spanning Tree Algorithms for Dependency Parsing. Ph.D. thesis, University of Pennsylvania, Philadelphia, PA."},{"key":"R32","unstructured":"McDonald, Ryan and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL-2006)), volume 6, pages 81\u201388, Trento."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00039"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"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 IJCNLP, pages 684\u2013693, Hainan Island.","DOI":"10.1007\/978-3-540-30211-7_72"},{"key":"R35","unstructured":"Miyao, Yusuke, Rune S\u00e6tre, Kenji Sagae, Takuya Matsuzaki, and Jun'ichi Tsujii. 2008. Task-oriented evaluation of syntactic parsers and their representations. In Proceedings of ACL-08: HLT, pages 46\u201354, Columbus, OH."},{"key":"R36","unstructured":"Miyao, Yusuke, Kenji Sagae, and Jun'ichi Tsujii. 2007. Towards framework-independent evaluation of deep linguistic parsers. In Proceedings of the GEAF 2007 Workshop, pages 238\u2013258, Stanford, CA."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2008.34.1.35"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1162\/coli.07-056-R1-07-027"},{"key":"R40","unstructured":"Nivre, Joakim and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of ACL-08: HLT, pages 950\u2013958, Columbus, OH."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.3115\/1219840.1219853"},{"key":"R42","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/S14-2008"},{"key":"R43","unstructured":"Oepen, Stephan and Jan Tore L\u00f8nning. 2006. Discriminant-based MRS banking. In Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC-2006), Genoa."},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1162\/0891201053630264"},{"key":"R46","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2008.34.2.257"},{"key":"R47","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00190"},{"key":"R48","doi-asserted-by":"publisher","DOI":"10.3115\/1614049.1614082"},{"key":"R49","doi-asserted-by":"crossref","unstructured":"Sagae, Kenji and Jun'ichi Tsujii. 2008. Shift-reduce dependency DAG parsing. In Proceedings of the 22nd International Conference on Computational Linguistics, pages 753\u2013760, Manchester.","DOI":"10.3115\/1599081.1599176"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P14-1042"},{"key":"R52","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00229"},{"key":"R53","doi-asserted-by":"publisher","DOI":"10.3115\/1596324.1596352"},{"key":"R54","unstructured":"Surdeanu, Mihai and Christopher D. Manning. 2010. Ensemble models for dependency parsing: Cheap and good? In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 649\u2013652, Los Angeles, CA."},{"key":"R55","doi-asserted-by":"publisher","DOI":"10.3115\/1699571.1699585"},{"key":"R56","unstructured":"Titov, Ivan, James Henderson, Paola Merlo, and Gabriele Musillo. 2009. Online graph planarisation for synchronous parsing of semantic and syntactic dependencies. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, pages 1562\u20131567, San Francisco, CA."},{"key":"R57","doi-asserted-by":"crossref","unstructured":"Torres Martins, Andre, 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\u2013350, Suntec.","DOI":"10.3115\/1687878.1687928"},{"key":"R58","doi-asserted-by":"crossref","unstructured":"Torres Martins, Andr\u00e9 Filipe, Dipanjan Das, Noah A. Smith, and Eric P. Xing. 2008. Stacking dependency parsers. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 157\u2013166, Honolulu, HI.","DOI":"10.3115\/1613715.1613738"},{"key":"R59","unstructured":"Tse, Daniel and James R. Curran. 2010. Chinese CCGbank: Extracting CCG derivations from the Penn Chinese treebank. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 1083\u20131091, Beijing."},{"key":"R60","unstructured":"Tse, Daniel and James R. Curran. 2012. The challenges of parsing Chinese with combinatory categorial grammar. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 295\u2013304, Montr\u00e9al."},{"key":"R61","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P15-1032"},{"key":"R62","doi-asserted-by":"publisher","DOI":"10.3115\/v1\/P14-1021"},{"key":"R63","unstructured":"Yamada, Hiroyasu and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In 8th International Workshop of Parsing Technologies (IWPT2003), pages 195\u2013206, Nancy."},{"key":"R64","doi-asserted-by":"publisher","DOI":"10.3115\/1699648.1699702"},{"key":"R65","doi-asserted-by":"crossref","unstructured":"Zhang, Yue and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 562\u2013571, Honolulu, HI.","DOI":"10.3115\/1613715.1613784"},{"key":"R66","unstructured":"Zhang, Yue and Stephen Clark. 2011a. Shift-reduce CCG parsing. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 683\u2013692, Portland, OR."},{"key":"R67","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00037"},{"key":"R68","unstructured":"Zhang, Yue and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 188\u2013193, Portland, OR."},{"key":"R69","unstructured":"Zhuang, Tao and Chengqing Zong. 2010. A minimum error weighting combination strategy for Chinese semantic role labeling. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 1362\u20131370, Beijing."}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T21:27:54Z","timestamp":1615584474000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/42\/3\/353-389\/1540"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":64,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1162\/COLI_a_00252"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00252","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}