Abstract
Sequence tagging models for constituent parsing are faster, but less accurate than other types of parsers. In this work, we address the following weaknesses of such constituent parsers: (a) high error rates around closing brackets of long constituents, (b) large label sets, leading to sparsity, and (c) error propagation arising from greedy decoding. To effectively close brackets, we train a model that learns to switch between tagging schemes. To reduce sparsity, we decompose the label set and use multi-task learning to jointly learn to predict sublabels. Finally, we mitigate issues from greedy decoding through auxiliary losses and sentence-level fine-tuning with policy gradient. Combining these techniques, we clearly surpass the performance of sequence tagging constituent parsers on the English and Chinese Penn Treebanks, and reduce their parsing time even further. On the SPMRL datasets, we observe even greater improvements across the board, including a new state of the art on Basque, Hebrew, Polish and Swedish.
Introduction
Constituent parsing—the process of breaking a sentence into nested hierarchical phrases—is a fundamental NLP task. Traditionally, this is achieved using chart-based or shift-reduce parsers. While accurate, these methods are often computationally expensive. A faster alternative is sequence tagging, where the parser assigns a single label to each word to represent its position in the tree. However, sequence tagging parsers historically suffer from three major flaws: closing bracket errors in long phrases, label sparsity due to complex tags, and error propagation from greedy decoding.
Methods: Better, Faster, Stronger
Dynamic Encodings (Better)
Standard sequence tagging often uses "relative" indexing to track tree depth, which can become problematic for deep trees. We introduce a secondary "top-down absolute" scheme and train the model to dynamically switch between the two based on which is more efficient for the current word. This flexibility allows the model to handle both short, simple phrases and long, complex constituents effectively.
Multi-task Learning (Faster)
To combat label sparsity, we decompose complex tags into separate sub-tasks. Instead of predicting one massive tag (e.g., "3 levels up, Noun Phrase, Unary branch"), the model jointly learns to predict three separate components. This Multi-task Learning (MTL) approach reduces the size of the output layer, making the model easier to train and increasing parsing speed by 1.17x due to faster softmax calculations.
Mitigating Greedy Decoding (Stronger)
We address error propagation through two primary techniques:
- Auxiliary Tasks: The model is forced to predict "syntactic distances" (a global measure of tree structure) as a side-task, providing the local tagger with broader structural context.
- Policy Gradient Fine-tuning: We use the REINFORCE algorithm to fine-tune the model. Instead of just minimizing token-level errors, the model is rewarded for improving the overall F-score of the entire tree.
Key Results and Insights
The proposed framework achieves an F-score of 91.67 on the English Penn Treebank (PTB), clearly surpassing previous sequence tagging benchmarks. A key driver of this improvement is the dynamic encoding scheme, which significantly reduces errors at lower tree levels (closing brackets).
Beyond English, the system set new state-of-the-art (SOTA) records for Basque, Hebrew, Polish, and Swedish within the SPMRL framework. The parser is remarkably efficient, processing 130 sentences per second on a single CPU. When optimized on a GPU, it reaches a staggering 1,267 sentences per second, making it one of the fastest high-accuracy parsers available.
Conclusion
By reinvigorating sequence tagging with dynamic encodings, multi-task learning, and reinforcement learning, we demonstrate that constituent parsing can be both highly accurate and exceptionally fast. While the use of pre-trained embeddings like BERT could further boost accuracy, the current model provides a superior balance of speed and performance for real-time applications.
Summary updated