Complementary Discrimination Learning: A Duality Between Generalization and Discrimination

Wei-Min ShenAAAI 1990

Author: Wei-Min Shen (1990)

Abstract

This paper introduces a fundamental bridge between two classic pillars of machine learning: generalization and discrimination. By formalizing the principle that "discriminating a concept is equivalent to generalizing its complement," the author presents the Complementary Discrimination Learning (CDL) algorithm. CDL learns concepts by simultaneously refining both a target concept and its negation, allowing for efficient incremental learning and robust noise handling without the need for pre-defined generalization hierarchies.

Introduction

In the early development of artificial intelligence, learning mechanisms were typically categorized into two distinct camps. Learning by Generalization involves starting from specific examples and moving toward general rules based on similarities (e.g., Winston’s arch learning). Conversely, Learning by Discrimination starts with general rules and narrows them down based on differences (e.g., ID3 decision trees).

While many systems attempted to utilize both approaches, the intrinsic relationship between them remained poorly defined. Furthermore, most "bi-directional" learners of the era required a priori domain knowledge, such as fixed generalization hierarchies, to function. Shen’s work seeks to unify these approaches into a single, flexible framework capable of learning any subset of an instance space without being constrained by pre-defined hierarchies.

The Duality Principle and CDL Algorithm

The core innovation of the paper is the Duality Principle: the realization that generalization and discrimination are two sides of the same coin. Specifically, one can achieve the effect of discrimination on a concept $C$ by performing generalization on its complement $\bar{C}$.

Incremental Revision

Unlike standard learners that only track a target concept $C$, the CDL algorithm learns both $C$ and $\bar{C}$ in parallel. When the system encounters a classification error (e.g., a false positive where an instance is predicted as positive but is actually negative), it does not merely adjust weights. Instead, it identifies the minimal differences between the current "troublesome" instance and previous correctly classified instances.

If $C$ is found to be over-general (covering too much), CDL discriminates $C$ by conjoining it with the identified differences. Simultaneously, it generalizes $\bar{C}$ by setting it to the negation of the newly refined $C$. This allows the algorithm to "jump" to new hypotheses based on syntactic differences rather than crawling slowly through a version space.

Representation and Noise Handling

Concepts are represented using Propositional Logic (DNF or CNF), facilitating integration with autonomous problem-solving systems. To handle real-world data, CDL introduces a parameter $M$, representing the percentage of instances a difference must cover. This prevents the algorithm from overfitting to isolated noisy data points.

Experimental Evaluation

Noise Tolerance: The LED Task

The author evaluated CDL using the classic Noisy LED Display benchmark. The goal is to identify decimal digits from a 7-segment display where each segment has a 10% chance of being inverted.

Figure 1: Learning curve of CDL on the noisy LED display task, showing stabilization at the theoretical upper bound of accuracy.

As shown in Figure 1, CDL reached a prediction rate of approximately 74%, which is the theoretical upper bound for 10% noise. The algorithm achieved this within 350-400 instances, demonstrating significant stability and outperforming contemporary non-incremental algorithms like IWN.

Efficiency: The Multiplexor Domain

CDL was also tested on the 6-bit Multiplexor task—a noise-free but difficult domain where the relevance of data bits depends entirely on address bits. This task often causes instability in noise-tolerant algorithms.

Figure 5: Comparative performance of CDL against ID-series algorithms on the 6-bit multiplexor task.

In this domain, CDL reached 100% accuracy in just 52 training events. As illustrated in Figure 5, CDL matched or exceeded the performance of ID3 (53 events) and significantly outperformed ID4 and ID5 variants, which required more events or failed to remain stable during the learning process.

Conclusion

Complementary Discrimination Learning provides a robust framework for incremental learning by exploiting the syntactic duality between generalization and discrimination. By relying on raw differences between instances rather than fixed categories, CDL can learn arbitrary subsets of an instance space efficiently. While the current implementation requires significant memory to store previous instances for difference calculation, the results on LED and Multiplexor tasks suggest that the duality approach is a powerful tool for autonomous concept discovery.

Summary updated

BibTeX
@inproceedings{shen1990complementary,
  author = {Wei-Min Shen},
  title = {{Complementary Discrimination Learning: A Duality Between Generalization and Discrimination}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure