A Probabilistic Analysis of Marker-Passing Techniques for Plan-Recognition

Glenn Carroll, Eugene CharniakUAI 1991

TL;DR

This paper tackles the problem of "useless paths" in marker-passing techniques for plan recognition. They introduce a probabilistic framework to analyze and prune these paths, significantly improving the efficiency and accuracy of plan recognition systems by filtering out unpromising search directions.

What Problem Does This Paper Address?

Plan recognition, a core task in understanding narratives or actions, often relies on matching observed events to generalized "schemas" (like a plan to buy groceries). A common technique for this is "marker-passing," which searches an associative network of concepts to find plausible connections between observed events and potential schemas. However, a major challenge is that marker-passing often generates a vast number of "useless" or incorrect paths, making it difficult to identify the true plan. This paper aims to address this by providing a principled, probabilistic method to filter these paths, making marker-passing a more viable and efficient approach.

Methods

The authors propose a probabilistic analysis of marker-passing. They frame the problem using Bayesian networks, where schemas and their relationships are represented as nodes and edges. The core idea is to use probability distributions to guide the marker-passing search.

  • Probabilistic Schema Evaluation: They evaluate the probability of a potential schema being the correct explanation for the input. This is done by embedding statements about schema instances and their relationships into a Bayesian network.
  • Probabilistic Schema Selection (Marker-Passing): They modify the standard breadth-first marker-passing algorithm. Instead of just propagating marks, they use probability information to control the search. This involves extending the search in promising directions and, crucially, terminating it in unpromising ones.
  • Vertebrate Bayesian Networks: They introduce a specific network structure called "vertebrate Bayesian networks" that is uniquely associated with each valid path. This structure allows for efficient calculation of an upper bound on the joint probability of the statements in a path.
  • Spinal Contribution: They define a "spinal contribution" as a measure of the probability of a path fragment. This measure is computed incrementally as the path is built, allowing for early pruning of low-probability paths.

Datasets

Not discussed in the paper. The authors refer to a "large corpus of stories" and a "Wimp3 story understanding system" for evaluation, but specific datasets are not detailed.

Key Insights and Ideas

  • Probability is Key to Pruning: The paper strongly argues that incorporating probabilistic information is essential for making marker-passing effective. Without it, the system is overwhelmed by irrelevant paths.
  • Early Pruning is Crucial: By calculating an upper bound on the probability of a path as it's being constructed (the "spinal contribution"), they can cut off unpromising paths much earlier, saving significant computation.
  • Evidence is Necessary: The authors highlight that the effectiveness of their approach relies heavily on the presence of "supporting evidence" (represented by an El node in their Bayesian networks). Without evidence, even good paths have low posterior probabilities.
  • A Gap in Probabilities: They observe a significant gap (a factor of 10 or more) between the "spinal contribution" of correct and incorrect paths, suggesting that even approximate prior probabilities are sufficient for effective filtering.

Key Results

The paper reports significant improvements in the ratio of "good" to "bad" paths.

  • They achieved a ratio of approved paths to asserted paths of 68% for the debugging corpus and 59% for the test corpus. This is a substantial improvement over previous marker-passing systems, which had a reported good-to-bad path ratio of around 10%.
  • By integrating probability valuation into the marker-passing mechanism, they made it impossible to estimate the exact number of paths eliminated by low probability values or invalid path filters.
  • They found that weeding out paths with no evidence accounted for the difference between paths that were asserted (used for network construction) and those that were evaluated.
  • For paths that were evaluated, approximately 94% were "good" (meaning they were approved after evaluation).

Limitations and Future Work

  • Dependence on Evidence: The authors acknowledge that the approach is highly dependent on the availability of supporting evidence for paths. Domains lacking such evidence might not benefit as much.
  • Approximate Priors: While they show that approximate priors are sufficient, the quality of these priors still impacts performance.
  • Future Work: The paper suggests that the ability to cheaply identify paths without evidence is crucial. They also imply that further refinement of the probability calculations and the integration with other AI systems (like Wimp3) are ongoing areas of research.

Summary updated

BibTeX
@inproceedings{carroll1991probabilistic,
  author = {Glenn Carroll and Eugene Charniak},
  title = {{A Probabilistic Analysis of Marker-Passing Techniques for Plan-Recognition}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1991},
}
Figure