2-Slave Dual Decomposition for Generalized Higher Order CRFs

Xian Qian, Yang Liu


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.
Anthology ID:
Q14-1027
Volume:
Transactions of the Association for Computational Linguistics, Volume 2
Month:
Year:
2014
Address:
Cambridge, MA
Editors:
Dekang Lin, Michael Collins, Lillian Lee
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
339–350
Language:
URL:
https://aclanthology.org/Q14-1027
DOI:
10.1162/tacl_a_00187
Bibkey:
Cite (ACL):
Xian Qian and Yang Liu. 2014. 2-Slave Dual Decomposition for Generalized Higher Order CRFs. Transactions of the Association for Computational Linguistics, 2:339–350.
Cite (Informal):
2-Slave Dual Decomposition for Generalized Higher Order CRFs (Qian & Liu, TACL 2014)
Copy Citation:
PDF:
https://aclanthology.org/Q14-1027.pdf