A Corpus-Based Learning Technique for Building A Self-Extensible Parser

Rey-Long Liu, Von-Wun SooCOLING 1994

TL;DR

This paper introduces SEP, a novel technique for automatically building parsers that can extend their own knowledge base using only raw sentences. By learning from parsing failures, SEP enables parsers to acquire missing linguistic rules without human intervention or pre-annotated data, paving the way for more scalable natural language acquisition.

What Problem Does This Paper Address?

Building robust natural language parsers requires extensive linguistic knowledge. Traditionally, acquiring this knowledge has relied heavily on human intervention or pre-annotated training corpora, which are costly, time-consuming, and prone to errors and inconsistencies. This bottleneck significantly hinders the scalability of natural language processing systems. Existing methods that attempt to automate this process often depend on heuristics or pre-existing processors, which themselves can become performance limitations. The core challenge this paper addresses is how to enable a parser to learn and acquire new linguistic knowledge autonomously, directly from raw text, without external help.

Methods

The paper proposes a learning technique called SEP (Self-Extensible Parser) that integrates with an existing parser. SEP is triggered when the parser fails to analyze an input sentence. It operates in two main phases:

  • Hypothesis Generation: This phase aims to identify potential missing linguistic rules.
  • Top-Down Phase: SEP uses the parser's existing knowledge to predict missing components of a constituent. For example, if a sentence requires an NP followed by a VP to form an Smaj, and the VP is known but the NP is not, SEP will hypothesize rules for constructing that NP.
  • Bottom-Up Phase: This phase uses the partial results of parsing (constituents that were successfully parsed) to hypothesize missing rules. For instance, if a VP is expected but not found, and an NP is found in its place, SEP might hypothesize a rule where a VP can be constructed from a verb and an NP.
  • Universal Constraints: SEP incorporates linguistic constraints, such as the X-Bar theory's "Three-Components Constraint," to limit the number and types of hypotheses generated, making the process more efficient and grounded.
  • Hypothesis Verification: After generating multiple hypotheses for a given sentence, SEP verifies them. It does this by collecting hypothesis sets from multiple training sentences. If a hypothesis set contains only one hypothesis, it's considered the target missing rule. Otherwise, SEP increments the frequency of each hypothesis and selects the one with the highest frequency across all sets, assuming that frequently generated hypotheses are more likely to be correct.

Datasets

The paper mentions using sentences extracted from an English textbook for training and evaluation. For evaluating the hypothesis verification module, they used a portion of the DJ corpus (Wall Street Journal articles). The size of the DJ corpus used was approximately 32 megabytes. The key difference noted is that SEP only requires raw sentences, unlike other methods that might need pre-processed data.

Key Insights and Ideas

  • Self-Extensibility: The core idea is that a parser can become "self-extensible" by learning from its own failures. This shifts the burden of knowledge acquisition from external sources to the parser itself.
  • Learning from Failure: Instead of treating parsing failures as dead ends, SEP leverages them as opportunities to identify and acquire missing linguistic knowledge.
  • Complementary Top-Down and Bottom-Up Learning: The paper highlights how the top-down and bottom-up phases of hypothesis generation work together, each focusing on different parts of a missing rule, to cover a wider range of learning scenarios.
  • The "Complete-When-One-Missing" Theorem: This theoretical insight suggests that if a parser is missing only one rule to parse a sentence, SEP is guaranteed to generate that rule as a hypothesis. This provides a theoretical basis for the effectiveness of the hypothesis generation process.
  • Frequency-Based Verification: Using hypothesis frequency across multiple sentences is a robust way to disambiguate and select the most likely correct rule when multiple hypotheses are generated.

Key Results

  • Hypothesis Generation Success: SEP successfully generated hypotheses for 55 out of 85 sentences that initially failed parsing. This indicates that the parser was not "too difficult" for SEP to learn from in these cases.
  • Average Hypotheses per Missing Rule: SEP produced an average of 3.67 hypotheses per missing rule that was successfully learned. This suggests that while SEP is effective, it still requires collecting multiple pieces of evidence to confirm a target rule.
  • Efficiency: The method is designed to be fully automatic, requiring only raw sentences, which are readily available, making large-scale acquisition more feasible.

Limitations and Future Work

  • Movement Constructions: The paper acknowledges that SEP, in its current form, cannot learn movement constructions (e.g., "Here comes the dog") because these require detecting structural changes that are not directly apparent in raw sentence analysis without additional cues.
  • Enhancing Constraints: The authors suggest that incorporating more sophisticated universal linguistic constraints could further reduce the number of hypotheses and improve their quality. For example, using X-Bar theory more extensively to filter hypotheses based on the expected roles of constituent components.
  • Integration with Other Frameworks: The authors mention ongoing work to integrate SEP with a framework for syntactic and semantic knowledge acquisition, suggesting a path towards more comprehensive language understanding.
  • Handling Noise: While the paper mentions noise-tolerant learning through multiple observations, the specific impact of noisy input on SEP's performance is an area for further exploration.

Summary updated

BibTeX
@inproceedings{liu1994corpus,
  author = {Rey-Long Liu and Von-Wun Soo},
  title = {{A Corpus-Based Learning Technique for Building A Self-Extensible Parser}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1994},
}
Figure