Automatic Generation of Object Class Descriptions Using Symbolic Learning Techniques

Robert L. Cromwell, Avinash C. KakAAAI 1991

Presented at AAAI-91, this research addresses a fundamental bottleneck in early computer vision: the reliance on manually crafted recognition rules. Cromwell and Kak propose a framework that automates the generation of symbolic object class descriptions from examples, enabling systems to adapt dynamically as new object types are introduced.

The Challenge: Moving Beyond Hand-Coded Logic

In the early 1990s, model-based vision systems were often brittle because they depended on domain-specific rules written by human experts. This approach fails in evolving environments where new objects must be recognized without constant human intervention.

The authors focus on the "$N+1$ class problem": if a system can already distinguish between $N$ known classes, how can it autonomously learn to incorporate a $(N+1)$-th class? The core difficulty lies in generalization—finding a description broad enough to encompass all members of a new class while remaining specific enough to exclude members of existing classes. This is particularly challenging with numerical attributes (e.g., dimensions), where the space of potential mathematical generalizations is theoretically infinite.

System Architecture and Flow

The proposed system is a multi-level learning framework that bridges the gap between raw sensory data and high-level symbolic logic.

Figure 1: The multi-level system architecture for generating classification rules from sensory data.

As shown in Figure 1, the process begins with sensory data (1), which is transformed into training data via human-supervised class assignment (2). The system then applies generalization rules (3) under both low-level and high-level control (4). Finally, it performs a selection of class descriptions (5) to produce the final classification rules.

Methodology: Split-Generalize-Merge

The system utilizes symbolic learning techniques, notably those developed by Ryszard Michalski, to process Attribute-Value (AV) pairs (e.g., (color: red), (size: 20)). To manage the combinatorial explosion of possible rules, the authors introduced a "Split-Generalize-Merge" strategy:

  1. Attribute Clustering: Descriptions are split into independent clusters based on attributes (e.g., size, shape).
  2. Independent Generalization: The system finds valid generalizations for each cluster using logic rules like the "Interval Rule" (creating numerical ranges) or the "Dropping Condition" (removing irrelevant attributes).
  3. Pruning and Merging: Crucially, the system prunes generalizations that lack "discriminatory power"—those that are too broad and overlap with other classes.
Figure 6: The process of pruning cluster generalizations to maintain discriminatory power.

Figure 6 illustrates this pruning stage. By evaluating generalizations against existing class descriptions, the system discards non-discriminatory features, ensuring that the final merged description is both accurate and efficient.

Experimental Evaluation

The framework was tested in two distinct domains to verify its versatility:

Symbolic Vehicle Domain

Using a synthetic dataset of jeeps, cars, and motorcycles, the system demonstrated its ability to handle the $N+1$ problem. For instance, it initially used a broad "Jeep" description, but automatically refined it when "Motorcycles" were introduced, demonstrating dynamic knowledge management.

Real-World Electronic Components

The system processed video images of capacitors, transistors, and resistors. It extracted four numerical features: pixel count ($np$), greylevel variance ($gv$), border length ($bl$), and a radius variance ratio ($r$). Despite very small training sets (fewer than six examples per class), the results were impressive:

  • Capacitors: Identified primarily by "roundness" (radius variance ratio) with a 4.0% false-positive rate.
  • Transistors: Identified via pixel count and greylevel variance with a 2.9% false-positive rate.

Key Insights

  • Discriminatory Power Principle: A feature is only valuable if it helps distinguish classes. The system can "forget" and "re-learn" features as the library of known objects grows.
  • Numerical-to-Symbolic Bridge: By treating numerical ranges as symbolic intervals, the system applies high-level logic to noisy, real-world data.
  • Life-long Learning: The system is designed for continuous operation, rewriting its internal library as it encounters new data.

Limitations and Future Directions

While successful, the system has dependencies that limit its current scope. It relies heavily on an external image analysis front-end for accurate segmentation; poor segmentation leads to invalid AV-pairs. Additionally, the heuristics used for determining the "most general" description could be further refined. Future work suggests extending this 2D symbolic approach to 3D object recognition, where varying poses add significant complexity.

Summary updated

BibTeX
@inproceedings{cromwell1991automatic,
  author = {Robert L. Cromwell and Avinash C. Kak},
  title = {{Automatic Generation of Object Class Descriptions Using Symbolic Learning Techniques}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure