Combining pattern-based CRFs and weighted context-free grammars

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=x1ldots xn∈ Dn is a sum of terms over intervals [i,j] where each term is non-zero only if the substring xildots xj equals a prespecified word w∈ Lambda. 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'i and Sanchez that combines em mboxN-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.