In structured prediction,
a major challenge for models is to represent the interdependencies
within their output structures.  For the common case where outputs are
structured as a sequence, linear-chain conditional random fields
(CRFs) are a widely used model class which can learn local
dependencies in output sequences.  However, the CRF's Markov
assumption makes it impossible for these models to capture 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 $\Lang$. 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 $\Lang$. 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 using synthetic data
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.

§ INTRODUCTION

Structured prediction is a field of machine learning where
outputs are expected to obey some predefined discrete
structure. Instances of structured prediction with various output
structures occur in many applications, including computer vision
(e.g., scene graph generation [Johnson et al., 2015] with
graph-structured output), natural language processing (e.g.,
linguistic parsing [Niculae et al., 2018] with tree-structured
output, relation extraction [Roth and Yih, 2004] with
tuple-structured output) or modeling the spatial structure of physical
entities and processes [Jiang, 2020].

A key difficulty faced by all models is to tractably model
interdependencies between different parts of the output.  As output
spaces tend to be combinatorially large, special techniques,
approximations, and independence assumptions must be used to work with
the associated probability distributions. Considerable research has
investigated specific structures for which such approaches make
machine learning tractable.  For instance, when outputs are trees over
a fixed set of nodes, maximal arborescence algorithms allow for exact
inference [Chu, 1965, Edmonds, 1967]; when outputs are
graph-structured, loopy belief propagation can be used for approximate
inference [Murphy et al., 1999].

In the specific case where outputs are structured as a linear
sequence, a commonly made independence assumption is the Markov
assumption. This requires that model outputs depend only on their
immediate neighbors, and do not depend directly on more distant ones.
A common model that makes use of this assumption is the linear-chain
conditional random field (CRF) [Lafferty et al., 2001], which
has found ubiquitous use across common sequence labeling tasks,
including part-of-speech tagging [Gimpel et al., 2011] and named entity
recognition [Lample et al., 2016]. This model became popular
with the use of hand-crafted feature vectors in the 2000s, and is
nowadays commonly used as an output layer in neural networks to
encourage the learning of structural properties of the output

The Markov assumption makes training tractable, but also limits the
CRF's expressive power, which can hamper performance, especially for
long sequences [Scheible et al., 2016].  Semi-Markov CRFs
[Sarawagi and Cohen, 2004] and skip-chain CRFs
[Sutton and McCallum, 2004] are techniques for relaxing the Markov
assumption, but both come with drawbacks in performance and

In this work, we propose a new method to tractably relax the Markov
assumption in CRFs.
Specifically, we show how to constrain the output of CRFs to a
regular language, such that the resulting
regular-constrained CRF (RegCCRF) is guaranteed to output
label sequences from that language. Since regular languages can encode
long-distance dependencies between the symbols in their strings,
RegCCRFs provide a simple model for structured prediction that
provides a guarantee to respect these non-local constraints. The
domain knowledge specifying these constraints is defined via regular
expressions, a straightforward, well understood formalism.

