Ordered Tree Decomposition for HRG Rule Extraction

Daniel Gildea, Giorgio Satta, Xiaochang Peng


Abstract
We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the problem of finding optimal tree decompositions for a graph is NP-hard. We also present polynomial-time algorithms for parsing based on our HRGs, where the input is a vertex sequence and the output is a graph structure. The intended application of our algorithms is grammar extraction and parsing for semantic representation of natural language. We apply our algorithms to data annotated with Abstract Meaning Representations and report on the characteristics of the resulting grammars.
Anthology ID:
J19-2005
Volume:
Computational Linguistics, Volume 45, Issue 2 - June 2019
Month:
June
Year:
2019
Address:
Cambridge, MA
Venue:
CL
SIG:
Publisher:
MIT Press
Note:
Pages:
339–379
Language:
URL:
https://aclanthology.org/J19-2005
DOI:
10.1162/coli_a_00350
Bibkey:
Cite (ACL):
Daniel Gildea, Giorgio Satta, and Xiaochang Peng. 2019. Ordered Tree Decomposition for HRG Rule Extraction. Computational Linguistics, 45(2):339–379.
Cite (Informal):
Ordered Tree Decomposition for HRG Rule Extraction (Gildea et al., CL 2019)
Copy Citation:
PDF:
https://preview.aclanthology.org/author-url/J19-2005.pdf