A Tensor-Based Formalization of the Event Calculus

1 Introduction

The Event Calculus (EC) is a first-order logical formalism for representing and reasoning about events and their effects [Kowalski and Sergot, 1986]. EC introduces the concept of inertia, which states that the effect of an event holds continuously in time if it is not disrupted by the effects of other events. Our work is motivated by the area of composite event recognition (CER). CER refers to the process of consuming a stream of time-stamped, simple derived events (SDEs), such as events coming from sensors, and identifying the time periods composite events (CE)s of interest - collections of events that satisfy a given pattern - hold. The definition of a CE imposes temporal and, possibly, atemporal constraints on its sub-events (SDEs or other CEs), and may be combined with static background knowledge [Giatrakos et al., 2020].

Logic-based approaches have been applied to CER, since they exhibit a formal, declarative semantics, and at the same time support efficient reasoning [Dousson and Maigat, 2007; Cugola and Margara, 2010; Paschke and Bichler, 2008]. As a CER engine, we adopt a logic programming implementation of the EC [Skarlatidis et al., 2015]. To reduce the complexity, we handle the input stream by means of windowing and employ caching techniques to avoid unnecessary recomputations [Artikis et al., 2015].

Streaming environments, which are typical in CER, are characterized by the high rate and volume of input data.

∗ https://cer.iit.demokritos.gr/publications/papers/2024/tensor-EC.pdf

Therefore, the development of scalable reasoning techniques that can deal with large amounts of data is essential. One promising approach to scalable logical inference is the computation of program models using linear algebraic operations. Algebraic computation has been extensively studied and there are various libraries that provide efficient implementations of algebraic operations. Furthermore, the presence of parallel versions of these processing algorithms, as well as the recent advancements in hardware resources, e.g., GPUs, favor the employment of numerical computation for inference.

Along these lines, Sakama et al. [2021] represent propositional logic programs as matrices or tensors and through multiplication and a non-linear operation, they compute models of programs. An optimization with sparse matrices is introduced in [Nguyen et al., 2022]. Sato [2017a] proposes a technique for obtaining the truth value of first-order logic formulas, where entities, logical connectives and existential quantifiers are formalized in tensor spaces. A procedure for query answering, where a query can be any nested formula, is also presented. This framework is applied to a Datalog program, where the transitive closure of a binary relation is computed by solving a system of linear matrix equations [Sato, 2017b].

We propose tensor-EC, a linear algebraic formulation of EC for CER under perfect model semantics. We map entities and time-points to vectors and events/fluents to matrices/tensors, depending on their arity. EC predicates increase by 1 the order of tensors by incorporating the temporal dimension. Our approach is not limited to square matrices or cubical tensors, since the entities and temporal sets can be of different size. Moreover, we show how to evaluate rules of an EC program, and solve a linear equation that produces the time-points at which a p-ary fluent holds. The resulting tensors, representing fluents, constitute the perfect model of the program. The contributions of this paper are:

• We present a translation of the language of EC in tensor spaces and show how to evaluate rules using algebraic operations.
• We evaluate experimentally tensor-EC on real data from the maritime domain, where we simulate a streaming environment and employ an EC program with many rules.
• We compare tensor-EC against the logic programming implementation of EC, and show that the former improves significantly reasoning time.

2 Background: Event Calculus

In this section, we present the EC dialect we adopt, as well as the logical inference procedure for CER.

2.1 Language

The time model of EC is linear and includes integer timepoints [Skarlatidis et al., 2015]. Variables start with an upper-case letter, while predicates and constants start with a lower-case letter. If fl is a fluent - a property that is allowed to have different values at different points in time - the term fl(X, Y )=v denotes that fluent fl has value v for variables X and Y . Boolean fluents are a special case in which the possible values are true and false. The predicate holdsAt(fl(X, Y )=v, T) is true if fl(X, Y )=v at time-point T. A fluent fl takes at most one value at each time-point. Event occurrences are expressed through the happensAt predicate. happensAt(e(X, Y ), T) denotes that event e occurs at time-point T for variables X and Y . Table 1 summarizes the available predicates of the EC language. EC events express instantaneous SDEs, while fluent-value pairs express SDEs and CEs that persist in time. Without loss of generality, we restrict our attention to events and fluents with arity ≤ 2.

