Structured Tree Alignment for Evaluation of (Speech) Constituency Parsing

Freda Shi, Kevin Gimpel, Karen Livescu

Abstract

We present the structured average intersection-over-union ratio (STRUCT-IOU), a similarity metric between constituency parse trees motivated by the problem of evaluating speech parsers. STRUCT-IOU enables comparison between a constituency parse tree (over automatically recognized spoken word boundaries) with the ground-truth parse (over written words). To compute the metric, we project the ground-truth parse tree to the speech domain by forced alignment, align the projected ground-truth constituents with the predicted ones under certain structured constraints, and calculate the average IOU score across all aligned constituent pairs. STRUCT-IOU takes word boundaries into account and overcomes the challenge that the predicted words and ground truth may not have perfect one-to-one correspondence. Extending to the evaluation of text constituency parsing, we demonstrate that STRUCT-IOU can address token-mismatch issues, and shows higher tolerance to syntactically plausible parses than PARSEVAL (Black et al., 1991).

Introduction

Constituency parsing—the task of identifying the nested syntactic structure of a sentence—has traditionally relied on the assumption of discrete, fixed word tokens. The standard evaluation metric, PARSEVAL, calculates precision and recall based on exact matches of word spans. However, this paradigm falters in "textless" or speech-centric environments. In modern speech parsing, models often generate trees directly from audio where word boundaries are continuous and fuzzy. If a predicted word boundary shifts by even a fraction of a second compared to the ground truth, PARSEVAL fails because the underlying tokens no longer align perfectly.

Beyond speech, this "token-mismatch" problem persists in text parsing for morphologically rich languages like Hebrew. Different tokenization strategies can result in different numbers of leaf nodes for the same sentence, making traditional metrics inapplicable. To bridge this gap, we introduce STRUCT-IOU (Structured Average Intersection-over-Union), a metric that treats tree nodes as time intervals and uses structured alignment to evaluate similarity without requiring identical leaf sets.

Methodology: The STRUCT-IOU Metric

STRUCT-IOU moves away from discrete indices toward a continuous representation of syntactic structures. The methodology consists of four primary components:

  1. Relaxed Segment Trees: Instead of defining constituents by word indices (e.g., words 2 to 5), every node in the tree is associated with a continuous segment or time interval. This allows the metric to operate on the physical or temporal reality of the signal rather than an idealized token list.
  2. Forced Alignment: To compare a text-based gold standard with a speech-based prediction, we use forced alignment to project the written ground-truth words onto the audio timeline. This establishes the "true" temporal boundaries for the gold constituents.
  3. Structured Alignment: This is the core innovation. The metric seeks an optimal matching between nodes of the same label (e.g., matching a Noun Phrase in the predicted tree to a Noun Phrase in the gold tree). The alignment is constrained to preserve the hierarchical "parent-child" logic of the trees, ensuring that the matched structure is syntactically coherent.
  4. Optimization: The similarity between matched nodes is measured using Intersection-over-Union (IOU) of their time spans. We provide a dynamic programming algorithm that finds the maximum-weight alignment in $O(n^2m^2)$ time, where $n$ and $m$ are the number of nodes in the respective trees.

Experimental Validation

We evaluated STRUCT-IOU across three distinct scenarios to test its robustness and correlation with human judgment:

  • Speech Parsing (NXT-SWBD): Using the NXT-Switchboard dataset, we examined how the metric handles the noisy word boundaries inherent in conversational speech.
  • English Text (PTB): Using the Penn Treebank, we compared STRUCT-IOU against PARSEVAL to ensure it remains a valid metric for standard text-based tasks.
  • Hebrew Text (SPMRL 2013): We utilized the Hebrew dataset to demonstrate the metric's ability to handle morphological misalignment, where different systems may split a single word into different functional units.

Key Insights

Tolerance for Syntactic Ambiguity

One significant advantage of STRUCT-IOU is its nuanced handling of structural ambiguity. In cases like "I saw the girl with the telescope," where multiple valid parses exist, PARSEVAL often penalizes a model heavily for choosing the "wrong" valid interpretation. STRUCT-IOU, by focusing on the overlap of segments and structured alignment, recognizes shared sub-structures and provides a more representative score for syntactically plausible parses.

Robustness to Boundary Noise

Through perturbation experiments, we found that STRUCT-IOU is highly stable against "jitter" (minor shifts in word boundaries) and "insertions" (splitting a word into two). It only shows significant drops when the underlying syntax is fundamentally altered, such as through the deletion of boundaries. This suggests the metric effectively captures the "shape" of the parse rather than being distracted by minor temporal noise.

Performance and Correlation

On the Penn Treebank, STRUCT-IOU achieved a strong Spearman’s correlation ($\rho = 0.821$) with the gold-standard PARSEVAL $F_1$ score, proving it is a reliable proxy for traditional metrics. In the Hebrew parsing task, it achieved a correlation of $0.823$ with human-judged quality, successfully navigating tokenization mismatches that would typically require manual alignment or complex preprocessing.

Conclusion and Future Work

STRUCT-IOU provides a robust, mathematically grounded framework for evaluating constituency parsing in the presence of boundary uncertainty. While currently optimized for constituency trees and continuous time ranges, the underlying principle of structured IOU alignment is a general-purpose tool for tree-matching tasks. Future research may extend this metric to dependency parsing or explore its application as a differentiable loss function to train models that are inherently more robust to boundary errors.

Summary updated

Abstract

We present the structured average intersection-over-union ratio (STRUCT-IOU), a similarity metric between constituency parse trees motivated by the problem of evaluating speech parsers. STRUCT-IOU enables comparison between a constituency parse tree (over automatically recognized spoken word boundaries) with the ground-truth parse (over written words). To compute the metric, we project the ground-truth parse tree to the speech domain by forced alignment, align the projected ground-truth constituents with the predicted ones under certain structured constraints, and calculate the average IOU score across all aligned constituent pairs. STRUCT-IOU takes word boundaries into account and overcomes the challenge that the predicted words and ground truth may not have perfect one-to-one correspondence. Extending to the evaluation of text constituency parsing, we demonstrate that STRUCT-IOU can address token-mismatch issues, and shows higher tolerance to syntactically plausible parses than PARSEVAL (Black et al., 1991).
BibTeX
@inproceedings{shi2024structured,
  author = {Freda Shi and Kevin Gimpel and Karen Livescu},
  title = {{Structured Tree Alignment for Evaluation of (Speech) Constituency Parsing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2024},
  url = {https://openreview.net/forum?id=IZVUispWXe},
}

Loading related content...

Figure