Constraining Linear-chain CRFs to Regular Languages
Authors: Sean Papay
Roman Klinger
Sebastian Pado
Venue: ICLR 2022 Poster (2022)
Keywords: constrained training
probabilistic graphical models
CRF
semantic role labeling
sequence labeling

Abstract: 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 local dependencies in the output. However, the CRF's Markov assumption makes it impossible for CRFs to represent distributions with 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.

Published as a conference paper at ICLR 2022
CONSTRAINING LINEAR-CHAIN CRFs TO REGULAR LANGUAGES
Sean Papay, Roman Klinger, & Sebastian Padó University of Stuttgart
pspan |kl knng paddo) @ @ims. uni -tw.ttgtttteeeeee.de.
ABSTRACT
A major challenge in structured prediction is 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 local dependencies in the output. However, the CRF's Markov assumption makes it impossible for CRFs to represent distributions with nonlocal dependencies, and standard CRFs are unable to respect nonlocal constraints of the data (such global arity constraints on output labels). We present generalization of CRFs that can enforce a broad class of constraints, including nonlocal ones, by specify- ing the space of possible output structures as regular language L. The resulting standard regular-constrained CRF (RegCCRF) has the same formal properties CRF. but assigns zero probability to all label sequences not in C. Notably, RegC- CRFs 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. Finally, we demonstrate practical benefit downstream tasks by incorporating a RegCCRF into a deep neural model for semantic role labeling, exceeding state-of-the-arr results standard dataset.
INTRODUCTION
Structured prediction is field of machine learning where outputs are expected to obey some pre- defined 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- graph-structured output), natural language processing (e.g., linguistic parsing (Niculae et al. 2018) with tree-structured output, relation extraction (Roth & Yih 2004) with tuple-structured out- put) or modeling the spatial structure of physical entities and processes (Jing
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 fixed of nodes, maximal arbores- cence algorithms allow for exact inference (Chul 1965 Edmonds] 1967); when outputs are graph- structured, loopy belief propagation can provide approximate inference (Murphy al. 1999).
If the output forms a linear sequence, a Markov assumption is often made: model outputs depend only on their immediate neighbors. but not (directly) on more distant ones. A common model that uses this assumption is the linear-chain conditional random field (CRF) (Lafferty et al.) (200T). which has found ubiquitous use for sequence labeling tasks, including part-of-speech tagging (Gimpel et al., (201)) and named entity recognition (Lample et al.) 2016). This model became popular with the use of hand-crafted feature vectors the 2000s, and is nowadays commonly used as an output layer in neural networks to encourage the learning of structural properties of the output sequence. The Markov assumption makes training tractable, but also limits the CRF's expressive power, which can hamper performance, especially for long sequences (Scheible al. 2016). Semi-Markon CRFs (Sarawagi & Cohen, 2004) and skip-chain CRFs (Sutton & McCallum, 2004) are techniques for relaxing the Markov assumption, but both come with drawbacks in performance and expressiveness.

---

Published as a conference paper at ICLR 2022
In this work, we propose new method to tractably relax the Markov assumption in CRFs. Specif- ically, we show how to constrain the output of a CRF 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 guaranteed respect these constraints. The domain knowledge specifying these constraints is defined via regular expressions, straightfor- ward, well understood formalism. We show that our method is distinct from approaches that enforce constraints at decoding time, and that it better approximates the true data distribution. We evaluate our model empirically as the output layer of a neural network and attain state-of- of-tth-art performance for semantic role labeling (Weischedel et al. 2011 Pradhan et al. 2012). Our PyTorch RegCCRF implementation can be used as drop-in replacement for standard CRFs.
RELATED WORK
We identify three areas of structured prediction that are relevant to our work: constrained decod- ing, which can enforce output constraints at decoding time, techniques for weakening the Markov assumption of CRFs to learn long-distance dependencies, and weight-learning in finite-state trans- ducers.
Constrained decoding. A common approach to enforcing constraints in model output is con- strained decoding: Models are trained in standard fashion, and decoding ensures that the model output satisfies the constraints. This almost always corresponds to finding or approximating a ver- sion of the model's distribution conditionalized on the output obeying the specified constraints. This approach is useful if constraints are not available at training time, such as in the interactive infor- mation extraction task of Kristjansson et al. (2004). They present constrained conditional random fields, which can enforce that particular tokens are or are not assigned particular labels (positive and negative constraints, respectively). Formally, our work is strict generalization of this approach, as position-wise constraints can be formulated as regular language, but regular languages go beyond position wise constraints. Other studies treat decoding with constraints as search problem, search- ing for the most probable decoding path which satisfies all constraints. For example. He et al. (2017) train a neural network to predict token-wise output probabilities for semantic role labeling following the BIO label-alphabet (Ramshaw & Mareus 1999), and then exact A * search to ensure that the output forms a valid BIO sequence and that particular task- aesk-specific constraints are satisfied. For au- toregressive models, constrained beam search (Hokamp & Liu 2017 Anderson et al.) 2017 Hasler et al. 2018) can enforce laaguagle constraints during search. We further discuss constrained decoding relates RegCCRFs in Section
Markoy relaxations. While our approach can relax the Markov assumption of CRFs through non- local hard constraints, another strand of work has developed models which can directly learn nonlo- cal dependencies in CRFs: Semi-Markov CRFs (Sarawagi & Cohen, (004) relax the Markov prop- erty the semi-Markov property. In this setting, CRFs are tasked with segmentation, where individ- ual segments may depend only on their immediate neighbors, but model behavior within a particu- lar segment need not be Markovian. As such, semi-Markov CRFs are capable of capturing nonlocal dependencies between output variables, but only to range of one segment and inside of segment. Skip-chain CRFs (Sutton & McCallum (2004) change the expressiveness of CRFs by relaxing the as- sumption 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, c.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.
Weight learning for finite-state transducers. While our approach focuses on the task of con- straining the CRF distribution to known regular language, a related task is that of learning weighted regular language from data. This task is usually formalized as learning the weights of a weighted finite-stee state transducer (FST), in e.g. Eisner (2002) with directly parameterized weights and Rastogi et al. (2016) with weights parameterized by a neural network. Despite the difference in task-setting, this task is quite similar ours in the formal sense, and in fact our proposal can be
2

---

Published as a conference paper at ICLR 2022
viewed as particularly well-behaved special case of FST weight learning for appropriately cho- sen transducer architecture and parameterization. We discuss this connection further in Section 4.3
PRELIMINARIES AND NOTATION
As our construction involves sinite-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 be nondeterministic finite-state automata (NFAs) without epsilon transitions. Let such an NEA be defined as a 5-tuple (E, Q. 91, F, E), where E ={a, (2....,.(E)) is a finite alphabet of symbols, Q= {41 92: -... Q) is finite set of states, E Q is the sole starting state, F C Q is a set of accepting states, and E' C Q x Σ x Q is set of directed, symbol-labeled edges between states. The edges define the NEA's transition func- tion A Q x Σ + 29, with r E Agg, a) ++ (q, r. E E. An automaton is said to accept string E E' iff there exists a contiguous path of edges from 91 to some accepting state whose edge labels are exactly the symbols of 8. The language defined by an automaton is the set of all such accepted strings. A language regular if and only it is the language of some NFA.
Linear-chain conditional random fields. Linear-chain conditional random fields (CRFs) Lafferty al. (2001) are a sequence labeling model. Parameterized by 9, they use global exponential model to represent the conditional distribution over label sequences y (yn, 1/, .... ./tt)))) conditioned on input sequences æ (2, 22): Po x)) exp E, få (az, y). with individual observations T, coming from some observation space X, and outputs y/ 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;. In order to avoid ambiguity, and since the term "state" already has a meaning for NEAs, we call y the CRF's tag sequence, and each yi tag. The terms label sequence and label will thus unambiguously refer to the original dataset labels.
Each f is potential function of and y. parameterized by 0. Importantly, in a linear-chain CRF, these potential functions are limited to two kinds: The transition function go (ye, 96+11) assigns a potential to each pair (yt, 3i++1) of adjacent tags y. and the emission function ha(y xx i) assigns a potential to each possible output tag y given the observation sequence æ and its position i. With these, the distribution defined by a CRF
Po a:) exp Σ go (o M6+1)
Σ ho (ar, Vo. ha(ar,y..))
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 & Martin 2009) can calculate negative log- likelihood (NLL)) loss during training, and the Viterbi algorithm (Viterbi, 1967 Jurafsky & Martin) 2009) can be used for inference. Both are linear in t, and quadratic in Y in both time and space.
4
CRFS
Given a regular language C, we would like to constrain a CRF to L. We formalize this notion of constraint with conditional probabilities CRF constrained to L is described by (further) conditionalized version of that CRF's distribution Po x), conditioned on the event that the tag sequence y is in L. We write this distribution as
sa Poly x)) if E L otherwise,
Po xr L)
10
with a 2 1 defined as a -1 Eyec Po(y x)).
In order to utilize this distribution for machine learning, we need to be able to compute NLL losses and perform MAP inference. As discussed in Section both of these efficiently computable for CRFs. Thus, if we can construct a separate CRF whose output distribution can be interpreted as P(y ær, L),, both of these operations will be available. We do this in the next section.
3

