PaperlayerView exact revision on arXiv

Source-linked AI summary

Concept Drift Adaptation by Exploiting Historical Knowledge

Yu Sun, Ke Tang, Zexuan Zhu, Xin Yao

arXiv:1702.03500v1cs.LG

TL;DR

Incremental learning with concept drift must decide which historical models to preserve and how to use them. DTEL adapts preserved models to new data and selects them for diversity; across synthetic and real-world streams, it significantly outperformed the compared approaches on average accuracy.

  • Problem

    Ensemble methods for incremental learning with concept drift must determine which historical models to preserve and how to exploit them for future learning.

    Source: §I · p. 1

  • Method

    DTEL uses diversity to preserve historical models, adapts them to new data as initial models, and combines them with a model built from scratch.

    Source: §I · p. 1, §III · p. 3, A. A Diversity-based Model Preservation · p. 4

  • Results

    DTEL had a Friedman rank of 1.2895 and significantly outperformed all compared approaches on average accuracy across synthetic and real-world data streams.

    Source: 2) Results · p. 8

  • Takeaways & Limitations

    Empirical studies on synthetic and real-world streams demonstrate DTEL’s advantages over a number of state-of-the-art incremental learning methods.

    Source: §V · p. 10

Abstract

from arXiv · show

Incremental learning with concept drift has often been tackled by ensemble methods, where models built in the past can be re-trained to attain new models for the current data. Two design questions need to be addressed in developing ensemble methods for incremental learning with concept drift, i.e., which historical (i.e., previously trained) models should be preserved and how to utilize them. A novel ensemble learning method, namely Diversity and Transfer based Ensemble Learning (DTEL), is proposed in this paper. Given newly arrived data, DTEL uses each preserved historical model as an initial model and further trains it with the new data via transfer learning. Furthermore, DTEL preserves a diverse set of historical models, rather than a set of historical models that are merely accurate in terms of classification accuracy. Empirical studies on 15 synthetic data streams and 4 real-world data streams (all with concept drifts) demonstrate that DTEL can handle concept drift more effectively than 4 other state-of-the-art methods.

I. INTRODUCTION

Incremental learning updates models as new data chunks arrive, raising the question of how knowledge from earlier tasks can support future ones. With concept drift, DTEL addresses which historical models to preserve and how to use them, while the learning goal at each step is a good model for the current distribution.

I. INTRODUCTION

  • Incremental learning updates models when new training-data chunks arrive, without requiring access to or reprocessing of earlier data.Each chunk forms a subtask, prompting the question of whether knowledge gained in one can benefit later tasks.Source: §I · p. 1
  • Concept drift makes it important to decide which historical models to preserve and how to exploit them for future learning.DTEL addresses these questions by preserving diverse models and using them as initial points for training on new data.Source: §I · p. 1

A. Basic Concepts and Notations

  • A data chunk at time t comes from distribution p_t(x, y), and concept drift is a change in that underlying distribution.A single example is a special case of a chunk, commonly called online learning.Source: A. Basic Concepts and Notations · pp. 1–2
  • At each time step, the learning goal is to obtain a good model for the current distribution, and the full process generates at least t models.The per-step objective is expressed through expected loss over the hypothesis set.Source: A. Basic Concepts and Notations · p. 2

B. Concept Drift Handling Techniques

Concept-drift methods either update models using recent data, detect drift and rebuild, or preserve historical models for reuse. For ensemble approaches, both the use of historical models and their bounded preservation require design choices.

B. Concept Drift Handling Techniques

  • Sliding-window methods update with recent and new data, while drift-detection methods rebuild from scratch when drift is detected.The cited sliding-window methods mainly apply to online learning; detection-based methods update the current model when no drift is detected.Source: B. Concept Drift Handling Techniques · p. 2
  • Preserving historical models can help when past concepts recur or correlate with current ones, but drift can also make historical models harmful.Ensemble methods therefore face the problem of gaining from historical models while preventing negative effects.Source: B. Concept Drift Handling Techniques · p. 2
  • SEA, DIC, AUE2, and Learn++.NSE combine historical-model outputs with a model built on the new chunk, whereas TIX uses historical outputs as added features.Their combination schemes include majority or weighted voting, dynamic selection, and weighting based on current and past performance.Source: B. Concept Drift Handling Techniques · p. 2
  • Because storage and computation constrain archive size, selection is needed, but existing approaches generally assess model quality by accuracy rather than explicit ensemble diversity.SEA assesses ensemble accuracy after replacement, while AUE2 evaluates candidate models directly; adaptations of other schemes had not been assessed.Source: B. Concept Drift Handling Techniques · pp. 2–3

