Alexander Artikis

Anastasios Skarlatidis

François Portet
email: francois.portet@imag.fr

Georgios Paliouras

Knowledge Engineering Review 1 Logic-Based Event Recognition

Today's organisations require techniques for automated transformation of their large data volumes into operational knowledge. This requirement may be addressed by employing event recognition systems that detect events/activities of special significance within an organisation, given streams of 'low-level' information that is very difficult to be utilised by humans. Consider, for example, the recognition of attacks on nodes of a computer network given the TCP/IP messages, the recognition of suspicious trader behaviour given the transactions in a financial market, and the recognition of whale songs given a symbolic representation of whale sounds. Various event recognition systems have been proposed in the literature. Recognition systems with a logic-based representation of event structures, in particular, have been attracting considerable attention, because, among others, they exhibit a formal, declarative semantics, they have proven to be efficient and scalable, and they are supported by machine learning tools automating the construction and refinement of event structures. In this paper we review representative approaches of logic-based event recognition and discuss open research issues of this field. We illustrate the reviewed approaches with the use of a real-world case study: event recognition for city transport management.

Introduction

Today's organisations collect data in various structured and unstructured digital formats, but they cannot fully utilise these data to support their resource management. It is evident that the analysis and interpretation of the collected data need to be automated, in order for large data volumes to be transformed into operational knowledge. Events are particularly important pieces of knowledge, as they represent activities of special significance within an organisation. Therefore, the recognition of events is of utmost importance.

Systems for symbolic event recognition -'event pattern matching', in the terminology of [START_REF] Luckham | The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems[END_REF] -accept as input a stream of time-stamped low-level events (LLE). A LLE is the result of applying a computational derivation process to some other event, such as an event coming from a sensor. Using LLE as input, event recognition systems identify high-level events (HLE) of interest -collections of events that satisfy some pattern1 . Consider, for example, the recognition of attacks on nodes of a computer network given the TCP/IP messages, the recognition of suspicious trader behaviour given the transactions in a financial market, and the recognition of whale songs given a symbolic representation of whale sounds.

Numerous event recognition systems have been proposed in the literature -see [START_REF] Luckham | The Power of Events: An Introduction to Complex Event Processing in Distributed Enterprise Systems[END_REF][START_REF] Vu | Automatic video interpretation: A novel algorithm for temporal scenario recognition[END_REF][START_REF] Lv | 3D human action recognition using spatio-temporal motion templates[END_REF][START_REF] Arasu | The CQL continuous query language: semantic foundations and query execution[END_REF][START_REF] Hakeem | Learning, detection and representation of multi-agent events in videos[END_REF][START_REF] Thonnat | Semantic activity recognition[END_REF][START_REF] Etzion | Event Processing in Action[END_REF] for a few examples and [START_REF] Cugola | Processing flows of information: From data stream to complex event processing[END_REF][START_REF] Paschke | Rule-based event processing and reaction rules[END_REF] for two recent surveys. Recognition systems with a logic-based representation of event structures, in particular, have been attracting considerable attention. In this paper we will present representative approaches of logicbased event recognition.

Chronicle Recognition

Chronicle recognition systems are temporal reasoning systems developed for efficient, run-time HLEchronicle -recognition. A chronicle is expressed in terms of a set of events linked together by time constraints and, possibly, a set of context constraints. A number of implementations have been developed for chronicle recognition. In this section we will present the chronicle recognition system (hereafter CRS) of Dousson and colleagues4 [START_REF] Dousson | Extending and unifying chronicle representation with event counters[END_REF][START_REF] Dousson | Improvement of chronicle-based monitoring using temporal focalization and hierarchisation[END_REF][START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchisation[END_REF]. CRS is an extension of IxTeT [START_REF] Ghallab | Managing efficiently temporal relations through indexed spanning trees[END_REF][START_REF] Dousson | Situation recognition: Representation and algorithms[END_REF][START_REF] Ghallab | On chronicles: Representation, on-line recognition and learning[END_REF][START_REF] Dousson | Alarm driven supervision for télécommunication network II -on-line chronicle recognition[END_REF], a version of which was marketed and tested for the supervision of gas turbines, aircraft turbines, and electrical power networks. CRS has been applied to numerous application domains such as cardiac monitoring [START_REF] Callens | Intelligent adaptive monitoring for cardiac surveillance[END_REF], intrusion detection [START_REF] Morin | Correlation of intrusion symptoms: an application of chronicles[END_REF] and mobility management (Dousson et al. 2007) in computer networks, and distributed diagnosis of web services (Le [START_REF] Guillou | Chronicles for on-line diagnosis of distributed systems[END_REF]).

In the following section we present the input language of CRS, in Section 2.2 we present various reasoning algorithms of this system, and in Section 2.3 we present techniques for automatically constructing HLE definitions in the CRS language.

Representation

A chronicle can be seen as a HLE -as mentioned above, it is expressed in terms of a set of events linked together by time constraints and, possibly, a set of context constraints. The input language of CRS relies on a reified temporal logic, where propositional terms are related to time-points or other propositional Table 1: Predicates of CRS.

Predicate Meaning

event(E, T) Event E takes place at time-point T event(F:(?V1,?V2), T) An event takes place at time-point T changing the value of attribute F from V1 to V2

noevent(E, (T1,T2)) Event E does not take place between [T1,T2)

noevent(F:(?V1,?V2), (T1,T2))

No event takes place between [T1,T2) that changes the value of attribute F from V1 to V2 hold(F:?V, (T1,T2

))

The value of attribute F is V between [T1,T2) occurs(N, M, E, (T1,T2)) Event E takes place at least N times and at most M times between [T1,T2)

terms. Time is considered as a linearly ordered discrete set of instants. The language includes predicates for persistence, event absence and event repetition. Table 1 presents the CRS predicates. Variables start with an upper case letter while predicates and constants start with a lower-case letter. ? is the prefix of an atemporal variable. 'Attributes' represent context information. Attributes and events (also called 'messages' in the CRS language) may have any number of parameters. Details about the input language of CRS, and CRS in general, can be found on the web page of the system 4 . The code below, for example, expresses HLE related to vehicle (bus/tram) punctuality in the CRS language:

(1) chronicle punctual[?Id, ?VehicleType](T2) { (2) event(stop_enter[?Id, ?VehicleType, ?StopId, scheduled], T1) (3) event(stop_leave[?Id, ?VehicleType, ?StopId, scheduled], T2) (4) T2 -T1 in [1,2000] (5) } (6) chronicle non_punctual[?Id, ?VehicleType](T1) { ( 7) event(stop_enter[?Id, ?VehicleType, *, late], T1) (8) } (9) chronicle punctuality_change[?Id, ?VehicleType, non_punctual](T2) { (10) event(punctual[?Id, ?VehicleType], T1) (11) event(non_punctual[?Id, ?VehicleType], T2) (12) T2 -T1 in [1, 20000] (13) noevent(punctual[?Id, ?VehicleType], (T1+1, T2)) ( 14) noevent(non_punctual[?Id, ?VehicleType], (T1+1, T2)) (15) }

The atemporal variables of a chronicle (HLE) and an event (LLE or HLE) are displayed in square brackets. * denotes that a variable can take any value. Lines (1)-(5) of the above CRS code express a set of conditions in which a vehicle of a particular type (represented by VehicleType) and Id is said to be punctual: the vehicle enters a stop and leaves the same stop (represented by StopId) at the scheduled time. The time-stamp of the 'punctual' HLE is the same as that of the 'stop leave' subevent (that is, T2). The first and the last subevent of the 'punctual' HLE, that is, 'stop enter' and 'stop leave', must take place within 2000 time-points in order to recognise 'punctual' (see line (4)). Lines ( 6)-( 8) express one out of several cases in which a vehicle is said to be non-punctual: the vehicle enters a stop after the scheduled time (that is, it is late). 'non-punctual' (respectively 'punctual') is defined as a disjunction of 'stop enter' and 'stop leave' LLE satisfying certain conditions. Disjunction is expressed in the CRS language with the use of multiple chronicles (explicit representation of disjunction is not allowed because it makes reasoning in CRS NP-complete -a presentation of the reasoning techniques of CRS is given in the following section). For simplicity we do not show here the chronicles expressing the other cases in which a vehicle is said to be non-punctual (respectively punctual).

Lines ( 9)-(15) of the above code fragment express the 'punctuality change' HLE: punctuality changes (to non-punctual) when a vehicle that was punctual at an earlier time now is not punctual. Another HLE definition (similar to the one shown above) deals with the case in which a vehicle was not punctual earlier and now is punctual.

Both quantitative and qualitative temporal constraints can be represented in the CRS language, the latter being replaced by numerical constraints during compilation -for instance, a constraint of the form T1 > T0 is translated to T1 -T0 in [1,∞). More details about the compilation stage of CRS are given in the following section. Note that the CRS language allows events not to be completely ordered. Consider the following code fragment: event(abrupt_acceleration[?Id, ?VehicleType], T1) event(sharp_turn[?Id, ?VehicleType], T2) T2-T1 in [-3, 8] According to the above constraints, 'sharp turn' may take place before, at the same time, or after 'abrupt acceleration'.

All events shown in the above code fragments are instantaneous. CRS does not allow for the explicit representation of durative events. One may implicitly represent the interval/duration of such an event in the CRS language by representing two instantaneous events, one indicating the time-point in which the durative event starts taking place, and one indicating the time-point in which it stops occurring. The CRS treatment of durative events allows the representation of the interval relations of a restricted interval algebra [START_REF] Vilain | Constraint propagation algorithms for temporal reasoning[END_REF][START_REF] Nebel | Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra[END_REF], but does not support all of [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF] interval relations.

Often in the literature durative events are not even implicitly represented -they are treated as if they occur at an atomic instant. It has been pointed out [START_REF] Paschke | ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics[END_REF]) that such a treatment leads to logical problems and unintended semantics for several event algebra operators -such operators facilitate the development of HLE definitions.

CRS is a temporal reasoner and, as such, it does not support mathematical operators on the constraints of atemporal variables. It is not possible to compute the distance between two entities given their coordinates, for example. In the CTM HLE definition concerning passenger safety, for instance, we cannot express that a vehicle accident or violence within a vehicle is more severe when the vehicle if far from a hospital or a police station. Moreover, the CRS language does not support universally quantified conditions. In CTM, for instance, we cannot define HLE using LLE coming from all vehicles (of a particular route).

Although the CRS language is limited in the aforementioned ways, it has proven to be expressive enough for numerous application domains, some of which were mentioned in the beginning of Section 2.

Reasoning

