11institutetext: Institute of Informatics & Telecommunications, National
Center for Scientific Research (NCSR) “Demokritos”, Athens, Greece
11email<EMAIL_ADDRESS>

# Learning Automata-Based Complex Event Patterns in Answer Set Programming

Nikos Katzouris  Georgios Paliouras

###### Abstract

Complex Event Recognition and Forecasting (CER/F) techniques attempt to
detect, or even forecast ahead of time, event occurrences in streaming input
using predefined event patterns. Such patterns are not always known in
advance, or they frequently change over time, making machine learning
techniques, capable of extracting such patterns from data, highly desirable in
CER/F. Since many CER/F systems use symbolic automata to represent such
patterns, we propose a family of such automata where the transition-enabling
conditions are defined by Answer Set Programming (ASP) rules, and which,
thanks to the strong connections of ASP to symbolic learning, are directly
learnable from data. We present such a learning approach in ASP and an
incremental version thereof that trades optimality for efficiency and is
capable 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.

###### Keywords:

Automata Learning Answer Set Programming Complex Event Recognition

##  1 Introduction

Complex Event Recognition and forecasting (CER/F) systems [8, 17, 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, 17, 19], 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, 12, 10,
11, 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.

##  2 Related Work

Although the field of automata learning [20, 34] has a long history in the
literature [18, 4, 28, 21, 33, 5, 16, 32, 15], 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 [18, 4, 16, 5, 15], 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
[13, 26, 6, 14], 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, 15]. 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 [15] 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.

##  3 ASP Background

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 Clingo111https://potassco.org/ syntax for
representing ASP expressions. A choice rule is an expression of the form
$\\{\alpha\\}\leftarrow\delta_{1},\ldots,\delta_{n}$, with the intuitive
meaning that whenever the body $\delta_{1},\ldots,\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},\ldots,\delta_{n}.[w@p,t_{1},\ldots,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},\ldots,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},\ldots,\delta_{n},t_{1},\ldots,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.

##  4 The Problem Setting and a Running Example

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
project222https://www.infore-project.eu/.

######  Example 1 (Running Example).

INFORE’s precision medicine use-case utilizes CER/F techniques to assist the
knowledge discovery process in personalized cancer treatment development. This
process involves running a vast amount of complex, multi-cellular simulations
to study the effects of various drug synergies on tumor growth. Such
simulations are extremely demanding computationally and their majority ends-up
in a negative result, signifying that a particular drug combination is not
effective. Using CER/F to detect/forecast non-promising simulations at an
early stage may thus speed up research by allowing to terminate non-
interesting simulations early-on and allocate resources towards the
exploration of more promising drug combinations. This calls for learning
patterns of interesting/non-interesting outcomes from labeled, historical
simulation data. Notably, the interpretability of such patterns is crucial in
this domain.Therefore, mainstream black-box time-series classification
methods, including deep learning techniques, are not an option. Figure 1
presents such a simulation generated by PhysiBoss [22], a bio-informatics
simulation environment that allows to explore the results of several
environmental and genetic alterations to populations of cells. Figure 1
presents tumor growth evolution over time, in terms of population sizes of
three types of cell: the tumor’s _alive_ cells, its _apoptotic_ cells, i.e.
cells that are “programmed” to die, due to apoptosis, and the tumor’s
_necrotic_ cells, i.e. cells that die due to the effects of an injected Tumor
Necrosis Factor (TNF), i.e. a drug combination.

Figure 1: A multi-cellular simulation of tumor evolution from the INFORE
project.

Multivariate time-series, such as the simulation data from Figure 1, may be
converted into symbolic multivariate sequences (MVSs), e.g. by using the
Symbolic Aggregate Approximation (SAX) algorithm [24, 25]. SAX converts time-
series into symbolic sequences, by mapping numerical values to symbols, drawn
from a fixed-length alphabet, such that each symbol in the converted sequence
corresponds to a bin (value range) in the original time-series.

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},\ldots,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
$\mathsf{obs}(SeqId,\mathsf{av}(A,V),T)$, meaning that the attribute $A$ of
the MVS with unique id $SeqId$ has value $V$ at time $T$.