---

Published as a conference paper at ICLR 2022
Az L)
ha(an, 0,
(a 3)
Au (a. 1.4)
B
in 9,03
SolB. 0)
[v(OO.B] B
Bu(B.1)
Y' {I 2.1) (n 3,2)) (22440) (12 Braa). Lea). (ax Smr). , (ax (gg)) (gs Lgx) (vo 2sss) (5sss,(() (4x 2,
Figure 1: Example for RegCCRE, showing NFA and unrolled factor graph. describes the lan-
guage (0 BI'O'
)I")" )* the language of valid BIO sequences for an even number of spans. We would like to calculate (3 x. L) for y = (B. O, B,I),, I). We show an unambiguous automaton M for & (left), and factor graph (right) for the auxiliary CRF computing (o x)), where y' Y corresponds to the sole accepting path of y through M (marked).
4.1 CONSTRUCTION
Let M = F)) be an NEA that describes L. We assume that M is unambiguous i.e.. every string in L is accepted by exactly one path through M. As every NEA can be transformed into equivalent unambiguous NEA (Mohri 2012), this assumption involves no loss of generality. Our plan is to represent Po x; L) by constructing a separate CRF with a distinct tag set, whose output sequences
be interpreted directly as paths through M. As M is unambiguous, each label sequence in L. corresponds to exactly one such path. We parameterize this auxiliary CRF identically our original CRF that is, with label-wise (not tag-wise) transition and emission functions. Thus, for all parameterizations 0, both distributions Po x) and Po σ; L) are well defined.
There are many ways construct such a CRE As CRF training and inference are quadratic in the size of the tag set Y, we would prefer construction which minimizes (Y). However, for clarity, we will first present conceptually simple construction, and discuss approaches reduce |Y] in Section 4.2 We start with our original CRF, parameterized by 0, with tag set Y Σ, transition function go. and emission funetion he, describing the probability distribution Po(y .>), y Σ" From this, we construct new CRE, also parameterized by the same 0, but with tag set Y', transition function Lg. and emission function h₂g This auxiliary CRF describes the distribution P/(3'' x) (with y E Y"),, which we will be able to interpret as Po x, L). The construction is as follows:
Y'=
(3)
ao) = -00
(4)
otherwise
if = 1,9 if = t otherwise.
1o( (g,0,
(5)
ho(a, a,
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 edge labels, and not on the edges themselves, and agree with the standard CRF's ge and he when no constraints are violated.
As M is unambiguous, every tag sequence y corresponds to single path through M, representable as an edge sequence π = (T1, T2...., Tt), म. E E. Since this path is a tag sequence for our auxiliary CRF, we directly calculate the auxiliary CRF's (T x). From the construction of d and h/ this must be equal to Po x, L), as it is proportional to Po x) for e L, and zero (or, more correctly, undefined) otherwise. Figure T illlstrraees this construction with concrete example.
4

---

Published as a conference paper at ICLR 2022
4.2 TIME AND SPACE EFFICIENCY
As the Viterbi and forward algorithms are quadratic in [Y,, very large tag sets can lead to perfor- mance issues, possibly making training or inference intractible in extreme cases. Thus, we would like to characterize under which conditions RegCCRF can be used tractibly, and identify tech- niques for improving performance. As Y corresponds to the edges of M, we would like to select our unambiguous automaton M to have as few edges as possible. For arbitrary languages, this problem NP-complete (Jiang & Ravikumar 1991,, , and, assuming P * NP, is not even efficiently approx- imable (Gruber & Holzer] 2007). Nonetheless, for many common classes of languages, there exist approaches to obtain a tractably small automaton.
One straightforward method is to construct M directly from a short unambiguous regular expression. Brüggemann Klein & Wood (1992) present a simple algorithm for constructing an unambiguous automaton from unambiguous regular expression, with Q) linear in the length of the expression. Using this method to construct M, the time- and space- complexxyy of Viterbi are polynomial in the length of our regular expression, with worst-case of quartic complexity when the connectivity graph of M is dense.
For many other tasks, reasonable approach is to leverage domain knowledge about the constraints to manually construct a small unambiguous automaton. For example, if the constraints require that a particular label occurs exactly n times in the output sequence, an automaton could be constructed manually to count ocurrences of that label. Multiple constraints of this type can then be composed via automaton union and intersection.
Without making changes to M. we can also reduce the size of |Y| by adjusting our construction. In- stead of making each edge of M tag, we can adopt equivalence classes of edges. Reminiscent of standard NFA minimization, we define (g, a. ~ (g', a'' r') ++ a) = (4' a'). When construct- ing our CRF, whenever transition would have been allowed between two edges, we allow tran- sition 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 L just as before.
4.3 INTERPRETATION AS A WEIGHTED FINITE-STATE TRANSDUCER
While we present our model as a variation of a standard CRF which enforces regular-language constraints, an alternate characterization as a weighted tinie--ttate transducer with the transducer topology and weight parameterization chosen so to yield the distribution Po(y æ, L)) In order to accommodate CRF transition weights, such an approach involves weight-learning in an auxiliary automaton whose edges correspond to edge-pairs in M we give full construction in Appendix C
This interpretation enables direct comparison to studies on weight learning in finite-state transducers, such as Rastogi et al. (016). While RegCCRF's can be viewed as special cases of neural-weighted FSTs, they inherit number of useful properties from CRFs not possessed by neural-weighted au- tomata in general. Firstly, as |y/ is necessarily equal to xz). the partition function Σvec Po(y) x, L) is guaranteed to be finite, and Pu xx, L) is a well-defined probability distribution for all f which is not true for weighted transducers in general, which may admit paths with unbounded lengths and weights. Secondly, as M is assumed to be unambiguous, string probabilities correspond exactly to path probabilities, allowing for exact MAP inference with the Viterbi algorithm. In contrast, finding the most probable string in the highly ambiguous automata used when learning edge weights for an unknown language is NP-Hard (Casacuberta & de la Higuera 1999), necessitating approximation methods such as crunching (May Knight 2006). Finally, as each RegCCRF can be expressed as CRF with a particular parameterization, the convexity guarantees of standard CRFs carry over, in that the loss is convex with respect to emission and transition scores. In contrast, training losses in general weighted finite-state transducers are usually nonconvex (Rastogi et al. 2016
5 CONSTRAINED TRAINING VS. CONSTRAINED DECODING
Our construction suggests two possible use cases for RegCCRF: constrained decoding, where CRF is trained unconstrained, and the learned weights are then used in a RegCCRF at decoding time, and constrained training, where RegCCRF is both trained and decoded with constraints. In
5

---

Published as a conference paper at ICLR 2022
this section, 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 P(æ, y). with each æ E X and each of matching length in some regular language L S 2 We wish to model the conditional distribution P(y x)) with either CRF or RegCCRF, by way of maximizing the model's ' (log) likelihood given the data distribution.
The unconstrained CRF corresponds to CRF that has been trained, without constraints, data from P(x, y). and is used directly for inference: It makes no of the language L. The model's output distribution is Po_ (y æ),, with parameter vector 02 minimizing the NLL objective:
6 arg min F. F (- In Po x;)]
In constrained decoding. CRF is trained unconstrained, but its weights are used in RegCCRF decoding time. The output distribution of such a model is Po. (y æ, C). It is parameterized by the same parameter vector 02 the unconstrained CRF, the training procedure is identical, but the output distribution is conditioned on y E L.
Constrained training involves directly optimizing RegCCRF's output distribution, avoiding any asymmetry between training and decoding time. In this case, the output distribution of the model is (y æ; L), where
f. arg min E -. In Po x, C)]
is the parameter vector which minimizes the NLL of the RegCCRF's constrained distribution.
These three approaches form hierarchy in terms of their ability match the data distribution: Lunconstrained 2 Leonstrained decoding 2 Leonstrained training. with each L corresponding to the negative log- likelihood assigned by each model to the data; see Appendix Bor a proof. This suggests we should prefer the constrained training regimen.
6 SYNTHETIC DATA EXPERIMENTS
While constrained training cannot underperform constrained decoding, the conditions where it is strictly better depend exactly how the transition and emission functions parameterized, and are not easily stated in general terms. We now empirically show two simple experiments on synthetic data where the
equivalent.
The procedure similar for both experiments. We specify a regular language L, an observation alphabet X, and joint data distribution P(z, y) over observation sequences in X and label se- quences in L. We then train two models, one with RegCCRF, parameterized by 9.. and one with an unconstrained CRF, parameterized by 0,. For each model, we initialize parameters randomly, then use stochastic gradient descent to minimize NLL with P. We directly generate samples from P to as training data. After optimizing 0g and Ou, construct RegCCRF with O,, for use model, and we compare the constrained-trainn with the cusstrined--eecoiinn distribution Pe_ (y x, L).
constrained
distribution Pe. (3 x. L)
We use a simple architecture for our models, with both the transition functions and emission functions he represented as parameter matrices. We list training hyperparameters in Appendix A
6.1 ARBITRARILY LARGE DIFFERENCES IN LIKELIHOOD
We would like to demonstrate that, when comparing constrained training to constrained decoding in terms of likelihood, constrained training can outperform constrained decoding by an arbitrary margin. We choose L (ac)* (bc)* to make conditional independence particularly relevant as every even-indexed label is c, an unconstrained CRF must model anddinnexed labels independently, while a constrained CRFcan use its constraints to account for nonlocal dependencies. For simplicity, we hold the input sequence constant, with X = {o).
Our approach is to construct sequences of various lengths. For k N, we let our data distribution be
2k (ac)*) = 4
and P(o 2h (bc)*) = 4'
(8)

