---
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_language: eng
dct_publisher: International Machine Learning Society@
dct_title: Inference algorithms for pattern-based CRFs on sequence data@
...