See discussions, stats, and author profiles for this publication at: [Link]

net/publication/320550516

Machine learning methods: An overview

Article · January 2015

CITATIONS READS

37 9,340

1 author:

Ravil I. Mukhamediev
Kazakh National Technical University
79 PUBLICATIONS 576 CITATIONS

SEE PROFILE

All content following this page was uploaded by Ravil I. Mukhamediev on 11 October 2022.

The user has requested enhancement of the downloaded file.

COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

Machine learning methods: An overview

Ravil I Muhamedyev
Institute of Problems of Information and Control, Ministry of Education and Science of the Republic of Kazakhstan. Pushkina 125, Almaty Kazakhstan

High School of management information systems ISMA, Lomonosov st. 1, Riga, Latvia

Corresponding author’s e-mail: [Link]@[Link]

Received 1 December 2015, [Link]

Abstract

This review covers the vast field of machine learning (ML), and relates to weak artificial intelligence. It includes the taxonomy of ML
algorithms, setup diagram of machine learning methods, the formal statement of ML and some frequently used algorithms (regressive,
artificial neural networks, k-NN, SVN, LDAC, DLDA). It describes classification accuracy indicators, the use of “learning curves” for
assessment of ML methods and data pre-processing methods, including methods of abnormal values elimination and normalization. It
addresses issues of application of ML systems at the processing of big data and the approaches of their solution by methods of parallel
computing, mapreduce and modification of gradient descent.

Keywords: machine learning learn ability preprocessing big data map reduce

1 Introduction 3.1 INDICATORS OF CLASSIFICATION ACCURACY

2 Machine learning techniques ESTIMATES
2.1 TYPES OF MACHINE LEARNING ALGORITHMS 3.2 “LEARN ABILITY” OF ALGORITHMS
2.2 SETUP OF MACHINE LEARNING SYSTEMS 4 Data preprocessing
2.3 FORMAL DEFINITION OF A MACHINE LEARNING 4.1 ELIMINATION OF ABNORMAL VALUES
PROBLEM 4.2 DATA NORMALIZING AND CENTERING METHODS
2.4 REGRESSIVE ALGORITHMS AND DATA CLASSIFICATION 5 Machine learning in Big Data management
ALGORITHMS Conclution
3 Quality assessment of machine learning systems Acknowledgment
References

1 Introduction artificial intelligence is machine learning (ML). ML is

successfully applied to solve of many kinds of problems.
The domain of Artificial Intelligence (AI) is quite extensive Nowadays ML is an established discipline in many ways.
and includes numerous directions, from logics through The methodology of application of ML considers selection
methods of text tonality analysis. Traditionally the Strong of relevant data and its pre-processing, selection of adequate
AI and the Weak Ai are distinguished. The first one is algorithms and solution quality assessment. Development of
oriented to creation of highly intelligent human-level this vast domain includes search for optimal usage of ac-
problem systems, and eventually to creation of thinking cumulated potential of big and heterogeneous data, search
machines. Such developments are financed by, DARPA [1], for rapid learning methods and analysis of application
for instance. The book [2] also may be mentioned as one of features depending on the field of application.
the first to define the notion itself of the thought and to The article describes consistently ML methods that
describe the principles of brain function in a popular way. found extensive practical application, methods of data pre-
Weak AI is oriented to creation of applications that paration and indicators of classification quality assessment
perform this or another intellectual ability of humans or and algorithms. A certain part is dedicated to big data mana-
animals. For instance, ability of safe across-country move- gement. The article consists of the following parts.
ment, beehive (ant) or distributed intelligence [3], systems Part 2 describes taxonomy of ML techniques, formal
of natural selection (referred to as genetic algorithms) etc. statement of a ML problem, some popular techniques and
Frequently, the field of intelligent agents [4] and multi-agent methodology of ML application to problems.
systems, described in detail in the research papers by Part 3 describes classification quality indicators and
Gorodetsky V.I. [5, 6] are also included herein. methodology of learning curves application in assessment
In the course of development, AI, being at the cutting-
of ML systems.
age of scientific research, is gradually changing its matter as
a science. If in the beginning of its development, its scope Part 4 describes methods of data pre-processing.
of interests included such problems as bio-identification, Part 5 is dedicated to ML techniques application in big
text recognition, etc., later on they transformed into the data management.
scope of technologies widely used in applied sciences, deve- The conclusion briefly resumes the describe techniques
lopments and industries [7]. One of successful directions of and methodologies.

14
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

2 Machine learning techniques recognition of an expected path; recognition problems of

face, facial gestures and emotions; analysis of user activity
Data interpretation is often connected to classification, when data from e-commerce systems, which allows to perform
a certain object is to be related to one of the previously both interface optimization and planning of system’s res-
determined classes, to clustering, when objects are split into ponse. In broader terms, this is a data analysis in different
initially undetermined groups (clusters) and to forecasting, information systems, letting forecast status and classify-
when by some volume of initial data describing the process cation of objects. Solution approaches of this problem differ.
background, for example, it is necessary to determine its UL techniques solve the problem of clustering, when the
future state in space or in time. In all the cases, when no range of initially undetermined objects is split into groups
strict formal techniques of classification or clustering are by means of automatic procedure based on the properties of
used, ML techniques are used extensively. these objects. Whereas the number of groups (clusters) may
ML techniques include a vast class of algorithms, starting be given in advance or generated automatically. Such algori-
with solution trees, genetic algorithms, and metric techniques, thms include the adaptive resonance theory -ART and self-
such as k-NN, SVM, statistical methods, Bayesian networks organizing maps- SOM or Kohonen maps [32], and a vast
and ending with artificial neural networks [4, 7, 8, 9]. On the group of clustering algorithms (k-means, mixture models,
merits this direction is meant to solve the central problem of hierarchical clustering etc.) [33, 34].
an intelligent system, anticipatory to all other actions – SL decide the problem of classification, when finite
assessment of a current object (situation). groups of somewhat determined objects are distinguished in
One of practical applications, where ML techniques are a potentially infinite aggregate of objects. As a rule, groups
used extensively since 1970’s is extraction of commercial are formed by an expert. Furthermore the expert can explain
minerals. For instance, artificial neural networks are applied or not the reasons of the initial classification.
in petrography for log data analysis, in lithology for asses- The algorithm of classification should put the following
sment of mineral resources base, in seismic sounding [10-17]. undetermined objects to this or another expert-organized
The research paper [18] is dedicated to application of neural group by use of the initial classification based on the
networks, the research paper [18] is dedicated to decision of properties of these objects. SL include a big number of
practical interpretation problems of oil production log data. algorithms or a class of algorithms being often divided to
The research papers [19-21] describe some results of feed-
linear and non-linear classifiers, depending on the shape
forward neural networks application for interpretation of
well-log geophysical data during uranium exploration. (hyperplane or hypersurface) of object dividing classes. In a
Still applications of ML are much more extensive. They two-dimension case, linear classifiers divide classes with the
include medicine [22-24], biology [25], robotics, municipal only straight line, whereas non-linear classifiers – with the
facilities and industry [26], service sector, ecology [27], inno- curve (Figure 1).
vative systems of communication [28], astronomy [29] etc.
Herewith the taxonomy of ML, key algorithms and
features of their application are being considered.

2.1 TYPES OF MACHINE LEARNING ALGORITHMS

ML, as a part of a vast scientific direction called Artificial

a) b)
Intelligence (AI), on the merits is implementing the
potential of AI idea. The main anticipation related to ML FIGURE 1 Linear (а) and non-linear (b) classifiers
considers implementation of demand for flexible, adaptive,
learning algorithms or methods of computation * . This Classification approaches for MO algorithms are presen-
results into new functions of systems and programs. ML ted in research papers [35, 36] in particular. Taxonomy of MO
opportunities, i.e. ability of learning and giving expert-level algorithms, not eligible for exhausttiveness, may be presented
recommendations in a narrow application domain, provide as the following below hierarchy structure (Figure 2):
algorithms, which are divided into two big groups, realizing Unsupervised learning (UL)
the main property – ability of learning: ART
 Unsupervised learning (UL) ART1
 Supervised learning (SL) ART2
