In:
Intelligent Data Analysis, IOS Press, Vol. 26, No. 1 ( 2022-01-14), p. 257-272
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.
Type of Medium:
Online Resource
ISSN:
1088-467X
,
1571-4128
Language:
Unknown
Publisher:
IOS Press
Publication Date:
2022
detail.hit.zdb_id:
2002356-X
SSG:
24,1
Permalink