---

Published as a conference paper at ICLR 2022
Constrained decoding
5
Constrained training
Negative log: lil--iiklhhodd
Data distribution entropy
0.8
P((aa))
3
0.4
2
Constrained decoding
Constrained training
Data distribution
5
10
15
20
&
Figure 2: Model output probabilities, and NLL losses, plotted against sequence length k. As k in- creases, constrained decoding becomes a progressively worse approximation for the data distribu- tion, while constrained training is consistently able to match the data distribution.
Table 1: Output distributions for constrained decoding (Po. Ix, and constrained training (Po, (y/ æz L)), compared the data distribution Ply æ). Constrained decoding cannot learn the data distribution exactly, and yields mode which disagrees with that of the data distribution.
y
P(y a))
Po., (y/ x. C)
(v. x, L)
acd
0.4
0.32
0.40
bcd
0.3
0.48
0.30
bce
0.3
0.20
0.30
As the marginal distributions for odd-indexed characters are not independent, an unconstrained CRF cannot exactly represent the distribution P. We train and evaluate individual models for each se- quence length k. Figure plots model probabilities and NLL losses for various k. We see that, re- gardless of k, Pe. (y x. L) is able to match P(y x)) almost exactly, with only small deviations due to sampling noise in SGD. On the other hand, as sequence length increases, Po., (y æ, L) becomes progressively "lop-sided", assigning almost all of its probability mass the string (ac)*. This be- havior reflected in the models' likelihoods constrained training stays at near-constant likelihood for all k, while the negative logelikelihood of constrained decoding grows linearly with k.
6.2 DIFFERENCES MAP INFERENCE.
We show here that constrained training and constrained decoding can disagree about which label se- quence they deem most likely. Furthermore, in this case, MAP inference agrees with the data distri- bution's 's mode for constrained training, but not for constrained decoding. To do this, we construct fixed-length output language
a add bed bce, where an unconstrained CRF limited by the Markov property to predict y prefix and suffix independently, and choose data distribution which violates this independence assumption. We select our data distribution.
P(ooo, acd) 0.4 and P(ooo,
0.3 and P(ooo, bce) 0.3,
be close 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.c. bcd). As before, we hold the observation sequence as a constant (ooo), We train constrained and unconstrained CRF to convergence, and compare Po., (y x L) to Po, (y x. L).
Table shows Po., (y xx C) and Pe. x, L)) as they compare to P( x). We find that, while the mode P(y æ²) is acd, with probability of 0.4, the mode constrained decoding distribution Po., (y) L) is bod, the string with the majority prefix and the majority suffix, to which the model assigns a probability of 0.48. Conversely, the constrained training distribution Po. (y x. L)
matches the data distribution almost exactly, and predicts the correct mode.

---

