Inference algorithms for pattern-based CRFs on sequence data

Rustem Takhanov, Vladimir Kolmogorov
Proceedings of the 30th International Conference on Machine Learning, PMLR 28(3):145-153, 2013.

Abstract

We consider \em Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x_1\ldots x_n is the sum of terms over intervals [i,j] where each term is non-zero only if the substring x_i\ldots x_j 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(n L), O(n L \ell_\max) and O(n L \min{|D|,\log (\ell_\max + 1)}) where L is the combined length of input patterns, \ell_\max is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of \citeYe:NIPS09 whose complexities are respectively O(n L |D|), O\left(n |Γ| L^2 \ell_\max^2\right) and O(n L |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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v28-takhanov13, title = {Inference algorithms for pattern-based CRFs on sequence data}, author = {Takhanov, Rustem and Kolmogorov, Vladimir}, booktitle = {Proceedings of the 30th International Conference on Machine Learning}, pages = {145--153}, year = {2013}, editor = {Dasgupta, Sanjoy and McAllester, David}, volume = {28}, number = {3}, series = {Proceedings of Machine Learning Research}, address = {Atlanta, Georgia, USA}, month = {17--19 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v28/takhanov13.pdf}, url = {https://proceedings.mlr.press/v28/takhanov13.html}, abstract = {We consider \em Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x_1\ldots x_n is the sum of terms over intervals [i,j] where each term is non-zero only if the substring x_i\ldots x_j 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(n L), O(n L \ell_\max) and O(n L \min{|D|,\log (\ell_\max + 1)}) where L is the combined length of input patterns, \ell_\max is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of \citeYe:NIPS09 whose complexities are respectively O(n L |D|), O\left(n |Γ| L^2 \ell_\max^2\right) and O(n L |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. } }
Endnote
%0 Conference Paper %T Inference algorithms for pattern-based CRFs on sequence data %A Rustem Takhanov %A Vladimir Kolmogorov %B Proceedings of the 30th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2013 %E Sanjoy Dasgupta %E David McAllester %F pmlr-v28-takhanov13 %I PMLR %P 145--153 %U https://proceedings.mlr.press/v28/takhanov13.html %V 28 %N 3 %X We consider \em Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x_1\ldots x_n is the sum of terms over intervals [i,j] where each term is non-zero only if the substring x_i\ldots x_j 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(n L), O(n L \ell_\max) and O(n L \min{|D|,\log (\ell_\max + 1)}) where L is the combined length of input patterns, \ell_\max is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of \citeYe:NIPS09 whose complexities are respectively O(n L |D|), O\left(n |Γ| L^2 \ell_\max^2\right) and O(n L |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.
RIS
TY - CPAPER TI - Inference algorithms for pattern-based CRFs on sequence data AU - Rustem Takhanov AU - Vladimir Kolmogorov BT - Proceedings of the 30th International Conference on Machine Learning DA - 2013/05/26 ED - Sanjoy Dasgupta ED - David McAllester ID - pmlr-v28-takhanov13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 28 IS - 3 SP - 145 EP - 153 L1 - http://proceedings.mlr.press/v28/takhanov13.pdf UR - https://proceedings.mlr.press/v28/takhanov13.html AB - We consider \em Conditional Random Fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) x_1\ldots x_n is the sum of terms over intervals [i,j] where each term is non-zero only if the substring x_i\ldots x_j 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(n L), O(n L \ell_\max) and O(n L \min{|D|,\log (\ell_\max + 1)}) where L is the combined length of input patterns, \ell_\max is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of \citeYe:NIPS09 whose complexities are respectively O(n L |D|), O\left(n |Γ| L^2 \ell_\max^2\right) and O(n L |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. ER -
APA
Takhanov, R. & Kolmogorov, V.. (2013). Inference algorithms for pattern-based CRFs on sequence data. Proceedings of the 30th International Conference on Machine Learning, in Proceedings of Machine Learning Research 28(3):145-153 Available from https://proceedings.mlr.press/v28/takhanov13.html.

Related Material