Request-and-Reverify: Hierarchical Hypothesis Testing for Concept Drift Detection with Expensive Labels

1 Introduction

In the last decades, numerous efforts have been made in algorithms that can learn from data streams. Most traditional methods for this purpose assume the stationarity of the data. However, when the underlying source generating the data stream, i.e., the joint distribution Pt(X, y), is not stationary, the optimal decision rule should change over time. This is a phenomena known as concept drift [Ditzler et al., 2015; Krawczyk et al., 2017]. Detecting such concept drifts is essential for the algorithm to adapt itself to the evolving data.

Concept drift can manifest two fundamental forms of changes from the Bayesian perspective [Kelly et al., 1999]:

∗This work was done when Shujian Yu was a research intern at Nokia Bell Labs, Murray Hill, NJ, USA.

1) a change in the marginal probability Pt(X); 2) a change in the posterior probability Pt(y|X). Existing studies in this field primarily concentrate on detecting posterior distribution change Pt(y|X), also known as the real drift [Widmer and Kubat, 1993], as it clearly indicates the optimal decision rule. On the other hand, only a little work aims at detecting the virtual drift [Hoens et al., 2012], which only affects Pt(X). In practice, one type of concept drift typically appears in combination with the other [Tsymbal, 2004]. Most methods for real drift detection assume that the true labels are available immediately after the classifier makes a prediction. However, this assumption is over-optimistic, since it could involve the annotation of data by expensive means in terms of cost and labor time. The virtual drift detection, though making no use of true label yt, has the issue of wrong interpretation (i.e., interpreting a virtual drift as the real drift). Such wrong interpretation could provide wrong decision about classifier update which still require labeled data [Krawczyk et al., 2017].

To address these issues simultaneously, we propose a novel Hierarchical Hypothesis Testing (HHT) framework with a Request-and-Reverify strategy for concept drift detection. HHT incorporates two layers of hypothesis tests. Different from the existing HHT methods [Alippi et al., 2017; Yu and Abraham, 2017], our HHT framework is the first attempt to use labels for concept drift detection only when necessary. It ensures that the test statistic (derived in a fully unsupervised manner) in Layer-I captures the most important properties of the underlying distributions, and adjusts itself well in a more powerful yet conservative manner that only requires labeled data when necessary in Layer-II. Two methods, namely Hierarchical Hypothesis Testing with Classification Uncertainty (HHT-CU) and Hierarchical Hypothesis Testing with Attribute-wise "Goodness-of-fit" (HHT-AG), are proposed under this framework in this paper. The first method incrementally tracks the distribution change with the defined classification uncertainty measurement in Layer-I, and uses permutation test in Layer-II, whereas the second method uses the standard Kolmogorov-Smirnov (KS) test in Layer-I and two-dimensional (2D) KS test [Peacock, 1983] in Layer-II. We test both proposed methods in benchmark datasets. Our methods demonstrate overwhelming advantages over stateof-the-art unsupervised methods. Moreover, though using significantly fewer labels, our methods outperform supervised methods like DDM [Gama et al., 2004].

Our methods

§ HHT features two layers of hypothesis test: Layer-I ouputs potential drift points, Layer-II reduce false alarms Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18)

2 Background Knowledge

2.1 ProblemFormulation

Given a continuous stream of labeled samples {Xt, yt}, t = 1, 2, ..., T, a classification model ˆ f can be learned so that ˆ f(Xt) ↦→ yt. Here, Xt ∈ Rd represents a ddimensional feature vector, and yt is a discrete class label. Let (XT+1,XT+2, ...,XT+N) be a sequence of new samples that comes chronologically with unknown labels. At time T + N, we split the samples in a set SA = (XT+N-nA+1,XT+N-nA+2, ...,XT+N) of nA recent ones and a set SB = (XT+1,XT+2, ...,XT+N-nA ) containing the (N - nA) samples that appear prior to those in SA. The problem of concept drift detection is identifying whether or not the source P (i.e., the joint distribution Pt(X, y)1 ) that generates samples in SA is the same as that in SB (even without access to the true labels yt) [Ditzler et al., 2015; Krawczyk et al., 2017]. Once such a drift is found, the machine can request a window of labeled data to update ˆ f and employ the new classifier to predict labels of incoming data.