On top of that, specify ART3
 Reinforcement learning [30] (RL) SOM
 Semi-supervised learning [31] (SSL) Generative Topographic Map (GTM)
The main problem decided with use of ML algorithms Cluster algorithms
involves relating the observed object to one or another class k-means
with the following automatic or manual decision generation. K-Means++
Such problems occur very frequently. As a specific illu- K-Medoids
stration may be given the problems that arise in the process Fuzzy C-Means Clustering Algorithm (FCM)
of mobile autonomous robot movement, and relating to Soft K-Means Clustering Algorithm (SKM)

*
Methods of computation is the term that introduced by Donald Knuth
to separate mathematically validated algorithms and empirical methods
that frequently used in practice

15
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

K-Harmonic Means Clustering Algorithm (KHM) Support Vector Classification (SVM) (Linear SVM и
Kernel K-Means Clustering Algorithm (KKM) Non-linear SVM)
Spectral Clustering Algorithm (SCA) Logistic regression (LogR)
Density models (DM) k-Nearest-Neighbor (k-NN)
Subspace models: Decision Tree (DT)
mixture models (MM), Random Forest (RF)
hierarchical clustering (HC) Neural Networks (NN)
Supervised learning (SL) Bayesian Networks (BN)
Linear Classifiers Reinforcement learning (RL)
Linear Discriminant Analysis Classifier (LDA) Q-Learning
Logical regression (LR) Deterministic Q-Learning (DQL)
Naive bayes Classifier (NBC) Monte-Carlo Methods (MCM)
Perceptron (P) Temporal Difference Methods (TDM)
Non-linear Classifiers Sarsa
Quadratic Classifier (QC) Semi-supervised learning (SSL)
Diagonal Linear Discriminant Analysis (DLDA)

Taxonomy of ML algorithms

Machine Learning
Semi-
supervised
learning
Unsupervised learning
Reinforcement
SCA learning

ART SOM Supervised learning

Cluster Q-
DM learning MCM
algorithms
ART1
GTM Subspace DQL TDM

ART2 models Linear Non-Linear

K-means Sarsa
classifier classifier
MM
K-Means++
LDA Quadratic Classifier
HC
K-Medoids
LR DLDA

FCM
NBC SVM

SKM
Perceptron LogR

KHM
K-NN

KKM
NN
FIGURE 2 Taxonomy of machine learning algorithms
Each of the mentioned algorithms, in fact forms a kind 2.2 SETUP OF MACHINE LEARNING SYSTEMS
of flock, modified according to these or another needs of
programs and algorithms that often differ by computational Application of ML techniques in the problems that do not
complexity, difficulty of implementation and learning operate any pure mathematical models, only data and
process automation, ability to classify only two types probably expert estimates, is often an optimal way of
solution. A learning system, an artificial neural network in
(binary classification) or several types of objects at once.
particular, is able to reproduce the behavior being difficult
Classification and other kind heterogeneous data pro- or impossible to formalize. In supervised learning problems
cesssing feature a range of peculiarities: it is often difficult to determine the quality of expert esti-
1) Data heterogeneity that will require introduction of mates. In a point of fact these problems include also the
different metrics for certain types of data in some cases problems of disease risk detection, product quality asses-
2) Frequent occurrence of big data volumes, when a sment, speech recognition, prediction of share quotation
problem must be solved relatively fast for incoming level in financial markets, the problem of lithology type
data portions, which obviously troubles the use of recognition, etc. Notwithstanding the experts give a list of
computationally complex learning techniques relevant features, ranges of measured physical quantities,
3) Complexities of results integration. expert estimates may be contradictory or display errors.
Besides, classification data may contain abnormal
values and mistakes, related to physical peculiarities of their

16
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

acquisition processes. Consequently a learning system can and comparison of algorithms against each other are a ne-
treat data with mistakes. cessary condition for development of scientifically proven
Analysis of ML techniques applicability, methods of automatic data interpretation software system.
data processing for application of the mentioned methods, The general diagram of ML alignment by active problem
is presented in Figure 3.

FIGURE 3 Generalized algorithm of a machine learning system alignment by active problem

The alignment technology is an interactive procedure, algorithm), which calculated a y(x) value by an object x (or
when correct functioning of the system requires multiple „close enough” value, if an inaccurate solution is considered
returns to the previous alignment blocks of parameters. acceptable).
According to this diagram we need to specify the very For a finite aggregate Y ={1,2,…,l}, a problem is called
problem of ML in formal form, to select algorithms to be a classification problem (per l non-intersecting classes). In
used in the system, to define quality parameters of ML this case it may be considered that a set X is split to classes
algorithms, to choose and to validate the methods of data K1,…,Kl , where Ki = {xX | y(x) = i} at i{1,2,…,l}:
pre-processing.
l

2.3 FORMAL DEFINITION OF A MACHINE X Ki