Each HLE definition expressed in the CRS language is typically translated to a Temporal Constraint Network (TCN) [START_REF] Dechter | Temporal constraint networks[END_REF][START_REF] Ghallab | On chronicles: Representation, on-line recognition and learning[END_REF][START_REF] Dousson | Alarm driven supervision for télécommunication network II -on-line chronicle recognition[END_REF][START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchisation[END_REF] (see [START_REF] Choppy | Coloured petri nets for chronicle recognition[END_REF], however, for a Petri-Net based semantics of the CRS language). Each subevent of a HLE definition corresponds to a node in the TCN, whereas the temporal constraints between two subevents determine the edge between the nodes expressing the subevents. Figure 2(a), for example, shows the TCN expressing the CTM HLE 'uncomfortable driving'. The subevents of this HLE are 'approach intersection', 'abrupt deceleration', 'sharp turn' and 'abrupt acceleration'. The temporal constraints on these events that, if satisfied, will lead to the recognition of 'uncomfortable driving', are expressed by the edges of the TCN. For example, 'abrupt deceleration' should take place, at the earliest, 2 time-points after the 'approach intersection' LLE and, at the latest, 5 time-points after this LLE. Briefly, a vehicle is said to be driven in an uncomfortable manner if, within a specified time period, it approaches an intersection, and then decelerates abruptly, turns sharply and accelerates abruptly. (There are other ways of defining 'uncomfortable driving'. This example is presented simply to provide a concrete illustration.) The CRS code of this simplified definition of 'uncomfortable driving' may be found below:

( During the off-line compilation stage, CRS propagates the constraints of a TCN using an incremental path consistency algorithm [START_REF] Mackworth | The complexity of some polynomial network consistency algorithms for constraint satisfaction problems[END_REF], in order to produce the least constrained TCN expressing the user constraints. Figure 2(b), for example, shows the TCN for 'uncomfortable driving' after constraint propagation. In this example, the edge between 'abrupt deceleration ' and 'sharp turn', and that between 'sharp turn' and 'abrupt acceleration', becomes [0 , 5 ] due to the temporal constraint [1 , 5 ] between 'abrupt deceleration' and 'abrupt acceleration'. The constraint [3 , 10 ] (dashed in Figure 2(b)) is removed because it is redundant with respect to the two other constraints [2 , 5 ] and [1 , 5 ] from which it can be completely deduced.

The use of the incremental path consistency algorithm allows for checking the consistency of the temporal constraints of a TCN -see [START_REF] Dousson | Alarm driven supervision for télécommunication network II -on-line chronicle recognition[END_REF] for details. CRS, therefore, detects inconsistent HLE definitions at compile-time and reports the inconsistencies to the user.

Once the least constrained TCN expressing the user constraints have been compiled, HLE recognition may commence. The recognition process of CRS is illustrated in Figure 3 -this figure shows the process of recognising 'uncomfortable driving'. The left part of Figure 3 shows the effects of the arrival of 'approach intersection' at time-point 6 , while the right part of this figure shows the effects of the arrival of 'abrupt deceleration' at time-point 10 . The arrival of 'approach intersection' creates an instance of 'uncomfortable driving', that is, a partial instantiation of the definition of this HLE. The horizontal grey lines in Figure 3 show the temporal windows of the subevents of 'uncomfortable driving', that is, the possible times in which a subevent may take place without violating the constraints of the 'uncomfortable driving' instance.

Upon the arrival of 'approach intersection', the temporal window of 'abrupt deceleration' becomes [8 , 11 ] because, according to the TCN of 'uncomfortable driving' (see Figure 2(b)), 'abrupt deceleration' must take place 2 time-points after the 'approach intersection' LLE at the earliest, and, at the latest, 5 timepoints after this LLE. Similarly, the temporal window of 'sharp turn' becomes [8 , 16 ], while that of 'abrupt acceleration' becomes [9 , 16 ]. The occurrence of 'abrupt deceleration' at time-point 10 is integrated into the displayed instance of 'uncomfortable driving', as it complies with the constraints of the instance (that is, 'abrupt deceleration' takes place within its temporal window), and constrains further the temporal windows of the (yet) undetected subevents of 'uncomfortable driving' (see the right part of Figure 3). Using this type of recognition, CRS may report to the user not only a fully recognised HLE, but also a partially recognised one, that is, a pending HLE instance. Moreover, CRS may report the events that need to be detected in order to fully recognise a HLE. These types of information have proven to be very helpful in various application domains (see, for example, [START_REF] Gao | Using temporal constraints to integrate signal analysis and domain knowledge in medical event detection[END_REF]). [3,6] approach intersection@1 approach intersection@4 abrupt deceleration@7 Figure 3 shows the evolution of one HLE instance. For each HLE definition more than one instance may be created. Figure 4 illustrates the instance management of CRS using the example of the 'uncomfortable driving' HLE. The occurrence of 'approach intersection' at time-point 1 creates a new instance of 'uncomfortable driving'. CRS computes the temporal windows of the forthcoming events -for example, 'abrupt deceleration' is expected between [3 , 6 ]. The occurrence of the second 'approach intersection' LLE at time-point 4 creates a new instance of 'uncomfortable driving'. Moreover, the passing of time results in constraining the temporal windows of the forthcoming events of the first instance. For example, the temporal window of 'abrupt deceleration' becomes [4 , 6 ]. Upon the arrival of 'abrupt deceleration' at time-point 7 , CRS makes a copy of the second instance of 'uncomfortable driving', thus creating a third instance of this HLE, and integrates 'abrupt deceleration' into the third HLE instance. CRS keeps the second instance because another 'abrupt deceleration' LLE may take place in the future (more precisely, between 7 and 9 ), which may lead to another recognition of 'uncomfortable driving'. The first instance of 'uncomfortable driving' is killed at time-point 7 , because no 'abrupt deceleration' LLE was detected between [4 , 6 ], and thus it is not possible to satisfy the constraints of this instance any more.

In the examples presented in this section we assume that events arrive in a timely manner. Such an assumption is made to simplify the presentation. We will discuss shortly the consequences of the delayed arrival of events.

Table 2 illustrates event recognition in CRS using a larger LLE narrative. More precisely, this table shows an example LLE narrative concerning a particular vehicle, and the 'uncomfortable driving' HLE that are recognised given this narrative. By time-point 19 all sub-events of the 'uncomfortable driving' HLE are detected. However, this HLE is not recognised because the detected LLE do not satisfy the temporal constraints of the HLE definition. The occurrence of 'abrupt acceleration' at time-point 19 is too late; at that time there are no pending instances of 'uncomfortable driving' (the last instance was killed at time-point 14 ).

The first recognition of 'uncomfortable driving' takes place at time-point 39 . The occurrence of 'abrupt acceleration' at that time is integrated into the pending instance of 'uncomfortable driving' that consists of the occurrence of 'approach intersection' at time-point 36 , 'abrupt deceleration' and 'sharp turn' at time-point 38 . This instance is duplicated before integrating the occurrence of 'abrupt acceleration' at 39 because it may lead to another recognition of 'uncomfortable driving' in the future. Indeed, at time-point 42 'uncomfortable driving' is recognised again: the occurrence of 'abrupt acceleration' at time-point 42 is integrated into the aforementioned pending instance.

Unlike the occurrences of 'abrupt acceleration' at time-points 39 and 42 , the occurrence of this LLE at time-point 55 does not lead to the recognition of 'uncomfortable driving'. At this time-point there is no pending instance of 'uncomfortable driving', as the last pending instance was killed at time-point 44 . CRS stores all pending HLE instances in trees, one for each HLE definition. At the arrival of a new event, and at a clock update, CRS traverses these trees in order to further develop, or kill, some HLE instances. For K HLE instances, each having n subevents, the complexity of processing each incoming event or a clock update is O(Kn 2 ).

To allow for the delay in the information exchange between distributed components, such as the LLE detection component and the HLE recognition component, CRS processes LLE arriving in a non-timely manner -the user specifies the maximum allowed delay for LLE. In this way, CRS may process LLE arriving in a non-chronological order, that is, process LLE that happened (were detected) before some of the already acquired LLE. This feature, however, affects the efficiency of CRS: CRS delays the time at which a pending HLE instance must be killed due to the possibility of a late arrival of a subevent of the HLE. In other words, the number K of HLE instances reduces at a slower rate.

Various techniques have been proposed for reducing the number K of HLE instances that are generated, and thus improving the efficiency of CRS. Bounding the temporal distance between the first subevent and the last subevent of a HLE (see, for example, the definition of punctual in Section 2.1) is one way to reduce HLE instance duplication. Moreover, there may be HLE that cannot have two completed instances overlapping in time or share the occurrence of an event. In this case, when a HLE instance is completed (the HLE is recognised) all its pending instances must be removed.

A recently developed technique for reducing the number of generated HLE instances, and, therefore, improving the efficiency of CRS, is called temporal focusing [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchisation[END_REF]. This technique can be briefly described as follows. Let's assume that, according to the definition of HLE Γ, event e r should take place after event e f in order to recognise Γ, e r is a very rare event and e f is a frequent event. The frequency of events is determined by an a priori analysis of the application under consideration. In this case CRS stores all incoming e f events and starts the recognition process, that is, creates a new instance of Γ, only upon the arrival of an e r event -the new instance will include e r and a stored e f that satisfies the constraints of Γ. In this way the number of generated HLE instances is significantly reduced.

Temporal focusing significantly improves the efficiency of recognising 'uncomfortable driving', for example, as 'approach intersection' is a very frequent LLE, 'abrupt deceleration' is a rare LLE, and 'abrupt deceleration' should take place after 'approach intersection' in order to recognise 'uncomfortable driving'.

Empirical analysis has shown that CRS can be very efficient and scalable [START_REF] Dousson | Chronicle recognition improvement using temporal focusing and hierarchisation[END_REF].

Although the CRS language is fairly comprehensible, synthesising and generalising expert temporal knowledge, which can be highly application-dependent, is not a trivial task. Therefore, methods for automatically generating and refining HLE definitions from data are highly desirable. In the following section we review machine learning techniques that have been used for constructing HLE definitions in the CRS language.

Machine Learning

Various approaches have been proposed in the literature for the automated construction of HLE definitions expressed in the CRS language. One of the earliest approaches is the automata-based learning method of [START_REF] Ghallab | On chronicles: Representation, on-line recognition and learning[END_REF]. Briefly, this method, which is inspired from learning techniques used in syntactical pattern recognition, learns automata from positive and negative HLE examples. Based on the learnt automata, discriminative 'skeleton models' are generated, containing only events and constraints, without context information. These skeleton models have to be completed by the human user with context information as well as quantitative temporal constraints.

Another line of research for the automated construction of HLE definitions concerns the use of unsu-pervised learning techniques. One such technique is the frequency-based analysis of sequences of eventssee, for example, [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF][START_REF] Yoshida | Mining sequential patterns including time intervals[END_REF][START_REF] Fessant | Mining of an alarm log to improve the discovery of frequent patterns[END_REF][START_REF] Hirate | Sequential pattern mining with time intervals[END_REF][START_REF] Vautier | Towards data mining without information on knowledge structure[END_REF][START_REF] Álvarez | A data mining algorithm for inducing temporal constraint networks[END_REF]. Most of the approaches adopting this technique rely on an extended version of the Apriori algorithm [START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF] to discover frequent sequences of events -the temporal distance between the events of a frequent sequence is computed using lower and higher frequency thresholds. A well-known approach for HLE definition discovery is the FACE system of [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF]. FACE uses an algorithm for incremental generation of definitions of HLE that are frequent in event narratives/logs. [START_REF] Fessant | Mining of an alarm log to improve the discovery of frequent patterns[END_REF] pointed out that FACE is very memory consuming in the presence of large event narratives. To address this issue, Fessant et al. proposed a pre-processing phase based on a Kohonen's self-organising map [START_REF] Kohonen | Self-Organising Maps[END_REF] to extract the most 'interesting' sub-narratives of events before the data mining phase of FACE. Frequency-based analysis is a promising approach for discovering unknown event patterns in databases or logs. However, these approaches are limited to propositional learning. Moreover, they may not be adapted to learning definitions of HLE that are not frequent in data -in some applications the recognition of such HLE is of utmost importance.

A common technique for learning HLE definitions in a supervised manner concerns the use of inductive logic programming (ILP) [START_REF] Muggleton | Inductive logic programming[END_REF]) -see, for example, [START_REF] Carrault | Temporal abstraction and inductive logic programming for arrhyhtmia recognition from electrocardiograms[END_REF][START_REF] Callens | Intelligent adaptive monitoring for cardiac surveillance[END_REF]. ILP is well-suited to the construction of HLE definitions expressed in the CRS language because, among others, the CRS HLE definitions can be straightforwardly translated into the logic programming representation used by ILP systems, and vice-versa -this translation is illustrated below. In what follows, therefore, we will present the use of ILP for constructing HLE definitions for CRS.

To illustrate the translation of CRS HLE definitions into logic programming consider, for example, the definition of 'uncomfortable driving' in logic programming (this definition was presented in the CRS language in the previous section):

uncomfortable driving(T4, Id, VehicleType) ← approach intersection(T1, Id, VehicleType), abrupt deceleration(T2, Id, VehicleType), sharp turn(T3, Id, VehicleType), abrupt acceleration(T4, Id, VehicleType), T2-T1 >= 2, T2-T1 =< 5, T4-T2 >= 1, T4-T2 =< 5, T4 >= T3, T4-T3 =< 8, T4 >= T1, T4-T1 =< 10, T2 =< T3

A chronicle ('uncomfortable driving', in this example), as well as every event in the definition of a chronicle (here 'approach intersection', 'abrupt deceleration', 'sharp turn' and 'abrupt acceleration'), can be translated into a predicate whose arguments are the chronicle/event occurrence time (T1, for example) and the chronicle/event parameters (for example, Id and VehicleType). Temporal constraints in the CRS language can be translated into arithmetic expressions -for instance, T2-T1 in [2,5] can be translated into T2-T1 >= 2, T2-T1 =< 5. In general, any chronicle definition can be translated into a Horn clause whose head is the predicate representing the chronicle, and whose body is the conjunction of predicates representing the events of the chronicle and arithmetic expressions constraining the occurrence of these events.

ILP is the combination of inductive machine learning and logic programming. It aims at inducing theories from examples in the form of a first-order logic program. It inherits, from machine learning, the principle of hypothesis induction from data, but its first-order logic representation allows the induction of more expressive theories than classical machine learning approaches, which induce propositional hypotheses. Furthermore, a-priori background knowledge, such as human expertise, can easily be used to guide learning. ILP has proven adequate in learning from very small datasets, especially in the presence of strong prior knowledge, while making good use of large volumes of data, where available. This also includes constructing theories that capture exceptional cases in datasets, where exceptions are a small minority of a dataset. A detailed account of ILP may be found in [START_REF] Dzeroski | Relational Data Mining[END_REF][START_REF] Konstantopoulos | Induction as a search[END_REF], for example.

The logical elements involved in ILP can be defined as follows:

• A set of positive examples E + and a set of negative examples E -. These are typically ground facts.

• A hypothesis language L H , from which hypotheses H are constructed.

• A background knowledge base B. B and H are sets of clauses/rules of the form α ← l 1 , . . . , l n where α is a 'head' literal and each l i is a 'body' literal.

ILP searches for hypotheses H ⊆ L H , such that B ∧ H E + (completeness) and B ∧ H ∧ E - (consistency) [START_REF] Muggleton | Inductive logic programming: Theory and methods[END_REF]. The completeness condition guarantees that all positive examples in E + can be deduced from H and B. The consistency condition guarantees that no negative example in E -can be deduced from H and B.

Different ILP methods adopt different strategies to induce hypotheses H . A simple and common approach starts by selecting a positive example e + from E + , constructing a conjunctive first-order clause h ∈ L H that entails e + , with respect to the background knowledge B, but does not entail any example from E -. All positive examples covered by h are then removed and the same procedure is iterated over the remaining positive examples to produce a new clause. Learning a clause h can be seen as walking through the space of clauses of L H that entail e + , with respect to B. Such a space, also known as version space, is shown in Figure 5. The empty clause, that is, the most general clause, is at the top of the space, and the most specific clause from L H that entails e + with respect to B -the 'bottom clause' -is at the bottom of the space. According to the strategy that is adopted, the search may be general-to-specific or specific-to-general. In a general-to-specific strategy, the search will start with the empty clause and will try to specialise it, for instance, by adding conjuncts that cover the positive example and help exclude negative ones. The opposite happens in a specific-to-general strategy that starts with the bottom clause. An exhaustive search is usually impossible, due to the exponential complexity of the version space, and thus pruning and heuristics must be employed to guide the search. For instance, during the search, if a clause does not cover the positive example under consideration (respectively covers a negative example) then it is meaningless to specialise (respectively generalise) this clause further, because it would not improve its coverage. When using a search method that allows backtracking, such as best-first search, a small list of the 'best' clauses generated so far is maintained, sorted according to their coverage. In this manner, search can backtrack directly to the next best option and continue from that point in the version space.

Reducing the version space and guiding more efficiently the search are two of the main challenges of ILP. One way to address these challenges is by acting on inductive bias. In ILP three types of bias are used [START_REF] Nédellec | Declarative bias in ILP[END_REF]: the search bias which specifies how the space is walked; the validation bias which determines the criteria according to which a candidate hypothesis (clause) is evaluated; and the language bias which restricts L H . A form of language bias that is typically used in ILP is called mode declarations. This particular form of bias will be illustrated presently.

Many ILP algorithms have been developed in the literature. These algorithms differ in, among others, the way they perform the search, and the way they bias learning. Examples of ILP algorithms include FOIL [START_REF] Quinlan | Induction of logic programs: Foil and related systems[END_REF], Progol5 [START_REF] Muggleton | Theory completion using inverse entailment[END_REF], icl6 [START_REF] Laer | From propositional to first order logic in machine learning and data mining[END_REF] andAleph 7 . In what follows we illustrate the use of Aleph -a frequently used ILP algorithm -for learning HLE definitions expressed in the CRS language. A detailed example of learning CRS HLE definitions using ILP may be found in [START_REF] Carrault | Temporal abstraction and inductive logic programming for arrhyhtmia recognition from electrocardiograms[END_REF].

To learn hypotheses H expressing HLE definitions of 'uncomfortable driving', for example, we use the following background knowledge B (only a fragment of B is shown here):

% LLE for bus b1 stop enter(e1, init, pos1, 0, b1, bus, s8, scheduled) stop leave(e2, e1, pos1, 1, b1, bus, s8, late) approach intersection(e3, e2, pos1, 2, b1, bus) abrupt deceleration(e4, e3, pos1, 4, b1, bus) sharp turn(e5, e4, pos1, 6, b1, bus) abrupt acceleration(e6, e5, pos1, 8, b1, bus) ... quantitative distance(e2, e1, 1) quantitative distance(e3, e2, 1) quantitative distance(e4, e3, 2) quantitative distance(e5, e4, 2) quantitative distance(e6, e5, 2) ...

% domain knowledge qualitative distance(X, Y, very long) ← quantitative distance(X, Y, D), D>120 qualitative distance(X, Y, long) ← quantitative distance(X, Y, D), D>10, D<121 qualitative distance(X, Y, short) ← quantitative distance(X, Y, D), D>5, D<11 qualitative distance(X, Y, very short) ← quantitative distance(X, Y, D), D<6
B includes the event narrative used for learning the hypotheses and a set of rules expressing domain knowledge. In this example, the narrative consists of a stream of detected CTM LLE. Each predicate representing a LLE, such as approach intersection, has the following arguments: the first argument represents the id of the LLE, while the second argument represents the id of the directly temporally preceding LLE. init states that there is no temporally preceding LLE, that is, the LLE having init as the second argument is the first LLE of the sequence. The first two arguments of LLE specify event chaining in a symbolic manner. Such a symbolic representation of temporal relations between events is necessary because Aleph does not perform numerical reasoning. The third argument of a LLE predicate associates the LLE with a positive example from E + (such as the first positive example pos1) or a negative example from E -, while the fourth argument represents the occurrence time of the LLE. The remaining arguments represent the standard properties of the LLE.

The quantitative distance facts included in B express the temporal distance between two events. The qualitative distance rules express domain knowledge: they translate the numerical temporal distances into symbolic distances (for example, 2 becomes very short). This translation is necessary because, as mentioned earlier, Aleph does not perform numerical reasoning. The distance classification may be obtained by simple equal-frequency discretisation on a log of quantitative distance facts, or by expertise if available.

Apart from the background knowledge B, we specify a set of mode declarations M -a type of language bias -to restrict the version space. Consider the following declarations specified for learning the definition of 'uncomfortable driving':

:-modeh(1,uncomfortable_driving(+ex)) :-modeb(1,stop_enter(-event,-event,+ex,-int,-id,-vehicletype,-stopid,-timetablecompliance)) :-modeb(1,stop_leave(-event,-event,+ex,-int,-id,-vehicletype,-stopid,-timetablecompliance)) :-modeb(1,approach_intersection(-event,-event,+ex,-int,-id,-vehicletype)) :-modeb(1,abrupt_deceleration(-event,-event,+ex,-int,-id,-vehicletype)) :-modeb(1,sharp_turn(-event,-event,+ex,-int,-id,-vehicletype)) :-modeb(1,abrupt_acceleration(-event,-event,+ex,-int,-id,-vehicletype)) :-modeb(*,qualitative_distance(+event,+event,#duration))

A mode declaration is either a head declaration modeh(r,s) or a body declaration modeb(r,s), where s is a ground literal, the 'scheme', which serves as a template for literals in the head or body of a hypothesis clause, and r is an integer, the 'recall', which limits how often the scheme is used. An asterisk * denotes an arbitrary recall. The placemarkers +, -, # express, respectively, input terms, output terms, and ground terms. Any input term in a body literal must be an input term in the head or an output term in some preceding body literal. A set M of mode declarations defines a language L(M ) ⊆ L H within which a hypothesis H must fall, that is, H ⊆ L(M ). A clause α ← l 1 , . . . , l n belongs in L(M ) if and only if the head literal α (respectively each body literal l i ) is obtained from some head (respectively body) declaration in M by replacing all # placemarkers with ground terms, all + placemarkers with input variables, and all -placemarkers with output variables. Given that H ⊆ L(M ), the head of a hypothesis, in the presented illustration, is uncomfortable driving, while in the body of a hypothesis we may have a predicate expressing the LLE shown above, as well as qualitative distance expressing the temporal distance between these LLE. No other LLE may be in the body of uncomfortable driving (we set this constraint due to prior knowledge about the subevents of uncomfortable driving).

Other types of bias may also be used, such as setting the maximum number of body literals that a clause may contain.

Finally, to further guide the learning, we have set the following 'integrity constraint':

⊥ ← hypothesis( , Body, ), broken sequence(Body)
hypothesis is a built-in Aleph predicate -the second argument of this predicate expresses the body of the hypothesis clause currently under consideration. broken sequence(Body) is a user-defined predicate that is true when more than one literal (event) in the Body does not have its directly temporally preceding event in Body. The above integrity constraint, therefore, states that any candidate hypothesis clause in which there is more than one event in the body that does not have a directly temporally preceding event must be discarded. The absence of a temporally preceding event is allowed only for the initial event of a hypothesis clause. and negative examples E -, Aleph performs the following operations. First, it selects an example from E + to be generalised (such as uncomfortable driving(pos1)). Second, it generates the most specific clause that entails this example with respect to B. In the case of uncomfortable driving(pos1) the following clause is produced:

[bottom clause]
uncomfortable driving(Ex) ← stop enter(E1, Init, Ex, T1, Id, VehicleType, StopId, TC1), stop leave(E2, E1, Ex, T2, Id, VehicleType, StopId, TC2), approach intersection(E3, E2, Ex, T3, Id, VehicleType), abrupt deceleration(E4, E3, Ex, T4, Id, VehicleType), sharp turn(E5, E4, Ex, T5, Id, VehicleType), abrupt acceleration(E6, E5, Ex, T6, Id, VehicleType), qualitative distance(E2, E1, very short), qualitative distance(E3, E2, very short), qualitative distance(E4, E3, very short), qualitative distance(E5, E4, very short), qualitative distance(E6, E5, very short) Third, Aleph searches for a more general clause than that generated in the previous step, aiming to cover as many positive examples from E + as possible, without covering any negative examples from E -. Fourth, it adds the clause to H, removing redundant clauses and restarting with a new example from E + until E + is empty.

In practice, the examples used to induce a hypothesis H, as well as the event narrative that is part of B, may be noisy. In order to facilitate learning under such conditions, ILP systems relax the consistency and completeness requirements, allowing some negative examples to be deduced from H and B and some positive ones to not be covered. An approach that has been specifically developed for learning hypotheses in noisy environments is presented in Section 4.

The result of ILP, in this case, comprises the following:

[Rule 1]
uncomfortable driving(Ex) ← approach intersection(E1, Init, Ex, T1, Id, VehicleType), abrupt deceleration(E2, E1, Ex, T2, Id, VehicleType), sharp turn(E3, E2, Ex, T3, Id, VehicleType), abrupt acceleration(E4, E3, Ex, T4, Id, VehicleType), qualitative distance(E2, E1, very short), qualitative distance(E3, E2, very short), qualitative distance(E4, E3, very short)

The above clause is translated into the following CRS code:

T2 -T1 in [0, 5] T3 -T2 in [0, 5] T4 -T3 in [0, 5] }
The above CRS code represents a less accurate account of the numerical temporal constraints than that of the definition presented in Section 2.2, but the HLE structure has been correctly discovered, without adding any unnecessary subevents such as stop leave. Learning numerical temporal constraints with the use of ILP is an issue of current research.

Learning HLE definitions that have other HLE as subevents is performed in a similar manner. In this case, however, one would have to add to the background knowledge base B a HLE narrative, as opposed to a LLE narrative. To learn the definition of the punctuality change HLE, for example, B would have to include a narrative of punctual and non punctual HLE.

The Event Calculus

The Event Calculus (EC) was introduced by [START_REF] Kowalski | A logic-based calculus of events[END_REF] as a logic programming framework for representing and reasoning about events and their effects. Since then various alternative formalisations and implementations have been developed. As [START_REF] Miller | Some alternative formulations of the event calculus[END_REF] point out, EC has been reformulated in various logic programming forms (for instance, [START_REF] Sadri | Variants of the event calculus[END_REF][START_REF] Chittaro | Efficient temporal reasoning in the cached event calculus[END_REF][START_REF] Denecker | A realistic experiment in knowledge representation in open event calculus: protocol specification[END_REF][START_REF] Paschke | ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics[END_REF])), in classical logic (for example, [START_REF] Shanahan | The event calculus explained[END_REF][START_REF] Miller | The event calculus in a classical logic -alternative axiomatizations[END_REF]Cervesato et al. 2000;Mueller 2006a)), in modal logic (for example, [START_REF] Cervesato | Modal event calculi with preconditions[END_REF][START_REF] Cervesato | The complexity of model checking in modal event calculi with quantifiers[END_REF]Cervesato et al. 2000)), and even in non-logic-based languages (such as [START_REF] Farrell | Using the event calculus for tracking the normative state of contracts[END_REF]).