2.2 RelatedWork

The techniques for concept drift detection can be divided into two categories depending on reliance of labels [Sethi and Kantardzic, 2017]: supervised (or explicit) drift detectors and unsupervised (or implicit) drift detectors. Supervised Drift Detectors rely heavily on true labels, as they typically monitor one error metrics associated with classification loss. Although much progress has been made on concept drift detection in the supervised manner, its assumption that the ground truth labels are available immediately for all already classified instances is typically over-optimistic. Unsupervised Drift Detectors, on the other hand, explore to detect concept drifts without using true labels. Most unsupervised concept drift detection methods concentrate on performing multivariate statistical tests to detect the changes of feature values Pt(X), such as the Conjunctive Normal Form (CNF) density estimation test [Dries and R¨uckert, 2009] and the Hellinger distance based density estimation test [Ditzler and Polikar, 2011]. Considering their high computational complexity, an alternative approach is to conduct univariate test on each attribute of features independently. For example, [Reis et al., 2016] develops an incremental (sequential) KS test which can achieve exactly the same performance as the conventional batch-based KS test.

Besides modeling virtual drifts of Pt(X), recent research in unsupervised drift detection attempts to model the real drifts by monitoring the classifier output ˆ yt or posterior probability as an alternative to yt. The Confidence Distribution Batch Detection (CDBD) approach [Lindstrom et al., 2011] uses Kullback-Leibler (KL) divergence to compare the classifier output values from two batches. A drift is signaled if the divergence exceeds a threshold. This work is extended in [Kim and Park, 2017] by substituting the classifier output value with the classifier confidence measurement. Another representative method is the Margin Density Drift Detection (MD3) algorithm [Sethi and Kantardzic, 2017], which tracks the proportion of samples that are within a classifier (i.e., SVM) margin and uses an active learning strategy in [ ˇZliobaite et al., 2014] to interactively query the information source to obtain true labels. Though not requiring true labels for concept drift detection, the major drawback of these unsupervised drift detectors is that they are prone to false positives as it is difficult to distinguish noise from distribution changes. Moreover, the wrong interpretation of virtual drifts could cause wrong decision for classifier update which require not only more labeled data but also unnecessary classifier re-training [Krawczyk et al., 2017].

1 The distributions are deliberated subscripted with time index t to explicitly emphasize their time-varying characteristics.

3 Request-and-Reverify HHT Approach

The observations on the existing supervised and unsupervised concept drift detection methods motivate us to propose the Request-and-Reverify Hierarchial Hypothesis Testing framework (see Fig. 1). Specifically, our layer-I test is operated in a fully unsupervised manner that does not require any labels. Once a potential drift is signaled by Layer-I, the Layer-II test is activated to confirm (or deny) the validity of the suspected drift. The result of the Layer-II is fed back to the Layer-I to reconfigure or restart Layer-I once needed.

In this way, the upper bound of HHT's Type-I error is determined by the significance level of its Layer-I test, whereas the lower bound of HHT's Type-II error is determined by the power of its Layer-I test. Our Layer-I test (and most existing single layer concept drift detectors) has low Type-II error (i.e., is able to accurately detect concept drifts), but has relatively higher Type-I error (i.e., is prone to generate false alarms). The incorporation of the Layer-II test is supposed to reduce false alarms, thus decreasing the Type-I error. The cost is that the Type-II error could be increased at the same time. In our work, we request true labels to conduct a more precise Layer-II test, so that we can significantly decrease the Type-I error with minimum increase in the Type-II error.

3.1 HHT with Classification Uncertainty (HHT-CU)

