A Unified View of Evaluation Metrics for Structured Prediction
Authors: Yunmo Chen
William Gantt
Tongfei Chen
Aaron Steven White
Benjamin Van Durme
Venue: EMNLP 2023 Main (2023)
Keywords: structured prediction
information extraction
evaluation metrics
template extraction
n-ary relation extraction

Abstract: We present a conceptual framework that unifies a variety of evaluation metrics for different structured prediction tasks (e.g. event and relation extraction, syntactic and semantic parsing).  Our framework requires representing the outputs of these tasks as objects of certain data types, and derives metrics through matching of common substructures, possibly followed by normalization. We demonstrate how commonly used metrics for a number of tasks can be succinctly expressed by this framework, and show that new metrics can be naturally derived in a bottom-up way based on an output structure. We release a library that enables this derivation to create new metrics. Finally, we consider how specific characteristics of tasks motivate metric design decisions, and suggest possible modifications to existing metrics in line with those motivations.

A Unified View of Evaluation Metrics for Structured Prediction
Yunmo Chen 1-
William 2antt Tongfei Chen
Aaron Steven 2hite
Benjamin Van Durme'
Johns Hopkins University Universitty of Rochester Microsoft
(yunmo vandurme e jhu.edu, (wganttéur. aaren. whitel rochester.edi. tongfei@pm.me
Abstract
Matching similartty for sets
Set
['[ox]
We present a conceptual framework that uni- fies a variety evaluation metrics for different structured prediction tasks (e.g. event and rela- tion extraction, syntactic and semantic parsing). Our framework requires representing the out- puts of these tasks as objects of certain data types, and derives metries through matching of common substructures, possibly followed by normalization. We demonstrate how com- monly used metries for a number of tasks can be succinctly expressed by this framework, and show that new metrics can be naturally derived a bottom-up way based on an output struc- ture. We release library that enables this derivation to create new metrics.' Finally, we consider how specific characteristics of tasks motivate metric design decisions, and suggest possible modifications to existing metrics in line with those motivations.
Element
Binilariy melched per 0y(X,))
Matching
UG
The United States
Zelensky
Ukrainian military
Joseph R. Biden, Jr.
United States
Volodymyr Zelemsky
Joseph R. Bidden,
Zelensky
Biden
Our generic framework, with the CEAF de metric (Luo, 2005) as for coreference resolution as an example. Here the task output a set entities, where each entity is of coreferent mentions identfied in the document. Computing CEAF thus amounts to cal- culating the matching similarity between the predicted (P) and reference (R) sets of entities.
Figure 1:
1 Introduction
A wide range of tasks in NLP be considered forms of structured prediction. Syntactic and semantic parsing produces tree or graph? based on text. Information extraction (IE) aims to produce structured representations data extracted from unstructured sources, often in the form of relations that may be used to populate database (Grishman, 2019). Such relations may be typed untyped, may have different numbers of arguments, and may relate objects of different kinds (e.g. mentions, entities, events, or even images).
tasks like template extraction, which requires pop- ulating various types of slots with sets mentions, categorical values, or even whole event structures, and AMR parsing (Langkilde and Knight, 1998; Banarescu et al., 2013), which requires generat- ing DAG of entities and values representing their semantic relations.
A wide array of evaluation metrics have been proposed across this spectrum of tasks. For simpler ones, researchers have generally converged to standardized of metrics (e.g. trigger and argu- ment F, for event extraction). However, for more complex tasks like template extraction, researchers have often proposed bespoke metrics tailored to the problem at hand, complicating comparison with prior work on similar problems (Chinchor, 1991, 1992; Du et al., 202 lb; Chen et al., 2023).
The structural complexity of these representa- tions varies considerably between tasks. On the simpler end, problems like binary relation extrac- tion require identifying relationships between pairs of entity mentions. On the more complex end are
Equal contribution.
tttps://gittee wewtttuu.cc.. htt.uu..oo/wwaman com//aanoo//etaneeri...
Often in the form of a directed acyolic graph (DAG), as
in the task of AMR parsing.
Given the common goal predicting structured

---

2.1 Relation Extraction
3.2 Coroference Resolution
subja
Cansion
mentions:
type: attack
rel:
Li Le-tarali Louf
(Aary Cietmo (ivelaany
fillers:
obj:
secetry of state
parp-0rr
4ds Carle
multiple
Vas
associate roles with entitles y
Naath Lopae
type:
acthod task -etrect-nttrii
viette
trig: { [afe-ase (Wed >,
args:
entity as argument
args:
methud
(Atveisa retwod: IPFN
type filler
perp-1ne
spent
monen peospee
VEctim
dntaset
MosuY
veagon
3.1 Event Extraction
3.3 M-ary Relation Extraction
344 Template Extraction
Figure 2: Output structure of common IE tasks discussed in this paper, with examples of their outputs.
objects, our aim is to present a similarly unified, high-level picture of evaluation. We observe that a variety of metries can be viewed as computing scores over a matching between substructures of predicted and reference objects, where this score decomposes as normalized sum over matched pairs. The process of computing metrics can thus be abstracted to framework shown in Figure 1.
plex ones, interleaving with examples throughout our exposition.
Records and Sets
We begin by focusing on records² with non-nested, fixed-named fields or slots. Specifically, for P, R e X of Predicted and Reference objects of record type X, we induce similarity function over X. Definition
On the one hand, this observation drives con- tribution to structured prediction theory, clarify- ing the relationships among numerous metrics pro- posed over the years by identifying their core com- ponents. On the other, it drives contribution to NLP practice, offering bottom-up process for de- output structure.
similarity over X a function Φ: X x X - [0, 1] such that Vx,y E X, 6(x,y) s 6(x,x) = 1, i.e. an object is at least as similar to itself as to any other. A relaxed version is an unnor- malized similarity, where Φ: X X +oo+
signing new metries based Our contributions can be summarized as follows:
Discrete Similarity* Equality is trivial but im- portant notion of similarity, which can be expressed by the Kronecker delta or the Iverson bracket as
We present a unified framework for expressing structured prediction metries;
xf if $
We demonstrate how to derive various classic metrics using this framework, given a specifica- tion of a task's output structure;
5x(x,y) = yI
(1)
Product Similarity for Records Given two sim- ilarities and & over sets X and Y, can define product similarity & for tuples of X x Y:
We consider how different problem features may recommend particular design decisions within the framework - often different decisions from those realized by existing metrics;
(ò x v) ((x, y). (x', (x',y)) 6(x,x) (y: (2)
We release a library that enables bottom-up ere- ation of new metrics based on predefined output data structure of a given task.
Clearly, the product similarity of two similarities is also a similarity. This generalizes to n-tuples,
the context relational databases, a record is row (also named tuple) describing structured data a table. Akin to discrete metric and discrete topology. Through- out this work use the word metric it's commonly used in NLP literature: score for evaluation purposes. rather than the formal mathematical notion that generalizes distances. The Iverson bracket [p] is p is true: otherwise 6 If at least one similarity in the product is unnormalized, the result is also unnormalized.
Throughout, we emphasize both how evaluation of substructures (e.g. mentions) composes in the evaluation of superstructures (e.g. relations, tem- plates), as well the different notions of similarity employed for different structures. Our discussion starts with simpler tasks and proceeds to more com-

---

record/class types? if similarity function is defined for each field in the record.
class Mention:
left: int left span offset (inclusive)
right: int
right span offset (inclusive)
Set Intersection and Normalization Sets are commonly compared with Jaccard similarity, or Fi score. Note that the core of such comparison is the overlap between two sets P. R S X, namely
Relation:
type: RelationType
# ss-capitat-of
subj: Mention
# London
obj: Mention
# United Kingdon
class RelationSet: # task output
Es R) P R|
relations: [Relation)
if we consider the elements of as discrete (using ox as their similarity). This overlap score N. is an unnormalized similarity under our definition.
We will now derive metric bottom-up. A stan- dard similarity for mentions is exact offset match where two mentions are considered the same and only if both the left and right boundaries match. This is an instance of product similarity:"
There are multiple ways to normalize this Σ
score so that the result is (proper) similarity. We consider few common choices: precision (Liq. 4),
oventio = ōteft X rright
(8)
recall (Eq. 5), and F1 (or Dice score; Eq. 6):
On the outer level, relation instances are considered correct only when all of its components correct:
JP IP|
R
Σ(P, R)
= P(P,R)
(4)
P)
IP RI
2(P.R)
Oeetttion Stpe X òsubj X óabs
r R(P.R)
(5)
|R|
I(R, R)
Finally, precision, recall, and Fi score are the most common metrics to evaluate predicted relations. Practically, this requires finding the intersection between predicted and reference relations:"
2pr
R)P,R)
(6)
p+r
And the Jaccard similarity:
JPn R [PUR] R
RelFi PRelationSet Frelations [oettation] (10)
J(P, R)
2.2
Dependency Parsing
R(P,R)
(7)
Our next example is dependency parsing, where dependencies are relations between a governor and its dependent. The output structure is as follows:
E(R
Note that all these normalizers can be expressed solely with the overlap scoring function Σ. Let N E (P, J} be normalizer over objects of type X. Hence we arrive at normalized similarity over sets of X: [[ R) (PE,(P, R)).
class Dependency:
gov:
dep: int # index of the word
rel: DependencyType nsubj, advmod,
We have created the basic tools needed derive metrics for many simple tasks. Next, we illustrate how to do so for two common NLP tasks.
class DependencyParse: task output
edges: Set (Dependency)
Dependency parsing is evaluated using unlabeled (UAS) and labeled (LAS) attachment scores (Buch-
2.1 Binary Relation Extraction
holz and Marsi, 2006), which are simply F1 scores over dependency edges:
Binary relation extraction (RE) focuses on typed re- lations (e.g. IS-CAPITAL-OF) with two arguments, a subject and an object. Traditionally, both the sub- ject and the object are text spans (i.e. mentions). Given a text passage, the objective is to output set of binary relations.
UAS Fedges [dgov X ddep]
(11)
LAS Fedges [ōgov X Ödep 6reil
(12)
8 For consistent presentation, we define deventionn in terms of offscts, but other string similarities could be substituted w.l.o.g.. e.g. based on string value of the tokens (e.g. bag-of- tokens Fj employed in MRC/QA (Rajpurkar et al., 2016)). field, write
To ground our discussion of concrete structured prediction tasks, we specify relevant output data structure(s) in Python dataclass-like syntax. For binary RE, these are as follows:
Given class Cls with fld ambiguous) where x, (x..lld f.d)
(cts. y) Φeld it mean rtax.,)
10 For concision, we present only F in our metric definitions. hut precision and recall are defined analogously, substituting or R for F as appropriate.
7 Product types in programming languages literature.

---

3 Matching of Sets
Thus we arrived generalization of our origi- nal overlap score. We denote the N-normalized (N E (P, R, F. matching score > [ex] simply as [Øx]- Such (normalized) matching scores are sometimes kernels, which have additional nice properties, For discussion, see Appendix B.
In the previous section, we derived Σs, a similar- ity for sets whose elements are discrete. However, elements of sets can be equipped with their own similarity. For example, in coreference resolution, the output of a system is a set of entities, where each entity is in turn a sel of mentions that may par- tially overlap. We develop the idea of a matching of sets to express these cases.
With the notion of matching of sets, we next consider metrics for several more complex tasks.
3.1 Event Extraction
We derive similarity ΦP(X) over sets of ele- ments of X (i.e. elements of the power set P(X)) using bipartite graphs. Assuming that elements in X are compared with a custom similarity Øx. given two sets P. R S X, we can construct a bipartite similarity graph G = (P, R, E) between P and R. where F C x R is the set of edges, and the weight each edge & 44 v) corresponds to the value of the similarity (Øx) between nodes and
Our first such task is event extraction." 11 We imag- ine that events and arguments represented using the following data structures:
class Trigger:
mention: Mention defined in $2.1
type: EventType
class Argument: mention: Mention
role: RoleType
We then determine a matching M S E on this bipartite graph G. An unnormalized matching score between P and R is defined to be the max- imum sum of weights of all edges in matching, subject to some constraint:
class Event:
trig: Trigger
args: Set [Argument]
class EventSet: task output
events: Set[Event]
[xxxx = max Σ vx(u,v), (13) (u.
The canonical metrics for event extraction are la- beled precision, recall, and F2 score for both event triggers and arguments (Li et al., 2013, i.a.). An event trigger is considered correct iff both the event type and the trigger mention offsets exactly match those of the reference (i.e. ÖTrigger Ömention X Stype). An event argument considered correct iff the argument mention offsets and role exactly match the reference (i.c. ōArgunent ôenttion rote) and the associated trigger is correct." 12 Given these, we can express trigger and argument F1 scores as
where o E [,,-,,~~} is the matching con- straint. Specifically we have the following:
1:1 (+)): Each element of P can be matched to at most one element of R, and vice versa. This is corresponds to the unbalanced assignment prob- lem, and can be solved efficiently with the Hun- garian algorithm (Kuhn, 1955; Munkres, 1957). We denote this M since the matching is a (par- tial) bijection between P and R.
TrigF; F Févents [derig] ArgF; Févents
(15)
N:1 (-) / 1:N (-): Each clement of P can be matched each element of R can be matched to multiple elements of P. We denote this M since the matching is a (partial) function from to R. A flipped version M obviously follows.
|ōeiig Eargs [0Argunnt]]] (16)
most one element of R. but
Note that the definition of ArgFi suggests that the metric can be viewed as a nested matching, which we first compute an unnormalized optimal argument matching score (Zargs i.e., raw count of matched arguments) based only on role type and ar- gument boundaries, and then use this score to iden- tiyy the optimal matching and score conditioned on
N:N (~): Every element of P may be matched with multiple elements of R, and vice versa, with- out constraints. We denote this M E, as the matching may be any relation between P and R.
This also covers semantic role labeling (SRL). which evaluated the same way, and event argument extraction (EAE), which differs only in considering arguments occurring outside the sentence containing the trigger.
Note that the overlap score developed $2 is a special case of the 1:1 matching score here, since
12 Unlaheled scores, in which event type and argument role are ignored, are also commonly reported.
Es R) Pn PORI= E
(14)

---

relations in $2.1, òtrig ren- ders F events trivial to compute, as an aligned event pair receives no credit if the triggers not match. However, this nested matching view articulates a key aspect of our framework, evidenced by other metrics discussed in this section - namely, that evaluation of complex structures depends on optimal matching of their substructures.
the trigger. As with Fre
CEAF offers nice illustration of the expres- siveness of our framework, computing a matching score between sets (of entities), where the internal metric over elements (entities) also a matching score over sets (of mentions).
MUC The main step of MUC scoring is to create (separate) partitions of the predicted and reference entities (Pradhan et al., 2014). Assume that the predicted and reference entity sets are P and R, and the partition of each reference entity R E created by intersecting with predicted entities P is Partp (R): i.e. UrePartp = R. MUC recall is computed as
3.2 Coreference Resolution
Event extraction deals only with trigger and argu- ment mentions, but IE also deals with coreference resolution, where systems predict set of entities, which in turn are sets of coreferent mentions:
RMUC ERER (IR) - (Prrtp(R))
class Entity:
(20)
nentions: Set [Mention]
ERER -1R1-1) 1)
class EntitySet: task output entities: (entiiy)yy)
Note that |R| - (PI-t(arty>())) ElePart (17) I):
We can define an unnormalized similarity (num- ber of shared links that link mentions to form a coreference chain) between entities:
A variety of metrics have been proposed for coref- erence resolution. Commonly used are CEAF (Luo, 2005), MUC (Vilain et al., 1995) and B² (Bagga and Baldwin, 1998).
Dlink Y) max (0, X n -
(21)
Using this, we see that |R| - |Partp =
CEAF We start with CEAF since it explicitly evaluates coreferences as sets of mentions. CEAF computes entity precision, recall, and F1 by find- ing a partial bijection between predicted and ref- erence entities that maximizes an entity similarity. Luo (2005) considers several functions denoted ① (1.2.33)4 ultimately preferring d3 and dæ:
Tentities (P, R) with the N:N (~) matching
constraint, and [Partæ [R] 1. Thus we have
RMUC = Re (oink).
(22)
Precision can be defined similarly.
B Different from MUC and CEAF, B assigns score each mention instead of each entity, Here, we need slightly different data structure, where we pair each mention with the entity it belongs to:
x = X
mentions [nmention]:
(17)
h4 = F [Ómention]:
(18)
Both correspond to intuitive notions of entity simi- larity, with d3 simply counting the number of men- tions a pair of entities have in common, while &4 F-normalizes this value." 14 In contrast to the iden- tity similarities (Ō's) typically used for mentions, the similarity used in coreference resolution is gra- dient: entities can be more or less correct based their constituent mentions. Coreference reso- lution researchers have often used Φ (Moosavi and Strube, 2016; Joshi et al., 2020, i.a.), where CEAF o4 just the F-normalized total score under a 04-tmtimal entity matching:
class Membership: # An instance of relation mention: Mention
entity: Entity
class CorefOutputfor83: rels: Set [Meebershhpp]
# membership relations
The recall of 3 assigns to each reference mention score equal the ratio of the number of cor- rect mentions in the predicted entity containing the reference mention the size of the reference en- tity to which that mention belongs (Pradhan et al., 2014). Under our new data structure this ratio is just Rentity Precision is computed similarly by switching the role of predicted and reference entities. Thus, B² can be succinctly expressed
CEAF 6,
F entities [d4]
(19)
F entities [Fre Fmettonns [owention]]
focus on entity coreference here, though the same metries can used for event coreference.
R3 Reets (Smontion Rentity [mention]] (23)
14 Note that de is an unnormalized similarity function.
P dB Pr [Snention p
P [Senntio]]] (24)

---

Our framework thus captures all three of the standard coreference resolution metrics.
two-sided matching constraints to one-sided:
CEAF-RME& = Frgg [ôrot x Φ=1
(27)
3.3
Role-Filler Entity Extraction & N-ary Relation Extraction
CEAF-RMEØ; = Fargs [rote x 6sl
(28)
Relation and event extraction generally take men- tions as arguments, but some tasks take entities as arguments (fillers) of roles (slots) in some relation:
N-ary Relation Extraction N-ary RE general- izes binary RE to relations among N entity or men- tion arguments. Here, we will assume we are deal- ing with entities; the case mention arguments is comparatively straightforward.
class RoleFillerEntity:
role: RoleType
Often, work on N-ary RE assumes gold entities are given to the model as input, along with set of candidate relations, and results are reported relation type classification accuracy Fj. This is true of much work on a number of recent, popular N-ary RE benchmarks, including SCIERC (Luan et al., 2018), DOCRED (Yao et al., 2019), and the dataset released by Peng et al. (2017).
entity: Entity
class NAryRelation:
type: RelationType
args: Se((RoleFillerEnnitty
class NAryRelationSet:
relations: Set [Nryyyeeeltii
Tasks of this form have been instantiated in various ways in prior work, which we discuss below.
In a more comprehensive task setting, entities or mentions must also be predicted, along with the relations. We highlight the SCIREX bench- mark (Jain et al., 2020), an extension of SCI- ERC, an example of evaluation in this set- ting. SCIREX requires extraction of quaternary (dataset, method, task, metric) relations over en- tities extracted from ML papers. We formulate the SCIREX metric in our framework below. For this task, mentions are represented as index ranges:
Role-filler Entity Extraction One such instance is role-filler entity extraction (REE), a subtask of template extraction in which one must populate the subset of slots (roles) of single identified template that takes entities as fillers (Du al., 2021a; Huang et al., 2021, i.a.). Since the task deals with a single template, the output is a single NAryRelation." 15 Du et al. (2021a) introduced the CEAF-REE metric for REE which differs from CEAF only in requiring matching entities to share role type and in using different & for entities:
class Mention: # alternative to definition in $2.1 indices: range # set of token indices
A predicted mention is considered to match a ref- erence mention iff their Jaccard similarity (consid- ered bag-of-integge offsets) exceeds 0.5:
Φ [P [
=
(25)
where P and R predicted and reference entities (sets of mentions). CEAF-REE is then defined as:
Ovention = I
[ntt] 0.5]]
(29)
CEAF-REF- = args [drote x Φc]
(26)
Jain et al. propose computing role-filling entity matching based mention and role matching:
Whereas Φ3 and 64 award partial credit to predicted entities that contain at least one correct mention, &c is much stricter, awarding no credit in cases where even one mention is incorrect, while simulta- neously awarding full credit to any non-empty sub- set of the reference entity. This may make sense in some settings, but in most, it is unduly harsh (sce $6). Responding to this observation, Chen al. (2023) suggest pair of alternatives CEAF-REE, CEAF-RME, and CEAF-RME, that treat pre- dicted mentions as singleton entities and relax the
ØRFE =
rate X @Hention] > 0.5 (30)
In other words, pair of entities Ep and ER will be matched iff more than half of Ep mentions appear in ER, and their role matches. Given this matching, predicted 4-ary relations are then evaluated against reference ones using F [dwAryRelation] where
OuAryRelation [ I
[dRFE] = I]. (31)
Fe [ [ΦRFE] = means that all four role-filler entities must match under dAFE to receive credit. F relations [dnAryRatation] further illustrates how
15 Some work has evaluated at the mention level (Patward- han and Riloff, 2009; Huang and Riloff, 2011; Du and Cardie, 2020), essentially doing namod entity recognition (NER).

---

matching superstructures depends on matching sub- structures, with optimal matching of relations de- pending on optimal matching of entities, which in turn depends on optimal matching of mentions.
P.R V. MUC-4 defines @set as:
1 P Set (P.R): ==
i: 0 otherwise
(33)
3.4 Template Extraction
This choice of set is notable for suggesting a means of handling hierarchical sub-ontologies the template ontology itself; such ontologies have seen considerable interest in many recent IE bench- marks, including RAMS (Ebner et al., 2020), WikiEvents (Li et al., 2021), and BETTER (Mckin- non and Rubino, 2022). We return to this in $6. String-fill slots
We now turn to template extraction, which arguably features the most complex outputs of any IE task. It generalizes N-ary RE by allowing roles in the relation be filled by any number of arguments N 2 0, which may be of any type
class SlotFiller(T):
evaluated based maxi- mum lexical overlap between a predicted mention and all mentions in reference entiry. We provide more detailed discussion Appendix C.
slot: SlotType
value: Mention, Entity, Event, boot, etc.
class Template:
type: TemplateType
fillers: Set[SlotFiller(Any)]
Sets with Latent Variables
TemplateSet: & output
templates: Set [Template]
Next, consider Abstract Meaning Representa- tion (AMR) parsing (Langkilde and Knight, 1998; Banarescu et al., 2013), which involves outputs with latent variables. AMR describes the seman- tics of a sentence as a rooted, directed graph rep- resented by set of neo-Davidsonian triples, each with a subject, an object, and relation. Subjects are variables and objects can be variables or con- cepts (e.g. from PropBank (Palmer et al., 2005)):
where distinct similarity function Φr may be needed for each T. Constraints on template match- ings are traditionally two-sided. Below, we con- sider the metrics employed for the classic MUC-4 task. In Appendix D, we also consider the more recent BETTER Granular benchmark.
The MUC-4 dataset (MUC, 1992: Sundheim, 1992) features 6 template types, which concern varieties of terrorist act (e.g. bombing, kidnapping) and which all contain the same slots. Some are "string-fill" slots, which take entity mentions as fillers, and others are "set-fill" slots, which take categorical value. Although the official MUC-4 evaluation reported several metrics," the overall score was F1 over slot fillers:
class Prop: logical propositions
rel: Relation instance, ARGO, ARG1,
subj: Var #
obj: Var Concept # want-01, boy,
class AMR:
props: Set[Prop]
Following the metrics for relation extraction, a prima facie appealing metric for AMR graphs would be just like Eq. 10 for binary RE:
F Ftemolates 1otye X Efitters [6 Φr]
(32)
F props [ōret x subb x dabj]
where &f (#set. (str) is the type-appropriate filler similarity function. Both Øset and &str are somewhat complex and, similar to da and d4, allow for partial credit. For some of the set-fill slots, the possible values are hierarchical; i.e., some values more specific, and thus considered more ac- curate, than others. Suppose set-fill slot takes values from a set V, and we write P <: R de- note P is a subtype of R. Then P iff P is a descendant R according to some hierarchy for
However, this poses a problem, as we cannot know whether two variables x and refer to the same ob- ject: instance boy) and ins instance boy) could match if there is no constraint enforcing that # y. Thus, it is not immediately clear what the similarity function for variables (Φvar) should be.
The commonly used SMATCH metric solves this problem. SMATCH is defined be the maximum F- score obtainable via one-to-one matching of vari- ables between two AMRs (Cai and Knight, 2013). That is, looks for an optimal partial bijection
16 See Chinchor (1992) for details.

---

M7 S Vpx x VR between the variables of the pre- dicted and reference AMRs (Vp and VR. respec- tively). Given My, we can define
problem given by Lqq. (37) is a weighted longest common subsequence (LCS) problem, and thus can be solved with dynamic programming.
We can further generalize this matching score to DAGs and graphs by noting that the total order 3 of sequence elements is relaxed partial order in DAGs and a preorder arbitrary directed graphs. The constrained optimization problem in Eq. 37 can solved via ILP, see Appendix A.
Svar (x. y) = (x. E Iy
(34)
where & denotes similarity conditioned the variables in its arguments being matched. Hence SMATCH is given by
SMATCH = max F props My
Props rorl x subs x 60o]]- (oos)-(33) (35)
Discussion
We generalize the spirit of SMATCH to any set of X with latent variables yet to be matched. The matching score of P, R with latent variables Vp. VR is defined to be
We have seen that diverse of structured predic- tion metrics can be framed computing normal- ized total matching score for an optimal matching, given some similarity, which may itself reflect a score over an optimal matching of the relevant sub- structures. We now consider how different problem settings may motivate particular design decisions within this framework. We also highlight couple of cases in which the actual metrics used for task might be modified to better fit the problem setting.
E (P,
max
Σ (x( (u,Y)EM
(36)
M. M
where M is an one-to-one matching between the variable set Vp and VR; and M is an matching between objects in P and R under constraint o. Computing this constrained optimization prob- lem requires solving Mÿ, which can be done via an integer linear programming (ILP) solver (Cai and Knight, 2013). See Appendix A for more details.
Partial Credit For many tasks, we want to award some credit for partially correct responses. In ap- plications where precision is paramount, it may be appropriate to insist exact matches, but less so when some modest tradeoff with recall is de- sired. Moreover, many IE objects intuitively admit gradient notions of correctness.
5 Matching of Other Structures
In the past few sections we developed tools to ob- tain matching of sets. We extend this to match more complex structures such sequences, DAGs, and arbitrary directed graphs
Perhaps the most obvious example of this is men- tions. Exact match mentions, whether string- or sefssetbassed remains surprisingly common de- spite the possibility for variation in how they are annotated (e.g. disagreements about the extent of NPs). More relaxed mention similarities - such as head word matching or Jaccard score - are typ- ically more appropriate. Recently, there has also been greater interest in the informativity of entity mentions (Li et al., 2021; Chen et al., 2023), where, e.g., names > nominal expressions > pronouns, and where scores may need to vary according men- tion's informativity. All of these can be captured by different choices of Φwention-
Recall the matching score in Eq. 13: we com- puted a sum of similaritics based on matched pairs. In the matching of structures, the matching should preserve the structure of the object being matched, Elements of sequence form total order where carlier elements precede later elements. Given two sequences P, R whose elements are of type X, each is equipped with a total order: sp), (R, 3R). To compute the matching score of two sequences, we define
(P. = max
Σ
vx(u,v)
(37)
(u.V)EM
REE offers another example. Earlier ($3.3), we saw that CEAF-REE uses the & entity similarity, which awards no credit at all to entities containing even one incorrect mention, but full credit to enti- ties containing just one correct mention. A more natural extension of the CEAF metric to the REE setting, and one that permits partial credit, would be to replace & with Φy or d4-
s.t. V(u, v), (n', M Sp SR v'.
That is, we seek maximum monotonic match- ing between P and that preserves the total or- der. For example, the matching score between (1,2,3,4,5) and 51,3,5, 9) is since 1, are monotonically matched. The sequence matching

---

Hierarchical Ontologies Type hierarchies are an- other common feature of IE problems: both events and entities may have types, subtypes, and even sub-subtypes. This is true of the event ontologies for FrameNet (Baker et al., 1998), RAMS (Ebner et al., 2020), WikiEvents (Li et al., 2021), and even MUC-4.17 Yet, the standard evaluation metrics for these datasets do not take the hierarchy into account, instead treating the ontology as flat.
7 Conclusion
We have presented a framework that unifies vari- ety of structured prediction metrics normalized scores over (possibly hierarchical) constrained op- timal matchings of structured objects. On the side of theory, our framework elucidates the relation- ships among tasks by defining the core components of their metrics. On the side of practice, it of- fers compositional toolkit for the design of new metrics (aided by our library) and for critically evaluating existing ones, showing where they may inadequately capture important task features ($6). We intend this work to help the NLP community converge both on a common language for metric design and on more standardized metric implemen- tations.
Following the discussion above, it may thus of- ten be appropriate to replace exact type matches (otype) with similarities that award partial credit for correct ancestor type prediction. One possibility is a level-based partial scoring: Given a D-level type ontology with types specified as a D-tuple P (PI. PD). we could, for instance, award credit based on the depth d E (O.....)) D} of the most specific correctly predicted type, e.g.:
Ethics Statement
22DD 0
if > 0: (38)
(eype(
As this work principally describes a conceptual framework and presents a survey of evaluation met- rics, we do not believe it raises ethical concerns.
otherwise,
where d 0 iff even the most general type is incor- rectly predicted. Or, one could adopt practices from related work in fine-gran fine-grained entity typing (Ling and Weld, 2012; Chen et al., 2020, i.a.). which use the Fi score of the set of all possible supertypes of pre- dicted/ reference types S(P) {rlp <: 1, P}:
Limitations
While this work aims to give a unified treatment of a variety of different metrics, our coverage of exist- ing metrics is not exhaustive, and is intended rather to convey the expressiveness of the framework.
Ptypo PP R) ((CP)
(39)
Our framework for evaluation is based on match- ing of substructures thus metrics based on struc- ture editing (e.g. string or tree edit distances; word error rate (WER) in speech recognition) cannot be expressed naturally in our formulation. One can of course define a & based on edit distances over se- quences, but that has to be an atomic definition and cannot be derived naturally under our bottom-up approach.
There is some precedent for schemes like this, but proper analysis of performance on tasks with hier- archical ontologies requires metrics that account for that hierarchy, and the field of IE as whole would benefit from adopting them more widely.
One-Sided vs. Two-Sided Constraints In gen- eral, metrics impose constraints on the matching between the predictions and the reference. Over- whelmingly, these tend to be two-sided (bijective) constraints, as systems usually try to generate just one predicted object for each one in the reference. But this is not always the case. The CEAF-RME metrics (Eqs. 27 and 28) proposed by Chen et al. (2023), which use one-sided constraints, are moti- vated in part by need evaluate model that pre- dicts mention fillers against references that contain entity fillers. This suggests a more general motiva- tion for one-sided constraints - namely, for cases where the reference outputs are sets, but where pre- dictions take the form of members of those sets.
References
Amit Bagga and Breck Baldwin. 1998. Algorithms for scoring coreference chains. In The first international conference on language resources and evaluation workshop on linguistics coreference, volume 1, pages 563-566. Citeseer.
Collin F. Baker, Charles J. Fillmore, and John B. Lowe. 1998. The Berkeley FrameNet project. In 36th An- nual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Volume I, pages 86-90, Montreal, Quebee, Canada, Association for Compu- tational Linguistics.
17 The attack template type is considered the parent type of all other template types in MUC-4.

---

Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013, Abstract Meaning Representation for sembanking. In Proceedings of the 7th Linguistic Annolation Workshop and Interoperubility with Dis- course, pages 178-186, Sofia, Bulgaria. Association for Computational Linguistics.
Xinya Du and Claire Cardie. 2020. Document-lever event role filler extraction using multi- coantiiganlrrttyy contextualized encoding. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 8010-8020, Online. Association for Computational Linguistics.
Xinya Du, Alexander Rush, and Claire Cardie. 2021a. GRIT: Generative role-filler transformers for document- event entity extraction. In Proceed- ings of the 16th Conference of the European Chap- ter of the Association for Computational Linguistics: Main Volume, pages 634-644, Online, Association for Computational Linguistics.
Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task multilingual dependency parsing. In Proceedings of the Tenth Conference on Computa- tional Natural Language Learning ( (CoNLL-X), pages 149-164, New York City. Association for Computa- tional Linguisties.
Xinya Du, Alexander Rush, and Claire Cardie. 2021b. Template filling with generative transformers. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computa- rional Linguistics: Human Language Technologies, pages 909-914, Online. Association for Computa- tional Linguisties.
Shu Cai and Kevin Knight. 2013. Smatch: an evaluation metric for semantic feature structures. In Proceed- ings of the St Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Pa- pers), pages -48-752. Sofia, Bulgaria. Association for Computational I Linguistics.
Seth Ebner, Patrick Xia, Ryan Culkin, Kyle Rawlins, and Benjamin Van Durme. 2020. Multi-sentence ar- gument linking. In Proceedings of the 58th Annual Meeting of the Association for Computational Lin- guistics, pages 8057-8077 Online. Association for Computational Linguistics.
Nathanael Chambers and Dan Jurafsky. 201 Template- based information extraction without the templates. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 976-986 Portland, Oregon, USA. Association for Computational Lin- guistics.
Ralph Grishman. 2019.
Twenty-five years of infor- mation extraction. Natural Language Engineering, 2566):677-692.
Tongfei Chen, Yunmo Chen, and Benjamin Van Durme. 2020. Hicrarchical entity typing via multi-level learn- ing to rank. In Proceedings of the 58th Annual Meet- ing of the Association for Computational Linguistics, pages 8465 8475, Online, Association for Computa- tional Linguistics.
David Haussler. 1999. Convolution kernels on discrete structures. Technical report, Department of Com- puter Science, University of California at Santa Cruz.
Huing- Huang, Sam Tang, and Nanyun Peng- 2021. Document-level entity-based extraction as tem- plate generation. In Proceedings of the 2021 Confer- ence on Empirical Methods in Natural Language Pro- cessing, pages 5257-5269, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
Yunmo Chen, William Gantt, Weiwei Gu, Tongfei Chen, Aaron White, and Benjamin Van Durme. 2023, Itera- tive document-level information extraction via imita- tion learning. In Proceedings of the 17th Conference of the European Chapter of the Association for Com- putational Linguistics, pages 1850- 1866, Dubrovnik, Croatia. Association for Computational Linguistics.
Ruihong Huang and Ellen Riloff. 2011. Peeling back the layers: Detecting event role fillers in secondary contexts. In Proceedings of the 49th Annual Meet- ing of the Association for Computational Linguistics: Human Language Technologies, pages 1137-1144 1477, Portland, Oregon, USA. Association for Computa- tional Linguistics.
Nancy Chinchor. 1991. MUC-3 evaluation metrics. In Third Message Uunderstanding Conference (MUC- 3): Proceedings of Conference Held in San Diego, California, May 21-23, 1991.
Nancy Chinchor. 1992. MUC-4 evaluation metrics. In Fourth Message Uunderstanding Conference (MUC- 4): Proceedings of a Conference Held in McLean, Virginia, June 16-18, 1992.
Qi Huangfu and J. A. J. Hall. 2018 Parallelizing the dual revised simplex method. Math. Program. Com- put., 10(1): 142.
Aliva Das, Xinya Du Barry Wang, Kejian Shi, Jiayuan Gu, Thomas Porter, and Claire Cardie. 2022. Auto- matic error analysis for document-leved information extraction. In Proceedings of the 60th Anmual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pages 3960-3975, Dublin, Ireland. Association for Computational Linguistics.
Sarthak Jain, Madeleine van Zuylen, Hannanch Ha- jishirzi, and Iz Beltagy. 2020. SciREX: A challenge dataset for document-level information extraction. In Proceedings of the 58th Annual Meeting of the Asso- ciation for Computational Linguistics, pages 7506- 7516. Online. Association for Computational Lin- guistics.

---

Mandar Joshi, Danqi Chen, Yinhan Liu, Daniel S. Weld, Luke Zettlemoyer, and Omer Levy. 2020. Span-
Resources and Evaluation Conference, pages 3595- 3600, Marseille, France. European Language Re- sources Association.
BERT: Improving pre-training by representing and predicting spans. Transactions of the Association for Computational Linguistics, 8:64-77.
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Tal- walkar. 2012. Foundations of Machine Learning. Adaptive computation and machine learning. MIT Press.
Nils M. Kriege, Poerre-Louis Giscard, and Richard C. Wilson. 2016. On valid optimal assignment ker- nels and applications to graph classification. In Ad- vances in Neural Information Processing Systems 29: Annual Conference on Neural Information Process- ing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 1615-1623.
Nafise Sadat Moosavi and Michael Strube. 2016. Which coreference evaluation metric do you trust? pro- posal for link-based entity aware metric. In Pro- ceedings of the 54th Annual Meeting of the Associa- tion for Computational Linguistics (Volume I: Long Papers), pages 632-642, Berlin, Germany, Associa- tion for Computational Linguistics.
Harold W Kuhn. 1955. The hungarian method for the assignment problem. Naval research logistics quar- terly, 2(1-2):83-97.
MUC. 1992. Fourth Message Uunderstanding Confer- ence (MUC-4); Proceedings of a conference held in McLean, Virginia, June 16-18, 1992.
Trene Langkilde and Kevin Knight. 1998. Generation that exploits corpus- corpus-based statistical knowledge. In 36th Annual Meeting of the Association for Compu- tational Linguistics and 17th International Confer- ence on Computational Linguistics, Volume 1. pages 704-710, Montreal, Quebec, Canada. Association for Computational Linguistics.
James Munkres. 1957. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32-38.
Martha Palmer, Daniel Gildea, and Paul Kingsbury. 2005. The Proposition Bank: An annotated corpus of semantic roles. Computational Linguisticx, 31(1):71- 106.
Qi Li, Heng Ji, and Liang Huang. 2013. Joint event extraction via structured prediction with global fea- tures. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Vol- ume I: Long Papers), pages 73-82, Sofi., Bulgaria. Association for Computational Linguistics.
Siddharth Patwardhan and Ellen Riloff. 2009. A unified model of phrasal and sentential evidence for infor- mation extraction. In Proceedings of the 2009 Con- ference on Empirical Methods in Natural Language Processing, pages 151-160, Singapore. Association for Computational Linguistics.
Sha Li, Heng Ji, and Jiawei Han. 2021. Document-level event argument extraction by conditional generation. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computa- tional Linguistics: Human Language Technologies, pages 994, Online. Association for Computa- tional Linguisties.
Nanyun Peng. Hoifung Poon, Chris Quirk, Kristina Toutanova, and Wen-tau Yih. 2017. Cross-sentence n-ary relation extraction with graph LSTMs. Trans- actions of the Association for Computational Linguis- tics, 1:101-115.
Xiao Ling and Daniel Weld. 2012. Fine-graad Fine-grained entity recognition. In Proceedings of the Twenty- Sixth AAAI Conference on Artificial Intelligence, July 22 22-26, 2012, Toronto, Ontario, Canada. AAAI Press.
Sameer Pradhan, Xiaoqiang Luo, Marta Recasens, Ed- uard Hovy, Vincent Ng, and Michael Strube. 2014. Scoring coreference partitions of predicted mentions: A reference implementation. In Proceedings of the 52nd Annual Meeting of the Association for Compu- tational Linguistics (Volume 2: Short Papers), pages 30-35, Baltimore, Maryland. Association for Com- putational Linguistics.
Yi Luan, Luheng He, Mari Ostendorf, and Hannaneh Hajishirzi. 2018. Multi-task identification of entities, relations, and coreference for scientific knowledge graph construction. In Proceedings of the 2018 Con- ference Empirical Methods in Natural Language Processing, pages 3219-3232, Brussels, Belgium. Association for Computational Linguistics.
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. 2016. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natu- ral Language Processing, pages 2383-2392, Austin, Texas, Association for Computational Linguistics.
Xiaoqiang Luo. 2005. On coreference resolution perfor- mance metrics. In Proceedings of Human Language Technology Conference and Conference on Empiri- cal Methods in Natural Language Processing, pages 25-32, Vancouver, British Columbia, Canada. Asso- ciation for Computational Linguistics.
Huitao Shen. 2019. Jaceard index a kernel.
Timothy Mckinnon and Carl Rubino. 2022. The IARPA BETTER program abstract task four new semanti- cally annotated corpora from IARPA's BETTER pro- gram. In Proceedings of the Thirleenth Language
Ian Soboroff. 2023. The better cross-language datasets. In Proceedings of the 46th International ACM SI- GIR Conference on Research and Development in Information Retrieval, pages 3047-3053.

---

Beth M. Sundheim. 1992. Overview of the fourth Mes- sage Understanding Evaluation and Conference. In Fourth Message Uunderstanding Conference (MUC- 4): Proceedings of a Conference Held in McLean, Virginia, June 16-18, 1992.
Marc Vilain, John Burger, John Aberdeen, Dennis Connolly, and Lynette Hirschman. 1995. A model- theoretic coreference scoring scheme. In Sixth Mes- sage Understanding Conference (MUC-6); Proceed- ings of Conference Held in Columbia, Maryland, November 6-8, 1995.
Pauli Virtanen, Ralf Gommers, Travis B. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Ev- geni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, Carey, Ilhan Polat, Yu Feng. Fiii W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles Harris, Anne M. Archibald, An- tônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. 2020. SciPy 1.0: Fundamental Aigorithms for Scientific Computing Python. Nature Methods, 17:261-272.
Yuan Yao, Deming Ye, Peng Li, Xu Han, Yankai Lin, Zhenghao Liu, Zhiyuan Liu. Lixin Huang, Jie Zhou, and Maosong Sun. 2019. DocRED: A large-scale document-level relation extraction dataset. In Pro- ceedings of the 57th Annual Meeting of the Associa- tion for Computational Linguistics, pages 764-777, Florence, Italy. Association for Computational Lin- guistics.

---

A Solving ILPs
N:1 Constraints (Optional) Each e P can only be matched to most one E R. This is naturally encoded as
We use the integer linear programming (ILP) solver scipy. scipy.optie ootpyyoppiiie.....m milp in SciPy (Virtanen et al., 2020), which wraps the HiGHS solver (Huangfu and Hall, 2018).
Σ may S 1.
(43)
1:N Constraints (Optional) Similarly, we have
A.1 Set Matching with Latent Variables
To solve the combinatorial optimization problem in Eq. (36)
Σ May S 1.
(44)
1:1 Constraints (Optional) This simply the two constraints above combined. This translation to ILP is a generalization of the method proposed in SMATCH (Cai and Knight, 2013).
Σ (P
Σ My.M M (U.))MM
6x(u, v),
we cast it as an ILP problem. Recall that P and R contains variables in the set of Vp. VR respectively. and &x is (unnormalized) similarity for X assum- ing that their variables match. Essentially, (x(u,,) v) is an upper bound of the actual score the pair (u, v)
A.2 Matching of Arbitrary Structure
To solve the combinatorial optimization problem in Eq. (37)
may obtain.
(P, = max
Σ
ox(u,
We create the following variables for ILP, where
M"
(M.))MM
B = 1):
s.t. V(u, v), (u', E M
Sp Sp - VR
mav B is set to true if u, v matches, i.e., a
P.v. E R and (u, v) E M
cast it an ILP problem similar the transla- tion above.
May B is set to true variables y matches, i.e, E Vp.y E VR and yx E Mÿ-
set to true if e P.v R A variable may and (u, v) E M: i.c. u and v are matched.
We are solving the following ILP problem
We similarly set the coefficient vector e such that Cuv = 4x v). Therefore we are maximizing c m under the monotonicity constraints
m
max [CT
0
(40)
M (u, v) M (u', - uu 1' vV
with the vector to be solved being m vee (me f vec(( and the coefficient vector e = (5x uuvl ("vee"" is the matrix vectorization operator). The following constraints applied as needed.
The monotonicity constraints can be encoded as linear constraints by the following:
Buy + ma'y' 1 s [u 3p u' = @ SR v'
Latent Variable Constraints (Required) Re- call that X is product type and its fields are (fld; ty If type, is Var (the type for yet-to- be-matched variables), then u matches v implies that u. fld,d, matches f.f.d; Translating this to con- straints:
which can be rewritten as
May + mare S 1 [u Sp u' = v SR vl.
B Kernels
Similarity functions have additional desirable prop- erties when certain conditions are met. Below, we describe conditions under which some similarity functions are (positive definite symmetric) kernels. Definition 2. A positive definite symmetric kernel (p.d.s. kernel) is a function k XxX - P. that sat- isfies symmetry x xxx,) = <(y,x) and positive-semi- definiteness: (e Z where Kij = x(x,,x)). all "". E X, c E R". (42)
Muv S @u.fldd..fllpp
VX.fld; Var.
(41)
1:1 Constraints on Variables (Required) Each Vp can only be matched to at most one y VR. and vice versa:
E S 1: Eixxy x
mxy I 1.

---

Lemma 1. The Kronecker ö X {0, 1} is a p.d.s. kernel.
Note that F score can be written as 2x(x, y)
yx, x(x,x) + +k(y,y) =2x(x, yx(x,,)H(xx,))
Lemma 2. (Mohri et al., 2012, Theorem 6.10) If K1 : X1 x X1 - R and K2 : X2 x X2 - IR are p.d.s. kernels, then the product kernel k (X1 x
Hence F[K] is kernel.
Lemma 8. If x is kerne,, J[k] is kernel.
X2) x (X1 X X2) - I. is p.d.s. kernel where x2(x),x2), (1 x2)) (x), x2)x),x2))
Proof. Thus
This is the kernel version of the product similar- ity we discussed in the main text.
x(x,y)
J[k](x, <(x,x) + k(y,)) y(x,))
Lemma 3. (Haussler, 1999) If is a kernel, the vertex label kernel [x] is a kernel.
=k(x,)) (x,,))
Definition 3. (Kriege et al., 2016) A kernel k XxX - R20 is strong kernel if x(x.xx 2 x(x,y) for all x, X.
1 F[k](x,)) I 1, we have k(x, ())(,,) s 2 1. By Lemma 6,
Since 2x(x, (H(x,))
is a kernel, so J[k] is a ker- 1 <(x, xxx,)) nel.
Lemma 4. A similarity function that is also a ker- nel is a strong kernel.
Lemma 5. (Kriege et al., 2016) If K is a strong kernel, the optimal assignment kernel M [x] is kernel.
Therefore, given the lemmata above, have the nice property that any kernels composed with Fe, J are kernels. The deductions presented here follows Shen (2019).
Lemma 6. If is a kernel bounded by above:
maxx,y y)x,) U < +00, then K' yx
C MUC-4 Evaluation: Additional Details
U -(x(x))) is kernel.
String-valued similarities and Interactive Scor- ing For string-valued slots, although full entities are annotated in the reference, systems are required to predict just one mention per entity. Two differ- ent versions of Qstr were used: one for determin- ing the template alignment and one for computing the score given that alignment. The first version awarded full credit when there was at least a one- word overlap between the predicted string and at least one of the strings in the reference entity, so long as that word was not a designated premodi- fier; zero credit was awarded otherwise. Suppose valid(P, R) is true iff neither word P nor word R is premodifier. Then
Proof. With Taylor expansion, we have
1 2a x(x,))
K' <'(x,)) y)
This series converges because <(x, y) U. Since kernels are closed under power series, this kernel.
Lemma 7. K is a kernel, F[K] is a kernel.
1
Proof. Let H(x,)) y)
x(x,x) + x(y,y) H is ker-
nel. To see this, we prove that it is positive semidefi- nite. For all n E N,c; E R. and x; E X (1 s n), let x;).
write:
Sword (P, R) = Pword [valid(P, R)]
(45)
Øsr = [oordl) > 0]
(46)
St + Cj
The second version dstr. used for final reporting, merely enhanced Eq. 46 by interactively querying the user in cases where a mismatch could not be automatically resolved, whereupon the user could determine the appropriate amount of credit to award, including partial (=half) credit. Full guide- lines on interactive scoring can be found in the gzip archive containing the MUC-3 and MUC-4 data here: https://www-nlpir.nistt.t htwp:piirr...tt..og/eeeeeeeee wrtjjcttts/ncccmmccc.aaa/aaatttt html (see TEST:/SCOEER/scorrnnn--gelellll
CiCi {-' -
1-1
cic,t"i -1::
1=1 j=l
di O. x
html
Hence H is a kernel.

---

Template Alignment Constraints Template alignments for the original evaluation featured couple of quirks. For one, it was possible to obtain partial (=half) credit for the template ("incident") type by predicting the generic attack label in place of any of the other, more specific labels (bombing, kidnapping, etc.). 18 For another, partial match at least one of the following slots was required: physical target identifier, physical target type, hu- man target name, human target description, human target type, perpetrator individual identifier, and perpetrator organization identifier. Chinchor (1992) notes that this constraint was put in place to pre- vent "fortuitous" but spurious template alignments that were observed in the MUC-3 evaluation. To our knowledge, researchers have not applied these rules in evaluating their own systems MUC-4 since the original evaluation.
still be optimized indirectly by instead optimizing the template alignment against the second term only, as this will be non-zero only cases where there is a match on template type.
For more on BETTER, see Soboroff (2023), Mckinnon and Rubino (2022). and the follow- ing URL: https://www. wawpp.wwww.aa.......t.........a. gow/index.phht research programs/better All BETTER pro- gram datasets available here (note that count registration is required, but free): https: Appendices and D of Chen et al. (2023) also provide a good overview of the Granular task and its evaluation, including definitions of Φ for all slot filler types. 19
MUC-4: Recent Work In recent years, it has become standard to evaluate only on the string-fill slots, plus the template type (Chambers and Juraf- sky, 2011; Du et al., 2021b; Das et al., 2022; Chen al., 2023). Du et al. (2021b) thus proposed version of Eq. 32 that sets +, =. which amounts using CEAF-REE (Eq. 26) determine the op- timal template alignment. Following on this work. Chen et al. (2023) additionally present MUC-4 re- sults using their relaxed (one-sided) metrics (Eqs. 27, 28) for ΦT.
D BETTER
BETTER Granular a recent template extraction dataset released as part of the IARPA BETTER program that is more complex than MUC-4 both in having different slots for each template type and in having greater diversity of filler types. Here, we focus just the key difference in overall score calculation compared to MUC-4. The Granular score is the product of the slot filler F1 score (Eq. 32) and the template type Fj score:
F Feeplaates [drype]
Fe X templates [ōtype x Eiillers [8stot x $1]] (47)
where Stype applies to template types and ØT applies to filler types, as in Eq. 32. Because this product cannot be expressed as a sum of scores over aligned template pairs (Bq. 13), it does not, on its face, fit within our framework. However, this score could
19 One distinctive feature of BETTER Granular in contrast to MUC-4 is that some slots may take events (as in $3. 1) as fillers, in addition to entities and categorical values.
18 Note that, as with scoring for set-fill slots, this presages the proposal in 36 for hicrarchy-aware scoring.


Reviews:
[{"review_id": "tB2zfZVQjH", "reviewer": "Reviewer_J1er", "summary": "", "questions": "Question A: Is there a convincing explanation/justification for your framework, independent of actual practice? That is, why should all IE-evaluation measures be based on your formulation, when there are actual measures which cannot be conveyed that way? To me, the (real) problems of MUC and B3 are not a reason why they should be discarded. Would it be possible to enlarge your framework so that they could be described there?", "limitations": "", "rating": 4, "confidence": 5, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for this positive review and hope to speak to your concerns below.\n\nUpon deeper reflection, we have realized that our framework actually does encompass both precision and recall for MUC and $\\rm B^3$, and we intend to update the appendix to reflect this. We should clarify that we were never intending to dismiss these metrics on the basis of their problems.\n\n To encompass MUC, we first need to extend our notion of alignment constraints. Right now in our formulation there are two kinds of constraints: a one-to-one mapping, and a many-to-one mapping. We introduce a many-to-many mapping here, essentially with no constraints: the score would just be the sum of all edges in the bipartite graph. Let’s denote this case as $\\sim$ (as opposed to $\\to$, since we are moving from a *function* to any binary *relation*). \n\n   - MUC considers the number of *coreferent links* in entities. Between two entities $X$ and $Y$, the number of shared links between them is $\\left| X \\cup Y \\right| - 1$ if they have more than 2 common mentions. Define this (shared number of coreferent links) as a score between a predicted entity and a reference entity: $ \\phi_{\\rm link}(X, Y) = \\max (0, \\left| X \\cup Y \\right| - 1 ) $.\n  Given the many-to-many mapping we just introduced (since MUC computes this score for *each pair* of predicted and reference entities), the precision of MUC would just be\n  $$ \\mathtt{P}\\_{\\rm MUC} = \\mathtt{P}\\_\\texttt{entities}^{\\sim} [\\phi_{\\rm link}] $$\n  Recall/F1 can be defined similarly.\n - Since $\\rm B^3$ assigns a score to each *mention* based on the *entity it belongs to*, we need to slightly modify the data structure of the output of coreference resolution system to encompass $\\rm B^3$: the type to derive a metric changes from *entities* to *(mention, entity) pairs*, just like a relation triplet describing a *membership* relation below. Under this output data structure, we can derive the precision and recall of $\\rm B^3$ on the `MembershipRelationSet` type as:\n$$ \\mathtt{P}\\_{\\rm B^3} = \\mathtt{P}\\_\\texttt{rels}^{\\leftrightarrow} [\\delta\\_\\texttt{mention} \\times \\mathtt{P}\\_\\texttt{entity}^{\\leftrightarrow}[\\delta\\_\\texttt{mention}]] $$\n$$ \\mathtt{R}\\_{\\rm B^3} = \\mathtt{R}\\_\\texttt{rels}^{\\leftrightarrow} [\\delta\\_\\texttt{mention} \\times \\mathtt{R}\\_\\texttt{entity}^{\\leftrightarrow}[\\delta\\_\\texttt{mention}]] $$\n\t\n```\n  class Membership:\n       mention: Mention\n       entity: Entity\n  class MembershipRelationSet:\n       rels: Set[Membership]\n```\n\n---\n\n> *Is there a convincing explanation/justification for your framework, independent of actual practice? That is, why should all IE-evaluation measures be based on your formulation, when there are actual measures which cannot be conveyed that way?*\n\nEven given our inclusion of MUC and $B^3$, we want to engage this point; it’s a good one. Suppose there *is* some other IE metric that in fact does not fit within the framework. We think the framework still has significant value for at least a couple of reasons.\n\n - First, it clearly is descriptive of a broad set of important IE metrics, and even generalizations that admit of exceptions can still be tremendously helpful by illuminating key commonalities across a range of superficially disparate things. We are *not* making a prescriptive argument that all IE metrics absolutely *must* fit this framework. Rather, we’re making a descriptive argument that it is intriguing and informative that so many of them do.\n\n - Second, as we contend in the introduction (L058-L060) and try to demonstrate in section 4, we think the framework is plausibly *generative*, inasmuch as it facilitates metric design by encouraging researchers to consider how the characteristics of the problem they’re working on are best reflected in the three framework components — constraints, similarity function, and normalization — and in how the scores for substructures compose in the scores for superstructures. \n\nThus, we take the justification to consist not only in “actual practice” (i.e. the descriptive characterization of existing metrics), but also in its generative potential. We think these are sufficient. If there is another form of justification that seems important that we have not spoken to, we would be keen to hear of it.", "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": "This paper provides an interesting generalization over many different evaluation measures in information extraction.", "reasons_to_reject": "Since not all IE-evaluation measures can be translated into this framework, maybe it is not that relevant.", "questions_to_authors": "Question A: Is there a convincing explanation/justification for your framework, independent of actual practice? That is, why should all IE-evaluation measures be based on your formulation, when there are actual measures which cannot be conveyed that way? To me, the (real) problems of MUC and B3 are not a reason why they should be discarded. Would it be possible to enlarge your framework so that they could be described there?", "paper_topic_and_main_contributions": "This paper provides a general formalism for IE extraction, defining three components: similarity function, alignment, and normalizing function, and show how many IE tasks can be described that way: from binary relation extraction to MUC4 template extraction. The paper also applies the framework to other non-IE tasks, and suggests that its use can improve the design of new metrics.\n", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eux5CcWPS8", "reviewer": "Reviewer_Aomu", "summary": "", "questions": "I wonder if there is any possibility to formally test with this framework whether a new evaluation measure is inconsistent or not robust.\n\n", "limitations": "", "rating": 4, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for this encouraging review!\n\n#### **Reasons to Reject**\n\n - *On mathematical notations:* Since we unified various metrics in terms of their *substructures*,  *alignment constraints*, and *normalizers*, we believe that our notation is needed to fully express these features of various metrics. We ourselves deliberated quite a bit over the clearest notation to use and would be open to any specific suggestions for improving it. \n - *On data structures:* We also acknowledge there is a risk of redundancy in giving explicit data structures for each problem we cover — particularly for readers intimately familiar with those problems. Our aim here was simply to avoid ambiguities **as well as to make the paper self-contained**, as similar problem settings often focus on different kinds of objects across benchmarks (e.g. extraction of mentions vs. entities in template filling and $N$-ary relation extraction). But we would likewise welcome recommendations for a more economical way of achieving this aim.\n\n#### **Questions**\n\n> *I wonder if there is any possibility to formally test with this framework whether a new evaluation measure is inconsistent or not robust.*\n\nThis is an intriguing thought. However, we don't view the framework as adjudicating questions of robustness or inconsistency *per se*. As we suggest at different points (principally in section 4), the framework clearly admits metrics that have less than desirable properties (e.g. inability to award partial credit, insensitivity to an ontology's type hierarchy), while also admitting many standard, widely accepted metrics (trigger and argument F1 for event extraction). As such, we wouldn't contend that the framework cuts \"robustness\" or \"inconsistency\" at the joints, but it *does* isolate the key metric components that one might want to evaluate with respect to these characteristics for whatever problem is at hand.\n\n#### **Missing References**\n\nWe appreciate the pointer to Lu et al. (2022), which is clearly relevant. We will be sure to include this citation in our revisions.", "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": "The theoretical aspects are well presented and the framework will be of interest not only for the IE field. \nThe same approach (a generalization of evaluation measures) could be applied (provided the necessary adaptations of the problems that do not take into account the same marching constraints) to other fields such as information retrieval and text classification, for example.\n\n", "reasons_to_reject": "The only issue that I can see is that, despite being a clear paper, the authors have added an overload of symbols for the mathematical notation. \nOff the top of my head, I do not have a solution for this. I can only imagine that in order to have a unified view, this solution is the easiest one.\n\nAs a minor issue, the examples of the data structures are good at the beginning of the paper. After a couple of examples, they are redundant.", "questions_to_authors": "I wonder if there is any possibility to formally test with this framework whether a new evaluation measure is inconsistent or not robust.\n\n", "paper_topic_and_main_contributions": "In this paper, the authors present two main contributions in the field of Information Extraction (IE). \nFirst, they propose a framework to enhance the IE theory by highlighting the interconnections among different evaluation metrics proposed over the years. Second, they provide a systematic bottom-up approach for devising new metrics.", "excitement": 4, "reproducibility": null, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "Not really a missing reference, but an interesting parallel work to check\n\nhttps://aclanthology.org/2022.acl-long.395.pdf\n"}, "extra_text": {}}, {"review_id": "jgMagRSlnH", "reviewer": "Reviewer_z6Hc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate this review and are pleased that you see merit in the framework! We hope to address your remaining concerns below.\n\n > *Lack of example applications of the framework for some widely used specific metrics of IE evaluation*\n\nWhile we acknowledge that our survey of IE metrics is certainly not exhaustive (L189-92) — indeed, it could not be, given the space — we do try to present a broad and representative collection of actual, widely used metrics across multiple tasks and show how they realize our framework. Additionally, we use the framework to propose some alternative metric designs in section 4. However, we think it's possible we've not fully understood the concern raised here. For instance, perhaps there are specific metrics you have in mind that we do not cover that you believe we really ought to. We would appreciate further elaboration on this point.\n\n> *Lack of explanation of limitations of the framework …*\n\n Thank you for highlighting these additional considerations. We do note two important limitations in the **Limitations** section — namely, that we cannot claim exhaustive coverage of all metrics and that there may be some metrics (e.g. MUC) that do fit the framework *(though see our response to Reviewer J1er on this point as we have expanded the framework to incorporate MUC and B3)*. We will be sure to address your concerns in our revisions, but below are some brief replies. In general, we think they represent points we could clarify, rather than genuine limitations.\n\n - *Extraction of variably sized tuples*: This can readily be accommodated, so long as a similarity function can be defined between tuples of different sizes (though plausibly, one would want to set similarity between tuples of different arity to zero).\n - *Infinite types (open-domain IE)*: Infinite label spaces can also be accommodated, once again so long as a similarity function can be defined between the relevant objects. Exact label match, for instance, does not require having a finite label set.\n - *Generative vs. extractive models*: The framework deals with data structures that are generally specified by the task, not the model. As such, the framework is agnostic to model choice, so long as models produce outputs that can be mapped to these data structures (which is presumably true of any model designed for the task).\n - *Favoring more tuples over fewer tuples*: The framework itself exhibits no preference in this regard. Granted, it is certainly possible to design a metric using the framework that does have such a preference for more tuples (e.g. any recall-normalized metric will have this property). But it is also possible to design a metric with the opposite preference (e.g. any precision-normalized metric).\n - *Restrictive alignment constraints*: These constraints are fundamentally just descriptive of what we actually observe across IE metrics: in the vast majority of cases, each predicted object is paired with a single reference object and vice-versa (two-sided one-to-one constraints). Much more rarely, multiple predictions may correspond to the same reference (as for CEAF-RME; one-sided constraints). As we have responded to Reviewer J1er, we included a relaxed alignment with *no constraints*: this would let our framework encompass the MUC metric for coreference resolution.\n\n> *Lack of some details, e.g. how to establish bijection, if the framework works at the sentence and/or document level*\n\nThank you for pointing out places where we could make our exposition clearer; we will happily include further clarifications on these points. To briefly address them here:\n\n - (Partial) bijections are established via optimization over the metric itself: selecting the mapping between predicted and reference objects that maximizes total metric score (e.g., under one-to-one alignment constraints, it can be solved with the Hungarian algorithm). This optimization problem is the one at the core of all *unbalanced assignment problems* (L126-132) but we will make this more explicit.\n - The framework is **fully agnostic to choice of text segmentation** (i.e. it can be applied to both sentence- and document-level problems).\n\nIf there are further details we can clarify, please let us know.", "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": "First theoretic framework of evaluation metrics for various IE tasks", "reasons_to_reject": "- Lack of example applications of the framework for some widely used specific metrics of IE evaluation\n- Lack of explanation of limitations of the framework, if it can be applied e.g. for the task of extracting tuples of various sizes, for open domain IE, where event types are not finite, for generative models, instead of extractive models, if the framework favors an IE system that produces more tuples than another producing less tuples, if the two constraints on the alignment in Section 2 are too restrictive\n- Lack of some details, e.g. how to establish bijection, if the framework works at the sentence and/or document level", "questions_to_authors": "", "paper_topic_and_main_contributions": "The authors present a theoretic framework of evaluation metrics for IE tasks, including binary/n-ary relation extraction, event extraction, coreference resolution, role-filler entity extraction and template extraction. This framework can server as a common language for evaluation metrics across the various IE tasks.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a general formalism for several Information Extraction tasks, ranging from binary relation extraction to MUC4 template extraction, utilizing similarity functions, alignment, and normalization functions.

Overall, the paper is well-written and offers interesting generalizations across various evaluation measures in Information Extraction. It is also the first theoretically motivated framework in this field.
Decision: Accept-Main