Learning Automata-Based Complex Event Patterns in Answer Set Programming

Complex Event Recognition and forecasting (CER/F) systems [8, 18, 2] detect, or even forecast ahead of time, occurrences of complex events (CEs) in multivariate streaming input, defined as temporal combinations of simple events, e.g. sensor data. CE patterns are typically defined by domain experts in some event specification language. However, such patterns are not always known in advance, or they frequently need to be revised, as the characteristics of the input data change over time, making machine learning techniques capable of learning such patterns from data highly desirable in CER/F.

Despite the great diversity of existing event specification languages, a minimal set of basic constructs/operators that should be present in every such language have been identified [36, 3, 18, 20], in the form of an abstract event algebra. The most important of these operators are the sequence operator and the closely related iteration operator (Kleene Closure), implying respectively that some particular events should succeed one another temporally, or that an event should occur iteratively in a sequence, and the selection operator, which filters (selects) events that satisfy a set of predefined predicates. Taken together, these three operators already point to a computational model for CER/F based on symbolic automata [9], and indeed, in most existing CER/F systems CE patterns are either defined directly as symbolic automata, or are compiled into such at runtime [35, 1, 36, 13, 11, 12, 30, 29, 7, 2]. In symbolic automata the transition-enabling conditions are predicates, rather than mere symbols, as in classical automata. In CER/F, the structure of such an automaton pattern corresponds to the conditions specified by the sequence/iteration operators in the CE pattern and their transition guards correspond to the pattern’s selection predicates.

Learning such symbolic automata-based CE patterns is a challenging task that requires to combine automata structure identification techniques with reasoning about the satisfiability of the selection predicates. To address this issue we propose a family of symbolic automata, which we call answer set automata (ASA), where the transition guards are defined by means of rules in Answer Set Programming (ASP), providing definitions for the selection predicates. Importantly, thanks to the strong connections of ASP with symbolic learning, ASA-based CE patterns are directly learnable from data. We present an approach that utilizes the power of ASP in declarative learning to automatically construct such patterns from data and we lift this approach to an incremental version that trades optimality for efficiency and allows our learning framework to scale to large datasets. We evaluate our approach on two CER datasets and compare it to state-of-the-art automata learning techniques, demonstrating empirically a superior performance, both in terms of predictive accuracy and scalability.

Although the field of automata learning [10, 34] has a long history in the literature [19, 5, 28, 21, 33, 4, 17, 32, 16], existing techniques that induce automata from positive & negative traces have several shortcomings, which limit their applicability in the CER/F domain. Most such algorithms either attempt to learn a model that perfectly discriminates between the positive/negative traces [19, 5, 17, 4, 16], or they use greedy techniques for state merging [28, 21], a technique that generalizes from a large, tree-like automaton (the Prefix Tree Acceptor – PTA), generated from the entire training set. These approaches tend to learn large, overfitted models that generalize poorly. More recent techniques [31] replace the PTA generalization heuristics with exact, constraint-based automata identification methods, achieving higher generalization capacity. However, the issue remains that such techniques still need to encode the entire training set into a PTA, raising memory/scalability issues in large datasets.

All aforementioned algorithms learn classical automata. Although some of these algorithms could, in principle, be applied to the symbolic automata learning setting, e.g. via propositionalization, that would entail an explosion in alphabet size and the combinatorial complexity of the learning task. On the other hand, although some algorithms for symbolic automata induction do exist [14, 26, 6, 15], they are mostly based on “upgrading” existing classical automata identification techniques to richer alphabets, and they thus suffer from the limitations outlined above, i.e. poor generalization, intolerance to noise and limited scalability.

Learning automata and grammars has been an application domain for ILP since its early days, targeting mostly classical automata expressed as definite clause grammars. More recent ILP frameworks, such as meta-interpretative learning (MIL) and learning from answer sets (ILASP), have also been applied to the task [27, 16]. However, both these approaches learn models that perfectly discriminate between positive and negative examples, therefore, they cannot deal with noise in the data. Moreover, the MIL approach of [27] learns classical automata, and although the ILASP-based approach of [16] does learn a form of symbolic automata, the transition guards therein are restricted to propositional clauses generated from combinations of the alphabet symbols, which falls short of the CER/F requirement for arbitrary selection predicates.

In contrast to the above-mentioned approaches, our symbolic automata learning framework utilizes the full expressive power of ASP in the definitions of transition guards and ASP’s declarative learning capabilities to learn highly compressive models that generalize adequately. Moreover, its incremental learning version is able to scale to arbitrarily large datasets.

