Concept Drift Evolution In Machine Learning Approaches: A Systematic Literature Review

This SLR aims to summarize and clarify the empirical evidence towards understanding the Concept Drift issue and Machine Learning. To achieve the objective of this study, the following four research questions were formulated.

The search strategy comprises search terms, literature resources, and search processes, which are detailed as follows;

This study follows the recommendations presented in (Kitchenham and Charters, 2007; Kitchenham, 2004; Petersen et al., 2008). These studies are the standard reference for study identification and selection process in the Computer Science domain. However, this study also used some defined inclusion and exclusion criteria. The inclusion and exclusion criteria draw the boundary line towards the study selection, which is essential to ensure an unbiased and quality search.

This Systematic Literature Review (SLR) exploits the relevant articles that address this study’s research questions. However, few articles do not directly act as evidence for the problem area but are essential for supporting evidence. Besides, these papers were not relevant to the subject matter.

The goal of data synthesis is to aggregate evidence from the selected studies for answering the research questions. A single piece of evidence might have small evidence force, but the aggregation of many of them can make a point stronger (Pfleeger, 2005). The data extracted in this review include quantitative data (e.g., values of estimation accuracy) and qualitative data (e.g., strengths and weaknesses of Concept Drift adaptation techniques).

The taxonomy and types of CD issues are well defined in numerous studies (Jameel et al., 2020a, b, c). However, these studies do not discuss their quantification and measuring methods (essential to handling CD issues). Therefore, this research question investigates causes, quantification, and measurement techniques. Many assumptions in ML are being used in static data (Budiman et al., 2017). However, the current trends demand the analysis (using ML) in the non-static assumption or online machine learning where dynamic conditions of data changes are often. Therefore, due to the addition of new data features, ML models degrade their performance accuracy or could fail to classify or predict the correct output. Notably, in Supervised Online ML, the model is learned through the input and output features from data of one-time span and will likely predict or classify the output (class category) from another time. The change in features (among both periods) are due to various conditions. It could be due to the data format (variety), distribution (variability), or sources (complexity), which change over time. Another term for Concept Drift refers to the classification boundary or clustering centers that continuously change with time elapsing (Zang et al., 2014). These conditions will adversely affect the classification performance of the model. In studies, the CD is modeled based on Bayesian decision theory for class output ‘c’ and input data X, as shown below. Zliobaite et al. (2014) (1) P ( c / X ) = P ( c ) P ( X / C ) / P ( X ) ( 1.1 )

Where P(c/X), P(c), P(X/c), and P(X) are posterior, prior, conditional, and feature-based probabilities, respectively (Budiman et al., 2017). One of the possible conditions is Real Concept Drift. Real Concept Drift arises when P(c/X) undergoes changes and causes a shift in the class boundary (conditional probabilities). In this condition, the number of output classes may change (Zliobaite et al., 2014). Furthermore, suppose the P (X) (feature-wise distribution of data changes) is due to insufficient or partial feature representation of existing data distribution (new additional feature adds or some feature updates). In that case, it is called Virtual Drift (Zliobaite et al., 2014). Also, a study introduces Hybrid Drift as a condition P(c/X), and P(X) occurred consequently (Budiman et al., 2016). However, few studies discuss possible configuration patterns based on the Frequency of drift, gradual drift (when the variety of concepts changes progressively), consecutive drift (when previous concepts reoccur), and sudden drift patterns (when a concept changes/substitutes abruptly) (Kuncheva, 2004). ML models are trained to classify according to input and output features with a predefined number of classes. Suppose a feature or class-wise distribution changes over time. In that case, ML models will face a substantial degradation in their performance (because ML models do not have prior knowledge of these changes). However, if these ML models retrain according to newly-arrived data, they cannot keep understanding of the Recurrent Context (previous training knowledge).

Today, the role of Machine Learning has found more applications in everyday life. However, the demand for online analysis has exponentially increased in several critical application domains, such as seismic analysis (Ghorbani et al., 2017), sustainability (Gupta and Dhawan, 2019), and others (Jensen et al., 2019).

