Kernel-Based Selective Ensemble Learning for Streams of Trees

1 Introduction

The advent of new technologies mainly related to web and ubiquitous services has determined the generation, at a rapid rate, of massive unbounded sequences of data elements, i.e. data streams. Data streams need to be processed quickly, using bounded memory resources, and keeping output errors as small as possible. Former approaches involved both unstructured (see, for example [Gaber et al., 2005]) and (semi-)structured data elements (e.g., [Asai et al., 2002; Kudo and Matsumoto, 2004; Bifet and Gavald`a, 2008; Bifet and Gavald`a, 2009]). These approaches, however, assumed the input distribution of data to be time-invariant. In many cases, however, this is hardly the case, since data streams tend to evolve with time, e.g. think of a stream of news or of stock market indices. This phenomenon is referred to as concept drift. By adopting the formalization presented in [Klinkenberg, 2004], if we model a stream as an infinite set of elements e1, . . . , ej, . . ., a data stream can be divided into batches, b1, b2, . . . , bn, . . ., where bi ≡ ei1 , . . . , eini . For each batch bi, data is independently distributed w.r.t. a distribution Pi(e). Depending on the amount and type of concept drift, Pi(e) will differ from Pi+1(e). In the context of data streams classification involving unstructured data elements, two main class of solutions have been proposed: instance selection and ensemble learning. Examples of the first method are Very Fast Decision Trees (VFDT) [Domingos and Hulten, 2000] and its improvements for concept drifting reaction and numerical attributes managing [Hulten et al., 2001; Gama and Pinto, 2006; Pfahringer et al., 2008; Cohen et al., 2008]. Ensemble learning employs multiple classifiers, extracting new models from scratch and deleting the outof-date ones continuously. Online approaches for bagging and boosting have been proposed in [Oza and Russell, 2001; Chu and Zaniolo, 2004; Bifet et al., 2009]. Alternative methods are described in [Street and Kim, 2001; Wang et al., 2003; Scholz and Klinkenberg, 2005; Kolter and Maloof, 2007; Grossi and Turini, 2011a], where an ensemble of weightedclassifiers is employed to cope with concept drifting. An interesting comparison between different techniques not only in terms of accuracy, but also including computational features, such as memory and time required by each system, is presented in [Bifet et al., 2009].

While the approaches cited above are more or less effective in dealing with concept drifting, all of them introduce an additional computational burden that may be the major reason for which, up to now, no approach for dealing with concept drift in streams of (semi-)structured data elements has been proposed. In fact, methods devised for this type of data are already computationally intensive and a na¨ıve application of the above approaches to them soon becomes computationally infeasible. This is a pity, since the number of applications involving (semi-)structured data is constantly growing. For example, the data exchanged between different web services are codified by XML files that take the form of tree-typed documents; the automated managing of blogs, news and emails coupled with the high interaction between users create new challenges in natural language processing; in this context, all the sentences are typically represented by trees enriched with semantic information to be processed by a machine.

In this paper, we propose a new kernel-based ensemble method, based on the architecture defined in [Grossi and Turini, 2011b] and the on-line kernel-based approach for stream of trees presented in [Aiolli et al., 2006]. We demonstrate how a well-known approach can be employed and reinvented to solve concept drifting problems in tree-structured learning. Starting from the problem of classifying trees, we employ a kernel-based approach for defining an ensemble of classifiers, that not only improves the overall accuracy of the base approach but guarantees a fast computation. In this context, a variant of the Perceptron algorithm called DAGPerceptron is employed to define a new approach for learning trees even in high-dynamical environments. The prototyped system is completely evaluated and compared in terms of accuracy and computational time with the online single DAGPerceptron. Our results demonstrated that the different models extracted from different levels of time granularity, and dynamically selected using current data distribution, provide a better result than a single flat model continuously updated.

2 DAG-Perceptron for Tree streams

The DAG-Perceptron [Aiolli et al., 2006; 2007] has been defined to deal with classification tasks involving a stream of trees. It is an efficient version of an on-line kernel-perceptron algorithm, adapted to tree-kernels, able to speed-up training of a factor above 3. From a functional point of view, this corresponds to keep in memory the set of the already seen trees for which the perceptron prediction was erroneous. More specifically, let T be a stream of example pairs (Ti, yi), where Ti are trees, and yi ∈ {-1,+1}. Then, at iteration t + 1, the scoring function of the perceptron for a new tree T is defined by