We assume some familiarity with ASP and refer to [23] for an in-depth account. In this section we review some basic ASP constructs that will be useful in what follows. Throughout, we use the Clingo¹¹1https://potassco.org/ syntax for representing ASP expressions. A choice rule is an expression of the form $\left\{\alpha \right\}\leftarrow {\delta }_1,\dots ,{\delta }_n$, with the intuitive meaning that whenever the body ${\delta }_1,\dots ,{\delta }_n$ is satisfied by an answer set $I$ of a program that includes the choice rule, instances of the head $\alpha$ are arbitrarily included in $I$ (satisfied) as well. A weak constraint is an expression of the form $\text{:texttildelow}{\delta }_1,\dots ,{\delta }_n.[w@p,t_1,\dots ,t_k]$, where ${\delta }_i$’s are literals, called the body of the constraint, $w$ and $p$ are integers, called respectively the weight and the priority level of the constraint and $t_1,\dots ,t_k$ are ASP terms. A grounding/instance of a weak constraint $c$ is an expression that results from $c$ by replacing all variables in ${\delta }_1,\dots ,{\delta }_n,t_1,\dots ,t_k$ by constants. Such an instance is satisfied by an answer set $I_{\Pi }$ of a program $\Pi$ that includes $c$ if $I_{\Pi }$ satisfies $c$’s ground body, which incurs a penalty of $w$ on $I_{\Pi }$. $I_{\Pi }$’s total cost is the sum of penalties resulting from each instance of $c$ that is satisfied by $I_{\Pi }$. Inclusion of weak constraints in an ASP program triggers an optimization process that yields answer sets of minimum cost. Priority levels in weak constraints model the constraints’ relative importance, since the aforementioned optimization process attempts to first minimize the total cost due to weak constraints of higher priority levels.

We next set the scene for our proposed automata-based CE pattern learning framework. CER/F applications usually deal with multivariate input, i.e., input that arrives in multiple streams, each representing a ‘‘signal’’ obtained by the evolution of a relevant domain attribute in time. We illustrate the case using a running example from the domain of precision medicine, as formulated in the context of the INFORE EU-funded project²²2https://www.infore-project.eu/.

In the event pattern learning setting that we put forward we assume that the training data consist of labeled, symbolic MVSs, each representing a training example. For instance, the symbolic MVS obtained by discretizing the simulation data in Figure 1, along with a label (e.g. interesting/non-interesting simulation) represents such a training example. In what follows, by MVS we always mean a symbolic MVS.

Given an MVS $S$ of maximum length $n$ (i.e. the length of the largest sequence in $S$) we use a logical representation of $S$ as a sequence of interpretations $I_1,\dots ,I_n$, where each $I_t$ consists of ground facts that describe $S$’s $t$-th coordinate. In particular, we assume that each sequence in $S$ corresponds to a domain attribute and consists of symbols from a fixed alphabet $\Sigma$ that represent the values of this attribute over time. Then, the interpretation $I_t$ that corresponds to $S$’s $t$-th coordinate consists of observation facts of the form $obs(SeqId,av(A,V),T)$, meaning that the attribute $A$ of the MVS with unique id $SeqId$ has value $V$ at time $T$.

If the set of next states is empty (i.e., if no transition feature associated with $q$ is satisfied by $I$), the “else” branch encodes the different operational semantics that may be defined to govern the automaton’s behavior in this case. Typical options for such semantics is either to self-loop on the current state, in which case $\delta (q,I)=\left\{q\right\}$, or to reject the input, by moving to an absorbing, “dead” state, which we denote by $\perp$. These semantics correspond to two different event consumption policies in CER/F, which are called skip-till-any-match and strict contiguity respectively [18].

$inState(Id,S,T+1)\leftarrow inState(Id,S,T),\#count\{F:satisfies(Id,F,T\left)\right\}=0.$

We now turn to our approach to Answer Set Automata Learning (ASAL) in ASP. Our learning objective may be formulated as follows: Given a training set consisting of positive and negative MVSs $S^{+}$ and $S^{-}$, a set of transition features $R$, a “state budget” $N$ and potentially, a set of structural and regularization constraints $SC$ and $RC$ respectively, learn an ASA $A$ that uses the transition features in $R$, respects $SC$, optimizes $RC$, does not exceed $N$ and minimizes the training error, defined as: ${\sum }_{s\in S^{+}}rejects(A,s)+{\sum }_{s\in S^{-}}accepts(A,s)$, i.e. the number of misclassified training examples.

