Keywords

1 Introduction

Artificial feedforward neural networks have been studied by many scientists e.g. [2, 12, 14, 27, 28, 31, 43, 45]. One of the most frequently used methods for training feedforward neural networks are gradient methods, see e.g. [18, 29, 44]. Most of the simulations of neural networks learning algorithms, like other learning algorithms [19, 20, 30, 33, 34, 36, 40, 41], work on a serial computer. The computational complexity of many learning algorithms is very high. This makes serial implementation very time consuming and slow. The Levenberg Marquart (LM) algorithm [21, 26] is one of the most effective learning algorithms, unfortunately, it requires a lot of calculations. But, for very large networks the computational load of the LM algorithm makes it impractical. A suitable solution to this problem is the use of high performance dedicated parallel structures, see eg. [3, 5,6,7,8,9,10,11,12,13, 38, 39, 48]. This paper shows a new parallel computational approach to the LM algorithm based on vector instruction. The results of the study of a new parallel approach to the LM algorithm is shown in the last part of the paper.

A sample structure of the feedforward neural network is shown in Fig. 1. This sample network has L layers, \(N_l\) neurons in each \(l-th\) layer, and \(N_L\) outputs. The input vector contains \(N_0\) input values.

The Eq. (1) describes the recall phase of the network

$$\begin{aligned} \begin{array}{l} s_i^{\left( l \right) }\left( t \right) = \sum \limits _{j = 0}^{{N_{l - 1}}} {w_{ij}^{\left( l \right) }\left( t \right) x_i^{\left( l \right) }\left( t \right) }, y_i^{\left( l \right) } (t) = f(s_i^{\left( l \right) } (t)). \\ \end{array} \end{aligned}$$
(1)
Fig. 1.
figure 1

Sample feedforward neural network.

Full size image

The Levenberg-Marquard method [21, 26] is used to train the feedforward neural network. The following loss function is minimized

$$\begin{aligned} E\left( {\mathbf{{w}}\left( n \right) } \right) = \frac{1}{2}\sum \nolimits _{t = 1}^Q {\sum \nolimits _{r = 1}^{{N_L}} {\varepsilon _r^{{{\left( L \right) }^2}}} \left( t \right) } = \frac{1}{2}\sum \nolimits _{t = 1}^Q {\sum \nolimits _{r = 1}^{{N_L}} {{{\left( {y_r^{\left( L \right) }\left( t \right) - d_r^{\left( L \right) }\left( t \right) } \right) }^2}} } \end{aligned}$$
(2)

where \(\varepsilon _i^{\left( L \right) } \) is defined as

$$\begin{aligned} \varepsilon _r^{\left( L \right) }(t) = \varepsilon _r^{\left( {Lr} \right) }(t) = y_r^{\left( L \right) }(t) - d_r^{\left( L \right) }(t) \end{aligned}$$
(3)

and \(d_r^{\left( L \right) }(t)\) is the \(r-th\) desired output in the \(t-th\) probe.

The LM algorithm is a modification of the Newton method and is based on the first three elements of the Taylor series expansion of the loss function. A change of weights is given by

$$\begin{aligned} \Delta \left( {\mathbf{{w}}(n)} \right) = - {\left[ {{\nabla ^\mathbf{{2}}}{} \mathbf{{E}}\left( {\mathbf{{w}}(n)} \right) } \right] ^{ - 1}}\nabla \mathbf{{E}}\left( {\mathbf{{w}}(n)} \right) \end{aligned}$$
(4)

this requires knowledge of the gradient vector

$$\begin{aligned} \nabla \mathbf{{E}}\left( {\mathbf{{w}}(n)} \right) = {\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{\varepsilon }}\left( {\mathbf{{w}}(n)} \right) \end{aligned}$$
(5)

and the Hessian matrix

$$\begin{aligned} {\nabla ^\mathbf{{2}}}{} \mathbf{{E}}\left( {\mathbf{{w}}(n)} \right) = {\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{J}}\left( {\mathbf{{w}}(n)} \right) + \mathbf{{S}}\left( {\mathbf{{w}}(n)} \right) \end{aligned}$$
(6)

where \(\textbf{J}\left( {\mathbf{{w}}(n)}\right) \) in (5) and (6) is the Jacobian matrix