i 1
LEARNING PROBLEM
When Y ={(α1,…,αl ) |α1,…,αl {0,1}} speak of a
A formal statement of a ML problem (an example-base classification problem per l intersecting classes. Here i-class
learning problem or supervised learning problem) is known – Ki = {x  X | y(x) = (α1,…,αl ), αi =1}.
and to be as follows [37]. Let X and Y be two metric spaces: Frequently the loss or cost function J(A(x), y(x)) can be
X (the space of admissible objects), Y (answer or label space) used in the problem to describe how “wrong” is our answer
and a (target) function y: X →Y, specified only in the finite A(x) against a true answer y(x). In case of a classification
aggregate of points (learning selection, sample sets): problem it may be considered that.
y(x1) ,…, y(xm ) , i.e. the labels of objects x1,…, xm are
known. It requires to build an algorithm A (or "instruct" an

17
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

1, A( x)  y( x) 
J ( A( x), y( x)    j :  j   J (0 ,1 ) , (2)
0, A( x)  y( x)  j

But in a regression problem – 

where  is a learning parameter, but J (0 ,1 ) is a
 j
J  A  x  , y  x   | A  x   y  x  |
derivative of cost function by  . The sign: = means
j
or
assignment contrary to the sign of equality (=) in algebraic
J  A  x  , y  x    ( A  x   y  x )2 . expressions.
Along with this the algorithm steps are arranged so that
A problem of learning using a set of training samples initially there occurs the simultaneous change of both
presents also an optimization task, which can be decided by parameters based on the Equation (2.2) and only afterwards
search of the minimum value of a cost function J ( ) across the assignment of new values to them. Put it differently, the
all available examples, defined as the Sum of Squared algorithmic sequence of one step of algorithm to be ex-
Differences of “a forecasted” value and a real value of y pressed in pseudo code will be the following in case of two
through a wealth of examples m. Herein a hypothesis h ( x) parameters
“is profiled” to provide the minimum value J ( ) at a
certain set of parameters i   . 
temp 0 :  0   J ( 0 , 1 ) ;
 0
m

 (h ( x
1
J ( )  min (i )
)  y (i ) ) 2 , (1) 
2m i 1 temp1: 1   J ( 0 , 1 ) ;
1
where m – is an aggregate of samples, h – is a function of
0 : temp0 ;
hypothese that can be linear h  0  1 x or non-linear, for
instance h  0  1 x   2 x 2 with a varying set of 1 : temp1 ;
parameters i   . Depending on the learning parameter  , the algorithm
Running ahead may be said that adjustments of may reach the minimum (converge) or, at a too large  , not
parameters i needs that parameters x j  X (in a multi- converge.
dimensional case) were expressed in units of the same The simplest in realization, but not the most optimal in
dimension and approximately of the same value. Most terms of time complexity the “Batch” Gradient Descent
frequently normalization is used to render all the parameters algorithm uses all learning examples through each step of
in numbers of the range 0  x  1 or 1  x  1 . Basically, the algorithm. In search for parameters  instead of the
j
gradientTdescent
1 T
algorithm the matrix equation can be used
selection of a normalization function depends on a   (X X ) X y ,
problem’s class. Furthermore, the process of data prepro- T 1
where  is a vector of parameters, ( X X ) is a inverse
cessing may employ the methods that provide exclusion of T T
matrix of X X , X is a transpose matrix of X .
anomalous values, exclusion of noises, for example, high- The advantage of matrix operations is that there is not
frequency, by the way of fitting, etc. Selection of such necessary to try the parameter  and to iterate several
methods also depends on a problem class. times. The disadvantage refers to the necessity of getting the
After the parameters have been normalized and data is inverse matrix, which computational complexity is propor-
properly framed, there is performed the search of the tional to O(n3 ) , and to impossibility of getting the inverse
hypothesis function h ( x) , which minimizes the cost J ( ) . matrix in several cases.
For solution of this problem a large number of algorithms is
used, partly they are described below. 2.4.2 Polynomial regression

2.4 REGRESSIVE ALGORITHMS AND DATA Contrary to linear regression polynomial one operates non-
CLASSIFICATION ALGORITHMS linear function of the hypothesis
h  0  1 x   2 x 2  3 x3  ...   n x n , which allows to
2.4.1 Linear regression plot extrapolated curves (hypersurfaces) of complex shape,
but increases the number of parameters and computational
A linear regression problem is stated as the search for the complexity. Apart from that, the danger of "relearning"
minimum cost function (see Formula 1) under the terms that exists, when a curve becomes too complex it fits well the
a hypothesis function is a linear one h  0  1 x . Obvi- learning set, but it produces a large error across the test set.
ously that such function realizes the linear classifier. The In the case when a classifier loses its ability to generalize
gradient descent algorithm is used to obtain an optimal regularization is used to decrease the effect of high order
function h ( x) , its essence is about the consequent change values
of parameters 0 ,1 from the following equation m n

 
1
J ( )  min [ (h ( x (i ) )  y (i ) ) 2   2
j]
2m i 1 j 1

18
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

Growth of the parameter  results into extension of the Logistics classifier can be used also for the case of
ability to generalize the algorithm. The function of several classes. Here, the classifier is adjusted separately for
hypothesis turns into the straight line within limits at a very each class. The class, which a new object belongs to, is
large value of the parameter. computed by value calculation of all functions of hypothesis
and selection of maximum rated value among them
2.4.3 Logistic regression
max h (i ) ( x) , where i is a class number.
i
It is used if objects have to be divided into two classes, for Put it differently, the object belongs to the class with the
instance, to "negative" and "positive". In this case the maximum function of hypothesis.
function of hypothesis requires fulfillment of the condition Same as in case of a linear regression, regularization is
0  h ( x)  1 , which is achieved with use of a sigmoid used to increase the generalizing ability of the algorithm
(logistic) function
m
 n

y 
1
J ( )  [  (i )
log h ( x (i ) )  (1  y (i ) ) log(1  h ( x (i ) ))]  2
j
1 m 2m
h ( x)  , i 1 j 1

1  e
T
x
2.4.4 Artificial neural networks
where  - a vector of parameters
Can be expressed also as Artificial neural networks (ANN) is an apparatus being
actively researched since 1940’s. NN, as a part of the theory
h ( x)  g (T x) , of connectionism, has passed the prominent path from the
epoch of overestimated expectations, afterwards, through
where g ( z ) - a sigmoid function.
the epoch of disappointments in 1970’s, to a widely appli-
Let us remark that a sigmoid function also is widely used
cable technology at present. The link between biological
in neural networks as an activation function of neurons, as it
neurons and opportunities of their modeling with use of
is continuously differential and hence guarantees conver-
logistic computations is stated in the paper Warren S.
gence of algorithms of neural network learning. The sample
McCulloch, Walter Pitts [40], in the Rosenblatt’s paper [41]
of a sigmoid is demonstrated in Figure 4.
the model of perceptron is described, in the books of Minsky
1 M. and Papert S. [42-44] limitations of a single-layer per-
ceptron are elicited. In 1974 Paul Werbos suggested the
algorithms of back propagation [45, 46] applicable for
0.5 learning of a multilayer perceptron or a neural network. The
most popular and helpful ANN is a network of forward
propagation, where non-linear elements (neurons) are
represented as consequent layers, but information is
0 distributed in one direction [47] (feed-forward neural
FIGURE 4 Sigmoid function
networks). In 1989 the research papers by Cybenco G. [48]
and Hornik K. etc. [49] demonstrated that such a network is
h (x) can be considered as the likelihood that the object able to approximate practically any function.
can be "positive” h ( x)  0.5 or "negative” h ( x) <0.5. In The theory of connectivism was contributed conside-
complex cases that requires a non-linear interface, for rably by national scientists [50-53], who demonstrated the
example in the shape of a circle (Figure 5) - possibility to decide classical computational problems based
h ( x)  g (0  1 x1  2 x2  3 x12  4 x2 2 ) on neural networks, thus putting a fundamental principle of
neural computers generation.
Application of a neural network apparatus addresses
decision of a wide range of computationally complex prob-
lems, such as optimization, signal processing, image reco-
gnition, forecasting and classification.
Let us consider application of feed-forward neural
networks. An individual neuron represents a logistic
FIGURE 5 Non-linear interface between objects of different classes element, consisting of input elements, an integrator, an
activating elements and a single output (Figure 6).
Adjustment of parameters  , after selection of the
function of hypothesis, is executed with regard to minimize x0
0
the cost function as follows
m x1 1

1
J ( )   [ y (i ) log h ( x(i ) )  (1  y (i ) ) log(1  h ( x(i ) ))] h (x)
m i 1 2
x2
g(z)
Same as in case of a linear regression, minimization is
reached with use of the gradient descent algorithms, though n
…
Conjugate gradient [38], BFGS, L-BFGS [39] is also xn
applicable.
FIGURE 6 Diagram of a classical neuron

19
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

Neural output is determined with the formulas m K


1
J ()   [ yk (i ) log(h ( x (i ) )) k  (1  yk (i ) )
z  0  1 x1  2 x2  3 x3  ...   n xn m i 1 k 1
,
L 1 Sl Sl 1
h ( x)  g ( z ) , 
where g ( z ) – a sigmoid function.
log(1  h ( x ))k ] 
(i )
2m 
l 1 i 1 j 1
(lji ) 2
To make the diagram simpler the integrator and the
activating element are united, thus a multilayer network can where L –number of neural network layers,
look as in the Figure 7. The network contains three input s l - number of neurons in the layer l,
neurons, three hidden layer neurons and one output neuron. K – number of classes (equal to the number of neurons
In the Figure input neurons are marked with the symbol х, in the output layer),
hidden layer neurons – with the symbols a1(2) , a2(2) , a3(2) , a0(2) ,  - a weight matrix.
and output layer neurons – with the symbol a1(3) . To train a multilayer neural network they use the back
propagation error algorithm and different modifications
x0 targeting to accelerate the training process.
a0( 2 )
2.4.5 k-Nearest-Neighbor (k-NN) [54, 55] algorithm
x1 a1( 2 ) h (x) The algorithm is based on calculation of the number of
a1(3) objects in each class of the sphere (hypersphere) with the
x2 a2( 2 ) centre in the recognized object. The object belongs to the
class, which objects dominate in this sphere. This technique
supposes that weights have been chosen individually for
a3( 2 ) every object.
x3 If weights are not same, instead of calculation of the
number of objects their weights can be added together. Thus,
FIGURE 7 Diagram of a multilayer network if the sphere around the recognized object contains 10
Output of each hidden layer neuron can be calculated reference objects of class A with the weight 2 and 15
same as the one for a single neuron: error/boundary objects of Class B with weights 1, the point
will be referred to Class A.
a1(2)  g (10
(1)
x0  11
(1)
x1  12
(1)
x2  13
(1)
x3 ) Weights of objects in the sphere can be expressed as
inversely proportional to their distance to the recognized
a2(2)  g (20
(1)
x0  21
(1)
x1  22
(1)
x2  23
(1)
x3 ) object. Thus, the closer is an object, the more significant it
is for this recognized object.
a3(2)  g (30
(1)
x0  31
(1)
x1  32
(1)
x2  33
(1)
x3 ) In total, a metric classifier can be described as:
l

[ y
The neural network output is determined from the
a(u; X l )  arg max (i )
u  y]w(i, u) ,
equation: yY
i 1
h ( x)  g (10 a0  11
(2) (2)
a1  12
(2) (2)
a2  13
(2) (2) (2) (2)
a3 )
where w (i, u) – a weight of an i-neighbour of an recognized
The benefit of the neural network is the opportunity to object u, a (u;Xl) – class of an object u, recognized by a
classify several classes at once. In this case the output layer selection Xl.
contains the number of neurons equal to the number of The radius of the hypersphere can be as constant, as
classes. For example, as may be required to classify objects dynamic. Moreover, in case of a dynamic radius, a radius of
of two classes we will get a network (Figure 8). each point is adjusted so that the number of objects in each
sphere is constant. Thus, for recognition in areas with vary-
x0 ing density of selection, the number of „neighboring” ob-
a0( 2 ) jects (being actually used in recognition) will be the same.
In this manner, there is excluded the situation when reco-
x1 a1( 2 ) a1(3) h1 ( x)
gnition suffers scarcity of data in low-density areas.

2.4.6 Support Vector Classification (Linear SVM and Non-

x2 a2( 2 ) linear SVM) [56]
a2(3) h2 ( x)
a ( 2) This algorithms refers to the group of boundary techniques:
3
it determines classes with use of area boundaries. The tech-
x3 nique is based on the concept of solution planes. A solution
FIGURE 8 Diagram of a multilayer network with double output plane divides objects of different classes. In high-dimension
spaces instead of straight lines there should be considered
To adjust the weights  of the neural network (training hyperplanes of one dimension less than the one of the
of the network) they use the cost function, reminding the assumed space. In R3, for example, a hyperplane is a two-
cost function for logistic regression. dimensional plane.

20
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

The support vector technique searches for samples, loca-

ted on class boundaries (at least two), i.e. support vectors,
d k  ( x  k )  1
( x  k )t , k  1, 2
and decides the problem of finding the division a set of In practice unknown mathematical expectations and
objects to classes with use of a linear decision function. The covariance matrix are replaced with their estimates
support vector technique builds classification function f(х)
Ik
as follows:
x
1
mk  i ,
f ( x)  sign( w, s  b) , Ik i 1

where < , > – scalar product, 1

w – normal (perpendicular) vector to a dividing S ( X 1t X 1  X 2t X 2 ) ,
I1  I 2  2
hyperplane,
b – auxilliary parameter equal to the absolute module of
~
where X k – a centered matrix Xk.
a distance from a hyperplane to the origin of coordinates. If If we set equal a distance d1 to a distance d2, d1=d2, in
a parameter b equals zero, a hyperplane passes through the the mentioned above forula, it makes possible to find the
origin of coordinates. formula of a class division curve. Along with this quadratic
Objects with f(x)=1 get into the first class, but objects terms are reduced and the equation becomes linear
with f(x)=-1 - into another one.
From the point of classification accuracy the best xw1t  v1  xw2t  v2 ,
straight line to be selected is the one maximally distant from
each class. Such straight line (in general — a hyperplane) is where
identified as an optimal dividing hyperplane. The problem
consists in selection of w and b, maximizing this distance. wk  mk S 1 ,
In case of non-linear division the approach of support
vector machine adaptation is available. It is necessary to vk  0.5mk S 1mkt .
input the space of Rn indicators into the space H of a larger
The values in different parts of the equation are iden-
dimensionality using the function of the form: φ = Rn → H.
tified as LDA-accounts, f1 and f2. The sample refers to class
Hence decision of the problem reduces to a linear
1, if f1 > f2, and, vice versa, to class 2, if f1 < f2.
divisible case, i.e. a dividing classification function is
searched again as: f ( x)  sign( w,  ( x)  b).
2.4.8 Diagonal Linear Discriminant Analysis (DLDA)
Also possible another option of data conversion –
conversion to polar coordinates:
Algorithm is a kind of the Linear Discriminatory analysis,
 x1  r cos( ), described above. This algorithm was described in 2002 [58]
 as an optimized LDA modification for multivariate data
 x2  r sin( ). (high-dimension problems). When all class densities have
same diagonal covariance matrixes:
2.4.7 Linear Discriminant Analysis Classifier (LDAC) [57]
  diag (12  G 2 ) .
In mathematical statistics classification is often identified as
discrimination. Discriminatory analysis is the section of The classification rule will look as follows:
multivariate statistical analysis, which includes statistical ( xi  ki )2

G
classification methods of multivariate observations. dk  .
Linear discriminatory analysis is a statistical and ML
i 1  i2
method used in search for linear combination of variables
eminently suitable for division of two and more classes of 3 Quality assessment of machine learning systems
objects or events. LDA tries to express a dependant variable
(class label) via a linear combination of other indicators or In a view of abundance of algorithms selection of their use
measurements. The acquired combination can be used as a in a certain ML problem can become complicated. To com-
linear classifier. The indicators used to distinguish one class pare algorithms and methods among themselves and proba-
(subset) from another are often identified as discriminatory bly with an expertise results they use indicators of algorithm
variables. classification accuracy and learning curves. The function of
Let the learning selection be expressed in matrixes X1 accuracy indicators is to give the estimate demonstrating
and X2, having by I1 and I2 lines (objects). The number of how much the certain ML classifications or forecasts differ
columns (variables) is the same. Initial assumptions are as from the ones made by experts. Along with this frequently
follows: use the elementary indicator – percentage of correctly classi-
 Each class (k=1 or 2) represented with normal fied examples. For estimation of type I and II errors also use
distribution; some important indicators: “precision”, “recall” and sum-
 Covariance matrixes of these two classes are equal Σ1= marizing indicators - T1 Score and kappa. Their use is
Σ2= Σ. especially important in case of unequal by volume classes,
The rule of LDA classification is the following: a new whereas the number of objects of one type significantly
sample x is referred to that class, which it is closer to in exceeds the number of objects of another type. One more
Mahalanobis units: important indicator of ML method is its learning ability, i.e.

21
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

improving its accuracy indicators as the number of samples negative (Fn) and False positive (Fp) of incorrect operation.
is increasing. At this point, it might happen that the method At this, Fn can be concerned as the sign of an excessively
showing very good results with train set of examples will pessimistic (cautious) classifier, Fp – vice versa, as the sign
produce unsatisfactory results with a testing one, i.e. it does of excessively optimistic or incautious classifier. Then
not feature the necessary degree of summarizing. The bala-
nce between summarizing ability and accuracy can be found Tp
with help of “learning curves”, which in a general case are Precision: P 
able to show if this or another method can improve its result (T p  Fp )
in a way that its accuracy indicators were approximately
will show a part of correctly recognized objects of the
equal and satisfied the research domain requirements as for
specified class referring to the total number of objects taken
training as for testing setoff values.
by the classifier as objects of the specified class.
Alternatively, recall
3.1 INDICATORS OF CLASSIFICATION ACCURACY
ESTIMATES Tp
R
At present in the field of ML quality assessment most (T p  Fn )
frequently apply:
will show the ratio of correctly recognized objects to the
Accuracy – fraction of correctly classified examples
total number of objects of the given class.
(percentage of correctly classified examples)
Both indicators and P and R show “confusion” of a
Nt classifier. Still P shows how optimistic is a classifier in its
Ac  , estimates, or how frequently it “likes” (low value of P)
N
adding objects of other classes to the given one. While R
where N t - number of correctly classified examples, N – shows how “pessimistic” is a classifier in its estimates, i.e.
total number of objects. how frequently it neglects (low value of R) objects of the
This indicator is essentially important, but if the number needed class.
of objects in classes is substantially unequal, said to be uneven Evidently, it is desirable that both of these indicators
or “skewed” classes, it might happen that a very bad classifier tend to 1. For some “average” estimate use
would produce a large value Aс. For example, if type I objects
2 PR
make 90% of total number of objects, but type II objects only T 1Score  ,
10%, it will be sufficient for a classifier just to report on ( P  R)
recognition of a type I object and its accuracy will reach 90%.
Thus, even if the algorithm will never recognize correctly a which, as is clear from the equation, also tend to 1, if both
type II object, still it will have a high indicator Aс. At this, if indicators P and R are close to 1.
recognition of type II objects is of prime importance, an Let us notice that use of simple Average= (P+R)/2 can
indicator Aс will just mislead. To avoid such an inadequate result into a wrong idea about properties of algorithm. For
estimate some more important indicators are taken: example, let us assume three algorithms showing the
“precision”, “recall” and a summarizing indicator - T1 Score, following Precision и Recall estimated (Table 2)
calculated from the following equations: It is evident that a simple average (column Average)
gives the highest estimate of an absolutely bad algorithm 3,
Tp which take all objects as required in error (P are very few).
Precision: P  , At the same time T1 Score shows the more correct result,
(T p  Fp )
giving the highest score to the algorithm 1, which shows
Tp close Precision and Recall estimates, and, consequently, will
Recall: R  be weighed in their estimates.
(T p  Fn )
TABLE 2
2 PR
T1 Score: T 1Score  Precision Recall
( P  R) (P) (R)
Ave-rage T1 Score

Let us explain the given equations. Algorithm 1 0.55 0.44 0.495 0.4888889
Let us concern the case of classification of two classes Algorithm 2 0.71 0.12 0.415 0.2053012
(or one type I class and all other classes, which we assign
Algorithm 3 0.03 1 0.515 0.0582524
the number 0) to. In this case the following situations in
Table 1 are optional. For a finer estimate of developed algorithms also use
indicators of errors designed for parts of a selection: error
TABLE 1 Classification of two classes on a control selection, error of cross-validation and valida-
Actual class tion techniques: fold validation, random subselection (sub-
1 0 sampling) validation.
1 True positive False positive Moreover, for the problems with greatly differing
Predicted class
0 False negative True negative
numbers of class representatives, the cost function (errors)
Cases True positive (Tp) and True negative are the cases can be computed in a specific way, for example, in case of
of correct operation of a classifier, appropriately, cases False skewed classes:

22
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

2 m mcv

   (h ( x
1 1
J ( )  min (h ( x(i ) )  y (i ) )2 J cv ( )  cv )  ycv
(i ) (i )
)2 ,
k 1
| {t | y( xt )  k}| i 1
2mcv i 1

where m – train set of examples, mcv - test set of examples

3.2 “LEARN ABILITY” OF ALGORITHMS
(cross validation - cv),
h – function of the hypothesis, which can be linear
The Estimation of recognition algorithms by simple compa-
h  0  1 x or non-linear, for example,
ring the quality indexes (accuracy, precision, recall) has the
h  0  1 x   2 x 2 with different set of parameters
disadvantage that makes it impossible to evaluate the
algorithms in the dynamics of change in the volume of
i   .
Model parameters that define the function h    , are
training sample. Particularly, in terms of neural networks,
accuracy indicators are effected substantially by the number calculated with use of a train set, and validated by examples
of hidden layers and the number of training examples. With from a testing set.
Looking ahead, it might be stated that compensation of
the use of linear regression its order, for k-NN – is the
nearest neighbours circle radius, etc. Along with this it is excess variables in case of overfit the regression model
important to consider the algorithm’s ability of learning, applies regularization, achieving that variables of higher
order showed lower effect. The cost estimate formula with
overfitting or underfitting. The correct balance between
underfit and overfit means the search of an algorithm and its consideration of regularization is specified below.
parameters, which would be able to show consistent results m n

 (h ( x 
1
for a testing set (or a cross validation set). An underfit algo- J ( )  (i )
)  y (i ) ) 2   2
j ,
rithm will show equally inconsistent results both for test and 2m i 1 j 1
train sets, while an overfit algorithm will demonstrate a high
result for a train set and a low one for a testing set. Let us where  - a regularization parameter.
assume, in case of regression, the appropriate formulas of If a neural network is used reduction in the number of
the curves, extrapolating distribution of training examples hidden layers of a neural network performs the similar
as shown below: function.
Application of regularization or reduction of the number
a) 0  1 x - high bias(underfit) of hidden layers increase summarizing ability of a ML
algorithms and consequently decreases learning ability, in
b) 0  1 x  2 x 2 - just right terms of flexibility of adjustment according to subtle
differences between classes.
c) 0  1 x  2 x 2  3 x3  4 x 4 - high Let us notify that ML systems can be classified as high
variance (overfit) bias, having a comparatively low capability to generate
complex interpolatory curves, and as high variance systems,
Extrapolation results at some hypothetic distribution of being able to form curves (surfaces) of complex shape.
train set objects are shown in Figure 9). Pattern of these algorithms (models) differs when the
number of training examples increases. Te first ones, as a
rule, summarize results ignoring frequently some, probably,
essential differences between examples. The second ones,
on the contrary, "trace" all nuances, probably random, but at
the same summarize insufficiently. The first ones feature
underfit, but the second ones – overfit (Figure 2.5) As a rule,
a) b) it is impossible to evaluate model abilities during one ex-
periment, as both first and second ones can produce close
error indicators.
In this context, trainability of ML algorithms is
estimated with help of so called learning curves, taking into
account the following empirical patterns:
 In normal environment, with an effective algorithm,
