Inference algorithms for pattern-based CRFs on sequence data

DOI10.1007/S00453-015-0017-7zbMATH Open1353.68237arXiv1210.0508OpenAlexW2157550084MaRDI QIDQ334918FDOQ334918

Authors: Vladimir Kolmogorov, Rustem Takhanov 

Publication date: 1 November 2016

Published in: Algorithmica (Search for Journal in Brave)

Abstract: 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\mathrm{...}{x}_n$ is the sum of terms over intervals $[i,j]$ where each term is non-zero only if the substring $x_i\mathrm{...}{x}_j$ equals a prespecified pattern $alpha$. 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(nLel{l}_{max})$ and $O(nLmin|D|,log(el{l}_{max}+1))$ where $L$ is the combined length of input patterns, $el{l}_{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|Gamma|L^{2}el{l}_{max}^2)$ and $O(nL|D|)$, where $|Gamma|$ 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.

Full work available at URL: https://arxiv.org/abs/1210.0508

Recommendations

• An introduction to conditional random fields
• Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data
• scientific article; zbMATH DE number 6378100
• Sequential inference of Markov networks by dynamic programming for structural pattern recognition
• Conditional random fields for pattern recognition applied to structured data

zbMATH Keywords

string algorithmsconditional random fieldssequence tagging

Mathematics Subject Classification ID

Random fields; image analysis (62M40) Learning and adaptive systems in artificial intelligence (68T05) Algorithms on strings (68W32)

Cites Work

• Recursive Star-Tree Parallel Data Structure
• Inference algorithms for pattern-based CRFs on sequence data

Cited In (6)

• Hierarchical semi-Markov conditional random fields for deep recursive sequential data
• Computing a partition function of a generalized pattern-based energy over a semiring
• Inference algorithms for pattern-based CRFs on sequence data
• Sequential inference of Markov networks by dynamic programming for structural pattern recognition
• A conditional random field-based model for joint sequence segmentation and classification
• Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data

This page was built for publication: Inference algorithms for pattern-based CRFs on sequence data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334918)