Branch and Bound Algorithm for Dependency Parsing with Non-local Features

Transactions of the Association for Computational Linguistics, 1 (2013) 37–48. Action Editor: Ryan McDonald. Submitted 11/2012; Revised 2/2013; Published 3/2013. c⃝2013 Association for Computational Linguistics. Branch and Bound Algorithm for Dependency Parsing with Non-local Features Xian Qian and Yang Liu Computer Science Department The University of Texas at Dallas {qx,yangl}@hlt.utdallas.edu Abstract Graph based dependency parsing is inefficient when handling non-local features due to high computational complexity of inference. In this paper, we proposed an exact and effi- cient decoding algorithm based on the Branch and Bound (B&B) framework where non- local features are bounded by a linear combi- nation of local features. Dynamic program- ming is used to search the upper bound. Ex- periments are conducted on English PTB and Chinese CTB datasets. We achieved competi- tive Unlabeled Attachment Score (UAS) when no additional resources are available: 93.17% for English and 87.25% for Chinese. Parsing speed is 177 words per second for English and 97 words per second for Chinese. Our algo- rithm is general and can be adapted to non- projective dependency parsing or other graph- ical models. 1 Introduction For graph based projective dependency parsing, dy- namic programming (DP) is popular for decoding due to its efficiency when handling local features. It performs cubic time parsing for arc-factored mod- els (Eisner, 1996; McDonald et al., 2005a) and bi- quadratic time for higher order models with richer sibling and grandchild features (Carreras, 2007; Koo and Collins, 2010). However, for models with gen- eral non-local features, DP is inefficient. There have been numerous studies on global in- ference algorithms for general higher order parsing. One popular approach is reranking (Collins, 2000; Charniak and Johnson, 2005; Hall, 2007). It typi- cally has two steps: the low level classifier gener- ates the top k hypotheses using local features, then the high level classifier reranks these candidates us- ing global features. Since the reranking quality is bounded by the oracle performance of candidates, some work has combined candidate generation and reranking steps using cube pruning (Huang, 2008; Zhang and McDonald, 2012) to achieve higher or- acle performance. They parse a sentence in bottom up order and keep the top k derivations for each s- pan using k best parsing (Huang and Chiang, 2005). After merging the two spans, non-local features are used to rerank top k combinations. This approach is very efficient and flexible to handle various non- local features. The disadvantage is that it tends to compute non-local features as early as possible so that the decoder can utilize that information at inter- nal spans, hence it may miss long historical features such as long dependency chains. Smith and Eisner modeled dependency parsing using Markov Random Fields (MRFs) with glob- al constraints and applied loopy belief propaga- tion (LBP) for approximate learning and inference (Smith and Eisner, 2008). Similar work was done for Combinatorial Categorial Grammar (CCG) pars- ing (Auli and Lopez, 2011). They used posterior marginal beliefs for inference to satisfy the tree con- straint: for each factor, only legal messages …

Content truncated to 500 words