with increasing the number of training examples the
c) error across the train set will slightly grow, but the
FIGURE 9 Chart of ML algorithm underfit and overfit error across the test set will decrease (Figure 10);
a) too linear divisor (underfit) b) almost ideal case  If a system is comparatively linear (high bias)
c) too many variables (overfit) increase in the number of training examples will be
of little use. The error both across the training and
At this error indicators across train and test (cross
test sets will be approximately equal and large
validation – cv) sets are determined from identical equations
(Figure 11);
(changes only a set of examples)
 In case of a high variance system, increase in the
m number of training examples will lead to reduction
 (h ( x
1
J train ( )  (i )
)  y (i ) ) 2 , of the error value across the test set, but it will differ
2m i 1 substantially from the error across the train set
(Figure 12);

23
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

To decrease the test set error even more it is possible to cleaning of abnormal values; data normalizing; "fitting";
increase essentially the training set (which is not always data reformatting; formatting of input data set, which for
possible). example can include formatting of a so-called dockable
Thus, to estimate which of two groups the analyzed pane, needed for analysis of patterns of presented data
algorithm belongs to (too linear or too flexible) it is sequences; data reconciliation, for example when one data
recommended to analyze the curve of learning errors with set is time, distance, spectrum, etc. translated, with respect
increasing body of the learning set, for example, if curves to others, etc. Let us notice that if the set of ML algorithms
show convergence, but in parallel a high level of errors, this is known and the properties of these algorithms are mostly
may point to a linear model (impossible to train it). well studied, the processes of data preprocessing vary and
If unwilling properties of the algorithm have been depend directly on the object domain and quality of
detected it is possible to try to adjust it, to change the body available data. Frequently, the specified above “classical”
of the learning set of examples or to choose additional set is added with additional stages, letting finally raise the
properties of objects, by taking into account the following: quality of data interpretation.
 increasing the size of the train set is helpful at high
