Complementary Discrimination Learning with Decision Lists

Wei-Min ShenAAAI 1992

Introduction

Presented at AAAI-92, CDL2 is a novel learning algorithm that bridges the gap between Piaget-inspired cognitive theories and formal symbolic logic. By integrating "Complementary Discrimination Learning" with "Decision Lists," CDL2 provides an efficient framework for learning complex concepts incrementally—one example at a time—without sacrificing the expressive power of the representation.

The Challenge of Incremental Concept Learning

In machine learning, concept learning involves inferring general rules from specific examples. Historically, this sub-field has faced two major hurdles:

  1. Representation Efficiency: Efficiently representing a concept and its complement (opposite) often required complex Boolean formulas that were computationally expensive to update.
  2. Incrementality: While batch processors are powerful, they require all data upfront. Incremental algorithms, which learn continuously like humans, have traditionally been slower or less expressive.

In 1987, Ronald Rivest demonstrated that Decision Lists (ordered sequences of if-then rules) are highly expressive and efficient. However, he left an open challenge: how to learn these structures incrementally. CDL2 addresses this gap.

The CDL2 Methodology

CDL2 combines two foundational concepts:

  • Complementary Discrimination Learning (CDL): Inspired by developmental psychology, this approach focuses on the boundary between a concept and its complement. When the learner makes an error, it "shrinks" the current hypothesis to exclude the mistake and "expands" the complement.
  • Decision Lists (DL): A DL is a list of rules: (if test1 then value1), (if test2 then value2).... The first matching rule determines the outcome.

Innovation: Behavioral Incrementality

When CDL2 encounters a misclassified instance, it identifies the "overly general" rule responsible. It then calculates the "difference" between the new instance and previous examples of that rule to "break" or "shrink" it into more specific sub-rules. Crucially, CDL2 extends standard Decision Lists to handle multiple concepts and includes a merging mechanism to maintain model parsimony.

Experimental Evaluation

The algorithm was tested across several domains, including a 6-bit Multiplexor, Quinlan’s Chess Task (551 configurations), Noisy LED Displays, and Hand-written Numeral Recognition (3,301 digits).

Performance and Compactness

On the chess end-game task, CDL2 demonstrated significant advantages over existing methods. As shown in the table below, CDL2 achieved a massive speedup—approximately 200 times faster than ID5r—while producing a significantly more compact model (36 decisions compared to 78-85 nodes in decision tree variants).

Table 1: Performance comparison on the Chess task, highlighting CDL2's speed and compactness.

Robustness to Noise

In the challenging hand-written numeral task, characterized by inconsistent and noisy data, CDL2 maintained high training accuracy. While its test accuracy was lower than specialized neural networks, it outperformed traditional symbolic learners like ID3 in handling data inconsistencies and training efficiency.

Table 2: Results on the Hand-written Numeral Recognition task.

Key Insights

  • The "Blocking" Power of Lists: The ordered nature of Decision Lists allows for easy updates; fixing an error often involves simply inserting a more specific rule earlier in the list to "block" the incorrect general rule.
  • Natural Complements: Decision Lists are "closed under complementation," allowing a single structure to represent both a concept and its opposite without redundancy.
  • Efficiency through Discrimination: By repartitioning the hypothesis space based on surprising instances rather than growing concepts from seeds, CDL2 identifies critical boundaries faster than traditional algorithms.

Limitations and Future Directions

Despite its strengths, CDL2 has areas for improvement:

  • Storage Costs: While behaviorally incremental, it currently stores some previous examples to compute differences. Future iterations could use statistical summaries to reduce memory overhead.
  • Geometric Constraints: The algorithm is optimized for finding "hyperrectangles" and may struggle with highly non-linear concept shapes.
  • Overfitting: Like many high-accuracy learners, CDL2 can overfit noisy data. Integrating domain-specific knowledge or advanced pruning techniques remains a goal for future research.

Summary updated

BibTeX
@inproceedings{shen1992complementary,
  author = {Wei-Min Shen},
  title = {{Complementary Discrimination Learning with Decision Lists}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}

Loading related content...

Figure