---
_id: '1794'
abstract:
- lang: eng
  text: We consider Conditional random fields (CRFs) with pattern-based potentials
    defined on a chain. In this model the energy of a string (labeling) (Formula presented.)
    is the sum of terms over intervals [i, j] where each term is non-zero only if
    the substring (Formula presented.) equals a prespecified pattern w. Such CRFs
    can be naturally applied to many sequence tagging problems. We present efficient
    algorithms for the three standard inference tasks in a CRF, namely computing (i)
    the partition function, (ii) marginals, and (iii) computing the MAP. Their complexities
    are respectively (Formula presented.), (Formula presented.) and (Formula presented.)
    where L is the combined length of input patterns, (Formula presented.) is the
    maximum length of a pattern, and D is the input alphabet. This improves on the
    previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively
    (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula
    presented.) is the number of input patterns. In addition, we give an efficient
    algorithm for sampling, and revisit the case of MAP with non-positive weights.
acknowledgement: This work has been partially supported by the European Research Council
  under the European Unions Seventh Framework Programme (FP7/2007-2013)/ERC grant
  agreement no. 616160.
article_processing_charge: No
arxiv: 1
author:
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Rustem
  full_name: Takhanov, Rustem
  id: 2CCAC26C-F248-11E8-B48F-1D18A9856A87
  last_name: Takhanov
citation:
  ama: Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence
    data. <i>Algorithmica</i>. 2016;76(1):17-46. doi:<a href="https://doi.org/10.1007/s00453-015-0017-7">10.1007/s00453-015-0017-7</a>
  apa: Kolmogorov, V., &#38; Takhanov, R. (2016). Inference algorithms for pattern-based
    CRFs on sequence data. <i>Algorithmica</i>. Springer. <a href="https://doi.org/10.1007/s00453-015-0017-7">https://doi.org/10.1007/s00453-015-0017-7</a>
  chicago: Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based
    CRFs on Sequence Data.” <i>Algorithmica</i>. Springer, 2016. <a href="https://doi.org/10.1007/s00453-015-0017-7">https://doi.org/10.1007/s00453-015-0017-7</a>.
  ieee: V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs
    on sequence data,” <i>Algorithmica</i>, vol. 76, no. 1. Springer, pp. 17–46, 2016.
  ista: Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs
    on sequence data. Algorithmica. 76(1), 17–46.
  mla: Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based
    CRFs on Sequence Data.” <i>Algorithmica</i>, vol. 76, no. 1, Springer, 2016, pp.
    17–46, doi:<a href="https://doi.org/10.1007/s00453-015-0017-7">10.1007/s00453-015-0017-7</a>.
  short: V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.
corr_author: '1'
date_created: 2018-12-11T11:54:02Z
date_published: 2016-09-01T00:00:00Z
date_updated: 2025-09-29T14:28:47Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00453-015-0017-7
ec_funded: 1
external_id:
  arxiv:
  - '1210.0508'
  isi:
  - '000381149500002'
intvolume: '        76'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1210.0508
month: '09'
oa: 1
oa_version: Preprint
page: 17 - 46
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '5316'
quality_controlled: '1'
related_material:
  record:
  - id: '2272'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 76
year: '2016'
...