The application-specific part of a formalization in EC is called event description.

Definition 1 (Event description). An event description comprises:

• (a) Ground happensAt and holdsAt predicates. These are the facts and constitute the input (SDEs) to the system.
• (b) Rules with initiatedAt and terminatedAt predicates at the head, expressing the effects of events on fluents. ■

We focus on the task of computing the time-points for which a fluent has a particular value.

Definition 2 (Syntax). initiatedAt rules have the following syntax:

Rule (1) comprises conjunctions, meaning that all body literals should be satisfied in order for the rule to fire. not denotes negation by failure [Clark, 1977], while [not] denotes that 'not' is optional. The variable T , present at the head and all body literals, constrains all literals to be evaluated at the same time-point. We use the term 'positive' to refer to events and fluents that must occur or hold at T , and the term 'negative' for events and fluents that should not occur or hold at T (symbol not). Rules of type (1) are Horn clauses and not restricted in the number of body literals. The only requirement is the first body literal to be a 'positive' happensAt predicate, which can then be followed by a possibly empty set of 'positive/negative' happensAt and holdsAt predicates, denoted by '[[ ]]'. Additionally, rules are 'safe', i.e. every variable that appears in the head of the rule or in any negative literal in the body also appears in at least one positive literal in the body. terminatedAt rules have a similar form. ■

In Def. 2, we restrict the first body literal to be a positive happensAt predicate for complexity reasons. The timepoints at which a fluent holds are usually a lot more than the time-points at which an event occurs. By selecting a positive happensAt predicate as the first body literal of initiatedAt and terminatedAt rules, we reduce complexity.

Example 1. An example fluent definition from the maritime domain, is the following:

Rule-set (2) formalizes the notion of a 'communication gap' [Pitsikalis et al., 2019]. Communication gaps occur when a vessel is not emitting its position, either due to the absence of a nearby receiving station or on purpose. In maritime situational awareness, communication gaps may indicate an intention of hiding (e.g. in cases of illegal fishing). A gap is initiated for aVessel if a gap start has occurred far from ports, and terminated when a gap end event is detected.

The time-points produced by initiatedAt and terminatedAt rules are used to specify the time-points a fluent has a particular value. According to the law of inertia, a fluent holds continuously if it has been initiated and not terminated in the meantime. For example, if fl(X, Y )=v was initiated at Ts and terminated at Tf , with Ts < Tf , it holds for every time-point between Ts and Tf , excluding Ts, i.e., Ts+1, Ts+2, . . . , Tf-1, Tf .

Definition 3 (Inertia axiom). The law of inertia is formalized by the following axiom:

The inertia axiom (3) is a disjunction of two rules. The predicate next(Tprev ,T) present in both rules, denotes that the next time-point after Tprev is time-point T. Notice that the inertia axiom allows reasoning about time-points that are not initiation or termination points.

2.2 Semantics and Operation

The EC language supports non-monotonic reasoning through negation-by-failure [Clark, 1977]. The event description (Def. 1) along with the inertia axiom constitute an EC program P. A common case in CER is the employment of hierarchical CE definitions [Giatrakos et al., 2020]. Hierarchy in an EC program can be achieved through stratification [Apt et al., 1988]. For instance, stratum P0 may comprise all the events and those fluents that do not depend on events or other fluents, serving as input to the system (these are the ground happensAt and holdsAt facts, Def. 1). Fluents of stratum P1 can be defined only in terms of events from P0 while fluents of stratum Ps>1 can be defined in terms of at least one event from P0, one fluent-value of Ps-1, and a possibly empty set of fluent-values from lower strata. The EC dialect that we use expresses locally stratified programs that may not necessarily be stratified [Przymusinski, 1987]. Note that local stratification is a standard assumption in EC [Artikis et al., 2015].

As a CER engine, we adopt a logic programming implementation of EC [Skarlatidis et al., 2015], equipped with optimization and caching techniques that make it suitable for continuous narrative assimilation on data streams [Artikis et al., 2015]. Recognition is performed by processing hierarchical definitions in a bottom-up manner, whereby the ground events and fluents at the bottom of the hierarchy (stratum P0) are processed first and all their time-points are cached. Subsequently, fluents of the next stratum P1 are processed, their time-points are cached, and stratum-by-stratum the top of the hierarchy is reached. This way, when evaluating rules of stratum Ps, the time-points of the fluents and events of the body literals are fetched from the cache, avoiding unnecessary re-computations.

The CER process aims at the computation of all timepoints at which CEs hold. This process takes place at specified query times q1, q2, . . . . The recognition at each qi is performed over the SDEs (input) that fall within a specified interval, the 'working memory' or window ω. All SDEs outside the window are discarded and not considered during recognition. This means that at each qi CER depends only on the SDEs that took place in the interval (qi - ω, qi]. This way, the cost of reasoning depends on the size of ω and not on the complete stream. The size of ω, as well as the temporal distance between two consecutive query times - the slide step qi-qi-1 - are user-specified.

In addition to events and fluent-value pairs, the domain of an application contains a nonempty set C of N constants {c1, . . . , cN}, called domain entities. For example, in the fluent-value pair gap(Vessel)=farFromPorts in rule (2), the variable Vessel is mapped to vessel IDs. Additionally, there is a nonempty ordered set T of Ω constants {t1, . . . , tΩ}, that correspond to the time-points specified by the application's temporal window ω. The time variable T in the EC predicates is mapped to some time-point tk, qi -ω < tk ≤ qi, ∀ 1 ≤ k ≤ Ω. Recall from inertia axiom (3), the predicate next(Tprev ,T). In case Tprev → tΩ, variable T cannot be mapped to a constant and thus predicate next(tΩ, T) returns false. This way we restrict fluents to hold inside window ω.

The sets C and T (ground terms) constitute the Herbrand universe UP of P, which is fixed and finite at each ω. If X is the set of all atoms of P, the Herbrand base (set of all ground atoms) of P is BP=XUP . A model MP of P is the set of ground atoms (⊆ BP ) that makes all the rules of the program true. Since P is stratified, MP is the unique perfect model of P [Gelfond and Lifschitz, 1988]. When a ground EC predicate r is entailed by MP , we write MP |= r.

The computation of MP is performed at each query time qi. Notice that, in the worst case, a fluent of a stratum may hold for the entire window ω, meaning that to compute all the time-points at which it holds we have to iterate through all the Ω constants in T (inertia axiom (3)).

3 Linear Algebraic Approach

We present our method, tensor-EC, for computing a model MP of an EC program P in tensor spaces. Before we delve into the details of the approach, we provide terminology and notation used henceforth.

3.1 Preliminaries

Vectors are represented by bold lower case letters, e.g., x. A vector of all ones is represented by 1. x · y = x⊤y is the dot product while x ◦ y = xy⊤ is their outer product. Matrices are written by bold upper case letters like X and the identity matrix is denoted by I. An order-p tensor (p specifies the number of dimensions, where p > 2) is written as X. X⊙Y is the Hadamard product (element-wise multiplication) of two tensors and is defined only on two tensors of the same order and size. We refer to an element of a vector x or an order-p tensor X, as xi and Xi1,...,ip , respectively.

Definition 4 (mode-(n,m) product). Let X and Y be two order-p and order-k tensors, respectively. The mode-(n,m) contracted product X ×n,m Y of X and Y is defined as:

In Def. 4, (n, m) index the dimensions of the two operands. Then, each element of the resulting tensor is the dot product of the fibers of size |z| of the n-th dimension of X and the fibers of size |z| of the m-th dimension of Y.

3.2 Encoding EC in Tensor Spaces

The EC language contains the sets of constants, C and T (section 2.2), events/fluents, and the predicates outlined in Table 1. We encode entities ci from C in one-hot vectors ci, i.e., vectors that have one at the i-th position and zeros elsewhere. Similarly, we encode time-points tk from T in one-hot vectors tk. The EC sets of constants now become C ′ = {c1, . . . , cN} and T ′ = {t1, . . . , tΩ}, forming the standard basis of RN and RΩ, respectively. When it is not clear from the context, we will specify the size of a vector x with xN or xΩ.

