# Constraining Linear-chain CRFs to Regular Languages

arXiv: https://arxiv.org/abs/2106.07306 · HTML: https://mlsanity.com/paper/2106.07306/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 49 references that are in the map.
- First posted on arXiv 14 Jun 2021.

## Builds on (most cited first, 13 of 13)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [Neural Architectures for Named Entity Recognition](https://mlsanity.com/paper/1603.01360/) (2016)
- [Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search](https://mlsanity.com/paper/1704.07138/) (2017)
- [Guided Open Vocabulary Image Captioning with Constrained Beam Search](https://mlsanity.com/paper/1612.00576/) (2016)
- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [SparseMAP: Differentiable Sparse Structured Inference](https://mlsanity.com/paper/1802.04223/) (2018)
- [Neural Machine Translation Decoding with Terminology Constraints](https://mlsanity.com/paper/1805.03750/) (2018)
- [Dependency or Span, End-to-End Uniform Semantic Role Labeling](https://mlsanity.com/paper/1901.05280/) (2019)
- [A Span Selection Model for Semantic Role Labeling](https://mlsanity.com/paper/1810.02245/) (2018)
- [Efficient Markov Network Structure Discovery Using Independence Tests](https://mlsanity.com/paper/1401.3478/) (2014)

## Built on by (most cited first, 6 of 6)

- [Improving Aspect-Based Sentiment with End-to-End Semantic Role Labeling Model](https://mlsanity.com/paper/2307.14785/) (2023)
- [A fast and sound tagging method for discontinuous named-entity recognition](https://mlsanity.com/paper/2409.16243/) (2024)
- [Actor Identification in Discourse: A Challenge for LLMs?](https://mlsanity.com/paper/2402.00620/) (2024)
- [Regular-pattern-sensitive CRFs for Distant Label Interactions](https://mlsanity.com/paper/2411.12484/) (2024)
- [Strategies for political-statement segmentation and labelling in unstructured text](https://mlsanity.com/paper/2503.07179/) (2025)
- [PathCRF: Ball-Free Soccer Event Detection via Possession Path Inference from Player Trajectories](https://mlsanity.com/paper/2602.12080/) (2026)

## Abstract (arXiv)

A major challenge in structured prediction is to represent the interdependencies within output structures. When outputs are structured as sequences, linear-chain conditional random fields (CRFs) are a widely used model class which can learn textitlocal dependencies in the output. However, the CRF's Markov assumption makes it impossible for CRFs to represent distributions with textitnonlocal dependencies, and standard CRFs are unable to respect nonlocal constraints of the data (such as global arity constraints on output labels). We present a generalization of CRFs that can enforce a broad class of constraints, including nonlocal ones, by specifying the space of possible output structures as a regular language L. The resulting regular-constrained CRF (RegCCRF) has the same formal properties as a standard CRF, but assigns zero probability to all label sequences not in L. Notably, RegCCRFs can incorporate their constraints during training, while related models only enforce constraints during decoding. We prove that constrained training is never worse than constrained decoding, and show empirically that it can be substantially better in practice. Additionally, we demonstrate a practical benefit on downstream tasks by incorporating a RegCCRF into a deep neural model for semantic role labeling, exceeding state-of-the-art results on a standard dataset.