$$\begin{aligned} \mathbf{{J}}(\mathbf{{w}}\left( n \right) ) = \left[ {\begin{array}{*{20}{c}} {\frac{{\partial \varepsilon _1^{\left( L \right) }(1)}}{{\partial w_{10}^{(1)}}}}&{} \cdots &{}{\frac{{\partial \varepsilon _1^{\left( L \right) }(1)}}{{\partial w_{ij}^{(k)}}}}&{} \cdots &{}{\frac{{\partial \varepsilon _1^{\left( L \right) }(1)}}{{\partial w_{{N^L}{N^{L - 1}}}^{(L)}}}}\\ \vdots &{} \cdots &{} \vdots &{} \cdots &{} \vdots \\ {\frac{{\partial \varepsilon _{{N_L}}^{\left( L \right) }(1)}}{{\partial w_{10}^{(1)}}}}&{} \cdots &{}{\frac{{\partial \varepsilon _{{N_L}}^{\left( L \right) }(1)}}{{\partial w_{ij}^{(k)}}}}&{} \cdots &{}{\frac{{\partial \varepsilon _{{N_L}}^{\left( L \right) }(1)}}{{\partial w_{{N_L}{N_{L - 1}}}^{(L)}}}}\\ \vdots &{} \cdots &{} \vdots &{} \cdots &{} \vdots \\ {\frac{{\partial \varepsilon _{{N_L}}^{\left( L \right) }(Q)}}{{\partial w_{10}^{(1)}}}}&{} \cdots &{}{\frac{{\partial \varepsilon _{{N_L}}^{\left( L \right) }(Q)}}{{\partial w_{ij}^{(k)}}}}&{} \cdots &{}{\frac{{\partial \varepsilon _{{N_L}}^{\left( L \right) }(Q)}}{{\partial w_{{N_L}{N_{L - 1}}}^{(L)}}}} \end{array}} \right] . \end{aligned}$$
(7)

In the hidden layers the errors \(\varepsilon _i^{\left( lr \right) } \) are calculated as follows

$$\begin{aligned} \varepsilon _i^{\left( {lr} \right) }\left( t \right) \buildrel \wedge \over = \sum \limits _{m = 1}^{{N_{l + 1}}} {\delta _i^{\left( {l\mathrm{{ + }}1,r} \right) }\left( t \right) w_{mi}^{\left( {l + 1} \right) }}, \end{aligned}$$
(8)
$$\begin{aligned} \delta _i^{\left( {lr} \right) }\left( t \right) = \varepsilon _i^{\left( {lr} \right) }\left( t \right) f'\left( {s_i^{\left( {lr} \right) }\left( t \right) } \right) . \end{aligned}$$
(9)

Based on this, the elements of the Jacobian matrix for each weight can be computed

$$\begin{aligned} \frac{{\partial \varepsilon _r^{\left( L \right) }\left( t \right) }}{{w_{ij}^{\left( l \right) }}} = \delta _i^{\left( {lr} \right) }\left( t \right) x_j^{\left( l \right) }\left( t \right) . \end{aligned}$$
(10)

It should be noted that derivatives (10) are computed in a similar way it is done in the classical backpropagation method, except that each time there is only one error given to the output. In this algorithm, the weights of the entire network are treated as a single vector and their derivatives form the Jacobian matrix \(\textbf{J}\).

The \(\mathbf{{S}}\left( {\mathbf{{w}}(n)} \right) \) component (6) is given by the formula

$$\begin{aligned} \mathbf{{S}}\left( {\mathbf{{w}}(n)} \right) = {\sum \nolimits _{t = 1}^Q {\sum \nolimits _{r = 1}^{{N_L}} {\varepsilon _r^{\left( L \right) }\left( t \right) } \nabla } ^2}\varepsilon _r^{\left( L \right) }\left( t \right) . \end{aligned}$$
(11)

In the Gauss-Newton method it is assumed that \(\mathbf{{S}}\left( {\mathbf{{w}}(n)} \right) \approx 0\) and that equation (4) takes the form

$$\begin{aligned} \Delta \left( {\mathbf{{w}}(n)} \right) = - {\left[ {{\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{J}}\left( {\mathbf{{w}}(n)} \right) } \right] ^{ - 1}}{\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{\varepsilon }}\left( {\mathbf{{w}}(n)} \right) . \end{aligned}$$
(12)