Our first method, HHT-CU, detects concept drift by tracking the classification uncertainty measurement ut = ‖ˆ yt - ˆP(yt|Xt)‖2, where ‖ · ‖2 denotes the ℓ2 distance, ˆP(yt|Xt) is the posterior probability estimated by the classifier at time index t, and ˆ yt is the target label encoded from ˆP(yt|Xt) using the 1-of-K coding scheme [Bishop, 2006]. Intuitively, the distance between ˆ yt and ˆP(yt|Xt) measures the classification uncertainty for the current classifier, and the statistic derived from this measurement should be stationary (i.e., no "significant" distribution change) in a stable concept. Therefore, the dramatic change of the uncertainty mean value may suggest a potential concept drift.

Different from the existing work that typically monitors the derived statistic with the three-sigma rule in statistical process control [Montgomery, 2009], we use the Hoeffding's inequality [Hoeffding, 1963] to monitor the moving average of ut in our Layer-I test.

Theorem 1 (Hoeffding's inequality) Let X1, X2,..., Xn be independent random variables such that Xi ∈ [ai, bi], and let ¯X = 1n ∑ni=1 Xi, then for ε ≥ 0:

where E denotes the expectation. Using this theorem, given a specific significance level α, the error εα can be computed as:

The Hoeffding's inequality does not require an assumption on the probabilistic distribution of ut. This makes it well suited in learning from real data streams [Fr´ıas-Blanco et al., 2015]. Moreover, the Corollary 1.1 proposed by Hoeffding [Hoeffding, 1963] can be directly applied to detect significant changes in the moving average of streaming values.

Corollary 1.1 (Layer-I test of HHT-CU) If X1, X2, ..., Xn, Xn+1, ..., Xn+m be independent random variables with values in the interval [a, b], and if ¯X = 1n ∑ni=1 Xi and ¯ Z = 1 n+m ∑n+m i=1 Xi, then for ε ≥ 0:

By definition, ut ∈ [0, √ K-1 K ], where K is the number of classes. ¯X denotes the classification uncertainty moving average before a cutoff point, and ¯ Z denotes the moving average over the whole sequence. The rule to reject the null hypothesis H0 : E( ¯X) > E( ¯ Z) against the alternative one H1 : E( ¯X) ≤ E( ¯ Z) at the significance level α will be ¯ Z - ¯X ≥ εα, where

Regarding the cutoff point, a reliable location can be estimated from the minimum value of ¯Xi + ε ¯Xi (1 ≤ i ≤ n+m) [Gama et al., 2004; Fr´ıas-Blanco et al., 2015]. This is because ¯Xi keeps approximately constant in a stable concept, thus ¯Xi + ε ¯Xi must reduce its value correspondingly.

The Layer-II test aims to reduce false positives signaled by Layer-I. Here, we use the permutation test which is described in [Yu and Abraham, 2017]. Different from [Yu and Abraham, 2017], which trains only one classifier ford using Sord and evaluates it on S′ord to get a zero-one loss ˆEord, we train another classifier f ′ord using S′ord and evaluate it on Sord to get another zero-one loss ˆE′ord . We reject the null hypothesis if either ˆEord or ˆE′ord deviates too much from the prediction loss of the shuffled splits. The proposed HHT-CU is summarized in Algorithm 1, where the window size N is set as the number of labeled samples to train the initial classifier ˆ f .

Algorithm 1 HHT with Classification Uncertainty (HHT-CU)

Input: Unlabeled stream {Xt}∞t=0 where Xt ∈ Rd ; Initially trained classifier ˆ f; Layer-I significance level Θ1; Layer-II significance level Θ2; Window size N. Output: Detected drift time index {Tcd}; Potential drift time index {Tpot}. 1: variables declaration 2: ¯Xcut: moving average of u1, u2, ..., ucut; 3: ¯ Zn: moving average of u1, u2, ..., un; 4: ε ¯Xcut and ε ¯ Zn : error bounds computed using Eqs. (2) and (4) respectively; 5: end variables declaration 6: {Tcd} = φ; {Tpot} = φ; 7: for t = 1 to∞do 8: Compute ut using ˆ f ; 9: Update ¯ Zt and ε ¯ Zt by adding ut; 10: if ¯ Zt + ε ¯ Zt ≤ ¯Xcut + ε ¯Xcut then 11: ¯Xcut = ¯ Zt; ε ¯Xcut = ε ¯ Zt ; 12: end if 13: if H0 : E( ¯Xcut) ≥ E( ¯ Zt) is rejected at Θ1 then 14: {Tpot} ← t; 15: Request 2N labeled samples {Xi, yi}t+N-1 i=t-N ; 16: Perform Layer-II test using {Xi, yi}t+N-1 i=t-N at Θ2; 17: if (Layer-II confirms the potentiality of t) then 18: {Tcd} ← t; 19: Update ˆ f using {Xi, yi}t+N-1 i=t ; 20: Initialize declared variables; 21: else 22: Discard t; 23: Restart Layer-I test; 24: end if 25: end if 26: end for

3.2 HHT with Attribute-wise "Goodness of fit" (HHT-AG))