EC has been frequently used for event recognition -to the best of our knowledge, only in a logic programming form, as in [START_REF] Chittaro | Using a general theory of time and change in patient monitoring: Experiment and evaluation[END_REF]Cervesato and Montanari 2000;[START_REF] Chaudet | Extending the event calculus for tracking epidemic spread[END_REF] EC is related to other formalisms proposed in the literature of commonsense reasoning, such as the Situation Calculus [START_REF] Mccarthy | Some philosophical problems from the standpoint of artificial intelligence[END_REF][START_REF] Reiter | Knowledge in Action: Logical Foundations for Describing and Implementing Dynamical Systems[END_REF], the action language C + ( [START_REF] Giunchiglia | Nonmonotonic causal theories[END_REF][START_REF] Akman | Representing the zoo world and the traffic world in the language of the Causal Calculator[END_REF]), the fluent calculus [START_REF] Thielscher | From situation calculus to fluent calculus: State update axioms as a solution to the inferential frame problem[END_REF][START_REF] Thielscher | The qualification problem: A solution to the problem of anomalous models[END_REF] and Temporal Action Logics [START_REF] Doherty | TAL) temporal action logics: Language specification and tutorial[END_REF][START_REF] Kvarnström | TALplanner and other extensions to temporal action logic[END_REF]. Comparisons between formalisms for commonsense reasoning and proofs of equivalence between some of them may be found in [START_REF] Kowalski | Reconciling the event calculus with the situation calculus[END_REF]Miller

