Combining pattern-based CRFs and weighted context-free grammars

Article type: Research Article

Authors: Takhanov, Rustem^{a; *} | Kolmogorov, Vladimir^b

Affiliations: [a] Mathematics Department, Nazarbayev University, Nur-Sultan City, Kazakhstan | [b] Institute of Science and Technology Austria, Klosterneuburg, Austria

Correspondence: [*] Corresponding author: Rustem Takhanov, Mathematics Department, Nazarbayev University, 53 Kabanbay Batyr Ave, Nur-Sultan City, Kazakhstan. E-mail: [email protected].

Abstract: 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.

Keywords: Pattern-based, conditional random fields, weighted context-free grammar, interaction grammars

DOI: 10.3233/IDA-205623

Journal: Intelligent Data Analysis, vol. 26, no. 1, pp. 257-272, 2022