III. THE PROPOSED APPROACH

DTEL adapts preserved historical models to new data instead of directly combining their outputs, then combines the adapted models with a model built from scratch. It preserves historical models using diversity, with an archive procedure that removes the model whose removal maximizes remaining diversity.

III. THE PROPOSED APPROACH

  • Historical models from a different concept may perform poorly, but DTEL uses them as initial candidates for transfer to the current concept.The paper motivates this by treating earlier and current concepts as correlated source and target domains.Source: §III · p. 3
  • DTEL adapts each preserved historical model to current data before combining the adapted models with a model constructed from scratch.This differs from directly combining historical-model outputs.Source: §III · p. 3

A. A Diversity-based Model Preservation

  • DTEL preserves historical models for diversity rather than accuracy, since different preserved models may adapt to different future concepts.A good final ensemble can still result if at least one preserved model adapts to the new concept and the combination scheme filters poor models.Source: A. A Diversity-based Model Preservation · p. 4
  • When its archive is full, DTEL temporarily adds the new model and removes whichever model leaves the greatest diversity among those remaining.The paper uses Yule’s Q-statistic as its diversity measure; Q compares the classification outcomes of a pair of models.Source: A. A Diversity-based Model Preservation · p. 4

B. Adapting Historical Models through Knowledge Transfer

DTEL transfers historical decision trees to each new chunk while preserving their structure and adapting their decision boundaries. It combines adapted trees with a fresh tree, while retaining newly trained trees—not adapted ones—in its historical archive.

B. Adapting Historical Models through Knowledge Transfer

  • The transfer method routes new-chunk examples to historical-tree leaves, resets their labels, and grows subtrees where stopping criteria permit.This retains the historical tree structure while fitting the new chunk.Source: B. Adapting Historical Models through… · p. 4
  • Adapted trees combine current data with historical structure, fit the current chunk, may not match one data distribution, and are discarded rather than archived.Source: B. Adapting Historical Models through… · p. 4

C. Detailed Steps of DTEL

  • DTEL adapts archived trees and trains a fresh tree on each new chunk, then combines the adapted trees and fresh tree into the current ensemble.The fresh tree updates the historical archive; adapted trees are not retained there.Source: C. Detailed Steps of DTEL · pp. 4–5
  • DTEL uses weighted voting: adapted-tree weights depend on chunk error, while the fresh tree’s weight uses random-classifier error as its reference.The passage identifies the adapted-tree error as MSE and defines the reference error as the mean square error of a random classifier.Source: C. Detailed Steps of DTEL · pp. 4–5

IV. EXPERIMENT

The experiment compares four representative methods across per-chunk classification, whole-stream performance, and time efficiency, using decision trees as base learners for a fair comparison.

  • Evaluation covers classification performance for each chunk, overall performance across each stream, and time efficiency.Source: §IV · p. 5
  • The experiment compares SEA, Learn++.NSE, AUE2, and TIX, which differ in how they adapt to concept drift and exploit historical knowledge.SEA and Learn++.NSE use historical models directly, whereas AUE2 updates them with the new chunk; their ensemble weighting schemes also differ.Source: §IV · p. 5
  • For fairness, the compared methods use decision-tree base learners; AUE2 uses a Hoeffding tree, while the others use CART.The ensemble size is 25 unless otherwise noted, and archive size is the experiment’s only parameter to set for SEA, AUE2, and DTEL.Source: §IV · p. 5

1) Datasets:

The synthetic experiments use five widely used concept-drift types and vary drift severity and chunk size. Each stream has 120 chunks and 10% noise, with separate training and test chunks at each step.

  • SEA uses three features, with x1 and x2 relevant and x3 noisy; drift changes θ during learning.Source: 1) Datasets · p. 5
  • ROT simulates drift by rotating the decision boundary or data points; the experiment uses six classes and rotates evenly during learning.Source: 1) Datasets · p. 5
  • CIR uses a circular decision boundary in two dimensions and simulates drift by changing its radius every 25 data chunks.Source: 1) Datasets · p. 5
  • SIN labels data using a sine curve in two dimensions, with θ changed evenly to generate distribution change.Source: 1) Datasets · p. 6
  • STAGGER uses categorical color, shape, and size features, with drift simulated by changing decision-rule items.Source: 1) Datasets · p. 6
  • Across five synthetic drift types, the study varies drift severity and chunk size and uses 120 chunks with 10% noise per stream.Two chunks are generated at each step: one for training and one for testing.Source: 1) Datasets · pp. 5–6