_(a) A toy training set consisting of two MVSs._ |
---|---
Positive example ($id_{1}$): |  Negative example ($id_{2}$):
_Alive cells:_ eeeedcbbbb |  _Alive cells:_ eecdbbbbbb
_Necrotic cells:_ aabbbcccde |  _Necrotic cells:_ aabbbbcccc
_Apoptotic cells:_ bbbcdghhhh |  _Apoptotic cells:_ bbbcfghhhh
_(b) The logical representation of MVS $id_{1}$:_ |
$I^{id_{1}}_{1}=\\{\textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(alive,\texttt{e}),1).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(necrotic,\texttt{a}),1).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(apoptotic,\texttt{b}),1).\\}$ |
$I^{id_{1}}_{2}=\\{\textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(alive,\texttt{e}),2).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(necrotic,\texttt{a}),2).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(apoptotic,\texttt{b}),2).\\}$ |
$I^{id_{1}}_{3}=\\{\textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(alive,\texttt{e}),3).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(necrotic,\texttt{b}),3).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(apoptotic,\texttt{b}),3).\\}$ |
… |
$I^{id_{1}}_{10}=\\{\textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(alive,\texttt{b}),10).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(necrotic,\texttt{e}),10).\ \textsf{\scriptsize obs}(id_{1},\textsf{\scriptsize av}(apoptotic,\texttt{h}),10).\\}$ |
Table 1: Multivariate, discrete sequences and their logical representation.

######  Example 2 (Labeled MVS).

Table 1 (a) presents a minimal, toy training set with a single positive and a
single negative example. Each example is an MVS consisting of three length-ten
sequences regarding the evolution of cell populations for the different types
of cell in our running example (Example 1). These sequences are short excerpts
of longer simulation sequences, which have been discretized using SAX. Each
symbol in a sequence corresponds to a bin of real values.Table 1 (b) presents
the logical representation of the positive example (MVS $id_{1}$) as a
sequence of interpretations $I^{id}_{1},\ldots,I^{id}_{10}$.

##  5 Answer Set Automata

We next define a family of symbolic automata that may be used to express CE
patterns over MVSs. The transition guard predicates, which we shall call
_transition features_ and correspond to selection predicates in a CER/F
context, will be defined by ASP rules, we therefore call the resulting
automata _answer set automata_ (ASA). Intuitively, a transition in an ASA is
enabled when the body of the corresponding transition feature rule is
satisfied by the input MVS. Note that ASA will be non-deterministic in
principle. This is because to enforce determinism in the case of symbolic
automata it must be ensured that the conditions that guard all outgoing
transitions from some state $q$ to a set of different states must be mutually
exclusive. This is infeasible to guarantee in the ASA framework, since the
transition features may encode arbitrary, domain-specific conditions that are
deemed informative to synthesize automata with. The non-determinism of the ASA
framework is in accordance with most event specification languages in the CER
domain, where complex event patterns are defined as, or are eventually
compiled into non-deterministic automata.

######  Definition 1 (Answer Set Automaton – ASA).

An answer set automaton is a tuple
$\mathcal{A}=\langle\Sigma,B,R,Q,q_{0},F,\delta\rangle$, where: $\Sigma$ is
the alphabet, represented by a set of ASP facts; $B$ is some background
knowledge represented by an ASP program; $R$ is a set of ASP rules, called the
_transition features_ ; $Q$ is a finite set of _states_ ; $q_{0}\in Q$ is a
designated _start state_ and $F\subseteq Q$ is a designated set of _accepting
states_ ; $\delta$ is a non-deterministic state transition function defined by
means of a _feature mapping_ $\delta_{R}:Q\times R\rightarrow Q$, where
$\delta_{R}(q,r)=q^{\prime}$ has the intuitive meaning that the transition
from state $q$ to $q^{\prime}$ is guarded by the transition feature $r$. Given
a feature mapping $\delta_{R}$, the transition function $\delta:Q\times
2^{\Sigma}\rightarrow 2^{Q}\cup\\{\bot\\}$ is defined as:

