Self-Adjusting Memory: How to Deal with Diverse Drift Types

1 Introduction

The classical batch setting of machine learning assumes that the complete task-specific data is all time available and can be accessed simultaneously without any restriction regarding the processing time. Furthermore, it is premised that the data is independent and identically distributed (i.i.d.). State of the art machine learning methods are able to obtain very accurate results within this framework. However, an ever growing field of real-world applications generates data in streaming fashion at increasing rate, requiring large-scale and real-time processing as well as life-long learning. Streaming data is prevalent in domains such as health monitoring, traffic management, financial transactions, social networks [Chen et al., 2014] and is the foundation of the Internet of Things [Atzori et al., 2010] technology. Supplementing streaming data with non-stationary environments leads to one of the recent key areas in data mining research: Learning in streams under concept drift. Here, algorithms are challenged by a variety of possible forms of drift under strict limitations in terms of memory consumption and processing time.

Heiko Wersing

HONDA Research Institute Europe Carl-Legien-Str. 30, 63073 Offenbach amMain

heiko.wersing@honda-ri.de

In supervised classification, concept drift [Gama et al., 2014] occurs when the joint distribution between the set of features x ∈ Rn and the target variable y ∈ {1, . . . , c} changes for at least two time steps t0 and t1:

The term real drift is used to specify that the relation between observation and labels Pt(y|x) varies over time. Virtual drift is present when the feature distribution Pt(x) changes without affecting the posterior of the classes Pt(y|x). Furthermore, the rate at which drift is taking place can be either classified as abrupt, resulting in a severe shift within the distribution, e.g. caused by a malfunctioning sensor, or incremental, an evolving change over time, e.g. evoked by a slowly degrading sensor. In the context of seasonal effects, drift is often characterized as reoccurring to describe that previous concepts are repeatedly emerging. In recent years, a few algorithms have been published which can be roughly divided in active and passive approaches [Ditzler et al., 2015]. Due to space constraints, we primarily review methods that are later also used in the experiments. A more complete overview is given in [Gama et al., 2014].

Active approaches explicitly detect the time of change and usually discard the accumulated knowledge up to this point. Often statistics such as the classification error, calculated on different time periods, are analyzed for significant deviations. A popular representative of these methods is ADaptive sliding WINdowing (ADWIN) [Bifet and Gavalda, 2007], utilized in various published algorithms. It efficiently monitors the binary error history since the last detected change. The history is repeatedly partitioned into two windows of various size. Whenever the difference of their average error exceeds a threshold a change is detected and the older window is dropped. Active approaches are often combined with a sliding window containing the most recent examples, as these are assumed to be the most valuable for current predictions. Hereby, the size is a trade-off between fast adaptation (small window) and good generalization in stable phases without drift (large window). To achieve both properties at the same time the size is adjusted dynamically. One exemplary method is the Probabilistic Adaptive Windowing (PAW) [Bifet et al., 2013] which randomly removes examples from the sliding window leading to a mix of recent and older instances. Active methods are able to quickly detect abrupt drift, however, they struggle with incremental change, which may not be significant enough and remains undetected. Another weakness is that knowledge either slowly fades out or is discarded in case of detected drift. Although the most recent examples are usually the most valuable for current predictions, there are also cases in which older data carries crucial information, e.g. reoccurring drift.

Passive approaches continuously adapt their model without explicit awareness of occurring drift. This prevents pitfalls such as missed or false detected drifts on the one hand, but the adaption speed is more or less constant, leading to costly delays in the case of abrupt drift, on the other hand. Passive algorithms are dominated by ensembles whose members are updated with incoming examples using techniques such as Bagging or Boosting. Jaber et al. presented Dynamic Adaption to Concept Changes (DACC) in [Jaber et al., 2013], an algorithm inspired by the Dynamic Weighted Majority [Kolter and Maloof, 2007] method. A classifier of the worst half of the pool is randomly removed after a predefined number of examples and replaced by a new one. Predictions for incoming examples are solely done by the best classifier within the pool, having the highest accuracy in the past. In Leveraging Bagging (LVGB) [Bifet et al., 2010] the randomization of Online Bagging [Oza, 2005] is increased and thereby also the diversity of the resulting ensemble. Additionally, ADWIN is used as change detector for every ensemble member such that every detected change leads to the replacement of the worst classifier by a new one. Learn++.NSE [Elwell and Polikar, 2011] processes incoming examples in chunks with a predefined size. A base classifier is trained for each chunk and added to the ensemble. In contrast to other methods, members are not learning continuously, but preserve their initial state. This fact is used to revive former members in the presence of reoccurring drift. Passive approaches can deal with incremental drift, but their inherent adaption speed has to be adjusted to the task-specific drift speed. In case of abrupt drift, the adaption delay is usually more pronounced than into active methods.