In the Levenberg-Marquardt method is is assumed that \(\mathbf{{S}}\left( {\mathbf{{w}}(n)} \right) = \mu \textbf{I}\) and that equation (4) takes the form

$$\begin{aligned} \Delta \left( {\mathbf{{w}}(n)} \right) = - {\left[ {{\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{J}}\left( {\mathbf{{w}}(n)} \right) + \mu \mathbf{{I}}} \right] ^{ - 1}}{\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{\varepsilon }}\left( {\mathbf{{w}}(n)} \right) . \end{aligned}$$
(13)

By defining

$$\begin{aligned} \begin{array}{c} \mathbf{{A}}\left( n \right) = - \left[ {{\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{J}}\left( {\mathbf{{w}}(n)} \right) + \mu \mathbf{{I}}} \right] \\ \mathbf{{h}}\left( n \right) = {\mathbf{{J}}^T}\left( {\mathbf{{w}}(n)} \right) \mathbf{{\varepsilon }}\left( {\mathbf{{w}}(n)} \right) \end{array} \end{aligned}$$
(14)

the Eq. (13) is as follows

$$\begin{aligned} \Delta \left( {\mathbf{{w}}(n)} \right) = \mathbf{{A}}{\left( n \right) ^{ - 1}}{} \mathbf{{h}}\left( n \right) . \end{aligned}$$
(15)

The Eq. (15) can be solved using the QR factorization

$$\begin{aligned} {\mathbf{{Q}}^T}\left( n \right) \mathbf{{A}}\left( n \right) \Delta \left( {\mathbf{{w}}(n)} \right) = {\mathbf{{Q}}^T}\left( n \right) \mathbf{{h}}\left( n \right) , \end{aligned}$$
(16)
$$\begin{aligned} \mathbf{{R}}\left( n \right) \Delta \left( {\mathbf{{w}}(n)} \right) = {\mathbf{{Q}}^T}\left( n \right) \mathbf{{h}}\left( n \right) . \end{aligned}$$
(17)

This paper used the Givens rotations for the QR factorization. The operation, in 5 steps, of the LM algorithm is described below:

  1. 1.

    The calculation of the network outputs for all input data, errors, and the loss function.

  2. 2.

    The calculation of the Jacobian matrix, using the backpropagation method for each error individually.

  3. 3.

    The calculation of weight changes \(\Delta \left( {\mathbf{{w}}(n)} \right) \) using the QR factorization.

  4. 4.

    The recalculation of the loss function (2) for new weights \({\mathbf{{w}}(n)} +\Delta \left( {\mathbf{{w}}(n)} \right) \). If the loss function is less than the one calculated earlier in step 1, then \(\mu \) should be reduced \(\beta \) times, the new weight vector is saved and the algorithm returns to Step 1. Otherwise, the \(\mu \) value is increased \(\beta \) times and the algorithm repeats step 3.

  5. 5.

    The algorithm stops running when the loss function falls below a preset value or the gradient falls below a preset value.

Fig. 2.
figure 2

Sample illustration for computational steps in LM algorithm.

Full size image

2 Vector Solution for Levenberg-Marquardt Algorithm

The Levenberg-Marquardt algorithm needs high computing power. Each epoch starts with steps 1 and 2, and next steps 3 and 4 can be repeated a few times. Figure 2 shows a single epoch of the LM algorithm, showing the first two steps and repeating steps 3 and 4. It is worth noting that the next pairs of steps 3 and 4 are independent of each other and can be performed at the same time. They only differ in the \(\mu \) parameter value and have the same starting point. Thus, they can be run parallel on separate processor cores. However, the solution proposed in this article uses processor vector instructions. Vector instructions allow 4, 8, and even 16 operations to be performed in parallel. This approach enables simultaneous determination of new 4, 8, or 16 points in the weight space using only one processor core, see Fig. 3. Figure 3a shows the epoch of the LM algorithm with the use of four-element vectors. After completing the first two steps, the algorithm calculates steps 3 and 4 for the next 4 parameters \(\mu \) at one time. Thus, the three consecutive computations of steps 3 and 4 are performed earlier and therefore do not take computational time. The rectangles with the line in the middle symbolize steps 3 and 4, which are used in the standard calculation method and are omitted in calculations using vector instructions. Figure 3b shows the version with eight-element vectors.

Fig. 3.
figure 3

