---
_id: '10737'
abstract:
- lang: eng
  text: 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.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Rustem
  full_name: Takhanov, Rustem
  id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
  last_name: Takhanov
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: Takhanov R, Kolmogorov V. Combining pattern-based CRFs and weighted context-free
    grammars. <i>Intelligent Data Analysis</i>. 2022;26(1):257-272. doi:<a href="https://doi.org/10.3233/IDA-205623">10.3233/IDA-205623</a>
  apa: Takhanov, R., &#38; Kolmogorov, V. (2022). Combining pattern-based CRFs and
    weighted context-free grammars. <i>Intelligent Data Analysis</i>. IOS Press. <a
    href="https://doi.org/10.3233/IDA-205623">https://doi.org/10.3233/IDA-205623</a>
  chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs
    and Weighted Context-Free Grammars.” <i>Intelligent Data Analysis</i>. IOS Press,
    2022. <a href="https://doi.org/10.3233/IDA-205623">https://doi.org/10.3233/IDA-205623</a>.
  ieee: R. Takhanov and V. Kolmogorov, “Combining pattern-based CRFs and weighted
    context-free grammars,” <i>Intelligent Data Analysis</i>, vol. 26, no. 1. IOS
    Press, pp. 257–272, 2022.
  ista: Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted
    context-free grammars. Intelligent Data Analysis. 26(1), 257–272.
  mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and
    Weighted Context-Free Grammars.” <i>Intelligent Data Analysis</i>, vol. 26, no.
    1, IOS Press, 2022, pp. 257–72, doi:<a href="https://doi.org/10.3233/IDA-205623">10.3233/IDA-205623</a>.
  short: R. Takhanov, V. Kolmogorov, Intelligent Data Analysis 26 (2022) 257–272.
date_created: 2022-02-06T23:01:32Z
date_published: 2022-01-14T00:00:00Z
date_updated: 2023-08-02T14:09:41Z
day: '14'
department:
- _id: VlKo
doi: 10.3233/IDA-205623
external_id:
  arxiv:
  - '1404.5475'
  isi:
  - '000749997700015'
intvolume: '        26'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1404.5475
month: '01'
oa: 1
oa_version: Preprint
page: 257-272
publication: Intelligent Data Analysis
publication_identifier:
  eissn:
  - 1571-4128
  issn:
  - 1088-467X
publication_status: published
publisher: IOS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Combining pattern-based CRFs and weighted context-free grammars
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 26
year: '2022'
...