  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 \textit{local} dependencies in the output. However,
the CRF's Markov assumption makes it impossible for CRFs to represent
distributions with \textit{nonlocal} 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 $\mathcal{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 $\mathcal{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.