2) Results:

On synthetic data streams, DTEL generally achieved strong, stable accuracy across several types and degrees of concept drift. Pairwise tests found it significantly better than the compared algorithms overall.

(c) SEA500G

  • On SEA streams, DTEL remained steady across chunks and drift severity, while AUE2 sometimes led but dropped in accuracy under drift.Source: 2) Results · p. 6

(f) ROT500G

  • On ROT streams, all compared algorithms fluctuated dramatically, but DTEL had the highest accuracy on every chunk.Source: 2) Results · p. 6

(i) CIR500G

  • On CIR streams, performance was similar across algorithms, though greater drift severity appeared not to affect DTEL on CIR200A and CIR200G as it affected others.Source: 2) Results · p. 6

(l) SIN500G

(o) STA500G

  • On STA streams, DTEL and TIX had high, low-variance accuracy; TIX performed best, while AUE2 led on SEA200G but had higher variance than DTEL.Across most streams, DTEL showed high accuracy and low standard deviation.Source: 2) Results · p. 6, (o) STA500G · p. 7, Figure 2 · p. 7

2) Results:

  • DTEL performed statistically significantly better than the compared algorithms on the synthetic data streams in pairwise comparisons.The authors report the test at the 95% confidence level.Source: (o) STA500G · p. 8

1) Datasets:

The evaluation uses four real-world data streams spanning environmental, card-game, electricity-market, and click-through prediction data. Their chunk sizes and composition differ.

  • The four streams are Covertype, PokerHand, Electricity, and Click-through Rate Prediction (CTRPrediction).Source: 1) Datasets · p. 8
  • Covertype has 51 cartographic variables and six forest-cover classes; PokerHand has five numerical and five ordinal features with ten hand classes.Source: 1) Datasets · p. 8
  • Electricity contains 45,312 dated instances, eight features, and a label indicating whether prices move up or down.Source: 1) Datasets · p. 8
  • CTRPrediction uses 600,000 examples with 100 features, sampled at 20,000 examples per day over 30 days.Chunk sizes were 1,000 for the first three streams and 10,000 for CTRPrediction; each CTR chunk represents half a day's observations.Source: 1) Datasets · p. 8

2) Results:

Across synthetic and real-world streams, DTEL significantly outperformed the compared approaches overall, although results varied across individual real-world streams and transfer added computational cost.

  • Real-world drift adaptation could not be analyzed precisely because drift occurrences and behaviors were unknown.Source: 2) Results · p. 8
  • On real-world streams, DTEL was stable on Covertype and generally best on CTRPrediction, while SEA led PokerHand and no clear winner emerged on Electricity.Source: 2) Results · p. 8, Figure 3 · p. 9
  • CTRPrediction's consecutive chunks showed accuracy near 100% followed by roughly 50%, consistent with click habits differing between work and leisure periods.Source: 2) Results · p. 8
  • 1.2895 was DTEL's rank value in a Friedman test that found it significantly better than all compared approaches on average accuracy.Source: 2) Results · p. 8
  • DTEL was the slowest approach and took about an order of magnitude longer in some cases, but parallelizing independent transfers could reduce runtime by an order of magnitude.Source: 2) Results · p. 9

C. Influence of Archive Size

The archive-size analysis recommends retaining more than 20 historical models, while the conclusion emphasizes DTEL's diversity-based preservation and transfer adaptation, alongside computational and base-learner limitations.

C. Influence of Archive Size

V. CONCLUSIONS AND FUTURE WORK

  • DTEL preserves previously trained models using a diversity-based criterion and adapts them to the current concept through transfer learning.Source: §V · p. 10
  • DTEL is more computationally costly than compared methods, and the study uses decision trees while leaving other base learners and transfer methods for future investigation.Source: §V · p. 10

Related papers

Loading 1702.03500v1…