--- title: "Learning from Ontology Streams with Semantic Concept Drift" authors: - "Jiaoyan Chen" - "Freddy Lecue" - "Jeff Z. Pan" - "Huajun Chen" doi: "10.24963/ijcai.2017/133" url: "https://ijcai.org/proceedings/2017/133" pdf: "https://ijcai.org/proceedings/2017/0133.pdf" venue: "Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence" year: 2017 pages: "957-963" track: "Main track" keywords: - "Machine Learning: Time-series/Data Streams" - "Knowledge Representation, Reasoning, and Logic: Description Logics and Ontologies" --- # Learning from Ontology Streams with Semantic Concept Drift Jiaoyan Chen, Freddy Lecue, Jeff Z. Pan, Huajun Chen *Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence*, pages 957-963. DOI: [10.24963/ijcai.2017/133](https://doi.org/10.24963/ijcai.2017/133) ## Abstract Data stream learning has been largely studied for extracting knowledge structures from continuous and rapid data records. In the semantic Web, data is interpreted in ontologies and its ordered sequence is represented as an ontology stream. Our work exploits the semantics of such streams to tackle the problem of concept drift i.e., unexpected changes in data distribution, causing most of models to be less accurate as time passes. To this end we revisited (i) semantic inference in the context of supervised stream learning, and (ii) models with semantic embeddings. The experiments show accurate prediction with data from Dublin and Beijing. ## Full text ## 1 Introduction and RelatedWork Stream learning, or the problem of extracting and predicting knowledge from temporal evolution of data, has been largely studied. Most of techniques in Database e.g., [Cheung et al., 1996], adapting Apriori [Agrawal et al., 1996] for streams, focus on syntactic representation of data to identify frequent associations and exploit them for prediction. [Lee et al., 2003] improved its scalability by partitioning all streams using a sliding-window filtering. Approaches in Machine Learning e.g., [Gama and Kosina, 2011] focus on learning decision rules for classifying data from streams in real-time. Although highly scalable, most approaches have been shown to be non robust to concept drift i.e., unexpected changes in data distribution [Coble and Cook, 2000]. Indeed their models, built on old data and then inconsistent with new data, are less accurate as time passes. Towards this challenge [Chu et al., 2011] applied online active learning using customized properties of weighing, Alternatively [Gao et al., 2007] prioritized recent data during the elaboration of the learning model through regular updates, assuming temporally adjacent data is the most representative information for prediction. [Bifet et al., 2015] went further by considering dynamic sliding windows. More details are presented in [Gama et al., 2014]. Although such approaches manage gradual changes, they fail in maintaining high accuracy for sudden, abrupt changes. This is mainly due to inconsistent evolution of knowledge and lack of metrics to understand the semantics of its changes and concept drifts. ∗Corresponding author. Towards this issue adapt the problem in semantic Web settings. Such streams, represented as ontology streams [Huang and Stuckenschmidt, 2005; Ren and Pan, 2011], are evolutive versions of ontologies where OWL (Web Ontology Language), which is underpinned by Description Logics (DL) [Baader et al., 2003], is used as a rich description language. From knowledge materialization [Beck et al., 2016; Gal´arraga et al., 2013; Ren et al., 2016], to predictive reasoning [Lecue and Pan., 2013; L´ecu´e, 2015], all are inferences where dynamics, semantics of data are exploited for deriving a priori knowledge from pre-established (certain) statements. However concept drift is not handled, which limits accuracy of prediction for highly changing streams. Our approach, exploiting the semantics of data streams, tackles the problem of learning and prediction with concept drifts. Given some continuous knowledge, how to manage its changes and their inconsistent evolution to ensure accurate prediction? Semantic reasoning and machine learning have been combined by revisiting features embeddings as semantic embeddings i.e., vectors capturing consistency and knowledge entailment in ontology streams. Such embeddings are then exploited in a context of supervised stream learning to learn models, which are robust to concept drifts i.e., sudden and inconsistent prediction changes. Our approach has been shown to be adaptable and flexible to basic learning techniques. The experiments have shown accurate prediction with live stream data from Dublin in Ireland and Beijing in China. The next section reviews the adopted logic and ontology stream learning problem. In Section 3 we study concept drift. Section 4 presents semantic embeddings and prediction. ## 2 Background The semantics of data is represented using an ontology. We focus on Description Logic (DL) to define ontologies since it offers reasoning support for most of its expressive families and compatibility to W3C standards e.g., OWL 2. Our work is illustrated using DL EL++ [Baader et al., 2005], which supports polynomial time reasoning. We review (i) DL basics of EL++, (ii) ontology stream, (iii) stream learning problem. ## 2.1 Description Logics EL++ A signature Σ, noted (NC , NR, NI ) consists of 3 disjoint sets of (i) atomic concepts NC, (ii) atomic roles NR, and (iii) individuals NI . Given a signature, the top concept ⊤, the bottom concept ⊥, an atomic concept A, an individual a, an atomic role expression r, EL++ concept expressions C and D in C can be composed with the following constructs: A DL ontology O .= 〈T ,A〉 is composed of TBox T , ABox A. A TBox is a set of concept, role axioms. EL++ supports General Concept Inclusion axioms (GCIs e.g. C ⊑ D), Role Inclusion axioms (RIs e.g., r ⊑ s ). An ABox is a set of concept assertion axioms, e.g., C(a), role assertion axioms, e.g., R(a, b), individual in/equality axioms e.g., a ̸= b, a = b. ## Example 1. (TBox and ABox Concept Assertion Axioms) Figure 1 presents (i) a TBox T where DisruptedRoad (2) denotes the concept of "roads which are adjacent to an event causing high disruption", (ii) concept assertions (11-12) with the individual r0 having roads r1 and r2 as adjunct roads. ``` SocialEvent ⊓ ∃type.Poetry ⊑ Event ⊓ ∃disruption.Low (1) Road ⊓ ∃adj.(∃occur.∃disruption.High) ⊑DisruptedRoad (2) Road ⊓ ∃adj.(∃occur.∃disruption.Low) ⊑ ClearedRoad (3) BusRoad ⊓ ∃travel.Long ⊑ DisruptedRoad (4) BusRoad ⊓ ∃travel.OK ⊑ ClearedRoad (5) Road⊓∃with.Bus ⊑ BusRoad (6) Road(r0) (7) Road(r1) (8) Road(r2) (9) Bus(b0) (10) adj(r0, r1) (11) adj(r0, r2) (12) Long ⊓OK ⊑ ⊥ (13) ``` Figure 1: O .= 〈T ,A〉. Sample of TBox T and ABox A. All completion rules, which are used to classify EL++ TBox T and entail subsumption, are described in [Baader et al., 2005]. Reasoning with such rules is PTime-Complete. ## 2.2 Ontology Stream We represent knowledge evolution by a dynamic, evolutive version of ontologies [Huang and Stuckenschmidt, 2005]. Data (ABox), its inferred statements (entailments) are evolving over time while its schema (TBox) remains unchanged. ## Definition 1. (DL L Ontology Stream) A DL L ontology stream P nm from point of time m to point of time n is a sequence of (sets of) Abox axioms (P nm(m),P nm(m+1), · · · ,P nm(n)) with respect to a static TBox T in a DL L where m, n ∈ N and m< n. P nm(i) is a snapshot of an ontology stream P nm at time i, referring to ABox axioms. Thus a transition from P nm(i) to P nm(i+1) is seen as an ABox update. We denote by P nm[i, j] i.e., ⋃jk=i P nm(k) a windowed stream of P nm between time i and j with i ≤ j. Any window [i, j] has a fixed length. 1length windows are denoted by (i). We consider streams P n 0 with [α] .= [i, j], [β] .= [k, l] as windows in [0, n] and i < k. ## Example 2. (DL EL++ Ontology Stream) Figure 2 illustrates EL++ streams P n 0 , Qn0 , Rn0 , related to events, travel time, buses, through snapshots at time i ∈ {0, 1, 2, 3} (i.e., a view on [0, 3]). In our example n is any integer greater than 5. Their dynamic knowledge is captured by evolutive ABox axioms e.g., (20) captures e1 as "a social poetry event occurring in r2" at time 1 of P n 0 . By applying completion rules on static knowledge T and ontology streams P n 0 , snapshot-specific axioms are inferred. The evolution of a stream is captured along its changes i.e., new, obsolete and invariant ABox entailments from one windowed stream to another one in Definition 2 [L´ecu´e, 2015]. Definition 2. (ABox Entailment-based StreamChanges) Let S n 0 be a stream; [α], [β] be windows in [0, n]; T be axioms, G its ABox entailments. The changes occurring from S n 0 [α] to S n 0 [β], denoted by S n 0 [β]∇S n 0 [α], are ABox entailments in G being new (14), obsolete (15), invariant (16). (14) reflects knowledge we gain by sliding window from [α] to [β] while (15) and (16) denote respectively lost and stable knowledge. All duplicates are supposed removed. Definition 2 provides basics, via ABox entailments [Ren et al., 2011], for understanding how knowledge evolves over time. Figure 2: Ontology Streams P n 0 (i), Qn0 (i), Rn0 (i)i∈{0,1,2,3}. | P n 0 (0) : (Incident ⊓ ∃impact.Limited)(e3), occur(r1, e3) | (17) | |---------------------------------------------------------------|--------| | Qn0 (0) : (Road ⊓ ∃travel.OK)(r1) | (18) | | Rn0 (0) : with(r1, b0) | (19) | | P n 0 (1) : (SocialEvent ⊓ ∃type.Poetry)(e1), occur(r2, e1) | (20) | | Qn0 (1) : (Road ⊓ ∃travel.OK)(r2) | (21) | | Rn0 (1) : with(r2, b0) | (22) | | P n 0 (2) : (Event ⊓ ∃disruption.High)(e2), occur(r2, e2) | (23) | | Qn0 (2) : (Road ⊓ ∃travel.Long)(r2) | (24) | | Rn0 (2) : with(r2, b0) | (25) | | P n 0 (3) : (Event ⊓ ∃disruption.High)(e2), occur(r2, e2) | (26) | | Qn0 (3) : (Road ⊓ ∃travel.Long)(r2) | (27) | | Rn0 (3) : with(r2, b0) | (28) | ## Example 3. (ABox Entailment-based StreamChanges) Table 1 illustrates changes occurring from (Q ∪ R)n0 [0, 1] to (Q ∪ R)n0 [2, 3] through ABox entailements. For instance "r2 as a disrupted road window [2, 3] of (Q ∪ R)n0 is new with respect to knowledge in [0, 1]. It is entailed using DL completion rules on (4), (6), (9), (24), (25), (27) and (28). Table 1: ABox Entailment-based Stream Changes. | | | | | |-------------------|-------------------------------|-------------------------------|-------------------------------| | Windowed Stream | (Q∪R)n0 [2, 3]∇(Q∪R)n0 [0, 1] | (Q∪R)n0 [2, 3]∇(Q∪R)n0 [0, 1] | (Q∪R)n0 [2, 3]∇(Q∪R)n0 [0, 1] | | Changes | obsolete | invariant | new | | with(r2, b0) | | ✓ | | | ClearedRoad(r2) | ✓ | | | | DisruptedRoad(r2) | | | ✓ | ## 2.3 Ontology StreamLearning Problem Definition 3 revisits classic supervised learning [Domingos and Hulten, 2000] for ontology stream as the problem of predicting knowledge (through entailment) in a future snapshot. ## Definition 3. (Ontology Stream Learning Problem) Let S n 0 be a stream; T , A be respectively TBox, ABox; g ∈ G be an ABox entailment. An Ontology Stream Learning Problem, noted OSLP〈S n 0 , k, T ,A, g〉, is the problem of estimating whether g can be entailed from T and A at time k ∈ (0, n] of stream S n 0 , given knowledge at time t < k of S n 0 . This estimation is denoted as p|T ∪A(S n 0 (k) |= g) with values in [0, 1] and k ≥ 1. g is a class assertion entailment in the form of G(a), with G a concept expression and a an individual. The estimation, adapted from [Gao et al., ], can be elaborated using knowledge from previous snapshots of S k 0 : Estimation p|T ∪A(S k-1 0 |= g) is the proportion of snapshots in S k-1 0 entailing g. The conditional probability of a in S k-1 0 (noted a ∈ S k-1 0 ) given S k-1 0 entailing g, or G(a), is 1. ## Example 4. (Ontology Stream Learning Problem) The problem of estimating whether class assertion g, defined as DisruptedRoad(r2), can be entailed from T and A at time 4 of (Q∪R)n0 is defined as OSLP〈(Q∪R)n0 , 4, T , A, g〉. The estimation can be retrieved using (29) hence p|T ∪A((Q∪ R)n0 (4) |=DisruptedRoad(r2)) .= 2/3. ## 3 Concept Drift in An Ontology Stream We introduce semantic concept drift, as a basis for qualifying, quantifying sudden and abrupt changes in an ontology stream. ## 3.1 Semantic Concept Drift Definition 7 revisits concept drift [Gao et al., 2007] for ontology streams as prediction changes (Definition 4) in ABox entailment, which are sudden and abrupt (Definitions 5, 6). ## Definition 4. (Prediction Change) Let S n 0 be a stream; T , A and G be TBox, Abox and its entailments. A prediction change in S n 0 is ocuring between time i and j in [0, n] with respect to T , A and its entailments iff: where ε ∈ (0, 1] is a variable bounding the difference of estimation, ‖v‖ refers to the absolute value of v, and j > i ABox entailment g is called an evidence entailment of the prediction change. We denote by C|T ∪A(S n 0 , i, j, ε), the set of all evidence entailments of the prediction change with an ε difference between time i and j of ontology stream S n 0 . ## Example 5. (Prediction Change) g .= DisruptedRoad(r2) can be entailed from T and A at time 2 of (Q ∪ R)n0 with a zero probability following (29). Therefore a prediction change between times 2 and 4 (cf. Example 4) is captured with g ∈ C|T ∪A((Q ∪ R)n0 , 2, 4, 1/3). ## Definition 5. (α-Sudden Prediction Change) A prediction change at point of time i in stream S n 0 , satisfying (30), is defined as α-sudden, with α ∈ (0, n-i] iff j = i + α. ## Definition 6. (Abrupt Prediction Change) A prediction change, satisfying (30), is abrupt iff ∃g′ ∈ G s.t. where ⋃max{i,j} k=0 S n 0 (k) captures all axioms from any snapshot S n 0 (k) of stream S n 0 with k ∈ [0,max{i, j}]. Suddenness characterises the proximity of prediction changes in streams i.e., the lower α the closer the changes. Abruptness captures disruptive changes from a semantic perspective i.e., conflicting knowledge among snapshots S n 0 (i), S n 0 (j) with respect to background knowledge T ∪A. ## Definition 7. (Semantic Concept Drift) A semantic concept drift in S n 0 , is defined as a 1-sudden and abrupt prediction change. Evaluating if a concept drift occurs for a snapshot update is in worst case polynomial time with respect to acyclic TBoxes and S n 0 in EL++ since subsumption and satisfiability in (30), (31) can be checked in polynomial time [Baader et al., 2005]. ## Example 6. (Semantic Concept Drift) Two prediction changes from time i = 2 to 3 and 3 to 4 (cf. Table 2) have occurred for g .=DisruptedRoad(r2) in (Q∪ R)n0 . They are semantic concept drifts as they are 1-sudden and abrupt with g′ .= ClearedRoad(r2) in (Q∪R)n0 (1). | Prediction - Past Points of Time | Prediction - Time i | Prediction - p|T ∪A ((Q∪R)n0 (i) |= g) | Prediction Change - g ∈ C|T ∪A ((Q∪R)n0 , i, i+1, 1/3) | Prediction Change - Abrupt- ness | |------------------------------------|-----------------------|----------------------------------------------------|---------------------------------------------------------------|------------------------------------| | {0} | 1 | 0 | 7 | 7 | | {0, 1} | 2 | 0 | ✓ | ✓ | | {0, 1, 2} | 3 | 1/2 | ✓ | ✓ | | {0, 1, 2, 3} | 4 | 2/3 | N/A | N/A | Table 2:Prediction Changes in (Q∪R)n0 (g .=Disrupted(r2)). ## 3.2 Significance of Concept Drift Significance of semantic concept drift (Definition 8) is an indicator on its severity. It captures the homogeneity of the concept drift across ABox entailments as the proportion of ABox entailments from S n 0 (i) and S n 0 (i+1) causing semantic concept drift. The values of significance range in [0, 1]. ## Definition 8. (Semantic Concept Drift Significance) The significance of a semantic concept drift, defined between points of time i ∈ (0, n) and i+1 of S n 0 with ε, T , A, G as difference, TBox, ABox, and entailments, is σ|T ∪A(S n 0 , i, ε): where the expression in between | refers to its cardinality. Evaluating (32) is in worst case polynomial time cf. complexity of Definition 7. ## Example 7. (Semantic Concept Drift Significance) By applying (32) on concept drifts of Table 2 we derive that σ|T ∪A((Q∪R)n0 , 2, 1/3) is 4/7 while σ|T ∪A((Q∪R)n0 , 3, 1/3) is 0, hence a more significant drift between times 2, 3 than 3, 4. In other words conflicting facts g .= DisruptedRoad(r2) and g′ .= ClearedRoad(r2) w.r.t. T and A have the most significant impact on prediction changes at times 2 and 3. ## Lemma 1. (Semantic Concept Drift Evolution) A semantic concept drift in any ontology stream S n 0 is more significant at time i > 0 than at time i+1 if |G [0,i],[0,i+1] new | = 0. Proof. (Sketch) Since |G [0,i],[0,i+1] new | = 0, S n 0 (i) and S n 0 (i+1) are similar w.r.t |=T ∪A. Thus, the set of all entailments, predicted at i+1 and i+2 from (29), are similar but with different prediction values (30) ∀ε ≥ 0. So σ|T ∪A(S n 0 , i, ε) and σ|T ∪A(S n 0 , i+1, ε) in (32) have same denominators while C|T ∪A(S n 0 , i+1, i+2, ε) ⊆ C|T ∪A(S n 0 , i, i+1, ε) hence σ|T ∪A(S n 0 , i+1, ε) ≤ σ|T ∪A(S n 0 , i, ε). Algorithm 1 [A1] retrieves significant concept drifts in S n 0 with minimal significance σmin. [A1] iterates on all snapshots updates except those with no new ABox entailment (line 5 - lemma 1) for minimizing satisfiability and subsumption checking. Semantic concept drifts, as 1-sudden and abrupt prediction changes, are retrieved (line 7). [A1] completes the process (line 9) by filtering drifts by significance σmin. ## Algorithm 1: [A1]SignificantDrift〈O, S n 0 , ε, σmin〉 ``` 1 Input: (i) Axioms O : 〈T ,A, G〉, (ii) Ontology stream S n 0 , (iii) Lower limit ε ∈ (0, 1] of prediction difference, (iv) Minimum threshold of drift significance σmin. 2 Result: S: Significant concept drifts in S n 0 w.r.t. σmin. 3 begin 4 S ← ∅; % Init. of the Significant concept drifts set. 5 foreach i ∈ (0, n] of S n 0 such that |G[0,i],[0,i+1] new | ̸= 0 do 6 % Selection of 1-sudden, abrupt prediction changes. 7 if ∃g, g′ ∈ G such that: ‖p|T ∪A(S n 0 (i) |= g)- p|T ∪A(S n 0 (i+1) |= g)‖ ≥ ε ∧ T ∪A∪S n 0 (i) ∪ S n 0 (i+1) ∪ g ∪ g′ |= ⊥ then 8 % Semantic concept drift with min. significance. 9 if σ|T ∪A(S n 0 , i, ε) ≥ σmin then 10 S ← S ∪ {(i, i+1)} % Add snapshot update. 11 return S; ``` Computing a solution with [A1] given a polynomial input n, number of axioms, entailments in O and S n 0 is in worst case polynomial time, due to the complexity of evaluating a semantic drift cf. complexity of Definition 7. However computing significant α-sudden, abrupt prediction changes following [A1] is in worst case NP w.r.t. the number snapshots. ## 4 Ontology StreamLearning We tackle the ontology stream learning problem by (i) computing semantic embeddings, as mathematical objects exploiting the properties of concept drifts, (ii) applying all embeddings in model-based learning approaches (Algorithm 2). ## 4.1 Semantic Embeddings The semantics of streams exposes two levels of knowledge which are crucial for learning with concept drift: (i) (in)consistency evolution of knowledge, and (ii) entailment of the forecasting target from stream assertions and axioms. They are semantic embeddings, captured as: consistency vectors (Definition 9) and entailment vector (Definition 10). ## Definition 9. (Consistency Vector) A consistency vector of snapshot S n 0 (i) in S n 0 , denoted by ci, is defined ∀j ∈ [0, n] by cij if i < j; cji otherwise such that: where the expressions in between | refer to its cardinality i.e., the number of new (14), obsolete (15), invariant (16) ABox entailments from S n 0 (i) to S n 0 (j). cij = cji ∀i, j ∈ [0, n]. A consistent vector, with values in [-1, 1]n+1 , encodes (i) (in-)consistency with (negative) positive values, and (ii) similarity of knowledge among S n 0 (i) and any other snapshot S n 0 (j)j∈[0,n] of streamS n 0 w.r.t axioms T andA. The number of invariant entailments has a positive influence on (33). On contrary, the number of new and obsolete ABox entailments, capturing some differentiators in knowledge evolution, has a negative impact. When an inconsistency occurs, the value 1 is subtracted instead of considering its additive inverse. This ensures that the invariant factor has always a positive impact. Evaluating (33) is in worst case polynomial time with respect to T and S n 0 in EL++. Indeed its evaluation requires (i) ABox entailment, and (ii) basic set theory operations from Definition 2, both in polynomial time [Baader et al., 2005]. ## Example 8. (Consistency Vector) Consistency vector c3 i.e., (c03, c13, c23, c33) of (Q∪R)n0 (3) is (0, - 0.8, 1, 1). Knowledge at time 3 is consistent / inconsistent / similar with knowledge at times 0 / 1 / 2 and 3. An entailment vector (Definition 10) is adapting the concept of feature vector [Bishop, 2006] in Machine Learning to represent the (non-)presence of all ABox entailments (using |= w.r.t. T , A) in a given snapshot. Each dimension captures whether a particular ABox entailment is in (1) or not (0). ## Definition 10. (Entailment Vector) Let G .= {g1, . . . , gm} be all distinct ABox entailments in S n 0 . An entailment vector of a snapshot S n 0 (i) in S n 0 , denoted by ei, is a vector of dimension m such that ∀j ∈ [0,m] ## Remark 1. (Feature vs. Entailment Vector) Feature vectors are bounded to only raw data while entailment vectors, with much larger dimensions, embed both data and its inferred assertions from T and DL completion rules. The latter ensures a larger and more contextual coverage. ## 4.2 Semantic Prediction Algorithm 2 [A2] aims at learning a model (line 12) over N ≤ n+1 snapshots of S n 0 , noted S n 0 |κ, for prediction at n+1. κ refers to the proportion of snapshots with concept drift used for modelling. S n 0 |κ is selected to capture (i) S n 0 (n) i.e., the closest (temporally) to S n 0 (n+1) (line 4), (ii) knowledge in the most (lines 8-9) significant concept drifts (Definition 8 - line 5), (iii) any other snapshots to meet N (line 11). The model is trained, following Stochastic Gradient Descent method [Zhang, 2004], using samples of the form {(ei, gi) | i ∈ {1, . . . ,N}} where ei is the entailment vector for S n 0 (i) and v(gi) is the target variable in [0, 1], capturing the estimation of gi to be entailed. The model is represented by a linear scoring function f(ei) = aT ei + b with model parameters a ∈ RN and b ∈ R. The goal of learning is to minimize the following objective function Oj : where L represents the loss function (e.g., hinge and log). R and α control the variance of the model in case of over fitting. R is a regularization term and α > 0 is a non-negative hyperparameter. Each sample (ei, gi) in (35) is weighted by ωij in (36) (resp. (37)) for filtering out consistent (resp. inconsistent) historical snapshots w.r.t. (33). ![Image](https://ijcai.org/proceedings/2017/fulltext/133/image_000000_3d87cd2b0cd240db5b0fda71d4615d0d17a701a70fb781a064ee418f70d34c00.png) [A1-2] parameterized with low ε, σmin, high κ and (36) as weight (line 12 (i)) favours models with significant concept drifts for prediction, which supports diversity and prediction changes in the model. Parameterized with high ε, σmin, low κ and (37) as weight, it will capture more consistent models. The linear scoring function f in (35) has the following advantages compared to more complex structures such as artificial neural network: (i) better handling over-fitting with reduced sample size - due to filtering of snapshots not involved in significant concept drifts (lines 8-9 in [A2]), (ii) ensuring efficient, scalable learning and prediction for online contexts. ## 5 Experimental Results We report accuracy by (i) studying the impact of [A2] and semantic embeddings on concept drift for Dublin-Ireland, Beijing-China applications, and (ii) comparing its results with state-of-the-art approaches. The system is tested on: 16 Intel(R) Xeon(R) CPU E5-2680, 2.80GHz cores, 32GB RAM. - Beijing Air Quality (BAQ) Context: BAQ index, ranging from Good (value 5), Moderate (4), Unhealthy (3), Very Unhealthy (2) to Hazardous (1), can be forecasted using data streams of B1: air pollutants and meteorology elements B2: wind speed, B3: humidity observed in 12 sites. The context variation, characterising a concept drift problem, makes BAQ index difficult to be forecasted. The semantics of context is based on a DL ALC ontology, including 48 concepts, 13 roles, 598 axioms. An average of 6, 500 RDF triples are generated at each update (i.e., every 600 seconds) for the streams. - Dublin Bus Delay (DBD) Context: DBD, classified as Free (value 5), Low (4), Moderate (3), Heavy (2), Stopped (1) can be forecasted using reputable live stream contextual data (Table 3) related to D1: bus GPS location, delay, congestion status, D2: weather conditions, D3: road incidents. However bus delay is subject to major changes due the high degree of context variation. The latter, responsible for the concept drift problem, impacts accuracy the most. We consider an extended settings by enriching data using a DL EL++ domain ontology (55 concepts, 19 roles and 25, 456 axioms). Table 3: Datasets Details of Dublin Bus Delay Context. | Feature DataSet | Size (Mb) per day | Frequency of Update (seconds) | #Axioms per Update | #RDF Triples per Update | |-------------------|---------------------|---------------------------------|----------------------|---------------------------| | D1: Bus | 120 | 40 | 3,000 | 12,000 | | D2: Weather | 3 | 300 | 53 | 318 | | D3: Incident | 0.1 | 600 | 81 | 324 | - Validation: Accuracy is measured by comparing predictions with real-world observations in cities. - Semantic Impact: Table 4 reports the positive impact of using semantic embeddings (cf. columns with ✓) on all forecasting tasks, with an average improvement of 26.6%. The embeddings naturally identify semantically (dis-)similar contexts by capturing temporal (in-)consistency(ies). Thus, they help in building discriminating models, even for long-termahead forecasting as shown for ∆ = 18-hours with a 33.1% gain. The difference of results between Beijing and Dublin confirms the importance of semantic expressivity i.e., 40+ times more axioms with a 71.5% gain of accuracy for Dublin. Computing semantic embedding (i.e., consistent vector / entailment vector) is on average 2.95s / 1.01s and 1.82 / 0.65s in respectively Dublin and Beijing contexts. . Table 4: Forecasting Accuracy of [A1] with (✓) and without (7) Semantic Embeddings in Beijing and Dublin Contexts. | City | ID : Features | ∆=6 hours - 7 | ∆=6 hours - ✓ | ∆=12 hours - 7 | ∆=12 hours - ✓ | ∆=18 hours - 7 | ∆=18 hours - ✓ | |-------------------------|-------------------------------------------|-----------------|-----------------|------------------|------------------|------------------|------------------| | Beijing | B1 : B1 | .351 | .398 | .344 | .441 | .261 | .342 | | Beijing | B2 : B1 + B2 | .398 | .449 | .350 | .453 | .279 | .371 | | Beijing | B3 : B1 + B3 | .421 | .508 | .373 | .459 | .282 | .379 | | Beijing | B4 : B1 + B2 + B3 Average Improvement (%) | .501 | .611 | .389 | .478 | .286 | .393 | | | | 17.206 | 17.206 | 25.890 | 25.890 | 33.954 | 33.954 | | Dublin | D1 : D1 | .455 | .514 | .387 | .441 | .321 | .387 | | Dublin | D2 : D1 +D2 | .534 | .688 | .499 | .553 | .361 | .497 | | Dublin | D3 : D1 +D3 | .601 | .701 | .513 | .645 | .371 | .547 | | Dublin | D4 : D1 +D2 +D3 | .659 | .921 | .533 | .834 | .601 | .745 | | Average Improvement (%) | Average Improvement (%) | 24.550 | 24.550 | 26.744 | 26.744 | 32.408 | 32.408 | - Feature Impact: Table 4 emphasises an extra accuracy gain when increasing the number of features i.e., average gain of 68.5% accuracy from 1 to 3 features. - Concept Drift is characterised by 48% and 51% of stream updates in respectively BAQ and DBD. We focus on 4 levels of concept drifts, ranging from a .2 to .8 significance ∀∆ ∈ {6, 12, 18}. Level 0 does not capture any change. Figure 3 reports the proportion of severity levels in concept drift for BAQ and DBD e.g., 7% are level-.4 for BAQ while 19% are level-.8 for DBD. Although accuracy clearly declined by increasing the severity level e.g., from 96% (level-.2) to 21% (level-.8) in DBD, semantic embeddings has shown to significantly boost accuracy. More interestingly the more severity the higher improvement i.e., (average) 36% to 56% on level.4 to .8. Thus integrating semantics is a way forward to build machine learning models which are robust to changes, potential erroneous sensor data and concept drifts. Semantic  Concept  Drift  Significance  (value  in  [0,1]) ![Image](https://ijcai.org/proceedings/2017/fulltext/133/image_000001_39368c4335830e7375ac05425ba284623d29349ae23fa705a19355d65fb38dad.png) Beijing Dublin Beijing Dublin Beijing Dublin Beijing Dublin Beijing Dublin Figure 3: Forecasting Accuracy vs. Drift Significance. - Model Consistency Impact: Figures 4 and 5 report accuracy of forecasting tasks on a High and Low Concept Drift versions of the Dublin and Beijing problems, noted HCD and LCD. 85% and 15% of snapshots are impacted by concept drift respectively in HCD and LCD. [A1-2] is evaluated with 3 variances of (ε, σmin, κ): (i) consistent model with (.9, .9, .1), (ii) mixed model with (.5, .5, .5), (iii) inconsistent model with (.1, .1, .9). N = 1, 500. Figure 4 (resp. 5) reports that prediction with consistent (resp. inconsistent) samples outperforms models with inconsistent (resp. consistent) samples by about 318% (resp. 456%) and 254% (resp. 322%) in respectively Beijing and Dublin for LCD (resp. HCD). These results confirm the importance of semantic encoding, which support the encoding of concept drift and consistency properties in our approach. Figure 4: Model Consistency & Forecasting Accuracy. Low Concept Drift. (15% of snapshots impacted by concept drift). ![Image](https://ijcai.org/proceedings/2017/fulltext/133/image_000002_e7f0e44e5c25705ee71262c94508718a7b6e5b3f7c702b665de435ced96907c5.png) Figure 5: Model Consistency & Forecasting Accuracy. High Concept Drift. (85% of snapshots impacted by concept drift). ![Image](https://ijcai.org/proceedings/2017/fulltext/133/image_000003_5c253cd08c7ef793e0ef941a40974ef1b2342e2bf9efc68f622441e8e36be7c9.png) - Baseline: We compare our approach Bi,Di,1≤i≤4 in Table 4 with (i) weighted Stochastic Gradient Descent (SGD), (ii) Auto-Regressive Integrated Moving Average (ARIMA), a standard time-series forecasting model [Saboia, 1977], and two methods addressing concept drift: (iii) Hoeffding Adaptive Tree (HAT), (iv) Leveraging Bagging (LB) [Bifet - et al., 2010b; 2010a]. ARIMA considers one stream variable: BAQ index for Beijing and DBD for Dublin while SGD, HAT and LB use all features of B4, D4 and favour recent snapshots during learning. The forecasted real value in [0, 5] is discretised back using our categories. Results with optimum parameters for [A1-2] are reported. Figure 6 emphasises that our approach (with 3 levels of features: B4, D4) over-performs state-of-the-art methods. The more features the more accurate. More interestingly classic learning algorithms do not generalise as well as [A1-2] in presence of semantics although SGD, HAT, LB integrate all features. [A1-2] shows to be very robust with less variance. Experiments also demonstrate that semantic (in-)consistency [Flouris et al., 2006] matters more than recentness during learning. - Lessons Learnt: Adding semantics to classic learning model has clearly shown the positive impact on accuracy, specially in presence of concept drifts. Our approach also demonstrates that the more semantic axioms the more robust is the model and hence the higher the accuracy. Axiom numbers are critical as they drive and control the semantics of data in streams, which improve accuracy, concept drift detection but not scalability (not reported in the paper). It is worst with more expressive DLs due to consistency checks, and with limited impact on accuracy. Lightweight semantics such as RDF-S would highly limit the scope of our model given the omission of inconsistency checking cf. Figures 4-5. Figure 6: Baseline Comparison of Forecasting Accuracy. (∆ = 6, Approach∗ : Approach with all features). ![Image](https://ijcai.org/proceedings/2017/fulltext/133/image_000004_d53083112aa2979b7d744466882f2f0da7dbfe41c2970b2926b7144052bbf988.png) ## 6 Conclusion We tackled the problem of learning with concept drifts. Semantic reasoning and machine learning have been combined by revisiting features embeddings as semantic embeddings. Such embeddings are exploited in a context of supervised stream learning to learn models, which are robust to concept drifts. Our approach has been shown to be adaptable and flexible to basic learning algorithms. Besides demonstrating accurate prediction with concept drifts in Dublin and Beijing forecasting applications, experiments have shown that encoding semantics in models is a way towards outperforming state-of-the-art approaches. We will investigate the impact of semantic embeddings in other Machine Learning models. ## Acknowledgments This work is funded by the Alibaba-ZJU joint project on e-Business Knowledge Graph, NSFC 61473260/61673338/61672393 and the EU Marie Curie IAPP K-Drive project (286348). ## References 1. [Agrawal et al., 1996] Rakesh Agrawal, Heikki Mannila, Ramakrishnan Srikant, Hannu Toivonen, and A. Inkeri Verkamo. Fast discovery of association rules. In Ad- vances in Knowledge Discovery and Data Mining, pages 307-328. AAAI/MIT Press, 1996. 2. [Baader et al., 2003] Franz Baader, Diego Calvanese, Deb- orah L. McGuinness, Daniele Nardi, and Peter F. Patel- Schneider, editors. The Description Logic Handbook: Theory, Implementation, and Applications, 2003. 3. [Baader et al., 2005] Franz Baader, Sebastian Brandt, and Carsten Lutz. Pushing the el envelope. In IJCAI, pages 364-369, 2005. 4. [Beck et al., 2016] Harald Beck, Minh Dao-Tran, and Thomas Eiter. Equivalent stream reasoning programs. In IJCAI, pages 929-935, 2016. 5. [Bifet et al., 2010a] Albert Bifet, Geoff Holmes, Richard Kirkby, and Bernhard Pfahringer. Moa: Massive online analysis. The Journal of Machine Learning Research, 11:1601-1604, 2010. 6. [Bifet et al., 2010b] Albert Bifet, Geoff Holmes, and Bern- hard Pfahringer. Leveraging bagging for evolving data streams. In Proceedings of the 2010 European Confer- ence on Machine Learning and Knowledge Discovery in Databases: Part I, ECML PKDD'10, pages 135-150, Berlin, Heidelberg, 2010. Springer-Verlag. 7. [Bifet et al., 2015] Albert Bifet, Gianmarco de Fran- cisci Morales, Jesse Read, Geoff Holmes, and Bernhard Pfahringer. Efficient online evaluation of big data stream classifiers. In SIGKDD, pages 59-68. ACM, 2015. 8. [Bishop, 2006] Christopher M Bishop. Pattern recognition. Machine Learning, 128:1-58, 2006. 9. [Cheung et al., 1996] David W Cheung, Jiawei Han, Vin- cent T Ng, and CY Wong. Maintenance of discovered association rules in large databases: An incremental up- dating technique. In ICDE, pages 106-114. IEEE, 1996. 10. [Chu et al., 2011] Wei Chu, Martin Zinkevich, Lihong Li, Achint Thomas, and Belle Tseng. Unbiased online ac- tive learning in data streams. In SIGKDD, pages 195-203. ACM, 2011. 11. [Coble and Cook, 2000] Jeffrey Coble and Diane J. Cook. Real-time learning when concepts shift. In Proceedings of the 13th International Florida Artificial Intelligence Re- search Society Conference, pages 192-196, 2000. 12. [Domingos and Hulten, 2000] Pedro Domingos and Geoff Hulten. Mining high-speed data streams. In SIGKDD, pages 71-80. ACM, 2000. 13. [Flouris et al., 2006] Giorgos Flouris, Zhisheng Huang, Jeff Z. Pan, Dimitris Plexousakis, and Holger Wache. In- consistencies, Negations and Changes in Ontologies. In AAAI, pages 1295-1300, 2006. 14. [Galárraga et al., 2013] Luis Antonio Galárraga, Christina Teflioudi, Katja Hose, and Fabian Suchanek. AMIE: As- sociation rule mining under incomplete evidence in onto- logical knowledge bases. In WWW, pages 413-422. ACM, 2013. 15. [Gama and Kosina, 2011] João Gama and Petr Kosina. Learning decision rules from data streams. In IJCAI, pages 1255-1260, 2011. 16. [Gama et al., 2014] João Gama, Indrė Žliobaitė, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. A survey on concept drift adaptation. ACM Computing Surveys (CSUR), 46(4):44, 2014. 17. Gao et al., ] Jing Gao, Wei Fan, and Jiawei Han. On ap- propriate assumptions to mine data streams: Analysis and practice. In ICDM. 18. [Gao et al., 2007] Jing Gao, Wei Fan, Jiawei Han, and S Yu Philip. A general framework for mining concept-drifting data streams with skewed distributions. In SDM, pages 3-14. SIAM, 2007. 19. [Huang and Stuckenschmidt, 2005] Zhisheng Huang and Heiner Stuckenschmidt. Reasoning with multi-version ontologies: A temporal logic approach. In International Semantic Web Conference, pages 398-412, 2005. 20. [Lecue and Pan., 2013] Freddy Lecue and Jeff Z. Pan. Pre- dicting Knowledge in An Ontology Stream. In IJCAI, 2013. 21. [Lécué, 2015] Freddy Lécué. Scalable maintenance of knowledge discovery in an ontology stream. In IJCAI, pages 1457-1463, 2015. 22. [Lee et al., 2003] Chang-Hung Lee, Ming-Syan Chen, and Cheng-Ru Lin. Progressive partition miner: An efficient algorithm for mining general temporal association rules. IEEE Trans. Knowl. Data Eng., 15(4):1004-1017, 2003. 23. [Ren and Pan, 2011] Yuan Ren and Jeff Z. Pan. Optimising Ontology Stream Reasoning with Truth Maintenance Sys- tem. In Proc. of the ACM Conference on Information and Knowledge Management (CIKM 2011), 2011. 24. [Ren et al., 2011] Yuan Ren, Jeff Z. Pan, and Kevin Lee. Par- allel ABox Reasoning of EL Ontologies. In Proc. of the First Joint International Conference of Semantic Technol- ogy (JIST 2011), 2011. 25. [Ren et al., 2016] Yuan Ren, Jeff Z. Pan, Isa Guclu, and Mar- tin Kollingbaum. A Combined approach to Incremental Reasoning for EL Ontologies. In Proc. of the 10th Inter- national Conference on Web Reasoning and Rule Systems (RR2016), 2016. 26. [Saboia, 1977] Joao Luiz Maurity Saboia. Autoregressive integrated moving average (arima) models for birth fore- casting. Journal of the American Statistical Association, 72(358):264-270, 1977. 27. [Zhang, 2004] Tong Zhang. Solving large scale linear pre- diction problems using stochastic gradient descent algo- rithms. In ICML, page 116. ACM, 2004.