$\delta(q,I)=\left\\{\begin{array}[]{ll}A_{q}=\\{\delta_{R}(q,r)\in Q\ |\
I\cup B\vDash body(r)\\}\text{, if }A_{q}\neq\emptyset,\\\
\square\in\\{\\{q\\},\\{\bot\\}\\},\text{ else.}\\\ \end{array}\right.$ (1)

The “alphabet” $\Sigma$ in Definition 1 is defined as the set of ground facts
that encode the simple events in the input, i.e., facts of the form
$\mathsf{obs}(alive,\mathtt{a})$, as per our running example. The transition
function $\delta$ operates on interpretations, i.e. subsets of $\Sigma$, as
indicated by the powerset $2^{\Sigma}$ in $\delta$’s signature. Then, given a
state $q$ and an interpretation $I$, the “if” branch of $\delta$ in Eq. (1)
maps $q$ to its set of “next states” $A_{q}$. Each $q^{\prime}\in A_{q}$ is
obtained by the feature mapping $\delta_{R}$, therefore, it is of the form
$q^{\prime}=\delta_{R}(q,r)$ and has the property that $I\cup B$ satisfies the
body of the corresponding transition feature $r$.

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)=\\{q\\}$, or to reject the input, by
moving to an absorbing, “dead” state, which we denote by $\bot$. These
semantics correspond to two different event consumption policies in CER/F,
which are called _skip-till-any-match_ and _strict contiguity_ respectively
[17].

The logical representation of an ASA consists of a set of facts of the form
$\mathsf{transition}(s_{1},f,s_{2})$, meaning that the transition from state
$s_{1}$ to $s_{2}$ is guarded by condition $f$. Figure 2 presents an example
of this representation, which is explained in more detail in Example 3 below.
Additionally, the accepting states in the ASA are specified via atoms of the
form $\mathsf{accepting(s)}$.

Reasoning with ASA is performed via an interpreter that defines the desired
ASA behavior. Such an interpreter is presented in Figure 2 as part of the
background knowledge $B$ (also to be discussed in Example 3). The first rule
in the interpreter states that for any example (input MVS) $SeqId$ an ASA is
initially (at time 1) in state $q_{0}$, i.e. $q_{0}$ is the start state. The
second rule states that an ASA moves from state $S_{1}$ to state $S_{2}$ at
time $T$, if there is a transition whose feature is satisfied by the current
example ($SeqId$) at time $T$. This is the meaning of the
$\mathsf{satisfies}/3$ atom that appears in that rule. Finally, the third rule
in the interpreter defines the accepting condition for the MVS $SeqId$, by
demanding the ASA to be in an accepting state at the end of the MVS. Rejection
of an input MVS is defined implicitly via closed-world assumption. Note that
this interpreter implements the strict contiguity operational semantics, i.e.
it rejects the input at time $T$ if the set of next states $A_{q}$ at $T$ is
empty. The skip-till-any match semantics may also be supported by adding to
the interpreter an extra rule that allows to self-loop when $A_{q}=\emptyset$,
e.g. by using count aggregates in ASP:

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

Transition Features. In this work the transition features are assumed to be
defined beforehand (learning them, along with the corresponding ASA is a
direction of future work) and are assumed to encode simple relations over
attributes and values. Given that the goal is to check if the transition
features are satisfied or not by the coordinates of an input MVS, we define
them via the predicate $\mathsf{satisfies}/3$ that is used by the interpreter.
The bodies of such $\mathsf{satisfies}/3$ rules consist of the conditions that
should be satisfied in order for a transition to be triggered. These
conditions are defined by means of attribute-value observation atoms (i.e.,
$\mathsf{obs}/3$ atoms, as in Table 1) and comparison predicates that encode
relations between such atoms.

Figure 2: An ASA that discriminates between the positive and negative MVSs of
Figure 1.

######  Example 3 (Answer set automata & transition features).