Fundamentally, the types of CD are classified by their feature and class boundaries. However, several studies also ranked CD types with the nature of occurrence or the concept transition frequency from one concept to another. Some introductory details regarding the types of CD concerning feature-wise or class wise change distribution. The abrupt change from concept one to concept two is known as Sudden Drift. The recurrent concept is not frequently in this type of drift (Nishida et al., 2008). Gradual drift involves the progressive change from one concept to another concept. These can be small or significant changes. Gradual drift is hard to detect because the shift in the boundaries needs a more sophisticated method because of drastic differences between the nature of these changes’ individualities. Sometimes, these changes could be an unvarying progression, and sometimes it could be varying and non-steady progress (Harel et al., 2014; Dyer and Polikar, 2012). Continuous drift follows a systematic pattern; these patterns repeatedly occur after a specific time interval (Khamassi et al., 2019; Saurav et al., 2018). Unlike the sudden drift, the blip drift is a spike of a new concept from the previous concept and recalls the previous concept back abruptly. The blip concept is coupled with minimal duration (Dongre and Malik, 2014). A typical example of blip drift could be a sale promotion offer for a limited time, for example, low fare rates by airlines for their customers on the day of its completion year cycle. Notably, these changes are not frequent or continuous; this drift in customer behaviors’ policies is relevant to a specific event. Therefore, due to its minor contribution towards understanding the behavior of the system or customer, some studies argued to not consider blip drift as a type of CD (Dariusz, 2010).

Several studies like (Iwashita et al., 2019; Sayed et al., 2018; Wadewale and Desai, 2015) emphasize to add all the possibilities of CD occurrence. These studies argue to consider blip concept drift as a type of Concept Drift. To consider blip drift as one of the types of CD is an entirely legitimate argument.

Moreover, the incremental drift follows a specific pattern; this pattern is based on steady progression from one concept to another by incrementing 1, each time internal the concept x steps up to x + 1. A typical example of a variation of fraud pattern is used to illustrate incremental CD (Iwashita et al., 2019). In short, CD types are based on transition frequencies, which define the manners between two concepts. Moreover, these concepts certainly also belong to either real, virtual, or hybrid type of CD. Several studies, like (Brzezinski and Stefanowski, 2014a; Hoens et al., 2012; Jagadeesh Chandra Bose et al., 2011; Huang et al., 2013; Minku et al., 2010; Tsymbal, 2004), discussed these changes in detail.

CD significantly degrades the performance of various online models. These online models participate in several real-world applications. It is essential to figure out the quantitative measurements of CD before mitigating it. In the literature, Concept Drift detection approaches are qualitative. However, few studies discuss the quantitative measure for the characterizing of CD. These quantitative measures act as an essential prerequisite to adapt to a CD. Geoffrey I. et al. (Webb et al., 2018) proposes the novel framework, measuring the CD on a quantitative basis, and suggests the first formal quantification of concept drift, which is a solid foundation to address the problem of this nonstationary environment. Any measure of the distance between distributions could be employed. Geoffrey I. et al. used Hellinger Distance (Hoens et al., 2012) to measure the CD through the drift magnitude and the degree of difference between two-time intervals. It also highlighted the necessity of quantitative description, presented the quantitative drift mapping techniques and CD visualization methods, and used maximum likelihood estimates of the probability distribution to illustrate the concept drift. Describing drift in different attribute subspaces is to measure the drift in the marginal distributions defined over various combinations of attributes. The proposed technique approximates the drift among a two-time step, initially by approximation distributions every time step and later computing the magnitude among those drifts using the maximum Likely Hood approach. Web b and Geoffrey et al. Webb et al. (2018) claimed that their proposed measures are more practical in real-world applications. The study proposes the measuring marginal concept drift and its different variants. The quantitative measurements of drift magnitude use the total drift magnitude between any two concepts; this approach uses Hellinger Distance (Hoens et al., 2011) and Total Variation Distance for this purpose. Marginal Drift Magnitude measures the drift by approximate Probability Distribution. Geoffrey I. Webb et al. (2018) uses the weighted averaging approach to deal with Conditional Distribution to tackle multiple distribution problems.

CD is a phenomenon that mostly occurs in Online Learning. The various conditions and types of CD make the existing ML models inappropriate for an online scenario. More specifically, the condition even goes worsens when dealing with multiple CDs at the same time. Furthermore, the available handling approaches are not generic and require separate handling mechanisms for each CD type. The adaptability in the learner is a primary way to overcome performance degradation due to a CD. However, the handling of drift recurrence scenarios is still challenging. Even though CD’s quantification is one of the primary factors to detect CD, only a few studies investigated this area. Mostly, the classifier/learner’s performance accuracy is considered the most appropriate way to observe the CD.

RQ2: Do the state of art approaches (for CD handling) are adequate for current and future computing trends?

The term handling (of CD) refers to the detection and adaptation process.

