@article{10737,
  abstract     = {We consider two models for the sequence labeling (tagging) problem. The first one is a 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 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 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 Hybrid model of Benedí and Sanchez that combines 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 Interaction Grammars.},
  author       = {Takhanov, Rustem and Kolmogorov, Vladimir},
  issn         = {1571-4128},
  journal      = {Intelligent Data Analysis},
  number       = {1},
  pages        = {257--272},
  publisher    = {IOS Press},
  title        = {{Combining pattern-based CRFs and weighted context-free grammars}},
  doi          = {10.3233/IDA-205623},
  volume       = {26},
  year         = {2022},
}