EC predicates are translated into matrices or tensors. The shape/order of a matrix/tensor equals the arity of events/fluents plus 1 for the temporal dimension. For illustration purposes, we restrict attention to binary events/fluents.

Definition 5 (EC predicates encoding). An EC predicate r is encoded by an order-3 tensor R ∈ {0, 1}N×N×Ω, where:

Element Ri,j,k equals 1 if predicate r is true in the model MP of the program for variable groundings ci, cj, tk, and 0 if it is not. The example below illustrates this encoding.

Example 2. Assume that C={c1, c2} has two entities, say vessel IDs, and T ={t1, t2} has two time-points. Then, C ′={c1, c2} and T ′={t1, t2}. Furthermore, assume the following groundings of the EC predicate initiatedAt(fl(X, Y )=v, T), expressing the initiation points of fluent fl:

Below we present, the one-hot vector of c1 (left), the onehot vector of t2 (middle), and the tensor S encoding the EC predicate initiatedAt(fl(X, Y )=v, T) (right):

The vertical line in the above tensor representation serves the separation of the temporal dimension, i.e., it separates the two temporal slices. In this example, t1 is expressed by the left slice while t2 is expressed by the right slice. The rows and columns of the tensor correspond to entities c1 and c2. For example, the first row and column of each temporal slice refer to c1. When we want to refer to a slice i of a tensor S, we use the notation S:,:,i . In the tensor representation in (4), a value of 1 signifies that for specific groundings of the variables the predicate is true and a value of 0 that the predicate is false. For example, the ground predicate initiatedAt(fl(c1, c2)=v, t2) corresponds to the element S 1,2,2 of S with value 1, and states that fluent fl is initiated at time-point t2 for entities c1 and c2.

To query the truth value of a specific variable grounding, e.g. initiatedAt(fl(ci, cj)=v, tk), we use the following:

3.3 Reasoning in Tensor-EC

The goal in EC is to compute the time-points at which a fluent holds. To achieve this, we first need to evaluate initiation and termination rules. To do this algebraically, we next show how we treat negation, conjunction, and disjunction.

EC predicates that participate negatively in the body of a rule (symbol not in rule (1)), imply that an event or fluent should not occur or hold at a specific time-point. To obtain a tensor representing a negative literal, we subtract from 1 each element of the tensor encoding the corresponding positive literal. Consider the negative literal not happensAt(a(X, Y ), T). The tensor ¬A used to represent this negative literal is computed as per Def. 6.

Definition 6 (Tensor Negation). Negation is defined as:

In Def. 6, notice that the outer product of all-ones vectors results in an all-ones order-3 tensor. ¬A is the result of subtracting from 1 all the elements of the positive counterpart tensor, i.e., A.

Example 3. The negation of S from (4) is:

Multiplication is used to evaluate the conjunction of literals. In EC rules conjunctive literals are evaluated at the same time-point, and usually on the same entities. Consider the following conjunction:

We denote each predicate with tensors A and B, respectively, and define tensor conjunction as per Def. 7.

Definition 7 (Tensor Conjunction). Conjunction is defined as the Hadamard product of two tensors:

Example 4. Consider the following tensors A and B:

Their conjunction would be:

stating that event a and fluent b have the same grounding of variables for entities c1 and c2 only at time-point t2.

In the Technical Appendix, we present a conjunction of literals in the presence of an existentially quantified variable. In that case, apart frommultiplying the dimensions specified by the variables that are common among the literals, we also sum the result across the dimension indexed by the quantified variable.

Disjunction is treated by tensor addition. Consider that we want to compute the following disjunction of literals:

Definition 8 (Tensor Disjunction). Disjunction is defined as:

