Inference algorithms for pattern-based CRFs on sequence data

V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.


Journal Article | Published | English
Department
Abstract
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.
Publishing Year
Date Published
2016-09-01
Journal Title
Algorithmica
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.
Volume
76
Issue
1
Page
17 - 46
IST-REx-ID

Cite this

Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7
Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica, 76(1), 17–46. https://doi.org/10.1007/s00453-015-0017-7
Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica 76, no. 1 (2016): 17–46. https://doi.org/10.1007/s00453-015-0017-7.
V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1, pp. 17–46, 2016.
Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.
Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1210.0508

Search this title in

Google Scholar