Abstract
General treebank analyses are graph structured, but parsers are typically restricted to tree structures for efficiency and modeling reasons. We propose a new representation and algorithm for a class of graph structures that is flexible enough to cover almost all treebank structures, while still admitting efficient learning and inference. In particular, we consider directed, acyclic, one-endpoint-crossing graph structures, which cover most long-distance dislocation, shared argumentation, and similar tree-violating linguistic phenomena. We describe how to convert phrase structure parses, including traces, to our new representation in a reversible manner. Our dynamic program uniquely decomposes structures, is sound and complete, and covers 97.3% of the Penn English Treebank. We also implement a proof-of-concept parser that recovers a range of null elements and trace types.- Anthology ID:
- Q17-1031
- Volume:
- Transactions of the Association for Computational Linguistics, Volume 5
- Month:
- Year:
- 2017
- Address:
- Cambridge, MA
- Editors:
- Lillian Lee, Mark Johnson, Kristina Toutanova
- Venue:
- TACL
- SIG:
- Publisher:
- MIT Press
- Note:
- Pages:
- 441–454
- Language:
- URL:
- https://aclanthology.org/Q17-1031
- DOI:
- 10.1162/tacl_a_00072
- Cite (ACL):
- Jonathan K. Kummerfeld and Dan Klein. 2017. Parsing with Traces: An O(n4) Algorithm and a Structural Representation. Transactions of the Association for Computational Linguistics, 5:441–454.
- Cite (Informal):
- Parsing with Traces: An O(n4) Algorithm and a Structural Representation (Kummerfeld & Klein, TACL 2017)
- PDF:
- https://preview.aclanthology.org/ingest-acl-2023-videos/Q17-1031.pdf