Inference algorithms for pattern-based CRFs on sequence data

Rustem Takhanov, Vladimir Kolmogorov

Research output: Contribution to conferencePaperpeer-review

5 Citations (Scopus)


We consider Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x 1... 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), 0(nLℓmax) and O(nL min{|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|Γ|L2max2) and O(nL\D\), where |Γ| 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. Finally, we apply pattern-based CRFs to the problem of the protein dihedral angles prediction.

Original languageEnglish
Number of pages9
Publication statusPublished - Jan 1 2013
Event30th International Conference on Machine Learning, ICML 2013 - Atlanta, GA, United States
Duration: Jun 16 2013Jun 21 2013


Other30th International Conference on Machine Learning, ICML 2013
CountryUnited States
CityAtlanta, GA

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Sociology and Political Science

Fingerprint Dive into the research topics of 'Inference algorithms for pattern-based CRFs on sequence data'. Together they form a unique fingerprint.

Cite this