Abstract
Random Neural Networks (RNNs) are a class of Neural Networks (NNs) that can also be seen as a specific type of queuing network. They have been successfully used in several do- mains during the last 25 years, as queuing networks to analyze the performance of resource sharing in many engineering areas, as learning tools and in combinatorial optimization, where they are seen as neural systems, and also as models of neurological aspects of living beings. In this article we focus on their learning capabilities, and more specifically, we a general description of these models using almost indistinctly the terminology of Queuing Theory and the neural one. We present the standard learning procedures used by RNNs, adapted from similar well-established improvements in the standard NN field. We describe in particular a set of learning algorithms covering techniques based on the use of first order and, then, of second order derivatives. We also discuss some issues related to these objects describes their most relevant applications, and also provides a large bibliography.
Neural Networks, Random Neural Networks, Supervised Learning, Pattern
Ntroduction
Supervised Learning is an area of the Machine Learning field that refers to a set of problems wherein the information is presented according to an outcome measurement associated with a set of input features. The information is presented as a dataset of labeled samples. The aim is “to learn” the relationship between input and output features. This learning process is done based on a set of examples in order to generate a learning model with the power of “generalising”, this is to make “good” predictions for new unseen inputs. The research on Neural Networks (NNs) is considered to have started with the work of Warren McCulloch and Walter Pitts in 1943 (McCulloch and Pitts, 1943), and it has produced a rich literature with a strong concentration of papers in the 80s and 90s. In the 80s Rumelhart et al. explored the relationship between Parallel Distributed Processing (PDP) systems and various aspects
Arxiv:1609.04846V1 [Cs.Ne] 15 Sep 2016
of human cognition. The authors defined a general framework of a PDP system reactivating the research on connectionist models (Rumelhart et al., 1986b). The most popular PDP systems are NNs. In the last decades several books and journals have been dedicated to the research on NNs. The interest in the NN area arises from both its theoretic aspects and its different fields such as engineering, biology, pattern recognition, theoretical physics, applied mathematics, statistics, etc.
There are many types of NNs, and the related literature is huge. This article focuses on a particular class of NNs called Random Neural Networks . The RNN model was introduced by E. Gelenbe in 1989 (Gelenbe, 1989a,b). RNNs are mathematical objects that combine features of both NNs and queueing models. They been successfully employed in many types of applications: in learning problems, in optimization, in image processing, in associative memories, etc.
Here, we are specifically interested in the situations where the model is applied for solving supervised learning tasks.
A Rnn Is A Pdp Composed Of A Pool Of
interconnected nodes, which process and transmit information (signals) between them. Each node is a simple processor and it is characterized by its state, a whole number. The nodes receives two kinds of signals (negative and positive) from their neighbors or from outside.
When a negative signal arrives to a node, it produces an effect that can be related to neural inhibition, its state its decreased by one. The arrivals of positive signals provoke the opposite effect, the state is increased by one. The fire of signals by the nodes is modeled by Poisson processes, and the pattern of connectivity among the neurons follows stochastic rules.
The design of the model was inspired from the biological behavior of neuron circuits in the neo-cortex. The model considers the following biological aspects: the action potentials in the form of spikes, the exchange of excitatory and inhibitory signals among the neurons, the synapses (weighted connections between two neurons), random delays between spikes, reduction of neuronal potential after firing, arbitrarily topology (Gelenbe, 1989a). The model has been also proven very powerful, from the computational viewpoint. In (Gelenbe et al., 2004b) the authors shown that under certain algebraic hypothesis the RNN is an universal approximator. Besides, it can be easily implemented in both software and hardware. In order to apply the model for solving learning tasks, several learning algorithms have been adapted from the classic NN to RNNs, such as the Gradient Descent (Gelenbe, 1993a) and Quasi-Newton methods (Basterrech et al., 2011; Likas and Stafylopatis, 2000). The number of applications of the model in the learning area is very large, but the model has been also applied to solve combinatorial optimization problems, such that the Traveling Salesman Problem or the Minimum Vertex Covering Problem (Gelenbe and Batty, 1992; Gelenbe et al., 1993).
Ain Contributions
The first overview about RNN was presented in 2000 (Bakircioğlu and Koçak, 2000). A survey about RNN focused on networking application and self-aware networks was intro- duced in (Sakellari, 2010). Another general and helpful survey about RNN was presented in (Timotheou, 2010), where the authors describe the main applications of RNNs, cov- In (Georgiopoulos et al., 2011) the authors focused on RNN for solving learning problems, they identified some drawbacks of the RNN learning applications. In addition, an extensive literature about RNN was presented in (Do, 2011). In the 25th anniversary of the RNN model, we present this tutorial that contains the following contributions with respect to the previous published material.
• We introduce the model as a simple computational processor in a PDP framework, allelism between this particular PDP and the model as belonging to the queueing area.
• We provide a structured overview about the numerical optimization algorithms used for training RNNs. We introduce algorithms that use the first derivative information present Quasi-Newton methods that use the information of the second derivative of the cost function. In this practical guide, all the algorithms used for training are shown in detail following a homogeneous format.
• We present a critical review and new perspectives on RNN in supervised learning. We discuss technical issues concerning stability problems in the model itself, as well as problems related to the parameters’ optimization in the learning process. We discuss some points related to the computational advantages of the model, as well as about its weaknesses and limitations. The overview concludes with remarks concerning some new trends and future research lines.
In addition, this article presents an overview of some selected applications of the RNN in the supervised learning area. In particular, we comment on two applications where the experimental results show a better performance of the model with respect to other techniques of the literature.
Organization Of The Article
This article is structured as follows. Section 2 formally describes the RNN model as a learn- ing tool and in the framework of queueing theory. Section 3 presents algorithms for training the RNN model. It starts with a formal specification of the computational problems in supervised learning. In Sec. 3.2 we give a general description of RNN in the learning con- text. We present the Gradient Descent algorithm in Sec. 3.3, and we introduce second order optimization methods in 3.4. We describe the following algorithms: the Broyden-Fletcher- Goldfarb-Shanno in Sec. 3.4.1, the Davidon-Fletcher-Powell in Sec. 3.4.2, the Levenberg- Marquardt in Sec. 3.4.3 and one variation of it in Sec. 3.4.4. We present a critical review about the RNN model for solving learning problems in Sec. 4. Section 5 presents an overview of applications. We conclude and present new research trends in Sec. 6.
The Random Neural Network Model
This Section formally introduces the RNN model. It has four parts. First, we describe a single neuron (Random Neuron) as an elementary processor. Second, we present the RNN as a system composed by interconnected neurons. Third, we review the model in the framework of queuing networks. The section ends introducing the different topologies and structural concepts of the RNN.
Random Neuron (Rn)
A Random Neuron (RN) is a real parametric function of two real variables, with a real parameter called the neuron’s rate. The input variables are assumed to be non-negative. The rate is positive. If x ≥0 is the first input variable, y ≥0 is the second one, and if r > 0 is the rate of the neuron, then the output is the real z given by the expression
(1)
See that a RN is characterized by its rate r. We can see the neuron as an input-output system with two “input ports”, one for x and the other one for y, and one output port for z. The ports associated with the output and with the first input value are called positive; the input port corresponding to the second input variable y is called negative (the reason for this is explained later), but all the variables involved are non-negative real numbers.
Figure 1 shows a neuron as an input-output device. When x ≥r +y we say that the neuron is saturated. Figure 1: A zoom on a random neuron (RN) seen as a “black-box” system; the inputs are the reals x, y ≥0; the parameter is the rate r > 0, and the output is the real z; we say that the first input variable x is connected to the positive input port of the RN (depicted ‘+’) and the second input variable y to the negative input port (depicted ‘−’); the output port is also said to be positive (and it is depicted ‘+’ in the figure) The output value z is seen as a measure of the activity of the neuron (as in most input- output systems). As such, see that z is increasing in x and decreasing in y. In real neurons, which also are input-output systems, the input signals belong to two types, excitatory signals, which are those contributing to the neuron’s activity measured by its output (the higher the excitatory signal, the higher the neuron’s activity) and inhibiting inputs playing the opposite role. This is why we call positive the signals arriving at the ‘+’ input port, and negative those arriving at the ‘−’ one.
We will say that a RN is controlled if its output z is modified according to the rule
(2)
So, in this case the RN’s output is always less than or equal to its rate, and it is equal to its rate when the neuron is saturated. In the case of the initial definition (1), the neuron is said to be uncontrolled.
Random Neural Network (Rnn)
A Random Neural Network (RNN) is a network composed of N interconnected RNs, that implements a function from R2N into RO, for some 1 ≤O ≤N, in the following way. We are given N RNs denoted 1, 2, . . , N (that is, we are given N strictly positive reals r1, r2, . , rN), and two N × N matrices denoted by P+ = (p+
Ij), Whose
components are probabilities. Both matrices and their sum are substochastic, that is, for
Ij + P−
ij) < 1 are called output neurons. We denote by O their number (so, 1 ≤O ≤N). The network outside is often referred to as the neuron’s environment with which the system operates (Rumelhart et al., 1986b).
Let us denote the 2N input variables of the network as x1, . . , xN, y1, . , yN. Then, the output of the network is the set of outputs of each of its output neurons. We need only to specify how are determined the inputs to the N RNs (the outputs are given by the previously described rules, in the uncontrolled or controlled cases). Let us call ui (respectively vi) the positive (respectively negative) input to neuron i. Then, the following equations must be
N Words, The Fraction P+
ji of the output zj of neuron j adds to the positive input ui to
Neuron I, And The Fraction P−
ji of the output zj of neuron j adds to the negative input vi to i. Of course, this means that the reals z1, . . , zN must satisfy the non-linear system of
Ri,
i = 1, 2, . . , N. This needs some technical discussions about the existence and unicity of solutions to this system, as we will see below.
(3)
we have 0 ≤di ≤1, and that neuron i is an output neuron when di > 0. We can also say that the network of neurons sends the part dizi of zi through the output port of i.
Observation:
in general in the learning applications, we use a RNN with N neurons as a function from RI to RO where I < 2N or even I < N, by setting 2N −I of the standard 2N input variables to a fixed value (typically to 0). We will see soon this frequent situation.
An important particular case covering all the applications done so far for these objects as learning tools is as follows. The network with N neurons implements a function with I ≤N input variables and O ≤N output variables. The input variables are denoted by x1, . . , xI, which are all connected to the positive port of I neurons called input neurons. In other words, no input variable is connected to a negative port. The function output is the set of outputs generated by the O output neurons. A group of neurons can have no interactions with the environment (when I + O < N). We call those units hidden neurons. Note that a neuron can be both an input and an output one.
A Queueing View Of The Random Neural Networks
The RNN method has been used with two different interpretations both referring to exactly the same mathematical model. One is the already described type of interconnected RNs. Another one is a type of queueing systems called G-queues and G-networks.
The First
interpretation is often employed in the Machine Learning contexts and the second one is applied in Performance Evaluation, for example. We begin by describing a single queue where customers arrive according to a Poisson process, say with rate λ > 0, and service times are exponentially distributed with param- eter r > 0. It is assumed that service times are mutually independent and that they are also independent of the inter-arrival times. This server queue is named M/M/1 queueing model (Kendall, 1953). At any time t the state of the system S(t) is the number of cus- tomers present in the queue. The queue storage capacity is infinite.
The Stochastic Process
{S(t), t ≥0} is a continuous time homogeneous Markov process on the non-negative inte- gers. We define the utilization factor of the queue as the ratio ϱ = λ/r. When the process
P(K) = Lim
t→∞P(S(t) = k) = ϱk(1 −ϱ).
(4)
A Jackson queueing network consists of N interconnected queues with the following characteristics. For each queue i the service time is exponentially distributed with rate ri. When a customer completes the service at queue i, it will either move to queue j with routing probability pij or leave the network with probability di (di = 1−PN
J=1 Pij). Customers Arrive
from the environment to queue i according to a Poisson process with rate λ+
I . At Any Time
t, the system state is the vector S(t) = (S1(t), . . , SN(t)), where Si(t) denotes the number of customers in queue i at time t. The assumptions about the independence among the
Processes Can Be Summarized As Follows:
• arrival processes, service processes and switching (routing) processes are independent
Of Each Other;
• at each server, the service times are independent of each other; • at each switching point, the successive switching results are independent of each other. We define Ti as the mean throughput at queue i. In order to avoid a trivial case, we
Assume That At Least One Of The Λ+
i ’s is non-zero (strictly positive). In addition, assuming that the system is irreducible (for any two nodes i and j in the Markovian graph there exists a path from i to j), and in equilibrium, Ti for all i can be determined by solving the flow
(5)
The strongly connected property of the Markovian graph implies that exists an unique (and strictly positive) solution. The utilization factor of queue i is given by ϱi = Ti/ri. A G-network (or equivalently, an RNN) is an extension of a Jackson’s network where there is a new entity in the system: negative customers. As in the previous network, in a G-network there are Poisson arrivals, probabilistic routing among the queues, exponential service rates and usual independence among the corresponding stochastic processes. There are two types of customers in the system, positive ones that operate as we defined for the Jackson network, and the negative ones that operate as follows. When a negative customer arrives at a non-empty queue, it destroys a positive customer in this queue, if any, and disappears. If there are no customers in the queue, a negative customer does not operate, it just disappears from the system. In several works negative customers are referenced as signals, thus there are two entities, customers (positive customers) and signals (negative customers).
In (Gelenbe, 1989a, 1991a) Gelenbe shows that, in an equilibrium situation, the ϱis
(8)
with the supplementary condition that, for all neuron i, we have ϱi < 1. An important result associated with open Jackson networks and with G-networks is called the product form theorem. Gelenbe proved that under Markovian assumptions G-networks have a product form equilibrium distribution. This means that the joint equilibrium distribution of the queue states is the product of the marginal distributions. For more details see (Gelenbe, 1989a).
Observation: Let us unify the notation that will be used through this article. So far we introduced the RNN as a function, next we presented the concept using a queueing point of view. In the rest of the article, we follow the most often used notation presented in (Gelenbe, 1989a). Let N be the number of interconnected neurons. For each neuron i its service rate is denoted by ri, the value at its positive port is denoted by T +
The Positive Input Value Λ+
i (the Poisson rate of the customers coming from outside), the
Negative Input Value Λ−
i (the Poisson rate of the negative customers coming from outside), and the probability to send information to the environment denoted by di characterize the interaction of i with outside. The output of neuron i is its activation rate ϱi. The connections between two neurons i and j are given by the probabilities p+
I,J. Figure 2 Shows
the main parameters involved in a RNN. We will introduce in our notation the concept of weights. For any two neurons i and j, they are defined as: w+
I,J = Rip−
i,j. The first one is called positive weight and the second one is called negative weight. Note that the weights are, by definition, positive reals. In the context of NNs, the traditional notation used for the weight connection (direct edge) between the nodes i to j is often denoted as (j, i). In the RNN context, the reverse order is traditionally used. This originates in the first paper about supervised learning with RNNs (Gelenbe, 1993a).
Figure 2:
A representation of a RN. The figure shows the main parameters involved in a RN embedded in a network.
The Network Topology
So far, we defined the RNN as a parallel distributed system composed of simple processors (RNs). Therefore, the network is a graph where the RNs are their nodes; the existence of an arc between two nodes is given by certain probability. The two most common topologies of networks are multi-layer feedforward and recurrent networks.
Feedforward Topology
We start describing the feedforward case. The identifying property is that there are no cyclic connections among the neurons, no circuits in the (directed) graph. The architecture of the graphs consists of multiple layers of neurons in a directed graph. There are three types of layers popularly known as input, hidden and output layers. The neurons can have only connections in a forward direction, from the input neurons to the output neurons, traveling through the hidden ones. Only neurons belonging to the input and to the output layers can exchange information with the environment. The activity rate for each output neuron is computed using a forward propagation procedure.
A Representation Of A Feedforward
network with one hidden layer is illustrated in Figure 3.
Figure 3:
A representation of a Feedforward Neural Network. The figure shows a network with a single hidden layer. The flow of information is from the the input neurons through the output ones. In this example there are 5 input neurons full connected to 9 hidden neurons, and the hidden neurons are full connected with 4 output neurons. A network with this topology is used for mapping a relationship from a 5-dimensional space into a 4-dimensional space.
The feedforward case has been widely used in supervised learning due to the fact that training process is much faster than in the recurrent case. Besides, the feedforward networks are easier to analyze than networks with recurrent topologies. One advantage is that the non-linear system of equations (6), (7) and (8) can be formally solved. Then, we can express the activity rate of the output units as functions of the inputs variables of the system. Let I be the number of input neurons, H is the number of hidden neurons and let O be the number of output neurons. We arbitrary index the input neurons from 1 to I, the hidden neurons from I + 1 to I + H and the output neurons from I + H + 1 to I + H + O = N.
We can compute the activity rate of the neurons using a forward procedure as follows. At the first step, we compute the activity rate of the input neurons, next the activities of the hidden neurons and finally those of the output neurons. Input neurons are the only ones that receive signals from the environment; so we set λ+
I = 0 For All I ∈[I + 1, N]. The
activity rates are given by the following explicit expressions:
,
∀o ∈[I + H + 1, N]. More general feedforward networks consist of successive layers where the signals can circulate only in one direction.
Recurrent Topology
In the case of recurrent networks circuits are allowed. The existence of directed cycles has an important impact in the model: we can not compute the rate activities of the output neurons as functions of the network inputs (except, of course, when N ≤4). A RNN with circuits connects to the concept of dynamical systems, rather than to functions, there is an idea of time implicit in the model. For simplicity we assume discrete time and we avoid to use temporal notation in ϱ. At each time instant, the network is characterized by an internal state ϱ formed by the activity rates ϱ = (ϱ1, . . , ϱN). When an input pattern is presented to the network, the network updates its internal state. For computing the network state we must solve the system of equations (6), (7) and (8), where the unknown parameters are ϱi, T +
And T −
i , for all i. For solving this system is necessary to perform a fixed point procedure (a summary about this computation is given in (Timotheou, 2010)). The output of the network is given by the state of the output neurons. Unlike the feedforward case, a recurrent network can use its internal states to process sequences of inputs. As a consequence, the recurrent case is often used for solving problems where the dataset presents temporal dependencies.
3. Random Neural Networks in supervised learning problems In this Section we present the algorithms used for learning. The Section starts with a formal definition of the supervised learning problem. Next, we present the algorithms of Gradient Descent type for training the RNN. Then, we introduce the algorithms that use the Hessian or an approximation of the Hessian matrix for training the RNN. We close the Section with a general discussion that covers topics such as: limitations of the algorithms in the numerical optimisation, analysis of the algorithmic time complexity, applications of the RNN concepts in the Reservoir Computing area, a discussion about the computational power of the RNN for approximating any regular function, and an analogy of the model with other NNs.
Specification Of A Supervised Learning Problem
We begin by specifying a supervised learning problem. Given a dataset L = {(a(k), b(k)), k = 1, . . , K}, where a(k) ∈A and b(k) ∈B, with A and B some given finite dimensional spaces (typically, sets of real vectors, or of vectors of elements in some alphabet, or a mix of both types of objects). The learning procedure consists in inferring a mapping ν(a, L) in order to predict the b values, such that some distance d(ν(a(k), L), b(k)) is minimized for all k ∈{1, 2, . , K}. We denote by I the dimension of the input vector a and O the dimension of the output vector b.
For each instance a(k), let us denote ϱ(k) the output produced by the network, that is ϱ(k) = ν(a(k), L). The distance above referred is a function L(·) named loss function or cost function that measures the deviations of the model predictions are the criteria of Sum-of-Squared Errors (LRSS) and the Kullback-Leibler distance (LKL), also called cross-entropy (Hastie et al., 2001; Schumacher et al., 1996). The RSS is defined
(9)
where ci = 1 when i is an output neuron, otherwise ci = 0.
There Are Several Slight
modifications of the previous distances, one of those is the Mean Square Error (MSE) given
(10)
In supervised learning when the targets are categorical or discrete variables the problem is called classification problem; when the target is a real vector, the problem is called regression problem.
Random Neural Network As A Learning Tool
A first approach for applying the RNN model in supervised learning tasks was introduced at the beginning of the 90s by Erol Gelenbe (Gelenbe, 1993a). This procedure is based on the classical backpropagation algorithm (Rumelhart et al., 1986a). As in practice, the input and output variables in learning problems are bounded with known bounds, the algorithm described in (Gelenbe, 1993a) assumes that a(k) ∈[0..1]I and b(k) ∈[0..1]O, for all sample k. The RNN model as a predictor is a parametric mapping ν(a, w+, w−, L), where the parameters w+ and w−are adjusted minimizing the loss function. In (Gelenbe, 1993a) was considered the quadratic error presented in the expression (10). The network architecture is defined with I input nodes and O output nodes. There are not additional constraints regarding the network topology, that means the network can be feedforward with one or several layers, or it can be recurrent network. We set the port of the input neurons each time that an input pattern a(k) is offered to the network. The inputs to the positive ports are
I
; the negative ports of input neurons are conventionally
Set To Zero (Λ−
i = 0). The output of the model is a vector of the activity rates produced by the output neurons. The adjustable parameters of the mapping are the weights connections among the neurons. We follow this Section describing the optimization algorithms that have been introduced over the last decades.
The Gradient Descent Optimization Algorithm
We can now describe the gradient-based algorithm that was used so far for training the RNN model (Gelenbe, 1993a). We define two set of neurons I and O that correspond to the set of input neurons and the output neurons, respectively. The weights are initialized
And W−(0)
u,v , for all u and v. At the τth-iteration, we select a