where αi ∈ {-1, 0,+1} is 0 whenever sign(Si(Ti)) = yi, and yi otherwise; K(·, ·) is a tree kernel, e.g. the SubSet Tree kernel (SST). The SST kernel counts the number of matching subset trees between two input trees. A subset tree of a tree T is a structure which is rooted in a node of T and it satisfies the constraint that each of its nodes is connected to either all its children in T or none of them. The SST kernel is defined as K(T1, T2) = ∑v1∈VT1 ∑v2∈VT2 C(v1, v2), where VT1 and VT2 are the sets of vertices of trees T1 and T2, respectively, C(v1, v2) is recursively computed according to the following rules: i) if label(v1) ̸= label(v2) then C(v1, v2) = 0; ii) if label(v1) = label(v2) and v1 is a preterminal then C(v1, v2) = 1; iii) if label(v1) = label(v2) and v1 is not a preterminal then C(v1, v2) = ∏nc(v1) j=1 (1 + C(chj [v1], chj [v2])), where nc(v1) is the number of children of v1 and chj[v] is the j-th child of vertex v. For a detailed description of the SST kernel see [Collins and Duffy, 2002]. By disregarding trees that have null weight, eq. (1) can be rewritten as

where Mt = {(Ti, yi) ∈ T : i ≤ t, Si(Ti) ̸= yi} is the model at time t of the perceptron. It is trivial to show that the cardinality of M, and consequently the memory required for its storage, grows up with the number of tree presentations. However, Mt can be efficiently maintained in a compact structure represented by a Directed Acyclic Graph (DAG) where any (sub)tree si, occurring f + t,si times in trees with yi = +1 and f - t,si times in trees with yi = -1, is represented only once and its root vsi is annotated with ft,vsi = f + t,si - f - t,si . In [Aiolli et al., 2006] it is shown that this compact representation can be exploited to efficiently compute the score for a tree by computing each C(·, ·) entry only once:St(T) = ∑

The above computation can easily be adapted to a voted version of the perceptron, thus improving the generalization ability of the system while still maintaining an efficient computation. This can be obtained by allocating for each vertex v of the DAG an additional variable, used for computing the score of the voted perceptron, which maintains the cumulated sum f voted t,v = ∑i≤t:sign(Si(Ti))̸=yi (t - i + 1) · fi,v , where we assume fi,v = 0 for all vertices v that first appear in the DAG after time i.

3 Selective Dag-Perceptron Ensemble

Capturing concept drifting is one of the main challenges in the context of mining data streams. A system should be conceived for ensuring a good trade-off between data reduction, and a powerful representation of all the evolving features.

Data reduction is needed because building a prediction model that embeds all the information concerning erroneously classified instances coming from a stream of data runs into the risk of generating a model of unbounded size. Thus, the mining process needs to select and/or compress information about misclassified instances. On the other side, a powerful representation of all the evolving features is required to cope with concept drifting, so that, as soon as a new concept appears, its characteristic features are identified and properly represented for prediction purposes. Characteristic features of out-of-date concepts still need to be preserved, since there is the possibility that those concepts will appear again in the future. One serious downside of allowing a powerful representation of all the evolving features is the need for a potentially huge amount of memory, i.e. it goes against the data reduction requirement we described above.

The approach proposed in [Grossi and Turini, 2011b] for ensuring a good trade-off between these two requirements has been to resort to a compact-layered ensemble method implementing a multi-resolution data reduction strategy. The adopted strategy can be summarized as follows. Streaming data, as long as it arrives, is partitioned in chunks, ck1, ck2, . . .. Recent chunks are used to build models belonging to the ensemble at level 1. These models, M1,M2, . . . are supposed to capture up-to-date concepts occurring in ck1, ck2, . . .. This is the way how the system is able to identify and to retain (as long as memory availability allows it) evolving features. The number of these models, let us say k, is a structural feature of the ensemble and it is decided apriori. When model Mk+1 is created, the eldest model M1 is discarded from level 1, so to make space for Mk+1. The discarded model M1 is inserted at level 2, and as soon as another model is discarded from level 1, i.e. M2, due to the insertion at level 1 of the most recently created model Mk+2, M1 is aggregated with M2 at level 2, and it will not be aggregable anymore for that level. The resulting aggregated model M1+2 is an high-order model since it covers, in a compressed form, all the instances belonging to chunks ck1 and ck2. This process is repeated till the number of models at level 2 exceeds k, in which case the outcoming model from level 2 is inserted into level 3. This is repeated until the maximum number of levels (again, defined apriori) is reached, in which case the outgoingmodel is lost. It is now clear that a model belonging at level i summarizes data coming from 2i-1 chunks, thus allowing a progressive aggregation of information along with the level index. Let us now explain how this strategy can be applied to a stream of trees.