Even though some of the introduced methods can be used for several types of drift by an appropriate setting of their meta parameters, this requires explicit prior knowledge about the task at hand. However, it is still unclear how to identify the type of drift in a given real-world data stream. Furthermore, in real-world applications, data usually do not change only in one specific form, but instead multiple, sometimes even concurrent, types of drift are taking place at various rates. One example is the field of personalized assistance, in which individual user behavior is taken into account to provide appropriate assistance in various situations [Schiaffino et al., 2008]. But, individual behavior in particular can change in arbitrary ways. Systems anticipating only certain forms of drift, will perform sub-optimal at best, or fail completely at worst, when unexpected forms of change occur.

Our Self-Adjusting Memory (SAM) in combination with the k Nearest Neighbor (kNN) classifier is able to cope with heterogeneous concept drift and can be easily applied in practice without any parametrization. The extensive evaluation on common benchmarks demonstrates the gain of SAM-kNN in comparison to current state of the art approaches. It exclusively achieves highly competitive results throughout all experiments, demonstrating its robustness and the capability of handling heterogeneous concept drift. This paper is an abridged report of [Losing et al., 2016].

2 Streaming Setting

Our focus is data stream classification under supervised learning for incremental / on-line algorithms. A potentially infinite sequence S = (s1, s2, . . . , st, . . .) of tuples si = (xi, yi) arrives one after another. As t represents the current time stamp, the learning objective is to predict the target variable yt ∈ {1, . . . , c} for a given set of features xt ∈ Rn . The prediction ˆ yt = ht-1(xt) is done according to the previously learned model ht-1. Before proceeding with the next example, the learning algorithm generates a new model ht = train(ht-1, st) based on the current tuple st and the previous model ht-1. The performance is measured via the Interleaved Test-Train error E(S) = 1t ∑ti=1 1(hi-1(xi) ̸= yi).

3 Architecture of SAM

In the research field of human memory the dual-store model [Atkinson and Shiffrin, 1968], consisting of the Short-Term and Long-Term memory (STM & LTM), is largely accepted. The SAM architecture is partly inspired by this model and exhibits analogies such as the explicit separation of current and past knowledge, different conservation spans among the memories, filtered transfer of knowledge from the STM to the LTM as well as a situation dependent usage of both memories.

Our basic idea is to combine dedicated models for the current concept Pt(x, y) and all former ones Pt-1(x, y), . . . , P1(x, y) in such a way that the prediction error is minimized. We construct two different memories: The Short-Term Memory (STM), containing data of the current concept and the Long-Term Memory (LTM), maintaining knowledge of past concepts. This approach is illustrated by Figure 1. We share the general assumption of new data being more relevant for current predictions. Hence, we remove those information from former concepts which is in conflict with the current one, but we explicitly preserve the rest in compressed fashion. We avoid any parametrization, by exploiting the minimization of the error on recent data at various steps. Our architecture is depicted in Figure 2 and described below in detail.

3.1 Model Definition

Memories are represented by sets MST, MLT, MC. Each memory is a subset in Rn × {1, . . . , c} of varying length, adjusted during the adaptation process. The STM represents the current concept and is a dynamic sliding window containing the most recent m examples of the data stream:

The LTM preserves all former information which is not contradicting those of the STM in a compressed way. In contrast to the STM, the LTM is neither a continuous subpart of the stream nor given by exemplars, but instead a set of p points:

The combined memory (CM) is the union of both memories with size m + p and defined as MC = MST ∪ MLT.

Every set induces a classifier, in our case a distance weighted kNN : Rn ↦→ {1, . . . , c}, kNNMST , kNNMLT , kNNMC . Weights wST, wLT, wC are representing the accuracy of the corresponding model on the current concept and are determined as described in section 3.2. The prediction of our complete model relies on the sub-model with the highest weight and is defined for a given point x as:

This model is adapted incrementally for every time t as described in section 3.2.

The hyperparameters of the model consist of the minimal length of the STM Lmin, the maximum number of stored examples Lmax (STM & LTM combined) as well as the number of neigbhors k. These can be robustly chosen and do not require a task-specific setting 1 .

3.2 Model Adaption

The adaption comprises the size m of the STM, the data points in the LTM and the weights wST, wLT, wC of the corresponding sub-models.

Adaption of the short termmemory

The STM is a dynamic sliding window containing the most recent examples. Every incoming example of the stream gets inserted such that the STM grows continuously. Its role is to exclusively contain data of the current concept. Therefore, its size has to be reduced, whenever the concept changes such that examples of the former concept are dropped. However, we do not explicitly detect a concept change, but instead we adjust the size such that the Interleaved Test-Train error of the remaining STM is minimized. This approach relies on the fact that a model trained on internally consistent data yields less errors and we assume the remaining instances to represent the current concept or being sufficiently "close" to it.

