DCKR – Knowledge Representation in Prolog and Its Application to Natural Language Processing

Hozumi TanakaCOLING 1986

TL;DR

This paper introduces DCKR, a novel knowledge representation system built on Prolog's definite clauses. DCKR aims to simplify natural language processing (NLP) by allowing knowledge and lexical item descriptions to be expressed as Prolog clauses, enabling Prolog's built-in inference engine to handle much of the semantic processing and context management. This approach significantly reduces the programming effort required for NLP systems.

What Problem Does This Paper Address?

Natural Language Processing (NLP) systems require robust methods for representing knowledge and understanding the meaning of words and sentences. Traditional approaches often involve separate interpreters for knowledge representation formalisms like frames or objects, leading to complex implementations. The authors identify a need for a more integrated approach where the underlying programming language's capabilities can directly support semantic processing. Specifically, they address the challenge of efficiently representing lexical items and their semantic roles in a way that leverages the power of logic programming, thereby alleviating the burden of writing custom semantic processing code.

Methods

The core contribution is the Definite Clause Knowledge Representation (DCKR) system. DCKR represents knowledge as Horn clauses in Prolog, where the sem predicate serves as the head. Objects, whether individuals or prototypes, are defined as a set of sem clauses with the same first argument (the object name).

Key aspects of DCKR include:

  • Object Representation: Objects are structured as sets of Prolog clauses. Individual objects are denoted with a # suffix (e.g., clyde#1), while prototypes are not (e.g., elephant).
  • Slots as Horn Clauses: Slots within an object are represented by sem predicates with specific attribute-value pairs as arguments. For example, sem(clyde#1, age:6, _). represents Clyde's age.
  • Inheritance: The isa predicate facilitates hierarchical knowledge inheritance from prototypes to individuals. For instance, sem(clyde#1, P, S) :- isa(elephant, P, [clyde#1:S]). means Clyde inherits properties from the elephant prototype.
  • Part-Whole Relations: The hasa predicate models part-whole relationships.
  • Context Tracking: The third argument of the sem predicate is used to stack the path taken during prototype traversal, allowing for context tracking and identifying the calling individual.
  • Grammar Rules: Definite Clause Grammars (DCG) are used for syntactic parsing, with "reinforcement terms" (Prolog goals) embedded within the grammar rules to perform semantic interpretation concurrently. The sem predicate is formally called via a seminterp predicate within these reinforcement terms.

Datasets

Not discussed in the paper. The paper focuses on the representation and processing mechanisms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Prolog as a Semantic Engine: The most significant insight is that Prolog's built-in unification and backtracking mechanisms can directly handle a substantial portion of semantic processing, including knowledge inheritance and slot filling, without requiring a separate, custom-built interpreter.
  • Unified Representation: DCKR provides a unified way to represent both general knowledge (prototypes, hierarchies) and specific lexical item descriptions (frames/objects), all within the Prolog framework.
  • Compile-time Efficiency: Unlike traditional frame-based systems that often rely on large, compiled data structures, DCKR's clause-based representation can be compiled, leading to potentially faster processing.
  • Integrated Syntax and Semantics: By embedding semantic interpretation directly into DCG rules via reinforcement terms, the system achieves a tight integration of syntactic and semantic processing, which is argued to be psychologically plausible.

Key Results

The paper demonstrates the functionality of DCKR through examples:

  • Age Calculation: The system can automatically calculate an individual's age based on its birth year stored in a prototype, e.g., ?-sem(elephant#1,age:X,). correctly yields X=6.
  • Property Retrieval: All properties of an individual can be retrieved by querying its sem predicate, including inherited properties.
  • Lexical Item Description: The paper provides a detailed DCKR description for the verb "open," showcasing how syntactic roles (subject, object, instrument) are mapped to semantic constraints and actions using extractsem.
  • Test Sentence Processing: The sentence "He opens the door with a key" is processed, and the resulting semantic structure is represented in DCKR form, demonstrating the system's ability to extract agent, instrument, and object.
  • Querying Semantic Results: The paper shows that the DCKR-formatted semantic results can be queried directly, e.g., asking "With what does he open the door?" (sem(open#J, instrument: X, )) yields X=key#7.

Limitations and Future Work

  • Limitations:
    • The paper acknowledges that while context processing is partially handled, it's not fully elaborated.
  • The "bottomof" predicate is introduced for context tracking, but its full implications and robustness are not deeply explored.
  • The paper focuses on the representation and mechanism; extensive empirical evaluation or comparison with state-of-the-art NLP systems is not presented.
  • Future Work:
    • The authors envision a natural language understanding system architecture (illustrated in Fig. 1) where DCKR forms the core of the knowledge base.
  • They suggest that a Prolog machine combined with a knowledge base machine (powered by DCKR) could form the basis of future natural language processing systems, aligning with the goals of projects like Japan's Fifth Generation Computer Systems.
  • Further exploration of context processing and more complex semantic constraints is implied.

Summary updated

BibTeX
@inproceedings{tanaka1986dckr,
  author = {Hozumi Tanaka},
  title = {{DCKR – Knowledge Representation in Prolog and Its Application to Natural Language Processing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1986},
}
Figure