Our approach, called EnDAG, is based on the structure explained before to build an ensemble. Such ensemble constitutes a tool for concept drift reaction, guaranteeing a fast kernel computation. The latter is one of the key aspects of this approach, since in complex structures as trees, computing kernel scores is computationally expensive.

Each tree-chunk generates a DAG-Perceptron model. DAGs are employed to maximize the number of elements for training classifiers. Generally, a model mined from a small set of elements tends to be less accurate than the one extracted from a large data set. This assumption is true in "traditional" learning contexts, but in a stream environment it is not necessarily satisfied. Due to concept drifting, large data set can include out-of-date concepts.

To clarify the role of each DAG inside our system, we distinguish two types of models; the DAGs computed directly from the stream, and the ones obtained by the aggregation of existing DAGs (high-order DAGs). The creation of a highorder DAG does not require any further access to the original data. Fig. 1 highlights the relation between the two types of models, showing an example of our structure called frame. A frame is defined by three values indicating the number of levels, the capacity of each level, and the number of DAGs that can be aggregated in a high-order DAG. For each tree-chunk of size k, Cjk = {T j 1 , ..., T j k }, a DAG-Perceptron (Dj,k) is computed. Successively, when the stream evolves the models are further aggregated in high-order DAGs, e.g. D2 j,2k or D3 j,4k . For each level, only the highlighted models are actually stored in the structure. The higher is the level, the larger is the data chunk considered by the high-order models. Moreover, Fig. 1 shows the logical na¨ıve management of the frame structure. All the DAGs computed directly from the stream are inserted at level 1 and represent the basic element of the structure. Since each level has a finite capacity, when a level is full the out-coming DAG is not deleted but it is inserted (or aggregated) into the successive level. DAGs coming out from the last level are simply deleted. From a logical perspective, this structure can be viewed as a set of sliding windows representing different complementary portions of the stream, with the properties that only the basic models access original data.

This logical view cannot be implemented directly. Managing all DAGs separately, as show in Fig. 1, tends to repeat the same structures in different DAGs with a waste of resources, in terms of time and memory. For this reason, the ensemble is efficiently represented by a single DAG (EnDAG) where a frame structure is associated with each node, thus avoiding to replicate the same structure several times and enabling a fast score computation for all needed models. The EnDAG is created and subsequently updated by an operation that adds a DAG to it:

As defined in eq. (2), the insertion of DAGj in EnDAG requires two distinct operations, namely shifting and adding.

Shitfing: Algorithm 1 defines the ------⇀ EnDAG operation. Since each level has a finite capacity, before adding a new element to the ensemble, we have to set a slot as free for each vertex of EnDAG. Given a vertex v, the value of the last slot of level i is forwarded to the first slot of level i+1 and all the remaining values of level i are shifted to the right. 1 The forwarded value is summed to the first slot of level i + 1 (aggregation) if a value not already aggregated is present, otherwise it is inserted into the first slot of level i + 1 after that the same procedure described above has be recursively applied to level i + 1. The recursive invocation is repeated until a value is aggregated or the last level of the frame is reached.

Adding: when a slot is set as free, the operation of adding a new DAG in the ensemble can be performed. We recall that our ensemble is represented by a single DAG, where for each vertex we manage a frame structure. The adding operation involves two different situations:

1. ∀vi ∈ DAGj such that ∃vk ∈ EnDAG for which tree(vi) ≡ tree(vk), then vk.frame[1, 1] ← fvi . The function tree(v) returns the tree rooted in v.
2. ∀vi ∈ DAGj such that ̸∃vk ∈ EnDAG for which tree(vi) ≡ tree(vk), then: i) vertex vi is added 2 to

1 This is actually implemented by a circular array.

2 Vertices of DAGj are examined following an inverted topolog-

Algorithm 1 The ------⇀ EnDAG algorithm 1: for all v ∈ EnDAG do 2: insert(v, 2, v.frame[1, limit]); 3: for j = limit -1 to 1 do 4: v.frame[1, j + 1] ← v.frame[1, j]; 5: end for 6: v.frame[1, 1] ← null; 7: end for insert(v, lev, val) if v.aggregable[lev] = 1 then v.f rame[lev, 1] ← v.frame[lev, 1] + val; v.aggregable[lev] ← 0; else insert(v, lev + 1, v.frame[lev, limit]); for j = limit - 1 to 1 do v.frame[lev, j + 1] ← v.frame[lev, j]; end for v.f rame[lev, 1] ← val; v.aggregable[lev] ← 1; end if

