Filtered Semi- M arkov CRF (2023)

Abstract: Semi-Markov CRF has been proposed as an alternative to the traditional Linear Chain CRF for text segmentation tasks such as Named Entity Recognition (NER). Unlike CRF, which treats text segmentation as token-level prediction, Semi-CRF considers segments as the basic unit, making it more expressive. However, Semi-CRF suffers from two major drawbacks: (1) quadratic complexity over sequence length, as it operates on every span of the input sequence, and (2) inferior performance compared to CRF for sequence labeling tasks like NER. In this paper, we introduce Filtered Semi-Markov CRF, a variant of Semi-CRF that addresses these issues by incorporating a filtering step to eliminate irrelevant segments, reducing complexity and search space. Our approach is evaluated on several NER benchmarks, where it outperforms both CRF and Semi-CRF while being significantly faster. The implementation of our method is available on Github.

## introduction sequence segmentation, the process of dividing a sequence into distinct, non-overlapping segments, has various applications, including named entity recognition and chinese word segmentation @xcite . in the past, this task has been approached as a sequence labeling problem using pre-defined templates, such as the bio and bilou schemes @xcite . the conditional random field (crf) @xcite has become a popular method for sequence labeling problems due to its ability to model the dependency between adjacent token tags. however, the crf model may not efficiently capture the underlying structure of the sequence, as it is limited to modeling relationships between individual tokens rather than segments. the semi-markov crf @xcite has been proposed as a variant of the crf, allowing for the incorporation of higher-level segment features, such as segment width. while the semi-crf allows for a more natural approach to sequence segmentation, it suffers from slower learning and inference due to its quadratic complexity with respect to the sequence length. additionally, the semi-crf often underperforms crf, showing only marginal improvements in some cases @xcite @xcite , which can be attributed to the semi-crf's significantly larger solution space, complicating the search for optimal solutions. to address the limitations of semi-crf, we propose filtered semi-crf, which introduces a filtering step to prune irrelevant segments using a lightweight local segment classifier. by leveraging transformer-based features, such as bert @xcite , this classifier can identify high-quality candidate segments. consequently, the task of the semi-crf is simplified to selecting the best segments from the pool of high-quality candidates. our experiments demonstrate that this filtering step not only accelerates the decoding process but also improves the overall model performance. although pruning techniques have been applied to accelerate parsing algorithms @xcite , they often involve a trade-off between accuracy and inference speed. in contrast, our filtering approach is learned jointly and collaboratively with the semi-crf during training, resulting in a model that not only increases efficiency but also improves overall performance. when evaluated on named entity recognition, our model significantly outperforms both the crf and semi-crf, achieving f1 score improvements of up to 2.5 and 1.1 points, respectively, on the conll 2003 dataset. additionally, our model also accelerates the decoding process to a speed that can be up to 20 times and 137 times faster than crf and semi-crf, respectively. ## filtered semi-markov crf in this section, we propose an alternative model to semi-crf, named filtered semi-crf, which aims to address two fundamental weaknesses of the original model. first, the semi-crf is not wellsuited for long texts due to its quadratic complexity and the prohibitively large search space. secondly, in tasks such as named entity recognition (ner), where certain segments are labeled as null (representing non-entity segments), the semi-crf graph can create multiple redundant paths, all leading to the same set of entities. for instance, consider the scenario described in § 2.3. in this scenario, multiple segmentations, such as @xmath0,2,per), (3,3,o), (4,4,o), (5,6,org)] or @xmath1,2,per), (3,4,o), (5,6,org)], would yield the same final set of labeled entities, specifically (1,2, per) and (5,6,org) in this case. to remedy these shortcomings, our proposed model incorporates a filtering step that eliminates irrelevant segments using a lightweight local classifier. by leveraging transformer-based features, this classifier effectively selects high-quality candidate segments, significantly reducing the task of the semi-crf to merely choosing the best among already highquality candidates. ## training in this section, we present our fsemicrf training which involves updating the whole model parameters to minimize the following loss function: here, l local and l global represent the filtering loss and the segmentation loss, respectively. ## main results fsemicrf vs. crf and semi-crf as shown in comparison to pior works in our work, we mainly compare our approach with previous work that we consider comparable, i.e. that uses sentence-level context and the same backbone model. as shown in the ## ablation study semi-crf + unit null we study a variation of the semi-crf that only allows for the use of null labels for unit length segments. to do this, we simply modify the original semi-crf by eliminating/masking segmentation paths that contain null segments with a size greater than one. the motivation for this study is to fix the multiple redundant paths problem of the semi-crf ( § 3). the results show that this approach improves performance on most of the datasets, but still does not perform as well as the other methods, thus validating the importance of segment filtering. fsemicrf w/o global loss we investigate the impact of removing the global loss (eq. 14) component on our fsemicrf model, resulting in a local span classfication model. the results are presented in ## conclusion in this paper, we introduce filtered semi-crf, a novel algorithm for text segmentation tasks. by applying our method to ner, we show substantial performance gains over traditional crf and semi-crf models on several datasets. additionally, our algorithm exhibits improved efficiency, speed, and scalability compared to the baselines. as future work, we plan to investigate the extension of filtered semi-crf to nested segment structures.