(F = V ) The value of fluent F is V at time 0 holdsAt(F = V , T ) The value of fluent F is V at time T holdsFor(F = V , I )
I is the list of the maximal intervals for which

F = V holds continuously initiatedAt(F = V , T )
At time T a period of time for which [START_REF] Miller | Some alternative formulations of the event calculus[END_REF]Mueller 2006a;Mueller 2006b;[START_REF] Craven | Execution mechanisms for the action language C+[END_REF], for example. The advantages of EC over other formalisms for commonsense reasoning with respect to event recognition are outlined in [START_REF] Paschke | ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics[END_REF][START_REF] Paschke | Rule-based event processing and reaction rules[END_REF].

F = V is initiated terminatedAt(F = V , T ) At time T a period of time for which F = V is terminated
In the following section we present a high-level review of the expressiveness of EC as a logic programming language, in Section 3.2 we present a concrete implementation of this formalism, while in Section 3.3 we present techniques for automatically constructing and refining an EC logic program.

Representation

In this section we present features of typical EC dialects for event recognition [START_REF] Artikis | A logic programming approach to activity recognition[END_REF]Cervesato and Montanari 2000;[START_REF] Paschke | ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics[END_REF]). The time model of EC is often linear and it may include real numbers or integers. Where F is a fluent -a property that is allowed to have different values at different points in time -the term F = V denotes that fluent F has value V . Boolean fluents are a special case in which the possible values are true and false. Informally, F = V holds at a particular time-point if F = V has been initiated by an event at some earlier time-point, and not terminated by another event in the meantime.

An event description in EC includes rules that define the event occurrences, the effects of events, and the values of fluents. Table 3 presents typical predicates of EC dialects for event recognition. Variables start with an upper-case letter while predicates and constants start with a lower-case letter.

An EC dialect for event recognition has typically built-in rules for holdsAt and holdsFor, that is, for computing the value of a fluent at a particular time and for computing the maximal intervals in which a fluent has a particular value (there are EC dialects with additional built-in rules for more expressive temporal representation [START_REF] Miller | Some alternative formulations of the event calculus[END_REF]). A partial specification of holdsAt, for example, is given below:

holdsAt(F = V, T ) ← initiatedAt(F = V, T s ), T s ≤ T, not broken(F = V, T s , T ) (1) broken(F = V, T s , T ) ← terminatedAt(F = V, T e ), T s ≤ T e ≤ T (2)
not represents 'negation by failure' [START_REF] Clark | Negation as failure[END_REF]. The above rules state that F = V holds at T if F = V has been initiated at T s , where T s ≤ T , and not 'broken', that is, terminated, in the meantime. The events that initiate/terminate a fluent are represented in the body of initiatedAt and terminatedAt -the definitions of these two predicates are specific to the domain under consideration. Alternatively, holdsAt may be defined in terms of holdsFor:

holdsAt(F = V, T ) ← holdsFor(F = V, I), (T s , T e ) ∈ I, T s ≤ T < T e (3)
For any fluent F , holdsAt(F = V, T ) if and only if time-point T belongs to one of the maximal intervals of I such that holdsFor(F = V, I). Intervals (T s , T e ) in the presented EC representation correspond to [T s , T e ). Quite elaborate implementations of holdsFor have been proposed in the literature. In the following section we sketch an implementation of holdsFor. For alternative implementations the interested reader is referred to [START_REF] Artikis | A logic programming approach to activity recognition[END_REF]Cervesato and Montanari 2000).

To illustrate the use of EC for event recognition, below we present definitions of CTM HLE concerning vehicle (bus/tram) punctuality:

happensAt(punctual (Id , VehicleType), DT ) ← happensAt(stop enter (Id , VehicleType, StopId , scheduled ), AT ), happensAt(stop leave(Id , VehicleType, StopId , scheduled ), DT ), 1 ≤ DT -AT ≤ 2000 (4)
happensAt(non punctual (Id , VehicleType), AT ) ← happensAt(stop enter (Id , VehicleType, , late), AT )

According to the above formalisation, a vehicle is said to be punctual if it enters and leaves a stop at the scheduled time. The LLE 'stop enter' and 'stop leave' must take place within 2000 time-points in order to recognise 'punctual'. A vehicle is said to be non-punctual if it enters a stop later than the scheduled time. (These conditions are not the only ones in which a vehicle is said to be punctual/non-punctual.) All events in the above rules are instantaneous and thus they are represented by means of happensAt.

Punctuality change may be expressed in EC as follows:

initially(punctuality( , ) = punctual) (6) initiatedAt(punctuality(Id , VehicleType) = punctual , T ) ← happensAt(punctual (Id , VehicleType), T ) (7) initiatedAt(punctuality(Id , VehicleType) = non punctual , T ) ← happensAt(non punctual (Id , VehicleType), T ) (8) happensAt(punctuality change(Id , VehicleType, Value), T ) ← holdsFor(punctuality(Id , VehicleType) = Value, I ), (T , ) ∈ I , T = 0 (9)
We defined an auxiliary fluent, punctuality, that records the time-points in which a vehicle is (non-)punctual. The fluent punctuality is defined by rules ( 6)-( 8). Initially, every vehicle is punctual.

Thereafter punctuality is affected by the punctual and non punctual HLE. Rule (9) expresses the definition of the HLE punctuality change. This rule uses the EC built-in implementation of holdsFor to compute the list of the maximal intervals for which a vehicle is continuously (non-)punctual. Punctuality changes at the first time-point of each of these intervals (see the last two lines of rule ( 9)). Note that, depending on the requirements of the user (city transport officials, in the CTM example), punctuality may itself be a HLE, as opposed to an auxiliary construct. In general, a HLE may not necessarily be treated as an EC event. In some cases it is more convenient to treat a HLE as an EC fluent. In the case of a durative HLE Γ, for example, treating Γ as a fluent and using the built-in holdsFor to compute the intervals of Γ, may result in a more succinct representation than treating Γ as an EC event and developing domain-dependent rules for happensFor to compute the intervals of Γ.

Of interest to city transport officials are two HLE concerning driving quality -these are defined as follows:

happensFor represents the list of the maximal intervals during which an event takes place (see Table 3). Note that in the case where an event E has not taken place, we have happensFor(E , []). Similarly, if F = V is never the case, we have holdsFor(F = V , []). intersect all computes the intersection of a list of lists of maximal intervals. For example, intersect all ([[(5, 20), (26, 30)], [(28, 35)]], [(28, 30)]). Similarly, union all computes the union of a list of lists of maximal intervals. For example, union all([[(5, 20), (26, 30)], [], [(28, 35)]], [(5, 20), (26, 35)]). Medium quality driving is recognised when the driving style is uncomfortable, but the vehicle is punctual. Low quality driving is recognised when the driving style is unsafe or the vehicle is non-punctual. punctuality is defined by rules ( 6)-( 8). To simplify the presentation we do not show here the definitions of the uncofmortable driving and unsafe driving HLE (see [START_REF] Artikis | Final version of knowledge base of event definitions and reasoning algorithms for event recognition[END_REF] for an extensive library of CTM HLE definitions formalised in EC). The use of interval manipulation constructs, such as union all and intersect all, often leads to a very concise HLE representation. Cervesato and Montanari (2000) have used interval manipulation constructs in order to define a set of complex event operators in the context of EC. These operators are expressed as follows:

m :: = e (basic event) | m 1 ; D d m 2 (sequence with delay d to D) | m 1 + m 2 (alternative) | m 1 || m 2 (parallelism) | m * (iteration)
The semantics of the above event operators is given in terms of a predicate that computes the interval of a complex event given the intervals of its sub-events. In a similar way, [START_REF] Paschke | ECA-RuleML: An approach combining ECA rules with temporal interval-based KR event/action logics and transactional update logics[END_REF] has formalised the following event operators in the context of EC: sequence, disjunction, mutual exclusivity, conjunction, concurrency, negation, quantification and aperiodicity.

The availability of the full power of logic programming is one of the main attractions of employing EC as the temporal formalism. It allows HLE definitions to include not only complex temporal constraints, but also complex atemporal constraints. For example, it is straightforward to develop in Prolog a predicate computing the distance between two entities.

The cited EC dialects for event recognition are not tied to a particular type of logic programming semantics. In this way a dialect may be directly implemented in various existing rule languages (such as Prova).

Logic programming, not including an EC implementation, has been used frequently for event recognition. A notable example is the work of Shet and colleagues [START_REF] Shet | VidMAP: video monitoring of activity with Prolog[END_REF][START_REF] Shet | Multivalued default logic for identity maintenance in visual surveillance[END_REF]; Shet et al. 2007). A benefit of EC, in comparison to pure Prolog, is that EC has built-in rules for complex temporal representation, such as the ones presented here, which help considerably the development of HLE definitions.

Reasoning

Several implementations of the EC built-in rules have been proposed in the literature. Reasoning in EC is often performed at query-time, that is, the incoming LLE are logged without processing, and reasoning about the LLE log is performed when a query, concerning the recognition of HLE, is submitted. To perform run-time event recognition using query-time reasoning -to recognise, for example, at real-time incidents affecting the smooth operation of public transportation -one would have to repeatedly query EC (say every 5 seconds). If the outcome of query computation (the intervals of the recognised HLE) is not stored, reasoning would be performed on all detected LLE, as opposed to the LLE detected between two consecutive query times. Consequently, recognition time would substantially increase over time. (In retrospective recognition, such as the recognition performed at the end of each day in order to evaluate the performance of public transportation, querying about the intervals of a HLE is performed once, so there is considerably less need to store the outcome of query computation.)

To overcome the above limitation, a cached version of the Event Calculus has been proposed: the socalled Cached Event Calculus (CEC) [START_REF] Chittaro | Efficient temporal reasoning in the cached event calculus[END_REF]. Reasoning in CEC is not performed at query-time, but at update-time: CEC infers and stores all consequences of LLE as soon as they arrive. Query processing, therefore, amounts to retrieving the appropriate HLE intervals from the memory. (Another EC dialect in which reasoning is performed at update-time may be found in [START_REF] Chesani | Commitment tracking via the reactive event calculus[END_REF]). We do not discuss here this dialect because its reasoning efficiency has not been evaluated yet.)

