The tendency to expand the use of event-driven architecture leads to the need to improve the e ciency of designing components of such systems, in particular, event-pattern detectors. Authors of the paper propose to use machine-learning to automate designing processes of event-pattern detectors. For substantiating their opinion, the authors conducted a series of computer experiments, showing that the idea is not groundless. Summing up, the authors draw attention to the issues that require further research aimed at creating information technology for the synthesis of event-pattern detectors.
Global network solutions, based on the Internet platform, which include
besides software components various subsystems of information
registration and executive physical subsystems form the class of complex systems
developing successfully nowadays. This class of systems is called
Internetof-Things (IoT) [
Realisation of EDA for information systems is known as Event Stream
Processing (ESP). ESP is a complex of technological tools designed for
assisting the development of event-driven information systems [
The mathematical model of such a system is proposed in [
In this paper, we propose to discuss the possibility of using machine
learning methods for automating synthesis process of one simple but
important class of event-pattern detectors. We use some ideas contained in
[
To build a mathematical model of an event-pattern detector, we need to establish how the detector interacts with other components of the ESP system or, in other words, what is the system context of the detector. This context is presented in Fig. 1. This sequence diagram is the same as the diagram in [10, Fig. 2, p. 105] excepting some insigni cant changes. We use this sequence diagram as a framework for building a mathematical model of event-pattern detectors used in ESP systems.
We accept the following series of suggestions, which is the base for building a mathematical model of the detector.
Suggestion 1. Each message is characterised by its class that is uniquely determined and belongs the nite prede ned set of event classes. A message can contain additional information but this information is used by executive systems only.
Suggestion 2. There are a nite set of event-patterns and each eventpattern is a language over event classes.
Suggestion 3. Any in nite sequence of messages contains at most one message that a detector accepts and, therefore, classi es.
Suggestion 4. A detector halts immediately if it has made a decision about belonging to some class of the received word otherwise it continues waits for an additional information to continue the analysis. These suggestions lead us to the following mathematical model, which we call a pattern-detecting machine.
start() msg par loop put(msg) loop
get() msgs opt [decision 6=
UNKNOW] reset() set(INITIAL)
:Detector analise(msgs)
decision job for processing set(decision) :Detector b De nition 1. Let and be nite sets called the event class set and the pattern set respectively then an event detector is a computable pre xfree partial mapping from + into .
In this de nition the following notation and concepts are used: + refers to the set of all nite non-empty sequences (non-empty words) of elements belonging to ; a pre x-free partial mapping means that this mapping is de ned on a subset of words that cannot contain a proper pre x of a word if it contains the word; a computable mapping means that for the mapping, there exists a Turing machine that halts on a word if and only if this word belongs to the domain of the mapping and the mapping value on the word coincides with output of the Turing machine.
The above suggestions cause to the conclusion that a self-delimiting Turing machine is adequate and the most general mathematical model of an event-pattern detector. We give the corresponding de nition following [8, see Sections 4.3 and 4.4] with minor changes.
De nition 2. An event-pattern detector with the class set and the pattern set where and are nite sets is a Turing machine with two tapes, one of which is called the input tape, i.e. it is right-way in nite and its head can move only to the right, and another is called the working tape, i.e. it is two-way in nite and the behaviour of its head is not limited. In addition, is an alphabet of the input type and it is assumed that each its cell has lled before the start of detector operation.
Finally, elements of are uniquely associated with nal states of the machine. Thus, the machine makes a decision at the moment of its halting and this decision is the element of associated with the corresponding nal state.
Bearing in mind that a general self-delimiting Turing machine is an overly complex object, we con ne ourselves to some simple subclass of these machines, namely, the subclass of those machines that do not have a working tape. 3
In the case where a self-delimiting Turing machine does not have the working tape, it can be described similarly to a nite state machine. De nition 3. A regular event-pattern detector is determined by a quintuple D = ( ; ; Q; q0; ) where { is a nite alphabet of message classes; { is a nite alphabet of decisions; { Q is a nite set of machine states; { q0 2 Q is some selected state, called the initial state; { : Q ! Q S is a mapping called the transition function. Now we de ne the relation ` + that models deriving the decision for the given input in the following manner for a1 : : : an 2 + and 2 such that qk = (qk 1; ak) for all 0 < k < n , and , there exists q1; : : : ; qn 1 2 Q = (qn 1; an) .
(1) Using mathematical induction gives the following statement. Proposition 1. If u ` uniquely , i.e. if u `
for u 2 + and and u ` 0 for ; 0 2 2
then u determines then 0 = .
Now we can formulate the idea how to use machine learning for the synthesis of regular event-pattern detectors.
Let us assume that for the system being designed, an expert community has found some nite set T = f(uk; k) 2 + j k = 1; : : : N g such that the subset fuk j k = 1; : : : N g + is pre x-free, in other words, for any 0 < k 6= l N , neither uk is a pre x of ul nor ul is a pre x of uk . Then we need to nd a regular event-pattern detector such that ensures uk ` k for all (uk; k) 2 T and k = 1; : : : ; N under condition that the number of states of the detector is minimal. 4
Regular Detector Synthesis Algorithm For the synthesis of a regular event-pattern detector according to the aforementioned idea, we use a two-step method. The rst step provides to build a tree-like detector DT and the second step provides to improve this detector reducing it while this is possible. The reduced completely detector D is considered as the required.
The algorithm of the rst step is presented in Alg. 1. A simple analysis of this algorithm shows that detector DT ensures u ` for some u 2 + and 2 if and only if (u; ) 2 T .
The algorithm of the second step is presented in Alg 2. A simple analysis of the presented algorithm shows 1. for any (u; ) 2 T , the deriving u ` is preserved for the detector
D ; 2. each step of the algorithm loop does not increase the number of states of the detector. 5
To evaluate the algorithm, we use an experimental environment, that randomly generates a detector D accordingly to Def. 3 based on xed alphabet , set of decisions and a number of possible states M . In these experiments we use common set of possible decisions and a common alphabet. We assign a random 2 to every possible terminal.
We use such a detector D to generate stochastically paths, ending in terminal nodes. Such paths represents the behaviour of word recognition, Data: An alphabets and and set T Result: The tree-like detector DT q0 ; Q fq0g; T = fu 2 + j (u; ) 2 T for some for u 2 T do
Q Q Sfu0 2 + j u0 is any proper pre x of ug end Q Q Sftrashg; for u 2 Q , a 2 do if ua 2 Q then
def (u; a) = ua else if (ua; ) 2 T then
def (u; a) = end for a 2 do
def (trash; a) = trash end return ( ; ; Q; q0; ); else end def (u; a) = trash
Algorithm 1: Building a tree-like detector T = f(uk; k) 2 Alg. 1. thus for every possible detector D we are able to generate a set of pairs + j 1 < k N g of recognised words T as in
For every generated detector D from the corresponding DT using the aforementioned algorithm, we generate a model detector D .
The accuracy of the synthesis is estimated as the probability to make the same decision by both detectors D and D .
Data: A tree-like detector DT
Result: The synthesised detector D
D = DT ;
for q 2 Q , a 2 do
if (q; a) = trash then
x is the result of random choice from Q S ;
redef (q; a) = x;
minimise the modi ed detector D using Hopcroft's algorithms [
Algorithm 2: Reduction algorithm After which, we check model's accuracy based on a D. One can see in Fig. 2 that the accuracy of the implemented algorithm for a detector with the two-element set of decisions under certain circumstances can reach up to 0:891 .
In the Fig. 3, the dependence of accuracy of synthesis on the number of states of the current detector in the learning process. Summing up, we can state that the idea of using machine learning algorithms in the design of event detectors is not unreasonable. Nevertheless, this document raises a number of problems that need to be solved in the process of creating information technology for the synthesis of eventpattern detectors on the base machine learning algorithms.
Such problems include Problem 1. Is it true that D = Pr detector D ? lim DT for any regular event-pattern
T !D For the special case, when contains only two elements this statement transforms into the following statement.
Problem 2. Is it true that L = Pr for any regular language L ? lim T where T is nite and T T !L
L Problem 3. Is it possible to improve the convergence of the algorithm by considering not only the set of con rmatory samples but also the set of counterexamples?