We evaluate differently sized STMs and adopt the one with minimum error for MSTt+1 . We test only bisected window sizes to bound logarithmically the number of comparisons. Whenever the STM is shrunk, the set of discarded examples Ot is defined as

Cleaning and transfer

The LTM contains all data of former concepts that is consistent with the STM. This requires a cleaning of the LTM according to every seen example. In addition, whenever the STM is reduced in size, we do not simply discard the data sorted out, since it still may contain valuable information for future prediction. One example for such a situation is reoccurring drift, as methods preserving knowledge in this case do not have to relearn former concepts and therefore produce fewer errors. Instead, we transfer as much knowledge as possible into the LTM. Before doing so, we delete examples from the separated set Ot (see eq. 1) which are contradicting those in MSTt+1 . This adaption is formalized by two operations.

1. We clean a set A by another set B regarding an example (xi, yi) ∈ B

where A,B, ˆ A ⊂ Rn × {1, . . . , c} and (xi, yi) ∈ B. ˆ A is defined in two steps.

(1) We determine the k nearest neighbors of xi in B \ (xi, yi) and select the ones with label yi. These define the threshold

(2) The k nearest neighbors of xi ∈ A which are inconsistent to B are cleaned based on the threshold, yielding the result of this operation:

1 We used for all experiments k = 5, Lmin = 50, Lmax = 5000.

2. We also require a cleaning operation for the full set B

where A,B, ˆ A|B| ⊂ Rn × {1, . . . , c}. This is defined iteratively by applying the former cleaning for all (xi, yi) ∈ B = {(x1, y1), . . . , (x|B|, y|B|)} as

The adaption of the LTM takes place at two different steps. To ensure a consistent model at any time, cleaning takes place according to every incoming sample (xt, yt)

Whenever the STM is shrunk, the discarded set Ot is transferred into the LTM after cleaning, i.e. the LTM becomes

Compression of the long termmemory

In contrast to the FIFO principle of the STM, instances are not fading out as soon as the size limit of the LTM is reached. Instead, we condense the available information to a sparse knowledge representation via clustering. This enables a far longer conservation than possible with simple out fading. Formally, for every class label ˆ c we group the corresponding data points in the LTM as MLTˆ c = {xi|(xi, ˆ c) ∈ MLT}. We use the clustering algorithm kMeans++ [Arthur and Vassilvitskii, 2007] with |MLTˆ c |/2 clusters. The resulting prototypes ˆMLTˆ c represent the compressed original data. The LTM is given by the union of all prototypes

This process is repeated each time the size limit is reached leading to a self-adapting level of compression.

Model weight adaption

The weight of a memory is its accuracy averaged over the last mt samples, where mt = |MSTt | is the size of the current STM. Hence, the weight of the LTM at time stamp t equals

and analogous for STM and CM.

4 Experiments

We couple the SAM architecture with the kNN classifier and evaluate it in comparison to well-known state of the art algorithms for handling concept drift in streaming data. Next to the methods discussed in section 1, we compare against a kNN classifier with a sliding window of fixed size (kNNS). A rough taxonomy of the methods is depicted in Table 1. The evaluation was done with common artificial and real-world benchmarks, which are extensively described in [Losing et al., 2016]. Window based approaches were allowed to store up to 5000 samples but never more than 10% of the whole dataset. No dataset specific hyperparameter tuning was done.

The error rates of all experiments are shown in Table 2 1 . SAM significantly outperforms the others by having nearly half the error rate in average compared to the second best method LVGB. Even more important is the fact that whereas other methods struggle at some datasets our approach delivers robust results without any hiccup. All concept drift types are handled better or at least competitive. Our results confirm the fact that kNN is in general a very competitive algorithm in the streaming setting. It is quite surprising that the simple sliding window approach kNNS performs comparably well or even better than more sophisticated methods such as DACC or L++.NSE. A more detailed evaluation as well as an analysis of the memory behavior and their respective functions can be found in [Losing et al., 2016].

5 Conclusion

In this paper we presented the Self-Adjusting Memory (SAM) architecture, especially designed to handle heterogeneous concept drift within streaming data. It explicitly separates the current concept from former ones and preserves both in dedicated memories. Thereby, it omits a common weakness of available methods which simply discard former knowledge and, therefore, have to relearn concepts in case of reoccurring concept drift. Our method is easy to use in practice since it requires no task-specific meta-parameterization. We compared SAM with current state of the art methods on various artificial and real-world benchmarks. As the only algorithm it demonstrated consistently accurate results for heterogeneous concept drift.

1 The drift properties of the real-world data were determined as described in [Losing et al., 2017]