Note that caching does not necessarily imply update-time reasoning. Caching techniques may be implemented for query-time reasoning.

Figure 6 shows the main modules of CEC. Each new LLE is entered into the database using update. updateInit and updateTermin are then called to manage fluents that are initiated and, respectively, terminated by the LLE. A fluent may represent a HLE or it may represent a context variable used in the definition of a HLE. updateInit may call creatingI to create a new maximal interval for a fluent. updateTermin may call breakingI to break a maximal interval of a fluent. The modules propagateAssert and propagateRetract deal with the non-chronological arrival of LLE, that is, the arrival of a LLE that happened (was detected) before some of the already acquired LLE. When a maximal interval (or part of it) of a fluent is retracted, or asserted, as a result of the occurrence of a LLE that arrived in a nonchronological order, the update has to be propagated to the fluents whose validity may rely on such . . .

an interval. The retraction or assertion of an interval [T 1 , T 2 ] in which a fluent has a particular value modifies the context of events occurring at time-points belonging to this interval, and possibly invalidates (or activates) the effects of these events. propagateAssert and propagateRetract may recursively activate the process of creating or breaking maximal intervals, by means of calling creatingI and breakingI . To avoid clutter in Figure 6, however, we do not show the information flow between propagateAssert, propagateRetract and the remaining CEC modules. We will illustrate the way CEC deals with the non-chronological arrival of LLE with the use of a simple example. Assume that we are interested in recognising HLE related to vehicle punctuality (see rules (4)-( 9)) and passenger satisfaction, a partial definition of which is presented below:

According to the above formalisation, passenger satisfaction concerning a vehicle is said to be reducing when passenger density in that vehicle becomes high while the vehicle is non-punctual. Recall that, for any fluent F , holdsAt(F = V, T ) if and only if time-point T belongs to one of the maximal intervals of I such that holdsFor(F = V, I) -see, for example, rule (3). Note that reducing passenger satisfaction, like punctuality, is represented as a fluent. Table 4 shows an example LLE narrative concerning a particular vehicle, and a set of HLE that are recognised given this narrative -more precisely, Table 4 shows the instantaneous punctual and non punctual HLE recognised at each time, the maximal intervals for which a vehicle is said to be nonpunctual, and the durative reducing passenger satisfaction HLE. A maximal interval (T s , inf ) indicates that a fluent holds continuously since T s . Moreover, as mentioned earlier, intervals (T s , T e ) in the presented EC representation correspond to [T s , T e ). Two LLE, in this example, arrive in a non-chronological order: stop enter (b 5 , bus, s 9 , scheduled ) and stop leave(b 5 , bus, s 9 , scheduled ). These LLE happened (were detected) before one of the already acquired LLE: passenger density change(b 5 , bus, high).

Upon the arrival of the first LLE of the narrative displayed in Table 4, CEC recognises that bus b 5 is non-punctual. This is due to the fact that b 5 entered stop s 8 later than the scheduled time. Passenger satisfaction is not affected at this time -the list of the intervals for which passenger satisfaction is reducing remains empty. The arrival of the second LLE does not lead to the recognition of a new HLE. b 5 is still considered non-punctual. The following LLE, passenger density change(b 5 , bus, high), leads to the recognition of reducing passenger satisfaction(b 5 , bus) because, at that time, bus b 5 is considered non-punctual (see rule ( 12)). The next two LLE arrive, as mentioned above, in a non-chronological order. They lead to the recognition of the punctual (b 5 , bus) HLE which is said to take place at time-point 14 (see rule ( 4)). This HLE breaks the interval for which b 5 is considered non-punctual. CEC, therefore, retracts the interval (14 , inf ) for which punctuality(b 5 , bus) = non punctual .

Given that the retraction of the aforementioned fluent interval was due to LLE that arrived in a nonchronological order, CEC has to propagate the retraction to the fluents whose validity relies on this interval -in this example, to the fluent representing the 'passenger satisfaction' HLE (see rule ( 12)). The retraction of the interval (14 , inf ) for which punctuality(b 5 , bus) = non punctual modifies the context of the passenger density change(b 5 , bus, high) LLE that happened at time-point 15 -we now consider b 5 punctual at that time-point. CEC, therefore, invalidates the effects of passenger density change(b 5 , bus, high): it retracts the interval (15 , inf ) for which reducing passenger satisfaction(b 5 , bus) = true.

The complexity of update processing (inferring and storing the consequences of an event) in CEC is measured in terms of accesses to happensAt and holdsFor Prolog facts, where happensAt facts represent the incoming LLE while holdsFor facts represent cached fluent intervals, including HLE intervals. On this basis, the complexity of update processing in CEC, considering a particular fluent, is O(n (L fw +1 )+2 ), where n is the number of initiating/terminating events for the fluent into consideration, and L fw is the maximum number of propagations of fluent interval assertions and retractions -as shown above, such propagations are caused by LLE arriving in a non-chronological order. Note that if L fw = 0 then the complexity of update processing is O(n 2 ). The complexity of query processing (retrieving the cached maximal intervals of a fluent) in CEC is O(n). Details about the complexity analysis of CEC may be found in [START_REF] Chittaro | Efficient temporal reasoning in the cached event calculus[END_REF].

The efficiency of CEC has been reported to be adequate for certain application domains [START_REF] Chittaro | Using a general theory of time and change in patient monitoring: Experiment and evaluation[END_REF]. In practice, where delayed LLE are considered only if the delay does not exceed a certain threshold, the complexity of update processing is considerably less than the worst-case complexity presented above. Moreover, ways to improve the efficiency of CEC have been identified [START_REF] Artikis | Final version of knowledge base of event definitions and reasoning algorithms for event recognition[END_REF]. Note, however, that caching in CEC concerns only HLE represented as fluents, and thus needs to be extended to cater for HLE represented as EC events (such as, for example, medium quality driving -see Section 3.1).

Machine Learning

Since EC event descriptions are typically expressed as logic programs, Inductive Logic Programming (ILP) methods are an obvious candidate for constructing domain-dependent rules representing HLE definitions. As discussed in Section 2.3, ILP can be used to induce hypotheses from examples. For instance, to learn the definition of the HLE punctual , one has to provide positive examples E + and negative examples E -for punctual using the happensAt predicate, and a background knowledge base B including a LLE narrative. The learnt hypotheses will be of the form of rules ( 4) and ( 5). In general, learning hypotheses for predicates for which examples are available (such as happensAt(punctual (Id , VehicleType), T )), that is, 'observation predicate learning' (OPL) [START_REF] Muggleton | Theory completion using inverse entailment[END_REF], may be achieved using ILP techniques as shown in Section 2.3.

Automatically constructing an EC logic program often includes learning hypotheses for predicates for which examples are not available, which implies that induction cannot be directly applied to produce the required hypotheses. Consider, for instance, the case in which we need to learn the definition of the CTM HLE 'reducing passenger satisfaction', we require to represent this HLE as a fluent in terms of initiatedAt (because, say, we expect that such a representation would be succinct), and the available examples for learning this HLE are given only in terms of holdsAt. In such a case, abduction may be combined with induction in order to produce the required hypotheses -a description of abductive logic programming may be found at [START_REF] Kakas | Abductive logic programming[END_REF][START_REF] Denecker | Special issue: abductive logic programming[END_REF][START_REF] Denecker | Abduction in logic programming[END_REF], for example. Abduction may produce ground initiatedAt rules, using the examples expressed by means of holdsAt and the EC built-in rules, such as ( 1) and ( 2), relating initiatedAt and holdsAt. Then, induction may generalise the outcome of abduction.

Various approaches have been proposed in the literature for combining abduction with induction in order to learn a logic program -see [START_REF] Wellner | An abductive-inductive learning framework for logic-based agents[END_REF][START_REF] Moyle | Using theory completion to learn a robot navigation control program[END_REF][START_REF] Tamaddoni-Nezhad | Application of abductive ILP to learning metabolic network inhibition from temporal data[END_REF]) for a few examples. In what follows we will briefly describe the XHAIL system [START_REF] Ray | Nonmonotonic abductive inductive learning[END_REF]) that has been recently developed for this task, and has been used for learning EC programs. The learning technique of XHAIL is based on the construction and generalisation of a preliminary ground hypothesis, called a Kernel Set, that bounds the search space in accordance to user-specified language and search bias. XHAIL follows a three-stage process. First, abduction is used to compute the head atoms of a Kernel Set. Second, deduction is used to compute the body literals of the Kernel Set. Third, induction is used to generalise the clauses of the Kernel Set.

Each stage of XHAIL, including the inductive stage, is specified as an executable abductive logic programming task -see [START_REF] Ray | Nonmonotonic abductive inductive learning[END_REF] for details. In this way, all stages may be implemented using an abductive logic programming reasoner, such as the A-system8 , or a high-performance answer set solver, such as clasp9 .

We will illustrate the use of XHAIL by showing how it may be used to learn the definition of the 'reducing passenger satisfaction' HLE. As mentioned above, we require to represent this HLE as a fluent in terms of initiatedAt, while the available examples are given in terms of holdsAt. The input to XHAIL for learning this HLE definition includes:

• A background knowledge base B containing the built-in EC rules and a LLE narrative.

• A set M of mode declarations (the language bias). Mode declarations in XHAIL are specified as in typical ILP systems -see Section 2.3. Recall that a set M of mode declarations defines a language L(M ) within which the learnt hypotheses H must fall, that is, H ⊆ L(M ). We use M + to denote the set of head declarations in M and M -to denote the set of body declarations. In the presented scenario, the head declaration in M + states that the head of learnt clause must be an initiatedAt predicate concerning the 'reducing passenger satisfaction' fluent, while the body declarations in M - state that a body literal of a learnt clause may be a predicate representing any LLE, that is, we have no prior knowledge concerning what affects passenger satisfaction, or a predicate representing any fluent expressing in-vehicle conditions such as noise level, temperature and passenger density.

• A set of positive and negative examples E such as:

holdsAt(reducing passenger satisfaction(b 1 , bus) = true, 8 ) not holdsAt(reducing passenger satisfaction(b 1 , bus) = true, 16 )

The first phase of XHAIL, that is, the abductive phase, computes ground initiatedAt atoms. The computed atoms ∆ = n i = 1 α i are such that E is entailed by B and ∆, and each α i is a well-typed ground instance of a clause in L(M + ). This is a standard abductive task. Below is an atom produced by the abductive phase of XHAIL:

initiatedAt(reducing passenger satisfaction(b 1 , bus) = true, 8 )
Recall that initiatedAt and holdsAt are related by the EC built-in rules (see rule (1), for instance). Each abduced initiatedAt atom constitutes the head of a clause of the Kernel Set.

The second phase of XHAIL, that is, the deductive phase, computes a ground program

K = n i = 1 α i ← δ 1 i , . . . , δ mi i
such that every δ j i , where 1≤i≤n and 1≤j≤m i , is entailed by B and ∆, and each clause in K is a well-typed ground instance of a clause in L(M ). n is the number of atoms abduced in the previous phase of XHAIL, while each m i is less or equal to the number of body declarations. In other words, the second phase of XHAIL adds body literals to the clauses of the Kernel Set K. To compute K, each head atom computed in the previous phase is saturated with body literals using a non-monotonic generalisation of the Progol level saturation method [START_REF] Muggleton | Inverse entailment and progol[END_REF]. To achieve this, the abductive system is made to behave as a deductive query answering procedure by setting an empty set of abducibles. Briefly, the atoms δ j i of each clause k i of the Kernel Set are computed by a deductive procedure that finds the successful ground instances of the queries obtained by substituting a set of input terms into the + placemarkers of the body declaration schemas. Below is a clause of the produced Kernel Set K: A temperature increase -more precisely, when the temperature becomes very warm -initiates a period of time for which passenger satisfaction is reducing, provided that the vehicle in question is non-punctual and the noise level inside the vehicle is high. Note that this clause concerns a particular time-point (8 ).

The third phase of XHAIL, that is, the inductive phase, computes a theory H that subsumes K and entails E with respect to B. Briefly, the Kernel Set K is translated into K ′ in which all input and output terms (recall that these are defined by means of mode declarations) are replaced by variables, and then as many literals and clauses as possible are deleted from K ′ while ensuring coverage of the examples in E. The resulting set of clauses constitutes H. Below is a clause of the computed theory H:

