Head-driven Phrase Structure Parsing in O($n^3$) Time Complexity
This work addresses a computational bottleneck for researchers and practitioners in natural language processing by making HPSG parsing more efficient, though it is incremental as it builds on existing joint parsing methods.
The paper tackled the high time complexity of decoding Head-driven Phrase Structure Grammar (HPSG) for syntactic parsing, which was O(n^5), by proposing an improved head scorer to achieve a parser with O(n^3) time complexity while preserving performance.
Constituent and dependency parsing, the two classic forms of syntactic parsing, have been found to benefit from joint training and decoding under a uniform formalism, Head-driven Phrase Structure Grammar (HPSG). However, decoding this unified grammar has a higher time complexity ($O(n^5)$) than decoding either form individually ($O(n^3)$) since more factors have to be considered during decoding. We thus propose an improved head scorer that helps achieve a novel performance-preserved parser in $O$($n^3$) time complexity. Furthermore, on the basis of this proposed practical HPSG parser, we investigated the strengths of HPSG-based parsing and explored the general method of training an HPSG-based parser from only a constituent or dependency annotations in a multilingual scenario. We thus present a more effective, more in-depth, and general work on HPSG parsing.