Quantifying and Simulating the Behavior of Knowledge-Based Interpretation Systems

AAAI 1980

TL;DR

This paper introduces a novel methodology for quantitatively measuring the performance of components within knowledge-based interpretation systems, like Hearsay-II. By defining "reliability" for intermediate system states and individual knowledge sources (KSs), the authors enable the simulation of system upgrades, allowing for more accurate predictions of performance improvements before costly implementation.

What Problem Does This Paper Address?

Developing and tuning knowledge-based interpretation systems, particularly complex ones like Hearsay-II for speech understanding, is currently more of an art than a science. There's a significant lack of formal methods to connect the overall system's performance to the performance of its individual components (knowledge sources or KSs, and schedulers). When Hearsay-II's initial configuration (C1) performed poorly, the developers relied on intuition to create a reorganized version (C2), which was a trial-and-error process. This paper aims to bridge this gap by providing a framework to quantify component behavior and simulate potential improvements, making system development more systematic and predictable.

Methods

The core of the paper's methodology revolves around the concept of "reliability" for both intermediate system states and individual KSs.

  • Reliability Measure: They define reliability as a combination of a hypothesis's accuracy (truth-value) and certainty (belief-value). This is operationalized through a "reflecting-back" process where belief and truth values of higher-level hypotheses are propagated back to the input hypotheses they support. This allows for a quantitative measure of the system's state.
  • KS Resolving Power: The "resolving power" of a KS is defined as the change in reliability it induces in the system state after a single execution. This is measured by comparing the reliability of input competitor sets before and after a KS processes them.
  • KS Simulation: The authors propose simulating KSs by using a "candidate generator" (which can be a real or simplified KS) and a "resolver." The resolver, guided by an "oracle" (which knows the true interpretation), adjusts belief values to achieve a desired resolving power, allowing for the simulation of upgraded or new KSs.
  • Scheduler Simulation: Similarly, schedulers are simulated by statistically rating KS instantiations based on their predicted impact on system reliability. This allows for modeling schedulers with varying degrees of accuracy.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and simulation, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Quantifying "Reliability": The paper introduces a novel way to quantify the state of a knowledge-based system by combining the certainty (belief-value) and accuracy (truth-value) of hypotheses. This moves beyond just belief propagation to a more holistic measure of how "good" the system's current understanding is.
  • Separating KS "Resolving Power" from Global Impact: The authors distinguish between the immediate, local effect of a KS execution (its resolving power) and its broader, long-term impact on the system. This separation is crucial for understanding individual component contributions.
  • Simulation as a Predictive Tool: The ability to simulate KSs and schedulers with specific performance characteristics (resolving power, accuracy) is a key insight. This allows researchers to predict the outcome of system modifications before implementing them, saving significant development time and effort.
  • Oracle-Assisted Simulation: The use of an "oracle" (a perfect judge of truth) is a clever way to enable quantitative evaluation and simulation without needing a fully functioning, perfect system.

Key Results

The paper presents a methodology and simulation framework, rather than empirical results from a specific system. The key "results" are the definitions and techniques themselves:

  • A formal measure for the reliability of an intermediate system state.
  • A method for quantifying the "resolving power" of individual KSs.
  • A simulation technique for KSs and schedulers that allows for predicting performance improvements.
  • An example calculation demonstrating how processing effectiveness (PE) can be measured as the difference between initial and intermediate state reliability, showing a positive PE of .058 in their illustrative example.

Limitations and Future Work

The authors acknowledge several limitations:

  • KS Simulation Limitations:
    • Simulated KSs rely on an oracle for truth-values, whereas real KSs infer truth from local consistency.
  • The statistical approach to simulation means that simulated KSs with similar errors might not exhibit correlated behavior, unlike real KSs.
  • Scheduler Simulation Limitations:
    • The current scheduler model takes an instantaneous view and cannot model algorithms that consider future processing.
  • The paper notes that real schedulers consider factors beyond just stimulus hypothesis truth-values, such as processing history and strategic choices (depth-first vs. breadth-first).
  • Future Work:
    • Validate the models by analyzing the behavior of KSs in existing knowledge-based systems and comparing it to simulations.
  • Develop a more comprehensive formulation for scheduler simulation that incorporates information about future processing.
  • Further explore the application of these measures and simulations to real-world systems.

Summary updated

BibTeX
@inproceedings{1980quantifying,
  title = {{Quantifying and Simulating the Behavior of Knowledge-Based Interpretation Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure