The Common Order-Theoretic Structure of Version Spaces and ATMS’s (Extended Abstract)

AAAI 1991

TL;DR

This paper unifies the mathematical underpinnings of two distinct AI techniques: version spaces for concept learning and Assumption-based Truth Maintenance Systems (ATMS) for belief revision. By introducing the concept of "convex spaces," the authors reveal a shared structure that allows for more efficient algorithms and a deeper understanding of their respective domains.

What Problem Does This Paper Address?

The paper tackles a perceived disconnect between two important AI paradigms: version spaces, used in machine learning to learn concepts from examples, and ATMS, used in knowledge representation to manage beliefs and dependencies. While both systems deal with sets of possibilities and their relationships, they were developed independently with different mathematical formalisms. The authors sought to find a common mathematical framework that could explain their similarities, potentially leading to new insights and more efficient implementations for both. Specifically, they were interested in how to represent and manipulate these sets of possibilities efficiently, especially when dealing with complex logical structures.

Methods

The core of the paper's contribution lies in the introduction and application of convex spaces as a unifying mathematical structure. A convex space, in this context, is a set of elements (representing concepts or environments) with a specific partial order, where certain subsets exhibit "convexity." This convexity allows for efficient representation using only the "boundary" elements (minimal and maximal elements) of these subsets, rather than the entire set.

Key techniques include:

  • Convex Space Formalism: Defining convex spaces and their properties, particularly "finite representability" (the ability to represent a space with finite boundary sets) and the "MW property" (a condition ensuring finite representability is preserved under certain operations).
  • Version Space Formulation: Reinterpreting version spaces as a specific type of convex space, allowing the application of convex space theory to concept learning. This leads to a formal criterion (the MW property) for when finite observation version spaces are finitely representable.
  • ATMS Reformulation: Describing ATMS label updates as operations on convex spaces. This allows for a new, more efficient algorithm for handling complex disjunctions in ATMS, avoiding the need for hyper-resolution rules.
  • Fringe Representation: Proving an isomorphism between finitely representable convex spaces and "fringes" (pairs of finite anti-chains), providing a concrete way to represent and manipulate these structures.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unification is Possible: The most significant insight is that version spaces and ATMS, despite their different origins, share a fundamental order-theoretic structure that can be captured by the theory of convex spaces.
  • Efficiency Through Boundaries: Representing complex sets of possibilities by their minimal and maximal elements (boundaries) is a powerful technique for achieving computational efficiency in both version spaces and ATMS.
  • MW Property as a Key: The "MW property" emerges as a crucial condition for ensuring that operations like merging in version spaces or updating labels in ATMS preserve finite representability.
  • New ATMS Algorithm: The paper presents a novel ATMS algorithm for handling complex disjunctions that is more efficient and conceptually simpler than existing hyper-resolution based methods.
  • Admissibility for Learning: The concept of "admissibility" for concept languages is formalized, providing a criterion for when the version space algorithm can guarantee finite representability.

Key Results

  • Theorem 1: A poset has the MW property if and only if finitely representable convex spaces form a sublattice of the lattice of convex spaces.
  • Theorem 2: The poset of finitely representable convex subsets is isomorphic to the poset of fringes, providing a concrete representation.
  • Theorem 4: A poset has the MW property if and only if the meet of every two finitely representable version spaces is finitely representable. This directly addresses the efficiency of version space merging.
  • Admissibility Criteria: Formal definitions and criteria (S property, admissibility) are provided for concept languages, with Theorem 6 showing that finite posets with MW and S properties are admissible.
  • New ATMS Label Update: Formulas (1) and (2) are derived for computing the intersection and union of representable convex spaces, which are then used to develop a new label update algorithm for ATMS.
  • Extended ATMS Algorithm: Theorems 7 and 8 outline a new approach to extended ATMS label updates using closure operations, avoiding hyper-resolution.

Limitations and Future Work

  • Admissibility for Infinite Languages: While the paper provides results on admissibility, it acknowledges that some important concept languages (like the rectangular concept space example) are infinite, and the current admissibility conditions might not fully capture their behavior.
  • Formal Semantics: The authors mention that their convex space treatment of ATMS leads to a formal semantics for both basic and extended ATMS, suggesting this as a direction for future work.
  • Negation and Prime Implicants: They also hint at future work showing how their approach can be used to calculate prime implicants for DNF propositional formulas when negation is introduced into the ATMS architecture.
  • Implementation: The paper notes that the extended ATMS algorithm is currently implemented on top of a basic ATMS, implying ongoing development and testing.

Summary updated

BibTeX
@inproceedings{1991common,
  title = {{The Common Order-Theoretic Structure of Version Spaces and ATMS’s (Extended Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure