Regular-pattern-sensitive CRF s for Distant Label Interactions (2025)

Abstract: While LLMs have grown popular in sequence labeling, linear-chain conditionalrandom fields (CRFs) remain a popular alternativewith the ability to directly model interactions between labels.However, the Markov assumption limits them to interactions between adjacent labels.Weighted finite-state transducers (FSTs), in contrast, can modeldistant label–label interactions, but exact label inference is intractable in general.In this work, we present regular-pattern-sensitiveCRFs (RPCRFs), a method of enriching standardlinear-chain CRFs with the ability to learnlong-distance label interactions through user-specified patterns.This approach allows users to write regular-expressionlabel patterns concisely specifying which types of interactionsthe model should take into account, allowingthe model to learn from data whether and inwhich contexts these patterns occur. The resultcan be interpreted alternatively as a CRF augmented with additional,non-local potentials,or as a finite-state transducer whose structureis defined by a set of easily-interpretable patterns.Critically, exact training and inferenceare tractable for many pattern sets. We detailhow an RPCRF can be automatically constructed from a set of user-specified patterns,and demonstrate the model’s effectiveness ona sequence of three synthetic sequence modeling datasets.

## introduction sequence labeling is a common paradigm which has provided a useful frame to modeling many tasks in machine learning, ranging from natural language processing (e.g., part-of-speech (pos) tagging @xcite ) to protein structure prediction @xcite and weather pattern prediction @xcite . sequence labeling is fundamentally a structured prediction task -individual labels are not in gen-eral independent from one another, but should form a coherent label sequence. e.g., in weather pattern prediction, while the weather at a specific time point may be uncertain, it should still be highly correlated to the weather at nearby time points. in part-of-speech tagging, where an individual word like "duck" may have ambiguous pos in isolation, models strive to tag all words so that they obtain a grammatical global pos sequence. in recent years, research in nlp, but also beyond, has been dominated by the impressive developments in the area of neural networks. with the widespread success of llm encoders such as bert @xcite , a common approach is to represent the entire input sequence in the joint latent space of such an llm encoder, and to make independent predictions for each token conditioned on this joint latent representation. 1 with a sufficiently powerful encoder, models can try to sidestep the issue of modeling interactions between output labels by modeling the interactions at the level of the input sequence. however, the success of llms is predicated on both practical and conceptual factors. for these reasons, we believe that structured prediction, with its ability to cope with a larger typology of input languages, still warrants investigation as a general approach to modeling interactions between labels. in this paper, we extend linear-chain conditional random fields (crfs) @xcite , maybe the most established approach to modeling label-label interactions. within this framework, interactions between adjacent labels are directly modeled, but distant labels are assumed to only interact by proxy of their intervening labels. this conditional independence assumption makes crfs well-suited for modeling local interactions between labels, but leads to difficulties when longdistance interactions are important, such as in quotation detection @xcite but fundamentally unable to account for more global constraints in the interest of computational efficiency. a related class of models are (neural) weighted finite-state transducers or fsts @xcite @xcite . like crfs, weighted fsts define a distribution over label sequences conditioned on an input sequence, but they do so by modeling transitions through latent states. fsts also obey a markov assumption, but in their case, this is a conditional independence assumption on states, not on labels. while the state at a given time step depends directly only on the states of neighboring time steps, the output label at that time step may not be conditionally independent from distant output labels, depending on the structure and weights of the underlying automaton, and which paths through that automaton might explain those labels. this ability to model distant interactions makes weighted fsts more powerful than crfs but also computationally more demanding. when the underlying automaton is nondeterministic, inferring the most probable label sequence is np-hard @xcite . furthermore, it is often not obvious how to chose the crucial automaton structure in order to be sensitive to specific types of label-label interactions. in this paper, we propose regular-patternsensitive crfs (rpcrfs), a model architecture combining the strengths of crfs and fsts for sequence labeling. an rpcrf can be seen as a linear-chain crf equipped with the ability to be sensitive to specific types of long-distance interactions between labels. when instantiating a model, a user specifies a set of regular-expression label patterns, such that the resulting model will be able to punish or reward occurrences of those patterns at specific positions in the label sequence. in this way, particular types of long-distance interactions can be chosen in a task-specific manner, while the model is still free to learn how and when those interactions are important for sequence labeling. figure 1 illustrates how an rpcrf can model long-distance interactions through sensitivity to patterns. equivalently, rpcrfs are a framework for specifying automaton structures for fsts in an easily interpretable manner such that the resulting fst will be sensitive to exactly those longdistance interactions the user would like to model. unlike in the general-case for weighted fsts, an rpcrf will always define a deterministic automaton, support efficient exact inference like crfs. we first characterize rpcrfs formally, and discuss how one can be implemented as a linear-chain crf defined over an alternative label sequence. we then discuss the time-complexity of parameter estimation and inference. finally, we perform a number of experiments on synthetic data wherein we compare an rpcrf against a linearchain, demonstrating different types of nonlocal label structures an rpcrf can be made sensitive to through an appropriate choice of patterns. ## experiments to concretely demonstrate the differences between rpcrfs and linear-chain crfs, we perform three experiments with synthetic data, each demonstrating a particular class of problem where an rpcrf can model interactions not capturable by a linearchain crf. each experiment will feature a synthetic dataset exhibiting a certain type of label structure, and a pattern set designed to be sensitive to that label structure. as all labels are trivially independent under certainty (i.e. when all label probabilities are either zero or one), all synthetic data tasks are fundamentally underspecified, such that models will always need to "guess" the right answer from some space of possibilities. thus, for each experiment, in addition to reporting model performance, we will report the highest level of performance possible by a hypothetical model employing an optimal strategy. for all synthetic data experiments, we will use digits as input symbols, and letters and underscores as output labels, with the specific meanings of these symbols varying by experiment. for all experiments, the emission and pattern potential functions are represented with a bilstm neural network @xcite , and the transition function is represented as a parameter matrix. all parameters are jointly optimized until convergence using the adam optimizer @xcite . we evaluate all tasks via exact-match accuracy. that means that we count a model as correct only when it predicts the label sequence exactly correct, and we don't assign partial credit. this turns out to be quite important, as many less-strict evaluation methods are explicitly insensitive to the global structures we are trying to capture. for instance, when evaluating by token-wise accuracy, models are not rewarded for producing globally plausible label sequences, only for ensuring that each individual label is likely in isolation, something that linear-chain crfs are already capable of. ## related work our proposed approach is one of many ways for extending a linear-chain crf in a manner that selectively circumvents the markov assumption of default crfs. here we will briefly discuss some alternate formalisms for defining and working with such 'higher-order' crfs. pattern-based crfs. a conceptually similar approach to our current proposal are patternbased crfs @xcite . as with our regular-patternsensitive crfs, pattern-based crfs allow practitioners to specify a set of label patterns, allowing the crf to learn long-distance dependencies by either encouraging or discouraging the presence of these patterns at particular locations of the label sequence. however, the patterns in pattern-based crfs are limited to exact string matches, while our rpcrfs allow for arbitrary regular-expression patterns. critically, a pattern-based crf can only model dependencies as distant as its longest search pattern, while rpcrfs can easily be designed to learn dependencies over arbitrary distances, as our experiment 1 demonstrated. semi-markov crfs. another approach commonly used for allowing crfs to learn nonlocal label interactions are semi-markov crfs @xcite . under this formalism, rather than labeling each individual token, a semi-markov crf outputs a segmentation of the input, labeling each segment. while segment labels must follow the markov assumption (each segment's label depends directly only on its neighboring segments), the model's behavior within each segment may be non-markovian. such models offer an efficient approach to modeling certain types of nonlocal interactions, but these interactions are limited to occurring within the same segment, again in contrast to our model. ## conclusions this paper introduced regular-pattern-sensitive crfs, a method for enriching linear-chain crfs with the ability to learn long-distance interactions which occur within user-specified regularexpression patterns. by representing all patterns in a single state-labeled dfa, and using an auxiliary crf to represent a distribution over paths through this dfa, we can selectively extend crfs with non-local features while preserving efficient parameter learning and inference. regular patterns are often sufficient to model the relevant structures in the domain, as experiment 2 illustrates. more complex structures can often be rewritten with regular patterns by assuming a maximum input length (cf. @xcite and experiment 1). even when regular-language patterns cannot fully capture the dependency structure of the labels, and imperfect approximation can still yield a substantial improvement, as we found in experiment 3. regular patterns offer a flexible and powerful tool for incorporating domain knowledge into sequence classification models that combine the knowledge-based and data-driven paradigms in a promising fashion. sequence labeling models can be made to account for specific tasks' output structures by simply specifying regular-expression patterns, without the need to explicitly construct an fst or otherwise adapt the model architecture. a promising direction for future work lies in the combination of rpcrfs with llm encoders. the strengths of these two paradigms could prove complementary, and llms with rpcrf output layers may make good models for structured prediction tasks such as relation extraction or semantic role labeling, where it is necessary to model both linguistic interactions in the input as well as structural interactions in the output.