2-Slave Dual Decomposition for Generalized Higher Order CRFs | Zendy

Xian Qian | Zendy; Yang Liu | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

2-Slave Dual Decomposition for Generalized Higher Order CRFs

Author(s) -

Xian Qian,

Yang Liu

Publication year - 2014

Publication title -

transactions of the association for computational linguistics

Language(s) - English

Resource type - Journals

ISSN - 2307-387X

DOI - 10.1162/tacl_a_00187

Subject(s) - crfs , computer science , dual (grammatical number) , decomposition , dependency (uml) , conditional random field , decoding methods , encoding (memory) , quadratic equation , sentence , maximization , algorithm , tree (set theory) , theoretical computer science , artificial intelligence , mathematical optimization , mathematics , combinatorics , biology , art , ecology , geometry , literature

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research