Notice that in case of tensor disjunction, the value of an element of the resulting tensor may be greater than 1. In this case, we employ a standard thresholding operation, denoted by θ>1 --→, that makes every entry greater than 1 equal to 1. The same applies to disjunctive rules (rules with the same head), as well as for conjunction in the presence of existentially quantified variables (see Technical Appendix). This operation is needed because a tensor may participate negatively in the body of a rule and the computation of its negation will result in negative values, if thresholding is not used.

.

3.4 Computing aModel in Tensor Spaces

To obtain the time-points a fluent holds, we need to compute its initiation and termination points. In rule (1), we presented the general syntax of initiatedAt and terminatedAt rules. Let S be the tensor encoding the initiation points of fluent fl(X, Y )=v, E, A, B the tensors encoding the event occurrences of events e(X, Y ), a(X, Y ), and b(X, Y ), respectively, and C, D the tensors encoding the time-points at which fluents c(X, Y )=vc and d(X, Y )=vd hold, where S,E,A,B,C,D ∈ {0, 1}N×N×Ω. Recall from rule (1) that the symbol [not] denotes that negation is optional. If a literal participates negatively in the body of a rule, the tensor encoding the predicate is negated according to Def. 6. To compute the initiation points of S, we have:

The symbol [¬] represents the optional negation of tensors. '[[ ]]', similarly to rule (1), denotes that the presence of the enclosed tensors is optional. The evaluation of rule (1) in tensor spaces, is the Hadamard product of the tensors encoding the body literals, and the result is tensor S encoding the initiation points of fluent fl. In Eq. (6), the initiation points of S are basically the time-points at which all tensors, E, [[ [¬] A, [¬]B, [¬]C, [¬]D]], are true for the same groundings of entities and time-points.

terminatedAt rules are evaluated in a similar manner. The reasoning process ends with the computation of the timepoints at which a fluent holds. To achieve this in tensor-EC, we employ the inertia axiom presented in rule-set (3). The inertia axiom is a disjunction of rules, where the variables are common among the first two body literals of each rule. Let S,T ∈ {0, 1}N×N×Ω be order-3 tensors, computed by the equivalent tensor formulation (Eq. (6)) of rules of type (1), that encode the time-points at which fluent fl is initiated and terminated, respectively. ¬T ∈ {0, 1}N×N×Ω is the negative version of T, computed as per Def. 6.

The predicate next(Tprev ,T) in inertia axiom (3) states that the next time-point of Tprev is T. We encode next with shift matrix U ∈ {0, 1}Ω×Ω, that is, a square matrix with ones only on the super-diagonal and zeros elsewhere. Postmultiplying a matrix A with U, i.e., AU, results in shifting the elements of A to the right by one position, with zeros appearing in the first column. Multiplying a tensor A with a shift matrix results in the shifting of elements along the temporal dimension, i.e., the first temporal slice is a matrix of zeros, A:,:,1 = 0N ◦ 0N , where 0N an all-zeros vector. Finally, let H be the tensor encoding the time-points at which fluent fl holds. Then, the inertia axiom can be seen as a first-order difference (recursive) equation of the form:

Eq. (7) states that a fluent holds at a time-point if it was initiated or held and not terminated at the previous time-point.

Unfolding Eq. (7) for every element of tensors H, S, ¬T, i.e., for every pair of entities ci, cj ∈ C and time-point tk ∈ T , we result in the following system of linear first-order difference equations:

. . .

Notice that the initial condition Hi,j,1= 0, 1 ≤ i, j ≤ N, states that at the first time-point t1, regardless the pair of entities ci, cj , no fluent can hold. The above system can be written in matrix form as:

where G ∈ RN 2Ω×N 2Ω is the coefficients matrix, and h ∈ RN 2Ω, b ∈ {0, 1}N 2Ω, are column vectors. Our goal is to solve Eq. (8) for h, i.e., the time-points at which a fluent holds for every pair of entities.

To construct the matrix equation (8), we must first perform a series of operations. We define vec[·] as the vectorization operator, which transforms a tensor into a vector. For example, let a be a vector and A a tensor, vec[A] : A ∈ RN×N×Ω → a ∈ RN 2Ω. Then, the operations to produce G and b in Eq. (8), are the following:

In (a), all the elements of the principal diagonal of G are set to 1, the first sub-diagonal (G⋆ ) is set to the result of vectorizing ¬T multiplied by -1, and all the remaining elements are set to 0. Notice that, due to multiplication of vec [¬T] by -1, G /∈ {0, 1}N 2Ω×N 2Ω but G ∈ {-1, 0, 1}N 2Ω×N 2Ω. Vector b, in (b), is the vectorization of the Hadamard product of initiation and non-termination tensors, S and ¬T, shifted (mode-(3,1) product) by matrix U.

G is a lower unitriangular matrix, i.e., a lower triangular matrix for which all elements on the principal diagonal equal to 1. Additionally, G is a bi-diagonal matrix [Demmel, 1997; Kılıc¸ and Stanica, 2013], since only the elements of the principal and the first sub-diagonal may differ from 0. Since G is unitriangular, its determinant is 1 (product of the principal diagonal elements), and thus, it has an inverse (G-1 ). Hence, Eq. (8) has a unique solution, that can be expressed formally for vector h and tensor H, both encoding the time-points at which fl(X, Y )=v holds, as per Def. 9.

Definition 9 (Inertia Axiom Solution). The time-points at which a fluent-value pair holds are computed by:

In Def. 9, vec-1 [ · ] is the inverse of the vectorization operator, i.e., transforms a vector to a tensor. This operation is needed, since H may participate in the body of initiatedAt/ terminatedAt rules of type (1) at higher strata. Notice, also, that h ∈ RN 2Ω. To constrain h ∈ {0, 1}N 2Ω we use the thresholding operation θ>1 --→, already discussed in Section 3.3. Def. 9 may be extended for tensors of any order, i.e., for fluents with arity > 2.

The process described so far is repeated for every stratum of the EC program P , as is also the case for symbolic-EC (see Section 2.2). The tensors of stratum Ps, encoding the timepoints at which fluents of Ps hold (computed as per Def. 9), are cached and propagated to higher strata (P>s). At the end, the tensors of all strata constitute the perfect model MP .

Proposition 1 (Correctness). The unique solution of Eq. (8), computed by Eq. (9), coincides with the time-points at which a fluent-value pair holds, as expressed by the perfect model of the corresponding program in symbolic-EC. ♦

The proof may be found in the Technical Appendix.

Proposition 2 (Complexity). The time complexity of solving Eq. (8) is O(N p-1Ω) for order-p tensors [Demmel, 1997].♦

Eq. (8) requires the construction of the coefficients matrix G and vector b. The first sub-diagonal of G depends on the non-termination tensor ¬T, while b depends on the Hadamard product of initiation and non-termination tensors, S and ¬T, shifted (mode-(3,1) product) by matrix U. S and T are produced by evaluating initiatedAt and terminatedAt rules of type (1) in tensor-EC (Eq. (6)), and require O(N p-1Ω) time for order-p tensors. The time complexity of the mode-(3,1) product (S ⊙ ¬T) ×3,1 U, is O(N p-1Ω2 ).

Evaluating axiom (3) in symbolic-EC for fluents with arity p-1, requires in the worst case O(N p-1Ω). Moreover, rules of type (1), in symbolic-EC, are bound by O(N p-1Ω2 ) [Tsilionis et al., 2022]. Hence, both methods, symbolic-EC and tensor-EC, are bound theoretically by the same complexity.

However, the performance of tensor-EC can be boosted through parallelism or/and the employment of sparse representations. In this paper, we do not exploit parallelism (it is left for future work), but note that operations such as the Hadamard and mode-(n,m) products are trivially parallelized. In real-life scenarios, the time-points at which fluents are initiated and terminated are usually very few, and thus, the corresponding tensors would be very sparse. Operations on sparse representations avoid unnecessary calculations by not examining null elements (time-points at which the EC predicates are false), resulting in peformance improvement [Nguyen et al., 2022]. Furthermore, recall that shift matrix U has 1s only on the first super-diagonal and its sparse structure can also be considered. Finally, matrix G in Eq. (8) is a bi-diagonal matrix, where only the elements of the principal and the first sub-diagonal may differ from 0. By taking advantage of the sparsity of G and the fact that the elements of the principal diagonal are equal to 1, the time of solving Eq. (8) can be further reduced (see in the Technical Appendix the computation of the inverse G-1 ). In the empirical analysis, we employ sparse representations for the tensors and matrices needed by tensor-EC and observe significant improvements.