Published as a conference paper at ICLR 2022
7 REAL-WORLD DATA EXPERIMENT: SEMANTIC ROLE LABELING
Task. As a final experiment, we apply our RegCCRE to the NLP task of semantic role labeling (SRL) in the popular PropBank framework (Palmer al. 2005). In line with previous work, we adopt the known-pree pron--predicat setting, where events are given and the task is to mark token spans as (types of) event participants. PropBank assumes 7 semantic core roles (ARGO through ARG5 plus ARGA) plus 21 non-core roles for modifiers such as times or locations. For example, in [ARGa Peter] saw [ARGI Paul] [ARGM-TMP yesterday], the argument labels inform us who does the seeing (ARGO), who is seen (ARGI), 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 naturally sequence labeling task (He 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 most once per event; (2) for continuations, the span type must occur previously in the sentence; (3) for references, the span type must occur elsewhere in the sentence.
Data. In line with previous work (Ouchi et al. 2018). we work with the OntoNotes corpus as used in the CoNLL 2012 shared task]] (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).
RegCCRF Models. To encode the three constraints listed above in a RegCCRF, we define a regu- lar language describing valid BIO sequences (Ramshaw & Marcus, 1999) over the 66 roles. A min- imal unambiguous NEA for this language has more than 2 states, which is too large to run the Viterbi algorithm our hardware. However, many labels are very rare, we can shrink our au- tomaton by discarding them at the cost of imperfect recall. We achieve further reductions in size by ignoring constraints reference roles, treating them identically to non-core roles. Our final au- tomaton recognizes 5 core role types (ARGO through ARG4), 17 non-core reference roles, and one continuation role type (for ARGI). This automaton has 672 states, yielding RegCCRF with 2592 tags. A description of our procedure for constructing this automaton can be found in Appendix [D]
Our model architecture is given by this RegCCRF, with emission scores provided by linear projec- tion 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 special reserved token in the input se- quence. RoBERTa parameters are fine-tuned during the learning of transition scores and projection weights. We perform experiments with both constrained training and constrained decoding settings we will refer to these as ConstrTr and ConstrDec respectively. A full description of the training procedure, including training times, provided in Appendix [A] As RegCCRF loss is only finite for label sequences in L. we must ensure that our training data do not violate our constraints. We dis- card some roles, as described above, by simply removing the offending labels from the training data. In six cases, training instances directly conflict with the constraints specified all cases involve continuation roles missing a valid preceding role. We discard these instances for ConstrTr.
CRF Baselines. As baseline models, we use the same architecture, but with a standard CRF re- placing the RegCCRF. Since we are not limited by GPU memory for CRFs, we are optionally able to include all role types present in the training set, using the complete training set. We present two CRF baseline models: CRF-full, which is trained on all role-types from the training set, and CRF- reduced, which includes the same subset of roles as the RegCCRF models. For CRF-reduced, we use the same learned weights as for CD, but we decode without constraints.
Results and analysis. We evaluate our models on the evaluation partition, and measure perfor- mance using Fi score for exact span matches. For comparability with prior work, we use the evalu- ation scripf" for the CoNLL-2005 shared task (Carreras & Märquez 2005). These results, averaged Excepting CRF-reduced, all of our models outperform the existing state-of-the--rt ensemble model Ouchi et al. (2018). We ascribe this improvement over the existing literature to our use of RoBERTa - prior work in SRL relies on ELMo (Peters et al. 2018). which tends to underperform transformer- model models downstream tasks (Devlin et al. 2019
over five trials, are presented in Table 2
As downloaded from ht httpa///////////ooooooo/oeeeeeee cording to httt:s///ccaaai..oooo//aattttttt As available hwtpp::/www.c...c...tt
and preprocessed ac-
8

---

Published as a conference paper at ICLR 2022
Table 2:
Results from our experiments (averaged over 5 trials), along with selected reported results
from recent literature. We rank of our models by precision, recall, and Fi score rankings differ if and only the difference is significant at p < 0.05 (two-tailed), measured by permutation test.
Model
Precision Recall
F (rank)
RoBERTa CRF (CRF-full)
86.82
87.73(1
87,27
Our experiments
RoBERTa CRF (CRF-reduced)
87.33
85,95(3)
86.63(3)
RoBERTa RegCCRF (ConstrDec)
87.28(1)
87.13
87.20
RoBERTa+ RegCCRF (ConstrTr)
87.22
87.79(1
87.51 (1)
He et al.
2017)
85.5
Results
Ouchi et al.
(2018)
87.1
85.3
86.2
from literature
Ouchi el al.
2018
(ensemble)
88.5
85.5
87.0
Li al.
85.7
86.3
86.0
Of our models, ConstrTr significantly outperforms the others in F1 score and yields a new SOTA for SRL on OntoNotes, in line with expectations from theoretical analysis and on synthetic data. Our other three models show trade-off's between precision and recall, wherein CRF-fill outperforms the other two in recall and underperforms them in precision. This is not surprising, as CRF-full is the only model capable of predicting rare role types. The other models, which use the reduced tag sets, have a theoretical maximum of 99% recall. Interestingly, when comparing between the three models that use the reduced tag sets, we find a statistically significant interaction between the constraint setting and model recall, but not between constraints and model precision: ConstrTr has significantly higher recall than ConstrDec, which in turn significantly beats CRF-reduced in recall, but there are no statistically significant differences between these models' precisions.
For our unconstrained models, CRF-full and CRF-reduced, the constraints specified in our automa- ton are violated in 0.81% and 0.84% all output sequences respectively" While this number is small, it should not be interpreted mean that constraints are useless for almost all instances as shown in Section 6.2 constraints during training can affect MAP inference even when none of the alternatives violate constraints.
CONCLUSION AND FUTURE WORK
We have presented method to constrain the output of CRFs to a regular language. Our construc- tion permits constraints to be used at training or prediction time; both theoretically and empirically, training-time time constraining better captures the data distribution. Conceptually, our approach consti- tutes a novel bridge between constrained CRFs and neural-weighted FSTs,
Future work could target enhancing the model's expressibility, either by allowing constraints to de- pend explicitly on the input as regular relations, or by investigating non-binary constraints, i.e., reg- ular language-bu 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. re- ducing manual specification and identifying non-obvious constraints. Another avenue for continu- ing research lies in identifying further applications for RegCCRFs. The NLP task of relation extrac- tion could be 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 our construction can- not be lifted directly to context-free free languages due to the unbounded state space of the correspond- ing pushdown automata, context-free language can be approximated by regular languages (Mohri & Nederhof 200T). On this basis, for example, a RegCCRF backed by a regular language describing trees of limited depth could also be applied to tasks with context-free constraints.
To encourage the use of RegCCRFs, we provide an implementation as a Python library under the Apache 2.0 license which can be used drop-in replacement for standard CRFs in PyTorch
'll significance results are at the 0.05 level (two-tailed), measured by permutation test over the five trials of each model.
Foor CRF-full, we only count violations of constraints for those roles that our automaton accounts for.
Available www. uni stuuttarrttt......... http://tttt..eeeee///aaaaaeeeaee

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work is supported by IBM Research AI through the IBM AI Horizons Network.
REPRODUCIBILITT STATEMENT
To ensure reproducibility, have released all code for the RegCCRF model as an open-source Python library under the Apache 2.0 license, which is included the supplementary materials. Additionally, we include Python scripts for reproducing all experiments presented in the paper, de- tailed descriptions of our datasets and preprocessing steps, and training logs. Furthermore, Ap- pendix [ lists all model hyperparameters, details the preprocessing steps taken for our experiments, and specifies the hardware used for our experiments along with average training and inference times for each experiment.
ETHICS STATEMENT
The research in this paper is fundamental in the sense that it enables machine learning models to better represent data and limit the search space at inference and learning time. It therefore does not in and of itself represent additional ethical risks on top of the previous work we build upon.
REFERENCES
Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. Guided open vocabulary im- age captioning with constrained beam search. In Proceedings of the 2017 Conference on Empir- ical Methods Natural Language Processing, pp. 936-945, Copenhagen, Denmark, September 2017. Association for Computational Linguistics. doi: 10.18653/v1/DI7-1000 URL https:
7/ www. wwt.a//www...ortaatttooooo/////.
Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. Inference of regular expres- sions for text extraction from examples. IEEE Trunsactions on Knowledge and Data Engineer- ing, 28(5): 2016. doi: 10. 10.1009020E..2115555557
Anne Brüggemann Klein and Derick Wood. Deterministic regular languages. In Alain Finkel and Matthias Jantzen (eds.), STACS 92, pp. 173-184, Berlin, Heidelberg, 1992. Springer Berlin Hei- delberg. ISBN 978-3-540-46775-5.
Xavier Carreras and Lluís Märquez. Introduction to the CoNLL-2005 shared task: Semantic role labeling. In Proceedings of the Ninth Conference on Computational Natural Laguugee Learning (CoNLIL-2005), pp. 152-164, Ann Arbor, Michigan, June 2005. Association for Computational Linguistics. URL ht.pp:::: // wwwp///w.... ac www.
http://///......o./o////--/----/ wwtp:hhoooll//o00000o0000 0620
F. Casacuberta and C. de la Higuera. Optimal linguistic decoding is difficult computational prob- lem. Pattern Recognition Letters, 2088),113-81,, January 1999, doi: 10. 10.1016/5016--855(999) 00045-8.
Yoeng-Jin Chu. On the shortest arborescence of a directed graph. Scientia Sinica, 14:1396-1400, 1965.
Jacob Devlin, Ming-Wo Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep
bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers). pp. 4171-4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19-11 1 URL https: www. aclwei org/ http//ooooooo/M1--11
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 Computational Intelligence, pp. 396-400 vol.1, 1994. doi: 0..109/CHHC11994444999
10