The general idea behind HHT-AG is to explicitly model Pt(X, y) with limited access to y. To this end, a feasible solution is to detect potential drift points in Layer-I by just modeling Pt(X), and then require limited labeled data to confirm (or deny) the suspected time index in Layer-II.

The Layer-I test of HHT-AG conducts "Goodness-offit" test on each attribute xk |dk=1 individually to determine whether X from two windows differ: a baseline (or reference) windowW1 containing the first N items of the stream that occur after the last detected change; and a sliding window W2 containing N items that follow W1. We slide the W2 one step forward whenever a new item appears on the stream. A potential concept drift is signaled if at least for one attribute there is a distribution change. Factoring Pt(X) into ∏dk=1 Pt(xk ) for multivariate change detection is initially proposed in [Kifer et al., 2004]. Since then, this factorization strategy becomes widely used [ ˇZliobaite, 2010;

Reis et al., 2016]. Sadly, no existing work provides a theoretical foundation of this factorization strategy. In our perspective, one possible explanation is the Sklar's Theorem [Sklar, 1959], which states that if H is a d-dimensional joint distribution function and if F1, F2, ..., Fd are its corresponding marginal distribution functions, then there exists a d-copula C: [0, 1]d → [0, 1] such that:

The density function (if exists) can thus be represented as:

where c is the density of the copula C.

Though Sklar does not show practical ways on how to calculate C, this Theorem demonstrates that if P(X) changes, we can infer that one of P(xi) should also changes; otherwise, if none of the P(xi) changes, the P(X) would not be likely to change.

This paper selects Kolmogorov-Smirnov (KS) test to measure the discrepancy of Pt(xk )|dk=1 in two windows. Specifically, the KS test rejects the null hypothesis, i.e., the observations in sets A and B originate from the same distribution, at significance level α if the following inequality holds:

where FC(x) = 1 |C| ∑ 1{c∈C,c≤x} denotes the empirical distribution function (an estimation to the cumulative distribution function P(X < x)), s(α) is a α-specific value that can be retrieved from a known table, m and n are the cardinality of set A and set B respectively.

We then validate the potential drift points by requiring true labels of data that come from W1 and W2 in Layer-II. The Layer-II test of HHT-AG makes the conditionally independent factor assumption [Bishop, 2006] (a.k.a. the "naive Bayes" assumption), i.e., P(xi |xj , y) = P(xi |y) (1 ≤ i ̸= j ≤ d). Thus, the joint distribution Pt(X, y) can be represented as:

According to Eq. (7), we perform d independent twodimensional (2D) KS tests [Peacock, 1983] on each bivariate distribution Pt(xk , y)|dk=1 individually. The 2D KS test is a generalization of KS test on 2D plane. Although the cumulative probability distribution is not well-defined in more than one dimension, Peacock's insight is that a good surrogate is the integrated probability in each of the four quadrants for a given point (x, y), i.e., P(X ≤ x, Y ≤ y), P(X ≤ x, Y ≥ y), P(X ≥ x, Y ≤ y) and P(X ≥ x, Y ≥ y). Similarly, a potential drift is confirmed if the 2D KS test rejects the null hypothesis for at least one of the d bivariate distributions. HHT-AG is summarized in Algorithm 2, where the window size N is set as the number of labeled samples to train the initial classifier ˆ f .

