=Paper=
{{Paper
|id=Vol-1614/paper_121
|storemode=property
|title=Machine Learning Methods and 'Real-Time' Economics
|pdfUrl=https://ceur-ws.org/Vol-1614/paper_121.pdf
|volume=Vol-1614
|authors=Vladimir Dorozhinsky,Arsen Khadikov,Nina Zholtkevych
|dblpUrl=https://dblp.org/rec/conf/icteri/DorozhinskyKZ16
}}
==Machine Learning Methods and 'Real-Time' Economics==
https://ceur-ws.org/Vol-1614/paper_121.pdf
Machine Learning Methods and “Real-Time”
Economics
Volodymyr Dorozhinsky1 , Arsen Khadikov1 , and Nina Zholtkevych2
School of Math. and Comp. Sci., V.N. Karazin Kharkiv National University1
School of Economics, V.N. Karazin Kharkiv National University2
vdorozhinsky@gmail.com
Abstract. In the paper some machine-learning method for synthesis an
on-fly event acceptor is proposed. Such an acceptor has become neces-
sary for the technique of the on-fly event processing. This technique is
increasingly being used in the design of information systems of economic
destination. In the paper the synthesis problem for such an acceptor is
considered in a rigorous mathematical formulation. The method for so-
lution of the problem and the computer experiment to study the method
are described. The directions for the further research are proposed.
Keywords: on-fly event processing, acceptor, regular language, prefix-
free language
Key Terms: Component, MathematicalModel, MachineIntelligence
1 Introduction
Modern Information Communication Technology (ICT) causes intensive
changes in, practically, all areas of human activity. These changes, in par-
ticular, impose non-traditional restrictions for decision processes in the
field of economy. New approaches for modelling economic processes such
as “econophysics” [6] are responses on these challenges in the information
society. The key reason of a huge number of the changes is a reduction
of the time scale for decision making to manage of economic processes.
This reduction can be argued that business management systems gain
more and more features inherent in real-time control systems for complex
technical objects. Thus, we may talk about real-time economic processes
and use the corresponding technique to analyse and design them on the
base of ICT. Today Event-Driven Architecture (EDA) is the generally
accepted architecture solution to construct an information system that is
scalable, adaptable, and capable to operate in real-time [3]. Mathemati-
cal fundamentals to analyse component behaviour of such a system have
been established in the papers [1, 7, 8]. The practically important class of
ICTERI 2016, Kyiv, Ukraine, June 21-24, 2016
Copyright © 2016 by the paper authors
- 470 -
message detectors for systems built on EDA has been defined and con-
sidered in [2]. The implementation of these ideas and theoretical results
in the development process of information systems for business a priori
constrained by the complexity of identifying message patterns of system
events. In such situations, the usage of the machine learning methods is
one possible way to overcome the complexity of the problem in progress of
solving it. The advantage of this approach is needlessness to construct a
general theory, covering all logically possible occasions. Instead, it creates
a mechanism to adapt the system to new situation that is not consistent
with the current knowledge of the system. The main goal of the paper is
to present the principal suggestions of our approach and the preliminary
results.
2 Basic Mathematical Model and Problem Statement
Here we describe the model proposed in [7] for a component of a system
based on EDA.
2.1 Basic Notation and Definitions
Below we use the following notation:
f : X 99K Y denotes that f is a partial mapping from X into Y ;
f (x) ↑ denotes that f (x) is not defined for the member x of
X;
f (x) ↓ denotes that f (x) is defined for the member x of X;
f (x) ↓= y denotes that f (x) ↓ and y = f (x) for the member y of
Y;
denotes the empty (zero-length) sequence;
X+ denotes the set of all non-empty finite sequences com-
posed of elements ofSX;
X∗ denotes the set {} X + ;
Xω denotes the set of all infinite sequences composed of
elements of X;
X∞ denotes the set X ∗ X ω ;
S
|x| denotes the length of the finite sequence x;
x[0] denotes the first element of a finite or infinite sequence
x;
x[1 : ] denotes the sequence obtained by removing the first
element of the sequence x.
- 471 -
Definition 1. For a finite set X a subset L of X ∗ is called a language
and, in the context, X is called an alphabet, and its members are called
symbols.
We interpret symbols as a prime messages informing that the correspond-
ing elementary event has happened. Some finite sequences of symbols in-
form about complex events and below these sequences are called events.
Other finite sequences of symbols do not carry information about com-
plex events and below we call them words. Sets of complex events must
meet the certain conditions. The most important of these conditions is
that any stream of elementary events is uniquely subdivided into a series
of complex events by directed viewing the stream from left to right. This
condition leads to the requirement that L is prefix-free [7]. Now we can
require that any set of complex events related with a system would be
prefix-free.
2.2 Mathematical Model
Let us briefly remind the principal tenets of the used model. Any com-
ponent of a system based on EDA is modelled by using the concept of a
CEP-machine.
Definition 2 (Structure of CEP-machine). Any CEP-machine is a
quintuple M = (X, Y, H, h0 , α) with the following constituents:
– the alphabet of atomic messages X, which is a finite set;
– the alphabet of machine responses Y , which is a finite set;
– the set of handlers H, which is a finite set, whose each member is
a partial mapping h : X + 99K Y such that its domain is a prefix-free
language;
– the initial handler h0 , which is some fixed element of H;
– the response function α, which is a mapping with domain Y and
codomain H.
The general behaviour of any CEP-machine is described in [7]. However
in the general case it is possible that a CEP-machine can become hung
while trying to recognize an event. But in our study we consider simpler
case, which was first considered in [2]. In this case the situation, when
the CEP-machine is hanging, is impossible. To specify this special case
we are in need in the following definition.
Definition 3 (Regular handler). A handler h : X + 99K Y is called
regular if there exist some finite set Z with the marked element z0 ∈ Z
- 472 -
and some mapping δ : Z × X → Z Y such that for any u ∈ X + and
S
y ∈ Y the condition h(u) ↓= y is fulfilled iff there exist z1 , . . . , z |u|−1 ∈ Z
such that
zi+1 = δ(zi , u[i]) for 0 ≤ i < |u| − 1 and
y = δ(z |u|−1 , u[|u| − 1]).
In this case we say that the handler h is realized by the triple (Z, z0 , δ).
Remark 1. It is evident that a handler is regular if there exist a finite
state machine realising it.
Definition 4 (Regular CEP-machine). A CEP-machine is called reg-
ular if all its handlers are regular.
2.3 Problem Statement
In practice we propose restrict our technique by methods of synthesis
for regular CEP-machines. This restriction is caused by technical and
theoretical difficulties of more general technique. Further, it is evident
that the synthesis problem for a regular CEP-machine is decomposed into
series of synthesis problems for regular handlers each of which has only
one possible response “accepted”. In this case we use the term “a regular
acceptor” instead the term “a regular handler”. Thus, a machine-learning
problem for synthesis process of a regular handler can be formulated in
the following manner.
Problem. Let E = {u1 , . . . , uM } be a finite prefix-free set of finite se-
quences composed by elements of X and C = {v 1 , . . . , v N } T
be a finite set
of finite sequences composed by elements of X such that E C = ∅ then
we interpret elements of set E as examples and elements of set C as coun-
terexamples; we need to find a regular acceptor h : X + 99K {accepted}
such that
1. h(ui ) ↓= accepted for all 0 ≤ i < M ;
2. h(vi ) ↑ for all 0 ≤ i < N ; and
3. the corresponding set Z has the least number of elements among all
possible.
3 Progress Review
Here we present a method to build a regular acceptor and describe a
computer experiment that instills confidence in the existence of a math-
ematical justification for this method.
- 473 -
3.1 Some Theoretical Background
We premise our presentation with a few simple theoretical results. The
techniques used to prove these results are quite common in automata
theory therefore we omit the corresponding proofs for simplicity of the
presentation. First of all, let us return to Remark 1 and discuss more de-
tail the interrelation between regular acceptors and finite state machines.
Namely, if we consider for any regular acceptor h : S X+ S99K Y that re-
alized by the triple (Z, z0 , δ) the machine (Q = Z S Y {qtrap }, X, δ :
Q × X → Q, q0 = z0 , Qaccept = Y ) where qtrap ∈ / Z Y and δ(y, x) =
qtrap ; δ(qtrap , x) = qtrap for any x ∈ X and y ∈ Y then the regular lan-
guage accepted by this machine coincides with the set of events accepted
by the regular acceptor. After this brief theoretical review, we can return
to our problem.
3.2 Proposed Method
The general view of the method to find an acceptor is presented by Alg. 1.
This method consists of the series of redirections for acceptor transitions
leading into the trap starting with the minimal acceptor for the set of
examples. Two functions used by the algorithm init and modify are
specified separately.
To complete the specification of the proposed method we need to
describe algorithms for the function init (see item 3 of the Alg. 1) and
for the function modify (see item 7 of the Alg. 1).
Function init. To build the minimal acceptor the following ideas are
used:
1. states of the acceptor are defined recursively as special sets of words;
2. we choose the set E as z0 and add it to Z;
3. we choose the empty set as trap;
4. if for x ∈ X in E there is not a word with the first symbol x then
assign δ(z0 , x) = trap else the set {u ∈ X ∗ | xu ∈ E} add to Z;
5. repeat recursively this consideration for all member of Z until Z is
stabilized;
6. denote the set {} by accepted.
The acceptor obtained in this manner is assigned as a result of the func-
tion init.
- 474 -
Algorithm 1. Specification of the proposed method
1 def learning method(E, C):
Require : the finite prefix-free set of events E
the finite set of words that are not events C
Ensure : the required acceptor
2 do that:
3 initiate the learning process by applying function init to the set E
and denoting the result by acceptor
# initialize the set of transitions that cannot be redirected
4 frozen transitions = set()
5 while halting condition is not fulfilled:
6 do that:
7 modify acceptor by redirecting a transition leading into the trap
and minimize the resulting acceptor wherein the redirected
transition cannot belong to frozen transitions
8 do that:
9 check that acceptor is admissible in the sense that it does not
accept any word from C
10 if the checking is successful: continue
11 else:
12 do that:
13 roll-back the modification and add the redirected transition
into frozen transitions
Function modify. To select a transition for redirection we use the fol-
lowing simple remark: the minimal regular acceptor has at most one state
that is an attractor, i.e. any transition that goes out from this state has
this state as a target. Moreover, if this acceptor accepts a finite language
then the existence of the attractor is guaranteed. Further, to minimize
the new acceptor we use standard Hopcroft’s algorithm [4].
3.3 Computer Experiment Schema
Thus, we assume that the described above method gives a solution of
our problem. To check reasonability of this assumption we designed the
computer experiment for searching counterexamples to the assumption.
The Alg. 2 specifies the schema of the experiment.
3.4 Case Study
To implement the mentioned experimental schema we have used language
Python with libraries “scipy” and “numpy” [5]. Particularly, all random
- 475 -
Algorithm 2. The schema of the computer experiment
1 for in range(given number of experiments):
2 do that:
3 generate randomly a regular acceptor acceptor
4 do that:
5 generate randomly sets E and C using acceptor
6 acceptor0 = learning method(E,C )
7 do that:
8 compare acceptor0 and acceptor
choices have been provided by the standard function random.choice con-
tained in the library “numpy”. To randomly generate a regular expression
the following schema has been used. An expression is represented by a
syntactic tree. Each leaf of this tree is marked by a token and each in-
ternal node of the tree is marked by a functor. Moreover, the number of
children for an internal node equals the arity of the corresponding func-
tor. The recursive structure of the syntactic tree that represents some
regular expression indicates the way of this tree random generation. To
make decision whether the root of the current subtree is an internal node
or a leaf we propose to use the following function p(n) that determines the
conditional probability to mark the current node as internal if its depth
is equal to n
1 n 2
1− if 0 ≤ n < µ
p(n) = 2 µ .
1 n
exp 1 − if n ≥ µ
2 µ
The results of the more than 10,000 experiments have shown that for a
randomly generated acceptor with the obtained sets E and C, the pre-
sented method of learning was restoring this acceptor using these sets.
Thus, we can assume that the proposed method is precise on regular ac-
ceptors. The last assumption can be considered as evidence in favour of
the validity of the proposed method of machine learning.
4 Conclusion and Future Study
The presented paper cannot be considered as a complete research. The ob-
tained results are preliminary, but they are very important because they
- 476 -
demonstrate a chance to substitute the complete logical analysis of situa-
tion by the learning on the examples and counterexamples during software
development of the on-fly processing systems. Also these results make the
need for further research in the following directions: future experimental
study of the proposed method in order to clarify the boundaries of its
applicability; finding rigorous formulations of the method convergence
conditions; mathematical justification of the method; evaluation of the
effectiveness of the method.
Acknowledgement. The authors thank Prof. Gregoriy Zholtkevych for
the idea proposed to them: to use machine learning methods for the syn-
thesis of the logical structure of the on-fly event processing mechanism.
References
1. Dokuchaev, M., Novikov, B., Zholtkevych G.: Partial Actions and Automata. Alg.
Discr. Math. 11(2), 51–63 (2011).
2. Dorozhinsky, V.: Regular Complex Event Processing Machines. Systemy obrobky
informacii. 8, 82–86 (2015).
3. Etzion, O., Niblett, P.: Event Processing in Action. Manning Publications (2010).
4. Hopcroft, J.: An n log n algorithm for minimizing states in a finite automaton. In:
Proc. Internat. Sympos., Technion, Haifa. Theory of machines and computations,
pp. 189–196. Academic Press, New York (1971)
5. Scientific Computing Tools for Python. http://scipy.org/
6. Stanley, H.E.: Interview on Econophysics. Published in: “IIM Kozhikode Society
& Management Review”, Sage publication (USA). 2(2), pp. 73–78 (2013) http:
//www.saha.ac.in/cmp/camcs/Stanley-interview.pdf.
7. Zholtkevych, G., Novikov, B., Dorozhinsky, V.: Pre-Automata and Complex Event
Processing. In: V. Ermolayev et al. (eds.) ICTERI 2014. CCIS, vol. 469, pp. 100–
116. Springer International Publishing, Switzerland (2014).
8. Zholtkevych, G.: Realisation of Synchronous and Asynchronous Black Boxes Using
Machines. In: V. Yakovyna et al. (eds.) ICTERI 2015. CCIS, vol. 594, pp 124–139.
Springer International Publishing, Switzerland (2016).