---

Published as a conference paper at ICLR 2022
Jack Edmonds. Optimal branchings. Journal of Research of the National Bureau of Standards, 71B(4):233-244 1967. URL bttpp::///lpppoo nist .ov http/nistpuubs jres 71B/ jresv71Bn4p28 Alb.pdf
Jason Eisner. Parameter estimation for probabilistic finite-state transducers. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pp. 1-8, Philadel- phia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. doi: 10.3115/ pttectts://aacaantthhoi
1773083.103005
Kevin Gimpel, Nathan Schneider, Brendan O'Connor, Dipanjan Das, Daniel Mills, Jacob Eisen- stein, Michael Heilman, Dani Yogatama, Jeffrey Flanigan, and Noah Smith. Part-of-speech tag- ging for twitter: Annotation, features, and experiments. In Proceedings of the 49th Anmual Meeting of the Association for Computational Linguistics, pp. 42 47, 2011. URL httpst/:
ac wwwpooooo...gggP...
Hermann Gruber and Markus Holzer. Inapproximability of nondeterministic state and transition complexity assuming P NP, In International Conference on Developments in Language Theory, pp. 205-216. Springer, 2007.
Eva Hasler, Adrià de Gispert, Gonzalo Iglesias, and Bill Bymee Neural machine translation decod- ing with terminology constraints. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Vol- ume 2 (Short Papers), pp. 506-512, New Orleans, Louisiana, June 2018, Association for Com- putational Linguistics. doi: 10.18653/v1/N18 2081.
URL https: /www aclweb. org
anthology/NII N118 2081
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 I: Long Papers), pp. 473-483, Vancouver, Canada, July 2017. Association for Computational Linguisties. doi: 10. 10.18653/1//11--1044 URL https:
7/ /acclanthoooyy.o wwwp:/llyyy..g/11-111000000
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), pp. 1535-1546, Vancouver, Canada, July 2017. Association for Computational Linguistics. doi: 10. 10.18655/11/111-11411 ht..stss::/ www. ac web.
larg//atthology/P17--1
Tao Jiang and Bala Ravikumar. Minimal NFA problems are hard. In International Colloquium on Automala, Languages, and Programming, pp. 629-640. Springer, 1991.
Zhe Jiang, Spatial structured prediction models: Applications, challenges, and techniques. IEEE Access, 8:38714-388 3-7227, 2020. doi: 10. 10.110/CCCESSS..20.000.0 299.255584..
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), pp-
2015. doi: 21109//VPR.201..779999
Daniel Jurafsky and James H. Martin. Speech and Language Processing (2nd Edition). Prentice- Hall, Inc., USA. 2009. ISBN 0131873210.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Yoshua Bengio and Yann LeCun (cds.). 3rd International Conference on Learning Representations, ICLR 2015, San Diego CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. URL http: //arxiv.orq abs / 1112. 6980
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, pp. 412-418, 2004.
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Probabilis- tic models for segmenting and labeling sequence data. In Proceedings of the Eighteenth Interna- tional Conference on Machine Learning, pp. 282-289, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.

---

Published as a conference paper at ICLR 2022
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, pp. 260-270, San Diego, California, June 2016. Association for Computational Linguistics. doi: 10.18653//1/N11-10330)
URLhtttss /wwww/www... wwwpwwwwllw...............w..www www.wwwwwee..... web. www./orttaagogggggooeoo
N16 N16-1030
Zuchao Li, Shexia He, Hai Zhao, Yiqing Zhang, Zhuosheng Zhang, Xi Zhou, and Xiang Zhou. De- pendency span, end-to-end uniform semantic role labeling. Proceedings of the AAAI Confer- ence on Artificial Intelligence, 33(01))6730-6737, Jul. 2019. doi: 10.1609/aadi v33101.33016730.
URL https: / /ojs aaai
phpp AAA http://AAAA/aaitteeeeeee
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 pretrain- ing approach. arXiv preprint arXiv:1907.11692 2019. URL https::/aaxxte org/ abs/
1907 692
Jonathan May and Kevin Knight. better n-best list: Practical determinization of weighted finite tree automata. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pp. 351-358, New York City, USA, June 2006. Association for Computational Linguistics. URL /ttp:tt:////aaaaccloooy//
Mehryar Mohri. A disambiguation algorithm for finite automata and functional transducers. In In- lernational Conference on Implementation and Application of Automata, pp. 265-277. Springer, 2012.
Mehryar Mohri and Mark-Jan Nederhof. Regular approximation of context-free grammars through transformation. In Robustness language and speech technology, pp. 153-163. Springer, 2001.
Kevin P. Murphy, Yair Weiss, and Michael I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pp. 467-475, Stockholm, Sweden, 1999. Morgan Kaufmann Publishers Inc. ISBN 1558606149.
Vlad Niculae, Andre Martins, Mathieu Blondel, and Claire Cardie. Sparsemap: Differentiable sparse structured inference. In International Conference on Machine Learning, pp. 3799-3808. PMLR, 2018.
Hiroki Ouchi, Hiroyuki Shindo, and Yuji Matsumoto. A span selection model for semantic role labeling. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 1630-1642, Brussels, Belgium, October-November 2018. Association for Com- putational Linguistics. doi: 10.18653/v1/D18- 1191. URL https: / www. ac web. org/
1191
Martha Palmer, Daniel Gildea, and Paul Kingsbury. The Proposition Bank: An annotated corpus of semantic roles. Computational Linguisties, 31(1):11-16,, 2005. doi: 10.1162/
0891201053630264. WRLLhttps:// /www. wwwwwb.wwwe.... http://wwww.....e/a.aataaooo....
Matthew Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. In Proceedings of the 2018 Con- ference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers). pp. 2227-2237, New Orleans, Louisiana, June 2018. Association for Computational Linguistics. doi: 10.18653/v1/N18. 1202. URL https:
wwwww. aww.wb..wb..... /
hwt.:wwww.rrgg.atooooo/////////a wwt.hlogyohohl--oooooo 1202
Sameer Pradhan, Alessandro Moschitti, Nianwen Xue, Olga Uryupina, and Yuchen Zhang. CoNLL- 2012 shared task: Modeling multilingual unrestricted coreference in OntoNotes. In Joint Con- ference EMNLP and CoNLL Shared Task, pp. 1-40, Jeju Island, Korea, July 2012. As- sociation for Computational Linguistics. URL https: www. aclweb. wwwp.otoooaaaggy///////
w12-4501
12

---

