Neural Network Mppt Matlab

A Tutorial about Random Neural Networks in Supervised

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 present a practical guide for using the RNN to solve supervised learning problems. We give 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 and present new perspectives about their use in supervised learning problems. The tutorial describes their most relevant applications, and also provides a large bibliography.

Keywords:

Neural Networks, Random Neural Networks, Supervised Learning, Pattern

1. Introduction

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 computational power for solving real problems. NNs have been successfully applied in many 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).

Main 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- ering several topics including biology, reinforcement learning, and optimization problems.

In (Georgiopoulos et al., 2011) the authors focused on RNN for solving learning problems,

2

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, instead of using concepts coming from queueing systems. Besides, we present a par- 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 of a quadratic cost function, such that the gradient descent type algorithms. We then 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.

2. 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

3

of queuing networks. The section ends introducing the different topologies and structural concepts of the RNN.

2.1 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

X

r + yr.

(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



r.

(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.

2.2 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



≤1.

Ij + P−

ij) < 1.

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

Zjp−

ji.

In 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

5

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.

2.3 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

6

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

J=1

Tjpji.

(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 +

I And To The Negative Port Is T −

i .

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

7

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.

2.4 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.

2.5 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

9

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.

2.6 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.

3.1 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 ϱs and the targets bs. Several types of loss functions have been used, the main examples 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.

3.2 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.

3.3 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

A(K), B(K)

, k = 1, . . , K, where k = τ −1 mod K + 1. The weight correction is computed following the delta learning rule (Rumelhart et al., 1986a), meaning that the weight correction is proportional to the partial derivative of the loss function with respect to each weight. From (3), the service rate of neuron i verifies

(11)

for all i ∈I ∪H. Also note that ri is a free-parameter when i is an output neuron. At each step τ, the current weight value descends in the direction of the negative gradient of L(·); the update rule for positive and negative weights (denoted with superscript ∗) of

W=W(Τ−1)

.

(13)

The parameter η ∈[0, 1] is called learning factor. It is used for tuning the convergence speed of the algorithm. Here, we set ci = 1 for all output neuron i, otherwise ci = 0.

Equation (13) leads to the following simplified expressions.

0,

otherwise.

12

Then, denoting by ϱ the vector of activity rates ϱ = (ϱ1, . . , ϱN):

(14)

where I and Ωare N-dimensional matrices, I is the identity, and the element (i, j) of Ωis

J

.

(15)

The partial derivatives were explicitly computed for a feedforward RNN with a single layer in (Georgiopoulos et al., 2011). An online version of the Gradient Descent (GD) algorithm is an iterative method that processes the input patterns one-by-one realizing the following two main operations: to compute the direction of the gradient of the loss function and to update the weights using the expression (12). The method can either be stopped using an arbitrary number of iterations or when the performance measure is smaller than some threshold value. The online version of the GD algorithm is specified in Algorithm 1. In contrast, an offline training scheme (also called batch algorithm) uses the whole pattern data before modifying the model parameters.

An input is offered to the network, the direction of the gradient is computed. When all data have been presented, the gradient directions are averaged. Finally, each weight is updated using the average of the gradient directions. In the Machine Learning literature coexists two opposite views concerning these two training schemes. As far as we know there has been no consensus on which scheme (on-line or offline) is more efficient for training a learning model (Nakama, 2009; Wilson and Martinez, 2003).

3.3.1 Slight modification of the gradient descent algorithm A slight variation of the GD algorithm for RNN was proposed in (Basterrech and Rubino, 2013b). The authors increase the amount of adjustable parameters during the training of the gradient descent algorithm without modifying the network topology and the time complexity of the algorithm.

They consider as adjustable parameters in the training objective the

For All Hidden And Output Neuron I, And The

service rate ri for all output neuron i. Considering the training error given by the expression (10), the update learning rule is given as follows. Let ∆, P, Λ+ and Λ−be matrices of dimensions N ×N, where the matrix

Pi,I = Ρi,

and the matrices Λ+ and Λ−have at the position (i, u) the value ∂ϱi

U

, respectively.

13

Algorithm 1: Specification of the GD learning algorithm for the RNN model (online version).

Inputs

: {(a(k), b(k)) : k = 1, . . , K} (training dataset), η (learning rate), maxIters (max. number of iterations), the topology of the RNN (that is, the routing

1 Τ = 0;

2 Initialize all weights (for instance, randomly); // we get w∗(0)

8

For all i̸ ∈O compute ri using (11); // weights are those at τ −1

12

Evaluate convergence. where Ωwas defined in the expression (15). Then, for each input pattern (a(k), b(k)) at the

(18)

where [I −Ω]−1, Λ∗and T ∗are computed using the current input (a, b) and Λ∗

U Denotes

the column u of the matrix Λ∗.

3.3.2 Technical Issues

We discuss here some technical issues related to the learning process, well illustrated by the GD procedure. Recall that the model can be seen as a network of queues (it is actually born in this way). This has some consequences, that have an impact on the design algorithmic decisions. A first point concerns the use of (12) for updating the weights. Indeed, it may happen that (12) leads to a new value for some weight that is negative or null. This does

14

not fit the analogy with a network of queues, or even a network of spiking neurons where the weights model mean throughputs of spikes: weights should be positive numbers. We

Can Accept A Null Value For Some W∗

u,v interpreted as the fact that there is actually no such connection between u and v, but a negative one has no interpretation. The usage is to respect this analogy, modifying the updating rule such that the weights are never negative.

Three possible approaches are proposed in (Gelenbe, 1993a):

(19)

and in the case that some weight is assigned value zero, then to apply one of the

Following Rules:

– fix a null value to this weight, and do not change it anymore in future iterations; – assign a zero value to this weight, but allow positive updates in subsequent iter- ations, keeping using (19).

• Another option is to decrease the value of η and update again the weight using (12). If the new weight is still negative, repeat until obtaining a positive number or stop the loop using some control parameter. Formally, this means that the learning factor becomes a variable parameter in the method. In a nutshell, the global idea in descent methods is to decrease little by little the learning factor, as we get closer and closer to a local minimum. Global accuracy can also be improved (but also cost) if η(τ), say, is built by a supplementary optimization process (this is called line searching in the area) (Press et al., 2002). We do not enter these details here.

• An alternative option was presented in (Likas and Stafylopatis, 2000). The authors

U,V

2. Then, instead of using the expression (14), we proceed as follows

U,V

.

(20)

3.3.3 Computational cost of the gradient descent algorithm When one data pattern is presented to update each weight in the network the main com- putational effort consists of computing [I −Ω]−1 using (14) (Gelenbe, 1993a). This effort has O(N3) time complexity. A remark made in (Gelenbe, 1993a) consists in that when a m-step relaxation method is applied the time complexity decreases to O(mN).

Additionally, the general scheme of the algorithm can be adapted when we use a feedfor- ward RNN. In this case the matrix I −Ωbecomes triangular, so the computational cost of computing its inverse decreases to O(N2). Also, the computational effort to compute each activity rate in feedforward networks is reduced, due to the the activity rate of any neuron depends only on the neurons in the preceding layers.

3.4 Second Order Optimization Methods

In this Section, we present the optimisation methods for RNN that use the information given by the second derivative of the loss function. We start introducing the Gauss-Newton (GN) methods, next we explore the Quasi-Newton (QN) techniques. We present four particular algorithms developed for training RNNs: the Broyden-Fletcher-Goldfarb-Shanno (BFGS), the Davidon, Fletcher and Powell (DFP), the Levenberg-Marquardt (LM) and the LM with Adaptative Momentum (LM-AM).

The Gauss-Newton (GN) algorithm is a technique for solving non-linear least squares problems that incorporates the second derivatives of the loss function or an approximation of those. Unlike the algorithms of first derivatives that can solve a large non-sparse optimization problems, a GN method can only be used when the loss function is given by a quadratic objective function, for instance the expression (10).

The Methods Of The Gn Type Are

generally considered more powerful in terms of accuracy and time than the algorithms that only use the first derivative information. The GN method is based on an expansion of the loss function in the Taylor series. Let M be the number of adjustable parameters (the number of weights w+

I,J). We Define

the M-dimensional vector w that collects in some arbitrary order the weights w+

I,J And W−

i,j. Let a be an input vector on the network. The GN algorithm employs a linear approximation

(21)

where δ is a M-dimensional vector that represents a small correction of the weights. The solution is found by solving the M × M set of equations (called normal equations)

(22)

where G and J are the gradient vector and the Jacobian matrix, respectively. For computing G and J we proceed as follows. Let e(k) be the residual row vector of dimension O for the

Kth Input-Output Training Pair,

e(k) = b(k) −ϱ(k).

(23)

Collecting those residuals, we have a vector E of S × 1 dimensions, with S = KO. Then, the gradient vector of L(·) has M × 1 dimensions and its mth element is

∂Wm

es.

(24)

The Jacobian matrix has dimensions S × M and its (s, m) element is Js,m = ∂Es/∂wm.

(25)

For computing the partial derivatives of (24) and (25) we use the expressions presented in (14).

16

The GN method is a batch type algorithm. We call an epoch of the GN algorithm when all the patterns in the training set are used (Schwenk and Bengio, 2000). At each epoch τ, the weight correction δ is computed, next the weights are updated as follows:

(26)

where α ∈(0, 1] is computed using a line search technique (Press et al., 1992).

In The

canonical GN method this parameter is set to 1. A better strategy is tuning α with less values until some suitable point. For details about how to tune α see Chapter 9 of (Press et al., 1992).

The GN method for solving the problem of minimization using NNs presents several drawbacks. The method requires a good initial solution, that is often not available (Drucker and Le Cun, 1992). Another drawback is that the GN method requires computing the Hes- sian matrix H (H = JTJ) and its inverse, both computations can be expensive. Therefore, the method is expensive in time and in storage.

A Quasi-Newton (QN) method type is a variant of the GN algorithms that uses an approximation of the Hessian matrix ( eH) for solving the normal equations. The general approach behind a QN method is an iterative procedure that consists of starting with a positive and symmetric matrix and updating it in successive steps in such a way that the matrix remains positive definite and symmetric. The update rule always moves in a downhill direction for solving the normal equations and guarantees that eH approximates H. As we already commented so far, the implementation of the second order methods is offline, thus at each epoch the network outputs are computed for the whole of input patterns. We present in Schema 2 a procedure that shows how to compute those model outputs. In the following of this Section we will use this schema as a black box being a part of the GN and Quasi- Newton algorithms. In the remainder of this Section, we present four algorithms based on approximations of the Hessian matrix.

Algorithm 2: Auxiliary schema. Given a RNN the procedure shows how to compute the network outputs for the whole input dataset. The procedure returns a K × N matrix, that has the vector ϱ(k) computed with the input pattern a(k) in its k-row.

Inputs

: {(a(k), b(k)) : k = 1 . . , K} (training dataset), the topology of the RNN Outputs: The neuron activity rate produced by the whole of input patterns: C a

Using (6), (7) And (8);

// see also 3.3.2 for many relevant technicalities

17

3.4.1 The Broyden-Fletcher-Goldfarb-Shanno algorithm The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method for the RNN model was introduced in (Likas and Stafylopatis, 2000). The BFGS is an offline algorithm, which at each epoch τ an approximation of the Hessian matrix eH(τ) is computed. The method starts using the identity matrix as the initial Hessian approximation eH(0) = I. The Choleski factorization is used for decomposing a symmetric and positive definite matrix into two triangular matrices.

Choleski factorization is more efficient than alternative methods for solving linear equations, it is about two times faster than the alternative ones. For details about the implementation of this factorization see (Press et al., 1992). The matrix eH(τ) is decomposed using Choleski

Factorization As

eH(τ) = L(τ)LT(τ).

(27)

Let c be an auxiliary scalar defined at each epoch as

(W(Τ) −W(Τ−1))T Eh(Τ)(W(Τ) −W(Τ−1))

.

We Define An Auxiliary Vector V As

v(τ) = c(τ)L(τ)(w(τ) −w(τ−1)).

Vt(Τ)V(Τ)

.

(30)

The update of the Hessian matrix approximation is given by eH(τ+1) = A(τ)AT(τ).

Finally, The Weight Update Is Given By Δ Solving

eH(τ+1)δ(τ+1) = −G(τ).

(32)

In summary, the BFGS method for RNN presented in (Likas and Stafylopatis, 2000) is defined in Algorithm 3.

3.4.2 The Davidon-Fletcher-Powell Algorithm

The Davidon-Fletcher-Powell (DFP) algorithm is another widely used QN method some- times referred as Fletcher-Powell (Press et al., 1992). The algorithm is a slight variation of BFGS algorithm, the difference between them is given in the following terms. The scalar c

(33)

and the vector v is such that solves the linear system, L(τ)v(τ) = c(τ)(G(τ) −G(τ−1)).

18

Algorithm 3: Specification of the BFGS algorithm for the RNN model.

Inputs

: {(a(k), b(k)) : k = 1 . . , K} (training dataset), maxIters (max. number of

1 Τ = 0;

2 Initialize all weights (for instance, randomly); // we get w∗

13

Compute c, v and A using (28), (29) and (30), respectively;

The Matrix A Is Determined By Computing

A(τ) = L(τ) −(G(τ) −G(τ−1))((w(τ) −w(τ−1))TL(τ) −vT(τ))

(W(Τ) −W(Τ−1))T(G(Τ) −G(Τ−1))

.

(36)

and we compute the search direction δ for update the weights solving the expression (32). According empirical results the BFGS performs better than the DFP method (Press et al., 1992).

Although, for some specific benchmark problems the DFP reached better accuracy than DFGS (Likas and Stafylopatis, 2000). The algorithm is summarized in 4.

3.4.3 The Levenberg-Marquardt Algorithm

The Levenberg-Marquardt (LM) algorithm is one of the most standard optimization methods used in the NN area (Press et al., 1992; Ampazis and Perantonis, 2000; Hagan and Menhaj, 1994). The LM is a sort of compromise between an offline version of the GD algorithm and a GN method (Marquardt, 1963; Press et al., 1992). The algorithm was introduced for training RNN in (Basterrech et al., 2011).

19

Algorithm 4: Specification of the DFS algorithm for the RNN model. The DFS and the BFGS algorithms differ only in details. As a consequence, we introduce the DFS referencing the schema already presented in Algorithm 3.

I,J : I, J = 1, . . . , N} (Network’S Weights)

// Perform the lines 1 until 7 of Algorithm 3.

Compute A Using (35);

// Perform the lines 14 until 17 of Algorithm 3. At each epoch τ, the approximation of the Hessian matrix is given by,

(37)

where µ(τ) > 0 is called dumping term, I is the identity matrix of dimension M × M, and J is the Jacobian matrix that is computed using (25). The dumping term µ is modified at each epoch. In the case that the prediction error decreases, then the dumping term is

Reduced By Some Constant Value Β

µ ←µ/β.

(38)

Otherwise, the dumping value is increased by a factor of β, µ ←µβ.

(39)

So far, the factor for modifying the dumping term was set as β = 10 (Press et al., 1992; Basterrech et al., 2011). The LM algorithm computes the weight correction δ solving the system (32). Then, the update rule for the weights is given by the expression (26). In (Basterrech et al., 2011), this weight update considers only the search direction δ. In other words, the authors set α = 1 in the expression (26). The algorithm can evolve through either of extreme possible situations are (Hagan and Menhaj, 1994; Press et al., 1992): • If the dumping term approaches to zero, the LM basically performs as the Gauss- Newton method.

• Otherwise, when the dumping term is very large, the matrix eH becomes diagonal dominant, so the update rule is similar to the updating expression of gradient descent method using a learning factor of 1/µ.

20

Concerning the stopping conditions, the method can fail if the Jacobian matrix becomes singular or nearly to singular. Even if this situation is rare in practice, a control of the condition number of J can be useful (Press et al., 1992). Besides, it is necessary to control that the dumping factor satisfies some boundary conditions. It is not recommended to stop after an epoch wherein the training objective error increases. For more technical discussion about the stopping criteria of the LM see (Press et al., 1992). We present the LM procedure in Algorithm 5.

Algorithm 5: Specification of the LM algorithm for RNN.

Inputs

: {(a(k), b(k)) : k = 1 . . , K} (training dataset), maxIters (max. number of iterations), the topology of the RNN, µ (dumping term), β (constant to

Tmp = W∗+ Δ;

// weights w∗are those at τ −1, see also 3.3.2 for technicalities

Evaluate Stopping Conditions;

3.4.4 Levenberg-Marquardt with adaptive momentum training A variation of the LM method applied to NNs was developed in (Ampazis and Perantonis, 2000; Ampazis et al., 1999). This approach was adapted for the case of RNN on learning problems in (Basterrech et al., 2011).

Deployment In Out-Of-Position Situations

D. Bendjaballah1, A. Bouchoucha1, M. L. Sahli1,2* and J-C. Gelin2

Abstract

Side-impact collisions represent the second greatest cause of fatality in motor vehicle accidents. Side-impact airbags have been installed in recent model year vehicle due to its effectiveness in reducing passengers’ injuries and fatality rates. In meeting these requirements, simulations of folding and deploying airbags are very useful and are widely used. The paper presents a simulation method for the deploying airbags using three materials in different working conditions. Finite element analysis is primarily used to evaluate this concept. In these simulations, the gas flow is described by the conservation laws of mass, momentum, and energy. The numerical results indicate that the FE method in this paper is capable of capturing airbag deploying process accurately.

Keywords: Airbag simulations, Out-of-position, Crash, Modeling, Out-of-position

Background

The passive safety of cars has become a very high prior- ity issue for the automotive industry. Today, there are not only one or two airbags in a car; certain models have ten times more than that. With the increasing usage of airbags, the number of accidents where the airbag itself can cause an injury to the occupant also increases

(Augenstein Et Al. 2003; Gabauer And Gabler 2010;

Audrey et al. 2011). As is well known, safety belts are also now devices designed to provide protection to the users of vehicles during crash events, minimizing the loads necessary to adapt their movement to the move- ment of the car (Freesmeier and Butler 1999; Schmitt et al. 1997). In general, the seat belt is designed to restrain the occupant in the vehicle and prevent the

Occupant From Having Harsh Contacts With Interior

surfaces of the vehicles. The airbag acts to cushion any impact with vehicle structure and has positive internal pressure, which can exert distributed restraining forces over the head and face. As a safety component of auto- mobile, an airbag decreases occupants’ injury likelihood effectively in case of an accident (Ruff et al. 2007). These safety elements can reduce the death rates on the roads, and its protection effects have been widely approved (Crandall et al. 2001; Teru and Ishikawa 2003). With computational tools such as finite element methods designed for dynamic contact problems, crashworthiness simulations can now be used with reliable accuracy to evaluate occupant protection in various collision condi- tions with safety metric/parameters such as acceleration, head injury criteria, intrusion distance, intrusion vel- ocity, and neck forces (neck injury risk or whiplash).

Thus, new types of airbag products are being developed to handle different collision scenarios.

Become Standard Equipment On Most New Passenger

vehicles (Braver and Kyrychenko 2004; Teng et al. 2007; Yoganandan et al. 2007). The airbag cushion is com- posed of a woven fabric which is rapidly inflated during a car crash. The airbag dissipates the passenger’s kinetic energy thereby reducing injury through biaxial stretching of the fabric bag and escaping gas through vents. There- fore, the performance of the airbag is greatly influenced by the mechanical properties of the fabric. Generally, air bags are designed to deploy in a crash that is equivalent to a vehicle crashing into a solid wall at 8 to 14 mph.

Air bags most often deploy when a vehicle collides with another vehicle or with a solid object like a tree. There are various types of airbags: frontal, side-impact, and curtain airbags. In general, the passenger side airbags are usually larger than the driver airbags (see Fig. 1).

Besançon, France

© The Author(s). 2017 Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Bendjaballah et al. International Journal of Mechanical

Doi 10.1186/S40712-016-0070-2

Extensive studies have shown that the airbag deploy- ment in load cases consists of two occupant loading phases: a punch-out effect where the airbag bursts out of its container with the airbag and airbag module cover accelerating towards the occupant and a second loading phase during which the airbag is taking on its deployed shape and volume (membrane-loading effect). Bankdak et al. (2002) developed an experimental airbag test system to study airbag-occupant interactions during close proximity deployment. The results provided insight for simulating the effect of inflation energy and mass flow on target response. Bedard et al. (2002) found that while left-side (driver-side) impacts accounted for only 13.5% of all crashes, the fatality rate among these

Crashes Was 68.3% In Comparison To Front Impact

(48.3%), right-side impact (31.3%), and rear impact (38.4%). These studies underscore the importance of oc- cupant safety during side-impact collisions. In the last years, the current market requested to reduce the time and cost airbag development. In order to achieve this result, virtual simulations play an important role since they allow to minimize the number of experimental tests (Pei et al. 2013; Cao et al. 2014). Several simulation models of airbag were established (Wang et al. 2007). It is feasible to optimize the parameters of airbag deploy- ment using simulation technology. Experimental and numerical studies have quantified injury risks to close- proximity occupants from deploying side airbags. These studies have focused on the prevention of the most ad- verse effects of airbag deployment (Duma et al. 2003).

Other studies have proposed airbag characteristics to minimize particular biomechanical responses (Haland and Pipkorn 1996). In a more recent study, Marklund and Nilsson (2003) compared deformation patterns with experimental data as well as the computational costs associated with three different airbag deployment simu- lation methods; they concluded that the SPH method is relatively inexpensive and produces incremental deform- ation patterns that compare most closely to the experi- mental results. The process of inflation of an airbag is one of the determining factors in saving lives. The duration from the initial impact of the crash to the full inflation of an airbag is about 40 ms, and during this time, the airbag goes from being in a folded state to a fully inflated state, with a high internal pressure. After achieving this state, the airbag begins to deflate, thus providing a nice cushion for the body impacting it.

Ideally, the person in the crash should come into contact with the airbag at this time. In the present study, a large volume passenger side airbag model is developed to handle different collision scenarios. The main aim is evaluate the performance of deploying of passenger side airbag using finite element methods (FEM).

Materials

The tensile specimens were made in different airbags (P: Peugeot, R: Renault, and VW: Volkswagen) with a length of 200 mm long and a width of 40 mm. Table 1 shows the mechanical properties of the airbag.

Tensile Tests

To determine the mechanical properties of the material of airbag used in the test pieces, tensile tests were performed on Lloyd EZ20 universal testing machine in Constantine. These tests were conducted using rect- angular samples. The axial force and axial displacement acquired during a test are converted into stress and the strain in order to be used for the fabric material model.

The continuous recording of the stress-strain data was performed during both the load and unload phases. A minimum of five samples were made in order to check the repeatability of the measurements. All the data was collected by using a PC-based data acquisition system and analyzed by commercial software. The picture frame test device that is made for this study is shown in Fig. 2.

Fig. 1 a Frontal and side airbags. b Oblique view of facet occupant model in sitting posture following airbag deployment (Lim et al. 2014)

0.150

Bendjaballah et al. International Journal of Mechanical and Materials Engineering (2017) 12:12

Page 2 Of 9

Figure 3 shows the stress-strain relationship of the airbag sample under axial tensile loads. The results are showing a linear increase in extension with the increas- ing stresses. This is an expected output and it confirms with the theoretical behavior of a sample subjected to tensile stress. The rupture strain values for different airbags (R/P/VW) were 0.322, 0.441, and 0.472, respect- ively. The measured elastic parameters (i.e., Young’s modulus E and initial yield strength) and Poisson’s ratio are summarized in Table 2. The tensile tests of the woven fabrics can show differences on mechanical prop- erties because woven fabrics can resist in-plane shear loads once the yarn lock-up angle has been reached. The differences of material property on material direction can affect the shape of fully deployed bag (see Fig. 3b).

Theoretical Background

Numerical simulations of airbags use very complex and techniques such as an orthotropic model to identify the mechanical behaviors during the airbag inflation and the fluid mechanics (gas flow) to describe the inflator gas flow (pressure gradient) and improve the representation of the pressures within the airbag. To model the airbag as an orthotropic model, three material constants have to be provided. Assuming a plane stress condition, the

Ð1Þ

where σ is the normal stress and τ is the shear stress, the subscript refers to the principal material directions, i.e., the fill and warp directions. Also, ε and γ are the strain components. The material elastic constants Qij are

Ð2Þ

where E1 and E2 are the Young’s modulus in the fill and wrap directions and G12 is the shear modulus of the fabric material. νij is the Poisson ratio of the material.

The gas exerts a pressure load on the airbag causing it to expand. This expansion puts the airbag under tensile stress lowering the expansion rate. In this study, heat conduction and heat transfer is not taken into account.

Fig. 2 A photograph of Lloyd EZ20 universal testing Fig. 3 Stress versus strain using Lloyd EZ20 machine for a three different airbags at 0° and 90° and b VW airbag test specimens at

Different Angles

Table 2 Physical and mechanical properties of the airbag

Page 3 Of 9

In the deployment of an airbag, an inflator supplies high velocity gas into an airbag causing it to expand rapidly. The gas inside the airbag is assumed to be ideal, to be of constant entropy, and to satisfy the equation of state:

Ð3Þ

Here p, ρ, and e are respectively the pressure, density, and specific internal energy, and γ is the ratio of the heat capacities of the gas. The gas flow is described by the conservation laws for mass, momentum, and energy that

Ð4Þ

here, V is a volume, A is the boundary of this volume,

N Is The Normal Vector Along The Surface A, And U

denotes the velocity vector in the volume. Applying Bernoulli’s equation in the case of an ideal gas with

Ð5Þ

Here, the subscript ex denotes quantities at the throat of the tube. Furthermore u, p, and ρ denote the quan- tities inside that part of the tube that is supplying mass.

Materials And Boundary Conditions

The airbag system mainly consists of three parts: the airbag itself, the inflator unit, and the crash sensor or diagnostic unit. Thus, to study the behavior of the airbag using FE simulations, we need to have an FE model of the airbag in the folded position. A FE model of the airbag was used to simulate the test condition as shown in Fig. 5. LS-DYNA® material model FABRIC (MAT_34) is used to simulate the airbag material. It is a variation of the layered orthotropic material model. Additionally, in the LS-DYNA® material model, fabric leakage can be accounted for. However, for this CAB material, the leak- age is almost negligible and therefore no leakage is specified. The mechanical properties can be determined from the physical test. Typical material properties for airbag fabrics are taken as given in Chawla et al. (2004a) (Table 3). These properties are used to simulate inflation process of airbag (see Table 1). The car dashboard is modeled as the rectangular thin plate using a MAT_RI-

Gid Material, And The Degrees Of Freedom Are Con-

strained in all the directions. The similar properties of thermoplastic polymer are assigned for contact purposes. The porosity of the fabric is assumed zero. The nitro- gen gas is taken for inflating the airbag. Properties of nitrogen gas and initial bag conditions are shown in Table 4. The example on which we perform the study is a typical passenger side airbag. The geometric de- tails have been measured from a commercially avail- able airbag. The initial state of the airbag is a closed rectangular whose sides are to be finished to 482 × 635 mm2 and is shown in Fig. 4.

Table 3 Material properties of airbag and rigid plate used in FE

–

Table 4 Initial values used for FE simulation of the swelling of

3.33 × 10−4

Fig. 4 The initial airbag geometry in the form of a rectangular Bendjaballah et al. International Journal of Mechanical and Materials Engineering (2017) 12:12

Related Journal Articles & DOI Links

Selected peer-reviewed publications relevant to 12 Lead ECG Acquisition. Click the DOI to access the full paper (may require institutional access).

Why Choose Us?

Bangalore guidance for robotics, Spectre and autonomous systems projects.