A generalized transition framework for identifying reduction domains in non-binary constituency parsing
Organizations: KAIST South Korea · UBC Canada
Abstract
Direct non-binary constituency parsing must identify an ordered sequence of children at each phrase-level reduction. We extend our earlier delimiter-guided bottom-up construction to a common calculus for top-down, in-order, and bottom-up parsing. At reduction, the rightmost delimiter marks the left boundary, the nonterminal marker supplies the mother label, and the completed items in the delimited segment determine the children and arity. We use a stack invariant to prove soundness and completeness and derive the exact length of the static oracle's action sequence. A projection-and-lifting theorem shows that each delimiter-guided system and its canonical counterpart generate the same set of trees under both the structural and grammar-licensed transition relations. In controlled experiments on PTB and CTB, the delimiter-guided parsers achieve similar labeled accuracy to their canonical counterparts across all traversal orders. For bottom-up parsing, delimiter guidance reduces the number of action classes and increases the number of supervised decisions per tree.
Figures & tables
| PTB | CTB | |||
| System | evalb | jp-evalb | evalb | jp-evalb |
| Previously reported canonical non-binary systems | ||||
| Top-down ( Dyer et al., 2016 ) | 92.40 | — | 82.70 | — |
| In-order ( Liu and Zhang, 2017a ) | 91.80 | — | 86.10 | — |
| Bottom-up ( Fernández-González and Gómez-Rodríguez, 2019 ) | 91.70 | — | 86.80 | — |
| Canonical non-binary systems, reimplemented | ||||
| PTB | CTB | |||||
| Order | Classes | Actions | MACs (M) | Classes | Actions | MACs (M) |
| Canonical | ||||||
| Top-down | 79 | 110.04 | 17.21 | 65 | 122.15 | 18.67 |
| In-order | 79 | 110.04 | 17.21 | 65 | 122.15 | 18.67 |
| Bottom-up | 251 | 67.25 | 13.48 | 227 | 73.08 | 14.20 |
| Delimiter-guided | ||||||
| PTB | CTB | |||
|---|---|---|---|---|
| Order | Canonical | Delimiter-guided | Canonical | Delimiter-guided |
| Top-down | ||||
| In-order | ||||
| Bottom-up | ||||
| System | |||||
|---|---|---|---|---|---|
| PTB | |||||
| Gold count | 8,879 | 23,840 | 7,381 | 2,317 | 1,859 |
| C Top-down | |||||
| C In-order | |||||
| C Bottom-up | |||||
| D Top-down | |||||
| System | 1–10 | 11–20 | 21–30 | 31–40 | |
|---|---|---|---|---|---|
| PTB | |||||
| Sentences | 270 | 764 | 778 | 433 | 171 |
| C Top-down | |||||
| C In-order | |||||
| C Bottom-up | |||||
| D Top-down | |||||
| PTB | CTB | |||||
|---|---|---|---|---|---|---|
| Order | Same | D higher | C higher | Same | D higher | C higher |
| Top-down | ||||||
| In-order | ||||||
| Bottom-up | ||||||
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Step | Top-down | In-order | Bottom-up |
|---|---|---|---|
| 1 | Nt (TOP) | d-Shift (Ms.) | d-Shift (Ms.) |
| 2 | Nt (S) | Nt (NNP) | Nt (NNP) |
| 3 | Nt (NP 1 ) | u-Reduce | u-Reduce |
| 4 | Nt (NNP) | Nt (NP 1 ) | Shift (Haag) |
| 5 | Shift (Ms.) | Shift (Haag) | Nt (NNP) |
| 6 | u-Reduce | Nt (NNP) | u-Reduce |