variance of the algorithms (many layers of neural 4.1 ELIMINATION OF ABNORMAL VALUES
network, high order of regression), when the
program does not feature the needed degree of 4.1.1 Normal distribution-based algorithm of abnormal
summarizing, and is adjusted mainly to the train set value detection
of examples and cannot normally classify examples
from the test set (overfit error). The normal distribution-based algorithm for abnormal
 Decrease in number of used properties or parameters activity detection is designed on the assumption that the
is helpful at high variance of the algorithms (many whole set of “correct” objects forms Gaussian distribution
layers of the neural network, high order of (normal distribution), i.e. x values are distributed according
regression), i.e. once again for the cases of overfit, to the normal law of distribution, defined by mathematical
and when in parallel the number of training examples expectation -  and mean square deviation -  2
is impossible to be increased substantially; x ~ N ( ,  2 ) ,
 Use of additional properties is helpful in case of too
linear algorithms (low order of regression, few which can be presented graphically with Figure 11.
neurons in hidden network layers, or few hidden
layers), when the program will show the same bad P(x)
results both on the test and train sets (underfit errors);
 Use of special synthesized (polynomial) properties,
showing higher degrees and products of basic (x12 ,
x22 ,x1 x2 ,…) is also helpful in case of too linear
algorithms (low order of regression, few layers of the
neural network) (underfit model). x
Error Error FIGURE 11 Approximate curve of х objects probability distribution
J cv ( )
subordinated to normal (Gaussian) law
J cv ( )
J train ( )
Along with this probability of that or another value is
J train ( ) calculated from the known formula