Structural constraints may include e.g. requirements for accepting states being absorbing ones, starting states not being accepting states etc. Regularization constraints are typically related to learning simpler models, where simplicity in our case is measured by the total number of states and transitions in an automaton. Several other simplicity criteria may be considered. For instance, an earliness bias would favor automata that accept/reject their input as early as possible, the intuition being that initial segments of the input are often enough to learn a good model, while trying to fit the entire input could yield more complicated automata with inferior generalization capacity.

We cast the automata learning problem as an abductive reasoning task in ASP. In its simplest form, such a task may be defined as a tuple $⟨\Pi ,IC,G,A⟩$, where $\Pi$ is a logic program that represents some background knowledge, $IC$ is a set of constraints that must be respected, $G$ is a set of ground constraints, often called “goals” and $A$ is a set of predicate signatures called abducibles. A solution to an abductive reasoning task is a set of ground logical facts $\Delta$, such that $B\cup IC\cup \Delta \models G$.

In our case, the background knowledge program $\Pi$ contains the ASA interpreter, the definitions of the transition features $R$ and the training MVSs $S^{+}\cup S^{-}$ in logical form; $IC$ are the structural and regularization constraints, $G$ is a set of ground constraints related to the acceptance/rejection of each MVS in $S^{+},S^{-}$ respectively and $A=\{transition/3,accepting/1\}$.

The abductive task is straightforward to specify and solve in ASP, via its generate-and-test methodology, according to which we generate automata via choice rules and test their performance via (weak) constraints. Table 2 presents an example formulation. The choice rules in the first block of rule generate ASA as collections of $transition/3$ and $accepting/3$ facts (as in Figure 2). The $feature/1$ rule is just a “type rule” added for each transition feature $r\in R$. For instance, for the transition feature $lt(A,V)$ from Figure 1, the corresponding type rule is $feature\left(lt\right(A,V\left)\right)\leftarrow att\left(A\right),val\left(V\right).$

The next block of rules is a set of weak constraints that minimize the training error. Note that the $accepted/1$ predicate is defined in the ASA interpreter in Figure 2 and the $positive/1$ and $negative/1$ predicates are facts that carry the label of each training MVS. The constraints may be weighted differently, accounting e.g. for imbalances between positive/negative examples in the training set. The weights are $w_{fp}$ for the first rule, which is the price paid for each false positive, and $w_{fn}$ for the second rule, the price paid for each false negative. These constraints have a higher priority, relative to the ones that follow in Table 2, making training error minimization the primary objective.

The next block of rules presents an example of regularization biases in the form of weak constraints. The first constraint attempts to compress the generated automata as much as possible, by penalizing $transition/3$ facts. The second rule attempts to maximize earliness by minimizing the length of the prefixes that an ASA needs to process before accepting³³3Maximizing earliness for input rejection, in addition to acceptance, would also be possible by modifying the ASA interpreter to not handle rejection via the closed-world assumption, but via explicit, absorbing dead states, and adding appropriate regularization constraints.. The $accepted/2$ predicate that is used in the earliness constraint simply monitors the number of steps needed to reach an accepting state, while the next rule defines acceptance in terms of such “partial” acceptance. To use the earliness bias constraint in ASAL  these two rules should replace the third rule in the ASA interpreter in Figure 2, while accepting states should be treated as absorbing. This essentially forces ASAL  to learn an automaton that accepts from prefixes of the input, whose length is to be minimized by the earliness constraint. The last rule in Table 2 is a structural constraint ensuring that accepting states are absorbing.

We empirically assess ASAL on two CER datasets from the domains of precision medicine and maritime monitoring. The former has already been outlined in Section 3. It consists of 644 time series, each containing three signals related to the alive, necrotic and apoptotic attributes, of length 49 each. The positive class (interesting simulations) amounts to the $20\%$ of the data. In addition to this dataset, to which we refer as Bio-small, in order to test the scalability of the incremental version of ASAL, we also used a significantly larger dataset with the same characteristics, but with 50K training simulations.

The maritime dataset contains data from nine vessels that cruised around the port of Brest, France. There are five attribute signals for longitude, latitude, speed, heading, and course over ground. The positive class is related to whether a vessel eventually enters the port of Brest and there are 2,980 negative and 2,269 positive examples, a total of 5,249 multivariate examples, each of length 30. The maritime dataset has been previously used in CER research, we therefore refer to [2] for more details. Both datasets were discretized using SAX with ten bins.

