TL;DR
This paper introduces a unified transition framework for non-binary constituency parsing that uses "delimiters" to explicitly mark constituent boundaries on the stack. By identifying the "reduction domain" via these delimiters, the authors eliminate the need for arity-specific actions in bottom-up parsing, significantly simplifying the action space while maintaining competitive accuracy across top-down, in-order, and bottom-up traversal orders.
What Problem Does This Paper Address?
Constituency parsing involves breaking a sentence into nested hierarchical groups (phrases). While many parsers "binarize" these trees (limiting each node to two children), direct non-binary parsing is more linguistically natural but computationally trickier.
The main challenge lies in "reduction": knowing when and how many children to group into a parent phrase. In traditional bottom-up systems, the parser must predict an action like REDUCE-NP#3 (meaning "reduce the top 3 items into an NP"). This requires the model to learn a separate action for every possible combination of label and "arity" (number of children), leading to a massive, sparse action space. While top-down and in-order systems use markers to help, there hasn't been a common mathematical framework that unifies all three traversal orders without relying on arity as a hard-coded parameter.
Methods
The authors propose a delimiter-guided calculus. Instead of the action itself carrying the "count" of children, the parser places a special symbol—a delimiter ($D$)—on the stack to mark the left boundary of a potential phrase.
- The Delimiter ($D$): Acts as a "bookmarker" for the start of a constituent.
- The Marker ($nt(X)$): Supplies the non-terminal label (e.g., VP, NP).
- Unified Reduction: When a reduction occurs, the parser simply looks back to the rightmost delimiter. Everything between that delimiter and the marker is identified as the "reduction domain" (the children).
The paper provides a formal proof of soundness and completeness using stack invariants. They also introduce a "projection-and-lifting" theorem, proving that these delimiter-guided systems are mathematically equivalent to their canonical counterparts—they generate the exact same set of trees.
Datasets
The researchers evaluated their framework on two standard benchmarks:
- Penn Treebank (PTB): The gold standard for English constituency parsing.
- Chinese Treebank (CTB) 5.1: A widely used benchmark for Chinese parsing.
They compared their delimiter-guided versions against "canonical" (standard) implementations of top-down, in-order, and bottom-up parsers.
Key Insights and Ideas
- Arity is an Emergent Property: The most significant "aha moment" is that the number of children (arity) doesn't need to be a predicted parameter. If you know where a phrase starts (the delimiter) and where it ends, the arity is simply the number of completed items in between.
- Action Space Simplification: For bottom-up parsing, this approach collapses the action space. Instead of learning hundreds of
REDUCE-LABEL#ARITYcombinations, the model only needs to learn a small set of labels. On the PTB, this reduced the number of action classes from 251 down to 82. - Structural vs. Grammar Licensing: The authors distinguish between "structural" rules (how the stack is manipulated) and "grammar" rules (whether a specific tree is valid according to a treebank). This allows them to prove the system works for any projective tree, regardless of the specific grammar.
Key Results
- Accuracy Parity: The delimiter-guided parsers achieved nearly identical labeled F1 scores to canonical systems. On PTB, the differences were within 0.11 points for top-down and 0.07 for bottom-up.
- Efficiency Trade-off: While the action space is smaller, the derivations are longer because the parser takes more steps (e.g., explicitly placing delimiters and markers). For bottom-up parsing, the number of decisions per tree increased by roughly 64-67%.
- Decoding Speed: Because of the longer derivations and the need to scan the stack for delimiters, the delimiter-guided bottom-up parser was about 9-15% slower than the canonical version. However, top-down and in-order speeds remained largely unaffected.
Limitations and Future Work
- Speed: The increased number of steps per tree is a clear trade-off. Future work could investigate if the simplified action space allows for smaller, faster neural scorers that might offset this overhead.
- Greedy Search: The experiments used greedy decoding. Exploring how this framework interacts with beam search or dynamic oracles could provide further insights into its robustness.
- Beyond Projectivity: The current framework assumes projectivity (no crossing branches). Extending this to non-projective structures would be a significant next step for languages with freer word order.
Summary updated