Beyond Incremental Processing: Tracking Concept Drift

Jeffrey C. Schlimmer, Richard H. GrangerAAAI 1986

In the mid-1980s, machine learning research primarily focused on static environments. Models were typically trained to recognize fixed patterns, with the expectation that the underlying definitions would not change during testing. However, real-world data is often dynamic: sensors can degrade, environments evolve, and previously reliable indicators can become obsolete.

In their 1986 paper, Schlimmer and Granger introduced STAGGER, an incremental learning system designed to handle "concept drift"—the phenomenon where the target concept's definition changes over time. STAGGER was a pioneer in addressing the challenges of learning in non-stationary environments.

The Problem: Noise vs. Concept Drift

The authors identified a significant limitation in early AI systems like ID3 or Version Spaces: they assumed fixed feature-label relationships. These systems struggled with two distinct types of inconsistencies:

  1. Noise: Random or systematic errors in data (e.g., a faulty sensor).
  2. Concept Drift: Fundamental shifts in the environment (e.g., a change in the rules of a task).

The core challenge for an adaptive system is attribution: when a mistake occurs, is it due to transient noise that should be ignored, or a fundamental change in the concept that requires a model update?

Methods: Distributed Concept Representation

STAGGER employs a "distributed concept representation" using a set of dually weighted Boolean functions. This hybrid approach combines statistical robustness with symbolic flexibility.

Bayesian Weighting

Each feature or characterization is assigned two Bayesian weights:

  • Logical Sufficiency ($LS$): How much the presence of a feature increases the odds of the concept being present.
  • Logical Necessity ($LN$): How much the absence of a feature decreases those odds.

If existing features fail to maintain accuracy, STAGGER uses search operators (AND, OR, NOT) to generate new, more complex Boolean characterizations. The system employs a beam search that starts with simple features and expands toward both more specific and more general boundaries based on performance.

The search space of Boolean characterizations ranging from maximally specific to maximally general.

To prevent overfitting, STAGGER includes a backtracking mechanism. If a newly created complex feature performs worse than its simpler components, the system prunes it and reactivates the simpler characterizations.

Key Insights: The "Old Dog" Effect

STAGGER incorporates psychological principles of contingency, where learning only occurs if a cue makes an outcome significantly more likely. A notable emergent property of the system is the "Old Dog" effect: resiliency to change is inversely proportional to the amount of training. A concept reinforced over hundreds of trials becomes deeply entrenched in the weights, making it significantly harder for the system to "unlearn" when drift eventually occurs, mirroring biological learning behaviors.

Key Results

The system was evaluated using simulated geometric domains where objects were defined by size, color, and shape.

Successful Drift Tracking

In experiments with successive concept definitions (e.g., shifting from "red and squarish" to "small or circular"), STAGGER demonstrated a robust ability to adapt. While accuracy dropped immediately following a concept shift, the system successfully recovered by searching for and weighting new characterizations.

STAGGER's classification accuracy drops when the target concept changes but recovers as the system adapts.

Noise Immunity and Overtraining

STAGGER also proved resilient to noise. When subjected to 25% systematic noise, the Bayesian weights allowed the system to maintain high classification accuracy without misinterpreting the noise as concept drift. However, as predicted by the "Old Dog" effect, increased training on a stable concept made the system significantly slower to adapt when that concept finally drifted.

Limitations and Legacy

While groundbreaking, STAGGER has several limitations:

  • Boolean Constraints: It is restricted to Boolean combinations of attribute-value pairs and cannot handle relational descriptions.
  • Supervised Learning: The system requires explicit feedback for every instance to update its weights.
  • Single Concept Focus: It tracks a single target concept rather than performing unsupervised conceptual clustering.

Despite these constraints, STAGGER remains a foundational work in the study of concept drift, providing an early computational account of how learning systems can balance stability and plasticity in a changing world.

Summary updated

BibTeX
@inproceedings{schlimmer1986beyond,
  author = {Jeffrey C. Schlimmer and Richard H. Granger},
  title = {{Beyond Incremental Processing: Tracking Concept Drift}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}
Figure