In-vehicle noise level is not included in the above clause because it did not prove to be a determining factor of the reduction of passenger satisfaction. The above clause complements rule (12) that was presented in Section 3.2. The proposed combination of abduction and induction has been applied to small, in terms of event narrative size, and noise-free applications [START_REF] Ray | Nonmonotonic abductive inductive learning[END_REF]. As mentioned in Section 2.3, the examples (annotated HLE) used to induce a hypothesis, as well as the event narrative (annotated or detected LLE or HLE) that is part of the background knowledge base, may be noisy. Next we present an approach that has been specifically developed for learning and reasoning about hypotheses in noisy environments.

Event recognition systems often have to deal with the following issues [START_REF] Shet | Bilattice-based logical reasoning for human detection[END_REF][START_REF] Artikis | A logic programming approach to activity recognition[END_REF]: incomplete LLE streams, erroneous LLE detection, inconsistent LLE and HLE annotation, and a limited dictionary of LLE and context variables. These issues may compromise the quality of the (automatically or manually) constructed HLE definitions, as well as HLE recognition accuracy. In this section we review Markov Logic Networks that consider uncertainty in representation, reasoning and machine learning, and, consequently, address, to a certain extent, the aforementioned issues.

Representation

Probabilistic graphical models are often used in the literature to handle uncertainty. Sequential graphical models, such as Dynamic Bayesian Networks [START_REF] Murphy | Dynamic bayesian networks: representation, inference and learning[END_REF] and Hidden Markov Models [START_REF] Rabiner | A tutorial on hidden Markov models[END_REF] are useful for modelling HLE definitions representing event sequences. Reasoning with such models is usually performed through maximum likelihood estimation on the LLE narratives. For largescale applications with complex events that involve long-range dependencies and hierarchical structure, sequential models have been extended to more complex variants [START_REF] Hongeng | Large-scale event detection using semi-hidden markov models[END_REF][START_REF] Nguyen | Learning and detecting activities from movement trajectories using the hierarchical hidden Markov model[END_REF][START_REF] Kersting | Logical hidden markov models[END_REF]). However, these models use a restricted temporal representation and most of them allow only for sequential relations between events. Moreover, the majority of them cannot naturally incorporate domain-specific knowledge.

On the other hand, logic-based formalisms, such as first-order logic, can compactly represent complex event relations, but do not naturally handle uncertainty. Assume a first-order logic knowledge base expressing HLE definitions. A possible world assigns a truth value to each possible ground atom. Each formula in the knowledge base imposes constraints on the set of possible worlds. A missed LLE or an erroneous LLE detection, violating even a single formula of the knowledge base, may result in a zeroprobability world.

The research communities of Statistical Relational Learning and Probabilistic Inductive Logic Programming have proposed a variety of methods that combine concepts from first-order logic and probabilistic models [START_REF] Getoor | Introduction to statistical relational learning[END_REF][START_REF] De Raedt | Probabilistic inductive logic programming[END_REF][START_REF] De Salvo Braz | A survey of first-order probabilistic models[END_REF]). This approach is adopted by Knowledge-Based Model Construction (KBMC) methods, where a logic-based language is used to generate a propositional graphical model on which probabilistic inference is applied [START_REF] De Salvo Braz | A survey of first-order probabilistic models[END_REF]. Markov Logic Networks (MLN) [START_REF] Richardson | Markov logic networks[END_REF][START_REF] Domingos | Markov Logic: An Interface Layer for Artificial Intelligence[END_REF]) is a recent and rapidly evolving KBMC framework, which provides a variety of reasoning and learning algorithms10 , and has recently been used for event recognition [START_REF] Biswas | Recognizing activities with multiple cues[END_REF][START_REF] Tran | Event modeling and recognition using markov logic networks[END_REF][START_REF] Kembhavi | Why did the person cross the road (there)? scene understanding using probabilistic logic models and common sense reasoning[END_REF][START_REF] Xu | Learning logic rules for scene interpretation based on markov logic networks[END_REF][START_REF] Helaoui | A statistical-relational activity recognition framework for ambient assisted living systems[END_REF][START_REF] Wu | User-centric environment discovery with camera networks in smart homes[END_REF][START_REF] Wu | Recognizing objects in smart homes based on human interaction[END_REF]. The main concept behind MLN is that the probability of a world increases as the number of formulas it violates decreases. Therefore, a world violating formulas becomes less probable, but not impossible as in first-order logic. Syntactically, each formula F i in Markov logic is represented in first-order logic and it is associated with a weight w i . The higher the value of the weight, the stronger the constraint represented by F i . Semantically, a set of Markov logic formulas (F i , w i ) represents a probability distribution over possible worlds.

Consider, for example, the formulas below, expressing a simplified version of the definition of the 'uncomfortable driving' CTM HLE:

abrupt movement(Id , VehicleType, T ) ← abrupt acceleration(Id , VehicleType, T ) ∨ abrupt deceleration(Id , VehicleType, T ) ∨ sharp turn(Id , VehicleType, T ) ( 14)

uncomfortable driving(Id , VehicleType, T 2 ) ← approach intersection(Id , VehicleType, T 1 ) ∧ abrupt movement(Id , VehicleType, T 2 ) ∧ before(T 1 , T 2 ) (15)
Variables, starting with upper-case letters, are universally quantified unless otherwise indicated. Predicates and constants start with a lower-case letter. The definition of uncomfortable driving is simplified here, in order to facilitate the presentation of reasoning techniques in the following section. According to the above formulas, uncomfortable driving is defined in terms of an auxiliary construct, abrupt movement, which is in turn defined in terms of the abrupt acceleration, abrupt deceleration and sharp turn LLE. before is a simple predicate comparing two time-points. Formulas ( 14) and ( 15) are associated with real-valued positive weights. MLN facilitate a mixture of soft constraints and hard constraints in a HLE knowledge base, where hard constraints correspond to formulas with infinite weight values. Hard constraints can be used to capture domain-specific knowledge or facts. For example, a bus is driven only by one driver at a time. Soft constraints, on the other hand, can be used to capture imperfect logical statements and their weights provide their confidence value. Strong weights are given to formulas that are almost always true. For instance, we may assign a strong weight to formula (15), as it is true most of the time. Respectively, weak weights may be assigned to formulas that describe exceptions. For example, we may assign a weak weight to the formula stating that 'unsafe driving' is recognised when we have 'abrupt movement', as normally a 'very abrupt movement' is needed for the recognition of 'unsafe driving'.

Reasoning

A MLN L is a template that produces a ground Markov network M L,C by grounding all its formulas F , using a finite set of constants C = c 1 , ...c |C| . More precisely, all formulas are translated into clausal form, where the weight of each formula is equally divided among its clauses, and then the produced clauses are grounded. For different sets of constants, the same MLN L will produce different ground Markov networks, but all will have certain regularities in structure and parameters -for example, all groundings of a clause will have the same weight. Each node in a M L,C is represented by a Boolean variable and corresponds to a possible grounding of a predicate that appears in L. Each subset of ground predicates, appearing in the same ground clause, are connected to each other and form a clique in M L,C . Each clique is associated with the corresponding weight w i of a clause and a Boolean feature. The value of the feature is 1 when the ground clause is true, otherwise it is 0.

A ground Markov network M L,C , therefore, comprises nodes that correspond to a set X of random variables (ground predicates). A state x ∈ X of M L,C represents a possible world, as it assigns truth values to all random variables in X. A probability distribution over states is specified by the ground Markov network M L,C , and represented as follows:

P (X = x) = 1 Z exp |Fy| i w i n i (x) (16)
F y ⊆ F is the set of clauses, w i is the weight of the i -th clause, n i (x) is the number of true groundings of the i -th clause in x, and Z is the partition function used for normalisation, that is, Z = x∈X exp(

|Fy| i w i n i (x))
, where X is the set of all possible states. We will illustrate the process of producing a ground Markov network and computing the probability of a state of such a network using the HLE definition expressed by formulas ( 14) and ( 15). These formulas are first translated into clausal form:

1 3 w 1 ¬abrupt acceleration(Id , VehicleType, T ) ∨ abrupt movement(Id , VehicleType, T ) (17) 1 3 w 1 ¬abrupt deceleration(Id , VehicleType, T ) ∨ abrupt movement(Id , VehicleType, T ) (18) 1 3 w 1 ¬sharp turn(Id , VehicleType, T ) ∨ abrupt movement(Id , VehicleType, T ) (19)
w 2 ¬approach intersection(Id , VehicleType, T 1 ) ∨ ¬abrupt movement(Id , VehicleType, T 2 ) ∨ ¬before(T 1 , T 2 ) ∨ uncomfortable driving(Id , VehicleType, T 2 ) ( 20
)
w 1 is the weight of formula ( 14)w 1 is equally divided among the three clauses of this formula -while w 2 is the weight of formula (15). In event recognition, the detected LLE provide the constants C that are necessary for producing ground Markov networks expressing a knowledge base of HLE definitions -see Figure 7. Consider, for example, a narrative of LLE about tram tr 0 taking place at time-points 100 and 101 . The constants involved in this narrativetr 0 , tram, 100 , 101 -define the domain of the corresponding variables -Id , VehicleType, T , T 1 , T 2 . If more LLE were included in the input narrative then the variable domains would have been extended. The grounding procedure produces, in this example, 16 ground predicates and 10 ground clauses. For example, clause ( 17) is grounded as follows:

1 3 w 1 ¬abrupt acceleration(tr 0 , tram, 100 ) ∨ abrupt movement(tr 0 , tram, 100 ) (17a)

The resulting ground Markov network is shown in Figure 8. Predicates appearing in the same ground clause are connected to each other in the network and form a clique. Consider, for instance, the clique created by ground clause (17a) consisting of abrupt acceleration(tr 0 , tram, 100 ) and abrupt movement(tr 0 , tram, 100 ). The clique is associated with the weight of the corresponding clause, that is, 1 3 w 1 , and a Boolean feature. In a state where abrupt movement(tr 0 , tram, 100 ) is true, the grounding (17a) of clause ( 17) is satisfied and therefore the value of the feature is 1.

We will illustrate how the probability of each state of a ground Markov network is computed by calculating the probability of two possible states, x 1 and x 2 , of the network shown in Figure 8. Assume that both x 1 and x 2 assign the same truth values to all predicates except uncomfortable driving(tr 0 , tram, 101 ). More precisely, in both states approach intersection(tr 0 , tram, 100 ), abrupt acceleration(tr 0 , tram, 101 ), abrupt movement(tr 0 , tram, 101 ) and before(100 , 101 ) are true. All the other ground predicates are false, except uncomfortable driving(tr 0 , tram, 101 ) being true in x 1 and false in x 2 . In this example, the weights w 1 and w 2 of formulas ( 14) and ( 15) are positive real numbers. The number of satisfied groundings of clauses ( 17), ( 18) and ( 19) is the same in both x 1 and x 2 , as the assignment of truth values to the predicates involved is the same. The number of satisfied groundings of clause (20), however, differs between x 1 and x 2 , because the truth assignment of uncomfortable driving(tr 0 , tram, 101 ) is different. As a result, in state x 1 all ground clauses of (20) are satisfied, but in state x 2 ground clause (20b) is not satisfied. Using equation ( 16) we compute the following:

P (X = x 1 ) = 1 Z exp( 1 3 w 1 • 2 + 1 3 w 1 • 2 + 1 3 w 1 • 2 + w 2 • 4) = 1 Z e 2w1+4w2 P (X = x 2 ) = 1 Z exp( 1 3 w 1 • 2 + 1 3 w 1 • 2 + 1 3 w 1 • 2 + w 2 • 3) = 1 Z e 2w1+3w2
According to the above results, a state (x 1 ) in which the 'uncomfortable driving' HLE and its subevents have all been recognised is more probable than a state (x 2 ) in which the subevents of 'uncomfortable driving' have been recognised while this HLE does not hold.

Event recognition in MLN involves querying a ground Markov network about HLE. The set X of random variables of a ground network can be partitioned as X = Q ∪ E ∪ H , where Q is the set of 'query variables', E is the set of 'evidence variables', and H is the set of the remaining variables with unknown value -also known as 'hidden variables'. In event recognition, query variables represent the HLE of interest, evidence variables represent the detected LLE, while hidden variables represent auxiliary constructs of a HLE definition. Event recognition queries require conditional inference, that is, computing the probability that a query variable holds given some evidence. For the computation of conditional probabilities a variety of exact and approximate probabilistic inference methods exist in the literature.

