Head-driven Phrase Structure Parsing in O($n^3$) Time Complexity

• URL: http://arxiv.org/abs/2105.09835v1
• Date: Thu, 20 May 2021 15:33:51 GMT
• Title: Head-driven Phrase Structure Parsing in O($n^3$) Time Complexity
• Authors: Zuchao Li, Junru Zhou, Hai Zhao, Kevin Parnow
• Abstract summary: 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. We propose an improved head scorer that helps achieve a novel performance-preserved in $O$($n3$) time complexity.
• Score: 48.683350567504604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• A Fundamental Algorithm for Dependency Parsing (With Corrections) [0.0]
  This paper presents a fundamental algorithm for parsing natural language sentences into dependency trees.<n>Unlike phrase-structure parsing, this algorithm operates one word at a time, attaching each word as soon as it can be attached.
  arXiv  Detail & Related papers  (2025-10-22T19:48:38Z)
• An Attempt to Develop a Neural Parser based on Simplified Head-Driven Phrase Structure Grammar on Vietnamese [1.4990724156326336]
  Existing Vietnamese corpora did not adhere to simplified Head-Driven Phrase Structure Grammar rules. We modified the first Penn Treebank by replacing it with the PhoBERT or XLM-Roa models, which can encode Vietnamese texts. Our experiments showed that the simplified HPSG Neural corpora achieved a new state-of-the-art F-score of 82% for constituency parsing.
  arXiv  Detail & Related papers  (2024-11-26T09:46:32Z)
• Cross-domain Chinese Sentence Pattern Parsing [67.1381983012038]
  Sentence Pattern Structure (SPS) parsing is a syntactic analysis method primarily employed in language teaching. Existing SPSs rely heavily on textbook corpora for training, lacking cross-domain capability. This paper proposes an innovative approach leveraging large language models (LLMs) within a self-training framework.
  arXiv  Detail & Related papers  (2024-02-26T05:30:48Z)
• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  This study on a neuro-symbolic architecture called the Compositional Program Generator (CPG) CPG has three key features: textitmodularity, textitcomposition, and textitabstraction, in the form of grammar rules. It perfect achieves generalization on both the SCAN and COGS benchmarks using just 14 examples for SCAN and 22 examples for COGS.
  arXiv  Detail & Related papers  (2023-09-28T14:33:20Z)
• Hexatagging: Projective Dependency Parsing as Tagging [63.5392760743851]
  We introduce a novel dependency, the hexatagger, that constructs dependency trees by tagging the words in a sentence with elements from a finite set of possible tags. Our approach is fully parallelizable at training time, i.e., the structure-building actions needed to build a dependency parse can be predicted in parallel to each other. We achieve state-of-the-art performance of 96.4 LAS and 97.4 UAS on the Penn Treebank test set.
  arXiv  Detail & Related papers  (2023-06-08T18:02:07Z)
• Schema-Free Dependency Parsing via Sequence Generation [33.58097441488377]
  Dependency parsing aims to extract syntactic dependency structure or semantic dependency structure for sentences. We propose to achieve universal and schema-free Dependency Parsing (DP) via Sequence Generation (SG)
  arXiv  Detail & Related papers  (2022-01-28T20:32:04Z)
• Span-based Semantic Parsing for Compositional Generalization [53.24255235340056]
  SpanBasedSP predicts a span tree over an input utterance, explicitly encoding how partial programs compose over spans in the input. On GeoQuery, SCAN and CLOSURE, SpanBasedSP performs similarly to strong seq2seq baselines on random splits, but dramatically improves performance compared to baselines on splits that require compositional generalization.
  arXiv  Detail & Related papers  (2020-09-13T16:42:18Z)
• A Simple Global Neural Discourse Parser [61.728994693410954]
  We propose a simple chart-based neural discourse that does not require any manually-crafted features and is based on learned span representations only. We empirically demonstrate that our model achieves the best performance among globals, and comparable performance to state-of-art greedys.
  arXiv  Detail & Related papers  (2020-09-02T19:28:40Z)
• SPARQA: Skeleton-based Semantic Parsing for Complex Questions over Knowledge Bases [27.343078784035693]
  We propose a novel skeleton grammar to represent the high-level structure of a complex question. This dedicated coarse-grained formalism with a BERT-based parsing algorithm helps to improve the accuracy of the downstream fine-grained semantic parsing. Our approach shows promising performance on several datasets.
  arXiv  Detail & Related papers  (2020-03-31T05:12:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.