Published as a conference paper at ICLR 2022
Lance Ramshaw and Mitchell Marcus. Text chunking using transformation-basee based learning. In Nar- ural Language Processing Using Very Large Corpora, pp. 157-176. Springer Netherlands, Dor- drecht. 1999. ISBN 978 94-017-2390-9. doi: 10.1007/978-94401--299990 10. URL https::: 7/doi.org/ 0
-1---------------- 9_
Pushpendre Rastogi, Ryan Cotterell, and Jason Eisner. Weighting finite-state transductions with neural context. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pp. 023-633, San Diego, California, June 2016. Association for Computational Linguisties. doi: 10. 18653v1/ N16-1076. URL https:/ / /tt:://clll
Dan Roth and Wen-tau Yih. A linear programmming formulation for global inference in natural language tasks. In Proceedings of the Eighth Conference on Computational Natural Language
Learning (CoNLL1-2004) at HL.I-NAACI. 2004, pp. 1-8, Boston, Massachusetts, USA, May May 7 2004. Association for Computational Linguistics. URL.ttps: /ttp::///wwwwweo
http://wwwwwwlllll....co.. acl www.eb...bb..................... wob.gr////rr/.
anthology/N04 2401
Sunita Sarawagi and William W Cohen. Semi-markov conditional random fields for information extraction. Advances in neural information processing systems, 17:1185-1192 2004.
Christian Scheible, Roman Klinger, and Sebastian Pad6. Model architectures for quotation detec- tion. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1736-1745 Berlin, Germany, August 2016. Association for Com- putational Linguistics. doi: 10.18653/v1/P16- 1164. URL
P16 (66-1664
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.
Andrew Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions Information Theory, 13(2):260-669, 1967. doi: 10.1 109/TIT. 1967.1054010.
Ralph Weischedel, Eduard Hovy, Mitchell Marcus, Martha Palmer, Robert Belvin, Sameer Pradhan, Lance Ramshaw, and Nianwen Xue. Ontonotes: A large training corpus for enhanced process- ing. In Handbook of Natural Language Processing and Machine Translation: DARPA Global Au- tonomous Language Exploitation. Springer, 2011.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Seao, Sylvain Gug- ger, 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, pp. 38 45, Online, October 2020. As- sociation for Computational Linguistics. URL https:: //www acl wwwweb..b......ccccccc......ceeb org.abhhoo///t/oo 2020. wwn.p-demos........ee-oc-eemm
A EXPERIMENTAL DESIGN
This appendix details the training procedures and hyperparameter choices for our experiments. These are summarized in Table 3 Full code for all experiments, along with training logs, are also included in the supplementary materials.
A.1 CRFS
For all CRFs and RegCCRFs, transition potentials were initialized randomly from a normal distribu- tion with mean zero and standard deviation 0.1. No CRFs RegCCRFs employed special start- or toddtrannitions- - that is, we did not insert any additional foinning-of-sqqueeee or end-of cad-of-sequence tags for the Viterbi or forward algorithms.
13

---

Published as a conference paper at ICLR 2022
Table 3: Summary of hyperparameters for models and experiments.
CRFs
Transition score initialization
(0.00.1)
Emission score initialization
PyTorch default
Optimizer
SGD
Synthetic data experiments
Training iterations
5000
Batch size
50
Initial learning rate
1.0
Learning rate decay
10% every 100 steps
RoBERTa weights
roberta-base PyTorch default Adam 10-5
Projection weight and bias initialization
Optimizer
SRL experiments
learning rate
Batch size
2
Gradient accumulation
4 batches
A.2 SYNTHETIC DATA EXPERIMENTS TRAINING PROCEDURE
For both synthetic data experiments, the emission potentials represented explicitly for each position as trainable parameters since the observation sequence was constant in all experiments, these did not depend on æ.
Parameters were initialized randomly using PyTorch default initialization, and optimized using stochastic gradient descent. To ensure fast convergence ing rate decay- learning rate was initially set to 1.0, and reduced by 10% every 100 training steps.
stable distribution, we employed learn-
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 A the total training time this experiment was approximately 35 minutes. The experiment described in Section 6.2 completed training in approximately 30 seconds.
A.3 SEMANTIC ROLE LABELING TRAINING PROCEDURE
In the semantic role labeling (SRL) experiments, incorporated pretrained RoBERTa net- work (Liu et al. 2019) the implementation and weights for this model were obtained using the roberta--ae -aarttabaaee model from the Hugging Face transformers library (Wolf al. 2020). RoBERTa embeddings were projected down to transmission scores using linear layer with bias projection weights and biases were initialized using the PyTorch default initialization.
Input tokens were sub-tokenized using RoBERTa's tokenizer. The marked predicate in each sentence was prefixed by special <unk> token. During training. for efficiency reasons, 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 Kingmma & Ba 2015) with a learning rate of 10-5, We fine-tune RoBERTa parameters and learn the projection and RegCCRF weights jointly. For performance reasons, batch size was set to 2, but we utilized gradient accumulation over groups of batches simulate a batch size
We utilized early stopping to avoid overfitting. Every 5000 training steps, we approximated our model's s F1 score against subset of the provided development partition, using simplified reimple- mentation of the official evaluation script. Each time exceeded the previous best Fi score for model. we saved all model weights to disk. After 50 such evaluations with no improvement, we ter- minated 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 average of 88 hours for RegCCRF models with constrained training, 23 hours for RegCCRF with constrained decoding, and 24 hours for CRF baseline models. Inference on the complete test set took average of 18 minutes 55 seconds for CT and CD, and an average
14

---

Published as a conference paper at ICLR 2022
of 55 seconds for CRF-full and CRF-reduced. All training logs with timestamps included in the supplementary materials.
B PROOF OF CONSTRAINED TRAINING INEQUALITY
In this appendix, we prove the inequality presented in section when compared by NLL against the data distribution, Lumconstrained 2 Leonstrinned decoding 2 Leonstrainee training, with each L corresponding to that model's negative log-liken ogg-iiklihood. We first prove the left side of this inequality, comparing an unconstrained CRF to constrained decoding, and then prove the right side, comparing constrained decoding to constrained training. We use the notation introduced in Section 5
Theorem 1. For arbitrary 0: F Po(y x)] 2 E Pe. In Poly x L)]
Here compare the distributions (3 x)) and (y x. We wish to demonstrate that Po(y z) can never achieve lower NLL than Po æ. L), and that the two distributions achieve identical NLL only when Py x)) Po x. L) i.e. when constraints have no effect. Of note, this proof is valid for all parameterizations 0, and not just for On.
Proof. Since every y in P L.
Poly 2., L) = a Po x))
(10)
with a 2 Thus, the NLL of the regular-con constraied CRF
E y (- Pa x. L)]
Pa x)] In
(11)
This differs from the NLL of the unconstrained CRF only by the term - In a. As a 2 1, the regular- constrained CRF's NLL is less than or equal to that of the unconstrained CRF, with equality only when a = and therefore (o x) = Po(y x, C).
Theorem 2. E E Po.. (y æ, L)] E 1-
x, C)]
In this case, we compare the distributions Po (y x, L) and Po x. C). We will demonstrate that the former cannot achieve a lower NLL against the data distribution than the latter.
Proof. This follows directly from our definitions, as we define 0. to minimize the NLL of Po æ, C) against the data distribution. Thus, Ps., (y x, could never yield a lower NLL than
Po æ, L), as that would contradict our definition of 0..
C CONSTRUCTION AS WEIGHTED FST
In this appendix, we present construction of the RegCCRF as a weighted finite-state transducer with weight sharing. We do this by first specifying the transducer topology used, and then specifying how edge weights are parameterized terms of The resulting transducer yields an identical distribution to that of the CRF-based construction, Po x, C).
C.I TRANSDUCER TOPOLOGY
Starting from L, we define Č to be the regular language of bigram sequences for the strings in L, iee.
Ë (($1. 82), (82, sa), .... (8) a Sla)); ($]a 8)) E C).
(12)
with S acting end-of-string symbol. We let A be an unambiguous FSA for the language č. and choose to interpret this automaton as a inite-state transducer by stipulating that all edges should accept any symbol in the input language (but only symbol per transition, and without allowing epsilon transitions). This unweighted transducer will be used as the topology for our weighted finite- state transducer.
15

---

