A Flexible Example-Based Parser Based on the SSTC

Mosleh Hmoud Al-Adhaileh, Enya Kong TangCOLING 1998

TL;DR

This paper introduces a novel example-based parsing approach for natural language that leverages a flexible annotation schema called Structured String-Tree Correspondence (SSTC). This method aims to overcome limitations of traditional rule-based parsers and existing example-based systems by effectively handling complex linguistic phenomena like featurization, lexicalization, and crossed dependencies, paving the way for more robust and adaptable NLP applications.

What Problem Does This Paper Address?

Parsing natural language sentences into a structured representation (like a phrase structure tree) is a fundamental task in Natural Language Processing (NLP). Traditional approaches often rely on hand-crafted grammar rules, which can be brittle and difficult to maintain, especially when dealing with the nuances and complexities of human language. While example-based approaches offer an alternative by learning from existing parsed sentences, they often struggle with flexibility. Specifically, existing methods can be restrictive in how they map sentence components to tree structures, often requiring one-to-one correspondences and limiting their ability to represent phenomena like:

  • Featurization: Where a linguistic element (e.g., a particle like "up" in "picks up") is not represented as a separate node but as a feature of another word (the verb "pick").
  • Lexicalization: Where a subtree represents the meaning of a part of the string that isn't explicitly phonologically realized, or where one part of the string maps to multiple nodes.
  • Crossed Dependencies: Where words in a sentence that correspond to a single subtree are not contiguous, leading to intertwined dependencies.

These limitations hinder the development of large-scale, practical example-based NLP systems.

Methods

The core of this paper is the Structured String-Tree Correspondence (SSTC) annotation schema. SSTC is designed to be a flexible way to represent parsed sentences. For each example sentence, SSTC captures:

  1. The sentence itself.
  2. Its representation tree (e.g., a dependency tree).
  3. The correspondence between substrings of the sentence and subtrees within the representation tree.

Crucially, SSTC allows for non-projective correspondences, meaning substrings can map to discontinuous subtrees, and vice-versa. This is achieved by defining correspondences between nodes and substrings, and between subtrees and substrings, allowing for potentially discontinuous mappings.

The parsing process itself is example-based:

  1. Bottom-Up Subtree Construction: For an input sentence, the system first attempts to build subtrees for phrases that have direct matches in the example-base.
  2. Top-Down Tree Assembly: These subtrees are then combined to form a single, rooted representation tree. This combination is guided by an example with a similar overall representation structure.
  3. Knowledge Index: A knowledge index is built from the example-base, storing information about each word (e.g., example number, frequency, syntactic category, type, parent category, position).
  4. Substitutions Generation and Combination: The system generates "substitutions" (partial SSTCs) for the input sentence based on the knowledge index. These substitutions are then combined, using a distance calculation (based on edit operations like insertion and deletion) to find the most plausible example to use as a base for constructing the final SSTC.

Datasets

Not discussed in the paper. The paper describes a method that relies on an "example-base" of already parsed sentences, but does not specify any particular corpus or benchmark dataset used for training or evaluation.

Key Insights and Ideas

  • SSTC as a Flexible Bridge: The SSTC schema is the central innovation, providing a unified way to represent sentences, their structures, and the complex mappings between them, explicitly designed to handle non-projective phenomena.
  • Learning from "Close" Examples: The core assumption is that if two sentences are "close" (semantically or structurally), their analyses should also be "close." This allows for adapting existing parsed structures to new sentences with modifications.
  • Handling Linguistic Complexity: The paper demonstrates how SSTC can effectively represent featurization, lexicalization, and crossed dependencies, which are challenging for more rigid parsing formalisms.
  • Example-Based Parsing as a Viable Alternative: By focusing on flexibility and a structured annotation scheme, the paper argues for the practical applicability of example-based parsing beyond simple cases.

Key Results

The paper presents a schema and an algorithm overview. It illustrates the concepts with examples, such as parsing the sentence "the old man picks the green lamp up" using a hypothetical example-base. The results are qualitative, demonstrating how the SSTC and the proposed parsing steps can generate a representation tree that accounts for the linguistic phenomena discussed. No quantitative results (e.g., accuracy scores, parsing speed) are provided.

Limitations and Future Work

The authors acknowledge several areas for further development:

  • Handling Multiple Substitutions: The current approach needs further work on efficiently managing and combining multiple substitutions, especially when they overlap.
  • Efficient Distance Calculation: Developing a more efficient method for calculating the distance between the input sentence and examples is crucial for scalability.
  • Detailed Formula for SSTC Computation: A precise formula is needed for computing the final SSTC, particularly when optional substitutions are involved and need to be handled (e.g., deleted).
  • Full Parsing Algorithm: The paper outlines the schema and a general algorithm but states that a "full version" of the parsing algorithm requires further consideration of these points.

Summary updated

BibTeX
@inproceedings{aladhaileh1998flexible,
  author = {Mosleh Hmoud Al-Adhaileh and Enya Kong Tang},
  title = {{A Flexible Example-Based Parser Based on the SSTC}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1998},
}

Loading related content...

Figure