jp-evalb: Robust Alignment-based PARSEVAL Measures (2024)

Abstract: We introduce an evaluation system designed to compute PARSEVAL measures, offering a viable alternative to evalb commonly used for constituency parsing evaluation. The widely used evalb script has traditionally been employed for evaluating the accuracy of constituency parsing results, albeit with the requirement for consistent tokenization and sentence boundaries. In contrast, our approach, named jp-evalb, is founded on an alignment method. This method aligns sentences and words when discrepancies arise. It aims to overcome several known issues associated with evalb by utilizing the ‘jointly preprocessed (JP)’ alignment-based method. We introduce a more flexible and adaptive framework, ultimately contributing to a more accurate assessment of constituency parsing performance.

## introduction for constituency parsing, whether statistical or neural, we rely on the evalb implementation 1 , which implements the parseval measures @xcite as the standard method for evaluating parser performance. there is also a variant of the evalb_spmrl implementation specifically designed for the spmrl shared task, allowing the evaluation to consider functional phrase labels @xcite . a constituent in a hypothesis parse of a sentence is labeled as correct if it matches a constituent in the reference parse with the same non-terminal symbol and span (starting and end indexes). despite its success in evaluating language technology, evalb faces unresolved critical issues in our discipline. evalb imposes constraints, demanding consistent tokenization and sentence boundary outcomes. its implementation assumes equal-length gold and system files with matching terminal nodes. in machine translation (mt), sentence alignment involves identifying corresponding sentences in two or more languages and linking sentences from one language to their corresponding counterparts in another. sentence alignment has been a subject of study for many years, leading to the development of various algorithms. early research in this area relied on statistical methods that used bilingual corpora to create models capturing the lexical equivalence between words in different languages. for instance, the gale-church algorithm, based on sentence length, was one such approach @xcite . bleualign introduced a more advanced iterative bootstrapping approach building on length-based methods @xcite . earlier approaches also aimed to enhance sentence alignment methodologies by incorporating lexical correspondences, as seen in hunalign @xcite or the ibm-model based lexicon translation approach @xcite . some attempts involved the integration of linguistic knowledge, heuristics, and various scoring methods to improve efficiency, as demonstrated by vecalign @xcite . word alignment methodologies are also employed to establish correspondences between words in one language and their direct translations in another. widely used ibm models @xcite , along with tools like giza++ @xcite or berkeleyaligner @xcite , are capable of aligning words. syntactic analysis in the current field of language technology has been predominantly reliant on dependencies. semantic parsing in its higherlevel analyses often relies heavily on dependency structures as well. therefore, dependency parsing and its evaluation method have their own advantages, such as a more direct representation of grammatical relations and often simpler parsing algorithms. however, constituency parsing maintains the hierarchical structure of a sentence, which can still be valuable for understanding the syntactic relationships between words and phrases. various studies on formal syntax have focused on constituent structures, such as combinatory categorial grammar (ccg) parsing @xcite @xcite or tree-adjoining grammar (tag) parsing @xcite (whereas ccg and tag also inherently incorporate dependency structures). in addition, there have been ongoing studies on constituency parsing, such as the linearization parsing method @xcite @xcite . if a method that utilizes constituent structures is designed to achieve the goal of creating an end-to-end system, it requires more robust evaluation methods for their constituent structure evaluation. this paper builds upon our recently introduced alignment-based algorithm, for computing par-seval measures @xcite , which offers a novel approach for calculating precision, recall, and f scores, even in cases of sentence and word mismatch. the primary objective of this paper is to replicate the outcomes generated by evalb during the evaluation process. this aims to achieve a comprehensive understanding of the parser's performance by addressing the previous issues of evalb and preserving its long-standing legacy. it includes the numbers of gold, test, matched brackets, and cross brackets, as well as precision, recall, and f scores. furthermore, we present the number of correct pos tags and their tagging accuracy, following a methodology employed by evalb. our proposed method jp-evalb is particularly crucial in end-to-end settings, where deviations from the gold file may arise due to variations in tokenization and sentence boundary results. ## detailing the jp-evalb algorithm to describe the proposed algorithms, we use the following notations for conciseness and simplicity. t l and t r introduce the entire parse trees of gold and system files, respectively. t l is a simplified notation representing t l(l) , where l is the list of tokens in l. this notation applies in the same manner to r. s t represents a set of constituents of a tree t , and c(t ) is the total number constituents of t . c(tp) is the number of true positive constituents where s t l ∩ s t r , and we count it per aligned sentence. the presented algorithm 1 demonstrates the pseudo-code for the new parseval measures. algorithm 1 pseudo-code for jp-evalb 1: function parsevalmeasures (tl and tr): 2: extract the list of tokens l and r from tl and tr 3: l ′ , r ′ ← sentencealignment(l, r) 4: align trees based on l ′ and r ′ to obtain t l ′ and t r ′ 5: while t l ′ and t r ′ do 6: extract the list of tokens l and r from t l ′ i and t r ′ i 7: l ′ , r ′ ← wordalignment(l, r) 8: st l ← getconstituent(t l ′ i (l ′ ) , 0) 9: st r ← getconstituent(t r ′ i (r ′ ) , 0) 10: c(tl) ← c(tl)+ len(st l ) 11: c(tr) ← c(tr)+ len(st r ) 12: while st l and st r do 13: if (label, startl, endl,l ′ j ) = (label, startr, endr,r ′ j ) then 14: c(tp) ← c(tp) + 1 15: end if 16: end while 17: end while 18: return c(tl), c(tr), and c(tp) algorithm 2 pseudo-code for alignment 1: function alignment (l, r): 2: while l and r do 3: in the first stage, we extract leaves l and r from the parse trees and align sentences to obtain l ′ and r ′ using the sentence alignment algorithm. algorithm 2 shows the generic pattern-matching approach of the alignment algorithm where sentence and word alignment can be applied. we define the following two cases for matched cases (i,j) of sentence alignment: in the next stage of algorithm 1, we align trees based on l ′ and r ′ to obtain t l ′ and t r ′ . by iterating through t l ′ and t r ′ , we conduct word alignment and compare pairs of sets of constituents for each corresponding pair of t l ′ i and t r ′ j . the word alignment algorithm adopts a logic similar to sentence alignment. it involves the accumulation of words in l ′ and r ′ under the condition that pairs of l i and r j do not match, often attributed to tokenization mismatches. here, we assume interchangeability between notations of sentence alignment (l) and word alignment (l i ). we define the following two cases for matched cases (i,j) of word alignment: when deciding whether to accumulate the token from l i+1 or r j+1 in the case of a word mismatch, we base our decision on the following condition, rather than a straightforward comparison between the lengths of the current tokens l i and r j : finally, we extract a set of constituents, a straightforward procedure for obtaining constituents from a given tree, which includes the label name, start index, end index, and a list of tokens. the current proposed method utilizes simple pattern matching for sentence and word alignment, operating under the assumption that the gold and system sentences are the same, with minimal potential for morphological mismatches. this differs from sentence and word alignment in machine translation. mt usually relies on recursive editing and em algorithms due to the inherent difference between source and target languages. ## word and sentence mismatches word mismatch we have observed that the expression of contractions varies significantly, resulting in inherent challenges related to word mismatches. as the number of contractions and symbols to be converted in a language is finite, we composed an exception list for our system to capture such cases for each language to facilitate the word alignment process between gold and system sentences. in the following example, we achieve perfect precision and recall of 5/5 for both because their constituent trees are exactly matched, regardless of any mismatched words. if the word mismatch example is not in the exception list, we perform the word alignment. we can still achieve perfect precision and recall (5/5 for both) without the word mismatch exception list because their constituent trees can be exactly matched based on the word-alignment of { 1.0 ca 1.1 n't} and { 1.0 can 1.1 not} (figure 1a ). the effectiveness of the word alignment approach remains intact even for morphological mismatches where "morphological segmentation is not the inverse of concatenation" @xcite , such as in morphologically rich languages. for example, we trace back to the sentence in hebrew described in @xcite as a word mismatch example caused by morphological analyses: pairs of { 1.0 h 1.1 cl, 1 cl} ('the shadow') and { 4.0 h 4.1 neim, 4 hneim} ('the pleasant') are wordaligned using the proposed algorithm, resulting in a precision of 4/4 and recall of 4/6 (figure 1b ). sentence mismatch when there are sentence mismatches, they would be aligned and merged as a single tree using a dummy root node: for example, @s which can be ignored during evaluation. in the following example, we obtain precision of 5/8 and recall of 5/7 (figure 1c ). assumptions to address morphological analysis discrepancies in the parse tree during evaluation, we establish the following two assumptions: (i) the entire tree constituent can be considered a true positive, even if the morphological segmentation or analysis differs from the gold analysis, as long ## usage of jp-evalb we use the following command to execute the jp-evalb script: ## case studies section 23 of the english penn treebank under identical conditions where sentences and words match, the proposed method requires around 4.5 seconds for evaluating the section 23 of the penn treebank. on the same machine, evalb completes the task less than 0.1 seconds. we do not claim that our proposed implementation is fast or faster than evalb, recognizing the well-established differences in performance between compiled languages like c, which evalb used, and interpreted languages such as python, which our current implementation uses. our proposed method also introduces additional runtime for sentence and word alignment, a process not performed by evalb. we present excerpts from three result files generated by evalb and our proposed method in figure 3 . the parsed results were obtained using the pcfg-la berkeley parser @xcite ). it's worth noting that there may be slight variations between the two sets of results because evalb excludes constituents with specific symbols and punctuation marks during evaluation. however, as we mentioned earlier, jp-evalb can reproduce the exact same results as evalb for a legacy reason. ## conclusion despite the widespread use and acceptance of the previous parseval measure as the standard tool for constituency parsing evaluation, it faces a significant limitation by requiring specific task-oriented environments. consequently, there is still room for a more robust and reliable evaluation approach. various metrics have attempted to address issues related to word and sentence mismatches by employing complex tree operations or adopting dependency scoring methods. in contrast, our proposed method aligns sentences and words as a preprocessing step without altering the original parseval measures. this approach allows us to preserve the complexity of the original evalb implementation of parseval while introducing a linear time alignment process. given the high compatibility of our method with existing parseval measures, it also ensures the consistency and seamless integration of previous work evaluated using parseval into our approach. ultimately, this new measurement approach offers the opportunity to evaluate constituency parsing within an end-toend pipeline, addressing discrepancies that may arise during earlier steps, such as tokenization and sentence boundary detection. this enables a more comprehensive evaluation of constituency parsing. all codes and results from the case studies can be accessed at https://github.com/jungyeul/ alignment-based-parseval/ .