A Message-Passing Control Structure for Text Understanding

Brian Phillips, James A. HendlerCOLING 1982

TL;DR

This paper introduces a novel object-oriented, message-passing control structure for natural language text understanding. It tackles the computational explosion in current systems by enabling early selection of appropriate linguistic and semantic alternatives through mutual access between knowledge sources.

What Problem Does This Paper Address?

As natural language understanding systems aim for broader syntactic and conceptual coverage, the computational effort required to search vast knowledge spaces grows exponentially. Existing systems often struggle to manage this complexity, leading to inefficient processing. The authors address this by proposing a control structure that allows syntactic and semantic modules to communicate dynamically, enabling them to resolve ambiguities early and prune unnecessary search paths. This approach aims to build a conceptual representation of the text concurrently with syntactic analysis, allowing semantic predictions to inform syntax, a departure from systems where semantics merely critiques syntax.

Methods

The core of the paper is an object-oriented, message-passing system, inspired by pseudo-parallel computation models. In this system, "objects" encapsulate data and operations, and communication occurs exclusively through sending messages. This allows for a more flexible control flow than traditional stack-based subprogram activation.

Key methodological components include:

  • Object-Oriented Design: The system is built around objects representing linguistic and semantic components (e.g., constituency objects for syntax, taxonomy objects for semantics).
  • Message Passing: Objects communicate by sending messages, which can be processed directly, or trigger further message passing to other objects. Objects don't necessarily expect a reply, and can maintain state between activations.
  • "Local Grammar" Formalism: For syntax, the paper uses a "local grammar" approach, which is a context-free phrase structure grammar augmented with blocking and percolation rules. This allows for flexible rule application and feature propagation.
  • Modified Left-Corner Parsing: The parsing algorithm is a variation of the left-corner routine, adapted to leverage the object environment for parallel parsing and merging of common subparses.
  • Semantic Network: General domain knowledge is represented in a semantic network where nodes are objects with associated processes dependent on their links. This allows for flexible querying and instantiation of knowledge.
  • Translator Object: A dedicated translator object mediates between syntax and semantics, matching syntactic constituents against semantic predictions and using the semantic network to resolve ambiguities.

Datasets

The paper uses "working abstracts of descriptions of Texas Instruments' issued patents." These texts are chosen for their restricted style and limited domain (solid-state micro-electronic devices), which helps mitigate problems of incomplete syntactic and conceptual coverage. No new benchmarks are introduced; the focus is on the control structure's application to naturally occurring data within this specific domain.

Key Insights and Ideas

  • Combinatorial Implosion: The system aims to achieve "combinatorial implosion" by allowing syntax and semantics to interact dynamically. This means that by building the conceptual representation in parallel with syntactic analysis and feeding semantic predictions back to syntax, the system can prune search spaces early.
  • Mutual Access for Early Resolution: The core idea is that syntactic and semantic knowledge sources should have mutual access. This allows for early selection of appropriate linguistic alternatives, significantly reducing computational overhead compared to systems that perform full syntactic analysis before semantic interpretation.
  • Autonomy of Linguistic Facets: The design aims to incorporate multiple facets of linguistic structure while maintaining their descriptive autonomy, a criterion not met by some other search-constraining methods.
  • Bidirectional Information Flow: Unlike systems where semantics only critiques syntax, this approach allows semantic predictions to be fed to syntax, creating a more integrated and efficient understanding process.
  • Object-Centric Knowledge Representation: The semantic network is implemented as a collection of objects, where nodes have associated processes. This makes the knowledge base more active and responsive to messages, rather than just passive data.

Key Results

The paper describes the system's architecture and approach rather than presenting quantitative results from extensive experiments. The key "result" is the proposed control structure itself and its theoretical advantages:

  • Reduced Computational Effort: The message-passing and early disambiguation mechanisms are designed to significantly reduce the computational effort associated with searching large knowledge spaces in text understanding.
  • Flexible Conceptual Representation: The system aims to build a conceptual representation that allows for more flexible retrieval than simple word-matching schemes.
  • Handling Ambiguity: The interaction between syntax and semantics, particularly through the translator object and semantic network, is shown to resolve syntactic ambiguities (e.g., attachment ambiguities) by leveraging domain knowledge.

Limitations and Future Work

  • Limited Domain: The system's application is currently restricted to the domain of Texas Instruments' patent abstracts. The authors acknowledge that extending this to more general domains would present significant challenges due to incomplete syntactic and conceptual coverage.
  • Pseudo-Parallelism: While inspired by parallel processing, the system is described as "pseudo-parallel," implying that true parallelism might not be fully realized in the current implementation.
  • Future Work: The authors suggest that further developments in natural language understanding and cognitive processes, along with advances in hardware and specialized machines, will contribute to building more viable natural language systems. They emphasize the importance of choosing the right approach, such as their object-oriented system, to avoid wasting computational power.

Summary updated

BibTeX
@inproceedings{phillips1982message,
  author = {Brian Phillips and James A. Hendler},
  title = {{A Message-Passing Control Structure for Text Understanding}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1982},
}
Figure