Efficiency Analysis of Multiple-Context TMSs in Scene Representation

Gregory M. ProvanAAAI 1987

Introduction

In the development of early AI reasoning engines, Truth Maintenance Systems (TMS) played a pivotal role in managing beliefs and justifications. Two primary architectures emerged: Justification-based TMS (JTMS), which maintains a single consistent world-view, and Assumption-based TMS (ATMS), designed to explore multiple "contexts" or alternative worlds simultaneously. For years, the AI community operated under the assumption that ATMS was the superior choice for problems requiring multiple solutions, believing that the worst-case exponential complexity ($2^n$) was rarely encountered in practice.

Gregory Provan’s research challenges this "efficiency myth." By examining high-level vision tasks, Provan demonstrates that ambiguity—a fundamental characteristic of domains like computer vision and speech recognition—naturally triggers the combinatorial explosion that makes ATMS computationally infeasible for large-scale applications.

The Vision Constraint Recognition System (VCRS)

To empirically test ATMS efficiency, Provan introduced the Vision Constraint Recognition System (VCRS). This system is tasked with identifying a "puppet" figure—a structured collection of 15 parts—within a complex scene of randomly overlapping 2D rectangles.

The PUPPET problem scene, showing a target figure (A-E) embedded in a cluttered environment of overlapping rectangles.

In this environment, the ATMS must manage numerous competing interpretations. Each rectangle in the scene could potentially represent several different body parts (e.g., an arm, a leg, or the trunk). As the system attempts to assemble these local fragments into a coherent global figure, the number of potential "partial solutions" or environments grows at an alarming rate.

The Combinatorial Explosion of Ambiguity

The core issue identified in Provan's analysis is that ambiguity is inherently exponential. In vision, local features are often insufficient to uniquely identify an object. When multiple plausible labels exist for every fragment, the ATMS is forced to track every valid combination of these labels.

Provan’s mathematical analysis focuses on "nogoods"—sets of assumptions proven to be inconsistent. While the ATMS uses nogoods to prune the search space, the effectiveness of this pruning is highly dependent on the size of the nogoods found.

The "Nogood" Paradox

A critical insight from the paper is that large nogoods are mathematically inefficient. Provan proves that the power of a nogood to reduce the search space is inversely proportional to its size. In complex scene representation:

  1. Small inconsistencies (small nogoods) are easy to find but only prune a small fraction of the total space.
  2. As the system builds larger, more complex partial solutions, the inconsistencies it discovers involve more assumptions (large nogoods).
  3. If inconsistencies only emerge when ten or more assumptions are combined, the ATMS must explore a massive portion of the $2^n$ space before any pruning occurs.

Even if a problem ultimately has only a few valid final solutions, the "intermediate explosion" of constructing exponential partial solutions can cause the system to fail long before reaching the goal.

Empirical Results and Simulations

The study utilized the "PUPPET Problem," a benchmark originally studied by Geoffrey Hinton, to validate these theoretical claims. Simulations of the mathematical models confirmed that the percentage reduction in search space provided by nogoods remains constant regardless of the problem size ($n$). This implies that increasing computational power or database size does not mitigate the fundamental efficiency problem.

For a problem with $n=100$ facts, the potential search space reaches approximately $1.26 \times 10^{30}$. Provan’s VCRS experiments showed that even relatively simple scenes required an "unreasonably large" number of environments to be constructed, corroborating the theoretical complexity analysis.

Conclusion and Future Directions

The findings suggest a significant limitation for the application of standard ATMS in ambiguous, high-level domains. To avoid computational collapse, Provan suggests several paths forward:

  • Enhanced Control Mechanisms: Problem solvers may need to exert tighter control over the ATMS, perhaps reverting to JTMS-like behavior (focusing on one solution at a time with dependency-directed backtracking) when complexity spikes.
  • Taxonomy of Problems: There is a need for a clearer classification of which problem domains are "ATMS-friendly" based on the expected size and frequency of nogoods.
  • Global Constraints: Incorporating high-level domain constraints (such as global scaling or perspective in vision) can prune the search space more aggressively than the internal logic of the ATMS alone.

Ultimately, while ATMS offers a powerful framework for multi-context reasoning, its "blind" exploration of combinations makes it a poor fit for the inherent ambiguity of real-world scene representation without significant external guidance.

Summary updated

BibTeX
@inproceedings{provan1987efficiency,
  author = {Gregory M. Provan},
  title = {{Efficiency Analysis of Multiple-Context TMSs in Scene Representation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}

Loading related content...

Figure