Abstract
This paper investigates the computational complexity of learning "existential conjunctive concepts" within structural domains, such as the blocks world. While these concepts are intuitive for describing relationships between objects, the mapping between scene objects and concept variables introduces significant computational hurdles. The study proves that finding a consistent hypothesis in this domain is NP-complete. However, it also demonstrates that these concepts are learnable in the PAC framework if the hypothesis space is expanded or if simple consistent hypotheses can be found through heuristics.
Introduction
In the early days of artificial intelligence, research often focused on "structural domains" where instances are defined not just by a list of attributes, but by a collection of objects and their interrelationships. A classic example is Winston’s "arch," which is defined by two posts supporting a lintel rather than just a collection of three blocks.
While intuitive, these structural concepts introduce a massive computational challenge: ambiguity. When comparing a scene to a concept, one must determine which physical object in the scene corresponds to which variable in the concept definition. This paper formally analyzes the computational complexity of this mapping problem and evaluates whether these structural concepts can be efficiently learned within the "Probably Approximately Correct" (PAC) framework.
Formal Representation and Methodology
Haussler formalizes the problem using existential conjunctive expressions in predicate calculus. Both scenes (data) and concepts (hypotheses) are represented as labeled directed graphs:
- Nodes represent individual objects, labeled with attributes such as shape, size, or shading.
- Edges represent binary relations between objects, such as spatial relationships (e.g., "inside," "on top of").
The attributes themselves can be structured hierarchically, allowing for generalizations. For instance, a specific shape like a circle can be generalized to an ellipse or a convex shape, facilitating broader concept matching across different levels of abstraction.
The analysis employs two primary mathematical tools: complexity theory to prove NP-completeness by reducing known hard problems to the "version space emptiness" problem, and Vapnik-Chervonenkis (VC) dimension to determine the sample complexity required for guaranteed accuracy.
Theoretical Insights
Several key insights emerge from this formalization:
- The Hardness of Ambiguity: Even in extremely simplified scenarios—such as scenes with only two objects and simple Boolean attributes—the task of finding a consistent concept is NP-complete. The bottleneck is the combinatorial explosion of possible mappings between objects and variables.
- Hypothesis Space Expansion: A counter-intuitive strategy for learning these "hard" classes is to search within a larger, more redundant hypothesis space (e.g., $k!$-CNF). While the space is larger, it may be more efficiently searchable than the minimal, precise target space.
- Occam’s Razor as a Guarantee: The paper proves that if a heuristic finds a simple hypothesis (one with few atoms) consistent with a sufficiently large random sample, that hypothesis is mathematically guaranteed to be a good approximation. This provides a theoretical justification for the use of greedy or heuristic algorithms in AI.
Complexity and Learnability Results
The paper establishes several foundational theorems:
- NP-Completeness: Finding a consistent existential conjunctive concept is NP-complete, implying this class is not polynomially learnable from random examples unless $RP = NP$.
- Learnability via Expansion: These concepts are learnable if the learner can output a hypothesis from a different, larger class, though this remains practical only for scenes with very few objects ($k \le 3$).
- Sample Complexity: The number of examples ($m$) required for learning grows logarithmically with the number of objects per scene ($k$), but linearly with the number of relations ($n$) and the simplicity ($s$) of the target concept. This suggests that structural learning is data-efficient even if it is computationally expensive.
Conclusion and Future Work
The primary limitation of the proposed positive results is the exponential growth ($k!$) of the mapping algorithm as the number of objects increases, making it impractical for complex scenes. Haussler concludes that the future of the field lies in identifying better heuristics and specific structural domains or query types that can bypass these hardness results. This work laid the groundwork for subsequent developments in inductive logic programming (ILP) and relational learning.
Summary updated