We show that our method is distinct from the common family of
approaches that enforce constraints at decoding time, and that our
constrained training approach better approximates the true data
distribution. We also test our method empirically as the output layer
of a neural network, and attain state-of-the-art performance for
semantic role labeling on the OntoNotes corpus [Weischedel et al., 2011, Pradhan et al., 2012]. To encourage the use of RegCCRFs, we release our code
as a Python library under the Apache 2.0 license,
to be used as a drop-in replacement for traditional CRFs in PyTorch
[Available at <https://www.ims.uni-stuttgart.de/data/regccrf>]

§ RELATED WORK

We identify three areas of structured prediction that are particularly
relevant to our current work: constrained decoding, which can enforce
output constraints at decoding time, techniques for weakening the Markov
assumption of CRFs to learn long-distance dependencies,
and structure learning for learning constraints from data in graphical models.

Constrained decoding.

A common approach to enforcing constraints in model output is
constrained decoding: Models are trained agnostic to
constraints, but during decoding it is ensured that the model output
satisfies the constraints.  This almost always corresponds to finding
or approximating a conditionalized version of the model's
distribution, conditionalized on the output obeying the specified
constraints.  We discuss constrained coding as it relates to RegCCRFs
in Section <ref>.

For CRFs, Kristjansson et al., 2004 present constrained
conditional random fields, which can enforce that
particular tokens either are or are not assigned particular labels
(positive and negative constraints, respectively). They propose a
constrained Viterbi algorithm for MAP inference and a constrained
forward-backward algorithm for marginal inference. In their
task, interactive information extraction, constraints are not
available at training time, and so they focus on constrained
decoding.  Formally, our work is a strict generalization of
this approach, as position-wise constraints can be formulated as a
regular language, but regular languages go beyond position-wise

Other existing works treat decoding with constraints as a search
problem, searching for the most probable decoding path which satisfies
all constraints.  In one example of this approach, [He et al., 2017]
train a neural network to predict token-wise output probabilities for
semantic role labeling following the BIO label-alphabet [Ramshaw and Marcus, 1999],
and then use
exact A* search to ensure that the output forms a valid BIO sequence
and that particular task-specific constraints are satisfied. For
autoregressive models, constrained beam search
[Hokamp and Liu, 2017, Anderson et al., 2017, Hasler et al., 2018] can enforce regular-language constraints
during search.

Markov relaxations.

While our approach can relax the Markov assumption of CRFs
through nonlocal hard constraints,
another strand of work has developed models which can directly
learn nonlocal dependencies in CRFs:

Semi-Markov CRFs [Sarawagi and Cohen, 2004] relax the
Markov property to the semi-Markov property.
In this setting, CRFs are tasked with
segmentation, where individual segments may depend only on their
immediate neighbors, but model behavior within a particular segment
need not be Markovian. As such, semi-Markov CRFs are capable of
capturing nonlocal dependencies between output variables, but only to
a range of one segment and inside of a segment.

Skip-chain CRFs [Sutton and McCallum, 2004] change the
expressiveness of CRFs by relaxing the assumption that only the linear
structure of the input matters: they add explicit dependencies between
distant nodes in an otherwise linear-chain CRF. These dependencies are
picked based on particular properties, e.g., input variables of the
same value or which share other properties. In doing so, they add
loops to the model's factor graph, which makes exact training and
inference intractable, and leads to the use of approximation
techniques such as loopy belief propagation and Gibbs sampling.

Structure learning for graphical models.
While our work focuses on incorporating known constraints into machine
learning methods, a related task is learning in the face of unknown
constraints, which must be learned from the data.  In the field of
probabilistic graphical models, this is most naturally framed as
structure learning. As the graphical model's graph structure encodes
conditional independence information between variables, learning that
graph structure can be seen as learning potential constraints.  Graph
structures can be learned globally, as in Lee et al., 2007
and Schmidt et al., 2008, or independence relationships can
be estimated locally, as in Bromberg et al., 2009.

§ PRELIMINARIES AND NOTATION

As our construction involves finite-state automata and conditional random
fields, we define these here and specify the notation we will use in
the remainder of this work.

§.§ Finite-state automata

All automata are taken to be nondeterministic finite-state automata (NFAs) without epsilon transitions.
Let such an NFA be defined as a 4-tuple $(\Sigma, Q, F, E)$,

* $\Sigma = \{a_1, a_2, ..., a_{|\Sigma|}\}$ is a finite alphabet
of symbols,

* $Q = \{q_1, q_2, ..., q_{|Q|}\}$ is a finite set of states. By convention, $q_1$ is the sole starting state.

* $F\subseteq Q$ is a set of accepting states.

* $E \subseteq Q \times \Sigma \times Q$ is a set of directed,
symbol-labeled edges between states.  These edges define the NFA's
transition function $\Delta: Q \times \Sigma \rightarrow 2^Q$,
with $r \in \Delta(q, a) \leftrightarrow (q, a, r) \in E$.

An automaton is said to accept a string $\bm{s} \in \Sigma^*$ if there exists a contiguous path of edges from $q_1$ to some
accepting state whose edge labels are exactly the symbols of $\bm{s}$.
The language defined by an automaton is the set of all such accepted strings.
A language is regular if and only if it is the language of some NFA.

§.§ Linear-chain conditional random fields

Linear-chain conditional random fields (CRFs)
[Lafferty et al., 2001] are a sequence labeling model.
Parameterized by $\theta$, they use a global exponential model to
represent the conditional distribution over label sequences
$\y = \langle y_1, y_2, ..., y_t \rangle$ conditioned on input
sequences $\x = \langle x_1, x_2, ..., x_t \rangle$:

\begin{equation}
\label{eqn:expmodel}
\Pu \propto \exp \sum_j f_{\theta}^j(\x, \y),
\end{equation}

with individual observations $x_i$ coming from some observation space
$X$, and outputs $y_i$ coming from
some finite alphabet $Y$. In this
work, we use CRFs for sequence labeling problems, but the dataset
labels do not correspond directly to the CRF's outputs $y_i$.  In
order to avoid ambiguity, and since the term “state” already has a
meaning for NFAs, we call $\y$ the CRF's tag sequence, and
each $y_i$ a tag. The terms label sequence and
label will thus unambiguously refer to the original dataset

Each $f_\theta^j$ is a potential function of $\x$ and $\y$,
parameterized by $\theta$.  Importantly, in a linear-chain CRF, these
potential functions are limited to two kinds: The transition
function $g_{\theta}(y_i, y_{i+1})$ assigns a potential to each
pair $(y_i, y_{i+1})$ of adjacent tags in $\y$, and the
emission function $h_{\theta}(y_i\mid\x, i)$ assigns a
potential to each possible output tag $y_i$ given the observation
sequence $\x$ and its position $i$.

With these, the distribution defined by a CRF is

\begin{equation}
\Pu \propto \exp \left(\sum_{i=1}^{t-1} g_{\theta}(y_i, y_{i+1}) + \sum_{i=1}^{t} h_{\theta}(\x,y_i,i)\right).
\end{equation}

Limiting our potential functions in this way imposes a Markov
assumption on our model, as potential functions can only depend on a
single tag or a single pair of adjacent tags.  This makes learning and
inference tractable: the forward algorithm [Jurafsky and Martin, 2009] can
calculate negative log-likelihood loss during training, and the
Viterbi algorithm [Viterbi, 1967, Jurafsky and Martin, 2009] can be used for
inference.  Both are linear in $t$, and quadratic in $|Y|$ in both
time and space.

In practice, the transition function $g_{\theta}$ is represented
explicitly as a $|Y|\times|Y|$ parameter matrix, and the emission
function $h_{\theta}$ can be an arbitrary learnable function –
increasingly commonly represented as a deep neural network.

§ REGULAR-CONSTRAINED CRFS

Given a regular language $\Lang$, we would like to
constrain a
CRF to $\Lang$.  We formalize this notion of constraint with
conditional probabilities – a CRF constrained to $\Lang$ is described
by a (further) conditionalized version of that CRF's distribution $\Pu$, conditioned
on the event that the tag  sequence $\y$ is in $\Lang$.
We write this distribution as

\begin{equation}
\Pc = \begin{cases}
\alpha \cdot \Pu & \text{if } \y \in \Lang \\
0 & \text{otherwise},\\
\end{cases}
\end{equation}

with $\alpha \geq 1$ defined as $\alpha = \frac{1}{\sum_{\y \in \Lang} \Pu}$.

In order to utilize this distribution for machine learning, we
need to be able to compute log-likelihood losses and perform MAP
inference.  As discussed in Section <ref>, both of these are
efficiently computable for CRFs.  Thus, if we can construct a separate
CRF whose output distribution can be interpreted as
$P(\y\mid\x, \Lang)$, both of these operations will be available.  We
do this in the next section.

§.§ Construction

[->,>=stealth',shorten >=1pt,auto,node distance=2.8cm,

inpath=[draw=ForestGreen, ultra thick, fill=ForestGreen]

[initial,accepting,state] at (0, 0) (q1) $q_1$;
[state] at (3, 0) (q2)  $q_2$;
[accepting,state] at (0, -2) (q3)  $q_3$;
[state] at (3, -2) (q4)  $q_4$;

(q1)  edge [loop above] node O (q1);
[inpath, preaction=draw,line width=1mm] (q1)  edge  node B (q2);
(q2)  edge [loop above] node I (q2);
[inpath] (q2) edge node O (q4);
(q4)  edge [loop below] node O (q4);
[inpath] (q4)  edge node B (q3);
(q2)  edge [bend left=15] node B (q3);
(q3)  edge [bend left=15] node B (q2);
[inpath] (q3)  edge [loop below] node I (q3);
(q3)  edge node O (q1);

[-] (5,.5) – (5,-2.5);

var=[draw, circle, minimum size=1cm, inner sep=0cm]
factor=[draw, rectangle, fill=white]

[var] at (0, 0) (y1) $\edge{q_1}{B}{q_2}$;
[var] at (4, 0) (y2) $\edge{q_2}{O}{q_4}$;
[var] at (8, 0) (y3) $\edge{q_4}{B}{q_3}$;
[var] at (12, 0) (y4) $\edge{q_3}{I}{q_3}$;
[var, given] at (6, 3) (x) $\x$;
(x) – (y1) node [midway, factor] $h_\theta(\x,\text{B}, 1)$;
(x) – (y2) node [midway, factor] $h_\theta(\x,\text{O}, 2)$;
(x) – (y3) node [midway, factor] $h_\theta(\x,\text{B}, 3)$;
(x) – (y4) node [midway, factor] $h_\theta(\x,\text{I}, 4)$;
(y1) – (y2) node [midway, factor] $g_\theta(\text{B}, \text{O})$;
(y2) – (y3) node [midway, factor] $g_\theta(\text{O}, \text{B})$;
(y3) – (y4) node [midway, factor] $g_\theta(\text{B}, \text{I})$;

$Y' = \left\{\edge{q_1}{O}{q_1}, \edge{q_1}{B}{q_2}, \edge{q_2}{I}{q_2}, \edge{q_2}{B}{q_3}, \edge{q_2}{O}{q_4}, \edge{q_3}{O}{q_1}, \edge{q_3}{B}{q_2}, \edge{q_3}{I}{q_3}, \edge{q_4}{B}{q_3}, \edge{q_4}{O}{q_4}\right\}$

Example for a RegCCRF, showing NFA and unrolled factor
graph. $\Lang$ describes the language
$(\text{O}\mid\text{BI}^*\text{O}^*\text{BI}^*)^*$, the language of
valid BIO sequences for an even number of spans.  We would like to
calculate $\Pc$ for
$\y = \langle \text{B}, \text{O}, \text{B}, \text{I} \rangle$.  We
show an unambiguous automaton $M$ for $\mathcal{L}$ (left), and a
factor graph (right) for the auxiliary CRF computing
$P_\theta(\bm{y'}\mid\x)$, where $\bm{y'} \in Y'^*$ corresponds to
the sole accepting path of $\y$ through $M$ (marked).

Let $M := (\Sigma, Q, F, E)$ be an NFA that describes $\Lang$.  We
assume that $M$ is unambiguous – i.e., every
string in $\Lang$ is accepted by exactly one path through $M$.  As
every NFA can be transformed into an equivalent unambiguous NFA
[Mohri, 2012], we can make this assumption with no
loss of generality.

Our plan is to represent $\Pc$ by constructing a separate CRF with a
distinct tag set, whose output sequences can be interpreted directly
as paths through $M$. As $M$ is unambiguous, each label sequence in
$\Lang$ corresponds to exactly one such path.  We parameterize this
auxiliary CRF identically to our original CRF – that is, with a
label-wise (not tag-wise) transition and emission functions. Thus, for
all parameterizations $\theta$, both distributions $\Pu$ and $\Pc$ are
well defined.

There are many ways to construct such a CRF.  As CRF training and
inference are quadratic in the size of the tag set $Y$, we would
prefer a construction which minimizes $|Y|$.  However, for clarity, we
will first present a conceptually simple construction, and then
discuss approaches to reduce $|Y|$.

We start with our original CRF, parameterized by $\theta$, with tag
set $Y = \Sigma$, transition function $g_\theta$, and emission
function $h_\theta$, describing the probability distribution
$\Pu$, $\y \in \Sigma^*$.  From this, we construct a new CRF, also
parameterized by the same $\theta$, but with tag set $Y'$, transition
function $g'_\theta$, and emission function $h'_\theta$. This
auxiliary CRF describes the distribution $P'_\theta(\bm{y'}\mid\x)$
(with $\bm{y'} \in Y'^*$), which we will be able to interpret as
$\Pc$.  The construction is as follows:

\begin{gather}
Y' = E \\
g'_{\theta}((q, a, r),(q', a', r')) =
\begin{cases}
g_{\theta}(a, a') & \text{if } r = q'\\
-\infty & \text{otherwise} \\
\end{cases} \\
h'_{\theta}(\x, (q, a, r), i) = \begin{cases}
-\infty & \text{if } i = 1, q \neq q_1\\
-\infty & \text{if } i = t, r \not\in F\\
h_{\theta}(\x, a, i) & \text{otherwise.}\\
\end{cases}
\end{gather}

This means that the tags of our new CRF are the edges of $M$, the
transition function assigns zero probability to transitions between
edges which do not pass through a shared NFA state, and the emission
function assigns zero probability to tag sequences which do not begin
at the starting state or end at an accepting state.  Apart from these
constraints, the transition and emission functions depend only on edge
labels, and not on the edges themselves, and agree with the standard
CRF's $g_\theta$ and $h_\theta$ when
no constraints are violated.

As $M$ is unambiguous, every tag sequence $\y$ corresponds
to a single path through $M$, representable as an edge sequence
$\bm{\pi} = (\pi_1, \pi_2, ..., \pi_t), \pi_i \in E$.  Since this path is a
tag sequence for our auxiliary CRF, we can directly calculate the
auxiliary CRF's $P'_\theta(\bm{\pi}\mid\x)$.  From the construction of
$g'_\theta$ and $h'_\theta$, this must be equal to $\Pc$, as it is
proportional to $\Pu$ for $\y \in \Lang$, and zero (or, more
correctly, undefined) otherwise.  Figure <ref>
illustrates this construction with a concrete example.

§.§ Tag-set minimization

As the Viterbi and forward algorithms are quadratic in $|Y|$,
very large tag sets can lead to performance issues during training and inference.
To alleviate this, we would like $|Y|$ to be as
small as possible. Without changing $\Lang$, there are two approaches we can
take here:

First, we can select $M$ to have as few edges as possible. This
problem for unambiguous NFAs is NP-complete in the general case
[Jiang and Ravikumar, 1991], and, assuming $\text{P} \neq \text{NP}$, is
not even efficiently approximable
[Gruber and Holzer, 2007]. Nonetheless, in practice many
languages can be minimized manually, and heuristic
approaches can reduce, if not minimize, the size of NFAs.

Second, we can reduce the size of $|Y|$ by adjusting our construction.
Instead of making each edge of $M$ a tag, we can adopt equivalence
classes of edges.  Reminiscent of standard NFA minimization, we define
$(q, a, r) \sim (q', a', r') \leftrightarrow (q, a) = (q', a')$. When
constructing our CRF, whenever a transition would have been allowed
between two edges, we allow a transition between their corresponding
equivalence classes.  We do the same to determine which classes are
allowed as initial or final tags.  As each equivalence class
corresponds (non-uniquely) to a single symbol $a$, we can translate
between tag sequences and strings of $\mathcal{L}$ just as before.

§ CONSTRAINED TRAINING VS. CONSTRAINED DECODING

Our construction suggests two possible use cases for a RegCCRF:
constrained decoding, where a CRF is trained unconstrained, and
the learned weights are then used in a RegCCRF at decoding time, and
constrained training, where a RegCCRF is both trained and decoded
with constraints.
In this section, we compare between these two approaches and a standard,
unconstrained CRF.
We assume a machine learning
setting where we have access to samples from some data distribution
$\widetilde{P}(\x, \y)$, with each $\x \in X^*$, and each $\y$ of
matching length in some regular language $\Lang \subseteq{\Sigma^*}$.
We wish to model the conditional distribution
$\widetilde{P}(\y\mid\x)$ with either a CRF or a RegCCRF, by way of minimizing the
cross-entropy between model and data distributions.

The unconstrained CRF corresponds to a CRF that has been trained, without constraints,
on data points from $\widetilde{P}(\x, \y)$, and is subsequently used
directly. As such, it makes no use of the language $\Lang$.
The model's output distribution is $\Pu[\thetau]$, with parameter

\begin{equation}
\thetau = \argmin_\theta \E{- \ln \Pu}
\label{eq:thetau}
\end{equation}

minimizing CRF cross-entropy with the data distribution.

In constrained decoding, a CRF is trained unconstrained,
but its weights are used in a RegCCRF at decoding time. The output distribution
of such a model is
It is parameterized by the same
parameter vector $\theta_u$ as the unconstrained CRF, as the training procedure is
identical, but the output distribution is conditioned on $\y \in \Lang$.

Constrained training involves directly optimizing a
RegCCRF's output distribution, avoiding any asymmetry between training and decoding time.
In this case, the output distribution of the model is $\Pc[\thetac]$,

\begin{equation}
\theta_c = \argmin_\theta \E{-\ln \Pc}
\end{equation}

is the parameter vector which minimizes the RegCCRF's cross-entropy
with the data distribution.

In the remainder of this section, we will demonstrate that these three approaches
form a hierarchy of sorts, when compared by their ability to match the data distribution.
In particular, when compared by cross-entropy, we show that

\begin{equation}
H_\text{unconstrained} \geq H_\text{constrained decoding} \geq H_\text{constrained training},
\end{equation}

with each $H$ corresponding to that model's cross-entropy with the data distribution.
This suggests we should prefer the constrained training regimen.

An unconstrained CRF cannot outperform constrained decoding.
Here we compare the distributions $\Pu[\thetau]$ and $\Pc[\thetau]$.
We wish to demonstrate that $\Pu[\thetau]$ can never achieve lower cross-entropy
with the data distribution than $\Pc[\thetau]$, and that the two distributions
achieve identical cross-entropy only when $\Pu[\thetau] = \Pc[\thetau]$ i.e. when constraints have no effect.
We demonstrate the more general case for arbitrary $\theta$.
Since every $\y$ in $\widetilde{P}$ is in $\Lang$,

\begin{equation}
\Pc = \alpha \cdot \Pu,
\end{equation}

with $\alpha \geq 1$.
Thus, the cross-entropy of the regular-constrained CRF is

\begin{equation}
\E{- \ln \Pc} = \E{- \ln \Pu} - \ln \alpha.
\end{equation}

This differs from the cross-entropy of the unconstrained CRF only by the term $- \ln \alpha$.
As $\alpha \geq 1$, the regular-constrained CRF's cross-entropy is less than or equal to that of the unconstrained CRF,
with equality only when $\alpha = 1$ and therefore $\Pu = \Pc$.

Constrained decoding cannot outperform constrained training.
In this case, we compare the distributions $\Pc[\thetau]$ and $\Pc[\thetac]$.
We will demonstrate that the former
can never outperform the latter, again as measured by cross-entropy with the data distribution.

This follows directly from our definitions, as we
define $\thetac$ to minimize cross-entropy between $\Pc$ and the data
distribution.  Thus, $\Pc[\thetau]$ could never yield a lower cross-entropy
than $\Pc[\thetac]$, as that would contradict our definition of $\thetac$.

§ SYNTHETIC DATA EXPERIMENTS

While we have shown that constrained training cannot underperform
constrained decoding, the conditions where it is strictly better
depend on exactly how the partition and emission functions are
parameterized, and are not easily stated in general terms.  In this
section, we compare the two regimens empirically to demonstrate
simple cases where the two are not equivalent.

The procedure is similar for both synthetic data experiments.  For
each experiment, we specify a regular language $\Lang$, an observation
alphabet $X$, and a joint data distribution $\widetilde{P}(\x, \y)$
over observation sequences in $X^*$ and label sequences in $\Lang$.
We then train two models, one with a RegCCRF, parameterized by
$\theta_{c}$, and one with an unconstrained CRF, parameterized by
$\theta_{u}$.  For each model, we initialize parameters randomly,
then use stochastic gradient descent to minimize cross-entropy with $\widetilde{P}$.
We directly generate samples from
$\widetilde{P}$ to use as training data.  After optimizing
$\theta_{c}$ and $\theta_{u}$, construct a RegCCRF with $\theta_u$
for use as a constrained-decoding model, and we compare the constrained-training
distribution $\Pc[\theta_c]$ with the constrained-decoding
distribution $\Pc[\theta_u]$.

We use a simple architecture for our models, with both the transition functions
$g_\theta$ and emission functions $h_\theta$ represented as parameter matrices.
We list training hyperparameters in the Appendix <ref>.

§.§ Arbitrary differences in cross-entropy

Model output probabilities, and cross-entropy with the data
distribution, plotted against sequence length $k$.  As $k$
increases, constrained decoding becomes a progressively worse
approximation for the data distribution, while constrained training
is consistently able to match the data distribution.

We would like to demonstrate that, when comparing constrained training
to constrained decoding in terms of cross-entropy with the data
distribution, constrained training can outperform constrained decoding
by an arbitrary margin.  We choose
$\Lang = (\texttt{ac})^*\mid(\texttt{bc})^*$ to make conditional
independence particularly relevant – as every even-indexed label is
, an unconstrained CRF must model odd-indexed labels
independently, while a constrained CRF can use its constraints to
account for nonlocal dependencies.  For simplicity, we hold the input
sequence constant, with $X = \{\texttt{o}\}$.

Our approach is to construct sequences of various lengths. For $k \in \mathbb{N}$, we let our data distribution be

\begin{equation}
\widetilde{P}(\texttt{o}^{2k}, (\texttt{ac})^k) = \frac{3}{4} \text{
and }
\widetilde{P}(\texttt{o}^{2k}, (\texttt{bc})^k) = \frac{1}{4}.
\end{equation}

We train and evaluate individual models for each sequence lengths
Figure <ref> plots model probabilities and
cross-entropies for various $k$.  We see that, regardless of $k$,
$\Pc[\theta_c]$ is able to match $\widetilde{P}(\y\mid\x)$ almost
exactly, with only small deviations due to sampling noise in SGD.  On
the other hand, as sequence length increases, $\Pc[\theta_u]$ becomes
progressively “lop-sided”, assigning almost all of its probability
mass to the string $(\texttt{ac})^k$.  This behavior is reflected the
models' cross-entropies with the data distribution – constrained
training stays at near-constant cross-entropy for all $k$, while the
cross-entropy of constrained decoding grows linearly with $k$.

§.§ Differences in MAP inference

We show here that constrained training and constrained decoding can disagree
about which label sequence they deem most likely.
Furthermore, in this case, MAP inference agrees with the data distribution's
mode for constrained training, but not for constrained decoding.
To do this, we construct a fixed-length output language
$\Lang = \texttt{acd}\mid\texttt{bcd}\mid\texttt{bce}$, where an
unconstrained CRF is be limited by the Markov property to predict $\y$'s prefix
and suffix independently.
We select our data distribution,

\begin{equation}
\widetilde{P}(\texttt{ooo}, \texttt{acd}) = 0.4 \text{ and }
\widetilde{P}(\texttt{ooo}, \texttt{bcd}) = 0.3 \text{ and }
\widetilde{P}(\texttt{ooo}, \texttt{bce}) = 0.3,
\end{equation}

to be close to uniform, but with one label sequence holding
the slight majority, and we ensure that the majority label sequence is not
the label sequence with both the majority prefix and the majority suffix (i.e. ).
As before, we hold the observation sequence as a constant ($\texttt{ooo}$).
We train a constrained and an unconstrained CRF to convergence, and compare $\Pc[\thetau]$
to $\Pc[\thetac]$.

Output distributions for constrained decoding ($\Pc[\thetau]$)
and constrained training ($\Pc[\thetac]$), compared to the data distribution $\widetilde{P}(\y\mid\x)$.
Constrained decoding cannot learn the data distribution exactly, and yields a
mode which disagrees with that of the
data distribution.

$\y$     $\widetilde{P}(\y\mid\x)$     $\Pc[\thetau]$     $\Pc[\thetac]$

0.4     0.32     0.40

0.3     0.48     0.30

0.3     0.20     0.40

Table <ref> shows $\Pc[\thetau]$ and $\Pc[\thetac]$ as they compare to
We find that, while the mode of $\widetilde{P}(\y\mid\x)$ is ,
the mode of constrained decoding distribution $\Pc[\thetau]$ is ,
the string with the majority prefix and the majority suffix.  Conversely, the constrained
training distribution $\Pc[\thetac]$ matches the data distribution almost
exactly, and predicts the correct mode.

§ REAL-WORLD DATA EXPERIMENT: SEMANTIC ROLE LABELING

Task. As a final experiment, we apply our RegCCRF to the
NLP task of semantic role labeling (SRL) in the popular PropBank
framework [Palmer et al., 2005]. In line with previous
work, we adopt the known-predicate setting, where events are
given and the task is to mark token spans as (types of) event
participants. PropBank assumes 7 semantic core roles (ARG0
through ARG5 plus ARGA) plus 21 non-core roles for modifiers
such as times or locations. For example, in [$_{\text{ARG0}}$
Peter] saw [$_{\text{ARG1}}$ Paul]
[$_{\text{ARGM-TMP}}\, \textit{yesterday}]$, the argument labels
inform us who does the seeing (ARG0), who is seen (ARG1), and when the
event took place (ARGM-TMP). In addition, role spans may be labeled as
continuations of previous role spans, or as
references to another role span in the sentence.

SRL can be framed rather naturally as a sequence labeling task
[He et al., 2017]. However, the task comes with a number of hard
constraints that are not automatically satisfied by standard CRFs,
namely: (1) Each core role may occur at most once per event; (2)
continuations require that the same span type occurs previously in the
sentence; (3) references require that the same span type occurs
elsewhere in the sentence (before or after).

Data. In line with previous work
[Ouchi et al., 2018], we work with the OntoNotes corpus as
used in the CoNLL 2012 shared task[
As downloaded from <https://catalog.ldc.upenn.edu/LDC2013T19>, and
preprocessed according to <https://cemantix.org/data/ontonotes.html>
[Weischedel et al., 2011, Pradhan et al., 2012],
whose training set comprises 66 roles (7 core roles, 21 non-core roles,
19 continuation types, and 19 reference types).

Model. To encode the three constraints listed above in a
RegCCRF, we define a regular language describing valid BIO
sequences [Ramshaw and Marcus, 1999] over the 66 roles. A minimal
unambiguous NFA for this language has more than
$2^2\cdot3^{19}$ states, which is too large to run the Viterbi
algorithm on our hardware.  However, as many labels are very rare,
we can shrink our automaton by discarding them at the cost of
imperfect recall. We achieve further reductions in size by ignoring
constraints on reference roles, treating them identically to non-core
roles. Our final automaton recognizes 5 core role types (ARG0 through
ARG4), 17 non-core / reference roles, and one continuation role type
(for ARG1). This automaton has 672 states, yielding a RegCCRF with
2592 tags.

Our model is then given by this RegCCRF, trained constrained, with emission scores provided
by a linear projection of the output of a pretrained RoBERTa network
[Liu et al., 2019].  In order to provide the model with event information,
the given predicates are prefixed by a special reserved token in the input
sequence. RoBERTa parameters are fine-tuned during the
learning of transition scores and projection weights – a full
description of the training procedure is provided in the Appendix <ref>.

As RegCCRF loss is only finite for label sequences in $\Lang$, we must
ensure that our training data do not violate our constraints.  For the
roles which we discard, we simply remove the offending labels from the
training data. In six cases, training instances directly conflict with
the constraints specified — all of these cases involve continuation
roles missing a valid preceding role.  We discard these instances.

Baseline. As a baseline model, we use the same
architecture with a standard CRF replacing the RegCCRF. Since for this
baseline, we are not limited by GPU memory, we include all role
types present in the training set, and use the complete training set.

Results and analysis.
We evaluate both regular-constrained and unconstrained CRF models against the
evaluation partition, and measure performance using $F_1$ score for exact span
For comparability with prior work, we use the evaluation script[As
available from <https://www.cs.upc.edu/ srlconll/soft.html>.]
for the CoNLL-2005 shared task [Carreras and Màrquez, 2005].
These results, averaged over five trials, are presented in Table <ref>.

Both our RegCCRF and the unconstrained CRF baseline outperform the
existing state-of-the-art ensemble model
[Ouchi et al., 2018]. We ascribe this improvement over the
existing literature to our use of RoBERTa – prior work in SRL tends
to rely on ELMo [Peters et al., 2018], which has been show to
do worse than pretrained transformer-based models in downstream tasks
[Devlin et al., 2019].

Between our RegCCRF and baseline models, we find that the former
significantly[All significance results are at the $p<0.05$
level, as measured by a two-tailed permutation test.]  outperforms
the latter in terms of $F_1$ score. This is despite the fact that our
RegCCRF is unable to predict rare role types, while the CRF has no
such limitation. In fact, just under 1% of all role spans in the test
data are of a type not included in the RegCCRF, leaving it with a
theoretical maximum of 99% recall. Nonetheless, our RegCCRF actually
achieves a higher average recall than the CRF, though this difference
is not significant. In contrast, unsurprisingly, the RegCCRF show
significantly better precision than the CRF.
No single model from the literature beats the RegCCRF in precision, only
the ensemble of [Ouchi et al., 2018].

Results from our experiments (averaged over 5 trials), along with selected
reported results from recent literature.

Model    Precision     Recall     $F_1$

2*Our experiments       RoBERTa + CRF     86.82     87.73     87.27

RoBERTa + RegCCRF     87.22     87.79     87.51

4*25mmResults from
literature     [He et al., 2017]     —     —     85.5

[Ouchi et al., 2018]     87.1     85.3      86.2

[Ouchi et al., 2018] (ensemble)     88.5     85.5     87.0

[Li et al., 2019]      85.7     86.3     86.0

§ CONCLUSION AND FUTURE WORK

In this work, we have presented a method to constrain the output of
CRFs to a regular language. Our construction allows constraints to be
used at training or prediction time, and we demonstrate that training
with constraints better captures the data distribution. To test our
method empirically, we carry out experiments on synthetic data, and
incorporate a RegCCRF into a deep neural model for semantic role labeling,
demonstrating improvements over the state-of-the-art.

For enhanced expressibility, future work could investigate
non-binary constraints, i.e., regular
language-based constraints with learnable weights.
Additionally, regular language
induction (e.g. [Dunay et al., 1994, Bartoli et al., 2016]) could be
used to learn languages automatically, reducing manual specification
and identifying non-obvious constraints.

Another avenue for continuing research lies in identifying further
applications for RegCCRFs. We believe that the NLP task of relation extraction
could be a fruitful target – RegCCRFs offer a mechanism to make the
proposal of a relation conditional on the presence of the right
number and type of arguments.

While the construction we have proposed cannot be lifted directly to
context-free languages due to the unbounded state space of the
corresponding pushdown automata, there is plentiful work on regular
approximations of context-free languages [Mohri and Nederhof, 2001]. On
this basis, for example, a RegCCRF backed by a regular language describing trees of
a limited depth could also be applied to tasks with context-free

Our implementation of RegCCRFs, as well as scripts for replicating our
experiments, are available at

§ ACKNOWLEDGEMENTS

This work is supported by IBM Research AI through the IBM AI Horizons

[Anderson et al., 2017]
Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould.
Guided open vocabulary image captioning with constrained beam search.
In Proceedings of the 2017 Conference on Empirical Methods in
Natural Language Processing, pages 936–945, Copenhagen, Denmark, September
2017. Association for Computational Linguistics.

[Bartoli et al., 2016]
Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao.
Inference of regular expressions for text extraction from examples.
IEEE Transactions on Knowledge and Data Engineering,
280 (5):0 1217–1230, 2016.

[Bromberg et al., 2009]
Facundo Bromberg, Dimitris Margaritis, and Vasant Honavar.
Efficient markov network structure discovery using independence
The Journal of Artificial Intelligence Research, 35:0
449–484, 05 2009.

[Carreras and Màrquez, 2005]
Xavier Carreras and Lluís Màrquez.
Introduction to the CoNLL-2005 shared task: Semantic role
In Proceedings of the Ninth Conference on Computational Natural
Language Learning (CoNLL-2005), pages 152–164, Ann Arbor, Michigan,
June 2005. Association for Computational Linguistics.

[Chu, 1965]
Yoeng-Jin Chu.
On the shortest arborescence of a directed graph.
Scientia Sinica, 14:0 1396–1400, 1965.

[Devlin et al., 2019]
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.
BERT: Pre-training of deep bidirectional transformers for language
In Proceedings of the 2019 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 1 (Long and Short Papers), pages 4171–4186,
Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.

[Dunay et al., 1994]
B.D. Dunay, F.E. Petry, and B.P. Buckles.
Regular language induction with genetic programming.
In Proceedings of the First IEEE Conference on Evolutionary
Computation. IEEE World Congress on Computational Intelligence, pages
396–400 vol.1, 1994.

[Edmonds, 1967]
Jack Edmonds.
Optimal branchings.
Journal of Research of the National Bureau of Standards,
71B0 (4):0 233–240, 1967.

[Gimpel et al., 2011]
Kevin Gimpel, Nathan Schneider, Brendan O'Connor, Dipanjan Das, Daniel Mills,
Jacob Eisenstein, Michael Heilman, Dani Yogatama, Jeffrey Flanigan, and Noah
Part-of-speech tagging for twitter: Annotation, features, and
In Proceedings of the 49th Annual Meeting of the Association
for Computational Linguistics, pages 42–47, 2011.

[Gruber and Holzer, 2007]
Hermann Gruber and Markus Holzer.
Inapproximability of nondeterministic state and transition complexity
assuming P$\ne$ NP.
In International Conference on Developments in Language
Theory, pages 205–216. Springer, 2007.

[Hasler et al., 2018]
Eva Hasler, Adrià de Gispert, Gonzalo Iglesias, and Bill Byrne.
Neural machine translation decoding with terminology constraints.
In Proceedings of the 2018 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 2 (Short Papers), pages 506–512, New Orleans,
Louisiana, June 2018. Association for Computational Linguistics.

[He et al., 2017]
Luheng He, Kenton Lee, Mike Lewis, and Luke Zettlemoyer.
Deep semantic role labeling: What works and what’s next.
In Proceedings of the 55th Annual Meeting of the Association
for Computational Linguistics (Volume 1: Long Papers), pages 473–483, 2017.

[Hokamp and Liu, 2017]
Chris Hokamp and Qun Liu.
Lexically constrained decoding for sequence generation using grid
beam search.
In Proceedings of the 55th Annual Meeting of the Association
for Computational Linguistics (Volume 1: Long Papers), pages 1535–1546,
Vancouver, Canada, July 2017. Association for Computational Linguistics.

[Jiang and Ravikumar, 1991]
Tao Jiang and Bala Ravikumar.
Minimal NFA problems are hard.
In International Colloquium on Automata, Languages, and
Programming, pages 629–640. Springer, 1991.

[Jiang, 2020]
Zhe Jiang.
Spatial structured prediction models: Applications, challenges, and
IEEE Access, 8:0 38714–38727, 2020.

[Johnson et al., 2015]
Justin Johnson, Ranjay Krishna, Michael Stark, Li-Jia Li, David A. Shamma,
Michael S. Bernstein, and Li Fei-Fei.
Image retrieval using scene graphs.
In 2015 IEEE Conference on Computer Vision and Pattern
Recognition (CVPR), pages 3668–3678, 2015.

[Jurafsky and Martin, 2009]
Daniel Jurafsky and James H. Martin.
Speech and Language Processing (2nd Edition).
Prentice-Hall, Inc., USA, 2009.

[Kingma and Ba, 2015]
Diederik P. Kingma and Jimmy Ba.
Adam: A method for stochastic optimization.
In Yoshua Bengio and Yann LeCun, editors, 3rd International
Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May
7-9, 2015, Conference Track Proceedings, 2015.

[Kristjansson et al., 2004]
Trausti Kristjansson, Aron Culotta, Paul Viola, and Andrew McCallum.
Interactive information extraction with constrained conditional
random fields.
In Proceedings of the AAAI Conference on Artificial
Intelligence, pages 412–418, 2004.

[Lafferty et al., 2001]
John Lafferty, Andrew McCallum, and Fernando CN Pereira.
Conditional random fields: Probabilistic models for segmenting and
labeling sequence data.
In Proceedings of the Eighteenth International Conference on
Machine Learning, page 282–289, San Francisco, CA, USA, 2001. Morgan
Kaufmann Publishers Inc.

[Lample et al., 2016]
Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian, Kazuya Kawakami, and
Chris Dyer.
Neural architectures for named entity recognition.
In Proceedings of the 2016 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, pages 260–270, San Diego, California, June 2016. Association
for Computational Linguistics.

[Lee et al., 2007]
Su-in Lee, Varun Ganapathi, and Daphne Koller.
Efficient structure learning of markov networks using
In B. Schölkopf, J. Platt, and T. Hoffman, editors,
Advances in Neural Information Processing Systems, volume 19. MIT
Press, 2007.

[Li et al., 2019]
Zuchao Li, Shexia He, Hai Zhao, Yiqing Zhang, Zhuosheng Zhang, Xi Zhou, and
Xiang Zhou.
Dependency or span, end-to-end uniform semantic role labeling.
Proceedings of the AAAI Conference on Artificial Intelligence,
330 (01):0 6730–6737, Jul. 2019.

[Liu et al., 2019]
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer
Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov.
RoBERTa: A robustly optimized BERT pretraining approach.
arXiv preprint arXiv:1907.11692, 2019.

[Mohri, 2012]
Mehryar Mohri.
A disambiguation algorithm for finite automata and functional
In International Conference on Implementation and Application
of Automata, pages 265–277. Springer, 2012.

[Mohri and Nederhof, 2001]
Mehryar Mohri and Mark-Jan Nederhof.
Regular approximation of context-free grammars through
In Robustness in language and speech technology, pages
153–163. Springer, 2001.

[Murphy et al., 1999]
Kevin P. Murphy, Yair Weiss, and Michael I. Jordan.
Loopy belief propagation for approximate inference: An empirical
In Proceedings of the Fifteenth Conference on Uncertainty in
Artificial Intelligence, page 467–475, Stockholm, Sweden, 1999. Morgan
Kaufmann Publishers Inc.

[Niculae et al., 2018]
Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie.
Sparsemap: Differentiable sparse structured inference.
In International Conference on Machine Learning, pages
3799–3808. PMLR, 2018.

[Ouchi et al., 2018]
Hiroki Ouchi, Hiroyuki Shindo, and Yuji Matsumoto.
A span selection model for semantic role labeling.
In Proceedings of the 2018 Conference on Empirical Methods in
Natural Language Processing, pages 1630–1642, Brussels, Belgium,
October-November 2018. Association for Computational Linguistics.

[Palmer et al., 2005]
Martha Palmer, Daniel Gildea, and Paul Kingsbury.
The Proposition Bank: An annotated corpus of semantic roles.
Computational Linguistics, 310 (1):0 71–106,

[Peters et al., 2018]
Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark,
Kenton Lee, and Luke Zettlemoyer.
Deep contextualized word representations.
In Proceedings of the 2018 Conference of the North American
Chapter of the Association for Computational Linguistics: Human Language
Technologies, Volume 1 (Long Papers), pages 2227–2237, New Orleans,
Louisiana, June 2018. Association for Computational Linguistics.

[Pradhan et al., 2012]
Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen
CoNLL-2012 shared task: Modeling multilingual unrestricted
coreference in OntoNotes.
In Joint Conference on EMNLP and CoNLL - Shared Task,
pages 1–40, Jeju Island, Korea, July 2012. Association for Computational

[Ramshaw and Marcus, 1999]
Lance Ramshaw and Mitchell Marcus.
Text chunking using transformation-based learning.
In Natural Language Processing Using Very Large Corpora, pages
157–176. Springer Netherlands, Dordrecht, 1999.

[Roth and Yih, 2004]
Dan Roth and Wen-tau Yih.
A linear programming formulation for global inference in natural
language tasks.
In Proceedings of the Eighth Conference on Computational
Natural Language Learning (CoNLL-2004) at HLT-NAACL 2004, pages
1–8, Boston, Massachusetts, USA, May 6 - May 7 2004. Association for
Computational Linguistics.

[Sarawagi and Cohen, 2004]
Sunita Sarawagi and William W Cohen.
Semi-markov conditional random fields for information extraction.
Advances in neural information processing systems,
17:0 1185–1192, 2004.

[Scheible et al., 2016]
Christian Scheible, Roman Klinger, and Sebastian Padó.
Model architectures for quotation detection.
In Proceedings of the 54th Annual Meeting of the Association
for Computational Linguistics (Volume 1: Long Papers), pages 1736–1745,

[Schmidt et al., 2008]
M. Schmidt, K. Murphy, Glenn Fung, and Rómer Rosales.
Structure learning in random fields for heart motion abnormality
2008 IEEE Conference on Computer Vision and Pattern
Recognition, pages 1–8, 2008.

[Sutton and McCallum, 2004]
Charles Sutton and Andrew McCallum.
Collective segmentation and labeling of distant entities in
information extraction.
In Proceedings of the ICML 2004 Workshop on Statistical
Relational Learning, 2004.

[Viterbi, 1967]
Andrew Viterbi.
Error bounds for convolutional codes and an asymptotically optimum
decoding algorithm.
IEEE Transactions on Information Theory, 130
(2):0 260–269, 1967.

[Weischedel et al., 2011]
Ralph Weischedel, Eduard Hovy, Mitchell Marcus, Martha Palmer, Robert Belvin,
Sameer Pradhan, Lance Ramshaw, and Nianwen Xue.
Ontonotes: A large training corpus for enhanced processing.
In Handbook of Natural Language Processing and Machine
Translation: DARPA Global Autonomous Language Exploitation. Springer, 2011.

[Wolf et al., 2020]
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue,
Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe
Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien
Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest,
and Alexander M. Rush.
Transformers: State-of-the-art natural language processing.
In Proceedings of the 2020 Conference on Empirical Methods in
Natural Language Processing: System Demonstrations, pages 38–45, Online,
October 2020. Association for Computational Linguistics.

§ EXPERIMENTAL DESIGN

Summary of hyperparameters for our models and experiments.

13cmCRFs     Transition score initialization     $\mathcal{N}(0, 0.1)$

63cmSynthetic data experiments
Emission score initialization     PyTorch default

Optimizer     SGD

Training iterations     5000

Batch size     50

Initial learning rate     1.0

Learning rate decay     10% every 100 steps

63cmSRL experiments
RoBERTa weights

Projection weight and bias initialization     PyTorch default

Optimizer     Adam

Learning rate     $10^{-5}$

Batch size     2

Gradient accumulation     4 batches

This appendix details the training procedures and hyperparameter choices for
our experiments.
These are summarized in Table <ref>.
Full code for all experiments, along with training logs, are also included in
the supplementary materials.

§.§ CRFs

For all CRFs and RegCCRFs, transition potentials were initialized randomly
from a normal distribution with mean zero and standard deviation 0.1.
No CRFs or RegCCRFs employed special start- or end-transitions – that is, we did not
insert any additional beginning-of-sequence or end-of-sequence tags for the
Viterbi or forward algorithms.

§.§ Synthetic data experiments – training procedure

For both synthetic data experiments, the emission potentials were represented
explicitly for each position as trainable parameters – since the observation
sequence was constant in all experiments, these did not depend on  $\bm{x}$.

Parameters were initialized randomly using PyTorch default initialization, and
optimized using stochastic gradient descent. To ensure fast convergence to a
stable distribution, we employed learning rate decay – learning rate was initially
set to 1.0, and reduced by 10% every 100 training steps.

We trained all models for a total of 5000 steps with a batch size of 50.
All models were trained on CPUs.
For the experiment described in Section 6.1, we trained separate models for each
$k$ – the total training time for this experiment was approximately 35 minutes.
The experiment described in Section 6.2 completed training in approximately 30

§.§ Semantic role labeling – training procedure

In the semantic role labeling (SRL) experiments, we incorporated a pretrained RoBERTa
network [Liu et al., 2019] – the implementation and weights for this model
were obtained using the  model from the Hugging Face
transformers library [Wolf et al., 2020]. RoBERTa embeddings
were projected down to transmission scores using a linear layer with a bias –
projection weights and biases were initialized using the PyTorch default

Input tokens were sub-tokenized using RoBERTa's tokenizer.
The marked predicate in each sentence was prefixed by a special
During training, for efficiency reasons, we excluded all sentences with 120 or
more subtokens – this amounted to 0.23% of all training instances.
We nonetheless predicted on all instances, regardless of length.

We optimized models using the Adam optimizer [Kingma and Ba, 2015] with a learning rate
of $10^{-5}$.
We fine-tune RoBERTa parameters and learn the projection and RegCCRF weights
For performance reasons, batch size was set to 2, but we utilized gradient
accumulation over groups of 4 batches to simulate a batch size of 8.

We utilized early stopping to avoid overfitting.
Every 5000 training steps, we approximated our model's $F_1$ score against a
subset of the provided development partition, using a simplified reimplementation of the
official evaluation script.
Each time we exceeded the previous best $F_1$ score for a model, we saved all
model weights to disk.
After 50 such evaluations with no improvement, we terminated training, and used
the last saved copy of model weights for final evaluation.

We performed all SRL experiments on GeForce GTX 1080 Ti GPUs.
Each experiment used a single GPU.
Training took an average of 88 hours for RegCCRF models, and 24 hours for CRF
baseline models.  All training logs with timestamps are included in the
supplementary materials.


# Probing ultra-light dark photon from inverse Compton-like scattering

Liangliang Su<EMAIL_ADDRESS>Department of Physics and Institute of
Theoretical Physics, Nanjing Normal University, Nanjing, 210023, China  School
of Physics, Yantai University, Yantai 264005, China  Lei Wu<EMAIL_ADDRESS>Department of Physics and Institute of Theoretical Physics, Nanjing Normal
University, Nanjing, 210023, China  Bin Zhu<EMAIL_ADDRESS>School
of Physics, Yantai University, Yantai 264005, China

(August 28, 2024)

###### Abstract

Dark photon not only provides a portal linking dark sector particles and
ordinary matter but also is a well-motivated dark matter candidate. We propose
to detect the dark photon dark matter through the inverse Compton-like
scattering process $p+\gamma^{\prime}\to p+\gamma$. Thanks to the ultra-high
energy primary cosmic rays, we find that such a method is able to probe the
dark photon mass from $10^{-2}$ eV down to $10^{-19}$ eV with the expected
sensitivity of eROSITA $X$-ray telescope, which can extend the current lower
limit of dark photon mass from Jupiter’s magnetic fields experiment by about
three orders of magnitude.

###### pacs:

Valid PACS appear here

##  I Introduction

A large amount of astrophysical and cosmological observations suggest the
existence of dark matter (DM). Investigation of the properties of DM is a
common interest of particle physics, astrophysics, and cosmology. Currently,
the only clues it gives us are through the gravitational effects, while there
is no clear signal of the DM observed in the laboratory experiments, such as
direct detection, indirect detection, and collider. The nature of the DM is
still mysterious.

Among various well-motivated DM candidates, the Weakly Interacting Massive
Particles (WIMP) have been intensively studied. However, the null results from
direct detection, indirect detection and collider experiments have produced
the strong constraints on some popular WIMP models. This has motivated to
study other DM possibilities in recent years. One of the simplest hypotheses
for DMs is that it belongs to a “hidden sector” or “dark sector” secluded from
the Standard Model (SM) Fayet (1980, 1981); Okun (1982); Georgi et al. (1983);
Fayet (1990); Pospelov (2009), whose interactions could be mediated by a dark
photon in an additional Abelian gauge group $U_{D}(1)$. The dark photon
couples with the ordinary photon through the kinetic mixing Holdom (1986), and
thus provides a portal linking the SM and new physics, which enables the dark
photon can be detected in various experiments An et al. (2013); Redondo and
Raffelt (2013); Liu et al. (2015); An et al. (2015); Aguilar-Arevalo et al.
(2017); Bhoonah et al. (2019); She et al. (2020); McDermott and Witte (2020);
Flambaum and Samsonov (2019); Garcia et al. (2020); Caputo et al. (2020);
Witte et al. (2020); An et al. (2020); Fitzpatrick et al. (2021). In the past
decades, great efforts have been devoted to hunting for the dark photon (see
the recent review Fabbrichesi et al. (2020); Caputo et al. (2021)).

Recently, a number of novel production mechanisms, including the misalignment
mechanism Nelson and Scholtz (2011); Arias et al. (2012), the parametric
resonance production Dror et al. (2019), the tachyonic instability Agrawal et
al. (2020); Co et al. (2019); Bastero-Gil et al. (2019) and the decay of a
cosmic string network Long and Wang (2019), have been proposed to efficiently
produce the dark photons with a sub-eV mass down to the fuzzy dark matter
scale $\sim 10^{-21}$ eV. Detections of such light dark photon dark matter
have been studied in high precision spectroscopy Jaeckel and Roy (2010);
Danilov et al. (2019), helioscope Redondo (2008); Ehret et al. (2010); Betz et
al. (2013), gravitational wave observation Guo et al. (2019); Co et al.
(2021). Besides, the ultralight dark photon DM can also affect early
cosmological observables and the evolution of astrophysical objects. For
example, the conversion of dark photon and photon leaves observable imprints
on the CMB background. In particular, the heating of the intergalactic medium
around the epoch of helium ($\mathrm{He}^{++}$) reionization and the depletion
of dark matter broaden the region of dark photon dark matter mass McDermott
and Witte (2020). However, these bounds are based on some certain assumptions
of the universe history, which is challenged by the recent different
measurements of Hubble constant in early and late universe Di Valentino et al.
(2021). Likewise, the heating/cooling rate of cold Galactic Center gas clouds
can also constrain dark photon dark matter by requiring the heating rate from
dark matter not exceeding the radiative cooling rate of the gas cloud Bhoonah
et al. (2019); Wadekar and Farrar (2019). However, this constraint depends on
the number density of elements in the gas cloud, such as electron number
density $n_{e}$. Different results of calculating this quantity exist in
Bhoonah et al. (2019) and Wadekar and Farrar (2019).

In this work, we propose an alternative way to probe the ultra-light dark
photon dark matter through the interaction of the dark photon with the proton
in the primary cosmic rays (CRs). Since the coupling of the dark photon with
the ordinary matter is small, we consider the inelastic scattering process,
$p+\gamma^{\prime}\to p+\gamma$, instead of the elastic scattering process.
The energy of photon in the final states is determined by the dark photon mass
and the proton energy in the CRs. Note that the latter is negatively
correlated with the former for a given photon energy. In addition, there
exists the “GZK cut-off” of the energy spectrum of the CRs, which arises from
the energy loss of CRs during its scattering with the CMB photon Greisen
(1966); Zatsepin and Kuzmin (1966). Due to such a cut-off, the $X$-ray
telescope is the most suitable experiment to detect the ultra-light dark
photon in the mass range we are interested in. Nowadays, several $X$-ray
telescopes have been launched, such as Chandra Weisskopf et al. (2002), XMM-
Newton Turner et al. (2001), and the extended ROentgen Survey with an Imaging
Telescope Array (eROSITA). Merloni et al. (2012). In the soft $X$-ray band
(0.2-2.3 keV), eROSITA has a better outstanding energy resolution and field of
view. The eROSITA all-sky survey will have reached a sensitivity more than 25
times higher than ROSITA all-sky survey at the end of eROSITA. Therefore, we
will show the expected sensitivity our proposal in the eROSITA experiment.

##  II Theoretical Framework

The massive dark photon interacts with ordinary matter via the kinetic mixing
with the ordinary photon. The relevant Lagrangian can be written as following,

$\displaystyle\mathcal{L}=$
$\displaystyle-\frac{1}{4}F_{\mu\nu}F^{\mu\nu}-eJ_{\mu}A_{\mu}$ (1)
$\displaystyle-\frac{1}{4}F_{\mu\nu}^{\prime}F^{\prime\mu\nu}+\frac{1}{2}m_{\gamma^{\prime}}^{2}A_{\mu}^{\prime}A^{\prime\mu}-\epsilon
eJ_{\mu}A^{\prime\mu}$

where $F_{\mu\nu}$ and $F_{\mu\nu}^{\prime}$ are the field strength tensors of
the ordinary photon and the dark photon. The dark photon mass can originate
from the Stueckelberg or the dark Higgs mechanisms. There are various
constraints on the dark photon mass. Among them, the large-scale structure
formation that requires the de Broglie wavelength of the dark photon does not
exceed the DM halo size of the smallest dwarf galaxies produces a lower bound
on the dark photon mass, $m_{\gamma^{\prime}}\gtrsim 10^{-22}$ eV Hui et al.
(2017). The last term represents the interaction of the dark photon
$A^{\prime\mu}$ with the electromagnetic current of the SM particles $J_{\mu}$
with the coupling $e\epsilon$. This makes the inelastic scattering process of
the primary CRs with the dark photon possible,
$\gamma^{\prime}(p_{1})+p(p_{2})\rightarrow\gamma(k_{1})+p(k_{2})$, i.e., the
inverse Compton-like scattering process, as shown in Fig. 1.

Figure 1: Schematic diagram of the inverse Compton-like scattering process
$\gamma^{\prime}(p_{1})+p(p_{2})\rightarrow\gamma(k_{1})+p(k_{2})$.

In the rest frame of the dark photon, the maximum and minimum energies of
outgoing photon for a given energy of the proton $E_{p}$ in CRs are given by

$\omega_{\mathrm{min}/\mathrm{max}}=\frac{m_{\gamma^{\prime}}^{2}+2m_{\gamma^{\prime}}E_{p}}{2E_{p}+2m_{\gamma^{\prime}}\pm
2\sqrt{E_{p}^{2}-m_{p}^{2}}}$ (2)

where $m_{\gamma^{\prime}}$ and $m_{p}$ are the mass of the dark photon and
the energy of the proton, respectively. For the ultra-high energy proton, we
can find that the maximum energy of photon radiation is close to the incoming
energy of the proton, while the minimum energy of the photon emission is
always larger than the half of the dark photon mass, $\omega\gtrsim
m_{\gamma^{\prime}}/2$.

The differential cross section $\mathrm{d}\sigma/\mathrm{d}\omega$ of this
process is also calculated by

$\displaystyle\frac{\mathrm{d}\sigma}{\mathrm{d}\omega}=$
$\displaystyle\frac{1}{32\pi
m_{\gamma^{\prime}}|\vec{p}_{2}|^{2}}\left(\frac{1}{6}\sum|\mathcal{M}|^{2}\right)$
(3) $\displaystyle=$ $\displaystyle\frac{e^{4}\epsilon^{2}}{6\pi
m_{\gamma^{\prime}}^{3}|\vec{p}_{2}|^{2}(2E_{p}+m_{\gamma^{\prime}})^{2}(2E_{p}+m_{\gamma^{\prime}}-2\omega)}$
$\displaystyle\times[m_{\gamma^{\prime}}^{2}(2E_{p}+m_{\gamma^{\prime}})^{2}(2E_{p}^{2}+2E_{p}m_{\gamma^{\prime}}+m_{p}^{2}+m_{\gamma^{\prime}}^{2})$
$\displaystyle+\omega^{2}(m_{\gamma^{\prime}}^{2}(2E_{p}+m_{\gamma^{\prime}})(6E_{p}+5m_{\gamma^{\prime}})+4m_{p}^{4}+2m_{p}^{2}m_{\gamma^{\prime}}(4E_{p}+3m_{\gamma^{\prime}}))$
$\displaystyle-2m_{\gamma^{\prime}}^{2}\omega^{3}(2E_{p}+m_{\gamma^{\prime}})$
$\displaystyle-2m_{\gamma^{\prime}}\omega(2E_{p}+m_{\gamma^{\prime}})(4E_{p}^{2}m_{\gamma^{\prime}}+E_{p}(2m_{p}^{2}+5m_{\gamma^{\prime}}^{2})+2m_{\gamma^{\prime}}(m_{p}^{2}+m_{\gamma^{\prime}}^{2}))],$

where the momentum of CR proton follow the relation
$|\vec{p}_{2}|^{2}=E_{p}^{2}-m_{p}^{2}$ and
$\left(\frac{1}{6}\sum|\mathcal{M}|^{2}\right)$ is the squared amplitude of
the inverse Compton-like scattering process. It should be noted that the
squared matrix element of the dark photon in Eq. 3 is different from that of
the axion. Using the polarization sum for the massive vector boson, we can
calculate the squared matrix element of the dark photon and expand it in the
small mass of the dark photon, which is given by $|M|^{2}\sim
16e^{4}\epsilon^{2}+\mathcal{O}(m_{\gamma^{\prime}})$. Similarly, for the
axion, the squared matrix element will go like $|M|^{2}\sim
8\omega^{2}m_{a}^{2}/(m_{p}^{2}-s)^{2}+\mathcal{O}(m_{a}^{3})$. Then, in
comparison with the axion case Alonso-Álvarez et al. (2020); Dent et al.
(2020), there will be an enhancement of $1/m_{\gamma^{\prime}}$ at the leading
order in Eq. 3 when the dark photon mass is small. On the other hand, since
the dark photon is a massive vector boson and its mass should be heavier than
$10^{-22}$ eV, the Eq. 3 will not be infinitely large. We check and find that
our cross section is the same as that of the Compton-like scattering process
$e\gamma\to e\gamma^{\prime}$ up to a factor of $2/3$ because the dark photon
in the initial states has three polarization states. Besides, we derive the
unitarity bound for our process and find that the constraint is independent of
the dark photon mass in the limit of $E_{p}\gg m_{\gamma^{\prime}}$ as shown
in the appendix.

Next, we will calculate the flux of the outgoing photon in the Compton-like
scattering process to derive the bounds on dark photon. The differential flux
can be written as

$\displaystyle\frac{\mathrm{d}\Phi}{\mathrm{d}\omega\mathrm{d}\Omega}=$
$\displaystyle\frac{1}{4\pi}\int_{l.o.s}\mathrm{d}l\int_{E_{p}^{\mathrm{min}}(\omega)}\mathrm{d}E_{p}\frac{\mathrm{d}^{2}\Gamma_{p+\gamma^{\prime}\rightarrow
p+\gamma}}{\mathrm{d}E_{p}\mathrm{d}\omega}$ (4) $\displaystyle=$
$\displaystyle\frac{D}{m_{\gamma^{\prime}}}\int_{E_{p}^{\mathrm{min}}(\omega)}\mathrm{d}E_{p}\frac{\mathrm{d}\sigma}{\mathrm{d}\omega}\frac{\mathrm{d}\Phi_{p}}{\mathrm{d}E_{p}},$

where $\mathrm{d}\Phi_{p}/\mathrm{d}E_{p}$ is the number of particles per
area/steradian/kinetic energy/time of the local interstellar spectrum. It
should be noted that the minimum energy of the proton in CRs that is needed to
produce a photon with the energy $\omega$ can be obtained from Eq. (2),

$\displaystyle E_{p}^{\mathrm{min}}=$ $\displaystyle\frac{\omega-
m_{\gamma^{\prime}}}{2}$ (5) $\displaystyle+$
$\displaystyle\frac{\sqrt{m_{\gamma^{\prime}}\omega^{2}(m_{\gamma^{\prime}}-2\omega)(m_{\gamma^{\prime}}^{2}-2m_{\gamma^{\prime}}\omega-4m_{p}^{2})}}{2m_{\gamma^{\prime}}(2\omega-
m_{\gamma^{\prime}})},$

which is approximately given as
$E_{p}^{\mathrm{min}}\simeq\omega/2+m_{p}\sqrt{\omega/2m_{\gamma^{\prime}}}$
for the ultra-light dark photon dark matter mass. This implies that the
minimal energy of the proton $E_{p}^{\mathrm{min}}$ in the CRs is proportional
to $\sqrt{\omega}$ and inversely proportional to $\sqrt{m_{\gamma^{\prime}}}$
in the very low mass range. On the other hand, the primary energy spectrum of
the CRs declines as the power law of the energy like $\sim E^{-2.7}$ when
$E<\mathcal{O}(10^{15})$ eV Gaisser et al. (2013). However, it will vanish at
the “GZK cut-off”. In other words, a lower threshold detector, such as $X$-ray
telescope, is needed to search for the dark photon dark matter in a wide mass
range. In principle, the electron in the CRs can also induce such a scattering
process. However, its contribution is negligible for the very light dark
photon because of the low “cut-off” energy of primary CR electron

In this work, we use the flux of the proton in the primary CRs in the four-
component “Global-Fit4” model Gaisser et al. (2013); Xia et al. (2020),

$\frac{\mathrm{d}\Phi_{p}}{\mathrm{d}E_{p}}=\sum_{i=1}^{4}c_{i}E_{p}^{-\alpha_{i}}\exp\left(-\frac{E_{p}}{R_{i}}\right)$
(6)

where $c_{i}$, $\alpha_{i}$ and $R_{i}$ represent the normalization constants,
the integral spectral indexes and the rigidity cut-off with the component
index $i$. The values of these parameters are listed in the Table. 1.

Global-Fit4 |  | $R_{1}$
---
(120 TeV)
| $R_{2}$
---
(4 PeV)
| $R_{3}$
---
(1.5 EeV)
| $R_{4}$
---
(40 EeV)
$c_{i}$ | 7000 | 150 | 12 | 1.2
$\alpha_{i}$ | 2.66 | 2.4 | 2.4 | 2.4
H4a |  | $R_{1}$
---
(4 PeV)
| $R_{2}$
---
(30 PeV)
| $R_{3}$
---
(60 EeV)
$c_{i}$ | 7860 | 20 | 200 |
$\alpha_{i}$ | 2.66 | 2.4 | 2.6 |
Table 1: The normalization constants $c_{i}$, the integral spectral indexes
$\alpha_{i}$ and the rigidity cut-off $R_{i}$ in the four-component “Global-
Fit4” and ”H4a” model of proton flux are taken as the Ref. Gaisser et al.
(2013); Xia et al. (2020).

The $D$-factor in Eq. 4 that depends on the DM density distribution can be
defined by the line-of-sight of integral of DM density of the Milky Way halo
Evans et al. (2016); Dekker et al. (2021),

$D(\phi)=\int_{l.o.s}\mathrm{d}l\rho_{\mathrm{DM}}(r(l,R,\phi)).$ (7)

where $l$ is the line-of-sight distance and the
$r(l,R,\phi)=\sqrt{l^{2}+R^{2}-2lR\cos{\phi}}$ is the radial distance from the
Galactic Center (GC). $R$ is the distance from GC to the Earth and $\phi$ is
the polar angle between the Earth-GC axis and line-of-sight direction. In this
paper, we assume that the dark matter density $\rho_{\mathrm{DM}}$ satisfy the
Navarro-Frenk-White (NFW) profile
distribution:$\rho_{\mathrm{DM}}=\rho_{s}/((r/r_{s})(r/r_{s}+1)^{2})$, the
scale radial and characteristic density $\rho_{s}$ refer to the Ref. Dekker et
al. (2021). Since only the DM that distributes in the region of the radial
distance from the Earth of 1 $\mathrm{kpc}$ is considered, we roughly assume
the cosmic-ray flux is isotropic. However, it should be mentioned that the
isotropy assumptions of the cosmic-ray flux may be broken down in the high
energy (more protons are believed to come from the direction of Ursa Major.)
The dedicated study of the anisotropy is beyond the scope of this paper. Under
the assumption that CRs distribution is isotropical in the galaxy, the
$D$-factor can be approximately proportional to the product of the effective
distance $D_{\mathrm{eff}}$ and local dark matter density
$\rho^{\mathrm{local}}_{\mathrm{DM}}$ Bringmann and Pospelov (2019); Wang et
al. (2020); Su et al. (2020); Flambaum et al. (2020).

In order to derive the constraints on the dark photon dark matter from $X$-ray
experiments, we can simply require the theoretical prediction of the $X$-ray
flux not exceeding the measured Cosmic X-ray Background (CXB) Dent et al.
(2020). However, this approach suffers from large uncertainties and may lead
to an over-conservative estimation because the Active Galactic Nuclei (AGN) as
main source of the CXB background may be underestimated. In Refs. Foster et
al. (2021); Dekker et al. (2021), a more accurate way was proposed. It is
supposed that the diffuse CXB follows a power-law relation
$C\times\omega^{-1.42}$ with normalization constant $C=8.44$
cts/$\mathrm{cm}^{2}$/$\mathrm{s}$ /$\mathrm{sr}$/$\mathrm{keV}$ at $\omega=1$
keV. On the other hand, the detector background has a flat energy spectrum and
distributes over the sky isotropically, which is estimated as 1151 counts
$\mathrm{s}^{-1}$ $\mathrm{sr}^{-1}$ $\mathrm{keV}^{-1}$ in Ref. Dekker et al.
(2021). By simulating the all-sky $X$-ray signal over each spatial pixel and
energy bin, one can obtain 95% C.L. exclusion limit from the joint-likelihood
analysis. With their derived results, we can impose the constraints on dark
photon dark matter in the photon energy $2<\omega<10$ keV.

##  III Numerical Results And Discussions

Figure 2: The flux of the photon produced in the scattering process of
$\gamma^{\prime}+p\to\gamma+p$ for different dark photon mass $m=10^{-19}$
eV(green), $m=10^{-18}$ eV(orange) and $m=10^{-17}$ eV(blue). We take
$D=10^{22}$ GeV/$\mathrm{cm}^{2}$ and $\epsilon=0.1$ as an example. Two
different parametric functions of the CRs: ”Global-fit4”(solid lines) and
”H4a”(dashed lines) are used. In the upper right corner of the figure, the
limit on the photon flux $\mathrm{d}\Phi_{\gamma}/\mathrm{d}\mathrm{\Omega}$
by using the analysis of the eROSITA experiment Dekker et al. (2021) is given
as well.

In Fig. 2, we show that the photon flux for the dark photon mass
$m_{\gamma^{\prime}}=10^{-19},\;10^{-18},\;10^{-17}$ eV in the photon energy
range $0.1<\omega<10^{3}$ keV. In the calculations, we choose $D=10^{22}$
GeV/$\mathrm{cm}^{2}$ and the kinetic mixing parameter $\epsilon=0.1$ as an
example. The different values of these two parameters only change the
magnitude of the photon flux, rather than distorting the shape. To show the
effect the choice of model has on our results, we compare the results of two
different parametric functions of the proton flux “Global Fit4” and “H4a” in
Eq. 6, whose parameters are given in Tab. 1. From Fig. 2. we find that the two
proton fluxes will give the similar results and thus we choose “Global Fit4”
in our following calculations. However, there remain large uncertainties in
high-energy cosmic ray flux data that haven’t been accounted for. In Fig. 2,
we can also see that the flux of the photon for a given dark photon mass
decreases sharply with its energy, which is caused by the “GZK cut-off” of the
CRs. The endpoints of each curve depend on the dark photon mass. For example,
the photon flux vanishes at $\omega\sim 2$ keV and $\omega\sim 200$ keV for
dark photon with $m_{\gamma^{\prime}}=10^{-19}$ eV and
$m_{\gamma^{\prime}}=10^{-17}$ eV, respectively. It can be understood that the
maximal value of $\omega$ in Eq. 2 increases with the dark photon mass for a
given proton energy, such as the “GZK cut-off”. Thus, in order to access
lighter dark photon through our inverse Compton-like scattering process, a
lower energy threshold detector is required. In the upper right panel of Fig.
2, we also display the limits on the photon flux by using the analysis of
eROSITA experiment, which requires $1.6\times
10^{-4}<\mathrm{d}\Phi_{\gamma}/\mathrm{d}\mathrm{\Omega}<1.8\times 10^{-3}$
cm-2s-1sr-1 in the energy range of $2\;\mathrm{keV}<\omega<10\;\mathrm{keV}$
Dekker et al. (2021).

Figure 3: The expected eROSITA limit by using inverse Compton-like scattering
process $\gamma^{\prime}+p\to\gamma+p$ on dark photon dark matter mass
$m_{\gamma^{\prime}}$ versus kinetic mixing parameter $\epsilon$. Other
constraints are also shown, such as Jupiter (orange) Davis et al. (1975);
Jaeckel and Ringwald (2010), Earth (purple) GOLDHABER and NIETO (1971),
COBE/FIRAS (brown) Caputo et al. (2020); Garcia et al. (2020), Coulomb (blue)
Jaeckel and Roy (2010), CROWS (green) Betz et al. (2013), LSW (red) Ehret et
al. (2010) and SUN-T (black) An et al. (2013).

In Fig. 3, we present the bounds on the dark photon with the expected
sensitivity of eROSITA $X$-ray telescope. In its energy range $2<\omega<10$
keV, the strongest bounds for ultra-light dark photon dark matter can be
obtained at the photon energy $\omega=2$ keV, as shown the upper right of Fig.
2. Besides, we also plot other constraints on the dark photon dark matter with
the mass less than 1 eV, including the magnetic fields of Jupiter Davis et al.
(1975); Jaeckel and Ringwald (2010) and Earth GOLDHABER and NIETO (1971), the
CMB (COEB/FIRAS) Caputo et al. (2020); Garcia et al. (2020), the atomic
experiments (Coulomb) Jaeckel and Roy (2010), the CROWS experiment Betz et al.
(2013), the light shining through a wall(LSW) experiments Ehret et al. (2010)
and Solar lifetime (SUN-T) An et al. (2013). On the other hand, the
constraints from the black hole superradiance are not shown because those
constraints are only relevant in the limit of vanishing coupling. We can find
that the dark photon mass from $10^{-6}$ eV to $10^{-19}$ eV with the kinetic
mixing parameter $\epsilon\sim{\cal O}(0.1)$ can be excluded by the future
eROSITA $X$-ray telescope experiment, which is lower than existing limit of
dark photon mass from Jupiter’s magnetic fields experiment by about three
orders of magnitude. Besides, we also checked the constraint from the existing
XMM-Newton data and fount it still much weaker than eROSITA. Finally it should
be mentioned that the bound on the kinetic mixing parameter derived from our
method is not as strong as others. However, it can cover a wide mass range in
a single experiment and would be improved by future lower threshold
telescopes.

##  IV Conclusions

In this work, we investigated the potential of probing the ultra-light dark
photon dark matter with $X$-ray produced from its inelastic scattering with
the cosmic rays, $\gamma^{\prime}+p\to\gamma+p$. Due to the contribution of
the ultra-high energy cosmic rays, we have found that the ultra-light dark
photon dark matter mass can be excluded down to $10^{-19}$ eV by using the
expected sensitivity of the eROSIRA $X$-ray telescope. Although the constraint
of the kinetic mixing parameter is not stronger than others, it gives a new
way to hunt for the ultra-light dark photon dark matter in a single
experiment. In the future, with the continuous improvement of $X$-ray
telescope experiments, our method will be able to further search for the
lighter dark photon dark matter.

##  V Acknowledgments

We thank Shan-Shan Weng for their helpful suggestions and discussions. This
work is supported by the National Natural Science Foundation of China (NNSFC)
under grant No. 11805161, by Jiangsu Specially Appointed Professor Program.

##  VI Appendix

In the section, we derive the unitarity bound on our model with the partial
wave method. For the $2\rightarrow 2$ scattering process, we can have the
partial wave $a_{fi}^{J}$,

$a_{fi}^{J}=\frac{1}{32\pi}\int_{-1}^{1}\mathrm{\leavevmode\nobreak\
d}\cos\theta
d_{\mu_{i}\mu_{f}}^{J}(\theta)\mathcal{T}_{fi}(\sqrt{s},\cos\theta),$ (8)

where $J$ and $\sqrt{s}$ are the the total angular momentum and the center of
mass energy (CM), respectively. The small Wigner $d$-function
$d_{\mu_{i}\mu_{f}}^{J}$ is related with the polar scattering angle $\theta$
in the CM and the difference of helicities
($\mu_{i(f)}=\frac{1}{2}(\lambda_{i_{1}(f_{1})}-\lambda_{i_{2}(f_{2})})$) of
the initial and final states. $\mathcal{T}_{fi}$ is the scattering amplitude
that is defined by
$(2\pi)^{4}\delta^{(4)}(p_{i}-p_{f})i\mathcal{T}_{fi}(\sqrt{s},\cos\theta)=\langle
f|S-1|i\rangle$. Especially, for $J=0$, $\mu_{i(f)}$ is zero. Thus, the
partial wave can be written as

$a_{0}=\frac{1}{32\pi}\int_{-1}^{1}\mathrm{\leavevmode\nobreak\
d}\cos\theta\mathcal{T}_{fi}(\sqrt{s},\cos\theta).$ (9)

Then, the unitarity condition of $S$ matrix, $S^{\dagger}S=1$, which implies

$|a_{0}|<1$ (10)

The key point is to calculate the scattering amplitudes $\mathcal{T}_{fi}$
between the initial and final state. For our scattering process
$p\bar{p}\to\gamma^{\prime}\gamma$, only the amplitudes $\mathcal{T}^{++++}$,
$\mathcal{T}^{++--}$, $\mathcal{T}^{--++}$ and $\mathcal{T}^{----}$ contribute
to the $J=0$ partial wave amplitudes. Thus, $a_{0}$ is rewritten as

$a_{0}=\frac{1}{32\pi}\int_{-1}^{1}\mathrm{\leavevmode\nobreak\
d}\cos\theta\begin{pmatrix}\mathcal{T}^{++++}&\mathcal{T}^{++--}\\\
\mathcal{T}^{--++}&\mathcal{T}^{----}\end{pmatrix},$ (11)

Next, we perform the calculations of the helicity amplitudes of the scattering
process $p(k_{1})\bar{p}(k_{2})\to\gamma^{\prime}(k_{3})\gamma(k_{4})$, which
is shown in Fig 4.

Figure 4: The diagrammatic sketch of the $2\rightarrow 2$ scattering in the
frame of the center of mass.

In the CM, the four-momenta of the initial and final states are given by

$\displaystyle k_{1}=$ $\displaystyle\frac{E_{cm}}{2}(1,0,0,\beta);$ (12)
$\displaystyle k_{2}=$ $\displaystyle\frac{E_{cm}}{2}(1,0,0,-\beta);$
$\displaystyle k_{3}=$
$\displaystyle(E_{cm}-\omega,\omega\sin{\theta},0,\omega\cos{\theta});$
$\displaystyle k_{4}=$
$\displaystyle(\omega,-\omega\sin{\theta},0,-\omega\cos{\theta}),$

where $E_{cm}$ is the energy of the CM. $\omega$ and $\beta$ are the angular
frequency of the photon and the speed of the proton, respectively. At the tree
level, the amplitudes of $u$\- and $t$-channels can be written as

$\displaystyle
i\mathcal{T}_{t}(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4})$
$\displaystyle=-\epsilon
e^{2}\bar{v}(k_{2},\lambda_{2})\gamma_{\mu}\epsilon_{\gamma}^{\ast\mu}(k_{4},\lambda_{4})$
(13) $\displaystyle\times\frac{i(\cancel{k}_{1}\
-\cancel{k}_{3}+m_{p})}{(k_{1}-k_{3})^{2}-m_{p}^{2}}\gamma_{\nu}\epsilon_{\gamma^{\prime}}^{\ast\nu}(k_{3},\lambda_{3})u(k_{1},\lambda_{1}),$

$\displaystyle
i\mathcal{T}_{u}(\lambda_{1},\lambda_{2},\lambda_{3},\lambda_{4})$
$\displaystyle=-\epsilon
e^{2}\bar{v}(k_{2},\lambda_{2})\gamma_{\mu}\epsilon_{\gamma^{\prime}}^{\ast\mu}(k_{3},\lambda_{3})$
(14) $\displaystyle\times\frac{i(\cancel{k}_{1}\ -\cancel{k}_{4}\
+m_{p})}{(k_{1}-k_{4})^{2}-m_{p}^{2}}\gamma_{\nu}\epsilon_{\gamma}^{\ast\nu}(k_{4},\lambda_{4})u(k_{1},\lambda_{1}),$

where $\epsilon$ is the kinetic mixing parameter and $m_{p}$ is the mass of
proton. $\gamma_{\mu(\nu)}$ is the Dirac matrix. By using the spinor
$u(\bar{v})$ and the polarization vector
$\epsilon_{\gamma^{\prime}}^{\ast\mu}(\epsilon_{\gamma}^{\ast\mu})$ in the
Weyl representation, we can obtain the helicity amplitudes as following

$\displaystyle\mathcal{T}^{++++}$ $\displaystyle=-\mathcal{T}^{----}$ (15)
$\displaystyle=\mathcal{T}_{t}(+,+,+,+)+\mathcal{T}_{u}(+,+,+,+)$
$\displaystyle=\frac{2\epsilon
e^{2}m_{p}}{E_{cm}(E_{cm}^{2}-m_{\gamma^{\prime}}^{2})(-1+\beta^{2}\cos^{2}{\theta})}\times(m_{\gamma^{\prime}}^{2}(2+\beta)$
$\displaystyle+2E_{cm}^{2}(-1+\beta+\beta^{2})+\beta(m_{\gamma^{\prime}}^{2}+2E_{cm}^{2}\beta)\cos{2\theta})$
$\displaystyle\overset{\beta\rightarrow 1}{=}-\frac{2\epsilon
e^{2}m_{p}(2E_{cm}^{2}+3m_{\gamma^{\prime}}^{2}+(2E_{cm}^{2}+m_{\gamma^{\prime}}^{2})\cos{2\theta})\csc^{2}{\theta}}{E_{cm}(E_{cm}^{2}-m_{\gamma^{\prime}}^{2})},$

$\displaystyle\mathcal{T}^{++--}$ $\displaystyle=-\mathcal{T}^{--++}$ (16)
$\displaystyle=\mathcal{T}_{t}(+,+,-,-)+\mathcal{T}_{u}(+,+,-,-)$
$\displaystyle=\frac{2\epsilon
e^{2}m_{p}}{E_{cm}(E_{cm}^{2}-m_{\gamma^{\prime}}^{2})(-1+\beta^{2}\cos^{2}{\theta})}(m_{\gamma^{\prime}}^{2}(-2+\beta)$
$\displaystyle+2E_{cm}^{2}(1+\beta-\beta^{2})+\beta(m_{\gamma^{\prime}}-E_{cm}^{2}\beta)\cos{2\theta})$
$\displaystyle\overset{\beta\rightarrow 1}{=}-\frac{4\epsilon
e^{2}m_{p}(2E_{cm}^{2}-m_{\gamma^{\prime}}^{2})}{E_{cm}(E_{cm}^{2}-m_{\gamma^{\prime}}^{2})},$

where $m_{\gamma^{\prime}}$ is the mass of the dark photon. In the limit of
$E_{cm}\gg m_{\gamma^{\prime}}$, the partial wave $a_{0}$ can be rewritten as

$a_{0}=\frac{\epsilon e^{2}m_{p}}{4\pi
E_{cm}}\int_{-1}^{1}\mathrm{d}\cos{\theta}\begin{pmatrix}-\cot^{2}{\theta}&-1\\\
1&\cot^{2}{\theta}\end{pmatrix},$ (17)

in which the largest eigenvalue is approximately given by

$|a_{0}|\approx\frac{148\epsilon\alpha m_{p}}{E_{cm}}.$ (18)

Thus, we can derive the bound on the kinetic mixing parameter $\epsilon$,

$\epsilon<\frac{E_{cm}}{148\alpha m_{p}},$ (19)

which shows that the unitarity will not be violated for a ultra-light dark
photon. The similar results can also be obtained in the scattering processes
$p\gamma^{\prime}\to p\gamma$ and
$p\bar{p}\rightarrow\gamma^{\prime}\gamma^{\prime}$.

## References

  * Fayet (1980) P. Fayet, Phys. Lett. B 95, 285 (1980).
  * Fayet (1981) P. Fayet, Nucl. Phys. B 187, 184 (1981).
  * Okun (1982) L. B. Okun, Sov. Phys. JETP 56, 502 (1982).
  * Georgi et al. (1983) H. Georgi, P. H. Ginsparg, and S. L. Glashow, Nature 306, 765 (1983).
  * Fayet (1990) P. Fayet, Nucl. Phys. B 347, 743 (1990).
  * Pospelov (2009) M. Pospelov, Phys. Rev. D 80, 095002 (2009), eprint 0811.1030.
  * Holdom (1986) B. Holdom, Phys. Lett. B 166, 196 (1986).
  * An et al. (2013) H. An, M. Pospelov, and J. Pradler, Phys. Lett. B 725, 190 (2013), eprint 1302.3884.
  * Redondo and Raffelt (2013) J. Redondo and G. Raffelt, JCAP 08, 034 (2013), eprint 1305.2920.
  * Liu et al. (2015) J. Liu, N. Weiner, and W. Xue, JHEP 08, 050 (2015), eprint 1412.1485.
  * An et al. (2015) H. An, M. Pospelov, J. Pradler, and A. Ritz, Phys. Lett. B 747, 331 (2015), eprint 1412.8378.
  * Aguilar-Arevalo et al. (2017) A. Aguilar-Arevalo et al. (DAMIC), Phys. Rev. Lett. 118, 141803 (2017), eprint 1611.03066.
  * Bhoonah et al. (2019) A. Bhoonah, J. Bramante, F. Elahi, and S. Schon, Phys. Rev. D 100, 023001 (2019), eprint 1812.10919.
  * She et al. (2020) Z. She et al. (CDEX), Phys. Rev. Lett. 124, 111301 (2020), eprint 1910.13234.
  * McDermott and Witte (2020) S. D. McDermott and S. J. Witte, Phys. Rev. D 101, 063030 (2020), eprint 1911.05086.
  * Flambaum and Samsonov (2019) V. V. Flambaum and I. B. Samsonov, Phys. Rev. D 100, 063541 (2019), eprint 1908.09432.
  * Garcia et al. (2020) A. A. Garcia, K. Bondarenko, S. Ploeckinger, J. Pradler, and A. Sokolenko, JCAP 10, 011 (2020), eprint 2003.10465.
  * Caputo et al. (2020) A. Caputo, H. Liu, S. Mishra-Sharma, and J. T. Ruderman, Phys. Rev. Lett. 125, 221303 (2020), eprint 2002.05165.
  * Witte et al. (2020) S. J. Witte, S. Rosauro-Alcaraz, S. D. McDermott, and V. Poulin, JHEP 06, 132 (2020), eprint 2003.13698.
  * An et al. (2020) H. An, F. P. Huang, J. Liu, and W. Xue (2020), eprint 2010.15836.
  * Fitzpatrick et al. (2021) P. J. Fitzpatrick, H. Liu, T. R. Slatyer, and Y.-D. Tsai (2021), eprint 2105.05255.
  * Fabbrichesi et al. (2020) M. Fabbrichesi, E. Gabrielli, and G. Lanfranchi (2020), eprint 2005.01515.
  * Caputo et al. (2021) A. Caputo, C. A. J. O’Hare, A. J. Millar, and E. Vitagliano (2021), eprint 2105.04565.
  * Nelson and Scholtz (2011) A. E. Nelson and J. Scholtz, Phys. Rev. D 84, 103501 (2011), eprint 1105.2812.
  * Arias et al. (2012) P. Arias, D. Cadamuro, M. Goodsell, J. Jaeckel, J. Redondo, and A. Ringwald, JCAP 06, 013 (2012), eprint 1201.5902.
  * Dror et al. (2019) J. A. Dror, K. Harigaya, and V. Narayan, Phys. Rev. D 99, 035036 (2019), eprint 1810.07195.
  * Agrawal et al. (2020) P. Agrawal, N. Kitajima, M. Reece, T. Sekiguchi, and F. Takahashi, Phys. Lett. B 801, 135136 (2020), eprint 1810.07188.
  * Co et al. (2019) R. T. Co, A. Pierce, Z. Zhang, and Y. Zhao, Phys. Rev. D 99, 075002 (2019), eprint 1810.07196.
  * Bastero-Gil et al. (2019) M. Bastero-Gil, J. Santiago, L. Ubaldi, and R. Vega-Morales, JCAP 04, 015 (2019), eprint 1810.07208.
  * Long and Wang (2019) A. J. Long and L.-T. Wang, Phys. Rev. D 99, 063529 (2019), eprint 1901.03312.
  * Jaeckel and Roy (2010) J. Jaeckel and S. Roy, Phys. Rev. D 82, 125020 (2010), eprint 1008.3536.
  * Danilov et al. (2019) M. Danilov, S. Demidov, and D. Gorbunov, Phys. Rev. Lett. 122, 041801 (2019), eprint 1804.10777.
  * Redondo (2008) J. Redondo, JCAP 07, 008 (2008), eprint 0801.1527.
  * Ehret et al. (2010) K. Ehret et al., Phys. Lett. B 689, 149 (2010), eprint 1004.1313.
  * Betz et al. (2013) M. Betz, F. Caspers, M. Gasior, M. Thumm, and S. W. Rieger, Phys. Rev. D 88, 075014 (2013), eprint 1310.8098.
  * Guo et al. (2019) H.-K. Guo, K. Riles, F.-W. Yang, and Y. Zhao, Commun. Phys. 2, 155 (2019), eprint 1905.04316.
  * Co et al. (2021) R. T. Co, K. Harigaya, and A. Pierce (2021), eprint 2104.02077.
  * Di Valentino et al. (2021) E. Di Valentino, O. Mena, S. Pan, L. Visinelli, W. Yang, A. Melchiorri, D. F. Mota, A. G. Riess, and J. Silk (2021), eprint 2103.01183.
  * Wadekar and Farrar (2019) D. Wadekar and G. R. Farrar (2019), eprint 1903.12190.
  * Greisen (1966) K. Greisen, Phys. Rev. Lett. 16, 748 (1966).
  * Zatsepin and Kuzmin (1966) G. T. Zatsepin and V. A. Kuzmin, JETP Lett. 4, 78 (1966).
  * Weisskopf et al. (2002) M. C. Weisskopf, B. Brinkman, C. Canizares, G. Garmire, S. Murray, and L. P. Van Speybroeck, Publ. Astron. Soc. Pac. 114, 1 (2002), eprint astro-ph/0110308.
  * Turner et al. (2001) M. J. L. Turner et al., Astron. Astrophys. 365, L27 (2001), eprint astro-ph/0011498.
  * Merloni et al. (2012) A. Merloni, P. Predehl, W. Becker, H. Böhringer, T. Boller, H. Brunner, M. Brusa, K. Dennerl, M. Freyberg, P. Friedrich, et al., arXiv e-prints arXiv:1209.3114 (2012), eprint 1209.3114.
  * Hui et al. (2017) L. Hui, J. P. Ostriker, S. Tremaine, and E. Witten, Phys. Rev. D 95, 043541 (2017), eprint 1610.08297.
  * Alonso-Álvarez et al. (2020) G. Alonso-Álvarez, R. S. Gupta, J. Jaeckel, and M. Spannowsky, JCAP 03, 052 (2020), eprint 1911.07885.
  * Dent et al. (2020) J. B. Dent, B. Dutta, J. L. Newstead, A. Rodriguez, I. M. Shoemaker, Z. Tabrizi, and N. T. Arellano (2020), eprint 2012.07930.
  * Gaisser et al. (2013) T. K. Gaisser, T. Stanev, and S. Tilav, Front. Phys. (Beijing) 8, 748 (2013), eprint 1303.3565.
  * Xia et al. (2020) C. Xia, Y.-H. Xu, and Y.-F. Zhou (2020), eprint 2009.00353.
  * Evans et al. (2016) N. W. Evans, J. L. Sanders, and A. Geringer-Sameth, Phys. Rev. D 93, 103512 (2016), eprint 1604.05599.
  * Dekker et al. (2021) A. Dekker, E. Peerbooms, F. Zimmer, K. C. Y. Ng, and S. Ando (2021), eprint 2103.13241.
  * Bringmann and Pospelov (2019) T. Bringmann and M. Pospelov, Phys. Rev. Lett. 122, 171801 (2019), eprint 1810.10543.
  * Wang et al. (2020) W. Wang, L. Wu, J. M. Yang, H. Zhou, and B. Zhu, JHEP 12, 072 (2020), [Erratum: JHEP 02, 052 (2021)], eprint 1912.09904.
  * Su et al. (2020) L. Su, W. Wang, L. Wu, J. M. Yang, and B. Zhu, Phys. Rev. D 102, 115028 (2020), eprint 2006.11837.
  * Flambaum et al. (2020) V. V. Flambaum, L. Su, L. Wu, and B. Zhu (2020), eprint 2012.09751.
  * Foster et al. (2021) J. W. Foster, M. Kongsore, C. Dessert, Y. Park, N. L. Rodd, K. Cranmer, and B. R. Safdi (2021), eprint 2102.02207.
  * Davis et al. (1975) L. Davis, A. S. Goldhaber, and M. M. Nieto, Phys. Rev. Lett. 35, 1402 (1975), URL https://link.aps.org/doi/10.1103/PhysRevLett.35.1402.
  * Jaeckel and Ringwald (2010) J. Jaeckel and A. Ringwald, Ann. Rev. Nucl. Part. Sci. 60, 405 (2010), eprint 1002.0329.
  * GOLDHABER and NIETO (1971) A. S. GOLDHABER and M. M. NIETO, Rev. Mod. Phys. 43, 277 (1971), URL https://link.aps.org/doi/10.1103/RevModPhys.43.277.