Given a MLN and some evidence E = e, a conditional query is specified as follows:

P (Q | E = e, H) = P (Q, E = e, H) P (E = e, H) (21)
Q are the query variables and H are the hidden variables. The numerator and denominator of this equation may be computed using equation ( 16). We may be interested in finding out, for instance, the trams that are driven in an uncomfortable manner, given a LLE narrative. Given equation ( 21), we may compute the probability of each grounding of uncomfortable driving(Id , VehicleType, T ). Complete grounding of MLN, even for simple HLE knowledge bases, results in complex and large networks. For this reason, only the minimal required network is constructed to answer a conditional query. In particular, query and evidence variables are used to separate the network into regions, allowing some variables to be removed from the network, as they cannot influence reasoning. For example, given the Markov network shown in Figure 8, we may be interested only in the HLE uncomfortable driving(tr 0 , tram, 101 ). The truth values of ground before predicates are trivially known. Moreover, the truth values of LLE are given as evidence -see Figure 9(a). The nodes for the ground predicates abrupt movement(tr 0 , tram, 100 ), uncomfortable driving(tr 0 , tram, 100 ), sharp turn(tr 0 , tram, 100 ), abrupt deceleration(tr 0 , tram, 100 ), abrupt acceleration(tr 0 , tram, 100 ), before(100 , 100 ) and before(101 , 100 ) can be omitted from the Markov network, as they cannot influence the reasoning process concerning the HLE uncomfortable driving(tr 0 , tram, 101 ). Therefore, the complete Markov network, shown in Figure 9(a), will be reduced into the network shown in Figure 9(b).

Further efficiency can be gained by employing (a) lazy inference methods that ground predicates as and when needed [START_REF] Singla | Memory-efficient inference in relational domains[END_REF]Domingos and Lowd 2009, Section 3.3), or (b) lifted inference methods which can answer queries without grounding the entire network [START_REF] Singla | Lifted first-order belief propagation[END_REF]Domingos and Lowd 2009, Section 3.4).

Sensors may detect LLE with certainty or with a degree of confidence. In the former case, the LLE are simple Boolean variables that are given directly to the MLN as evidence. In the latter case, the detected LLE are usually added to the MLN knowledge base as clauses having weights proportional to their detection probability [START_REF] Tran | Event modeling and recognition using markov logic networks[END_REF]. For example, if the LLE sharp turn(tr 0 , tram, 20 ) is detected with some probability P (sharp turn(tr 0 , tram, 20 )), the unit clause sharp turn(tr 0 , tram, 20 ) will be added to the MLN with weight value w = log P (sharp turn(tr 0 , tram, 20 )) 1 -P (sharp turn(tr 0 , tram, 20 ))

The additional clauses, which represent the detected LLE with a degree of confidence, alter the posterior distribution over possible worlds by introducing additional features in the ground Markov Network. In this manner, the detected LLE propagate their degree of confidence to the whole MLN.

Even in a very large state space, the computation of equation ( 21) can be efficiently approximated by sampling methods, such as Markov Chain Monte Carlo (MCMC) algorithms -for example, Gibbs sampling. Markov Chains form graphs of possible states, over which a Monte Carlo simulation takes a random walk and draws a set of sample states from the target distribution. In MCMC, a successive sample state depends only on the current state. In Gibbs sampling, for instance, each sample state is produced by successively changing the truth value assignment of its ground predicates. This re-assignment of truth values is performed efficiently, as the value of each predicate in the ground Markov network depends only on the truth values of its neighbour predicates. The set of neighbouring predicates is called Markov blanket and represents predicates that appear together is some grounding of a clause. For instance, the Markov blanket of abrupt movement(tr 0 , tram, 101 ) in the network shown in Figure 8 is composed of uncomfortable driving(tr 0 , tram, 101 ), before(100 , 101 ), approach intersection(tr 0 , tram, 100 ), sharp turn(tr 0 , tram, 101 ), abrupt acceleration(tr 0 , tram, 101 ), abrupt deceleration(tr 0 , tram, 101 ), approach intersection(tr 0 , tram, 101 ) and before(100 , 101 ). The conditional probability in equation ( 21) can be computed by a MCMC algorithm that rejects all moves to states where E = e does not hold. Therefore, only the variables that belong to Q and H are allowed to change in each sample. In each step, the MCMC algorithm has the tendency to keep samples that represent states with high probability and, therefore, often converges in local maxima. The estimated probability of the query variables, that is, the HLE of interest, is the fraction of samples in which those variables are true. The more samples are generated, the more accurate this estimation becomes.

Due to the combination of logic with probabilistic models, inference in MLN must handle both deterministic and probabilistic dependencies. Deterministic or near-deterministic dependencies are formed from formulas with infinite and strong weights respectively. Being a purely statistical method, MCMC can only handle probabilistic dependencies. In the presence of deterministic dependencies, two important properties of Markov Chains, ergodicity and detailed balance, are violated and the sampling algorithms give poor results [START_REF] Poon | Sound and efficient inference with probabilistic and deterministic dependencies[END_REF]. Ergodicity is satisfied if all states are aperiodically reachable from each other, while detailed balance is satisfied if the probability of moving from state x i to state x j is the same as the probability of moving from x j to x i . Ergodicity and detailed balance are violated in the presence of deterministic dependencies because these dependencies create isolated regions in the state space by introducing zero-probability (impossible) states. Even near-deterministic dependencies create regions that are difficult to cross, that is, contain states with near zero-probability. As a result, typical MCMC methods, such as Gibbs sampling, get trapped in local regions. Thus, they are unsound for deterministic dependencies and they find it difficult to converge in the presence of near-deterministic ones.

To overcome these issues and deal with both deterministic and probabilistic dependencies, MLN use the MC-SAT algorithm [START_REF] Poon | Sound and efficient inference with probabilistic and deterministic dependencies[END_REF][START_REF] Domingos | Markov Logic: An Interface Layer for Artificial Intelligence[END_REF], Section 3.2), which is a MCMC method that combines satisfiability testing with slice-sampling [START_REF] Damlen | Gibbs sampling for Bayesian non-conjugate and hierarchical models by using auxiliary variables[END_REF]. Initially, a satisfiability solver is used to find those assignments that satisfy all hard-constrained clauses (that is, clauses with infinite weights). At each subsequent sampling step, MC-SAT chooses from the set of ground clauses satisfied by the current state the clauses that must be satisfied at the next step. Each clause is chosen with probability proportional to its weight value. Clauses with infinite or strong weights, that represent, respectively, deterministic and near-deterministic dependencies, will always be chosen with, respectively, absolute certainty and high probability. Then, instead of taking a sample from the space of all possible states, slice-sampling restricts sampling to the states that satisfy at least all chosen clauses. In this manner, MCMC cannot get trapped to local regions, as satisfiability testing helps to collect samples from all isolated and difficult-to-cross regions.

Machine Learning

Learning a MLN involves estimating the weights of the network and/or the first-order rules forming the network structure, given a set of training data, that is, LLE annotated with HLE. In Section 4.3.1 we present approaches on weight learning while in Section 4.3.2 we discuss structure learning.

Weight Learning

Weight learning concerns the estimation of the weights of the clauses that represent a HLE knowledge base -recall that the first-order rules of such a knowledge base are translated into clausal form. Different clauses, derived from the same rule, may be assigned different weights. For example, it may be estimated that the weights of the clauses derived from rule (14) are different: of how well the probabilistic model (MLN) fits the training data. In particular, weights can be learned by either generative or discriminative estimation [START_REF] Singla | Discriminative training of Markov logic networks[END_REF][START_REF] Lowd | Efficient weight learning for Markov logic networks[END_REF][START_REF] Huynh | Discriminative structure and parameter learning for Markov logic networks[END_REF]Domingos and Lowd 2009, Section 4.1). Generative learning attempts to optimise the joint distribution of all variables in the model. In contrast, discriminative learning attempts to optimise the conditional distribution of a set of outputs, given a set of inputs.

Generative estimation methods search for weights that optimise the likelihood function, given a HLE knowledge base and training data. Learning can be performed by a standard gradient-ascent optimisation algorithm. However, it has been shown that computing the likelihood and its gradient is intractable [START_REF] Richardson | Markov logic networks[END_REF]. For this reason, the optimisation of the pseudo-likelihood function is used instead, which is the product of the probabilities of the ground predicates, conditioned on their neighbours in the network, that is, their Markov blanket. In particular, if x is a state of a ground network and x l is the truth value of the l -th ground predicate X l , the pseudo-likelihood of x, given weights w, is:

log P * w (X = x ) = n l=1 log P w (X l = x l | MB x (X l )) (25)
MB x (X l ) represents the truth values of the ground predicates in the Markov blanket of X l . Thus, computation can be performed very efficiently, even in domains with millions of ground predicates, as it does not require inference over the complete network. The pseudo-likelihood function assumes that each ground predicate's Markov blanket is fully observed, and does not exploit information obtained from longer-range dependencies in the network. In some cases this assumption may lead to poor results. Consider, for example, formulas ( 14) and (15) expressing, respectively, abrupt movement and uncomfortable driving, and a training dataset including a LLE narrative annotated only for uncomfortable driving, that is, there is no annotation for abrupt movement. Figure 10 displays the resulting ground Markov network. As mentioned in Section 4.2, the Markov blanket of abrupt movement includes the sharp turn, abrupt acceleration and abrupt deceleration LLE. The Markov blanket of uncomfortable driving includes abrupt movement. In this case, pseudo-likelihood may give poor results with respect to the uncomfortable driving HLE. This is due to the fact that it will only use information from the Markov blanket of this HLE, making an assumption about the absent annotation of abrupt movement -usually a closed-world assumption. In other words, it will not exploit the information provided by the abrupt acceleration, abrupt deceleration and sharp turn LLE of the training dataset.

One way to address the aforementioned issue is to treat absent annotations as missing information and employ the expectation maximisation algorithm of [START_REF] Dempster | Maximum likelihood from incomplete data via the EM algorithm[END_REF] in order to learn from incomplete data [START_REF] Poon | Joint unsupervised coreference resolution with Markov Logic[END_REF]Domingos and Lowd 2009, Section 4.3).

In event recognition, we know a-priori which variables form the evidence (LLE) and which ones concern queries (HLE). In the usual case, where we aim to recognise the latter given the former, it is preferable to learn the weights discriminatively by maximising the conditional likelihood function. In particular, if we partition the variables of the domain into a set of evidence variables E and a set of query variables Q, then the conditional likelihood function is defined as follows: log P (Q = q | E = e) = i w i n i (e, y) -log Z e (26)

Z e normalises over all states consistent with the evidence e, and n i (e, y) is the number of true groundings of the i -th clause in the training dataset. In contrast to Q and E, the state of a hidden variable, such as abrupt movement, is unknown as, in most cases, the state of such variables is not available in the training dataset. In the presence of hidden variables, therefore, the conditional likelihood must be computed by marginalising over the hidden variables. It has been shown that learning weights discriminatively can lead to higher predictive accuracy than generative learning [START_REF] Singla | Discriminative training of Markov logic networks[END_REF]. This is partly due to the fact that, in contrast to the pseudo-likelihood function, conditional likelihood can exploit information from longer-range dependencies. Similar to the likelihood function, conditional likelihood requires inference. However, there is one key difference: conditioning on the evidence in a Markov network reduces significantly the number of likely states. Therefore, inference takes place on a simpler model and the computational requirements are reduced. Weights in MLN are estimated using either first-order or second-order optimisation methods. First-order methods, for example, perform gradient ascent optimisation in order to maximise an evaluation function, such as the conditional likelihood function (26). Weights may be initialised to zero, they may be given random values, or they may be given values according to other information concerning the application under consideration. Then, weights are iteratively updated according to the following equation:

w t+1 = w t + ηg (27)
t indicates the current iteration of the optimisation process, w t is a vector that contains weight values of the current iteration for all clauses in the knowlege base, while w t+1 is a vector that contains the updated weight values. The constant η expresses the learning rate, defining the extent of weight adjustment in each iteration. The vector g represents the gradient. This is composed of the partial derivatives of function ( 26) with respect to the corresponding clause weights. The value of a derivative defines the direction and the magnitude of a weight update. The computation of the gradient requires inference, which can be efficiently approximated using MCMC methods, as discussed in Section 4.2. By iteratively adjusting the weights using equation ( 27), the fit of the model to the HLE in the dataset is optimised. Assume, for example, that in a given training dataset the abrupt acceleration LLE is rarely associated with the occurrence of the HLE uncomfortable driving. On the other hand, the abrupt deceleration and sharp turn LLE are closely associated with the HLE uncomfortable driving. In this case, weight learning will assign a low weight value to clause (22) and high weight values to clauses (23) and (24).