Algorithm 2 HHT with Attribute-wise Goodness of fit (HHT-AG)

Input: Unlabeled stream {Xt}∞t=0 where Xt ∈ Rd ; Significance level Θ1; Significance level Θ2 (= Θ1 by default); Window size N .

Output: Detected drift time index {Tcd}; Potential drift time index

{Tpot}. 1: for i = 1 to d do 2: c0 ← 0; 3: W1,i ←first N points in xi from time c0; 4: W2,i ←next N points in xi in stream; 5: end for 6: while not end of stream do 7: for i = 1 to d do 8: Slide W2,i by 1 point; 9: Perform KS test with Θ1 on W1,i and W2,i; 10: if (KS test rejects the null hypothesis) then 11: {Tpot} ←current time; 12: W1 ←first N tuples in (xi , y) from time c0; 13: W2 ←next N tuples in (xi , y) in stream; 14: Perform 2D KS test with Θ2 on W1 and W2; 15: if (2DKS test rejects the null hypothesis) then 16: c0 ←current time; 17: {Tcd} ←current time; 18: Clear all windows and GOTO Step 1; 19: end if 20: end if 21: end for 22: end while

4 Experiments

Two sets of experiments are performed to evaluate the performance of HHT-CU and HHT-AG. First, quantitative metrics and plots are presented to demonstrate HHT-CU and HHTAG's effectiveness and superiority over state-of-the-art approaches on benchmark synthetic data. Then, we validate, via three real-world applications, the effectiveness of the proposed HHT-CU and HHT-AG on streaming data classification and the accuracy of its detected concept drift points. This paper selects soft margin SVM as the baseline classifier because of its accuracy and robustness.

4.1 Experimental Setup

We compare the results with three baseline methods, three topline supervised methods, and two state-of-the-art unsupervised methods for concept drift detection. The first two baselines, DDM [Gama et al., 2004] and EDDM [Baena-Garc´ıa et al., 2006], are the most popular supervised drift detector. The third one, we refer to as Attribute-wise KS test (A-KS) [ ˇZliobaite, 2010; Reis et al., 2016], is a benchmark unsupervised drift detector that has been proved effective in real applications. Note that, A-KS is equivalent to the LayerI test of HHT-AG. The toplines selected for comparison are LFR [Wang and Abraham, 2015], HLFR [Yu and Abraham, 2017] and HDDM [Fr´ıas-Blanco et al., 2015]. HLFR is the first method on concept drift detection with HHT framework, whereas HDDM introduces Hoeffding's inequality on concept drift detection. All of these methods are operated in supervised manner and significantly outperform DDM. However, LFR and HLFR can only support binary classification. In addition, we also compare with MD3 [Sethi and Kantardzic, 2017] and CDBD [Lindstrom et al., 2011], the state-of-the-art concept drift detectors that attempt to model Pt(y|X) without access to y. We use the parameters recommended in the papers for each competing method. The detailed values on significance levels or thresholds (if there exist) are shown in Table 1.

4.2 Results on Benchmark Synthetic Data

We first compare the performance of the HHT-CU and HHT-AG against aforementioned concept drift approaches on benchmark synthetic data. Eight datasets are selected from [Souza et al., 2015; Dyer et al., 2014], namely 2CDT, 2CHT, UG-2C-2D, MG-2C-2D, 4CR, 4CRE-V1, 4CE1CF, 5CVT. Among them, 2CDT, 2CHT, UG-2C-2D and MG-2C-2D are binary-class datasets, while 4CR, 4CRE-V1, 4CE1CF and 5CVT have multiple classes. To facilitate detection evaluation, we cluster each dataset into 5 segments to introduce 4 abrupt drift points, thus controlling ground truth drift points and allowing precise quantitative analysis. Quantitative comparison is performed by evaluating detection quality. To this end, the True Positive (TP) detection is defined as a detection within a fixed delay range after the precise concept change time. The False Negative (FN) is defined as missing a detection within the delay range, and the False Positive (FP) is defined as a detection outside the delay range range or an extra detection in the range. The detection quality is measured jointly with Precision, Recall and delay detection using Precision-Range curve and Recall-Range curve respectively (see Fig. 2 for an example), where Precision = TP/(TP + FP), and Recall = TP/(TP + FN).

