Source-linked AI summary
Characterizing Concept Drift
Geoffrey I. Webb, Roy Hyde, Hong Cao, Hai Long Nguyen, Francois Petitjean
TL;DR
Deployed machine-learning models face changing data distributions, while prior concept-drift categories lacked rigorous formal and quantitative characterization. The paper introduces quantitative measures and formal definitions that produce a comprehensive taxonomy, clarify ambiguities, and support more objective analysis and future online-learning design.
Problem
Changing distributions can deteriorate deployed model performance, but prior concept-drift definitions were often qualitative, informal, and insufficiently rigorous for objective analysis.
Method
The paper develops quantitative drift measures and formal definitions based on a model of stable-concept periods interspersed with drift.
Results
The paper provides a comprehensive set of formal definitions and quantitative measures that clarify ambiguities and support more objective evaluation of stream-learning performance.
Takeaways & Limitations
The framework provides a foundation for developing technologies that detect, characterize, and resolve concept drift and for designing more robust online-learning systems.
Takeaways & Limitations
The formal qualitative definitions assume streams contain stable periods separated by drift, an assumption the authors identify as questionable for many streams.
Abstract
from arXiv · showhide
Most machine learning models are static, but the world is dynamic, and increasing online deployment of learned models gives increasing urgency to the development of efficient and effective mechanisms to address learning in the context of non-stationary distributions, or as it is commonly called concept drift. However, the key issue of characterizing the different types of drift that can occur has not previously been subjected to rigorous definition and analysis. In particular, while some qualitative drift categorizations have been proposed, few have been formally defined, and the quantitative descriptions required for precise and objective understanding of learner performance have not existed. We present the first comprehensive framework for quantitative analysis of drift. This supports the development of the first comprehensive set of formal definitions of types of concept drift. The formal definitions clarify ambiguities and identify gaps in previous definitions, giving rise to a new comprehensive taxonomy of concept drift types and a solid foundation for research into mechanisms to detect and address concept drift.
1 Introduction
Concept drift threatens deployed machine-learning models because data distributions change over time, while prior drift definitions were often qualitative, informal, and ambiguous. The paper introduces quantitative measures and formal definitions to clarify drift types and support objective evaluation and future detection and handling research.
- Changing data distributions can deteriorate the performance of models trained on historical data.This motivates mechanisms for detecting and handling concept drift.
- Quantitative drift measures are presented as more objective and exact than qualitative measures, which are subjective and imprecise.
- The paper proposes core quantitative measures and a framework for developing further measures and formal drift definitions.
- Formal definitions clarify ambiguities in prior categorizations, including the relationship between incremental and gradual drift and which examples count as gradual.
- The resulting framework and taxonomy provide a foundation for research on detecting, characterizing, resolving, and adapting to diverse concept drift types.
- The paper is broadly relevant to deployed learned models and stream-mining tasks beyond classification, including clustering, association discovery, and outlier detection.
- The paper does not directly address how to detect and handle concept drift from data, leaving application of its conceptual tools to future research.
2 Initial Definitions
The paper frames its analysis around time-stamped data streams, probabilistic concepts, and distributions that may change over time. It defines concepts and drift so the later quantitative characterization can apply beyond a single learning setting.
- 2.1 Data Streams: The analysis is couched in data streams, but its fundamental issues and techniques apply whenever models learned from historical data are used in future contexts.
- 2.1 Data Streams: A data stream is a time-stamped dataset from which models learn using earlier observations and are applied to later observations.
- 2.1 Data Streams: For classification, the paper distinguishes class labels Y and covariates X and represents each object as a pair of attribute values and label.
- 2.2 Concepts and concept drift: A concept is defined probabilistically for stream classification as the joint distribution P(X, Y), equivalent to specifying P(Y) and P(X | Y).
- 2.2 Concepts and concept drift: The paper notes that its formalization supports classification and has broader applicability beyond classification models.
- 2.2 Concepts and concept drift: Concept drift occurs between times t and u when the relevant distributions change.
3 Quantitative measures of drift
The paper develops quantitative measures for comparing concepts and describing how drift evolves over time. These measures can be applied to probabilistic relationships and to several distributions relevant to classification.
- Concept drift can be quantified even when concepts are probabilistic relationships between X and Y values.
- The framework leaves the distribution-distance function unspecified, with possible choices including Kullback-Leibler Divergence and Hellinger Distance.The paper uses Hellinger Distance in its case study because it satisfies desirable distance properties discussed there.
- Drift magnitude measures the distance between concepts at the start and end of a drift period.The distance function returns a non-negative value and may be chosen according to the domain.
- Drift duration is the elapsed time from the start time t to the end time u, expressed as Duration_t,u = u − t.
- Path length measures cumulative deviation during drift and can exceed drift magnitude when the path is non-monotone.Gradual and incremental examples can have equal magnitude but different path lengths.
- Drift rate quantifies how rapidly a distribution changes at a time or on average between two times.
- In classification, drift distances may compare joint, covariate, class, posterior, or likelihood distributions.
4 Qualitative characterization of drift types
The paper formalizes drift subjects and scope, distinguishing changes in class and covariate distributions and defining how broadly those changes affect the instance space. It also proposes pure forms that isolate posterior-only or covariate-only changes while retaining more general drift definitions.
- Taxonomy: The taxonomy formalizes drift categories and provides formal definitions for each category.It is summarized in Fig. 2 and is intended to clarify ambiguities in earlier informal terminology.
- Drift subject: Concept drift can involve changes in P(Y), P(Y | X), P(X | Y), or P(X), all of which change the joint distribution P(X, Y).The paper notes that these distributional aspects are inter-related.
- Drift subject: Class drift changes P(Y | X), while covariate drift changes P(X) over time.The paper gives changing tax-law relationships as an example of class drift and changing customer demographics as an example of covariate drift.
- Definition boundaries: Earlier definitions may impose questionable causal or conditional-distribution constraints that exclude plausible real-world class-drift cases.The paper argues that many learning systems use correlations without requiring a particular causal direction.
- Pure drift forms: The paper proposes pure class drift and pure covariate drift to describe cases where only posterior probabilities or covariate distributions change.It argues that the more general class and covariate drift definitions remain useful when both forms occur together.
- Drift scope: Drift scope measures the proportion of Dom(X) where P(Y | X) changes, distinguishing subconcept drift from full-concept drift.Scope affects the ease of detecting changes and how much of a model must be updated.
4.3 Drift magnitude
Drift magnitude characterizes how much one stable concept differs from the next. The appropriate response can depend on this magnitude, even when the drift is abrupt.
- Magnitude and handling: Drift magnitude affects how an abrupt change should be handled.For abrupt minor drift, refining the existing model may be appropriate; for abrupt major drift, abandoning it and starting afresh may be preferable.
- Magnitude and handling: Abrupt minor drift may call for retaining and refining the model for concept a, whereas abrupt major drift may call for replacing it.These are examples of handling choices tied to the size of the change.
4.4 Drift Frequency
Drift frequency measures how often concept changes begin within a specified interval. Higher frequency means shorter separations between drift events, while lower frequency means longer intervals.
- Definition: Drift frequency refers to how often concept drifts occur over a defined period.The paper defines frequency relative to a time interval [t, u].
- Interpretation: A high frequency means new drifts begin within short intervals, whereas a low frequency means long intervals separate drifts.The paper illustrates this by comparing faster transitions in Alice’s exercise pattern with slower transitions in Bob’s.
4.5 Drift Duration
Drift duration describes how a transition unfolds, including abrupt, extended, gradual, incremental, probabilistic, and blip forms. The formalization distinguishes related categories that prior literature sometimes conflated.
- Duration: Abrupt drift changes suddenly from concept a to concept a+1, whereas extended drift unfolds over a longer period.The paper uses a market crash and a recession as examples of abrupt and extended drift, respectively.
- Duration: The threshold δ defining the maximum duration of abrupt drift depends on the data stream’s context.Different streams may therefore use different abrupt-drift duration thresholds.
- Blip drift: Blip drift is abrupt drift with a very short-lived concept replacing the dominant concept.Unlike an outlier, a blip is a short sequence of examples belonging to one concept.
- Gradual and incremental drift: Gradual drift consists of small changes over time, while incremental drift steadily moves away from concept a toward concept a+1.Incremental drift requires distance from the old concept to increase and distance to the new concept to decrease at each time step.
- Probabilistic drift: Probabilistic drift occurs when two concepts alternate in prevalence, with one initially dominant and the other eventually dominant.The new concept’s probability is modeled by a monotonically increasing function, and probabilistic drift may or may not be incremental.
- Relations among types: Incremental and probabilistic drift are distinct but related: either may occur without the other.The paper’s formal definitions make this distinction explicit despite prior literature treating them as equivalent.
4.8 Drift Recurrence
Drift recurrence describes concepts reappearing in a stream, with cyclical drift being recurrence in a specific order. Its periodicity has multiple dimensions, including which timings or durations remain fixed.
- Drift recurrence occurs when a new concept is a recurrence of a pre-existing concept in the data stream.
- Cyclical drift is recurring drift in which two or more concepts recur in a specific order.
- Periodicity can vary across dimensions: winter’s timing and duration may vary, whereas working-day boundaries may remain precise.
- Fixed-frequency cyclical drift constrains the total cycle duration, such as the seasons recurring over 365.24 days.
- Other fixed cyclical patterns constrain concept duration, drift duration, concept onset, or drift onset.
- Varying-frequency and varying-duration or onset variants are defined by negating the corresponding fixed definitions.
4.9 Drift Predictability
Drift predictability concerns how predictable any aspect of drift is, but formalizing every possible aspect is impractical. Among the defined types, fixed timing or duration patterns are inherently predictable because they contain inferable constants.
- Drift predictability describes how predictable an aspect of drift is, including its onset, end, subject, or other properties.
- Formal definitions for every type of drift predictability would be impractical because the possible aspects of drift form a long list.
- Fixed frequency, concept duration, drift duration, concept onset, and drift onset drift are inherently predictable because each contains an inferable constant.
5 Case studies
The case studies use synthetic abrupt class and covariate drifts to examine how MOA classifiers respond. Results reveal distinct recovery patterns and explain why pure covariate drift can substantially affect tree learners.
- Study design: The pilot study tests claims about quantitative drift characterizations using synthetic streams with abrupt pure class or pure covariate drift.
- Study design: The experiments use MOA classifiers, including ensembles, drift-detection methods, and Hoeffding tree variants.
- Study design: The data consist of 100 synthetic streams of 300,000 time steps, with abrupt posterior-probability drift at t = 100,000.
- Pure class drift: For Naive Bayes and OzaBoost, larger class-drift magnitudes cause larger immediate error increases and longer recovery times.
- Pure class drift: For HoeffdingAdaptiveTree, HoeffdingOptionTree, HoeffdingTree, and OzaBag, error jumps increase with drift magnitude but recovery takes the same time.
- Pure class drift: For several ensemble and drift-detection methods, initial error increases track drift magnitude, but recovery rates are not ordered by magnitude.
- Pure covariate drift: Pure covariate drift can produce a substantial error jump proportional to drift magnitude, contrary to the expectation that tree models would be little affected.
- Pure covariate drift: Tree learners fail to learn a complete tree because some covariate combinations are substantially less frequent, leaving splits undetected.
6 Discussion
The discussion presents quantitative drift characterization as essential for comparing learner responses and designing detection, remediation, and online-learning mechanisms, while identifying important scope limits and assumptions.
- Experimental evidence: The experiments are preliminary because they examine only one specific pre- and post-abrupt drift concept and do not explain learners’ differing responses.The authors also note the surprising improvement from covariate drift for tree-based learners.
- Experimental evidence: Quantitative drift measures make it possible to relate drift magnitude to learner behavior, including faster Hoeffding Tree recovery and lower final error under greater pure covariate drift.Figure 10 reports learning curves for different drift magnitudes and compares drifted streams with no-drift streams.
- Implications: The taxonomy can guide more thorough experiments, because it makes explicit the drift types that may affect algorithm performance and supports comparisons across different drift forms.The authors specifically connect this role to synthetic data streams used for evaluating algorithms under possible drift types.
- Implications: The framework supports more objective evaluation of stream-mining algorithms by providing formal definitions and quantitative measures for comparing responses across drift scenarios.The proposed measures include cycle duration, drift rate, magnitude, frequency, duration, and path length.
- Implications: The definitions may inform drift-detection and online-learning design, including systems intended to be more robust to diverse drift types and predictable triggers.The paper presents this as a potential application of improved understanding of drift mechanisms.
- Limitations and assumptions: The framework assumes streams consist of stable-concept periods separated by drift periods, an assumption the authors describe as questionable for many streams.The paper also states that real-world quantification may be infeasible when distributions cannot be accurately estimated over time.
7 Conclusion
The paper identifies shortcomings in qualitative descriptions of concept drift and addresses them with quantitative measures and formal definitions. It argues that this framework can support more objective evaluation, better drift-handling mechanisms, and learning techniques robust to more diverse drift types.
- Qualitative drift descriptions rely on subjective thresholds, assume drift-free periods, and provide limited discrimination among drifts of the same general type.
- The paper defines drift magnitude and duration as key quantitative measures, from which rate and path length can be derived.
- The quantitative framework is intended to standardize terminology and provide a rigorous basis for designing mechanisms to detect, characterize, and resolve concept drift.
- The framework is intended to clarify which forms of drift are best handled by different mechanisms.
- The authors identify applications in creating more diverse synthetic drift data, evaluating stream-mining algorithms more objectively, and designing models robust to diverse drift types.