A Project Report on NP: an Assumption-based NL Plan Inference System that uses Feature Structures

John K. MyersCOLING 1990

TL;DR

This paper introduces NP, a novel Natural Language (NL) plan inference system that leverages feature structures and an Assumption-based Truth Maintenance System (ATMS). NP can infer dialog and domain-level plans from semantic parser output, handling uncertainty and multiple possibilities, which is crucial for robust dialog understanding in applications like automatic interpreting telephone systems.

What Problem Does This Paper Address?

Understanding human communication, especially in dialogs, goes beyond just parsing sentences. It requires inferring the underlying intentions, goals, and plans of the speakers. This is a challenging task because:

  • Unobservability: Mental states like intentions and beliefs are not directly observable. We must rely on assumptions.
  • Uncertainty: There's often insufficient information to represent these concepts with certainty. Communication is inherently an assumption-based process.
  • Complexity: Dialogs involve a complex interplay of speech acts, illocutionary acts, and domain-specific knowledge.
  • Ambiguity: Utterances can be ambiguous, requiring the system to consider multiple interpretations.

Existing systems often struggle with these aspects, particularly in representing and reasoning with uncertainty and multiple potential interpretations simultaneously. This paper aims to build a more robust dialog understanding system by addressing these challenges through an assumption-based plan inference engine.

Methods

The core of NP is a hybrid inference engine that combines the strengths of feature structures and an ATMS:

  • Feature Structures: Used for representing complex, incomplete, or underspecified information. They are excellent for pattern matching and unification, making them suitable for representing NL utterances and plan schemata.
  • Assumption-based Truth Maintenance System (ATMS): This is the key innovation. The ATMS allows the system to:
  • Represent and reason with assumptions.
  • Handle multiple, potentially conflicting, possible worlds or interpretations simultaneously.
  • Maintain the truth of derived beliefs in a nonmonotonic fashion (i.e., beliefs can be retracted if new information contradicts them).
  • Pre-instantiate hypothetical assertions and implications, significantly speeding up processing.

Plan Schemata: Plan actions are represented as feature-structure "plan schemata" that include preconditions, hierarchical decompositions, and effects. These schemata are the building blocks for inference.

Inference Engine: The inference engine uses a rewriting system for pattern matching and the ATMS for managing conjunctive implications and assumptions. This allows NP to perform plan recognition, prediction, and inference. The system uses a five-valued uncertainty logic (ACTUAL, POSSIBLE, HYPOTHETICAL, INCONSISTENT, NULL) to represent belief states.

Datasets

Not explicitly discussed in the paper. The paper mentions using a corpus of five conversations (20 utterances each) representing the output of the ATR parsing system for testing. Additionally, a separate set of 46 plans was used to replicate a "four-layer" recognition model.

Key Insights and Ideas

  • Assumption-based reasoning is fundamental for dialog understanding: The paper strongly argues that human communication relies heavily on assumptions, and any robust system must model this.
  • ATMS is a powerful tool for handling uncertainty and multiple possibilities: By allowing the simultaneous consideration of multiple consistent interpretations, the ATMS enables the system to deal with ambiguity and incomplete information more effectively.
  • Hybrid systems offer significant advantages: Combining feature structures for representation with an ATMS for reasoning provides a powerful framework for complex NL understanding tasks.
  • Pre-instantiation significantly boosts efficiency: By pre-loading hypothetical assertions and implications into the ATMS, processing time can be drastically reduced.
  • Feature structures are a natural fit for representing NL and plans: Their ability to handle underspecification and complex relationships makes them ideal for this domain.

Key Results

The paper reports on NP version 2.0, which has been finished and demonstrated.

  • Demonstrated understanding: The system understands portions of all five test conversations.
  • Plan schema coverage: 53 plan schemata have been written, covering various aspects of conversation, including opening/closing, question-answering, inferred knowledge, and common-sense knowledge.
  • Instantiation of assertions: In one test, 232 feature-structure assertions were instantiated.
  • Flexibility: The system can infer plans directly from semantic parser output and provide information to downstream modules like transfer and generation systems.

Limitations and Future Work

  • Instantiation Method: The authors note that the instantiation method needs improvement.
  • Nonmonotonic Reasoning: Representing and reasoning with multiple possible nonmonotonic plans is an area of ongoing research.
  • Conditional Branches: The system needs to be extended to represent and infer plans containing conditional branches, particularly for information-gathering plans.
  • Disambiguation: The primary future research direction is the design of a disambiguation system. This is identified as an evidential reasoning problem that will likely require integrating a causal reasoning system with the multi-world ATMS.
  • Pronoun Resolution: A module is needed to resolve zero pronouns using possible plans, as the lack of fully resolved utterances hinders plan recognition.
  • Intentions: Further work is required for representing and reasoning with intentions found in dialog.

Summary updated

BibTeX
@inproceedings{myers1990project,
  author = {John K. Myers},
  title = {{A Project Report on NP: an Assumption-based NL Plan Inference System that uses Feature Structures}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1990},
}

Loading related content...

Figure