[{"uri_base":"https://research-explorer.ista.ac.at","article_processing_charge":"No","day":"01","dc":{"publisher":["ML Research Press"],"title":["Inference algorithms for pattern-based CRFs on sequence data","JMLR"],"source":["Takhanov R, Kolmogorov V. Inference algorithms for pattern-based CRFs on sequence data. In: ICML’13 Proceedings of the 30th International Conference on International. Vol 28. ML Research Press; 2013:145-153."],"rights":["info:eu-repo/semantics/openAccess"],"language":["eng"],"date":["2013"],"description":["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.\r\nWe 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.\r\nIn 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. "],"identifier":["https://research-explorer.ista.ac.at/record/2272"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"creator":["Takhanov, Rustem","Kolmogorov, Vladimir"]},"scopus_import":"1","date_published":"2013-06-01T00:00:00Z","page":"145 - 153","citation":{"chicago":"Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” In ICML’13 Proceedings of the 30th International Conference on International, 28:145–53. ML Research Press, 2013.","mla":"Takhanov, Rustem, and Vladimir Kolmogorov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” ICML’13 Proceedings of the 30th International Conference on International, vol. 28, no. 3, ML Research Press, 2013, pp. 145–53.","short":"R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, ML Research Press, 2013, pp. 145–153.","ista":"Takhanov R, Kolmogorov V. 2013. Inference algorithms for pattern-based CRFs on sequence data. ICML’13 Proceedings of the 30th International Conference on International. ICML: International Conference on Machine Learning, JMLR, vol. 28, 145–153.","ieee":"R. Takhanov and V. Kolmogorov, “Inference algorithms for pattern-based CRFs on sequence data,” in ICML’13 Proceedings of the 30th International Conference on International, Atlanta, GA, USA, 2013, vol. 28, no. 3, pp. 145–153.","apa":"Takhanov, R., & Kolmogorov, V. (2013). Inference algorithms for pattern-based CRFs on sequence data. In ICML’13 Proceedings of the 30th International Conference on International (Vol. 28, pp. 145–153). Atlanta, GA, USA: ML Research Press."},"publication":"ICML'13 Proceedings of the 30th International Conference on International","issue":"3","abstract":[{"lang":"eng"}],"alternative_title":[],"type":"conference","oa_version":"Submitted Version","intvolume":" 28","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2272","month":"06","language":[{}],"conference":{"start_date":"2013-06-16","location":"Atlanta, GA, USA","end_date":"2013-06-21","name":"ICML: International Conference on Machine Learning"},"quality_controlled":"1","main_file_link":[{"url":"http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515","open_access":"1"}],"oa":1,"creator":{"id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","login":"kschuh"},"publist_id":"4672","volume":28,"dini_type":"doc-type:conferenceObject","date_updated":"2023-10-17T09:51:32Z","date_created":"2018-12-11T11:56:41Z","related_material":{"record":[{"id":"1794","relation":"later_version","status":"public"}]},"author":[{"id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","first_name":"Rustem","last_name":"Takhanov"},{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov"}],"department":[{"tree":[{"_id":"ResearchGroups"},{"_id":"IST"}],"_id":"VlKo"}],"publication_status":"published"}]