EnDAG; ii) vk.frame[1, 1] ← fvi and all the remaining slots of vk.frame[, ] get the null value.

Fig. 2 shows, for a given vertex v ∈ EnDAG, an example of evolution of the content of v.frame (of size 2×2) following the insertion into the ensemble of DAGs generated after reading some tree-chunks. For each insertion, next to the ':' character, both the value associated with the input vertex vDi (i = 2, . . . , 5) and the current content of v.frame, as well as the result of the ⊕ operation, are shown.

Fig. 3 provides a complete picture about the insertion of a new DAG into EnDAG. For all the vertices already available in the ensemble, we only update the frame structure. Otherwise, as in the case of vertex with label q, a new vertex is added to EnDAG with a frame that contains only a value (the fv value) in first position.

This construction, where all the common substructures are not duplicated between DAGs, enables an efficient high-order DAGs creation and a fast score computation. In fact, given a tree, we can compute the score associated with every DAG in the structure by visiting EnDAG only once, and simply considering the values different from null inside each frame.

It is worth to notice that the computation of high-order DAGs does not imply any loss of information as long as any high-order DAG is lost:

ical order. This guarantees that when a vertex v must be inserted into EnDAG, all its children already belong to EnDAG.

where EnDAG = D1⊕· · ·⊕Dm, and EnDAG uses a vertex frame of size r ×c such that (c ∑ri=1 2i-1 ) = c(2r -1) ≥ m. Proof: the proof of this theorem is derived from the one presented in [Aiolli et al., 2006] and not reported here due to space limitations.

Finally, it is worth observing that a data stream involves an infinite set of elements, that cannot be stored completely even with this structure. In fact, the actual size of the frame is decided beforehand on the basis of the available computational resources.

3.1 Ensemble management

The actual ensemble management is a four-phase approach. i. For each tree-chunk Ci, a triple (Di,wi,bi) representing a model, its weight and a boolean value bi is extracted from Ci (see below for more info about wi and bi). ii. Subsequently, Di ⊕ EnDAG is computed; notice that each entry of any EnDAG vertex's frame will correspond to a model. iii. Since data distribution can change through time, at time t the DAGs currently in the structure (i.e., the corresponding entries into the frames associated with vertices of EnDAG) are re-weighed as follows: ∀i, wi = accuracy(Di, C0.25 t ) where accuracy(Di, C0.25 t ) is the accuracy of the model Di computed over 25% of trees belonging to tree-chunk Ct; it should be noticed that wi is independent fromwhich specific v ∈ EnDAG is considered. iv. A set of active DAGs (i.e., frame entries) is selected, setting the boolean value bi associated with a Di as true. The set of active models is selected based on the value of an activation threshold θ. All the classifiers that differ at most θ from the best classifier with the highest weight are enabled. This behavior allows the ensemble to dynamically select those models that best match the concepts currently represented in the stream. However, currently disabled models are not deleted from the ensemble since they can be enabled in the future in case associated matching concepts come back as relevant.

4 Comparative Experimental Evaluation

We compared 3 applications of our approach with the incremental single flat model (labelled Dag) proposed in [Aiolli et al., 2007; 2006]. We considered a weighed-ensemble approach, labeled WE, where all the models are active and the final score is computed, even considering the weight associated with each DAG. In the remaining two approaches, the selective behavior is enabled. The final class is computed considering the weighed score or a majority class of the active DAGs only. These two approaches are labeled SE and SEM respectively. In all the cases, even the voted approaches are tested as well.

The aim of the faced task is to predict, for each tree, the average vertex out-degree. All the experiments involve the use of semi-real data, where it is possible to control concept drift, and test how the latter influences the final results. Original data includes two sets of trees computed as Part-of-Speech of sentences taken from PropBank dataset. Specifically, the input trees are real, taken from the POS tagging, while the task is artificially created (by randomly changing the threshold through time) for studying the behavior of the systems in the presence of different drifting phenomena. Table 1 reports the statistics about the datasets.

This approach is motivated by the fact that, before assessing our approach with a real-world task, we must demonstrate the reliably of the approach on controlled tasks. Due to space limitation, only results on "hard" concept drifts are presented. It is worth observing that in case of small concept fluctuations, an ensemble of classifiers is by construction (due to the average operator) robust.

