---
res:
  bibo_abstract:
  - "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. @eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Rustem
      foaf_name: Takhanov, Rustem
      foaf_surname: Takhanov
      foaf_workInfoHomepage: http://www.librecat.org/personId=2CCAC26C-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Vladimir
      foaf_name: Kolmogorov, Vladimir
      foaf_surname: Kolmogorov
      foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
  bibo_issue: '3'
  bibo_volume: 28
  dct_date: 2013^xs_gYear
  dct_identifier:
  - UT:000381149500002
  dct_language: eng
  dct_publisher: ML Research Press@
  dct_title: Inference algorithms for pattern-based CRFs on sequence data@
...