Active Learning for Data Streams Under Concept Drift and Concept Evolution

Abstract

Data streams classi cation is an important problem however, poses many challenges. Since the length of the data is theoretically in nite, it is impractical to store and process all the historical data. Data streams also experience change of its underlying distribution (concept drift ), thus the classi er must adapt. Another challenge of data stream classi cation is the possible emergence and disappearance of classes which is known as (concept evolution) problem. On the top of these challenges, acquiring labels with such large data is expensive. In this paper, we propose a stream-based active learning (AL) strategy (SAL) that handles the aforementioned challenges. SAL aims at querying the labels of samples which results in optimizing the expected future error. It handles concept drift and concept evolution by adapting to the change in the stream. Furthermore, as a part of the error reduction process, SAL handles the sampling bias problem and queries the samples that caused the change i.e., drifted samples or samples coming from new classes. To tackle the lack of prior knowledge about the streaming data, non-parametric Bayesian modelling is adopted namely the two representations of Dirichlet process; Dirichlet mixture models and stick breaking process. Empirical results obtained on real-world benchmarks show the high performance of the proposed SAL method compared to the state-of-the-art methods.

Keywords

• Data Streams
• Active Learning
• Concept Drift
• Concept Evolution
• Novelty detection

Introduction

with minimal supervision. AL deliberately queries particular instances to train the classi er using as few labelled data instances as possible. AL for data streams is more challenging because both concept drift and concept evolution can occur at any time and anywhere in the feature space. Another challenge associated with AL, in general, is the sampling bias [18] where the sampled training set does not re ect the underlying data distribution in a destructive way. Basically, AL seeks to query samples which labelling them signi cantly improves the learning. That is instead of sampling from the data underlying distribution, AL deliberately creates a bias training set. However, as AL becomes increasingly con dent about its sampling assessment, valuable samples could be ignored and the bias of the training set could become harmful.

