[{"month":"01","publication_identifier":{"eissn":["1571-4128"],"issn":["1088-467X"]},"language":[{"iso":"eng"}],"doi":"10.3233/IDA-205623","quality_controlled":"1","isi":1,"oa":1,"external_id":{"isi":["000749997700015"],"arxiv":["1404.5475"]},"main_file_link":[{"url":"https://arxiv.org/abs/1404.5475","open_access":"1"}],"date_updated":"2023-08-02T14:09:41Z","date_created":"2022-02-06T23:01:32Z","volume":26,"author":[{"full_name":"Takhanov, Rustem","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","first_name":"Rustem","last_name":"Takhanov"},{"full_name":"Kolmogorov, Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","last_name":"Kolmogorov","first_name":"Vladimir"}],"publication_status":"published","department":[{"_id":"VlKo"}],"publisher":"IOS Press","year":"2022","day":"14","article_processing_charge":"No","scopus_import":"1","date_published":"2022-01-14T00:00:00Z","article_type":"original","page":"257-272","publication":"Intelligent Data Analysis","citation":{"chicago":"Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” Intelligent Data Analysis. IOS Press, 2022. https://doi.org/10.3233/IDA-205623.","mla":"Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” Intelligent Data Analysis, vol. 26, no. 1, IOS Press, 2022, pp. 257–72, doi:10.3233/IDA-205623.","short":"R. Takhanov, V. Kolmogorov, Intelligent Data Analysis 26 (2022) 257–272.","ista":"Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 26(1), 257–272.","ieee":"R. Takhanov and V. Kolmogorov, “Combining pattern-based CRFs and weighted context-free grammars,” Intelligent Data Analysis, vol. 26, no. 1. IOS Press, pp. 257–272, 2022.","apa":"Takhanov, R., & Kolmogorov, V. (2022). Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. IOS Press. https://doi.org/10.3233/IDA-205623","ama":"Takhanov R, Kolmogorov V. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 2022;26(1):257-272. doi:10.3233/IDA-205623"},"abstract":[{"lang":"eng","text":"We consider two models for the sequence labeling (tagging) problem. The first one is a Pattern-Based Conditional Random Field (PB), in which the energy of a string (chain labeling) x=x1…xn∈Dn is a sum of terms over intervals [i,j] where each term is non-zero only if the substring xi…xj equals a prespecified word w∈Λ. The second model is a Weighted Context-Free Grammar (WCFG) frequently used for natural language processing. PB and WCFG encode local and non-local interactions respectively, and thus can be viewed as complementary. We propose a Grammatical Pattern-Based CRF model (GPB) that combines the two in a natural way. We argue that it has certain advantages over existing approaches such as the Hybrid model of Benedí and Sanchez that combines N-grams and WCFGs. The focus of this paper is to analyze the complexity of inference tasks in a GPB such as computing MAP. We present a polynomial-time algorithm for general GPBs and a faster version for a special case that we call Interaction Grammars."}],"issue":"1","type":"journal_article","oa_version":"Preprint","title":"Combining pattern-based CRFs and weighted context-free grammars","status":"public","intvolume":" 26","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10737"},{"oa_version":"Preprint","intvolume":" 76","status":"public","title":"Inference algorithms for pattern-based CRFs on sequence data","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"1794","issue":"1","abstract":[{"lang":"eng","text":"We consider Conditional random fields (CRFs) with pattern-based potentials defined on a chain. In this model the energy of a string (labeling) (Formula presented.) is the sum of terms over intervals [i, j] where each term is non-zero only if the substring (Formula presented.) equals a prespecified pattern w. 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 (Formula presented.), (Formula presented.) and (Formula presented.) where L is the combined length of input patterns, (Formula presented.) is the maximum length of a pattern, and D is the input alphabet. This improves on the previous algorithms of Ye et al. (NIPS, 2009) whose complexities are respectively (Formula presented.), (Formula presented.) and (Formula presented.), where (Formula presented.) 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."}],"type":"journal_article","date_published":"2016-09-01T00:00:00Z","page":"17 - 46","citation":{"mla":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica, vol. 76, no. 1, Springer, 2016, pp. 17–46, doi:10.1007/s00453-015-0017-7.","short":"V. Kolmogorov, R. Takhanov, Algorithmica 76 (2016) 17–46.","chicago":"Kolmogorov, Vladimir, and Rustem Takhanov. “Inference Algorithms for Pattern-Based CRFs on Sequence Data.” Algorithmica. Springer, 2016. https://doi.org/10.1007/s00453-015-0017-7.","ama":"Kolmogorov V, Takhanov R. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 2016;76(1):17-46. doi:10.1007/s00453-015-0017-7","ista":"Kolmogorov V, Takhanov R. 2016. Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. 76(1), 17–46.","ieee":"V. Kolmogorov and R. Takhanov, “Inference algorithms for pattern-based CRFs on sequence data,” Algorithmica, vol. 76, no. 1. Springer, pp. 17–46, 2016.","apa":"Kolmogorov, V., & Takhanov, R. (2016). Inference algorithms for pattern-based CRFs on sequence data. Algorithmica. Springer. https://doi.org/10.1007/s00453-015-0017-7"},"publication":"Algorithmica","day":"01","scopus_import":1,"volume":76,"date_created":"2018-12-11T11:54:02Z","date_updated":"2023-10-17T09:51:31Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"2272"}]},"author":[{"id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87","first_name":"Vladimir","last_name":"Kolmogorov","full_name":"Kolmogorov, Vladimir"},{"id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","last_name":"Takhanov","first_name":"Rustem","full_name":"Takhanov, Rustem"}],"publisher":"Springer","department":[{"_id":"VlKo"}],"publication_status":"published","acknowledgement":"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.","year":"2016","publist_id":"5316","ec_funded":1,"language":[{"iso":"eng"}],"doi":"10.1007/s00453-015-0017-7","project":[{"_id":"25FBA906-B435-11E9-9278-68D0E5697425","grant_number":"616160","call_identifier":"FP7","name":"Discrete Optimization in Computer Vision: Theory and Practice"}],"quality_controlled":"1","external_id":{"arxiv":["1210.0508"]},"oa":1,"main_file_link":[{"url":"http://arxiv.org/abs/1210.0508","open_access":"1"}],"month":"09"},{"month":"06","conference":{"end_date":"2013-06-21","start_date":"2013-06-16","location":"Atlanta, GA, USA","name":"ICML: International Conference on Machine Learning"},"language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"http://proceedings.mlr.press/v28/takhanov13.pdf?CFID=105472548&CFTOKEN=5c5859b5d97b4439-27B4AC58-BA92-A964-B598CAACEE6CC515"}],"oa":1,"quality_controlled":"1","publist_id":"4672","related_material":{"record":[{"id":"1794","status":"public","relation":"later_version"}]},"author":[{"id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","first_name":"Rustem","last_name":"Takhanov","full_name":"Takhanov, Rustem"},{"full_name":"Kolmogorov, Vladimir","first_name":"Vladimir","last_name":"Kolmogorov","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}],"volume":28,"date_created":"2018-12-11T11:56:41Z","date_updated":"2023-10-17T09:51:32Z","year":"2013","publisher":"ML Research Press","department":[{"_id":"VlKo"}],"publication_status":"published","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2013-06-01T00:00:00Z","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.","short":"R. Takhanov, V. Kolmogorov, in:, ICML’13 Proceedings of the 30th International Conference on International, ML Research Press, 2013, pp. 145–153.","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.","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.","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.","ama":"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."},"publication":"ICML'13 Proceedings of the 30th International Conference on International","page":"145 - 153","issue":"3","abstract":[{"text":"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. ","lang":"eng"}],"type":"conference","alternative_title":["JMLR"],"oa_version":"Submitted Version","_id":"2272","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 28","title":"Inference algorithms for pattern-based CRFs on sequence data","status":"public"}]