A Parsing Architecture Based on Distributed Memory Machines

Jon M. SlackCOLING 1984

TL;DR

This paper proposes a novel computational architecture for natural language parsing that leverages "distributed memory machines" (DMMs). These DMMs, inspired by holographic associative memory, store associations as composite vectors, allowing for efficient encoding of complex linguistic constraints. The architecture demonstrates how principles from Lexical Functional Grammar (LFG) can be naturally derived from the properties of these DMMs, offering a new approach to building parsers that integrate syntactic and semantic processing.

What Problem Does This Paper Address?

Parsing natural language, the process of analyzing a sentence to understand its grammatical structure and meaning, is a computationally challenging task. Traditional approaches often struggle to efficiently represent and process the intricate relationships between words and their grammatical roles. This paper addresses the need for a more powerful and flexible parsing mechanism, particularly one that can effectively handle the complex syntactic and semantic constraints inherent in language. The authors aim to bridge the gap between theoretical linguistic frameworks like Lexical Functional Grammar (LFG) and computational implementations, proposing a system that can derive both grammatical and semantic representations from input sentences.

Methods

The core of the proposed architecture lies in the use of Distributed Memory Machines (DMMs). These are computational devices that store large numbers of associations on a single composite vector, inspired by holographic associative memory. Key operations include:

  • Convolution (*): Used to associate two memory vectors (e.g., <A>*<B>). This operation is associative and commutative.
  • Correlation (#): Used for retrieval. Presenting one vector (e.g., <A>) to a DMM that stores <A>*<B> retrieves a noisy version of <B>.
  • Vector Addition (+): Used to concatenate multiple associations into a single composite vector, allowing for the representation of multiple hypotheses or states.

The paper demonstrates how these DMM operations can naturally implement principles of Lexical Functional Grammar (LFG). Specifically:

  • Case-Frame Parsing: DMMs are used to store case-frame structures associated with verbs. Input noun phrases are correlated with these structures to identify their grammatical roles (e.g., agent, object).
  • Syntactic Knowledge Encoding: The architecture integrates with a context-free grammar (CFG) to derive phrase structure trees. These trees are then used to generate functional structures (f-structures), which represent grammatical relations. The DMMs are used to efficiently encode and derive these f-structures from augmented phrase structure trees, bypassing intermediate steps often required in LFG parsing.

Datasets

Not discussed in the paper. The paper focuses on the theoretical architecture and its computational properties rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Holographic Memory as a Linguistic Primitive: The paper suggests that the associative and distributive properties of holographic associative memory provide a natural computational substrate for encoding linguistic knowledge, particularly the complex interplay of syntax and semantics.
  • Convolution for Association, Correlation for Retrieval: The distinct roles of convolution for forming associations and correlation for retrieving them offer a powerful mechanism for memory-based language processing.
  • Direct Derivation of LFG Structures: A significant insight is that the computational properties of DMMs allow for the direct derivation of LFG's functional structures from augmented phrase structure trees, simplifying the parsing process.
  • Unified Representation of Syntax and Semantics: The architecture aims to produce both grammatical relations (f-structures) and semantic representations (case-frame instantiations) within a single, integrated system.
  • Robustness to Noise: The correlation operation inherently produces noisy versions of retrieved items, which the authors suggest can be managed by filtering mechanisms (part of the output function) and can also reflect the similarity between concepts.

Key Results

The paper presents a theoretical framework and a proposed architecture rather than empirical results with quantitative metrics. The key "results" are conceptual:

  • A demonstration that DMMs can naturally encode case-frame structures and facilitate their instantiation with input phrases.
  • A method for deriving LFG functional structures from augmented phrase structure trees using DMM operations, effectively integrating syntactic parsing with semantic representation.
  • The proposed architecture is shown to be capable of generating both semantic and grammatical relational structures.

Limitations and Future Work

  • Ambiguity Handling: The paper acknowledges that unambiguous case assignment requires integrating syntactic and semantic processing, and that semantic knowledge alone is insufficient. The proposed architecture aims to address this by combining syntactic information (from CFG) with semantic information (from case-frame DMMs).
  • Computational Complexity: While DMMs offer efficiency in representation, the paper doesn't deeply explore the computational complexity of the proposed parsing algorithm in practice.
  • Empirical Validation: The paper is primarily theoretical. Future work would involve implementing this architecture and evaluating its performance on real-world linguistic data.
  • Heterarchical Control: The parsing system is described as having heterarchical control, suggesting a need for further investigation into the management of complex interactions between DMMs.

Summary updated

BibTeX
@inproceedings{slack1984parsing,
  author = {Jon M. Slack},
  title = {{A Parsing Architecture Based on Distributed Memory Machines}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1984},
}
Figure