We compared the following algorithms: (a) $ASA{L}_{classic}^{batch}$ and $ASA{L}_{classic}^{incr}$, the batch and incremental version of ASAL that learns ASA that resemble classical automata, by using no transition feature other that equality, i.e. an attribute having a particular value found in the data. This is similar to using a symbol for each attribute-value. This version of ASAL was evaluated to assess the merits of using relational transition features; (b) $ASA{L}_{symb}^{batch}$ and $ASA{L}_{symb}^{incr}$, the batch and incremental versions respectively of ASAL, as described in the previous sections. These were used with five predefined transition features, similar to those presented in Figure 2; (c) RPNI [28] and an improved version thereof, EDSM [21], two widely used algorithms of the state-merging (SM) family, that compress a PTA (see Section 3) using greedy heuristics. Note that although these algorithms are quite old, the main ideas behind them are the SoA in SM-style learning and their \(\mathsf{LearrnLib}\lx@note{footnote}{\url{https://learnlib.de/}}\)⁴⁴4https://learnlib.de/ implementation used in the experiments is extremely efficient and frequently used by practitioners; (d) DISC [31], a recent algorithm that translates the PTA compression problem into a Mixed Integer Linear Programming problem, which it delegates to the off-the-shelf Gurobi solver. DISC is similar to ASAL in the sense that it is able to learn optimal automata, given enough time and memory.

The experimental setting was a five-fold cross validation with $80/20$ training/testing set splits. The experiments were carried-out on a 3.6GHz processor (4 cores, 8 threads) and 16GB of RAM. Whenever $ASA{L}_{classic}^{batch}$ was used it was given a timeout (maximum allowed time), in order to obtain a solution in a feasible amount of time.

The results are presented in Table 3 in the form of average testing set $F_1$-scores, number of states and transitions, as well as training times for the algorithms compared. Note that RPNI, EDSM and DISC deal with single strings and cannot handle multivariate input. To compare to these algorithms we used a univariate version of the bio dataset, which contains the alive attribute only, as it is informative enough to learn a useful model. No such attribute has this property in the maritime dataset, we therefore did not experiment with RPNI, EDSM and DISC on it. Moreover, only the “classic” version of ASAL was used on the univarate bio dataset, since there are no cross-feature relations that could be captured by transition features in the symbolic version.

The first block in Table 3 concerns the small version of the univariate dataset. It can be seen that RPNI and EDSM are lightning-fast, learning a model in approx. three secs. On the other hand, they have significantly inferior predictive performance as compared to all other algorithms and they are significantly more complicated, as indicated by their size. DISC has a better $F_1$-score and learns slightly simpler models, as indicated by its states number (the reduced number of transitions for DISC is misleading, since DISC omits self loops). On the other hand, it takes a little less than an hour on average to train. $ASA{L}_{classic}^{batch}$ has the best predictive performance, achieved within 1 min. Its incremental version closely follows in predictive performance in almost half the time.

In the large version of the univiariate bio dataset (second block in Table 3) $ASA{L}_{classic}^{incr}$ was the only usable algorithm, since RPNI, EDSM and DISC terminated with memory errors, due to the size of the dataset. In contrast, thanks to its incremental learning strategy that never loads the entirety of the training data into memory, ASAL was able to learn a good model in approx. 13 minutes.

The results from the small version of the full bio dataset (containing all the features) in the next block in Table 3), highlight the advantages of learning symbolic automata. Indeed, both the batch and the incremental version of ASAL achieve significantly better results than the classical version of ASAL and learn automata with much fewer transitions. Note that the $F_1$-scores of the two versions of the batch ASAL version were achieved with the same time-out value and the incremental versions of ASAL have comparative training times. Therefore, the symbolic version learns better models without significantly compromising efficiency. The results from the large bio dataset (full, all features used) and the maritime dataset also seem to confirm this claim.

We presented a methodology for learning symbolic automata where the transition guards are defined via ASP rules, and evaluated our approach on two CER datasets, demonstrating its efficacy. There are several directions for future work, including a more thorough experimental assessement on more datasets and settings, a formal characterization of the expressive power of ASA in relation to common event algebras used in CER, scalability improvements, e.g. via symmetry breaking, and jointly learning the transition features definitions, along with the automaton.

This work is supported by the project entitled “ARIADNE - AI Aided D-band Network for 5G Long Term Evolution”, which has received funding from the European Union’s Horizon 2020 research & innovation programme under grant agreement No 871464, and by the project entitled “INFORE: Interactive Extreme-Scale Analytics and Forecasting”, which has received funding from the European Union’s Horizon 2020 research & innovation programme under grant agreement No 825070.