CD detection identifies the real changes in the input stream during online classification. CD detection is a prerequisite for adaptation. However, the process of determining the changes is merely dependent on the type of data stream or the nature of Concept Drift. Hence the provided solution is not generalizing. An early study, Probably Approximately Correct learning model (PAC learning model Kearns and Vazirani, 1994), states that the error rate will always be minimum after expansion in sample size in a static learning environment.

Contrary to this, the error rate significantly escalated after observing the change in class distribution. The CD detection techniques are classified into a type of Machine Learning problem. For example, most of the proposed techniques which are applicable for supervised learning, such as DDM by Gama et al. (2004) and Early Drift Detection Method (EDDM), (Baena-Garcıa et al., 2006) are not applicable for the unsupervised problem (Lavaire et al., 2015). Unlike the Supervised Drift Detection, possible change is observed in the Unsupervised Drift Detection after statistical hypothesis tests. Also, the classifier does not participate in detecting drift. For example, in a study (Friedman and Rafsky, 1979), Friedman and Rafsky’s propose an Unsupervised Drift Detection algorithm. This empirical study focuses on the growth of execution time on datasets with increasing dimensions and comparative accuracy of algorithms concerning their drift detection ability. Few detection models work well for both supervised and unsupervised learning scenarios. For example, ONLINDDA, proposed by Spinosa et al. (2007), uses the integrated set of clusters to identify the newly emerging concept drift scenarios. These clusters are capable of detecting possible changes in both scenarios.

The majority of the studies in the literature detects the Concept Drift using the performance monitoring algorithms (performance measures, properties of the data are monitored over time) (Zeira et al., 2004) and distribution comparing algorithms (Monitoring distributions on two different time-windows. A reference window, that usually summarize past information, and a window over the most recent examples) (Kifer et al., 2004). In a recent study, a concept drift detector is based on computing multiple model explanations over time and observing their changes’ magnitudes. The model explanation is calculated using a methodology that yields attribute-value contributions for prediction outcomes, provides insight into the model’s decision-making process, and enables transparency. The evaluation has revealed that the methods surpass the baseline methods in terms of concept drift detection, accuracy, robustness, and sensitivity (Demšar and Bosnić, 2018). Many studies discuss the available Concept Drift Detection techniques (Zeira et al., 2004; Kifer et al., 2004; Demšar and Bosnić, 2018). Most of the methods use the Weight Determination Approach, Window Approach, or Statistical Analysis Approach. In 2004, Gama et al. (2004) proposed a novel Drift Detection Method (DDM) framework. DDM is one of the preliminary frameworks which identifies the expected drift employed by a probability distribution and online error-rate. In this approach, Gama et al. mention a specific error-rate threshold for warning and drift levels. The drift observes after the error-rate crosses the warning threshold level (when it observes more than 30 errors). Later, the model starts its training mechanism to tune with detected changes. In 2006, an extension of DDM, the Early Drift Detection Method (EDDM), was proposed by Baena-Garcıa et al. (2006). EDDM technique uses two parameters to detect the drift, 1) many error rate and 2) the difference between two successive errors. The proposed model follows the inverse relation of concept drift and distance between errors. The authors state that when the new concept arrives, the distance among the errors significantly decreases. EDDM is proven to be a better drift detection approach (especially for gradual drift) than DDM, and it is more delegate to noise than DDM.

A sequential analysis-based technique is Page-Hinkley Test (PHT) (Page, 1954; Mouss et al., 2004). PHT calculates the classifier accuracy to determine the occurrence of Concept Drift. For example, if the classifier degrades its performance accuracy to a specific threshold value, it is considered a drift situation. This approach fundamentally computes the Actual Accuracy and Average Accuracy (up to the current moment). The cumulative difference between Actual Accuracy and Average Accuracy represents “U.T.,” and the minimum difference between Actual Accuracy and Average Accuracy is described as “mT.” Both “U.T.” and “mT” values are computed to determine the drift occurrence. For example, higher “U.T.” values indicate that the observed values differ considerably from their previous values. More specifically, the drift observes when the difference between U.T. and mT is above a specified threshold corresponding to the magnitude of allowed (k) changes. An ensemble-based drift detection method was proposed by Kitani et al. Yasumura et al. (2007). This approach determines the drift by comparing the classification accuracy of two ensemble classifiers. In this approach, the AdaBoost (Freund and Schapire, 1997) algorithm is used to determine each ensemble classifier’s inverse weight to distinguish between the actual drift and noise. In 2008, Maloof et al. proposed a novel Paired Learner (PL) drift detection approach (Bach and Maloof, 2008). P.L. typically presents two different algorithms to detect the change from the input stream, such as Stable Learner (SL) and Reactive Learner (R.L.). The SL utilizes its historical knowledge for prediction contrary, the R.L. predicts based on a window of recent examples. However, the drift identifies by the computational contribution of both learners and their accuracy.

