TL;DR
This paper presents a novel approach to parsing Enhanced Universal Dependencies (EUD) graphs by splitting them into multiple linguistic-based trees. These trees are then parsed using a sequence-labeling parser, and the results are collated to reconstruct the original EUD graph. While the system's performance was not top-tier, it offers an interesting exploration into applying sequence labeling to graph parsing and highlights the challenges of accurately labeling complex dependency structures.
What Problem Does This Paper Address?
Enhanced Universal Dependencies (EUD) represent linguistic dependencies as graphs, which can be more expressive than traditional tree structures but also more complex to parse. Existing parsing methods often struggle with the richness and potential non-projectivity of these graphs. The authors aim to simplify the parsing of EUD graphs by breaking them down into smaller, more manageable tree structures that can be handled by sequence-labeling parsers, a technique that has proven successful for tree-based parsing but has not been widely applied to graph parsing. They also explore whether splitting graphs based on linguistic criteria, rather than purely algorithmic ones, can lead to better learning of dependency relationships.
Methods
The core of the proposed method involves splitting an EUD graph into four distinct trees:
- Basic Tree: This tree primarily consists of edges that directly correspond to Universal Dependencies (UD) edges, with a modification for relative position of lemmas.
- Relative Clause Tree: This tree is derived from the basic tree by replacing incoming edges to nodes with "ref" edges, specifically targeting relative clauses.
- Conjunct Tree: This tree is created by replacing "conj" edges in the basic tree with their corresponding EUD column edges.
- Control Tree: This tree modifies the basic tree by replacing "nsubj" edges with alternative "nsubj" edges when a node's head has an "xcomp" or "ccomp" edge.
Crucially, these trees are not necessarily disjoint and can overlap. The system then uses a sequence-labeling parser (a BiLSTM network with word and character embeddings) to predict each of these tree types independently. Finally, a simple collating procedure combines the predicted edges from all four trees to reconstruct the EUD graph. The authors note that cycle detection and resolution (using the Chu-Liu-Edmonds algorithm) are incorporated at various stages.
Datasets
The paper evaluates its approach on EUD treebanks from various languages, as indicated by the tables and figures showing performance across different treebanks (e.g., ar-padt, bg-btb, cs-cac, en-ewt, etc.). The specific datasets are not explicitly listed as a separate section but are implied to be standard EUD treebanks used in the IWPT 2021 Shared Task.
Key Insights and Ideas
- Sequence Labeling for Graph Parsing: The paper pioneers the application of sequence-labeling parsing techniques to graph-based dependency parsing, opening up new avenues for research in this area.
- Linguistic-Based Splitting: The authors hypothesize that splitting graphs into linguistically meaningful components (like relative clauses or conjuncts) might facilitate joint learning of different dependency types, a strategy that has shown promise in other NLP tasks.
- Trade-off Between Structure and Labeling: The results suggest that while the system can effectively predict the underlying graph structure (high UAS scores), accurately labeling the edges remains a significant challenge (lower LAS scores). This points to the complexity of EUD edge labels, especially when dealing with relative positional encoding for case marking.
- Collator Simplicity: The collating procedure is described as "egregiously simple," highlighting a potential area for improvement. The naive approach of taking unique edges and prioritizing labels from the basic tree might lead to issues.
Key Results
- The system achieved relatively poor overall results, with the authors describing them as "not a total disaster."
- Figure 7 shows that the average performance of parsers trained on individual tree types (basic, conjunct, control, relative) is quite stable, with scores around 80-90% for UAS and LAS.
- Table 3 indicates that when collating the predicted trees back into EUD graphs, the average scores drop significantly, with UAS around 86.66, EULAS around 72.02, and ELAS around 69.21.
- Figure 8 and Table 4 provide a detailed breakdown of performance across different treebanks, consistently showing higher UAS (graph structure) than LAS (labeled dependencies). For instance, the average UAS is around 91.22, while the average LAS is around 72.02.
- The authors note that their system was the second-to-last overall in the full treebank set.
Limitations and Future Work
- Mistake in Relative Tree Splitting: The authors acknowledge a mistake in their implementation of the relative tree split, where they lost certain "REF" edges. This error likely impacted performance.
- Naive Collator: The collating procedure is identified as a limitation. Future work could involve more sophisticated collators, potentially considering only edges relevant to the specific phenomenon of a given tree type.
- Higher-Order Edges: The current method cannot capture higher-order edges, and attempts to use a "SWEEP tree" for this purpose were cut short by time constraints.
- Labeling Complexity: The significant gap between UAS and LAS suggests that accurately labeling EUD edges is a major challenge. The use of relative positional encoding for case marking is suspected to contribute to this difficulty.
- Further Exploration: The authors suggest that separating relative case marking from relation labels and treating it as a separate task in a multi-task learning system could be a promising direction. They also mention exploring other tree-splitting strategies.
Summary updated