Sample illustration for calculating method with vector instructions. a) the 4-elements vector, b) the 8-elements vector

Full size image
Fig. 4.
figure 4

Sample illustration for training process with vector instructions.

Full size image

Figure 4 shows an example of the learning process using the LM algorithm. In the following epochs, you can see a different number of steps 3 and 4 repetitions. There are epochs where the repetition does not occur and there are those with a large number of repetitions, in this case, vector instructions can be used, which makes it possible to calculate up to four pairs of steps 3 and 4 at the same time and consequently shortening the learning time. Of course, eight- or sixteen-element vectors can be used instead of using four-element vectors. This increases the parallelism and speed of the proposed calculation method.

3 Experimental Results

The proposed solution was tested against the classical variant of the Levenberg-Marquardt learning algorithm on several test problems. Two types of forward-coupled artificial neural networks were tested in the experiment: MLP — Multilayer Perceptron, FCMLP — Fully Connected Multilayer Perceptron. The performance of the presented calculation method was measured in average training time in milliseconds. The presented results are compiled according to the best combination of training parameters. In all cases, the initial weights were randomly selected from the range [–0.5,0.5]. The number of epochs has been limited to 1,000. Each training session was repeated 100 times.

3.1 Logistic Function Approximation

The logistic function is a unary function given by the formula

$$\begin{aligned} y=f\left( x\right) =4x\left( 1-x\right) \end{aligned}$$
(18)

The teaching sequence contains 11 samples where \(x \in \left[ 0, 1\right] \). The average accepted error threshold has been set to 0.001. Table 1 shows the simulation results for two kinds of neural networks MLP and FCMLP. Both networks have five neurons in the hidden layer. The symbols LM, LMP 4, LMP 8, and LMP 16 represent the average network training time using the LM algorithm and its vector versions for 4, 8, and 16 element vectors, respectively. The speed factor means how many percent the vector version is faster then the classical one and is given by the formula

$$\begin{aligned} SF=\left( 1-{LMPx\over LM}\right) *100\% \end{aligned}$$
(19)
Table 1. Training results for the LOG function.
Full size table

3.2 Hang Function Approximation

The Hang function is a nonlinear two-argument \( x_1 \) and \( x_2 \) function with the following formula

$$\begin{aligned} y=f\left( x_1, x_2\right) = {\left( 1 + x_1^{-2} + \sqrt{x_2^{-3}} \right) }^2 \end{aligned}$$
(20)

The Hang teaching sequence contains 50 samples that cover arguments in the range of \(x_1, x_2 \in \left[ 1, 5\right] \). The target error threshold was set to 0.001 as the epoch average. The results of simulations for the Hang function are shown in Table 2. Both tested networks have 15 neurons in the hidden layer.

Table 2. Training results for the HANG function.
Full size table

3.3 IRIS Function Classification

The iris dataset contains 150 instances describing three species of iris flowers. The flowers are identified with 4 numerical attributes describing the lengths and widths of the petals of the flower. The target error has been set to 0.05. Table 3 shows the simulation results.

Table 3. Training results for the IRIS function.
Full size table

3.4 The Two Spirals Classification

Two spirals is a well-known classification problem where a neural network has to identify one of the two helices based on two-dimensional coordinates. The training set for this problem contains 96 samples. The target error has been set to 0.05. Table 4 shows the simulation results.

Table 4. Training results for the TS function.
Full size table

4 Conclusion

In this paper, the new computational approach to the Levenberg-Marquardt learning algorithm for a feedforward neural network is proposed. Two types of feedforward neural networks were used in the experiments: multilayer perceptron and fully interconnected multilayer perceptron. The networks were trained with different training sets: Logistic function, Hang, Iris, and Two Spirals. We can compare the computational performance of the proposed solution, based on vector instructions of the Levenberg-Marquardt learning algorithm, with a classical solution. The conducted experiments showed a significant reduction of the real learning time. For all training sets, calculation times have been reduced by an average of 50%. It has been observed that the performance of the proposed solution is promising.

A vector approach can be used for other advanced learning algorithms of feedforward neural networks, see eg. [2, 8]. In the future research, we plan to design parallel realization of learning of other structures including probabilistic neural networks [32] and various fuzzy [1, 15, 20, 22, 24, 37, 42, 46, 47], and neuro-fuzzy structures [16, 17, 23, 25, 35].