Introduction
Syntactic parsing is a cornerstone of natural language processing, aiming to uncover the structural relationships within sentences. While standard constituent parsing often assumes a nested, non-overlapping structure, many languages—particularly those with flexible word order like German—exhibit "discontinuous" constituents. These structures involve phrases whose components are separated by other words, leading to crossing branches in traditional tree representations.
In their AAAI-20 paper, "Discontinuous Constituent Parsing with Pointer Networks," Daniel Fernández-González and Carlos Gómez-Rodríguez propose a novel neural architecture that addresses this complexity. By reframing discontinuous constituent parsing as a non-projective dependency parsing task and leveraging Pointer Networks, they achieve state-of-the-art results on challenging benchmarks.
The Challenge of Discontinuity
Traditional constituent parsing groups words into hierarchical phrases (e.g., Noun Phrases, Verb Phrases). However, standard Context-Free Grammars (CFGs) are restricted to projective trees where branches do not cross. Discontinuous constituent trees, while more linguistically expressive, are significantly harder to parse. More complex formalisms like Linear Context-Free Rewriting Systems (LCFRS) exist but are computationally expensive and often too slow for practical use.
As shown in the figure above, a discontinuous tree (a) can be mapped to a dependency-like structure (c). The authors' key insight is to exploit this relationship, using the efficiency of dependency parsing algorithms to solve the more complex constituent problem.
Proposed Methodology: Spines and Pointer Networks
The core of the proposed approach is a three-pillar strategy that transforms constituent trees into a format manageable by neural dependency parsers.
1. Augmented Dependency Representation
The authors decompose the constituent tree into "spines" (vertical paths from a word to its highest ancestor in the tree). The interactions between these spines are then modeled as dependency arcs. To preserve the full hierarchical information of the original constituent tree, these arcs are "augmented" with labels that include non-terminal symbols and attachment orders (e.g., NP#1, S#1).
2. Pointer Network Architecture
Pointer Networks are uniquely suited for this task because they can select positions from an input sequence of arbitrary length. For each word in a sentence, the network "points" to its most likely head word. This mechanism is inherently capable of handling non-projective (crossing) arcs, which are necessary for representing discontinuities.
3. Multi-Task Learning
The model employs a Bi-LSTM-CNN encoder to capture both character-level and word-level features. A unidirectional LSTM decoder then generates hidden states for each word. The system uses a biaffine attention mechanism to perform two tasks simultaneously:
- The Parser: Predicts the probability of a dependency arc between words.
- The Labeler: Predicts the augmented label for each predicted arc.
Jointly training these components allows the model to learn the intricate relationship between syntactic structure and phrase labels in a single stage, avoiding the error propagation common in two-stage pipelines.
Experimental Results
The model was evaluated on the NEGRA and TIGER German treebanks, both of which are known for high rates of discontinuity (over 25%).
| Dataset | Metric | Previous SOTA | This Work |
|---|---|---|---|
| NEGRA | F1 Score | 83.2 | 85.4 |
| TIGER | F1 Score | 82.5 | 85.3 |
Notably, the model achieved these results even without the use of Part-of-Speech (POS) tags, demonstrating the strength of the Bi-LSTM-CNN encoder. On the specific task of identifying discontinuous constituents, the model saw a significant jump in performance (e.g., from 56.3 to 58.8 F1 on NEGRA), proving its effectiveness at "untangling" complex linguistic structures.
Conclusion and Future Work
By combining spine-based decomposition with the flexibility of Pointer Networks, Fernández-González and Gómez-Rodríguez have provided a highly efficient and accurate solution for discontinuous constituent parsing. While the current representation struggles with rare unary nodes, the approach's success on German benchmarks suggests it is a powerful tool for parsing languages with flexible word orders. Future research may explore integrating this architecture with semi-supervised learning or re-ranking techniques to further push the boundaries of syntactic analysis.
Reference: Fernández-González, D., & Gómez-Rodríguez, C. (2020). Discontinuous Constituent Parsing with Pointer Networks. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7724-7731.
Summary updated