4 Empirical Analysis

We present an empirical analysis on real datasets from the field of maritime monitoring.

4.1 Experimental Setup

Symbolic-EC is implemented in XSB Prolog while the tensor-based implementation is written in Python. The source code of both methods and a subset of one of the datasets, are available in the Code & Data Appendix. The experiments were performed on a single core, on a computer with AMD EPYC 7543 and 400 GB of RAM, running Debian GNU/Linux 12, XSB Prolog 5.0.0 and Python 3.11.4.

The composite event recognition (CER) process involves the computation and caching of all time-points at which fluent-value pairs, expressing CEs, hold. On the field of maritime monitoring, CER concerns the recognition of composite maritime events (recall 'communication gap' from (2)) and is typically achieved by monitoring the messages vessels emit while sailing at sea. These messages are exchanged through the Automatic Identification System (AIS) [Bereta et al., 2021] and contain information about the position, heading, speed, etc. of vessels at different points in time. Moreover, these messages can be annotated automatically, conveying information about the start/end of sailing at a low/high speed, changes in speed/heading, entrance or exit in an area of interest, etc. [Patroumpas et al., 2017]. The annotated AIS messages constitute the input to our system.

The CE description used in our empirical analysis includes forty input events and twenty two fluents. Recall that each fluent is defined by one or more initiatedAt and terminatedAt rules, plus the inertia axiom. We employed two datasets for our empirical analysis; the first is a publicly available dataset, concerning approx. 5K vessels sailing in the Atlantic Ocean around the port of Brest, France, and consists of approx. 15M SDEs. The second dataset is proprietary and was provided to us by IMIS Global. It concerns 34K vessels sailing in the European seas and consists of approx. 32M SDEs. These datasets allow us to test the scalability of the methods.

Recall from Section 2.2, that CER takes place at specified query times q1, q2, . . . , where the recognition at each qi is performed over the SDEs (input - ground happensAt/ holdsAt predicates) that fall within a user-specified window ω. To simulate a streaming behavior, the datasets are stored in CSV files and are processed periodically in chunks according to the window ω specification. Moreover, the slide step (distance between consecutive query times) is set equal to ω in the experiments, i.e., non-overlapping windows are used. Notice that, given a constant window ω, the number of SDEs varies from window to window and consequently, the number of vessels (the N constants of the entity set C) changes, while the Ω time-points of set T (size of ω) remain unchanged.

Since the data concerning each vessel is very sparse due to periodic message emission, we use sparse representation of the tensors encoding fluents. However, efficient implementations of operations, such as the Hadamard or the mode(n,m) product, on sparse tensors do not exist. Therefore, we convert tensors to matrices. For example an order-3 tensor F ∈ {0, 1}N×N×Ω is converted to a matrix F ∈ {0, 1}N 2×Ω.

10 3

(a) Brest dataset

10 4

(b) European seas dataset

Figure 1: Tensor vs. symbolic-EC.

4.2 Experimental Results

Figures 1(a) and (b) display our experimental results for the Brest and the European seas dataset, respectively. In both datasets, we employ temporal windows of four different sizes and on the x-axis we state the size of the window, as well as the average number of SDEs and average number of vessels/entities falling inside the window. The y-axis of both figures corresponds to average recognition time (in log scale).

In the Brest dataset the temporal window varies from 1 to 8 hours, while in the European seas dataset the window varies from 200 to 2000 seconds. In both datasets, the time-points of the windows correspond to seconds. Notice that the number of SDEs and vessels increases dramatically in the European seas dataset, even for smaller windows. Tensor-EC achieves a performance gain for all window sizes in both datasets, highlighting the efficiency of the method in comparison to the symbolic one. Recall that the experiments were performed on a single core, i.e., no parallelization was used.

5 RelatedWork

