Mapping Between Semantic Representations Using Horn Clauses

Ralph M. WeischedelAAAI 1983

In the early 1980s, a significant challenge in Natural Language Understanding (NLU) was not just parsing a sentence, but translating that parse into a form a computer could actually execute. This 1983 paper addresses the "second transduction phase"—the bridge between a system's initial semantic understanding and the specific formal representation required by an underlying application.

The Gap Between Human and Machine Semantics

When an NLU system parses a sentence, it typically generates a semantic representation (R). However, R is often still "too human." It reflects the linguistic structure of the input, which frequently includes spatial metaphors (e.g., "the top of the stack"), vague terms, or paraphrases that are not optimized for computational tasks.

Conversely, the target application—whether it is a database, a theorem prover, or a formal software specification tool—requires a very specific, formal representation (S). The transition from R to S involves three primary challenges:

  1. Metaphor Analysis: Translating conceptual metaphors into concrete data operations (e.g., mapping "one end" to "the first element of a sequence").
  2. Application Optimization: Converting a general request into a computationally efficient form for a specific backend.
  3. Contextual Paraphrasing: Recognizing that different linguistic expressions (e.g., "the $i^{th}$ element" vs. "the element at position $i$") refer to the same internal concept.

Methodology: Horn Clauses as a Mapping Engine

The author proposes using Horn clauses—a subset of first-order logic—to drive this mapping process. The system architecture follows a three-stage pipeline:

  1. Parsing and Interpretation: An augmented RUS parser generates the initial semantic representation.
  2. Logic Conversion: A component developed by Daniel Chester handles quantifier scope and reference resolution, outputting a set of Horn clauses.
  3. The Mapping Component: This is the core contribution. It uses specialized Horn clause rules to transform the initial formulas into the final application-ready form.

By using Horn clauses, the mapping becomes inference-driven rather than simple pattern-matching. The system can reason about the domain context. For instance, if the system knows a "stack" is a type of "ordered list," and it possesses a rule for mapping "ends" of "ordered lists," it can automatically infer how to handle the "top" of a stack without requiring an explicit rule for every possible data structure.

Evaluation and Domain Application

The approach was evaluated using English descriptions of abstract data types (ADTs) derived from the classic textbook Fundamentals of Data Structures by Horowitz and Sahni (1976).

A primary example involves the definition: "A stack is an ordered list in which all insertions and deletions occur at one end called the top."

The system successfully maps this complex sentence into a formal Horn clause representation. This output is suitable for a theorem prover to verify software properties. The mapping component identifies "the top" as a specific sequence position and unifies various paraphrases for retrieving elements into a single formal predicate.

Key Insights

  • Factoring the Process: By separating "understanding English" from "mapping to the application," the NLU component becomes more portable. The linguistic logic remains constant, while only the mapping rules need to change for different backends.
  • Frozen Metaphors: In technical domains, metaphors like "the top of a stack" are often "frozen" or standardized. Logic rules are uniquely effective at unpacking these into concrete operations like SEQUENCE-ELEMENT.
  • Handling Vagueness: The system can resolve "extended" uses of words. If a user says "add item I to stack S," the system can map the vague "add" to a specific "insert at position X" operation, where X is inferred to be the "top."
  • Uniformity: Because the knowledge base, the semantic representation, and the mapping rules are all encoded as Horn clauses, the system can seamlessly integrate new information into its reasoning chain.

Limitations and Future Directions

Despite its success in the ADT domain, the system faced several hurdles. The mapping rules required manual engineering, a labor-intensive process. The author suggested that future work should explore the automatic generation of these rules from text. Additionally, as the rule set grows, search efficiency becomes a concern, necessitating better indexing techniques and potentially a shift toward "forward-chaining" modes for the mapper. Finally, while effective for technical metaphors, the system's ability to handle more creative or fluid linguistic metaphors remains an open question.

Summary updated

BibTeX
@inproceedings{weischedel1983mapping,
  author = {Ralph M. Weischedel},
  title = {{Mapping Between Semantic Representations Using Horn Clauses}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure