Introduction
In the late 1980s, machine learning transitioned from controlled laboratory environments to large-scale real-world applications. This shift highlighted a significant bottleneck: the computational explosion associated with first-order representation languages. While these languages are essential for describing complex relational data—such as the spatial relationships between parts of an object—their complexity grows exponentially with the number of training examples. This paper presents an integrated scheme that combines characterization and discrimination to prune training data effectively, focusing the learner's resources on the most informative "near miss" examples.
The Three-Stage Learning Scheme
The proposed method moves away from traditional data reduction techniques, which often rely on simple attribute-value pairs or incur high computational costs. Instead, it employs a "bootstrap" approach consisting of three sequential phases:
1. Characterization
The process begins by analyzing only the positive examples of a concept. The goal is to generate a rough, computationally inexpensive approximation ($\phi'$). This description captures the commonalities among positive instances but is intentionally "loose"—it may inadvertently cover some negative examples.
2. Discrimination and the "Near Miss"
This stage is the core of the innovation. The system uses the rough characterization from the first step to filter the negative examples. A "near miss" is operationally defined as a negative example that the initial characterization incorrectly labeled as positive. By focusing incremental learning exclusively on these near misses, the system avoids processing the vast majority of negative examples that are too dissimilar to provide useful boundary information.
3. Simplification
Once a consistent description is achieved, the system prunes the resulting rule. Elements that were necessary for the initial characterization but are redundant for distinguishing between classes are removed, leading to a more robust and simpler final formula.
Experimental Evaluation
The researchers tested the scheme across two distinct domains to measure its efficiency and accuracy.
Michalski’s Trains
A classic benchmark in inductive learning, this domain requires the system to distinguish between trains heading East and West based on the properties (shape, load, number) and sequence of their carriages. This task tests the system's ability to handle structured, relational data.
2D Image Recognition
To test the scheme in a "noisy" real-world environment, the authors used a dataset of 198 printed capital letters. Captured via a TV camera, these images were decomposed into primitives like lines and curves. This domain is significantly more complex than the artificial train benchmark, providing a rigorous test of the scheme's scaling capabilities.
Results and Discussion
The integrated approach demonstrated substantial improvements in learning efficiency without sacrificing accuracy. Efficiency was measured by the "Time Ratio"—the computation time of a traditional discrimination method divided by the time taken by the new integrated scheme.
- Trains Domain: The system achieved a 1.4x speedup.
- 2D Image Recognition: The system achieved a 3.3x speedup, reducing processing time from 1016 seconds to just 311 seconds.
A key insight is that the method's performance improves as the complexity and noise of the data increase. In simple domains, the overhead of the initial characterization phase might outweigh the benefits; however, in large-scale relational datasets, the "near miss" filter becomes a powerful tool for maintaining computational tractability.
Conclusion
By operationalizing the concept of the "near miss," the authors provided a practical solution to the scaling problems of first-order inductive learning. The integrated characterization and discrimination scheme ensures that the learner focuses only on the most informative data points, achieving significant speedups in complex image recognition tasks while maintaining the integrity of the learned knowledge.
Summary updated