For a straightforward comparison, Table 2 reports the number of required labeled samples (in percentage) for each algorithm, whereas Table 3 summarizes the Normalized Area Under the Curve (NAUC) values for two kinds of curves. As can be seen, HLFR and LFR can provide the most accurate detection as expected. However, they are only applicable for binary-class datasets and require true labels for the entire data stream. Our proposed HHT-CU and HHTAG, although slightly inferior to HLFR or LFR, can strike the best tradeoff between detection accuracy and the portion of required labels, especially considering the overwhelming advantage over MD3 and CDBD that are the most relevant counterparts. Although the detection module of MD3 and CDBD are operated in fully unsupervised manner, they either fail to provide reliable detection results or generate too much false positives which may, by contrast, require even more true labels (for classifier update). Meanwhile, it is very encouraging to find that HHT-CU can achieve comparable or even better results than DDM (i.e., the most popular supervised drift detector) with significantly fewer labels. This suggests that our classification uncertainty is as sensitive as the total classification accuracy in DDM to monitor the nonstationary environment. And, we can see HHT-AG can significantly improve the Precision value compared to A-KS. This suggests the effectiveness of Layer-II test on reverifying the validity of suspected drifts and denying false alarms. In addition, in the extreme cases when P(X) remains unchanged but P(y|X) does change, our methods (and the state-of-the-art unsupervised methods) are not able to detect the concept drift which is the change of the joint distribution P(X, y). This limitation is demonstrated in our experiments on the synthetic 4CR dataset where P(X) remains the same.

Table 2: Averaged number of required labeled samples in the testing set (%) for all competing algorithms. The performances of supervised detectors (HLFR, LFR, DDM, EDDM, and HDDM) are omitted because they require all the true labels (i.e., 100%). Also, MD3 and CDBD cannot be applied to multi-class datasets including 4CR, 4CRE-V1, 4CR1CF, and 5CVT. The least and second least labeled samples used for each dataset are marked with red and blue respectively. Our methods and A-KS do not detect any drifts on 4CR, and thus they use "0" labeled samples for 4CR. MD3 in many cases uses the least labels, but its detection accuracy is the worst as in Table 3.

4.3 Results on Real-world Data

In this section, we evaluate algorithm performance on realworld streaming data classification in a non-stationary environment. Three widely used real-world datasets are selected, namely USENET1 [Katakis et al., 2008], Keystroke [Souza et al., 2015] and Posture [Kaluˇza et al., 2010]. The descriptions on these three datasets are available in [Yu and Abraham, 2017; Reis et al., 2016]. For each dataset, we also select the same number of labeled instances to train the initial classifier as suggested in [Yu and Abraham, 2017; Reis et al., 2016].

The concept drift detection results and streaming classification results are summarized in Table 4. We measure the cumulative classification accuracy and the portion of required labels to evaluate prediction quality. Since the classes are balanced, the classification accuracy is also a good indicator. In these experiments, our proposed HHT-CU and HHT-AG always feature significantly less amount of false positives, while maintaining good true positive rate for concept drift detection. This suggests the effectiveness of the proposed hierarchical architecture on concept drift reverification. The HHT-CU can achieve overall the best performance in terms of accurate drift detection, streaming classification, as well as the rational utilization of labeled data.

5 Conclusion

This paper presents a novel Hierarchical Hypothesis Testing (HHT) framework with a Request-and-Reverify strategy to detect concept drifts. Two methods, namely HHT with Classification Uncertainty (HHT-CU) and HHT with Attributewise "Goodness-of-fit" (HHT-AG), are proposed respectively under this framework. Our methods significantly outperform the state-of-the-art unsupervised counterparts, and are even comparable or superior to the popular supervised methods with significantly fewer labels. The results indicate our progress on using far fewer labels to perform accurate concept drift detection. The HHT framework is highly effective in deciding label requests and validating detection candidates.

(a) USENET1

(b) Keystroke

(c) Posture