m (training set size) 1 ( x   )2

p( x;  ,  2 ) 
m (training set size)
exp( ).
a) b) 2 2 2
Error

J cv ( ) If objects have several properties, then probabilities will

subordinate to the multivariate Gaussian distribution.
n
J train ( ) At this, p ( x)   j 1
p ( x j ;  j ,  j 2 ) , where n – number
m (training set size)

c) of object properties to be classified (number of parameters).

FIGURE 10 Learning curves In this manner, the calculation algorithm of abnormal
a) normal situation, learning algorithm with good summarizing ability objects is as follows:
b) hard-trained algorithm, a high bias system Step 1. Based on m train set examples the parameters of
с) high variance algorithm the multivariate Gaussian distribution are determined -
{1 ,..., n ; 12 ,...,  n2 } :
4 Data preprocessing m

x
1
j  (i )
j ,
ML method use require to render the processed data to a m i 1
certain format that would allow to feed them to learning and
analysis algorithms input. Along with this important cycles
of processing are performed, including as a the rule,

24
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

m ( x  xmin )(b  a)
(x
1 p a,
2j  (i )
j   j )2 , ( xmax  xmin )
m i 1
where [a,b] – the range of acceptable input signals;
where x (ji ) - a j-parameter of an x object in the training
[ xmin , xmax ] – the change range of input variable values; р
example I from the set of examples m
Step 2. For each new х item its probability is calculated – conversed input signal.
When using this method of conversion (linear
n n
( x j   j )2 normalizing) big change range of input variable can become
 
1
p ( x)  p( x j ;  j ,  j 2 )  exp(  ). a problem. In such cases it is possible to use conversion from
j 1 j 1 2 j 2 j 2
equations of the sigmoid function or the hyperbolic tangent.
Step 3. If the calculated probability is lower than some When coding quantitative variable in a general case it is
threshold values  , then this object х is considered necessary to consider the profound characteristic value, its
abnormal location over the interval of values, accuracy of measu-
rement. Conversion can be performed using two equations:
If p( x)   then x is abnormal.
xi  M(xi )
xi 
In practice, training a system to detect abnormal values q(xi )
considers detection of the threshold value  . Adjustment of
this threshold can be performed based on available examples or
(similarly to supervised algorithms). After the series of
experiments such a threshold  is established so that all (or xi  M ( xi )
xi  ,
most part of) “wrong” objects would be detected as abnormal. max | xi  M ( xi ) |
The applied approach of abnormal value detection is
illustrated graphically with Figure 12 where xi - an i-coordinate of an input vector Х;
Sampling estimate of mathematical expectation xi
P(x) (mean value):
n
M ( xi )  1/ n x
i 1
i

Sampling estimate of the mean square deviation:

