=Paper=
{{Paper
|id=Vol-2858/short8
|storemode=property
|title=Application of binary dynamical systems in the problem of classification of Boolean vectors
|pdfUrl=https://ceur-ws.org/Vol-2858/short8.pdf
|volume=Vol-2858
|authors=Gennady Oparin,Vera Bogdanova,Anton Pashinin
|dblpUrl=https://dblp.org/rec/conf/aicts/OparinBP20
}}
==Application of binary dynamical systems in the problem of classification of Boolean vectors==
https://ceur-ws.org/Vol-2858/short8.pdf
Application of binary dynamical systems in the problem of
classification of Boolean vectors
G A Oparin, V G Bogdanova and A A Pashinin
Matrosov Institute for System Dynamics and Control Theory SB RAS, Lermontov St.
134, Irkutsk, Russia, 664033
bvg@icc.ru
Abstract. The article proposes a method based on using binary dynamical systems in the
classification problem for Boolean vectors (binary feature vectors). This problem has practical
application in various fields of science and industry, for example, bioinformatics, remote
sensing of natural objects, smart devices of the Internet of things, etc. Binary synchronous
autonomous nonlinear dynamic models with an unknown characteristic matrix are considered.
Matrix elements are chosen in such a way that the Boolean reference vectors are equilibrium
states of the binary dynamic model. The attraction regions of equilibrium states act as classes
(one reference vector corresponds to each class). The classified vector is the initial state of the
model. Simple and aggregated classifiers are considered. The proposed method is demonstrated
using an illustrative example.
1. Introduction
The development of methods based on using dynamic models is one of the promising research areas in
solving the classification problem for various object types [1]. The principle of these methods is that
the memorized reference objects are the equilibrium states of a dynamic model, and the classes
represent attraction regions of the corresponding equilibrium states. The tuning process for the
dynamic model consists of selecting such values of its parameters that ensure in this model the
presence of the required set of equilibrium states (attractors) with given quantitative characteristics of
their regions of attraction (basins), as well as the required dynamics of the model's functioning.
The study aims to apply this approach to the Boolean feature vectors classification problem based
on parameterized binary dynamic models. The use of such models determines the novelty of our
method. Boolean feature vectors that need to be matched with one class or another are the initial
conditions for a binary dynamical system. The classifier work result is the equilibrium state, to which
the trajectory converges with the given initial conditions. If this equilibrium state belongs to the set of
reference Boolean vectors, then the classification problem has a positive solution. Otherwise, the input
binary feature vector does not belong to any of the predefined classes.
Many practical problems in various fields of science and technology, in particular,
bioinformatics [2], remote sensing of natural objects [3], smart devices of the Internet of things [4],
and others are reduced to the classification of Boolean vectors.
The development and analysis of a Boolean features system are critical in the classification
theory [5], but they are subject-oriented and are not considered further.
_____________
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0
International (CC BY 4.0).
The article is structured as follows. Section 2 provides a brief overview of the use of dynamic
models in solving the classification problem. The statement of the classification problem for Boolean
vectors is formulated in Section 3. In Section 4, the method for solving this problem is proposed. This
method application using a nonlinear binary dynamic model is demonstrated with an illustrative
example in Section 5. In the final section 6, the advantages of the proposed method are presented.
2. Related work
The well-known Hopfield neural network [6] and its development, the Hamming neural network [7],
are among the most famous examples of the application of dynamical systems in the problem of
classifying binarized objects. In the Hopfield model, reaching an equilibrium state does not guarantee
the correct response of the network (the network converges to the so-called false attractors). The
correct answer is an equilibrium state that matches one of the reference binary vectors. The Hamming
network, unlike the Hopfield network, does not give out the reference vector but its number. If there
are several such numbers, a conclusion is made about the impossibility of assigning the input vector to
a specific class. However, the obtained numbers indicate the most similar reference vectors. Compared
to the Hopfield network, the Hamming network is characterized by lower memory and computational
costs. Improved Hopfield and Hamming network models have found the application for solving a wide
range of problems from various fields of knowledge [2-4, 8, 9].
In addition to traditional models of neural networks, in which fixed points are attractors, models of
so-called chaotic neural networks [10] are proposed, the most famous of which is Freeman's KIII
model [11]. In such networks, the reference vector does not correspond to an equilibrium state, but to a
cycle (oscillation between the reference and its inversion). For the “I don’t know” state the dynamics
of the network is chaotic (chaotic attractor). Chaotic neural networks are a special kind of dynamic
neural network models in which deterministic chaos plays a key role in the classification process.
Some areas of their application can be found in works [12-13].
In practice, using both types of networks is associated with high computational costs for computer
modeling of systems of differential or difference equations. One of the main reasons for this is the
need to use data of a real type and, accordingly, slow operations on them. The use of binary dynamic
models allows the reducing computational costs. These models provide all transformations necessary
for solving the classification problem using high-speed Boolean operations on binary variables.
3. Problem statement
We consider a nonlinear binary dynamic system of the following form:
x(t 1) A x(t ), x(0) x 0 , (1)
where t 0,1,2,... is the discrete time, x(t ) col( x1 (t ), x2 (t ),...xn (t )) is the state vector,
x(t ) B n , B {0,1} , B n is the state space of system (1), A is an unknown binary matrix of dimension
n n , the symbol means the conjunctive product of two matrices defined as
C A B, where c ik j (aij b jk ).
A set of reference Boolean vectors is given as
P { p1 , p 2 ,..., p m } , where p i col( p1i , p2i ,..., pni } , p ij {0,1} , i 1, m , j 1, n .
It is required for system (1) to find such matrix A* that the set P belongs to the set of equilibrium
states of the system
x(t 1) A* x(t ) . (2)
Further, using system (2), it is necessary to match the Boolean vector x 0 B n to one of the
reference Boolean vectors from the set P (one reference vector from P corresponds to each class), or to
conclude that the vector x 0 does not correspond to any of the reference vectors.
4. Solution method
Each reference vector from the set P must be an equilibrium state of the system (1), and therefore
satisfy the system of nonlinear Boolean equations
p i A p i , i 1, m (3)
with n2 unknown variables, elements of the matrix A. The number of scalar equations in system (3) is
equal to m n .
It is known that system (3) is reduced to a single Boolean equation 1 ( A) 1 . The function 1 ( A)
is easy to represent in conjunctive normal form, which makes it possible to use efficient AllSAT
solvers to find solutions [14].
Depending on a given set of reference vectors P, an equation 1 ( A) 1 can have a single solution,
many solutions, and none. In the last case, the classification problem for the set of reference Boolean
vectors P cannot be solved using the proposed method.
With a plurality of solutions, it is possible to add to constraint (3) additional requirements regarding
the dynamics of system (1) and the size of the region of attraction of reference vectors:
1. Each row of the matrix A must contain exactly one 1. The corresponding Boolean constraint is
written as 2 ( A) 1 . This condition ensures that for each scalar equation of system (1) there
is only one variable in the right side, which makes it possible to solve the classification
problem for any x 0 B n in one step (the radius of the region of attraction of each equilibrium
state, including for the reference vector, is equal to one).
2. The number k of zero columns in the matrix A must be maximum ( k k max ). This condition
allows to obtain the maximum region of attraction, equal 2 kmax 1 states, for each reference
vector. We can write the Boolean constraint on the presence of k zero columns in the matrix A
as an equation 3k ( A) 1 .
All three constraints are reduced to one Boolean equation
CNF 1 ( A) 2 ( A) 3k ( A) 1 . (4)
An iterative process for searching k max is organized for the parameter k using the well-known
interval halving method. In a considered problem, such an interval is a set of integers from 0 to n-1.
The calculation of all solutions to equation (4) (or identification of their absence) for a given k is
performed by the AllSAT solver [14].
If k max 0 and equation (4) is solvable with respect to A, the solution matrix A* will be permutable
(exactly one 1 in a row and the absence of zero columns). In this case, all equilibrium states will be
isolated (with empty regions of attraction) and a one-step classification is meaningless.
If k max 0 two ways are possible:
1) The equation (4) has one solution A*. Then if for a given initial vector x 0 B n there is a
vector x1 A* x 0 P , then the classification problem for the vector x 0 is solved,
otherwise none of the reference vectors corresponds to the vector x 0 . Such a classifier with a
single matrix A* is called a simple classifier.
2) Equation (4) has many solutions A1* , A2* ,..., Aq* . This case corresponds to an aggregated
classifier, which is an ensemble of simple classifiers:
x11 A1* x 0 , x12 A2* x 0 ,..., x1q Aq* x 0 .
If these vectors x11 , x12 ,..., x1q are pairwise equal and x11 P , then belonging of x 0 to a certain class
is established. If for all i 1,2,...,q x1i P , then none of the reference vectors is comparable to the
vector x 0 . We will say that the aggregated classifier produces a deterministic solution if one of these
two conditions is satisfied. Otherwise, we have a probabilistic solution when, based on the analysis of
vectors x11 , x12 ,..., x1q , the probability of a vector x 0 belonging to a particular class or the probability of
the absence of a property of belonging to any class is calculated. In this case, the aggregated classifier
produces a probabilistic solution. Suppose the input vector x 0 is comparable with reference vectors
b P and c P with probabilities correspondently of 0.3 and 0.5. Additionally, x 0 is not matched
with any reference vector from the set P with a probability of 0.2. The sum of these probabilities is 1.
The software implementation of the proposed technology for classifying Boolean vectors is based
on the HPCSOMAS framework [15] in the form of a set of composite microservices [16]. These
microservices implement some functions of the Boolean constraints method in the qualitative analysis
of binary dynamical systems [17].
HPCSOMAS automates the creation of microservices based on application modules and managing
their execution in a distributed computing environment. This framework also provides post-processing
tools, in particular, graphical visualization of the results.
5. Illustrative example
It is required to construct a classifier for five (m = 5) reference Boolean vectors p1 , p 2 ,..., p 5 of
dimension n = 9 (table 1). The list of input vectors to be classified is given in table 2.
Table 1. Reference vectors.
Binary features
Reference
1 2 3 4 5 6 7 8 9
P1 0 1 0 0 1 0 0 1 0
P2 1 1 1 1 0 1 1 0 1
P3 1 0 1 1 1 1 1 0 1
P4 1 1 1 1 0 0 1 0 0
5
P 0 0 0 0 1 0 0 0 0
We synthesize CNF in the DIMACS format [18] from equation (4) and start the search k max
procedure with simultaneous calculation of all solutions to equation (4) using the AllSAT solver.
Applying this procedure, we obtain k max 4 and 8 matrices A* shown in figure 1. Each matrix has
exactly one 1 in each row and 4 zero columns.
Table 2. Input vectors.
Binary features
x0
1 2 3 4 5 6 7 8 9
s1 0 0 1 1 1 1 1 0 1
2
s 0 0 1 0 1 0 0 0 0
s3 0 0 0 0 1 0 0 1 0
Let us consider the construction of a simple classifier using a matrix A3* as an example (figure 1).
Based on the matrix A3* , we write the binary dynamical system (2) in scalar form:
x1t 1 x 7t , x 2t 1 x 2t , x3t 1 x7t ,
x 4t 1 x 7t , x5t 1 x5t , x 6t 1 x 6t , (5)
x 7t 1 x 7t , x8t 1 x8t , x9t 1 x 6t .
Figure 1. All founded matrixes A1* , A2* ,..., A8* .
Using HPCSOMAS services, we perform the following actions:
Search for equilibrium states;
Verifying the presence of reference vectors among these states;
Verifying the isolation property for reference vectors;
Search for its attraction regions (basins);
Visualization of reference vector basins.
Figure 2 shows 32 found equilibrium states in the output DIMACS format of SAT solver. In these
format, variables x10 , x20 ,..., x90 , x11 , x12 ,..., x19 are encoded by one-dimensional indexes
1, 2, ..., 9, 10, 11, ...,18 . Indexes are calculated for x it using the formula i nt, i 1,9, t 0,1, n 9 .
These indexes are positive or negative if the x it is equal correspondently to 1 or 0. For example, the
reference vector p5 (0 0 0 0 1 0 0 0 0) is shown for t = 0 as (-1 -2 -3 -4 5 -6 -7 -8 -9) in figure 2. The
value 0 denotes the end of a string in DIMACS format. Reference vectors are highlighted in bold.
The isolation property for these vectors is not satisfied. Therefore reference vectors are attractors of
the system (5). Figure 3 shows the basins of these attractors including 15 states. In figure 3, the
i1 ai 2i1 , where a1a 2 ...a9 - the
9
decimal values of the states are calculated by the formula
corresponding binary state values.
The analysis of the attractor regions in Figure 3 shows that the classifier has the property of
correctly recreating the reference vector for a highly distorted input Boolean vector x 0 .
We use a simple classifier to match the input vectors s1, s2, s3, presented in table 2, with the
reference ones. As a result, the response of system (5) to the vector s1 coincides with the reference
vector p3 and to the vector s2 - with the reference vector p5. The response to the vector s3 does not
coincide with any of the reference vector.
Figure 2. Equilibrium states. Figure 3. Visualization of basins of reference vectors.
We use the aggregated classifier to match the input vectors s1, s2, s3, s4, s5, s6 (table 3) with the
reference ones.
Table 3. Input vectors.
Binary feature
x0
1 2 3 4 5 6 7 8 9
1
s 0 0 1 1 1 1 1 0 1
s2 0 0 1 0 1 0 0 0 0
s3 0 0 0 0 1 0 0 1 0
4
s 0 1 1 1 0 1 1 0 0
5
s 0 1 1 0 1 0 0 1 1
s6 0 1 1 1 0 1 0 0 1
The classification results are shown in table 4. The response of system (5) to the vector s1 coincides
with the reference vector p3 with probability 3/4, to the vector s2 - with the reference vector p5 also
with the probability 3/4, to the vector s6 - with the reference p2 with probability 1/2, and on the vector
s5 - with the reference p1 with probability 3/8. The response of the system (1) to the vector s3 does not
coincide with any reference vector, and for the vector s4 it is revealed that it belongs to different
classes - p2 and p4 with the same probability 3/8.
Table 4. Results of the aggregated classifier operation.
Simple classifier
x0
A1* A2* A3* A4* A5* A6* A7* A8*
s1 p3 p3 p3 p3 p3 - - p3
s2 - p5 p5 p5 - p5 p5 p5
s3 - - - - - - - -
s4 p2 p2 p2 p4 p4 - - p4
s5 - p1 p1 - - - p1 -
s6 p2 p2 - p2 p2 - - -
6. Conclusion
Boolean vectors classification method based on the use of binary nonlinear dynamical systems is
proposed. The software implementation of this method is performed using the HPCSOMAS
framework. An example of using the developed software is considered.
The advantages of the proposed method lie in the simplicity of tuning the binary dynamic system to
a given set of reference vectors, solving the classification problem in one step of the dynamic system
functioning, as well as calculating the probability of belonging the input vector x 0 to each of the
specified classes of the set P. Additionally, in our model (in contrast to the Hopfield model), there are
no false attractors, which significantly speeds up the classification process.
Despite the fact that all actions of the proposed algorithm are performed on binary values using
only Boolean algebra operations, such a classifier has good generalization abilities and is capable of
correctly recreating the reference for a strongly distorted input Boolean vector x 0 .
Acknowledgments
The study was supported by the Ministry of Science and Higher Education of the Russian Federation,
project no. 121032400051-9. The authors would like to thank Irkutsk Supercomputer Center of SB
RAS for providing the access to HPC-cluster "Akademik V.M. Matrosov" [19].
References
[1] Andreyev Yu V, Dmitriev A S and Matveev M A 1995 Application of chaotic dynamical
systems to the problems of recognition and classification Proc. of the 3rd Int. Workshop
NDES-95, Dublin, Ireland pp 249–252
[2] Conforte A J, Alves L, Coelho F C, Carels N and Silva F A B 2020 Modeling basins of
attraction for breast cancer using Hopfield networks Frontiers in Genetics 11 314
[3] Khristodulo O I, Makhmutov A A and Sazonova T V 2017 Use algorithm Based at Hamming
Neural Network Method for Natural Objects Classification Procedia Computer Science
103 388–395
[4] Boriskov P 2020 IoT-oriented design of an associative memory based on impulsive Hopfield
neural network with rate coding of LIF oscillators Electronics 9 1469
[5] Hancock J T and Khoshgoftaar T M 2020 Survey on categorical data for neural networks J Big
Data 7 28
[6] Hopfield J J 1982 Neural networks and physical systems with emergent collective
computational abilities PNAS 79 (8) 2554–2558
[7] Lipman R 1987 An introduction to computing with neural nets IEEE Acoustic, Speech and
Signal Processing Magazine 4 (2) 4–22
[8] Cantini L and Caselle M 2019 Hope4Genes: a Hopfield-like class prediction algorithm for
transcriptomic data Sci Rep 9 337
[9] Koutroumbas K and Kalouptsidis N 2005 Generalized hamming networks and applications
Neural Networks 18(7) 896–913
[10] Andreyev Yu V, Belsky Yu L and Dmitriev A S 1992 Information processing in nonlinear
systems with dynamic chaos Proc. Int. Seminar Nonlinear Circuits and Systems Moscow,
Russia vol 1 pp 51–60
[11] Freeman W J 1987 Simulation of chaotic EEG patterns with a dynamic model of the olfactory
system Biological Cybernetics 56 139–150
[12] He Y and Wang L 2000 Chaotic neural networks and their applications Proceedings of the 3rd
World Congress on Intelligent Control and Automation (Cat. No. 00EX393), Hefei, China
vol 2 pp 826–830
[13] Velichko A 2020 Neural network for low-memory IoT devices and MNIST image recognition
using kernels based on logistic map Electronics 9 1432
[14] Toda T and Soh T 2016 Implementing Efficient All Solutions SAT Solvers ACM Journal of
Experimental Algorithmics 21(1) 1–44
[15] Oparin G A, Bogdanova V G, Pashinin A A and Gorsky S A 2019 Microservice-oriented
approach to automation of distributed scientific computations Proc. of the 42st Int.
Convention on Information and Communication Technology, Electronics and
Microelectronics, MIPRO 2019, Opatija, Croatia pp 253-258
[16] Oparin G A, Bogdanova V G and Pashinin A A 2020 Automated tools for the development of
microservice compositions for hybrid scientific computations Proceedings of the 2nd
International Workshop on Information, Computation, and Control Systems for Distributed
Environments, Irkutsk, Russia pp 201–213
[17] Oparin G, Bogdanova V and Pashinin A 2019 Qualitative analysis of autonomous synchronous
binary dynamic systems MESA 10(3) 407–419
[18] Satisfiability suggested format. [Online]. Available:
http://beyondnp.org/static/media/uploads/docs/satformat.pdf
[19] Irkutsk Supercomputer Centre of SB RAS. [Online]. Available: http://hpc.icc.ru