Inference algorithms for pattern-based CRFs on sequence data Conference Paper

Author(s): Takhanov, Rustem; Kolmogorov, Vladimir
Title: Inference algorithms for pattern-based CRFs on sequence data
Title Series: JMLR
Affiliation IST Austria
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. 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 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. In 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.
Conference Title: ICML: International Conference on Machine Learning
Volume: 28
Issue 3
Conference Dates: June 16-17, 2013
Conference Location: Atlanta, GA, USA
Publisher: Omnipress  
Date Published: 2013-01-01
Start Page: 145
End Page: 153
Sponsor: 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.
DOI: 10.1007/s00453-015-0017-7
Notes: The authors thank Herbert Edelsbrunner for helpful discussions.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work