The world is dynamic, in a constant state of flux, while machine learning systems typically learn static models from historical data. Failure to account for the dynamic nature of the world may result in sub-optimal performance when these models of the past are used to predict the present or future. This research investigates this phenomenon of concept drift and how it is best addressed.
Our software for generating synthetic data streams with abrupt drift can be downloaded here.
Our system for describing the concept drift present in real-world data can be downloaded here.
Our Extremely Fast Decision Tree (EFDT) module for MOA can be downloaded here. A third party implementation of EFDT is included in scikitlearn: link.
Publications
Lee, Loong Kuan; Webb, Geoffrey I.; Schmidt, Daniel F.; Piatkowski, Nico
Knowledge and Information Systems, vol. 66, pp. 7527-7556, 2024, ISSN: 0219-3116.
@article{Lee2024,
title = {Computing marginal and conditional divergences between decomposable models with applications in quantum computing and earth observation},
author = {Loong Kuan Lee and Geoffrey I. Webb and Daniel F. Schmidt and Nico Piatkowski},
doi = {10.1007/s10115-024-02191-7},
issn = {0219-3116},
year = {2024},
date = {2024-01-01},
journal = {Knowledge and Information Systems},
volume = {66},
pages = {7527-7556},
publisher = {Springer Science and Business Media LLC},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Lee, Loong Kuan; Piatkowski, Nico; Petitjean, Francois; Webb, Geoffrey I.
Computing Divergences between Discrete Decomposable Models
Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 10, pp. 12243-12251, 2023.
@article{Lee2023,
title = {Computing Divergences between Discrete Decomposable Models},
author = {Loong Kuan Lee and Nico Piatkowski and Francois Petitjean and Geoffrey I. Webb},
doi = {10.1609/aaai.v37i10.26443},
year = {2023},
date = {2023-06-01},
journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
volume = {37},
number = {10},
pages = {12243-12251},
abstract = {There are many applications that benefit from computing the exact divergence between 2 discrete probability measures, including machine learning. Unfortunately, in the absence of any assumptions on the structure or independencies within these distributions, computing the divergence between them is an intractable problem in high dimensions. We show that we are able to compute a wide family of functionals and divergences, such as the alpha-beta divergence, between two decomposable models, i.e. chordal Markov networks, in time exponential to the treewidth of these models. The alpha-beta divergence is a family of divergences that include popular divergences such as the Kullback-Leibler divergence, the Hellinger distance, and the chi-squared divergence. Thus, we can accurately compute the exact values of any of this broad class of divergences to the extent to which we can accurately model the two distributions using decomposable models.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
There are many applications that benefit from computing the exact divergence between 2 discrete probability measures, including machine learning. Unfortunately, in the absence of any assumptions on the structure or independencies within these distributions, computing the divergence between them is an intractable problem in high dimensions. We show that we are able to compute a wide family of functionals and divergences, such as the alpha-beta divergence, between two decomposable models, i.e. chordal Markov networks, in time exponential to the treewidth of these models. The alpha-beta divergence is a family of divergences that include popular divergences such as the Kullback-Leibler divergence, the Hellinger distance, and the chi-squared divergence. Thus, we can accurately compute the exact values of any of this broad class of divergences to the extent to which we can accurately model the two distributions using decomposable models.
Lee, Loong Kuan; Webb, Geoffrey I; Schmidt, Daniel F; Piatkowski, Nico
Computing Marginal and Conditional Divergences between Decomposable Models with Applications
Proceedings of the IEEE International Conference on Data Mining (ICDM), pp. 239-248, IEEE 2023.
@inproceedings{Lee2023a,
title = {Computing Marginal and Conditional Divergences between Decomposable Models with Applications},
author = {Loong Kuan Lee and Geoffrey I Webb and Daniel F Schmidt and Nico Piatkowski},
doi = {10.1109/ICDM58522.2023.00033},
year = {2023},
date = {2023-01-01},
booktitle = {Proceedings of the IEEE International Conference on Data Mining (ICDM)},
pages = {239-248},
organization = {IEEE},
abstract = {The ability to compute the exact divergence between two high-dimensional distributions is useful in many applications but doing so naively is intractable. Computing the alpha-beta divergence\textemdasha family of divergences that includes the Kullback-Leibler divergence and Hellinger distance\textemdashbetween the joint distribution of two decomposable models, i.e chordal Markov networks, can be done in time exponential in the treewidth of these models. However, reducing the dissimilarity between two high-dimensional objects to a single scalar value can be uninformative. Furthermore, in applications such as supervised learning, the divergence over a conditional distribution might be of more interest. Therefore, we propose an approach to compute the exact alpha-beta divergence between any marginal or conditional distribution of two decomposable models. Doing so tractably is non-trivial as we need to decompose the divergence between these distributions and therefore, require a decomposition over the marginal and conditional distributions of these models. Consequently, we provide such a decomposition and also extend existing work to compute the marginal and conditional alpha-beta divergence between these decompositions. We then show how our method can be used to analyze distributional changes by first applying it to a benchmark image dataset. Finally, based on our framework, we propose a novel way to quantify the error in contemporary superconducting quantum computers. Code for all experiments is available at: https://lklee.dev/pub/2023-icdm/code.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
The ability to compute the exact divergence between two high-dimensional distributions is useful in many applications but doing so naively is intractable. Computing the alpha-beta divergence—a family of divergences that includes the Kullback-Leibler divergence and Hellinger distance—between the joint distribution of two decomposable models, i.e chordal Markov networks, can be done in time exponential in the treewidth of these models. However, reducing the dissimilarity between two high-dimensional objects to a single scalar value can be uninformative. Furthermore, in applications such as supervised learning, the divergence over a conditional distribution might be of more interest. Therefore, we propose an approach to compute the exact alpha-beta divergence between any marginal or conditional distribution of two decomposable models. Doing so tractably is non-trivial as we need to decompose the divergence between these distributions and therefore, require a decomposition over the marginal and conditional distributions of these models. Consequently, we provide such a decomposition and also extend existing work to compute the marginal and conditional alpha-beta divergence between these decompositions. We then show how our method can be used to analyze distributional changes by first applying it to a benchmark image dataset. Finally, based on our framework, we propose a novel way to quantify the error in contemporary superconducting quantum computers. Code for all experiments is available at: https://lklee.dev/pub/2023-icdm/code.
Manapragada, Chaitanya; Gomes, Heitor M.; Salehi, Mahsa; Bifet, Albert; Webb, Geoffrey I.
An eager splitting strategy for online decision trees in ensembles
Data Mining and Knowledge Discovery, vol. 36, pp. 566-619, 2022.
@article{Manapragada_2022,
title = {An eager splitting strategy for online decision trees in ensembles},
author = {Chaitanya Manapragada and Heitor M. Gomes and Mahsa Salehi and Albert Bifet and Geoffrey I. Webb},
url = {https://rdcu.be/c1y4Z},
doi = {10.1007/s10618-021-00816-x},
year = {2022},
date = {2022-01-01},
journal = {Data Mining and Knowledge Discovery},
volume = {36},
pages = {566-619},
publisher = {Springer Science and Business Media LLC},
abstract = {Decision tree ensembles are widely used in practice. In this work, we study in ensemble settings the effectiveness of replacing the split strategy for the state-of-the-art online tree learner, Hoeffding Tree, with a rigorous but more eager splitting strategy that we had previously published as Hoeffding AnyTime Tree. Hoeffding AnyTime Tree (HATT), uses the Hoeffding Test to determine whether the current best candidate split is superior to the current split, with the possibility of revision, while Hoeffding Tree aims to determine whether the top candidate is better than the second best and if a test is selected, fixes it for all posterity. HATT converges to the ideal batch tree while Hoeffding Tree does not. We find that HATT is an efficacious base learner for online bagging and online boosting ensembles. On UCI and synthetic streams, HATT as a base learner outperforms HT at a 0.05 significance level for the majority of tested ensembles on what we believe is the largest and most comprehensive set of testbenches in the online learning literature. Our results indicate that HATT is a superior alternative to Hoeffding Tree in a large number of ensemble settings.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Decision tree ensembles are widely used in practice. In this work, we study in ensemble settings the effectiveness of replacing the split strategy for the state-of-the-art online tree learner, Hoeffding Tree, with a rigorous but more eager splitting strategy that we had previously published as Hoeffding AnyTime Tree. Hoeffding AnyTime Tree (HATT), uses the Hoeffding Test to determine whether the current best candidate split is superior to the current split, with the possibility of revision, while Hoeffding Tree aims to determine whether the top candidate is better than the second best and if a test is selected, fixes it for all posterity. HATT converges to the ideal batch tree while Hoeffding Tree does not. We find that HATT is an efficacious base learner for online bagging and online boosting ensembles. On UCI and synthetic streams, HATT as a base learner outperforms HT at a 0.05 significance level for the majority of tested ensembles on what we believe is the largest and most comprehensive set of testbenches in the online learning literature. Our results indicate that HATT is a superior alternative to Hoeffding Tree in a large number of ensemble settings.
Manapragada, Chaitanya; Salehi, Mahsa; Webb, Geoffrey I.
Extremely Fast Hoeffding Adaptive Tree
Proceedings of the 2022 IEEE International Conference on Data Mining (ICDM), pp. 319-328, IEEE, 2022.
@inproceedings{ManapragadaEtAl22,
title = {Extremely Fast Hoeffding Adaptive Tree},
author = {Chaitanya Manapragada and Mahsa Salehi and Geoffrey I. Webb},
doi = {10.1109/ICDM54844.2022.00042},
year = {2022},
date = {2022-01-01},
booktitle = {Proceedings of the 2022 IEEE International Conference on Data Mining (ICDM)},
pages = {319-328},
publisher = {IEEE},
abstract = {Many real-world data streams are non-stationary.
Subject to concept drift, the distributions change over time.
To retain accuracy in the face of such drift, online decision
tree learners must discard parts of the tree that are no longer
accurate and replace them by new subtrees that reflect the
new distribution. The longstanding state-of-the-art online
decision tree learner for non-stationary streams is Hoeffding
Adaptive Tree (HAT), which adds a drift detection and response
mechanism to the classic Very Fast Decision Tree (VFDT) online
decision tree learner. However, for stationary distributions,
VFDT has been superseded by Extremely Fast Decision Tree
(EFDT), which uses a statistically more efficient learning
mechanism than VFDT. This learning mechanism needs to be
coupled with a compensatory revision mechanism that can
compensate for circumstances where the learning mechanism is
too eager.
The current work develops a strategy to combine the best
of both these state-of-the-art approaches, exploiting both the
statistically efficient learning mechanism from EFDT and the
highly effective drift detection and response mechanism of HAT.
To do so requires decoupling of the EFDT splitting and revision
mechanisms, as the latter incorrectly triggers the HAT drift
detection mechanism. The resulting learner, Extremely Fast
Hoeffding Adaptive Tree, responds to drift more rapidly and
effectively than either HAT or EFDT, and attains a statistically
significant advantage in accuracy even on stationary streams.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Many real-world data streams are non-stationary.
Subject to concept drift, the distributions change over time.
To retain accuracy in the face of such drift, online decision
tree learners must discard parts of the tree that are no longer
accurate and replace them by new subtrees that reflect the
new distribution. The longstanding state-of-the-art online
decision tree learner for non-stationary streams is Hoeffding
Adaptive Tree (HAT), which adds a drift detection and response
mechanism to the classic Very Fast Decision Tree (VFDT) online
decision tree learner. However, for stationary distributions,
VFDT has been superseded by Extremely Fast Decision Tree
(EFDT), which uses a statistically more efficient learning
mechanism than VFDT. This learning mechanism needs to be
coupled with a compensatory revision mechanism that can
compensate for circumstances where the learning mechanism is
too eager.
The current work develops a strategy to combine the best
of both these state-of-the-art approaches, exploiting both the
statistically efficient learning mechanism from EFDT and the
highly effective drift detection and response mechanism of HAT.
To do so requires decoupling of the EFDT splitting and revision
mechanisms, as the latter incorrectly triggers the HAT drift
detection mechanism. The resulting learner, Extremely Fast
Hoeffding Adaptive Tree, responds to drift more rapidly and
effectively than either HAT or EFDT, and attains a statistically
significant advantage in accuracy even on stationary streams.
Subject to concept drift, the distributions change over time.
To retain accuracy in the face of such drift, online decision
tree learners must discard parts of the tree that are no longer
accurate and replace them by new subtrees that reflect the
new distribution. The longstanding state-of-the-art online
decision tree learner for non-stationary streams is Hoeffding
Adaptive Tree (HAT), which adds a drift detection and response
mechanism to the classic Very Fast Decision Tree (VFDT) online
decision tree learner. However, for stationary distributions,
VFDT has been superseded by Extremely Fast Decision Tree
(EFDT), which uses a statistically more efficient learning
mechanism than VFDT. This learning mechanism needs to be
coupled with a compensatory revision mechanism that can
compensate for circumstances where the learning mechanism is
too eager.
The current work develops a strategy to combine the best
of both these state-of-the-art approaches, exploiting both the
statistically efficient learning mechanism from EFDT and the
highly effective drift detection and response mechanism of HAT.
To do so requires decoupling of the EFDT splitting and revision
mechanisms, as the latter incorrectly triggers the HAT drift
detection mechanism. The resulting learner, Extremely Fast
Hoeffding Adaptive Tree, responds to drift more rapidly and
effectively than either HAT or EFDT, and attains a statistically
significant advantage in accuracy even on stationary streams.
Krempl, Georg; Hofer, Vera; Webb, Geoffrey; Hullermeier, Eyke
Beyond Adaptation: Understanding Distributional Changes (Dagstuhl Seminar 20372)
Schloss Dagstuhl - Leibniz-Zentrum fur Informatik 2021.
@techreport{Krempl2021,
title = {Beyond Adaptation: Understanding Distributional Changes (Dagstuhl Seminar 20372)},
author = {Georg Krempl and Vera Hofer and Geoffrey Webb and Eyke Hullermeier},
doi = {10.4230/DAGREP.10.4.1},
year = {2021},
date = {2021-01-01},
institution = {Schloss Dagstuhl - Leibniz-Zentrum fur Informatik},
keywords = {},
pubstate = {published},
tppubtype = {techreport}
}
Goldenberg, Igor; Webb, Geoffrey I.
PCA-based drift and shift quantification framework for multidimensional data
Knowledge and Information Systems, vol. 62, pp. 2835-2854, 2020.
@article{Goldenberg2020,
title = {PCA-based drift and shift quantification framework for multidimensional data},
author = {Igor Goldenberg and Geoffrey I. Webb},
doi = {10.1007/s10115-020-01438-3},
year = {2020},
date = {2020-01-01},
journal = {Knowledge and Information Systems},
volume = {62},
pages = {2835-2854},
abstract = {Concept drift is a serious problem confronting machine learning systems in a dynamic and ever-changing world. In order to manage concept drift it may be useful to first quantify it by measuring the distance between distributions that generate data before and after a drift. There is a paucity of methods to do so in the case of multidimensional numeric data. This paper provides an in-depth analysis of the PCA-based change detection approach, identifies shortcomings of existing methods and shows how this approach can be used to measure a drift, not merely detect it.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Concept drift is a serious problem confronting machine learning systems in a dynamic and ever-changing world. In order to manage concept drift it may be useful to first quantify it by measuring the distance between distributions that generate data before and after a drift. There is a paucity of methods to do so in the case of multidimensional numeric data. This paper provides an in-depth analysis of the PCA-based change detection approach, identifies shortcomings of existing methods and shows how this approach can be used to measure a drift, not merely detect it.
Pratama, M.; Pedrycz, W.; Webb, G. I.
IEEE Transactions on Fuzzy Systems, vol. 28, no. 7, pp. 1315-1328, 2020, ISSN: 1063-6706.
@article{Pratama19,
title = {An Incremental Construction of Deep Neuro Fuzzy System for Continual Learning of Non-stationary Data Streams},
author = {M. Pratama and W. Pedrycz and G. I. Webb},
doi = {10.1109/TFUZZ.2019.2939993},
issn = {1063-6706},
year = {2020},
date = {2020-01-01},
journal = {IEEE Transactions on Fuzzy Systems},
volume = {28},
number = {7},
pages = {1315-1328},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Goldenberg, Igor; Webb, Geoffrey I.
Survey of distance measures for quantifying concept drift and shift in numeric data
Knowledge and Information Systems, vol. 60, no. 2, pp. 591-615, 2019, ISSN: 0219-3116.
@article{Goldenberg2018,
title = {Survey of distance measures for quantifying concept drift and shift in numeric data},
author = {Igor Goldenberg and Geoffrey I. Webb},
doi = {10.1007/s10115-018-1257-z},
issn = {0219-3116},
year = {2019},
date = {2019-01-01},
journal = {Knowledge and Information Systems},
volume = {60},
number = {2},
pages = {591-615},
abstract = {Deployed machine learning systems are necessarily learned from historical data and are often applied to current data. When the world changes, the learned models can lose fidelity. Such changes to the statistical properties of data over time are known as concept drift. Similarly, models are often learned in one context, but need to be applied in another. This is called concept shift. Quantifying the magnitude of drift or shift, especially in the context of covariate drift or shift, or unsupervised learning, requires use of measures of distance between distributions. In this paper, we survey such distance measures with respect to their suitability for estimating drift and shift magnitude between samples of numeric data.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Deployed machine learning systems are necessarily learned from historical data and are often applied to current data. When the world changes, the learned models can lose fidelity. Such changes to the statistical properties of data over time are known as concept drift. Similarly, models are often learned in one context, but need to be applied in another. This is called concept shift. Quantifying the magnitude of drift or shift, especially in the context of covariate drift or shift, or unsupervised learning, requires use of measures of distance between distributions. In this paper, we survey such distance measures with respect to their suitability for estimating drift and shift magnitude between samples of numeric data.
Yu, Hualong; Webb, Geoffrey I
Adaptive Online Extreme Learning Machine by Regulating Forgetting Factor by Concept Drift Map
Neurocomputing, vol. 343, pp. 141-153, 2019.
@article{yuetal2019,
title = {Adaptive Online Extreme Learning Machine by Regulating Forgetting Factor by Concept Drift Map},
author = {Hualong Yu and Geoffrey I Webb},
doi = {10.1016/j.neucom.2018.11.098},
year = {2019},
date = {2019-01-01},
journal = {Neurocomputing},
volume = {343},
pages = {141-153},
publisher = {Elsevier},
abstract = {In online-learning, the data is incrementally received and the distributions from which it is drawn may keep changing over time. This phenomenon is widely known as concept drift. Such changes may affect the generalization of a learned model to future data. This problem may be exacerbated by the form of the drift itself changing over time. Quantitative measures to describe and analyze the concept drift have been proposed in previous work. A description composed from these measures is called a concept drift map. We believe that these maps could be useful for guiding how much knowledge in the old model should be forgotten. Therefore, this paper presents an adaptive online learning model that uses a concept drift map to regulate the forgetting factor of an extreme learning machine. Specifically, when a batch of new instances are labeled, the distribution of each class on each attribute is firstly estimated, and then it is compared with the distribution estimated in the previous batch to calculate the magnitude of concept drift, which is further used to regulate the forgetting factor and to update the learning model. Therefore, the novelty of this paper lies in that a quantitative distance metric between two distributions constructed on continuous attribute space is presented to construct concept drift map which can be further associated with the forgetting factor to make the learning model adapt the concept drift. Experimental results on several benchmark stream data sets show the proposed model is generally superior to several previous algorithms when classifying a variety of data streams subject to drift, indicating its effectiveness and feasibility.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
In online-learning, the data is incrementally received and the distributions from which it is drawn may keep changing over time. This phenomenon is widely known as concept drift. Such changes may affect the generalization of a learned model to future data. This problem may be exacerbated by the form of the drift itself changing over time. Quantitative measures to describe and analyze the concept drift have been proposed in previous work. A description composed from these measures is called a concept drift map. We believe that these maps could be useful for guiding how much knowledge in the old model should be forgotten. Therefore, this paper presents an adaptive online learning model that uses a concept drift map to regulate the forgetting factor of an extreme learning machine. Specifically, when a batch of new instances are labeled, the distribution of each class on each attribute is firstly estimated, and then it is compared with the distribution estimated in the previous batch to calculate the magnitude of concept drift, which is further used to regulate the forgetting factor and to update the learning model. Therefore, the novelty of this paper lies in that a quantitative distance metric between two distributions constructed on continuous attribute space is presented to construct concept drift map which can be further associated with the forgetting factor to make the learning model adapt the concept drift. Experimental results on several benchmark stream data sets show the proposed model is generally superior to several previous algorithms when classifying a variety of data streams subject to drift, indicating its effectiveness and feasibility.
Manapragada, Chaitanya; Webb, Geoffrey I.; Salehi, Mahsa
Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1953–1962, ACM, London, United Kingdom, 2018, ISBN: 978-1-4503-5552-0.
@inproceedings{ManapragadaEtAl18,
title = {Extremely Fast Decision Tree},
author = {Chaitanya Manapragada and Geoffrey I. Webb and Mahsa Salehi},
doi = {10.1145/3219819.3220005},
isbn = {978-1-4503-5552-0},
year = {2018},
date = {2018-01-01},
booktitle = {Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining},
pages = {1953\textendash1962},
publisher = {ACM},
address = {London, United Kingdom},
series = {KDD '18},
abstract = {We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree\textemdash"Extremely Fast Decision Tree", a minor modification to the MOA implementation of Hoeffding Tree\textemdashobtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
We introduce a novel incremental decision tree learning algorithm, Hoeffding Anytime Tree, that is statistically more efficient than the current state-of-the-art, Hoeffding Tree. We demonstrate that an implementation of Hoeffding Anytime Tree—"Extremely Fast Decision Tree", a minor modification to the MOA implementation of Hoeffding Tree—obtains significantly superior prequential accuracy on most of the largest classification datasets from the UCI repository. Hoeffding Anytime Tree produces the asymptotic batch tree in the limit, is naturally resilient to concept drift, and can be used as a higher accuracy replacement for Hoeffding Tree in most scenarios, at a small additional computational cost.
Webb, Geoffrey I; Lee, Loong Kuan; Goethals, Bart; Petitjean, Francois
Analyzing concept drift and shift from sample data
Data Mining and Knowledge Discovery, vol. 32, no. 5, pp. 1179-1199, 2018.
@article{WebbEtAl18,
title = {Analyzing concept drift and shift from sample data},
author = {Geoffrey I Webb and Loong Kuan Lee and Bart Goethals and Francois Petitjean},
url = {http://rdcu.be/IUTI},
doi = {10.1007/s10618-018-0554-1},
year = {2018},
date = {2018-01-01},
journal = {Data Mining and Knowledge Discovery},
volume = {32},
number = {5},
pages = {1179-1199},
abstract = {Concept drift and shift are major issues that greatly affect the accuracy and reliability of many real-world applications of machine learning. We propose a new data mining task, concept drift mapping - the description and analysis of instances of concept drift or shift. We argue that concept drift mapping is an essential prerequisite for tackling concept drift and shift. We propose tools for this purpose, arguing for the importance of quantitative descriptions of drift and shift in marginal distributions. We present quantitative concept drift mapping techniques, along with methods for visualizing their results. We illustrate their effectiveness for real-world applications across energy-pricing, vegetation monitoring and airline scheduling.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
Concept drift and shift are major issues that greatly affect the accuracy and reliability of many real-world applications of machine learning. We propose a new data mining task, concept drift mapping - the description and analysis of instances of concept drift or shift. We argue that concept drift mapping is an essential prerequisite for tackling concept drift and shift. We propose tools for this purpose, arguing for the importance of quantitative descriptions of drift and shift in marginal distributions. We present quantitative concept drift mapping techniques, along with methods for visualizing their results. We illustrate their effectiveness for real-world applications across energy-pricing, vegetation monitoring and airline scheduling.
Zaidi, Nayyar A.; Webb, Geoffrey I.; Petitjean, Francois; Forestier, Germain
On the Inter-Relationships among Drift Rate, Forgetting Rate, Bias/Variance Profile and Error
arxiv, pp. 1801.09354, 2018.
@article{ZaidiEtAl18b,
title = {On the Inter-Relationships among Drift Rate,
Forgetting Rate, Bias/Variance Profile and Error},
author = {Nayyar A. Zaidi and Geoffrey I. Webb and Francois Petitjean and Germain Forestier},
url = {https://arxiv.org/abs/1801.09354},
year = {2018},
date = {2018-01-01},
journal = {arxiv},
pages = {1801.09354},
abstract = {We propose two general and falsifiable hypotheses about expectations on generalization error when learning in the context of concept drift. One posits that as drift rate increases, the forgetting rate that minimizes generalization error will also increase and vice versa. The other posits that as a learner's forgetting rate increases, the bias/variance profile that minimizes generalization error will have lower variance and vice versa. These hypotheses lead to the concept of the sweet path, a path through the 3-d space of alternative drift rates, forgetting rates and bias/variance profiles on which generalization error will be minimized, such that slow drift is coupled with low forgetting and low bias, while rapid drift is coupled with fast forgetting and low variance. We present experiments that support the existence of such a sweet path. We also demonstrate that simple learners that select appropriate forgetting rates and bias/variance profiles are highly competitive with the state-of-the-art in incremental learners for concept drift on real-world drift problems.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
We propose two general and falsifiable hypotheses about expectations on generalization error when learning in the context of concept drift. One posits that as drift rate increases, the forgetting rate that minimizes generalization error will also increase and vice versa. The other posits that as a learner's forgetting rate increases, the bias/variance profile that minimizes generalization error will have lower variance and vice versa. These hypotheses lead to the concept of the sweet path, a path through the 3-d space of alternative drift rates, forgetting rates and bias/variance profiles on which generalization error will be minimized, such that slow drift is coupled with low forgetting and low bias, while rapid drift is coupled with fast forgetting and low variance. We present experiments that support the existence of such a sweet path. We also demonstrate that simple learners that select appropriate forgetting rates and bias/variance profiles are highly competitive with the state-of-the-art in incremental learners for concept drift on real-world drift problems.
Webb, G. I.; Hyde, R.; Cao, H.; Nguyen, H. L.; Petitjean, F.
Data Mining and Knowledge Discovery, vol. 30, no. 4, pp. 964-994, 2016.
@article{WebbEtAl16,
title = {Characterizing Concept Drift},
author = {G. I. Webb and R. Hyde and H. Cao and H. L. Nguyen and F. Petitjean},
url = {https://rdcu.be/7vMN},
doi = {10.1007/s10618-015-0448-4},
year = {2016},
date = {2016-01-01},
journal = {Data Mining and Knowledge Discovery},
volume = {30},
number = {4},
pages = {964-994},
abstract = {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.},
keywords = {},
pubstate = {published},
tppubtype = {article}
}
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.
Webb, G. I.
Proceedings of the 14th IEEE International Conference on Data Mining, pp. 1031-1036, 2014.
@inproceedings{Webb14,
title = {Contrary to Popular Belief Incremental Discretization can be Sound, Computationally Efficient and Extremely Useful for Streaming Data},
author = {G. I. Webb},
doi = {10.1109/ICDM.2014.123},
year = {2014},
date = {2014-01-01},
booktitle = {Proceedings of the 14th IEEE International Conference on Data Mining},
pages = {1031-1036},
abstract = {Discretization of streaming data has received surprisingly
little attention. This might be because streaming data
require incremental discretization with cutpoints that may vary
over time and this is perceived as undesirable. We argue, to
the contrary, that it can be desirable for a discretization to
evolve in synchronization with an evolving data stream, even
when the learner assumes that attribute values. meanings remain
invariant over time. We examine the issues associated with
discretization in the context of distribution drift and develop
computationally efficient incremental discretization algorithms.
We show that discretization can reduce the error of a classical
incremental learner and that allowing a discretization to drift in
synchronization with distribution drift can further reduce error.},
keywords = {},
pubstate = {published},
tppubtype = {inproceedings}
}
Discretization of streaming data has received surprisingly
little attention. This might be because streaming data
require incremental discretization with cutpoints that may vary
over time and this is perceived as undesirable. We argue, to
the contrary, that it can be desirable for a discretization to
evolve in synchronization with an evolving data stream, even
when the learner assumes that attribute values. meanings remain
invariant over time. We examine the issues associated with
discretization in the context of distribution drift and develop
computationally efficient incremental discretization algorithms.
We show that discretization can reduce the error of a classical
incremental learner and that allowing a discretization to drift in
synchronization with distribution drift can further reduce error.
little attention. This might be because streaming data
require incremental discretization with cutpoints that may vary
over time and this is perceived as undesirable. We argue, to
the contrary, that it can be desirable for a discretization to
evolve in synchronization with an evolving data stream, even
when the learner assumes that attribute values. meanings remain
invariant over time. We examine the issues associated with
discretization in the context of distribution drift and develop
computationally efficient incremental discretization algorithms.
We show that discretization can reduce the error of a classical
incremental learner and that allowing a discretization to drift in
synchronization with distribution drift can further reduce error.