Figure 2 presents an ASA, its logical representation and its transition
features $R$, along with some background knowledge $B$ necessary to reason
with the ASA. $B$ consists of the ASA interpreter and the specification of
attribute-value domain constants. We first discuss the transition features $R$
before going into the details of the ASA and its functionality. The first rule
in $R$ specifies the conditions under which an MVS $SeqId$ satisfies, at time
$T$, a predicate with signature $\mathsf{neg}(A,V)$, stating that at time $T$
in $SeqId$ (i.e., in $SeqId$’s $T$-th coordinate), the attribute $A$ does not
have the value $V$. The next rule defines a predicate
$\mathsf{lt}(A_{1},A_{2})$ stating that at time $T$ the value of attribute
$A_{1}$ is less than (hence, $\mathsf{lt}$) the value of attribute $A_{2}$.
Finally, the third rule in $R$ defines $\mathsf{atLeast}(A,V)$ stating that at
time $T$ the value of attribute $A$ is at least $V$.

Given these definitions, and based on the instances of the transition features
that guard the edges of the ASA in Figure 2, the behavior of the ASA is the
following: It self-loops on $q_{0}$ for as long as the size of the alive cells
population in the input – recall our running example – is not $\mathtt{b}$; it
transitions to the accepting state $q_{1}$ if an observation comes in, where
the size of the alive cells population is smaller than that of the necrotic –
an indication that a drug is promising; and it expects the necrotic cells
population size to exceed a threshold ($\mathtt{c}$) from that point on, by
self-looping on the accepting state.

The ASA in Figure 2 accepts the positive ($id_{1}$) and rejects the negative
example ($id_{2}$) in Table 1. To see the former note the ASA self-loops on
$q_{0}$ until time $T=7$, when the value of $\mathit{alive}=\mathtt{b}$,
causing $B\cup I_{7}^{id_{1}}$ to no longer satisfy the self-loop condition on
$q_{0}$. However, at the same time point $\mathit{necrotic}=\mathtt{c}$, which
exceeds the value of _alive_ (recall that the symbols in the running example
represent bins of values and they are ordered by the lexicographic ordering,
i.e. letters later in the alphabet represent bins of larger values).
Therefore, $B\cup I_{7}^{id_{1}}\vDash\mathsf{lt}(alive,necrotic)$, causing
the ASA to transition to the accepting state $q_{1}$. The values of _necrotic_
in the remaining time steps are at least $\mathtt{c}$, thus the ASA self-loops
on the accepting state for the rest of the input.

To see that the ASA rejects $id_{2}$ note that at time $T=5$ in $id_{2}$
$\mathit{alive}=\mathtt{b}$, causing the condition that allows to self-loop on
$q_{0}$ up to that point to fail. Moreover, the condition that allows to
transition from $q_{0}$ to $q_{1}$ is also not satisfied, since
$\mathit{necrotic}=\mathtt{b}$. Therefore, since the interpreter implements
the strict contiguity semantics, the ASA is in no state at time $T=6$ (i.e. it
implicitly moves to the dead state) and the input is rejected.