Structure Learning

In addition to weight learning, the structure of a MLN can be learned from training data. In principle, the structure of a MLN can be learned in two stages, using any ILP method, as presented in Section 2.3, and then performing weight learning. However, separating the two learning tasks in this way may lead to suboptimal results, as the first optimisation step (ILP) needs to make assumptions about the weight values, which have not been optimised yet. Better results can be obtained by combining structure learning with weight learning in a single stage.

A variety of structure learning methods have been proposed for MLN. In brief, these methods can be classified into top-down and bottom-up methods. Top-down structure learning [START_REF] Kok | Learning the structure of Markov logic networks[END_REF]Domingos and Lowd 2009, Section 4.2) starts from an empty or existing MLN and iteratively constructs clauses by adding or revising a single predicate at a time, using typical ILP operations and a search procedure. However, as the structure of a MLN may involve complex HLE definitions, the space of potential top-down refinements may become intractable. For this reason, bottom-up structure learning can be used instead, starting from training data and searching for more general hypotheses [START_REF] Mihalkova | Bottom-up learning of Markov logic network structure[END_REF][START_REF] Kok | Learning Markov logic network structure via hypergraph lifting[END_REF][START_REF] Kok | Learning markov logic networks using structural motifs[END_REF]Domingos and Lowd 2009, Section 4.2). This approach usually leads to a more specialised model, following a search through a manageable set of generalisations.

Summary and Open Issues

We presented three representative logic-based approaches to event recognition. All approaches assume as input a stream of time-stamped low-level events (LLE) -a LLE is created as a result of applying a computational derivation process to some other event. Using such input, event recognition systems identify high-level events (HLE) of interest, that is, collections of events that satisfy some pattern. We illustrated the use of the three reviewed approaches drawing examples from the domain of city transport management.

Being based on logic, all three approaches benefit from a formal and declarative semantics, a variety of inference mechanisms, and methods for learning a knowledge base of HLE definitions from data. As a result, compared to procedural methods, logic-based ones facilitate efficient development and management of HLE definitions, which are clearly separated from the generic inference mechanism. Moreover, compared to methods exhibiting informal semantics, logic-based approaches support validation and traceability of results. At the same time, recent logic-based methods appear to be sufficiently mature and scalable to be used in industrial applications.

The presented Chronicle Recognition System (CRS) has been specially developed for event recognition and is the choice of preference for efficient, purely temporal recognition. CRS was developed with the aim to support only temporal reasoning and thus a line of future work concerns its extension with atemporal reasoning. The developers of CRS are currently making it open-source (C. Dousson, personal communication), thus facilitating extensions of its reasoning engine.

The Event Calculus (EC) provides a more generic and expressive representation of HLE definitions, taking advantage of the full power of logic programming on which it is based. Thus, EC supports complex temporal as well as atemporal representation and reasoning. A line of further work concerns the optimisation of the reasoning of EC for run-time event recognition. Caching techniques, in particular, should be investigated, supporting all types of HLE representation.

Markov Logic Networks (MLN) combine the strengths of logical and probabilistic inference. Consequently, they may address, to a certain extent, the issues of incomplete LLE streams, erroneous LLE detection, inconsistent LLE and HLE annotation, and limited dictionary of LLE and context variables. This is in contrast to CRS and EC that do not consider uncertainty in representation and reasoning. MLN also offer a very expressive framework for HLE definition representation, as the full power of firstorder logic is available. The use of MLN for event recognition, however, has been limited so far and there are many issues that need to be resolved still, such as the incorporation and use of numerical temporal constraints in MLN inference.

Finally, a number of challenging issues remain open in learning HLE definitions. Examples of such issues are the use of abduction to handle partial supervision in large datasets that is commonly available for event recognition, and the simultaneous optimisation of numerical parameters -for example, weights and temporal constraints -and the logical structure of the knowledge base expressing HLE definitions.

Fig. 1 :

 1 Fig. 1: Event Recognition for City Transport Management.

Fig. 2 :

 2 Fig. 2: Temporal Constraint Network.

  Fig. 3: HLE Instance Recognition.

Fig. 4 :

 4 Fig. 4: HLE Instance Management.

  Fig. 5: Version Space.

  ; Paschke 2005; Paschke 2006; Paschke et al. 2007; Paschke and Bichler 2008; Teymourian and Paschke 2009; Artikis, Kukurikos et al. 2011; Artikis, Sergot and Paliouras 2010).

Fig. 6 :

 6 Fig. 6: The Cached Event Calculus.

  initiatedAt(reducing passenger satisfaction(Id , VehicleType) = true, T ) ← happensAt(passenger density change(Id , VehicleType, high), T ), holdsAt(punctuality(Id , VehicleType) = non punctual , T )

  initiatedAt(reducing passenger satisfaction(b 1 , bus) = true, 8 ) ← happensAt(temperature change(b 1 , bus, very warm), 8 ), holdsAt(punctuality(b 1 , bus) = non punctual ), 8 ), holdsAt(noise level (b 1 , bus) = high), 8 )

  initiatedAt(reducing passenger satisfaction(Id , VehicleType) = true, T ) ← happensAt(temperature change(Id , VehicleType, very warm), T ), holdsAt(punctuality(Id , VehicleType) = non punctual ), T )

  Fig. 7: Ground Markov Network Construction for Event Recognition.

Fig. 9 :

 9 Fig. 9: (a) Complete Ground Markov Network. (b) Ground Markov Network Reduced for Event Recognition. Nodes with a thick line represent query variables, shaded nodes represent variables with known truth values, and nodes with a dashed line represent variables which can be safely removed.

wFig. 10 :

 10 Fig. 10: Ground Markov Network Produced from Partially Annotated Dataset. The shaded nodes represent predicates with known truth values as described in the annotated dataset.

Table 2 :

 2 Event Recognition in CRS.

	Input LLE	Output HLE
	event(approach intersection[b5, bus], 5)
	event(abrupt deceleration[b5, bus], 7)
	event(sharp turn[b5, bus], 8)
	event(stop enter[b5, bus, s8, scheduled], 15)
	event(stop leave[b5, bus, s8, late], 17)
	event(abrupt acceleration[b5, bus], 19)
	event(approach intersection[b5, bus], 36)
	event(abrupt deceleration[b5, bus], 38)
	event(sharp turn[b5, bus], 38)
	event(abrupt acceleration[b5, bus], 39)	event(uncomfortable driving[b5, bus], 39)
	event(abrupt acceleration[b5, bus], 42)	event(uncomfortable driving[b5, bus], 42)
	event(abrupt acceleration[b5, bus], 55)
	...

  To learn a hypothesis H concerning uncomfortable driving, a set of positive examples E + and a set of negative examples E -are given: Using the background knowledge B, various types of bias, integrity constraints, positive examples E +

	% E+
	uncomfortable_driving(pos1)
	...
	% E-
	uncomfortable_driving(neg1)
	...

Table 3 :

 3 Main Predicates of the Event Calculus.

	Predicate	Meaning
	happensAt(E , T )	Event E is occurring at time T
	happensFor(E , I )	I is the list of the maximal intervals during which event E takes place
	initially

  happensFor(medium quality driving(Id , VehicleType), MQDI ) ← happensFor(uncomfortable driving(Id , VehicleType), UCI ), holdsFor(punctuality(Id , VehicleType) = punctual , PunctualI ), intersect all([UCI , PunctualI ], MQDI )

	(10)
	happensFor(low quality driving(Id , VehicleType), LQDI ) ←
	happensFor(unsafe driving(Id , VehicleType), USI ),

holdsFor(punctuality(Id , VehicleType) = non punctual , NPI ), union all([USI , NPI ], LQDI )

Table 4 :

 4 Event Recognition in the Cached Event Calculus.

	Input LLE	Output HLE
	happensAt(stop enter (b5 , bus, s8 , late), 5 )	happensAt(non punctual (b5 , bus), 5 )
		holdsFor(punctuality(b5 , bus) =
		non punctual , [(5 , inf )])
		holdsFor(reducing passenger satisfaction(b5 , bus) =
		true, [])
	happensAt(stop leave(b5 , bus, s8 , late), 12 )	holdsFor(punctuality(b5 , bus) =
		non punctual , [(5 , inf )])
		holdsFor(reducing passenger satisfaction(b5 , bus) =
		true, [])

happensAt(passenger density change(b5 , bus, high), 15 ) holdsFor(punctuality(b5 , bus) = non punctual , [(5 , inf )]) holdsFor(reducing passenger satisfaction(b5 , bus) = true, [(15 , inf )]) happensAt(stop enter (b5 , bus, s9 , scheduled ), 13 ) holdsFor(punctuality(b5 , bus) = non punctual , [(5 , inf )]) holdsFor(reducing passenger satisfaction(b5 , bus) = true, [(15 , inf )]) happensAt(stop leave(b5 , bus, s9 , scheduled ), 14 ) happensAt(punctual (b5 , bus), 14 ) holdsFor(punctuality(b5 , bus) = non punctual , [(5 , 14 )]) holdsFor(reducing passenger satisfaction(b5 , bus) = true, [])

  ¬approach intersection(tr 0 , tram, 100 ) ∨ ¬abrupt movement(tr 0 , tram, 100 ) ∨ ¬before(100 , 100 ) ∨ uncomfortable driving(tr 0 , tram, 100 ) (20a) w 2 ¬approach intersection(tr 0 , tram, 100 ) ∨ ¬abrupt movement(tr 0 , tram, 101 ) ∨ ¬before(100 , 101 ) ∨ uncomfortable driving(tr 0 , tram, 101 ) (20b) w 2 ¬approach intersection(tr 0 , tram, 101 ) ∨ ¬abrupt movement(tr 0 , tram, 100 ) ∨ ¬before(101 , 100 ) ∨ uncomfortable driving(tr 0 , tram, 100 ) (20c) w 2 ¬approach intersection(tr 0 , tram, 101 ) ∨ ¬abrupt movement(tr 0 , tram, 101 ) ∨ ¬before(101 , 101 ) ∨ uncomfortable driving(tr 0 , tram, 101 )

	1 3 w 1 ¬abrupt acceleration(tr 0 , tram, 101 ) ∨ abrupt movement(tr 0 , tram, 101 )	(17b)
	Similarly, clause (20) is grounded as follows:
	w 2

  In this case, the set of query variables Q includes only uncomfortable driving(Id , VehicleType, T ), the set of detected LLE that forms E may include, among others approach intersection(tr 0 , tram, 100 ) abrupt acceleration(tr 0 , tram, 101 ) sharp turn(tr 24 , tram, 100 ) and the set of hidden variables H includes, among others abrupt movement(tr 0 , tram, 101 ) abrupt movement(tr 24 , tram, 101 )

[START_REF] Pottebaum | Final requirements, use case and scenario specification[END_REF] discuss the relationship between the terms 'low-level event' and 'high-level event' and other terms proposed in the literature, including the glossary of the Event Processing Technical Society(Luckham and Schulte

2008).

http://www.prova.ws

http://www.ict-pronto.org/

http://crs.elibel.tm.fr

http://www.doc.ic.ac.uk/ ~shm/Software/progol5.0/

http://dtai.cs.kuleuven.be/ACE/

http://www.comlab.ox.ac.uk/activities/machinelearning/Aleph/

http://dtai.cs.kuleuven.be/krr/Asystem/asystem.html

http://www.cs.uni-potsdam.de/clasp/

A system implementing MLN reasoning and learning algorithms may be found at http://alchemy.cs.washington. edu/

Acknowledgments

This work has been partially funded by EU, in the context of the PRONTO project (FP7-ICT 231738). Francois Portet is supported by the French national project Sweet-Home (ANR-09-VERS-011).

This paper is a significantly updated and extended version of (Artikis, Paliouras et al. 2010). We would like to thank the reviewers and participants of the Fourth International Conference on Distributed Event-Based Systems, as well as the reviewers of the Knowledge Engineering Review, who gave us useful feedback.

We should also like to thank Christophe Dousson for his suggestions regarding the Chronicle Recognition System. The authors themselves, however, are solely responsible for any misunderstanding about the use of this technology.