In this paper, we propose an AL algorithm, called Stream Active Learning (SAL), that overcomes all the aforementioned challenges in a uni ed systematic way. In contrast to most of the existing AL approaches which adopt heuristic AL criteria, SAL aims at directly optimizing the expected future error [19]. Similar AL approaches are proposed in [19{21], however, they work in o ine setting and do not take into account the challenges associated with data streams. In our previous work [22], we proposed a bi-criteria AL approach (BAL) that seeks to select data samples that reduce the future expected error. Because closed form calculation of the expected future error is intractable, BAL approximates it by combining online classi cation and online clustering models. The classi cation model estimates the conditional distribution of the labels given the data, while the clustering model estimates the marginal distribution of the data. BAL only considers binary classi cation and ignores concept evolution. In contrast, SAL adopts the same concept as in [22] with some di erences. Instead of using two existing classi cation and clustering models as in the case of BAL, SAL uses a uni ed non-parametric Baysian model. Simplistically, the proposed model is a Dirichlet process mixture model [23] with a stick breaking prior [24] attached to each mixture component. This prior is applied over the classes of the data in the mixture components. The model can approximate the conditional and marginal distributions. Dirichlet process mixture model is used to approximate the marginal distribution. It allows the complexity of the model to grow as more data is seen. Such proprieties is useful in the case of data stream as not much prior knowledge is available. In contrast to BAL, SAL allows multi-class classi cation with dynamic number of classes and therefore capable of dealing with concept evolution. The application of stick-breaking prior over the classes allows the potential growth of the number of classes. We employ a particle lter method [25{30] to perform online inference.

As in [22, 31], SAL handles sampling bias problem caused by AL using importance weighted empirical risk [32]. Such problem is more severe in online setting as the model on which AL bases its queries has to adapt. On the other hand, the adaptation can depend on the queried data. While techniques in [22,31] are limited to binary classi cation, SAL is capable of performing classi cation with changing number of classes.

To motivate the proposed approach, consider the example of activity recognition in the smarthome setting. Instead of collecting a static set of data from the deployed sensors then training a learner o ine, considering the data as a stream and continuously training a learner online is more realistic. Firstly, the online learner can be fed with streaming data where it adapts to di erent static settings such as di erent house settings and various sensors layout. Such learning can also adapt to dynamic change within the same scenario concept drift while processing an in nite data length. For example, change in the individual activity patterns (e.g., the individual's walk style depends on his/her health). Furthermore, for o ine learner, the number of classes are xed while in reality, it can change concept evolution; for example, the di erent activities of an individual can not be counted and he/her may come up with new ones over time. Secondly, employing AL can lead to more autonomous learning as the algorithm can be plugged in with no knowledge about the potential activities (labels). Instead of monitoring the individual activities, AL can query the individual about his/her own activities when necessary. However, it is not practical to keep asking the person about his activities all the time. To summarize, this application example includes following data streams challenges: in nite length, concept drift, concept drift and labelling expense. 2

Active Learning Approach

Many active learning approaches seek to minimize an approximation of the expected error of the learner Eq. ( 1 ) [19{21]. SAL follows the same methodology but with more challenging setting where the data comes as a stream.

R = x

L(p^(yjx); p(yjx))p(x)dx 1 1 1 Where (x; y) is a pair of random variables, such that x represents the data instance (observation) and y is its class label. p(yjx)) and p(x) are the true conditional and marginal distributions respectively. p^(yjx) is the learner conditional distribution used to classify the data. The learner receives observations drawn from p(x) with latent labels y unless they are queried by the AL algorithm. We denote the labelled observations up to time t as XLt and their labels as YLt . The unlabelled observations up to time t are denoted as XUt . We also use Xt to denote the sequence (x1; x2; :::; xt). We separate the learner algorithm or the hypothesis class from the AL strategy so that we can simply plug in any learner to test the AL. Let p(yjx; ) refer to the learner conditional distribution p^(yjx), where is the parameter vector that governs the learner distribution.

In the following, we discuss the o ine AL approaches used to minimize an approximation of Eq. ( 1 ) as a closed form solution is not available. Then we present our online AL approach. Authors in [20] approximate the expected error using the empirical risk over the unlabelled data: jPU j x2PU ^ RPU (

PL ) =

X L(p(yjx;

PL ); p(yjx)) where PU and PL are pools of unlabled and labled samples. We refer to the classi er parameters after being trained on PL as PL . Di erent types of loss functions can be adopted according to the classi cation model. Active learning seeks to optimize Eq.( 2 ) by asking for the labels of the samples that, once incorporated in the training set, the empirical risk drops the most. Ideally, the selection should depend on how many queries can be made. However, the solution of such optimization problem is NP hard. Hence, most commonly used AL strategies greedily select one example at a time [20, 21, 31].

x~ = arg min R^PU (x;y) ( x2PU

PL+(x;y) ) The empirical risk over the labelled and unlabelled samples are considered in [21]: ^ RPL[PU (

PL ) =

X jPL [ PU j x2PL[PU

L(p(yjx;

PL ); p(yjx))

Let q Ber(a) a random variable distributed according to a Bernoulli distribution with parameter a. It indicates if the data instance x is queried. The risk incurred when training the learner is the one related to the labelled data: ( 1 ) ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) In active learning, a subset of unlabled samples is selected for labelling. Thus, the data instances used to train the model are sampled from a distribution induced by the AL queries instead of the data underlying distribution. That is, the distribution of the queried data p(xjq = 1) is di erent from the original one p(x). Hence, Equation ( 5 ) is a biased estimator of ( 1 ) and the learned classi er may be less accurate than when learned without using AL. Similar to [22, 31], we use the importance weighting technique [32] in order to come up with unbiased estimator. Thus, Equation ( 5 ) can be written as follows:

R^P0L (

PL ) =

1 X 1 jPLj x2PL p(q = 1jx)

L(p(yjx;

PL ); p(yjx)) Thus, the unbiaseness of the estimator above can be shown as:

jPLj x2PL ^ RPL (

PL ) =

X L(p(yjx;

PL ); p(yjx)) Ex p(xjq=1) R^P0L (

PL ) = Ex p(x) R^PL (

PL )

So far, we assumed that the underlining conditional distribution p(yjx) is known, but in reality it is not. Thus, we need to estimate it. Furthermore, in online setting, comparing the e ect of labelling certain data instance against that of other data instances (as done in Eq.( 3 )) is not possible. Thus, storing pools of data seen so far might be a choice; however, it will break the online where t denotes the classi er parameters after being trained on fXLt ; YLt g . Based on Equations ( 8 ) and ( 9 ), we can develop an online querying strategy similar to the one proposed in Eq. ( 3 ). The data instance can be assessed on-the- y by comparing the error reduction incurred by labelling it against the highest error reduction. To compute the highest error reduction, we can generate a pool of unlabed data at each time step from p(xjXUt ). Then we search for the sample that labelling it incurred the highest error reduction. More direct approach is to use a non-convex optimizer to nd the highest error reduction then take it as a reference. Both approaches are computationally expensive (time-consuming) as they involve integrals estimation. Further, we need to compute the expectation of the error reduction as the labels are unknown which makes the computation more expensive.

We can conclude from Eq. ( 8 ), ( 9 ) that the error can be reduced by labelling the samples that have the largest contribution to the current error. This contribution can be expressed through the following equations:

R^Dt 1;XUt 1 ( t 1; xt) = L(p(ytjxt; t 1); p(ytjxt; Dt 1))p(xtjXUt 1 )

R^D0t 1;XLt 1 ( t 1; xt) = L(p(ytjxt; t 1); p(ytjxt; Dt 1))p~(xtjXLt 1 ) Once xt is queried, SAL integrates the weigh e ect of p(qt = 1jxt) into the current labled data marginal distribution by updating it with xt ( p(qt=11jxt) ) times. Hence, p~(xtjXLt 1 ) represents the labled data marginal distribution involved the weight e ect of the previously queried samples. Equation ( 10 ) encourages querying samples that have strong representativeness among the unlabled data and that are expected to be wrongly classi ed; while Eq.( 11 ) encourages querying those which have strong representativeness among the labelled data, but, still wrongly classi ed. Such samples are rare. However Eq. ( 11 ) allows the learner to be completely independent from the sampling approach, as it integrates the sampling bias independently from the learner algorithm. Thus, as the learner proceeds, Eq. ( 11 ) also helps to switch the focus from only representative samples to samples which are underestimated.

The querying probability is computed by comparing the samples with the one that has the largest contribution to the error. A solution can be devised by trying to optimize Eq.( 10 ) and Eq.( 11 ). However, to avoid time-consuming computation and keeping the AL algorithm independent of the learner, we take the comparator sample from the already seen ones. A forgetting factor empirically set to 0:9 is used to consider the dynamic nature of the data: ( 8 ) ( 9 ) ( 10 ) ( 11 ) ( 12 ) ( 13 ) learning principle. We, instead, estimate the probability of unlabled and labled data at time t. Consider p(yjx; Dt), p(xjXUt ) and p(xjXLt ) as estimators for the true conditional distribution, the unlabled data distribution and the labled data distribution at time t, where Dt represents the set of the previously seen data instances including the labels of the queried ones. Thus, Equation ( 4 ) with the importance weighting on the labelled data can be written as the sum of the following equations: ^ RDt;XUt ( t) = R^D0t;XLt ( t) =

Z

L(p(yjx; t); p(yjx; Dt))p(xjXUt )dx x Z L(p(yjx; t); p(yjx; Dt)) x p(q = 1jx)

p(xjXLt )dx

At = max (R^Dt 1;XUt 1 ( t 1; xt) + R^D0t 1;XLt 1 ( t 1; xt)); At 1 p(qt = 1jxt; Dt 1; t 1) =

A1t R^Dt 1;XUt 1 ( t 1; xt) + R^D0t 1;XLt 1 ( t 1; xt)

The number of classes evolves over time such that new classes may emerge and old ones may vanish. Thus, p(ytjxt; Dt 1)) in Equations ( 10 ) and ( 11 ) must account for all the classes that may appear in the data stream. Theoretically, the length of the stream is in nite, which means that the probability of receiving in nite di erent classes is not zero. Hence, the support of the distribution over the classes must be in nite. To allow that stick-braking distribution is imposed as a prior over the class. Intuitively, this prior allows foresee a probability on the creation of new classes. As for forgetting old irrelevant classes, we propose an online estimator of p(ytjxt; Dt 1)) equipped with forgetting factor to handle the evolving nature of data. The same model estimates online p(xtjXLt 1 ) and p(xtjXUt 1 ). More details are found in the next section. The steps of SAL are portrayed in Fig.1 (the variables are de ned in Sec. 3).

Under limited labelling resources, a rationale querying strategy to optimally use those resources needs to be applied. To this end, the notion of budget was introduced in [33] in order to estimate the labelling budget. Two counters were maintained: the number of labelled instances ft = jXLt j and the budget spent so far: bt = jdata sefetn so farj = jxf1t:tj .

As data arrives, we do not query unless the budget is less than a constant Bd and querying is granted by the sampling model. However, over in nite time horizon this approach will not be e ective. The contribution of every query to the budget will diminish over the in nite time and a single labelling action will become less and less sensitive. Authors in [33] propose to compute the budget over xed memory windows w. To avoid storing the query decisions within the windows, an estimation of ft and bt were proposed: ( 14 ) ( 15 ) ^bt = ^ ft w where f^t is an estimate of how many instances were queried within the last w incoming data examples.

f^t = (1

1=w)f^t 1 + labellingt 1 where labellingt 1 = 1 if instance xt 1 is labelled, and 0 otherwise. Using the forgetting factor (1 (1=w)), the authors showed that ^bt is unbiased estimate of bt.

In the present paper, this notion of budget will be adopted in SAL so that we can assess it against the active learning proposed in [33]. Note that in our experiments in relation to the budget, we set w = 100 as in [33]. 3

Estimator Model

In this section, we develop the model that will be used to estimate the distributions (in Eq. ( 10 ) and ( 11 )) needed for SAL to work online. First, we give a brief background on Dirichlet process (DP) which is the core of our model. DP is used as a non-parametric prior in Dirichlet process mixture model (DPMM) which, in contrast to parametric model, allows the number of components to vary during inference. Second, we describe the proposed estimator model and develop an online particle inference algorithm for it. While DPMM estimates the marginal distributions, the conditional distribution is estimated by an upgrade of DPMM. It accommodates labelled data using a stickbreaking process [34] over the classes. These estimations are done on- y by performing online inference using the particle inference algorithm.

(a) DP model

mixture (b) Finite mixture model DP is one of the most popular prior used in the Bayesian non-parametric model. Its rst use by the machine learning community dates back to [35, 36]. In general, a stochastic process is a probability distribution over a space of paths which describe the evolution of some random value over time. DP is a family of stochastic processes whose paths are probability distributions. It can be seen as an in nite-dimensional generalization of Dirichlet distribution, where it is a prior over the space of countably in nite distributions. In the literature, DP has been constructed in di erent ways, the most well-known constructions are: in nite mixture model [36], distribution over distributions [37], Polya-urn scheme [38] and stick-breaking [34]. For more details, the interested reader is referred to [39]. zij kjG0 xijzi;

Dirichlet( 0=L; :::; 0=L) Discrete( 1; :::; L) G0

F ( zi ) F ( zi ) denotes the distribution of the observation xi given zi, where zi is the parameter vector associated with component zi. Here zi indicates which latent cluster is associated with observation xi. Indicator zi is drawn from a discrete distribution governed by parameter drawn from dirichlet distribution parametrized by 0. We can simply say that xi is distributed according to a mixture of components drawn from prior distribution G0 and picked with probability given by the vector of mixing proportions . The model represented by Eq.( 16 ) above is a nite mixture model, where L is the xed number of parameters (components). The in nite mixture model can be derived by letting L ! 1, then can be represented as an in nite mixing proportion distributed according to stick-breaking process GEM ( ) [34]. Thus, Eq.( 16 ) can be equivalently expressed according to the graphical representation as:

Gj ; G0

ijG xij i

DP ( ; G0) G

F ( i) where G = Pk1=1 k i is drawn from DP prior, i is a Dirac delta function centred at i. Technically, DP is a distribution over distribution [37], where DP (G0; ), is parametrized by the base distribution G0, and the concentration parameter . Since DP is distribution over distributions, a ( 16 ) ( 17 ) For an observation xi with zi 6= zj f or all j < i, a new component gets created with indicator zi = cnew. For more details about the process of obtaining the prior distribution, reader is referred to [40]. 3.2

Proposed Model

For the sake of simpli cation, we start with an unsupervised clustering model, then we add a new ingredient to the model in order to accommodate labelled data.

p(zi = cjz1; :::; zi 1) = nc i + 0=L Unsupervised clustering Figure 3 shows the in nite mixture model where is drawn from a stick-breaking process GEM ( ) and G0 is a Normal-Inverse-Wishart distribution N IW (:j 0; 0; k0; v0). Where 0 is the prior of the clusters' means, 0 controls the variance among their means, k0 scales the di usion of the clusters means and v0 is the degree of freedom of the Inverse-Wishart distribution. Given the concentration parameter 0 and the prior distribution parameters f 0; 0; k0; v0g, we aim at computing online the probability of the current data assignment to the existing clusters p(ztjxt; x1:t 1) without the need for saving all data x1:t 1. draw G from it is a distribution. Thus, we can sample i from G. Back to Eq.( 16 ), by integrating over the mixing proportion , we can write the prior for zi as conditional probability of the following form [40]: where nc i is the number of zi for j < i that are equal to c. By letting L goes to in nity we get the following equations: p(ztjxt; x1:t 1) = X p(ztjz1:t 1; xt; x1:t 1)p(z1:t 1jxt; x1:t 1)

Following [27], we de ne a state vector Ht that summarizes the data seen up to time t. Ht = fzt; mt; nt; stg where mt is the number of components, nt is the number of data assigned to each component and st is the su cient statistics for each mixture component. The data x1:t 1 along with their assignments z1:t 1 in the rst term of the second Equ. in ( 20 ) can be replaced by Ht 1: p(xtjzt; z1:t 1; x1:t 1) = p(xtjzt; Ht 1) = ( 19 ) ( 20 ) If zt refers to a new component, p( jzt; Ht 1) becomes equivalent to the prior G0. Otherwise, zt refers to an already existing component. Then p( jzt; Ht 1) becomes equivalent to p( jszt;t 1). The su cient statistics (mean, covariance) szt;t 1 = fsuzt;t 1; sczt;t 1g, where Thus, Eq.21 can be solved given Ht 1 and G0. More details can be found in the Appendix. The rst term of the third Equation in ( 20 ) can be written as follows: The assignment z1:t 1 in the rest of Eq.( 20 ) can be replaced by Ht 1. ( 22 ) ( 23 ) Equation ( 24 ) has the same solution as Eq.( 19 ). Equation ( 25 ) is the posterior of the state vector Ht 1 which must be inferred online. Thus, the task is to track the posterior of Ht online. Assume that the posterior p(Ht 1jx1:t 1) is known, we need to nd the updated posterior p(Htjx1:t). As the number of assignments con gurations grows exponentially, it is impossible to compute the distribution over all possible Ht 1. To solve this problem, we resort to particle lters to approximate the posterior by a set of N weighted particles.

p(Htjx1:t) =

N X w(i) (Ht

t i=1

Ht(i)) where each Ht(i) represents the state vector with di erent assignments z1:t of the data seen so far. The weight wt(i) re ects the importance of the particle and is the dirac delta function. So, given a set of N particles and their normalized weights at time t 1, we can approximate the posterior at time t in two steps:

Updating:

Z

Ht 1 p(Htjx1:t) /

p(HtjHt 1; xt)p(xtjHt 1)p(Ht 1jx1:t 1) Given a particle Ht(i)1 along with its weight wt(i)1, the update can be written as follow. p(Htjx1:t) /

N X p(HtjHt(i)1; xt)p(xtjHt(i)1)wt(i)1 i=1 Following the update step, the number of resulting particles for each Ht(i)1 equals to the number of existing components mt(i)1 + 1. The new assignments zt expresses the di erent con gurations of the new particles. Therefore, p(Ht(j)jHt(i)1; xt) = p(zt = jjHt(i)1; xt)

/ p(xtjzt = j; Ht(i)1)p(zt = jjHt(i)1) Htj = 8>zt > >>>nj;t > > >>>nk;t > > >>suj;t > > > >>>scj;t > > > > > < >>>>zt > >>>mt > > >>>nj;t > > >>nk;t > > >>>suj;t > > >:scj;t

M X minfcwtj ; 1g = N j=1 where n0zt;yt;t refers to the number of the data which are assigned to component zt and have label yt at time t. So, to compute ( 34 ), the distribution of the labels to the data in each component must be = j = = = = ( 34 )

The second term of Eq.(28) can be written as follows

p(xtjHt(i)1) =

X p(xtjzt; Ht(i)1)p(ztjHt(i)1) where is a forgetting factor which allows the components to adapt with change. Equation ( 31 ) can be solved in the same way as Eq.( 29 ). Having approximated all the terms of Eq.( 28 ), we end up with M = PN

i=1(mit 1 + 1) new particles along with their weight wtj . So, we move to the next step which reduces the number of created particles to a x number N .

Re-sampling:

We follow the resampling technique proposed in [28] which discourages the less-likely particles (con gurations) and improves the particles that explain the data better. It keeps the particles whose weight is greater than 1=c, and re-samples from the remaining particles. The variable c is the solution of the following equation: The weight of re-sampled particles is set to 1=c and the weight of the particles greater than 1=c is kept unchanged.

Next, we consider the labels by proposing stick-breaking prior over the classes. Semi-supervised clustering The stick-breaking component assignment is the same as the Gaussian component assignment. That is, every Gaussian component is associated with a stick-breaking one GEM ( 1 ) and the variable zt controls the component selection (see Fig.4).

Assume that at time t, we need to predict the distribution over yt given all the data and their labels seen so far.

p(ytjxt; Dt 1) =

X p(ytjzt; Dt 1)p(ztjDt 1; xt) zt The rst term of Eq.( 33 ) can be computed in a similar way as Eq.( 19 ), where zt selects the stickbreaking component generating yt. Hence, the probability of yt depends only on the data assigned to component zt. More details can be found in the appendix p(ytjzt; Dt 1) / (n0zt;yt;t 1 yt is an existing class yt is a new class memorized. The second term of Eq.( 33 ) is similar to ( 20 ) but with additional observation y1:t 1. We propose to include the label information in the state vector Ht so that it becomes Ht0 = fHt; n0tg, where n0t is the label distribution over the data in each component. Hence, p(ztjDt 1; xt) is solved in the same way as in Eq.( 19 ) after replacing Ht 1 by Ht0 1. Similar to what we did in Eq.( 25 ), the posterior of the state vector Ht0 1 must be tracked online. Similar to the previous unsupervised model, we resort to particle lters to approximate the posterior by a set of N weighted particles. p(Ht0jDt) =

N X w0(i) (Ht0

t i=1

Ht0(i)) We can approximate the posterior at time t using two steps; updating and re-sampling. The resampling step is the same as in the unsupervised clustering; we just replace the old weights with the new ones. The updating step follows the same way as in the unsupervised clustering. p(xt; ytjHt0(i)1) =

X p(xt; ytjzt; Ht0(i)1)p(ztjHt0(i)1) p(xtjx1:t 1) =

X p(xtjz1:t 1; x1:t 1)p(z1:t 1jx1:t 1) The estimation of p(yt+1jxt+1; Dt)) in SAL is computed in Eq.( 33 ). where the terms of Eq.( 41 ) are computed as in Eq.( 20 ). The estimation of p(xtjxUt 1 ) and p(xtjxLt 1 ) in SAL can be derived from Eq.( 41 ) by simply memorizing two state vectors, one for p(Ht0jDt) /

N X p(Ht0jHt0(i)1; xt; yt)p(xt; ytjHt0(i)1)w0(i)

t 1 i=1 p(Ht0(j)jHt0(i)1; xt; yt) = p(zt = jjHt0(i)1; xt; yt) / p(xt; ytjzt = j; Ht0(i)1)p(zt = jjHt0(i)1) p(xt; ytjzt = j; Ht0(i)1) = p(xtjzt = j; Ht0(i)1)p(ytjzt = j; Ht0(i)1)) The second term of Eq.( 37 ) is computed in Eq.( 24 ). Equation ( 38 ) can be solved in the same way as the rst term in Eq.( 33 ) and Eq.( 34 ). The elements of the new state vector are updated in the same way as in Eq.( 30 ): ( 35 ) ( 36 ) ( 37 ) ( 38 ) ( 39 ) ( 40 ) ( 41 ) the unlabelled data Htu and one for the labelled data Htl. To sum up, three estimator model represented by state vectors associated with their weights: f(Ht0; wt0), (Htu; wtu) and (Htl; wl) t g and their hyper-parameters: f( 0; 1; 0; 0; k0; v0), ( 0u; 1u; 0u; 0u; k0u; v0u) and ( 0l; 1l; l0; l0; k0l; v0l)g are maintained. 4

Experiments

We evaluate SAL on three real-world benchmark datasets widely used in the AL area: Pageblocks, Covertype (Forest) and KDDCup 99 network intrusion detection (KDD). These datasets are downloaded from UCI repository [41]. SAL is compared against two types of stream-based AL approaches. The rst type of approaches [33] does consider challenges of data stream namely the in nite length of the data and concept drift, but ignore concept evolution. The methods based on [33] are as follows: - VarUn: Variable Uncertainty, stream-based AL.

- RanVarUn: Variable Randomized Uncertainty, stream-based AL.

We also consider A baseline random sampling: Rand. The aim of this comparison is to show how SAL performs against these methods just cited (with restricted budget). Fortunately, these methods are integrated in the MOA data stream software suite [42] which helps carry out the experiments without the need to implementing them.

The second type of stream-based AL approaches are developed to cope with concept evolution [43, 44]. However, they do not explicitly handle concept drift and avoid the sampling bias problem. More details about these methods are discussed in Sec. ??. We consider the following - lowlik : Low-likelihood criterion specialized for quick unknown class discovery [44] - qbc: Query-by-Commitee, a stream-based verion is used in [43] - qbc-pyp: Stream-based joint exploration-explotation AL proposed in [44]

These methods have shown good class discovery performance on unbalanced data including the datasets that we use in this study. Hence, by comparing against them, we highlight the e ciency of SAL in handling the concept evolution in challenging setting where the class of the datasets are highly unbalanced. We set up the same settings described in [43].

For all the experiments, the number of particles N is set to 5. Normally, as we increase the number of particles, the estimator model gives better estimation, but the computation becomes heavier.

All experiments are repeated 30 times and the results are averaged in order to capture the real performance of SAL. 4.1

datasets The three datasets Pageblocks, Forest and KDD show multiple classes in naturally unbalanced proportions. Such property will help manifest the capability of SAL to e ciently discover the unknown classes while querying data samples that result in good classi cation performance. The datasets are presented in Tab.1 and Tab.2, where where N is the number of instances, d is the number of features/attributes, Nc is the number of classes, S% and L% are proportions of smallest and largest classes, respectively.

Pageblocks dataset: the task is to separate text from graphic area of the page layout document. Thus, the classi er has to classify the blocks of the page detected by a segmentation process. The blocks classes are text, horizontal line, picture, vertical line and graphic.

Forest dataset: this dataset is often used as a benchmark for evaluating stream classi ers. The task is to predict forest cover type from cartographic variables.

KDD dataset: This dataset contains TCP connection records extracted from LAN network tra c at MIT Lincoln Labs over a period of two weeks. Each record refers either to a normal connection or attack.

In this paper, we use the full Pageblocks but only portions of Forest and KDD datasets. When comparing against the rst type of competitors [33], We use 10000 instances from the forest dataset and 23535 instances from KDD dataset. As for the second type of competitors [43, 44], we follows the setting in [43] where 5000 and 33650 instances are used from Forest and KDD respectively. In this section, we evaluate SAL against the methods in [33] in order to study classi cation e ciency.

Settings As we have shown previously, SAL is exible and any learner (classi er) can be simply plugged in. Here, we use Naive Bayes as a learner as in [33].

The evaluation of the algorithms is based on a prequential methodology: each time we get an instance, rst we compute the probability of querying it. If selected, then it is used to train the learner (classi er). Otherwise, it is used for testing the classi er given that all samples labels are known insight. The classi cation performance of SAL is measured according to the average accuracy which is the correctly classi ed data samples divide by the total testing data samples.

The hyper-parameters of the estimator model are xed apriori (see Tab. 3). However, changing their values has slight e ect on the nal results. In order to allow obscure prior, we set 0, 0u and 0l to 1. The means u0, u0u and ul0 are set to 0. The covariance matrices 0, 0u and 0l are roughly set to be as large as the dispersion of the data. We set them to the identity matrix times the distance between the two farest points in the data: (x1;x2)2X(jjx1x2jj)I max ( 42 ) The degree of freedom of the Wishart distributions v0, v0u , v0l must be greater than d. We set them to d + 2. The hyper-parameters k0, k0u and k0l are empirically set to 0:01. Because at this stage, we are interested only in the classi cation error, the hyper-parameter 1 which controls the prior over the classes is set to a low value. It can be seen from Eq. ( 34 ) that when 1 is low the model tends to put low probability on the emergence of new classes. We empirically set it to 0:01. The e ect of the forgetting factors and 0 in Eq.( 30 ) and Eq.( 39 ) on SAL classi cation accuracy is studied in Fig. 6, Fig.7 and Fig8. We, rst, set the forgetting factors 0 to 0:6 and study the e ect of for the three datasets. Then, we set to the values that result in the best accuracy and study the e ect of 0. Finally, the forgetting factors and 0 are set to the values that result in the best accuracy. However, we can notice that the accuracy is almost insensitive to the change of the forgetting factors values.

The proposed non-parametric Bayesian model tackles the lack of prior knowledge about the streaming data where the parameter settings of SAL estimator model are almost the same for all the three datasets. SAL performance is almost insensitive to the parameter settings of the model. (a) Pageblocks dataset (b) Forest dataset (c) KDD dataset Performance Analysis Following similar setting in [33], we carry out the experiments on the three datasets using di erent budget values [0:01; 0:4]. Figure 5 shows the classi cation accuracy of SAL and the competitors for di rent values of budget Bd.

SAL noticeably outperforms the competitors on the three datasets. While the competitors show inconsistency especially on Pageblock dataset, SAL provides classi cation accuracy which consistently increases as more data samples are queried. For example, VarUn and RanVarUnc produce uctuating accuracy on Pageblocks dataset for Bd = 0:05, 0:1, 0:2, 0:25, 0:3, 0:35 and 0:4. Moreover, the baseline Rand outperforms VarUn and RanVarUnc for some budget values. When using the Forest dataset, Rand shows comparable performance to VarUn and RanVarUnc. As for KDD dataset, even though the accuracy almost converges when using budget over 0:3, SAL strongly beats Rand, VarUn and RanVarUnc using budget less than 0:1. Such superior accuracy with low budget is a very strong point for SAL as it aligns with the goal of AL which is high accuracy with low budget.

The reasons why SAL outperforms the competitors are rooted from the fact that SAL tries to directly minimize the expected future error instead of employing heuristic AL criteria as the competitors do. We can intuitively highlight two main di erences between SAL and the competitors AL approaches. Firstly, SAL explicitly handles sampling bias problem resulting in drift aware AL strategy. On the other side, RanVarUn combines naive randomization with stationary online uncertainty criterion to deal with drift. By doing so, the budget is wasted on some random queries. VarUnc does not handle sampling bias problem. Secondly, SAL takes into account the importance of data marginal distribution while the competitors do not. In order to highlight the capability of concept evolution (class discovery), SAL is compared against [43, 44], the state-of-the-art methods.

Settings The performance of SAL is measured using the average class accuracy [45]. The nal accuracy is obtained by averaging accuracies. It is worth mentioning that the nal class accuracy is fairly penalized when there are mi-classi cations in small classes.

SAL takes into account the data density when querying. It might then consider the data representing small classes as outliers or noise and therefore never queries them. To avoid such a scenario and to improve the class discovery performance of SAL, we increase the importance of the small classes by integrating online their e ect in the loss function L(:). In other words, we weight the loss according to the size of the classes seen at time t. Thus, the loss in Eq.( 10 ) and Eq.( 11 ) is formulated as follows:

L0(p^(yjx); p(yjx)) =

1 s(y)

L(p^(yjx); p(yjx)) ( 43 ) where s(y) represents the importance of the class. It is proportional to the number of samples from a class y. To consider the dynamic nature of the data, we use a forgetting factor instead of counting all the samples seen so far. If the class is new, the weight is equal to one. All the parameters of the estimator model excluding 1 are set to the same values as in the previous section. Because 1 controls the prior over the classes, therefore, it has impact on the class discovery performance. As shown in Eq.( 34 ), the model tends to put high probability on the emergence of new classes when 1 is high. We studied its e ect on each dataset. So, it is set to 0:5 for Pageblocks and KDD and 0:4 for Forest. We can see that the value of 1 for Forest dataset is less than the others. Such di erence can be interpreted as a result of the less unbalance classes in the Forset dataset compared to Pageblocks and KDD datasets.

Performance Analysis In these experiments, we follow the same setting as in the competitors [43, 44], where the maximun number of queries is set to 150 instances (SAL takes the budget ratio as input).

The results of the experiments are shown in Tab.4 and Tab.5. Table 4 presents the number of classes discovered by the di erent methods. Table 5 presents the average class accuracy achieved using the di erent methods. The results show that SAL provides a comparable class discovery performance compared to the competitors. SAL was able to discover all the classes for the Pageblocks and Forest datasets and 8 out of 15 classes for the KDD data (see Tab.4). Its average class accuracy is the best on the Forest data which can be explained by the fact that the data is less unbalanced. That might be a result of SAL consideration of the data density which has shown good classi cation performance in the previous section. As for Pageblocks and KDD, SAL has the second and third best results among the competitors. 4.4

Discussion

While SAL shows far better classi cation performance than all the competitors on all datasets, its class discovery performance is not the best on all of them. The reason can be rooted to SAL outliers avoidance. This latter along with the sampling bias mechanism have led to strong classi cation performance. Nonetheless, the class discovery performance is comparable to strong competitors which some of them are specialized for detecting the outliers as novel classes. Furthermore, SAL has shown better class discovery performance on the Forest data which class unbalance is less sever.

To conclude, SAL can be reliably used for novelty detection tasks, however, there might be better alternative. On the other hand, SAL is a strong method for task requiring high classi cation performance where the number of classes is unknown. In this latter, the focus is on the classi cation performance, where the error for all data samples are the same and no penalization is applied or the emergent classes are mostly normal. 5

Conclusion and future work

We proposed an active learning algorithm for data streams capable of dealing with data streams challenges: in nite length, concept drift and concept evolution. The SAL algorithm labels the samples that reduce the future expected error in a completely online scenario. It also tackles the sampling bias of active learning. Experimental results on real-world data showed the limitation of the proposed approach regarding class discovery when applying to highly unbalanced datasets. However, the main goal of the proposed algorithm is to perform classi cation with unknown number of classes. Furthermore, its class discovery performance is comparable to the state-of-the-art and sometime better when the classes are not severely unbalanced.

In future investigations, we will employ the proposed method on a real world application e.g, AR is a strong candidate. However, in such scenarios we might need to consider more challenges such as the labelling delay.

Compute Equ. (21):

{ If zt refers to a new component: p(xtjzt; z1:t 1; x1:t 1) = p(xtjzt; Ht 1)

Z = where t refer to student's t-distribution which we end up with as a result of using a conjugate prior (i.e., the Normal Inverse Wishart prior) over the normal distribution parameter . ( 44 ) ( 45 ) (46) (47) (48) (49) (50) (51) (52) (53) (54) where d is the dimension of the data. { If zt refers to an already seen component: 1 = 1 =

0 k0(v0

Compute the rst term of Equ. (33):

Given zt, yt is independent of the observations x1:t 1. Hence,

p(ytjzt; Dt 1) = p(ytjzt; yt 1) As zt selects the stick breaking component generating yt, the distribution of yt depends only on the label of the data assigned to components zt. By marginalizing the selected stick breaking component the same way as in Eq.( 19 ), we end up with the following equations: p(ytjzt; Dt 1) = 8 nzt;yt;t < 1+n0zt;t 1 / n0zt;yt;t : 1+n0z1t;t 1 / 1 yt is an existing class yt is a new class (a) Forgetting factors (b) Forgetting factors 0

Figure. 8 KDD data (budget 0.01)

References

1. G. Hulten , L. Spencer , and P. Domingos , \ Mining time-changing data streams," in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining . ACM , 2001 , pp. 97 { 106 .

2. Y. Yang , X. Wu , and X. Zhu , \ Combining proactive and reactive predictions for data streams," in Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining . ACM , 2005 , pp. 710 { 715 .

3. C. C. Aggarwal, Data streams: models and algorithms . Springer Science & Business Media , 2007 , vol. 31 .

4. M. M. Gaber , A. Zaslavsky , and S. Krishnaswamy , \ Mining data streams: a review," ACM Sigmod Record , vol. 34 , no. 2 , pp. 18 { 26 , 2005 .

5. P. Domingos and G. Hulten, \ Mining high-speed data streams," in Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining . ACM , 2000 , pp. 71 { 80 .

6. M. Sayed-Mouchaweh , Learning from Data Streams in Dynamic Environments . Springer, 2016 .

7. J. Gama , I. Zliobaite_, A. Bifet , M. Pechenizkiy , and A. Bouchachia , \ A survey on concept drift adaptation," ACM Computing Surveys (CSUR) , vol. 46 , no. 4 , p. 44 , 2014 .

8. M. Sayed-Mouchaweh , \ Handling concept drift," in Learning from Data Streams in Dynamic Environments . Springer, 2016 , pp. 33 { 59 .

9. A. Bouchachia and C. Vanaret , \ Gt2fc: an online growing interval type-2 self-learning fuzzy classi er," Fuzzy Systems, IEEE Transactions on , vol. 22 , no. 4 , pp. 999 { 1018 , 2014 .

10. C. C. Aggarwal , J . Han, J . Wang , and P. S. Yu , \ A framework for on-demand classi cation of evolving data streams," Knowledge and Data Engineering, IEEE Transactions on , vol. 18 , no. 5 , pp. 577 { 589 , 2006 .

11. A. Bouchachia, \ Incremental learning with multi-level adaptation," Neurocomputing , vol. 74 , no. 11 , pp. 1785 { 1799 , 2011 .

12. Y. Sun , K. Tang , L. L. Minku , S. Wang , and X. Yao , \ Online ensemble learning of data streams with gradually evolved classes," IEEE Transactions on Knowledge and Data Engineering , vol. 28 , no. 6 , pp. 1532 { 1545 , 2016 .

13. M. M. Masud , Q. Chen , L. Khan , C. Aggarwal , J. Gao , J. Han, and B. Thuraisingham , \ Addressing concept-evolution in concept-drifting data streams," in Data Mining (ICDM ), 2010 IEEE 10th International Conference on. IEEE , 2010 , pp. 929 { 934 .

14. M. M. Masud , J. Gao , L. Khan , J. Han, and B. Thuraisingham , \ Classi cation and novel class detection in concept-drifting data streams under time constraints," Knowledge and Data Engineering, IEEE Transactions on , vol. 23 , no. 6 , pp. 859 { 874 , 2011 .

15. T. Al-Khateeb , M. M. Masud , L. Khan , C. Aggarwal , J. Han, and B. Thuraisingham , \ Stream classi - cation with recurring and novel class detection using class-based ensemble," in Data Mining (ICDM ), 2012 IEEE 12th International Conference on. IEEE , 2012 , pp. 31 { 40 .

16. M. A. Pimentel , D. A. Clifton , L. Clifton , and L. Tarassenko, \ A review of novelty detection," Signal Processing , vol. 99 , pp. 215 { 249 , 2014 .

17. R. P. Adams and D. J. MacKay , \ Bayesian online changepoint detection," arXiv preprint arXiv:0710.3742 , 2007 .

18. S. Dasgupta, \ Two faces of active learning," Theoretical computer science , vol. 412 , no. 19 , pp. 1767 { 1781 , 2011 .

19. D. A. Cohn , Z. Ghahramani , and M. I. Jordan , \ Active learning with statistical models," Journal of arti cial intelligence research , 1996 .

20. N. Roy and A. McCallum , \ Toward optimal active learning through monte carlo estimation of error reduction," ICML, Williamstown , pp. 441 { 448 , 2001 .

21. S. Vijayanarasimhan and K. Grauman , \Multi-level active prediction of useful image annotations for recognition," in Advances in Neural Information Processing Systems , 2009 , pp. 1705 { 1712 .

22. Mohamad , Bouchachia, and Sayed-Mouchaweh, \A bi-criteria active learning algorithm for dynamic data streams," IEEE transactions on neural networks and learning systems (Minor revision, 2016 ).

23. Y. W. Teh, \ Dirichlet process," in Encyclopedia of machine learning . Springer, 2011 , pp. 280 { 287 .

24. J. Sethuraman, \ A constructive de nition of dirichlet priors," Statistica sinica , pp. 639 { 650 , 1994 .

25. P. Del Moral , A. Doucet , and A. Jasra , \ Sequential monte carlo samplers," Journal of the Royal Statistical Society: Series B (Statistical Methodology) , vol. 68 , no. 3 , pp. 411 { 436 , 2006 .

26. O. Cappe , S. J. Godsill , and E. Moulines, \ An overview of existing methods and recent advances in sequential monte carlo," Proceedings of the IEEE , vol. 95 , no. 5 , pp. 899 { 924 , 2007 .

27. C. M. Carvalho , H. F. Lopes , N. G. Polson , M. A. Taddy et al., \ Particle learning for general mixtures," Bayesian Analysis , vol. 5 , no. 4 , pp. 709 { 740 , 2010 .

28. P. Fearnhead, \ Particle lters for mixture models with an unknown number of components," Statistics and Computing , vol. 14 , no. 1 , pp. 11 { 21 , 2004 .

29. A. Doucet , N. De Freitas, and N. Gordon , \ An introduction to sequential monte carlo methods," in Sequential Monte Carlo methods in practice . Springer, 2001 , pp. 3 { 14 .

30. Y. Ulker, B. Gunsel, and A. T. Cemgil , \ Sequential monte carlo samplers for dirichlet process mixtures," in International Conference on Arti cial Intelligence and Statistics , 2010 , pp. 876 { 883 .

31. W. Chu, M. Zinkevich , L. Li , A. Thomas , and B. Tseng , \ Unbiased online active learning in data streams," in Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining . ACM , 2011 , pp. 195 { 203 .

32. A. Beygelzimer , S. Dasgupta , and J. Langford , \ Importance weighted active learning," in Proceedings of the 26th Annual International Conference on Machine Learning. ACM , 2009 , pp. 49 { 56 .

33. I. Zliobaite , A. Bifet , B. Pfahringer , and G. Holmes, \ Active learning with drifting streaming data," Neural Networks and Learning Systems , IEEE Transactions on, vol. 25 , no. 1 , pp. 27 { 39 , 2014 .

34. J. Sethuraman, \ A constructive de nition of dirichlet priors," DTIC Document , Tech. Rep. , 1991 .

35. R. M. Neal , \ Bayesian mixture modeling," in Maximum Entropy and Bayesian Methods . Springer, 1992 , pp. 197 { 211 .

36. C . E. Rasmussen, \ The in nite gaussian mixture model." in NIPS , vol. 12 , 1999 , pp. 554 { 560 .

37. T. S. Ferguson, \ A bayesian analysis of some nonparametric problems," The annals of statistics , pp. 209 { 230 , 1973 .

38. D. Blackwell and J. B. MacQueen , \ Ferguson distributions via polya urn schemes," The annals of statistics , pp. 353 { 355 , 1973 .

39. Y. W. Teh, \ Dirichlet process," in Encyclopedia of machine learning . Springer, 2010 , pp. 280 { 287 .

40. R. M. Neal , \ Markov chain sampling methods for dirichlet process mixture models," Journal of computational and graphical statistics , vol. 9 , no. 2 , pp. 249 { 265 , 2000 .

41. A. Asuncion and D. Newman , \ Uci machine learning repository ," 2007 .

42. A. Bifet , G. Holmes, R. Kirkby , and B. Pfahringer , \Moa: Massive online analysis," Journal of Machine Learning Research , vol. 11 , no. May , pp. 1601 { 1604 , 2010 .

43. C. C. Loy , T. M. Hospedales , T. Xiang , and S. Gong , \ Stream-based joint exploration-exploitation active learning," in Computer Vision and Pattern Recognition (CVPR ), 2012 IEEE Conference on. IEEE , 2012 , pp. 1560 { 1567 .

44. C. C. Loy , T. Xiang , and S. Gong , \ Stream-based active unusual event detection," in Asian Conference on Computer Vision . Springer, 2010 , pp. 161 { 175 .

45. T. M. Hospedales , S. Gong , and T. Xiang, \ Finding rare classes: Active learning with generative and discriminative models," IEEE transactions on knowledge and data engineering , vol. 25 , no. 2 , pp. 374 { 386 , 2013 .

(a) Forgetting factors (b) Forgetting factors 0 Figure. 6 Pageblocks data (budget 0 .03)