##  6 Learning Answer Set Automata

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 $\mathcal{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^{+}}\mathsf{rejects}(\mathcal{A},s)+\sum_{s\in
S^{-}}\mathsf{accepts}(\mathcal{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
$\langle\Pi,IC,G,A\rangle$, 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\vDash 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=\\{\mathsf{transition}/3,\mathsf{accepting}/1\\}$.

$\begin{array}[]{l}\text{\emph{Generate ASA:}}\\\
\\{\mathsf{transition}(S_{1},F,S_{2})\\}\leftarrow\mathsf{state}(S_{1}),\mathsf{state}(S_{2}),\mathsf{feature}(F).\\\
\mathsf{feature}(\phi)\leftarrow\mathsf{type}_{1}(var^{1}_{\phi}),\ldots,\mathsf{type}_{n}(var^{n}_{\phi}).\\\
\\{\mathsf{states}(S)\\}\leftarrow\mathsf{maxStates}(S).\\\
\\{\mathsf{accepting}(S)\\}\leftarrow\mathsf{state}(S).\\\
\mathsf{maxStates}(1..q_{N}).\ \ \ \mathsf{start}(1).\\\ {}\\\
\text{\emph{Minimize the training error:}}\\\ \text{:\texttildelow}\ \
\mathtt{accepted}(SeqId),\ \mathtt{negative}(SeqId).\ [w_{fp}@2,SeqId]\\\
\text{:\texttildelow}\ \ not\ \mathtt{accepted}(SeqId),\
\mathtt{positive}(SeqId).\ [w_{fn}@2,SeqId]\\\ {}\\\ \text{\emph{Example of
regularization constraints:}}\\\ \text{:\texttildelow}\ \
\mathtt{transition}(S_{1},X,S_{2}).\ [1@1,S_{1},S_{2},X]\\\
\text{:\texttildelow}\ \ \mathtt{accepted}(SeqId,T).\ [T@1,SeqId,T]\\\
\mathtt{accepted}(SeqId,T)\leftarrow\mathtt{inState}(SeqId,S,T),\mathtt{accepting}(S).\\\
\mathtt{accepted}(SeqId)\leftarrow\mathtt{accepted}(SeqId,\\_).\\\ {}\\\
\text{\emph{Example of structural constraints:}}\\\
\leftarrow\mathtt{transition}(S,_{,}S2),\mathtt{accepting},S2\neq
S.\vspace*{-0.2cm}\end{array}$
---
Table 2: Abductive ASA learning in ASP.

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 $\mathsf{transition}/3$ and
$\mathsf{accepting}/3$ facts (as in Figure 2). The $\mathsf{feature}/1$ rule
is just a “type rule” added for each transition feature $r\in R$. For
instance, for the transition feature $\mathsf{lt}(A,V)$ from Figure 1, the
corresponding type rule is
$\mathsf{feature}(\mathsf{lt}(A,V))\leftarrow\mathsf{att}(A),\mathsf{val}(V).$

The next block of rules is a set of weak constraints that minimize the
training error. Note that the $\mathsf{accepted}/1$ predicate is defined in
the ASA interpreter in Figure 2 and the $\mathsf{positive}/1$ and
$\mathsf{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 $\mathit{w_{fp}}$ for the first rule, which is the price paid for each
false positive, and $\mathit{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 $\mathsf{transition}/3$
facts. The second rule attempts to maximize earliness by minimizing the length
of the prefixes that an ASA needs to process before accepting333Maximizing
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 $\mathsf{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.

######  Example 4 (ASAL in Action).

Let $\Pi$ be the program consisting of the rules in Table 2, $B$ and $R$ from
Figure 2 and the logical representation of the two training examples in Table
1, as the union of the $I_{t}^{id_{1}}$’s and the $I_{t}^{id_{2}}$’s, along
with the facts $\mathsf{positive}(id_{1})$ and $\mathsf{negative}(id_{2})$.
Running $\mathsf{Clingo}$ on $\Pi$ and filtering the $\mathsf{transition}/3$
and the $\mathsf{accepting}/1$ facts from the generated solutions yields the
learnt ASA. One of these ASA is the one illustrated in Figure 2, which is
suboptimal, based on the constraints in Table 2. It can be seen that optimal
ASA consist of two states and two transitions. e.g. the ASA

$\mathsf{transition}(q_{0},\mathsf{at\\_least}(alive,\mathtt{e}),q_{0}).\
\mathsf{transition}(q_{0},\mathsf{at\\_least}(apoptotic,\mathtt{d}),q_{1}).$

$\mathsf{accepting}(q_{1}).$

In addition to being smaller, it can be seen that this ASA accepts the
positive example $id_{1}$ at step $6$, in contrast to the ASA in Figure 2,
which accepts at step 8. If we drop the earliness constraint in Table 2 we may
obtain a single-state ASA:

$\mathsf{transition}(q_{0},\mathsf{neg}(apoptotic,\mathtt{f}),q_{0}).$

$\mathsf{accepting}(q_{0}).$

Although this ASA correctly classifies the examples, it is degenerate and has
an unconventional behavior, always starting from an accepting state and
failing later on to reject the negative examples (e.g. it moves to the
implicit dead state at step 5 to reject $id_{2}$).

###  6.1 Incremental Learning & Automata Revision

ASAL is guaranteed to find an optimal, constraint-compliant solution to the
abductive ASA learning task, given enough time and memory. The main drawback,
however, is that the requirements for such resources grow exponentially with
the complexity of the learning task (e.g. alphabet size, number of transition
features etc.) and the size of the input (e.g. number and length of the
training examples), making the approach infeasible for larger datasets. To
alleviate this issue we give-up the requirement for optimal ASA and opt for an
incremental learning strategy that simply learns ASA with a good fit in the
training data. Additional strategies for improving ASAL’s scalability, such as
incorporating symmetry-breaking constraints, in order to ignore isomorphic
ASA, are future work directions.

ASAL’s incremental learning version operates on mini-batches of the training
data, sufficiently small to allow for fast ASA induction from each batch and,
ideally, sufficiently large and diverse to allow for learning relatively good
ASA from samples of the training set. This is paired with an ASA revision
technique, which tries to apply minimal structural modifications on existing
automata, to improve their performance on new mini-batches. The algorithm – we
omit the pseudocode due to space limitations – is a greedy, iterative hill-
climbing search that works as follows: At each point in time, an initially
empty, best-so-far ASA $\mathcal{A}$ is maintained. At each mini-batch $D$, if
$\mathcal{A}$’s local classification performance on $D$ is lower than a given
error threshold, $\mathcal{A}$ is revised by running $\mathsf{Clingo}$ on a
program $\Pi$ similar to the one described in Example 4, augmented as follows:
For each $\mathsf{transition}(q_{i},\phi_{i},q_{j})$ and each
$\mathsf{accepting}(q_{i})$ fact in the logical specification of $\mathcal{A}$
we add to $\Pi$ the following:

$\mathsf{existing}(\mathsf{transition}(q_{i},\phi_{i},q_{j})).$

$\mathsf{existing}(\mathsf{accepting}(q_{i})).$

$\text{:\texttildelow}\ \ \mathsf{not}\
\mathsf{transition}(q_{i},\phi_{i},q_{j}),\mathsf{existing}(\mathsf{transition}(q_{i},\phi_{i},q_{j})).\
[{-}w_{i}@1]$

$\text{:\texttildelow}\ \ \mathsf{not}\
\mathsf{accepting}(q_{i}),\mathsf{existing}(\mathsf{accepting}(q_{i})).\
[1@1]$

The first two facts simply state which facts already exist in the structural
description of $\mathcal{A}$, while the weak constraints penalize their
removal, thus fostering minimal revisions. The weight $w_{i}$ in the first
weak constraint is defined as $w_{i}=n-p$, where $n,p$ are respectively the
number of negative/positive examples throughout the entire training set, which
are accepted by $\mathcal{A}$ and the acceptance paths use the corresponding
transition feature $\phi_{i}$. Note the “-” sign in front of $w_{i}$, which
makes $w_{i}$ positive (i.e., a penalty in the optimization process) if $n>p$
and negative (i.e. a reward) in the opposite case.

An ASP solver runs on the augmented program $\Pi$ for a given time $t$, and
the $k$ best solutions found in that time are preserved, where the time-out
$t$ and $k$ are run-time parameters. Subsequently, these $k$ locally best
solutions are evaluated on the entire training set (updating the
aforementioned $p,n$ counts for each $\mathsf{transition}/3$ fact in these
ASA). If an ASA $\mathcal{A}^{\prime}$ is found after this process has a
better global performance than $\mathcal{A}$, it replaces $\mathcal{A}$ as the
new best ASA. The process is repeated for a given number of iterations, by
shuffling and re-partitioning the training set into new mini-batches at the
beginning of each iteration. The current best ASA that results from this
process is returned in the output.

|  Method |  $\mathbf{F_{1}}$-score |  #States |  #Transitions |  Time (min)
---|---|---|---|---|---
Bio Small-U |  RPNI |  0.702 |  13 |  292 |  0.05
|  EDSM |  0.722 |  12 |  278 |  0.05
|  DISC |  0.833 |  10 |  13 |  51
|  $\mathsf{ASAL_{classic}^{batch}}$ |  0.887 |  3 |  35 |  1 (time-out)
|  $\mathsf{ASAL_{classic}^{incr}}$ |  0.882 |  3 |  41 |  0.566
Bio Large-U |  $\mathsf{ASAL_{classic}^{incr}}$ |  0.858 |  3 |  57 |  13
Bio Small |  $\mathsf{ASAL_{classic}^{batch}}$ |  0.902 |  3 |  53 |  5 (time-out)
|  $\mathsf{ASAL_{classic}^{incr}}$ |  0.889 |  3 |  60 |  2.7
|  $\mathsf{ASAL_{symb}^{batch}}$ |  0.968 |  3 |  5 |  5 (time-out)
|  $\mathsf{ASAL_{symb}^{incr}}$ |  0.924 |  3 |  7 |  3.4
Bio Large |  $\mathsf{ASAL_{classic}^{incr}}$ |  0.852 |  3 |  12 |  25
|  $\mathsf{ASAL_{symb}^{incr}}$ |  0.942 |  3 |  8 |  39
Maritime |  $\mathsf{ASAL_{classic}^{incr}}$ |  0.892 |  3 |  15 |  6
|  $\mathsf{ASAL_{symb}^{incr}}$ |  0.952 |  3 |  8 |  18
Table 3: Experimental results

##  7 Experimental evaluation

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) $\mathsf{ASAL_{classic}^{batch}}$
and $\mathsf{ASAL_{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) $\mathsf{ASAL_{symb}^{batch}}$ and
$\mathsf{ASAL_{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}$444https://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
$\mathsf{ASAL_{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. $\mathsf{ASAL_{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)
$\mathsf{ASAL_{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.

##  8 Conclusions and Future Work

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.

## Acknowledgements

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.

## References

  * [1] Agrawal, J., Diao, Y., Gyllstrom, D., Immerman, N.: Efficient pattern matching over event streams. In: Proceedings of the 2008 ACM SIGMOD international conference on Management of data. pp. 147–160 (2008)
  * [2] Alevizos, E., Artikis, A., Paliouras, G.: Complex event forecasting with prediction suffix trees. The VLDB Journal 31(1), 157–180 (2022)
  * [3] Alevizos, E., Skarlatidis, A., Artikis, A., Paliouras, G.: Probabilistic complex event recognition: A survey. ACM Computing Surveys (CSUR) 50(5), 1–31 (2017)
  * [4] Angluin, D.: Learning regular sets from queries and counterexamples. Information and computation 75(2), 87–106 (1987)
  * [5] Angluin, D., Eisenstat, S., Fisman, D.: Learning regular languages via alternating automata. In: Twenty-Fourth International Joint Conference on Artificial Intelligence (2015)
  * [6] Argyros, G., D’Antoni, L.: The learnability of symbolic automata. In: International Conference on Computer Aided Verification. pp. 427–445. Springer (2018)
  * [7] Cugola, G., Margara, A.: Tesla: a formally defined event specification language. In: Proceedings of the Fourth ACM International Conference on Distributed Event-Based Systems. pp. 50–61 (2010)
  * [8] Cugola, G., Margara, A.: Processing flows of information: From data stream to complex event processing. ACM Computing Surveys (CSUR) 44(3), 15 (2012)
  * [9] D’Antoni, L., Veanes, M.: The power of symbolic automata and transducers. In: International Conference on Computer Aided Verification. pp. 47–67. Springer (2017)
  * [10] Demers, A., Gehrke, J., Hong, M., Riedewald, M., White, W.: Towards expressive publish/subscribe systems. In: International Conference on Extending Database Technology. pp. 627–644. Springer (2006)
  * [11] Demers, A.J., Gehrke, J., Panda, B., Riedewald, M., Sharma, V., White, W.M., et al.: Cayuga: A general purpose event monitoring system. In: Cidr. vol. 7, pp. 412–422 (2007)
  * [12] Diao, Y., Immerman, N., Gyllstrom, D.: Sase+: An agile language for kleene closure over event streams. UMass Technical Report (2007)
  * [13] Drews, S., D’Antoni, L.: Learning symbolic automata. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems. pp. 173–189. Springer (2017)
  * [14] Fisman, D., Frenkel, H., Zilles, S.: Inferring symbolic automata. arXiv preprint arXiv:2112.14252 (2021)
  * [15] Furelos-Blanco, D., Law, M., Jonsson, A., Broda, K., Russo, A.: Induction and exploitation of subgoal automata for reinforcement learning. Journal of Artificial Intelligence Research 70, 1031–1116 (2021)
  * [16] Giantamidis, G., Tripakis, S., Basagiannis, S.: Learning moore machines from input–output traces. International Journal on Software Tools for Technology Transfer 23(1), 1–29 (2021)
  * [17] Giatrakos, N., Alevizos, E., Artikis, A., Deligiannakis, A., Garofalakis, M.N.: Complex event recognition in the big data era: a survey. VLDB J. 29(1), 313–352 (2020)
  * [18] Gold, E.M.: Language identification in the limit. Information and control 10(5), 447–474 (1967)
  * [19] Grez, A., Riveros, C., Ugarte, M.: A formal framework for complex event processing. In: 22nd International Conference on Database Theory (ICDT 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
  * [20] De la Higuera, C.: Grammatical inference: learning automata and grammars. Cambridge University Press (2010)
  * [21] Lang, K.J., Pearlmutter, B.A., Price, R.A.: Results of the abbadingo one dfa learning competition and a new evidence-driven state merging algorithm. In: International Colloquium on Grammatical Inference. pp. 1–12. Springer (1998)
  * [22] Letort, G., Montagud, A., Stoll, G., Heiland, R., Barillot, E., Macklin, P., Zinovyev, A., Calzone, L.: Physiboss: a multi-scale agent-based modelling framework integrating physical dimension and cell signalling. Bioinformatics 35(7), 1188–1196 (2019)
  * [23] Lifschitz, V.: Answer set programming. Springer (2019)
  * [24] Lin, J., Keogh, E., Lonardi, S., Chiu, B.: A symbolic representation of time series, with implications for streaming algorithms. In: Proceedings of the 8th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery. pp. 2–11 (2003)
  * [25] Lin, J., Keogh, E., Wei, L., Lonardi, S.: Experiencing sax: a novel symbolic representation of time series. Data Mining and knowledge discovery 15(2), 107–144 (2007)
  * [26] Maler, O., Mens, I.E.: A generic algorithm for learning symbolic automata from membership queries. In: Models, Algorithms, Logics and Tools, pp. 146–169. Springer (2017)
  * [27] Muggleton, S.H., Lin, D., Pahlavi, N., Tamaddoni-Nezhad, A.: Meta-interpretive learning: application to grammatical inference. Machine learning 94(1), 25–49 (2014)
  * [28] Oncina, J., Garcia, P.: Identifying regular languages in polynomial time. In: Advances in structural and syntactic pattern recognition, pp. 99–108. World Scientific (1992)
  * [29] Pietzuch, P.R., Shand, B., Bacon, J.: A framework for event composition in distributed systems. In: ACM/IFIP/USENIX International Conference on Distributed Systems Platforms and Open Distributed Processing. pp. 62–82. Springer (2003)
  * [30] Schultz-Møller, N.P., Migliavacca, M., Pietzuch, P.: Distributed complex event processing with query rewriting. In: Proceedings of the Third ACM International Conference on Distributed Event-Based Systems. pp. 1–12 (2009)
  * [31] Shvo, M., Li, A.C., Icarte, R.T., McIlraith, S.A.: Interpretable sequence classification via discrete optimization. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI). pp. 9647–9656 (2021)
  * [32] Smetsers, R., Fiterău-Broştean, P., Vaandrager, F.: Model learning as a satisfiability modulo theories problem. In: International Conference on Language and Automata Theory and Applications. pp. 182–194. Springer (2018)
  * [33] Ulyantsev, V., Zakirzyanov, I., Shalyto, A.: Bfs-based symmetry breaking predicates for dfa identification. In: International Conference on Language and Automata Theory and Applications. pp. 611–622. Springer (2015)
  * [34] Wieczorek, W.: Grammatical Inference. Springer (2017)
  * [35] Wu, E., Diao, Y., Rizvi, S.: High-performance complex event processing over streams. In: Proceedings of the 2006 ACM SIGMOD international conference on Management of data. pp. 407–418 (2006)
  * [36] Zhang, H., Diao, Y., Immerman, N.: On complexity and optimization of expensive queries in complex event processing. In: Proceedings of the 2014 ACM SIGMOD international conference on Management of data. pp. 217–228 (2014)