Since our aim is to analyze the reaction of the systems to concept drifting, three families of tests were considered. All the systems were stressed by considering different situations, where concept drift may occur. Given a set of trees, a drift is simulated by classifying the trees based on their average out-degree value. In particular, a threshold h is randomly changed through time to assign the class value to a tree. If a tree T has an average vertex out-degree higher than h, T is classified as +1, otherwise t class is -1. Figure 4 highlights the concept drifting phenomenon inside a specific train data of DS-0 and DS-2. With reference to Table 2, DS-0 involves the use of exactly 1000 trees taken from Seta, namely 500 for the test set and 500 for the train set. Every 500 elements a drift may occur. This situation represents a pure concept drifting phenomenon, since from a drift to the next one the same set of trees changes its class value. DS-1 shares the same philosophy of DS-0, but a change may occur every 1000 trees and the same tree can be randomly repeated many times both in the train and the test set. DS-1 proposes a real context, where some features appear in multiple and unpredictable forms, while others are more unlikely. Finally, DS-2 selects a subgroup from Setb, and estimates the reliability of each system by varying the ratio between a drift and the next one. The described datasets are freely available at http://www.math.unipd.it/˜sperduti/TreeCD.

All the systems were implemented in Java 1.6 and the experiments were run on a PC with Intel E8200 DualCore with 4Gb of RAM, employing Windows Vista as OS.

Our experiments consider frames of size 8 × 4. This frame size is large enough to consider DAGs representing big portions of data at higher-levels. The dimension of the frame is selected to avoid loss of information, so to have a fair comparison of our approach versus the single flat DAG model, which does not lose information.

The model activation threshold θ is set to 0.1 as the default value used in [Grossi and Turini, 2011b]. For each test, a collection of 10 training sets (and corresponding test sets of equal size as the training sets) are randomly generated with respect to the features outlined in Table 2. Every system is run, and the accuracy is computed by using a train-and-test approach. After a learning batch of 200 trees, the reliability is tested with a test set of 200 unseen elements. Finally, the average accuracy and 95% of interval confidence is reported.

Table 3 presents the overall accuracy reported by the systems. As a general observation, we can state that our SE and Dag approaches provide an average accuracy higher than the other ones even considering the confidence value. We additionally performed a test of significance between these two systems, highlighting when the difference between SE and Dag is statistically relevant. Moreover, Table 3 shows how the selective behavior is important to guarantee a powerful tool for reacting to concept drift. In this situation, WE approach does not guarantee a reliable performance in the presence of multiple data changes. DS-2 data set shows how the accuracy of SE and Dag tends to be the same, increasing the period between two changes. The use of the voted version does not provide any improvement in the accuracy of our approaches. This is due to the nature of the voted approach that implicitly simulates an ensemble method.

The run-time behavior of the systems is proposed in Table 4. The latter highlights how our SE (and SEM) guarantees a performance that outperforms all the others. This result is provided by the structure of EnDAG that manages all the DAGs in the ensemble in a unique structure avoiding the repetition of substructures. Tests not reported here for lack of space showed that the described EnDAG implementation, on the average, improves speed of a factor 4 on the na¨ıve approach that maintains all the DAGs separated.

These results show that, in the presence of concept drifting, in most cases the accuracy of our system is increased with respect to a single model. Moreover, if we consider SE and Dag approaches, they demonstrate that even if in some cases the accuracy of the two systems is similar, the run time values guarantee that our SE approach is more suitable to be employed in a streaming environment.

As a final test, we studied the behavior of our systems (excluding voting) on a large dataset of 1 million of trees generated from Setc in Table 1. We tested only our SE with Dag, since the two systems are the most representative ones, given the past tests. In particular, if we consider the behavior proposed by SE, i.e. an average accuracy of 95.72% and runtime of 211976.6 seconds, the results show that Dag is much slower than SE, being able to process only 42.2% of the input trees in the same amount of time needed by SE to complete its task.

5 Conclusions

Kernel methods provide a powerful tool for modeling structured objects in learning algorithms. Unfortunately, they require a high computational complexity to be used in streaming environments.

This work is the first that demonstrates how kernel methods can be employed to define an ensemble approach able to quickly react to concept drifting and guarantees an efficient kernel computation. Our experimental assessment demonstrates that for high dynamical data streams our system provides an high level of reliability both in terms of accuracy and time performance.

Acknowledgments

Valerio Grossi was supported by the FSE fellowship Id: 2105/1/13/2215/2009.