[{"article_type":"original","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","month":"01","publication_status":"published","date_published":"2022-01-14T00:00:00Z","citation":{"chicago":"Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” <i>Intelligent Data Analysis</i>. IOS Press, 2022. <a href=\"https://doi.org/10.3233/IDA-205623\">https://doi.org/10.3233/IDA-205623</a>.","ama":"Takhanov R, Kolmogorov V. Combining pattern-based CRFs and weighted context-free grammars. <i>Intelligent Data Analysis</i>. 2022;26(1):257-272. doi:<a href=\"https://doi.org/10.3233/IDA-205623\">10.3233/IDA-205623</a>","mla":"Takhanov, Rustem, and Vladimir Kolmogorov. “Combining Pattern-Based CRFs and Weighted Context-Free Grammars.” <i>Intelligent Data Analysis</i>, vol. 26, no. 1, IOS Press, 2022, pp. 257–72, doi:<a href=\"https://doi.org/10.3233/IDA-205623\">10.3233/IDA-205623</a>.","ista":"Takhanov R, Kolmogorov V. 2022. Combining pattern-based CRFs and weighted context-free grammars. Intelligent Data Analysis. 26(1), 257–272.","apa":"Takhanov, R., &#38; Kolmogorov, V. (2022). Combining pattern-based CRFs and weighted context-free grammars. <i>Intelligent Data Analysis</i>. IOS Press. <a href=\"https://doi.org/10.3233/IDA-205623\">https://doi.org/10.3233/IDA-205623</a>","short":"R. Takhanov, V. Kolmogorov, Intelligent Data Analysis 26 (2022) 257–272.","ieee":"R. Takhanov and V. Kolmogorov, “Combining pattern-based CRFs and weighted context-free grammars,” <i>Intelligent Data Analysis</i>, vol. 26, no. 1. IOS Press, pp. 257–272, 2022."},"volume":26,"article_processing_charge":"No","department":[{"_id":"VlKo"}],"oa":1,"arxiv":1,"_id":"10737","publication_identifier":{"issn":["1088-467X"],"eissn":["1571-4128"]},"publication":"Intelligent Data Analysis","scopus_import":"1","publisher":"IOS Press","fulldoi":"https://doi.org/10.3233/IDA-205623","quality_controlled":"1","page":"257-272","isi":1,"year":"2022","external_id":{"isi":["000749997700015"],"arxiv":["1404.5475"]},"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."}],"intvolume":"        26","oa_version":"Preprint","language":[{"iso":"eng"}],"title":"Combining pattern-based CRFs and weighted context-free grammars","date_updated":"2024-10-09T21:01:33Z","day":"14","status":"public","doi":"10.3233/IDA-205623","type":"journal_article","issue":"1","main_file_link":[{"url":"https://arxiv.org/abs/1404.5475","open_access":"1"}],"date_created":"2022-02-06T23:01:32Z","corr_author":"1","author":[{"full_name":"Takhanov, Rustem","id":"2CCAC26C-F248-11E8-B48F-1D18A9856A87","first_name":"Rustem","last_name":"Takhanov"},{"full_name":"Kolmogorov, Vladimir","last_name":"Kolmogorov","first_name":"Vladimir","id":"3D50B0BA-F248-11E8-B48F-1D18A9856A87"}]}]