2014/04/22 by Rustem Takhanov, Vladimir Kolmogorov, Takhanov, Rustem +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.7 #Machine Learning (cs.LG) #cs.DS #cs.FL #cs.LG
paper · pdf · doi:10.48550/arxiv.1404.5475
11 pages
arxiv created 2014/11/01 · arxiv updated 2014/11/04
We consider two models for the sequence labeling (tagging) problem. The first one is a \em Pattern-Based Conditional Random Field (\PB), in which the energy of a string (chain labeling) x=x1… xn∈ Dn is a sum of terms over intervals [i,j] where each term is non-zero only if the substring xi… xj equals a prespecified word w∈ Λ. The second model is a \em Weighted Context-Free Grammar (\WCFG) frequently used for natural language processing. \PB and \WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a \em Grammatical Pattern-Based CRF model (\GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the \em Hybrid model of Benedí and Sanchez that combines \em N-grams and \WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a \GPB such as computing MAP. We present a polynomial-time algorithm for general \GPBs and a faster version for a special case that we call \em Interaction Grammars.