n
x q( xi )  (1/ n  ( x  M ( x ))
i 1
i i
2

Normal objects
«Нормальные» объекты Abnormal objectобъект
Аномальный
FIGURE 12 Exclusion of abnormal objects To make minor changes of big values significant (for
example, when the value of an input variable can reach 10000,
Let us notice that if the distribution differs from normal,
but in terms of analysis significant is the value change by 1),
it can be normalized by calculating the logarithm of х or the
three kinds of numerical data preprocessing are used –
degree of х values.
modular, positional and functional. For accounting of minor
changes every value is coded with a vector formed by the
4.1.2 Use of ML for detection of abnormal values
rules specified below, instead of the only amount.
Obvious, that supervised learning algorithms are quite
4.2.2 Modular preprocessing
feasible for detection of abnormal objects. In this case
abnormal objects represent an individual class of objects,
There is given a set of positive numbers yi ,..., yk . Calculate
which can be detected with algorithms k-NN or logistical
each component of the vector Z as follows
regression. In both cases adjustment of those object
properties being essential in segregation of abnormal values. (( x mod yi )  yi )(b  a)
zi  a ,
2 yi
4.2 DATA NORMALIZING AND CENTERING
METHODS where [a,b], as before, – the range of acceptable input
signals.
4.2.1 Linear normalizing Let us explain that when x mod y is calculated the
remainder on dividing х by y is returned, for example, if x=5
In a view of cleaning the abnormalities data and operation y=3, x mod y= 2
comfort perform data normalizing and centering so that each
component of the input vector is located on the segment 4.2.3 Functional preprocessing
from 0 to 1 or from -1 to 1. If knowing the change range of
input variable there can be used the simplest type of In a general case, transformation of an input characteristic x
conversion into a k-dimensional vector Z occurs as described below.

25
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

There are selected k numbers, satisfying the condition 1. In the beginning examples from the train set are
randomly rearranged.
xmin  yi  ...  yk  xmax ,
2. Over all m examples from the learning set, for each of
The elements of the vector Z are computed n parameters a new value of the parameter is calculated. In
SGD pseudo-code this can be written as:
( ( x  yi )  min )(b  a) for iter:=1 to K
zi  a ,
max  min for i:=1 to m
for j:=1 to n
where  - the function, determined within the interval  j :  j   (h ( x(i ) )  y (i ) ) x j (i )
[ xmax  yk , xmin  y1 ] , а max , min - the maximal and the end
minimal value of the function within this interval. end
end
4.2.4 Positional preprocessing [59] Number of iterations K=1,...,10.
At the same time, the pseudo-code of the batch gradient
The approach in this case is approximately the same as in descent- BGD algorithm looks as follows
case of building the positional representation. A positive y Do
value is selected, meeting the condition y k  ( xmax  xmin ) . for i:=1 to m
Let us shift an x parameter so that it had only positive values for j:=1 to n
m

 (h ( x
and zero. For calculation of the vector Z we use the 1
following formulas  j :  j   (i )
)  y (i ) ) x j (i )
m i 1
zo  ( x  xmin ) mod y , end
end
z1  (( x  xmin ) / y) mod y , enddo
Thus, at each of m steps of the BGD algorithm
zk  (( x  xmin ) / y k ) mod y . cumbersome summing is performed, while SGD uses only
one example per each iteration. Assessment of compu-
Other methods of input value conversion – raising to the tational complexity of SGD - O(m) comparing to O(m 2 )
power, rooting, calculation of reciprocal values, exponential for BGD under condition that the number of parameters n is
curves and logarithms, and also certain combinations of much fewer than m. Still use of SGD results into
variables - products, quotients, etc. that can reduce the approximate decision, not into the global minimum of the
length of the input data vector. cost function. Besides, SGD, same as the described below
MBGD also suffer the convergence problem. This means
5 Machine learning in Big Data management that instead of getting better their result can even get worse
with increase in the number of processes examples.
The main problem of ML techniques application in classify- The MBGD algorithm per each iteration uses only a part
cation and regression of big data are computational comple- (b) of examples
xity of the cost function calculation (Equation (2.1)) and of
for iter:=1 to K
appropriate parameters of the function of hypothesis
for i:=1 to m with step b
(Equation (2.2)) due to a large number of examples.
For example, the standard gradient descent algorithm is for j:=1 to n
k b

 (h ( x
an iterative procedure provided via comparatively large 1
number of elementary steps.  j :  j   (i )
)  y (i ) ) x j (i )
b k i
Let us assume that we have 100 000 000 examples, 10
parameters and calculate parameters for 500 iterations of end
gradient descent at the average. The number of required end
calculations will make 5*1011 . Assuming that a computer end
is able to calculate 1 mln. iterations of gradient descent per Its computational complexity can be assessed as O(bm) ,
minute, we get about 140 hours for calculation of only one which in terms of b<<m can be traced to O(m) .
set of parameters of the function of hypothesis. If it is Except for the mentioned above SGD and MBGD para-
needed to draft a learning curve the time of calculation lleling of calculations can be applied to overcome the problem
increases proportionally to the number of curve point and of large number of calculations [62, 63], which can allow to
can reach absolutely unsuitable values. Though the use of decide the problem of finding the parameters of the function of
matrix operations (Equation (2.3)) eliminates iterations, still
hypothesis with help of BGD during the acceptable period of
it becomes impossible due to great computational
complexity of derivation of a reciprocal matrix. time parallel to large number of independent processes.
To overcome “the curse of dimensionality” for the gra- The essence of the Map-reduce method is as follows.
dient descent algorithms two algorithms are suggested in Calculation of the sum
this case: the one of Stochastic gradient descent – SGD [60] m

 (h ( x
1
and the one of mini-batch gradient descent – MBGD [61].  j :  j   (i )
)  y (i ) ) x j (i ) .
The SGD algorithm functions as follows: m i 1

26
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

Is performed on separate machines or processors. Taken platform MLBase is described, which provides problem
that the number of processors is B pieces, the calculation can statement and use ML together with high-level operators.
be performed like this:
6 Conclusion
m/ B
Sum j 0 :  (h ( x
i 1
(i )
)  y )x j (i ) (i )
The domain of Artificial Intelligence is very vast and
includes many disciplines, beginning from logical reasoning
m/ B to the methods of text tonality analysis. Traditionally reco-
Sum j1 :  (h ( x
i 1
(i )
)  y (i ) ) x j (i ) gnize the so-called strong artificial intelligence and weak
artificial intelligence. The first one is oriented at develop-
ment of high intelligence human-centric decision systems,
... eventually at creation of intelligent machines. Weak artifi-
cial intelligence is oriented at development of applications,
m / B  k *( m / B )


realizing this or another intellectual ability of humans or
Sum jk : (h ( x (i ) )  y (i ) ) x j (i ) animals. The potential of weak artificial intelligence concept
i  k *( m / b ) 1
is realized using machine learning.
... The review considers machine learning techniques as a
part of weak artificial intelligence methods, applicable for
m / B  ( B 1)*( m / B ) analysis data including for big data processing. The taxo-
Sum jB 1 : 
i  ( B 1)*( m / b ) 1
(h ( x (i ) )  y (i ) ) x j (i ) nomy of machine learning techniques was proposed. This
schema unites various kinds of supervised and unsupervised
learning algorithms. At this, classification or other kind of
heterogeneous data processing has a range of specific
B 1
features: heterogeneity of data types, frequently occurring

1 large massives of data, complications in data collation.
 j :  j   ( Sum jk )
m k 0 The classical diagram of adjustment for machine learning
decision techniques is described. The ML problem is for-
For example, if the number of processors is 3, but the mally stated and some frequently used algorithms are des-
number of examples is 300000: cribed (linear regression, polynomial regression, logistical
regression, artificial neural networks, algorithms k-NN,
100000 SVN, LDAC, DLDA). Assessment indicators of classifica-
Sum j 0 :  (h ( x
i 1
(i )
)  y (i ) ) x j (i ) tion accuracy (accuracy, precision, recall) and the summa-
rizing indicator (T1 Score) are considered in detail. The
concept of learn ability of ML algorithms and its practical
200000


use (methods of learning curve interpretation) is described.
Sum j1 : (h ( x(i ) )  y (i ) ) x j (i ) Some data preprocessing methods are described in detail,
i 100001 including the methods of abnormal value elimination and
300000 normalization. Briefly considered the application of machi-
Sum j 3 : 
i  200001
(h ( x(i ) )  y (i ) ) x j (i ) ne learning methods at the processing of big data and
techniques of solving some specific problems with help of
parallelized computing, mapreduce approach and modifi-
3 cations of the gradient descent algorithm.

1
 j :  j   ( Sum jk ) Development of machine learning techniques proceeds
300000 k 0 in parallel with their practical application, which results into
increasing number of applications, appearance special
Obviously that computational complexity of the method decision techniques of applied problems using ensembles of
m2 algorithms. Programming environments and languages
can be rated as O( ) . At small B values, growth of including declarative ones are suggested now. Some of them
B
are targeted to facilitate applications at big data. One of the
calculation speed will be negligent, but if the number of
significant task of future researches is development pre-
processors is comparable to the number of processors in
processing methods that could be used at many kinds of data
modern supercomputer clusters (1000-1000000) the growth automatically or semi-automatically.
rate can reach up to several orders.
Application of ML in big data management has serious Acknowledgment
opportunities. Special languages and platforms are sugge-
sted for realization of ML potential in big data management.
This work was supposed by grants 0168/GF4 and 2318/GF3
For example, in [64] the language (SystemML) is suggested
and the ways of its application are described for realization from the Ministry of Education and Science of the Republic
of ML techniques in big clusters MapReduce. In [65] the of Kazakhstan.

27
Review Paper
COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

References

[1] Systems of Neuromorphic Adaptive Plastic Scalable Electronics [24] Mannini A, Angelo M S 2010 Machine learning methods for
[Link] classifying human physical activity from on-body accelerometers
morphic_Adaptive_Plastic_Scalable_Electronics_(SYNAPSE).aspx Sensors 2 1154-75
10 Aug 2014 [25] Ballester P J, Mitchell J B 2010 A machine learning approach to
[2] Блейксли C, Хокинс Д 2007 Об интеллекте 128 predicting protein–ligand binding affinity with applications to
[3] Weiß G 1999 Multiagent Systems: A Modern Approach to Distributed molecular docking Bioinformatics 9 1169-75
Artificial Intelligence 648 [26] Farrar C R, Worden K 2012 Structural health monitoring: a machine
[4] Russell S, Norvig P 2010 Artificial Intelligence: A modern approach learning perspective 66
1078 [27] Recknagel F 2001 Application Of macine Learning To Ecological
[5] Gorodetsky V I 2012 Self-organization and multi-agent systems Modelling Ecological Modelling 303-10
Proceedings of the Russian Academy of Sciences Theory and control [28] Charles C, Hecker J, Stuntebeck E, Shea T O 2007 Applications of
systems 2 92-120 machine learning to cognitive radio networks Wireless
[6] Gorodetsky V I 2012 Self-organization and multi-agent systems Communications IEEE 4 47-52
Applications and technology development Proceedings of the Russian [29] Ball N M, Brunner R J 2010 Data mining and machine learning in
Academy of Sciences Theory and control systems 3 55-75 astronomy International Journal of Modern Physics 7 1049-1106
[7] Jones M T 2008 Artificial Intelligence: A Systems Approach New [30] Szepesvari C 2009 Algorithms for Reinforcement Learning Synthesis
Delhi: INFINITY SCIENCE PRESS LLC 500 Lectures on Artificial Intelligence and Machine Learning series by
[8] Zhang G P 2000 Neural Networks for Classification: A Survey IEEE Morgan & Claypool Publishers 98
Transactions on systems man and cybernetics—Part C: Applications [Link]
and reviews 30(4) [31] Zhu X 2008 Semi-Supervised Learning Literature Survey Computer
[9] Kriesel D 2015 A Brief Introduction to Neural Networks Sciences [Link]
[Link] [32] Kohonen T 1982 Self-Organized Formation of Topologically Correct
[10] Van der Baan M, Jutten C Neural networks in geophysical applications Feature Maps Biological Cybernetics 43(1) 59–69
Geophysics. 65(4) 1032-47 [33] Jain A K, Murty M N, Flynn P J 1999 Data Clustering: A Review ACM
[11] Baldwin J L, Bateman R M, Wheatley C L 1990 Application of a neural Computing Surveys 31(3)
network to the problem of mineral identification from well logs The [34] Barbakh W A,Wu Y, Fyfe C 2009 Review of Clustering Algorithms.
Log Analyst 279-93 Non-Standard Parameter Adaptation for Exploratory Data Analysis
[12] Benaouda B, Wadge G, Whitmark R B, Rothwell R G, MacLeod C Studies in Computational Intelligence 249 7-28
1999 Inferring the lithology of borehole rocks by applying neural [35] Ayodele T O 2010 Types of Machine Learning Algorithms New
network classifiers to downhole logs - an example from the Ocean Advances in Machine Learning 19-48
Drilling Program Geophysical Journal International 136 477- 91 [36] Hamza A, Hamza I 2012 Taxonomy of Machine Learning Algorithms to
[13] Saggaf M M, Nebrija E L 2003 Estimation of missing logs by classify realtime Interactive applications International Journal of Computer
regularized neural networks AAPG Bulletin 87(8) 1377-89 Networks and Wireless Communications (IJCNWC) 2(1) 69-73
[14] Тененёв В А, Якимович Б А, Сенилов М А, Паклин Н Б 2002 [37] Дьяконов А Г 2010 Анализ данных, обучение по прецедентам,
Интеллектуальные системы интерпретации геофизических логические игры, системы WEKA, RapidMiner и MatLab
исследований скважин Штучний інтелект 3 338 (Практикум на ЭВМ кафедры математических методов
[15] Алёшин С П, Ляхов А Л 2011 Нейросетевая оценка минерально- прогнозирования) 277
сырьевой базы региона по данным геофизического мониторинг [38] Møller M F A scaled conjugate gradient algorithm for fast supervised
Нові технології 1(31) 39-43 learning Neural Networks 6(4) 525-33
[16] Карпенко А Н, Булмасов О В 2015 Применение нейроносетевых [39] Dong C. Liu, J 1989 Nocedal On the limited memory BFGS method for
технологий при интерпретации данных геофизических large scale optimization Mathematical Programming 45(1-3) 503-28
исследований скважин. [Link] [40] McCulloch W S, Pitts W 1943 A logical calculus of the ideas immanent
[Link]/[Link]?name=articles&op=view&id=11&pag=3&num=1 in nervous activity The bulletin of mathematical biophysics 5(4) 115-33
[17] Rogers S J, Chen H C, Kopaska-Merkel D C, Fang J H 1995 Predicting [41] Rosenblatt F 2015 The perceptron: A probabilistic model for
permeability from porosity using artificial neural networks AAPG information storage and organization in the brain Psychological
Bulletin 786-1797 Review 65(6) 386-408 [Link]
[18] Костиков Д В 2007 Инструментальные средства интерпретации [42] Minsky M 1987 Seymour Papert Perceptrons expanded edition 308
геофизических исследований скважин на основе [43] Минский М 1971 Пейперт С Персептроны 263
преобразованных каротажных диаграмм с помощью [44] Minsky M 1987 Seymour Papert Perceptrons expanded edition 308
многослойной нейронной сети Диссертация кандидата [45] Werbos P 1974 Beyond Regression: New Tools for Prediction and
технических наук 189 Analysis in the Behavioral Sciences
[19] Muhamediyev R, Amirgaliev E, Iskakov S, Kuchin Y, Muhamedyeva [46] Werbos P J 1988 Backpropagation: past and future IEEE International
E 2014 Integration of Results of Recognition Algorithms at the Conference on Neural Networks 1 343-53
Uranium Deposits Journal of ACIII 18(3) 347-52 [47] Saad D 2009 1998 Introduction. On-Line Learning in Neural Networks
[20] Амиргалиев Е Н, Искаков С Х, Кучин Я В, Мухамедиев Р И 2013 Cambridge University Press 3-8
Интеграция алгоритмов распознавания литологических типов [48] Cybenco G 1989 Approximation by superpositions of a sigmoidal
Проблемы информатики 4(21) 11-20 function Mathematics of Control Signals and Systems 2(4) 304-14
[21] Amirgaliev E, Iskakov S, Kuchin Y, Muhamediyev R 2013 Machine- [49] Hornik K 1989 Multilayer feedforward networks are universal
learning techniques in the pattern recognition of rock at uranium approximators Neural Networks 2 359-66
deposits Proceedings of National Academy of Sciences of Kazakhstan [50] Галушкин А И 2006 Решение задач в нейросетевом логическом
3 82-8 базисе Нейрокомпьютеры: разработка, применение 2 49-71
[22] Joseph A C, David S 2006 Wishart Applications of Machine Learning [51] Галушкин А И 2010 Нейронные сети: основы теории Горячая линия
in Cancer Prediction and Prognosis Cancer Informatics 2 59–77 [52] Ясницкий Л Н 2008 Введение в искуственный интеллект:
[23] Shoeb A H, John V 2010 Guttag Application of machine learning to Уч.пос.для вузов 176
epileptic seizure detection Proceedings of the 27th International [53] Нейрокомпьютеры: Учеб. Пособие для вузов 2004 320
Conference on Machine Learning 975-82 [54] Dudani S A 1976 The distance-weighted k-nearest-neighbor rule

28
Review Paper
 COMPUTER MODELLING & NEW TECHNOLOGIES 2015 19(6) 14-29 Muhamedyev R

Systems, Man and Cybernetics, IEEE Transactions 4 325-7 Gradient Descent Proceedings of COMPSTAT'2010 177-86
[55] K-nearest neighbor algorithm Support vector machine. [61] Bottou L 1998 Online learning and stochastic approximation. On-Line
[Link] Learning in Neural Networks Cambridge University Press 9-43
22.02.2012[Link] [62] Chu C-T 2006 Map-Reduce for Machine learning on multicore.
nearest_neighbor_algorithm/ 5 Jun 2012. Advances in Neural Information Processing Systems Proceedings of
[56] Support vector machine. the 2006 Conference 281-310
[Link] 22.02.2012 17 [63] Leskovec J, Rajaraman A, Ullman J D 2014 Mining of Massive
Mar 2013 Datasets Cambridge University Press 476
[57] Linear discriminant analysis. [64] Amol G, Krishnamurthy R, Pednault E, Reinwald B, Sindhwani V,
[Link] Nov2012 Tatikonda S, Tian Y, Vaithyanathan S 2011 SystemML Declarative
[58] Dudoit S, Fridlyand J, Terence P 2002 Comparison of Discrimination machine learning on MapReduce Data Engineering (ICDE) IEEE 27th
Methods for the Classification of Tumors Using Gene Expression Data International Conference 231-42
Journal of the American Statistical Association 97(457) 77-87 [65] Tim K, Talwalkar A, Duchi J C, Griffith R, Franklin M J, d Jordan M
[59] Миркес E M 1998 Нейрокомпьютер. Проект стандарта I 2013 MLbase: A Distributed Machine-learning System Conference
[Link] 19 Jan 2015. on Innovative Dta Systems Research (CIDR) 7-9
[60] Bottou L 2010 Large-Scale Machine Learning with Stochastic

Author
Ravil I Muhamedyev, Kazakhstan, Almaty

Current position, grades: Head of Department CSSE&T, professor, International IT University, Almaty, Kazakhstan
University studies: International IT University, Almaty, Kazakhstan
Scientific interest: stochastic simulation, machine learning, simulation of anisochronous systems
Publications: 160 papers, 5 books

29
Review Paper

View publication stats