A Unified View of Evaluation Metrics for Structured Prediction (2023)

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.

## introduction a wide range of tasks in nlp can be considered as forms of structured prediction. syntactic and semantic parsing produces a tree or graph 2 based on text. information extraction (ie) aims to produce structured representations of data extracted from unstructured sources, often in the form of relations that may be used to populate a database @xcite . such relations may be typed or untyped, may have different numbers of arguments, and may relate objects of different kinds (e.g. mentions, entities, events, or even images). the structural complexity of these representations varies considerably between tasks. on the simpler end, problems like binary relation extraction require identifying relationships between pairs of entity mentions. on the more complex end are figure 1: our generic framework, with the ceaf 𝜙 4 metric @xcite as for coreference resolution as an example. here the task output is a set of entities, where each entity is a set of coreferent mentions identfied in the document. computing ceaf 𝜙 4 thus amounts to calculating the matching similarity between the predicted (𝑃) and reference (𝑅) sets of entities. a wide array of evaluation metrics have been proposed across this spectrum of tasks. for simpler ones, researchers have generally converged to a standardized set of metrics (e.g. trigger and argument f 1 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 @xcite @xcite . on the one hand, this observation drives a contribution to structured prediction theory, clarifying the relationships among numerous metrics proposed over the years by identifying their core components. on the other, it drives a contribution to nlp practice, offering a bottom-up process for designing new metrics based on an output structure. our contributions can be summarized as follows: throughout, we emphasize both how evaluation of substructures (e.g. mentions) composes in the evaluation of superstructures (e.g. relations, templates), as well as the different notions of similarity employed for different structures. our discussion starts with simpler tasks and proceeds to more com-plex ones, interleaving with examples throughout our exposition. ## records and sets we begin by focusing on records foot_0 with non-nested, fixed-named fields or slots. specifically, for 𝑃, 𝑅 ∈ 𝑋 of predicted and reference objects of record type 𝑋, we induce a similarity function over 𝑋. an object is at least as similar to itself as to any other. a relaxed version is an unnormalized similarity, where 𝜙 : 𝑋 × 𝑋 → [0, +∞). ## sets with latent variables next, we consider abstract meaning representation (amr) parsing @xcite , which involves outputs with latent variables. amr describes the semantics of a sentence as a rooted, directed graph represented by a set of neo-davidsonian triples, each with a subject, an object, and a relation. subjects are variables and objects can be variables or concepts (e.g. from propbank @xcite ): class prop: # logical propositions rel: relation # instance, arg0, 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: however, this poses a problem, as we cannot know whether two variables 𝑥 and 𝑦 refer to the same object: instance(𝑥, boy) and instance(𝑦, boy) could match if there is no constraint enforcing that 𝑥 ≠ 𝑦. 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 to be the maximum fscore obtainable via a one-to-one matching of variables between two amrs @xcite . that is, it looks for an optimal partial bijection 𝑀 ↔ 𝑉 ⊆ 𝑉 𝑃 × 𝑉 𝑅 between the variables of the predicted and reference amrs (𝑉 𝑃 and 𝑉 𝑅 , respectively). given 𝑀 ↔ 𝑉 , we can define φvar (𝑥, 𝑦) = ⟦(𝑥, 𝑦) ∈ 𝑀 ↔ 𝑉 ⟧, we generalize the spirit of smatch to any set of 𝑋 with latent variables yet to be matched. the matching score of 𝑃, 𝑅 with latent variables 𝑉 𝑃 , 𝑉 𝑅 is defined to be computing this constrained optimization problem requires solving 𝑀 ↔ 𝑉 , which can be done via an integer linear programming (ilp) solver @xcite . see appendix a for more details. ## matching of other structures in the past few sections we developed tools to obtain matching of sets. we can extend this to match more complex structures such as sequences, dags, and arbitrary directed graphs. recall the matching score in eq. 13: we computed a sum of similarities based on matched pairs. in the matching of structures, the matching should preserve the structure of the object being matched. elements of a sequence form a total order where earlier elements precede later elements. given two sequences 𝑃, 𝑅 whose elements are of type 𝑋, each is equipped with a total order: (𝑃, ⪯ 𝑃 ), (𝑅, ⪯ 𝑅 ). that is, we seek a maximum monotonic matching between 𝑃 and 𝑅 that preserves the total order. for example, the matching score between (1, 2, 3, 4, 5) and (1, 3, 5, 7, 9) is 3 since 1, 3, 5 are monotonically matched. the sequence matching problem given by eq. ( 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 ⪯ of sequence elements is relaxed to a partial order in dags and a preorder in arbitrary directed graphs. the constrained optimization problem in eq. 37 can be solved via ilp, see appendix a. ## discussion we have seen that a diverse set of structured prediction metrics can be framed as computing a normalized total matching score for an optimal matching, given some similarity, which may itself reflect a score over an optimal matching of the relevant substructures. we now consider how different problem settings may motivate particular design decisions within this framework. we also highlight a couple of cases in which the actual metrics used for a task might be modified to better fit the problem setting. partial credit for many tasks, we want to award some credit for partially correct responses. in applications where precision is paramount, it may be appropriate to insist on exact matches, but less so when some modest tradeoff with recall is desired. moreover, many ie objects intuitively admit gradient notions of correctness. perhaps the most obvious example of this is mentions. exact match on mentions, whether stringor offset-based, remains surprisingly common despite 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 typically more appropriate. recently, there has also been greater interest in the informativity of entity mentions @xcite , where, e.g., @xmath0, and where scores may need to vary according to a mention's informativity. all of these can be captured by different choices of 𝜙 mention . 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 entities 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 𝜙 3 or 𝜙 4 . hierarchical ontologies type hierarchies are another 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 @xcite , rams @xcite , wikievents @xcite , 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. following the discussion above, it may thus often be appropriate to replace exact type matches (𝛿 type ) with similarities that award partial credit for correct ancestor type prediction. one possibility is a level-based partial scoring: given a 𝐷-level type ontology with types specified as a 𝐷-tuple 𝑃 = ( 𝑝 1 , . . . , 𝑝 𝐷 ), we could, for instance, award credit based on the depth 𝑑 ∈ {0, . . . , 𝐷} of the most specific correctly predicted type, e.g.: there is some precedent for schemes like this, but proper analysis of performance on tasks with hierarchical ontologies requires metrics that account for that hierarchy, and the field of ie as a whole would benefit from adopting them more widely. one-sided vs. two-sided constraints in general, metrics impose constraints on the matching between the predictions and the reference. overwhelmingly, 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 @xcite , which use one-sided constraints, are motivated in part by a need to evaluate a model that predicts mention fillers against references that contain entity fillers. this suggests a more general motivation for one-sided constraints -namely, for cases where the reference outputs are sets, but where predictions take the form of members of those sets. ## conclusion we have presented a framework that unifies a variety of structured prediction metrics as normalized scores over (possibly hierarchical) constrained optimal matchings of structured objects. on the side of theory, our framework elucidates the relationships among tasks by defining the core components of their metrics. on the side of practice, it offers a 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 implementations.