---
_id: '2272'
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) x1...xn is
    the sum of terms over intervals [i,j] where each term is non-zero only if the
    substring xi...xj equals a prespecified pattern α. Such CRFs can be naturally
    applied to many sequence tagging problems.\r\nWe 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 O(nL), O(nLℓmax) and O(nLmin{|D|,log(ℓmax+1)}) where L is the combined
    length of input patterns, ℓmax is the maximum length of a pattern, and D is the
    input alphabet. This improves on the previous algorithms of (Ye et al., 2009)
    whose complexities are respectively O(nL|D|), O(n|Γ|L2ℓ2max) and O(nL|D|), where
    |Γ| is the number of input patterns.\r\nIn addition, we give an efficient algorithm
    for sampling. Finally, we consider the case of non-positive weights. (Komodakis
    & Paragios, 2009) gave an O(nL) algorithm for computing the MAP. We present
    a modification that has the same worst-case complexity but can beat it in the
    best case. "
alternative_title:
- JMLR
article_processing_charge: No
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. Inference algorithms for pattern-based CRFs on sequence
    data. In: <i>ICML’13 Proceedings of the 30th International Conference on International</i>.
    Vol 28. ML Research Press; 2013:145-153.'
  apa: 'Takhanov, R., &#38; Kolmogorov, V. (2013). Inference algorithms for pattern-based
    CRFs on sequence data. In <i>ICML’13 Proceedings of the 30th International Conference
    on International</i> (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press.'
  chicago: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
    CRFs on Sequence Data.” In <i>ICML’13 Proceedings of the 30th International Conference
    on International</i>, 28:145–53. ML Research Press, 2013.
  ieee: R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs
    on sequence data,” in <i>ICML’13 Proceedings of the 30th International Conference
    on International</i>, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.
  ista: 'Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs
    on sequence data. ICML’13 Proceedings of the 30th International Conference on
    International. ICML: International Conference on Machine Learning, JMLR, vol.
    28, 145–153.'
  mla: Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based
    CRFs on Sequence Data.” <i>ICML’13 Proceedings of the 30th International Conference
    on International</i>, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53.
  short: R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International
    Conference on International, ML Research Press, 2013, pp. 145–153.
conference:
  end_date: 2013-06-21
  location: Atlanta, GA, USA
  name: 'ICML: International Conference on Machine Learning'
  start_date: 2013-06-16
corr_author: '1'
date_created: 2018-12-11T11:56:41Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2025-09-29T14:28:48Z
day: '01'
department:
- _id: VlKo
external_id:
  isi:
  - '000381149500002'
intvolume: '        28'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515
month: '06'
oa: 1
oa_version: Submitted Version
page: 145 - 153
publication: ICML'13 Proceedings of the 30th International Conference on International
publication_status: published
publisher: ML Research Press
publist_id: '4672'
quality_controlled: '1'
related_material:
  record:
  - id: '1794'
    relation: later_version
    status: public
scopus_import: '1'
status: public
title: Inference algorithms for pattern-based CRFs on sequence data
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 28
year: '2013'
...