2-Slave Dual Decomposition for Generalized Higher Order CRFs

2-Slave Dual Decomposition for Generalized Higher Order CRFs Xian Qian and Yang Liu Computer Science Department The University of Texas at Dallas {qx,yangl}@hlt.utdallas.edu Abstract We show that the decoding problem in generalized Higher Order Conditional Random Fields (CRFs) can be decomposed into two parts: one is a tree labeling problem that can be solved in linear time using dynamic programming; the other is a supermodular quadratic pseudo-Boolean maximization problem, which can be solved in cubic time using a minimum cut algorithm. We use dual decomposition to force their agreement. Experimental results on Twitter named entity recognition and sentence dependency tagging tasks show that our method outperforms spanning tree based dual decomposition. 1 Introduction Conditional Random Fields (Lafferty et al., 2001) (CRFs) are popular models for many NLP tasks. In particular, the linear chain CRFs explore local structure information for sequence labeling tasks, such as part-of-speech (POS) tagging, named entity recognition (NER), and shallow parsing. Recent studies have shown that the predictive power of CRFs can be strengthened by breaking the locality assumption. They either add long distance dependencies and patterns to linear chains for improved sequence labeling (Galley, 2006; Finkel et al., 2005; Kazama and Torisawa, 2007), or directly use the 4-connected neighborhood lattice (Ding et al., 2008). The resulting non-local models generally suffer from exponential time complexity of inference except some special cases (Sarawagi and Cohen, 2004; Takhanov and Kolmogorov, 2013; Kolmogorov and Zabih, 2004). Approximate decoding algorithms have been proposed in the past decade, such as reranking (Collins, 2002b), loopy belief propagation (Sutton and Mccallum, 2006), tree reweighted belief propagation (Kolmogorov, 2006). In this paper, we focus on dual decomposition (DD), which has attracted much attention recently due to its simplicity and effectiveness (Rush and Collins, 2012). In short, it decomposes the decoding problem into several sub-problems. For each sub-problem, an efficient decoding algorithm is deployed as a slave solver. Finally a simple method forces agreement among different slaves. A popular choice is the sub- gradient algorithm. Martins et al. (2011b) showed that the success of the sub-gradient algorithm is strongly tied to the ability of finding a good decomposition, i.e., one involving few overlapping slaves. However, for generalized higher order graphical models, a lightweight decomposition is not at hand and many overlapping slaves may be involved. Martins et al. (2011b) showed that the sub-gradient algorithm exhibits extremely slow convergence in such cases, and they proposed the alternating directions method (DD-ADMM) to tackle these. In this paper, we propose a 2-slave dual decomposition approach for efficient decoding in higher order CRFs. One slave is a tree labeling model that can be solved in linear time using dynamic programming. The other is a supermodular quadratic pseudo-Boolean maximization problem, which can be solved in cubic time via minimum 339 Transactions of the Association for Computational Linguistics, 2 (2014) 339–350. Action Editor: Kristina Toutanova. Submitted 11/2013; Revised 6/2014; Published 10/2014. c⃝2014 Association for Computational Linguistics. cut. Experimental results on Twitter NER and sentence dependency tagging tasks demonstrate the effectiveness of our …

Content truncated to 500 words