Published as a conference paper at ICLR 2022
C.2 EDGE WEIGHTS
In line with Rastogi et al. (2016), we would like assign weights to the edges our transducer M with neural network. In order obtain the same distribution as from our CRF-based construction, these weights must be parameterized in terms of our transition function go and emission function hg. For each edge M, the weight depends only on the emitted bigram, the input sequence, and the index of the current input symbol the weight does not depend on the FST states, For symbol bigram (a, b), input sequence æ, and index i, the edge weight is equal to
[go b) + ho(a,, a, b (ho(2, a)
W.. 0,
(13)
otherwise
Each string in C corresponds bijectively to exactly one bigram sequence in E, which corresponds bijectively to exactly one accepting path in AM - this path's weight (in the Log semiring) is equal to the unscaled probability produced by our CRF construction, and so the weighted FST, interpreted as probability distribution, yields the distribution Po L).
D AUTOMATON CONSTRUCTION FOR SEMANTIC ROLE LABELING
In this appendix, describe how generate the automaton architecture for our semantic role la- beling experiments. While our experiments used core-roles, 17 non-core roles, and one continu- ation role, discuss here generalized setting with arbitrary sets of core, noncore, and continua- tions of core roles.
Algorithm I provides pseudocode for construction. The core idea is to subsets of roles as NEA states, so that we can keep track of which core roles have already ocurred. Additional states used in order to ensure all strings valid BIO sequences.
16

---

Published as a conference paper at ICLR 2022
Data: Sets Raore Rnoncore. and Ranntimaation- of core, noncore, and continuation roles, respectively
Result; finite-state automaton M = (I, Q, 91 E), parameterized as described Section Σ < {OUTSIDE) U ((BEGIN, INSIDE} (Reore U noncore U Rcominuationn)
Q - Ø;
Q1 Ø;;
< Ø;;
E' Ø;
for p E R do
Q - Qu(p:
(
E. < [P OUTSIDE,
for r E Rnoncore do
8 (r,p);
- QU{s}:
E EU {(, (EEGIN,r),P) (p, (BEGIN, s)}:
E EU {(r, (INSIDE, r), (r, (INSIDE,T),P) p).
end for
Reontimaatio do The core role corresponding to is in p then
(r,p);
Q + QU(QQ(()))
E EU ([p, (BEGIN, p), (p, (BEGIN, s);
E + EU (INSIDE, r), 8), (r, (NSIDE,r),P)
end end for
E (Roor \,)) do
8 + (r.p);
t t (r(
Q + {8{s):
E EU (1, (BEGIN, (RGGN,r),s) 8), (p, (BEGIN, r), ()):
E + EU ((8, [INSIDE, 8), (8, (INSIDE, r)]
end end return (E, Q, E)
Algorithm 1: Construction of FSA from given sets of core, noncore, and continuation roles.
To represent BIO labels, we use tuples of the form (BEGIN, <roleType>) for B labels, tuples of the form (INSIDF, (roleType>) for labels, and the symbol OUTSIDE for the sole label.
17


Reviews:
[{"review_id": "pnRBxY2lmV", "reviewer": "Reviewer_ephA", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "On novelty:\n\nI think if you asked any CRF practitioner to incorporate non-local hard constraints into a CRF, their first reaction would be to say, “I can hack it into the tag set.” And then they would have to hack the transition and emission feature functions to ignore the new information in the expanded tags to avoid parameter blow-up, and then the transition potential function to enforce the constraint. (I have done this.) They would eventually wind up with a one-off solution that looks very much like what the transformation described here would have handed them. Now the engineer is given another problem: to design a finite-state machine describing the output language, and to make it have as few edges as possible. I would argue that this is a step forward, and a worthwhile ML contribution.\n\nStrengths:\n- This is a useful addition to the CRF toolbox; it is a nice, clean formalism for adding regular language constraints, and by making the connection explicitly to regular languages and NFAs, it opens up the possibility of fruitful cross-pollination with formal language research.\n- The paper is well-written and very easy to follow.\n- The authors get out ahead of the inevitable question of the utility of their work in the face of more general work on learning weights for FSTs. I think Section 4.3 is strong, and gives a good argument why this contribution has value in the face of previous work.\nThe authors took the time to show that the technique helps even in the context of a state-of-the-art model.\n\nWeaknesses:\n- CRF’s quadratic dependence on tag set size, and the mapping from NFA edges to tags means that for many constraint sets, this solution will be infeasible.\n- In general, I found 4.2 on tag-set minimization a little hard to follow. The advice amounts to, “minimize manually, and apply NFA minimization where applicable.” I think an example of an organic application of NFA minimization (plus a citation to the algorithm the authors have in mind!) would go a long way toward improving it.\n- I didn’t find the proofs in Section 5 particularly compelling - they were easy to follow, but they extend almost trivially from definitions. In particular, the impact of training with constraints seems to (1) assume perfect minimization of the training objective and (2) ignore generalization error entirely. However, the synthetic data experiments do a good job compensating for this.\n- The real-world experiment is not particularly convincing - it’s very good that the authors report statistical significance because the deltas in performance look very very small. I also think that it’s good that they attribute much of their strong performance to RoBERTa.\n  - I think it would be informative to include the number constraint failures in the unconstrained model.\n  - It would also be informative to include an unconstrained model that has the same computational concessions as the constrained model (removal of rare labels).\n", "summary_of_the_paper": "This paper describes a transformation to add a hard regular language constraint to the output space of a linear chain CRF. Given a Non-deterministic Finite State Automaton (NFA) describing the CRF’s output space, their method maps the edges in that machine to a new CRF tag set, and wraps the potential function from the original CRF in a function that is aware of the compatibility of adjacent tags based on the edges they represent. They prove some basic properties about this transformation, and discuss its relation to learning weights in arbitrary FSTs. Finally, they provide experiments showing the technique’s application to synthetic data, as well as semantic role labeling, which has natural constraints such as uniqueness of core roles. They are able to show small but significant improvements over both an unconstrained ablation and the state-of-the-art on this dataset.", "summary_of_the_review": "This paper formalizes and systematizes how to incorporate regular language constraints into CRF training and inference. This simplifies the incorporation of constraints, and makes it clear when they will become computationally infeasible. It also provides exciting hooks into formal language theory for future contributions. The experiments are not super-exciting, nor are the proofs, but the framework is a nice addition to CRFs overall.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "p6_UBWIXTon", "reviewer": "Reviewer_qQNs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n1. Consider the problem of external constraints in the CRF model and propose a solution to address the nonlocal dependency issue.\n\n2. Give a detailed mathematical description and proof of the proposed method.\n\nWeakness:\n\n1. The author mentioned that RegCCRF can incorporate their constraints during training, while related models only enforce constraints during decoding, but no matter in theory, I can't see what gains can be brought to the model by using constraints during training (in the current version). Because maximum likelihood estimation is used on the golden data during training, the labels will strictly follow the constraints, the constraints cannot bring any redundant information, so I don't see any advantages for supervised training under general data situations. On the contrary, I think it may be useful for training in unsupervised situations, but it has not been studied.\n\n2. The article claims that constrained training is substantially better than constrained decoding in practice, but unfortunately from the actual results in Table 2, it is obviously not in line with this point. The difference between the two is 0.31. Because the SRL test set is not large, this result is far from significant.\n\n3. For RegCCRF, what about the training efficiency and decoding efficiency, and how does it perform compared to traditional CRF? None of these questions have been answered in this article, so this obviously cannot make RegCCRF a replacement for traditional CRF.\n\n4. The paper mentioned a lot of related work, but no comparisons were made in the experiment, such as Semi-Markov CRF, Skip-chain CRF, and constrained decoding (constrained beam search), which makes the performance of RegCCRF difficult to discuss.\n\n5. Since the added tag-wise CRF can be viewed as a particularly well-behaved special case of FST weight learning for an appropriately chosen transducer architecture and parameterization, a baseline that needs to be compared is to directly use an RNN network to simulate FST, its speed is obviously faster and can be trained.\n\n6. The results reported by the article on the SRL are only an improvement from the baseline, which is not significant compared to the traditional CRF model, and the results have not reached SOTA.\n\n\n=======\nI have read the response and it has addressed parts of my concerns, so I raised my score.\n", "summary_of_the_paper": "This paper claims to propose a generalization version of CRF, regular-constrained CRF (RegCCRF). Compared with traditional CRF, it can not only model local interdependencies but also incorporate non-local constraints for the model. Specifically, by specifying the space of possible output structures as a regular language, assigns zero probability to all label sequences not in language to achieve the goal.\nThe paper spent a lot of space analyzing the difference between the proposed RegCCRF and constrained decoding, Markov relaxations methods, and finite-state transducers, and gave two settings: constrained training and constrained decoding. But as far as the actual implementation is concerned, only the introduction of a new tag-wise CRF, combined with the traditional label-wise CRF, is not much novel. In addition, the experimental part is seriously lacking, and there is no adequate experimental comparison and ablation study of the proposed method.", "summary_of_the_review": "Although the discussion is very interesting, the current version of the experiment did not meet the requirements for publication, and many parts of the method were not properly studied.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jdylFr9eX_", "reviewer": "Reviewer_82Jb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I liked this paper, but it took me a little while to overcome my initial hesitations about why one would want to do this. First, the application to BIO tagging is a good one, and it would help your presentation enormously to mention this application in the introduction. Second, readers may differ depending on their background, but I was initially confused about why one wouldn't want to just use finite transducers. This is explained adequately in Section 4.3, but I feel it is a little late. Perhaps the explanation can be left where it is, but summarized in the introduction.\n\nI think the theorems in Section 5 are pretty intuitive, and if you are need of space, you could relegate the proof of Theorem 1 to an appendix. In Section 6, the experiments are interesting, but couldn't you go further and prove formally that a CRF is incapable of generating these particular string relations?\n\n- I think there is a typo in the statement of Theorem 2; the two sides of the inequality are the same.\n\nThe method improves performance on semantic role labeling, but the improvements due to the proposed method (as opposed to using RoBERTa) are not dramatic. Nevertheless, they produce apparently the new SOTA on this task.\n\n- On page 8, I'd like to see a clearer explanation of how the constraint language is constructed. There are a lot of magic numbers here that would benefit from explanation, and I certainly wouldn't be able to replicate the results from this explanation.\n\nIt had been claimed in Section 4.3 that direct comparison between the proposed method and neural-weighted finite transducers is possible. Maybe you meant direct theoretical comparison, but I definitely would have liked to see an experimental comparison between the two. The advantages claimed in Section 4.3 are legitimate, but I am not sure how much difference they make in practice.\n", "summary_of_the_paper": "This paper describes CRFs that are constrained to generate tag sequences that belong to a given regular language (RegCCRF). This is useful, for example, in BIO tagging where tag sequences must be of the form O*(BI*O*)*. Since CRFs do not have hidden state, the constraint makes them more powerful. On the other hand, the claimed advantage of RegCCRFs over general finite transducers are (1) guarantee that the partition function converges, (2) finding the best path is the same as finding the best string, (3) the loss function is convex.\n", "summary_of_the_review": "I like this paper and just think it needs some improved motivation in the introduction. An experimental comparison against neural-weighted finite transducers would strengthen the paper a lot by justifying the claims in Section 4.3.\n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Z6qXdnCIv3G", "reviewer": "Reviewer_1EHx", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think the paper proposes a clever approach to deal with an interesting problem. The approach and constructions are simple and natural. The results in their few experiments also support the effectiveness of the approach. I was curious to see if they applied their method to a larger problem and if the approaches to optimize the computational costs made a significant difference.  \n\nThey have an interesting discussion on the relationship between their approach and WFSTs. I understand that in contrast to WFSTs, this approach does not suffer from the issue of paths with unbounded lengths. But does it not arise from the need to induce a regular language before applying the approach which itself could be hard in some cases.  \n\nThe paper is very well written and the arguments are very clearly presented. I appreciate the extra effort put in by the authors for the reproducibility and accessibility of their implementation.  \n\nI think authors could have explored more synthetic languages to solidify their claims. The synthetic experiments were on two very simple languages. I think a more systematic exploration even within the hierarchy of regular languages to test the limits of the approach would have been more insightful.  \n\nThe improvement in the SRL task also seems to be incremental and the need to induce regular language for various practical structured prediction tasks could be difficult in certain cases.  ", "summary_of_the_paper": "The paper proposes a modification over linear chain CRF models such that the output space of the model is constrained to be in a regular language. Linear Chain CRFs use Markov assumption where a given output only directly depends on its immediate neighbours which restricts the influence of distant ones. The assumption makes training tractable for the model but restricts its expressive power which could inhibit the performance on longer sequences. Some approaches have been previously proposed to relax the assumption but the authors claim they have certain drawbacks in terms of performance and expressive power. \n \nThe authors propose a new way to relax the Markov assumptions by constraining the output of a CRF to be in a regular language. They describe a simple way to construct such a constrained CRF when given an NFA by setting certain transition and emission probabilities to 0. They then discuss ways to make the algorithm more efficient by making use of equivalences classes and heuristics to minimize NFAs to minimize the size of tag sets. The authors also discuss the relationship between the constrained CRF model and weighted FSTs, and point certain distinctions in favour of the constrained CRF model.  \n\nSome previous constrained variants of CRFs are trained in the same way as standard CRFs, and then the constraints are enforced during decoding by setting certain output probabilities to 0. Unlike those approaches, the proposed approach could be trained and then used in a constrained manner. Training in a constrained fashion will directly minimize the NLL against the data distribution and achieve a better error, given output y \\in regular language L.  \n\nThe authors conduct two synthetic experiments to showcase that their model with constrained training is able to better capture non-local dependencies and data distributions compared to a model with constrained decoding. Additionally, they show slight improvements on a semantic role labeling task compared to baseline CRF models. ", "summary_of_the_review": "In summary, it seems like a good paper, with a simple and clever idea to improve a fundamental model in structured prediction. The arguments are made very clearly while presenting the idea but the paper lacks enough empirical evidence to back up the efficacy of the proposed idea.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper does as it’s title suggests, it introduces an algorithm for constraining a CRF’s output space to correspond to a pre-specified regular language. The authors build upon a wealth of prior work aiming to enable CRFs to capture particular non-local dependencies and output constraints and present a coherent general algorithm to specify such constraints with a regular language. This is a clearly presented and well motivated contribution.

The reviewers predominantly agree that this work is clearly and rigorously presented and that the formalisation of constraints for CRFs through regular languages is a useful contribution for practitioners. One reviewer questioned the utility of constraining the output distribution at training time. In response the authors convincingly argue that unconstrained models will fail to learn the data generating distribution when non-local constraints exist in the data and have included a clear synthetic example of this in the paper.

The most significant weakness identified of this paper is the limited experimentation, consisting of one synthetic experiment and an application to semantic role labelling. The key motivation for formalising constraints on CRFs with regular languages is the argument that this allows model builders to use a familiar formalism across disparate tasks rather than producing bespoke solutions for each. As such it would be informative when assessing the contribution of this work to see a number of practical examples of task output spaces formalised as regular languages such that we can form an intuition for how natural this representation is for more than one task, while also shedding light on the ease, or otherwise, of the crucial processing of minimising the representation to maximise efficiency.

While the application to a broader range of tasks would definitely strengthen this paper, in its current form it provides a useful formalism that will be of interest to those working in structured learning and as such is a contribution worthy of publication.
Decision: Accept (Poster)