Bifet et al. propose a dynamic sliding window approach ADWIN (Bifet, 2009). ADWIN typically handles one-dimension data using a single window. However, multiple sliding windows can detect multi-dimension data (each window for each dimension). The window size narrows down when a rate of change perceives from the data in these windows, and an apparent change has been established. This approach dynamically regulates window size to the most appropriate point between reaction time and small variation. An extension of ADWIN, known as ADWIN2, was proposed to overcome the deficiencies in time and memory in ADWIN. The experimental results are better by ADWIN2 (Bifet and Gavalda, 2007); maintaining the same accuracy performance while utilizing less memory and consuming shortens the time. Nishida et al. proposed a statistical-based approach, namely the Statistical Test of Equal Proportions (STEPD) (Nishida, 2008). Like other various studies (Gama et al., 2004; Baena-Garcıa et al., 2006), warning and drift threshold are specified in this approach. This approach classifies the drift and non-drift scenarios based on recent accuracy and overall accuracy (from the beginning) of the classifier. It suggests a concept drift scenario; the current accuracy will always have a significant difference compared to the overall accuracy of the model. In this approach, Nishida et al. performed chi-square tests and computed the acquired value from the standard normal distribution to determine the significance level; a secondary significance level portrays the drift occur acne. Rose et al. proposed a novel approach EWMA (Ross et al., 2012). This approach used an exponentially weighted average moving mechanism and meant a sequence of random variables to detect the changes in the underlying distribution of the input stream. Typically, this mechanism constructs the EWMA chart (to monitor a streaming classifier) to observe the possible drift. EWMA is a modular technique and added an extra layer for observing a drift; this addition of drift detection layer contributes to detecting drift in a parallel execution manner with any underlying classifier. In contrast with other available drift detection techniques, in EWMA, the rate of false-positive detections is controlled and constant over time. Adaptive Learning with Covariant Shift-Detection (ALCSD) is an extension of EWMA. This approach detects the possible shifts using the EWMA shift detection text and covariant shift analysis (Raza et al., 2014). Sobhani et al. also proposed a novel approach to detect the drift using the nearest neighbor approach. The algorithm handles input data chunks by chunks of several batches. All the previous batches with the most immediate neighbor values are computed for every instance in the current batch and compared with their respective labels. A distance map is generated to classify the drift and non-drift batches and instances. More specifically, a drift is observed when the average and standard deviation of all degrees of drift evaluate, and contemporary value (current) are distinct to the average or above than the standard deviation parameter “S.”

To find new means to handle CD in the context of BD and OML is an essential task for the future of ML (Rouse, 2009). Nevertheless, several studies urged to adopt these dynamic changes (in classifier) through self-regulatory mechanisms (Ditzler and Polikar, 2013; Zliobaite et al., 2012). Existing adaptation approaches for CD handling are Shallow Learning and Deep Learning Classifiers or Hybrid using Single and Ensemble approaches.

The comprehensive literature analysis deduces that the existing CD handling (detection and adaptation) approaches are classified based on their behavior and structure. The current concept drift detector can be classified into three major categories;

Detection Concept Drifts by Data Distribution.

However, few studies utilized the weight, window approach, ensemble approach, and statistical methods to determine the possible change from the input stream among these categories. Furthermore, most of the studies define a threshold value for warning a drift and actual drift. However, all these solutions possess a common problem that they have overlooked noise as concept drift, and there is no particular way to distinguish the noise and potential concept drift. Also, there is not a single generalized adaptation approach, which applies to all types of CD. Moreover, the classification degradation does not reasonably retain after CD handling for complex datasets (such as Imagery Streams) and complex CD scenarios (recurrence scenarios). In literature, the ensemble way of handling CD issues is more appropriate. However, it requires further online training options to avoid any manual intervention for CD adaptation (which is desirable for future analysis trends). The ensemble classifier approach ensures the CD adaptation due to its diversity feature to adopt new changes. In comparison, single classifier results may not exceed the ensemble due to its shared weight changes.