Computing models of logic programs in vector spaces has recently gained a lot of attention. Sakama et al. [2021] presented a method for computing models, where they encode propositional programs into matrices. Optimization techniques that make the method able to cope with huge programs in vector spaces, have also been proposed [Nguyen et al., 2018; Nguyen et al., 2021]. Our work is not directly comparable to these propositional approaches. We also compute the model of a program but we use a first-order language. Propositionalization in CER would lead to millions of propositional atoms in the Herbrand base, and the construction of the program matrix would be practically infeasible, due to huge memory requirements and time complexity. Additionally, the matrix construction process needs to be repeated at each temporal window, since the set of domain entities/vessels C does not remain the same in each window.

The work closest to ours is that by Sato [2017a; 2017b]. Sato [2017a] utilizes a first-order language with a finite domain of constants. Entities are represented by one-hot vectors and p-ary relations by order-p (cubical) tensors. Quantifiers are also encoded as tensors and their order depends on the number of appearances of the quantified variable. Then, a procedure, consisting of matrix multiplications or tensor mode-(n,m) products, is proposed for determining the truth value of nested quantified logic formulas. This procedure can also be used for computing the encoding of a rule head, but it is only applicable to square matrices encoding binary predicates. In the case of tensors, redundant computations are introduced, increasing the order of the resulting tensor (in the Technical Appendix we demonstrate the reason). To solve this issue, when the variables are common among the head and the body literals, as in a rule of type (1), we employ the Hadamard product in Eq. (6), a cheaper operation compared to matrix multiplication and mode-(n, m) products. A further improvement is the use of an evaluation approach that does not increase the order of the head tensor, in the presence of existentially quantified variables (see Technical Appendix).

The method for computing square matrices that constitute the least model of a transitive closure program in Datalog, is described in [Sato, 2017b]. The model is determined by solving a linear recursive equation and significant speedups, compared to symbolic systems, are observed. Our work is inspired by this study and in Eq. (7) we formalize the inertia axiom (3) as a linear recursive equation. Furthermore, we provide in Def. 9 a solution that can be extended to tensors of any order, as opposed to the square (binary predicates) matrix solution in [Sato, 2017b]. Consider again, the predicate holdsAt(fl(X, Y )=v, T) that is encoded by tensor H ∈ {0, 1}N×N×Ω. The corresponding square matrix would be H ∈ {0, 1}NΩ×NΩ. Expressing the inertia axiom as a discrete Sylvester equation, as proposed by Sato, and solving it would require O(N 3Ω3 ) time. In our approach, with the use of a bi-diagonal matrix, the time complexity is O(N 2Ω), orders of magnitude lower. Recall that N in our empirical analysis reached a value of 13K in the European seas dataset.

Several EC implementations for logical reasoning over traces of events have been proposed in the literature [Chittaro and Montanari, 1996; Chesani et al., 2010; Bragaglia et al., 2012; Chesani et al., 2013; Montali et al., 2014; Arias et al., 2022]. These approaches represent the whole history and thus, as the trace grows, they are unable to scale to streaming applications. Tensor-EC adopts the optimization techniques of [Artikis et al., 2015], such as windowing and caching in hierarchical EC programs, to avoid unnecessary re-computations and scale to data streams.

6 Summary and FutureWork

We proposed a linear algebraic approach for computing the perfect model of a hierarchical EC program. We represent EC predicates as tensors and demonstrate that the time-points any p-ary fluent (CE) holds can be assessed by solving a linear recursive equation. The scalability of our system is empirically demonstrated on real-world streaming data from the maritime domain. Additionally, our numerical approach improves the performance of the symbolical implementation of EC, by orders of magnitude. An interesting future work direction would be to develop tensor representations that avoid the grounding of every time-point at which a fluent holds. Encoding in tensors the time intervals a fluent holds continuously, will reduce substantially the inference time. Finally, we intend to exploit parallel algorithms of linear algebra and hardware resources (e.g., GPUs) to further boost performance.

Acknowledgements

This work was supported by the ENEXA "Efficient Explainable Learning on Knowledge Graphs" project (No 101070305), which has received funding from the EU Horizon Europe research and innovation programme.