Forecast Method for Natural Language Constructions Based on a Modified Gated Recursive Block

Abstract

The paper proposes a method for predicting natural language constructions based on a modified gated recursive block. For this, an artificial neural network model was created, a criteria for evaluating the efficiency of the proposed model was selected, two methods for parametric identification of the artificial neural network model were developed is based on the backpropagation through time algorithm and based on simulated annealing particle swarm optimization algorithms. The proposed model and methods for its parametric identification make it possible to more accurately control the share of information coming from the input layer and the hidden layer of the model, increase the parametric identification speed and the prediction probability. The proposed method for predicting natural language constructions can be used in various intelligent natural language processing systems.

Keywords

• modified gated recursive block
• prediction of natural language constructions
• particle swarm optimization
• simulated annealing
• parametric identification

-

Currently, one of the most important problems in the field of natural language processing is the insufficiently high accuracy of the analysis of alphabetic and/or phoneme sequences [ 1, 2 ]. This leads to the fact that natural language processing may be ineffective. Therefore, the development of methods for predicting natural language constructions is an important task.

As a prediction method, a neural network forecast [ 3 ] was chosen, which, when forecasting natural language constructions, has the following advantages: ─ correlations between factors are studied on existing models; ─ no assumptions regarding the distribution of factors are required ; ─ prior information about factors may be absent; ─ source data can be highly correlated, incomplete or noisy; ─ analysis of systems with a high degree of nonlinearity is possible; ─ fast model development; ─ high adaptability; ─ analysis of systems with a large number of factors is possible; ─ full enumeration of all possible models is not required; ─ analysis of systems with heterogeneous factors is possible.

The following recurrent networks are networks [ 4-6 ]: most often used as forecast neural ─ Jordon neural network (JNN) [ 7, 8 ]; ─ Elman neural network (ENN) or simple recurrent network (SRN) [ 9, 10 ]; ─ bidirectional recurrent neural network (BRNN) [ 11, 12 ]; ─ long short-term memory(LSTM) [ 13, 14 ]; ─ gated recurrent block (GRU) [ 15, 16 ]; ─ echo state network (ESN) [ 17, 18 ]; ─ liquid state machine (LSM) [ 19, 20 ].

Criterion

aLolowcaplreoxbtarbeimliutymof getting into - - - - - + + High learning speed + + + - + + + Possibility of batch training - - - - - - + Dynamic control of the share of information from the input and - - - + + - hidden layers

According to table 1, none of the networks meets all the criteria. In this regard, the creation of training methods that will eliminate these drawbacks is relevant.

To increase the probability of falling into a global extremum and replacing batch training with multi-agent training, metaheuristic search is often used instead of local search [ 21-25 ]. Metaheuristics expands the capabilities of heuristics by combining heuristic methods based on a high-level strategy [26-30].

Modern metaheuristics may have one or more of the following disadvantages: ─ there is only a generalized method structure or the method structure is focused on solving only a specific problem [ 21 ]; ─ iteration numbers are not present when searching for a solution [ 22 ]; ─ the method may not converge [31]; ─ material potential solutions are unacceptable [32]; ─ there is no formalized parameter values search strategy [33]; ─ the method is not intended for conditional optimization [34]; ─ the method does not possess high accuracy [35].

Thereby, arises the problem of constructing an effective metaheuristic optimization method.

Thus, the task to create an effective forecast model for alphabetic and/or phoneme sequences, which is trained based on effective metaheuristics, is relevant today.

The purpose of the work is to develop a forecast method for natural language constructions based on a modified gated recurrent block. To achieve the goal, the following tasks were set and solved: 1. Create a model of a modified gated recursive block. 2. Select a criteria for evaluating the efficiency of the proposed model. 3. Develop a method for the parametric identification of a model based on local search. 4. Develop a method for parametric identification of a model based on a multi-agent metaheuristic search. 5. Conduct a numerical study. 2

Creating a model of a modified gated recursive block

The paper proposes a modification of GRU by introducing 1 rj n factor for the weighted sum of the neurons outputs in the input layer, which allows to more accurately control the share of information coming from the input layer and the hidden layer.

The proposed modified gated recurrent unit (MGRU) is a recurrent two-layered artificial neural network (ANN) with an input layer in , a hidden layer h , an output layer out . Just as for a regular GRU, each neuron in hidden layer is associated with reset and update gates is (FIR filters). The structural representation of the MGRU model is shown in Fig. 1.

in … out … h r … … … z

Fig. 1. Structural representation of a modified gated recurrent block (MGRU) Gates determine how much information to pass. Thereby, the following special cases are possible. If the share of information passed by the reset gate is close to 0.5, and the share of information passed by the update gate is close to 0, then we get SRN. If the share of information passed by the reset gate is close to 0 and the share of information passed by the update gate is close to 0, then the ANN information is updated only due to the input (short-term) information. If the share of information passed by the update gate is close to 1, then the ANN information is not updated. If the share of information passed by the reset gate is close to 0 and the share of information passed by the update gate is close to 1, then the ANN information is updated only due to internal (long-term) information.

The modified gated recurrent block (MGRU) model is presented in the following form: ─ calculating the share of information passed by the reset gate

 N0 N1  rj n  f  i1 iijnr yiin n  i1 ihj r yih n 1  , j 1, N 1 , ─ calculating the share of information passed by the update gate

 N0 N1  z j n  f   uinz yiin n   uhz yih n 1  , j 1, N 1 ,

 i1 ij i1 ij  ─ calculating the output signal of the candidate layer

 N(0) N(1)  y hj (n)  g  (1 rj (n)) i1 wiijnh yin (n  i)  rj (n) i1 wihjh yih (n 1)  , j 1, N 1 , ─ calculating the output signal of the hidden layer ─ calculating the output signal of the output layer y hj (n)  z j (n) y hj (n 1)  (1 z j (n)) y hj (n), j 1, N 1 ,

 N1  y ojut n  f   whout yih n  , j 1, N 2 ,

ij  i1  f  s 

1 1 es , g s  tanh s , where N 0 is the number of neurons in the input layer; time n , rj n  0, 1 ; at a time n , z j n  0, 1 ;

N 2 is the number of neurons in the output layer; N 1 is the number of neurons in the hidden layer;  inr , uiijnz are connection weight from the i th input neuron to the reset gates and ij update of the j th hidden neuron;  hr , uihjz are connection weight from the i th hidden neuron to the reset gates and ij update of the j th hidden neuron; winh is connection weight from the i th input neuron to the j th hidden neuron; ij whh is connection weight from the i th hidden neuron to the j th hidden neuron; ij whout is connection weight from the i th hidden neuron to the output neuron; ij rj n is share of information passed by the reset gate of the j th hidden neuron at a z j n is share of information passed by the update gate j th of the hidden neuron yiin n is output of the i th input neuron at time n ; yiout n is output of the i th output neuron at time n ; y hj n is output of the j th hidden neuron at time n ; f  , g  are activation function.

To evaluate the effectiveness of the proposed model, it is necessary to select criterion. 3

Selection of criterion for evaluating the effectiveness of the proposed model

In the paper, to evaluate the parametric identification of the MGRU model, a model adequacy criterion is chosen, which means the choice of such parameter values as W   iijnr n, uiijnz n, wiijnh n, ihj r n, uihjz n, wihjh n, wihjout n  , which deliver a minimum of the mean squared error (the difference between the model output and the desired output):

F  1 P N2 2

  yopuit  d pi   min .

PN 2 p1 i1 W In the paper, to evaluate the functioning of the MGRU model in test mode, a forecast probability criterion is selected, which means the choice of such parameter values as W   iijnr n, uiijnz n, wiijnh n, ihj r n, uihjz n, wihjh n, wihjout n  , which deliver the maximum probability:

F  1 P 1,

  round  yoput  , d p   min ,   a, b   P p1 W 0, a  b a  b where round  is function that rounds a number to the nearest integer.

According to the first criterion, the methods of parametric identification of the MGRU model are proposed in this paper. 4

Creation of method for parametric identification of the

MGRU model based on local search

In this paper, we first propose a method for parametric identification of the MGRU model based on the traditional for GRU backpropagation through time (BPTT).

The proposed method allows you to find a quasi-optimal vector of parameters’ values of the MGRU model and consists of the following blocks.

Block 1 – Initialization: ─ set the current iteration number n to one; ─ initialization by uniform distribution over the interval 0, 1 or 0.5, 0.5 weights  inr  n , uinz n , winh  n , i 1, N 0 , j 1, N 1 ,  hr  n , uhz  n , ij ij ij ij ij whh n , i 1, N 1 , j 1, N 1 , whout n , i 1, N 1 , i 1, N 2 , where N 0 is ij ij the number of neurons in the input layer, N 2 is the number of neurons in the output layer, N 1 is number of neurons in the hidden layer.

Block 2 – Setting the training set  x , d  x  RN0 , d  RN2  ,  1, P , where x is  th training input vector, d is  th training output vector, P is the power of the training set. Number of the current pair from the training set   1 .

Block 3 is Initial calculation of the output signal for the hidden layer hi n 1  0 , i 1, N 1 .

Block 4 is Calculation of the output signal for each layer (forward propagation) yiin n  xi , rj n  f  srj n ,

N0 N1 srj n  i1 iijnr n yiin n  i1 ihjr n yih n 1 , j 1, N 1 ,

z j n  f  s zj n ,  szj n  uinz n yiin n uhz n yih n1, j1, N1 ,

ij ij  N(0) N(1)  shj(n)  (1rj(n)) winh(n)yiin(n)rj(n) wihjh(n)yih(n1) ,

ij i1 i1



Block 5 – Calculation of ANN error energy 1 N2 2 j1

En   e2j n, ej n  yjL nd j .

Block 6 – Setting up synaptic weights based on a generalized delta rule (back propagation) whout n1  wihjout n wihjout n , i1, N1 , j1, N2 , ij winh n1  wiijnh n wiijnh n, i1, N0 , j1, N1 , ij whh n1  wihjh n wihjh n , i1, N1 , j1, N1 ,

ij uinz n1  uiijnz n uiijnz n , i1, N0 , j1, N1 , ij uhz n1  uihjz n uihjz n, i1, N1 , j1, N1 , ij  inr n1 iijnr n iijnr n , i1, N0 , j1, N1 , ij  hh n1 ihjh n ihjh n, i1, N1 , j1, N1 ,

ij where  is a parameter that determines the learning speed (for large  , learning is faster, but the risk of getting the wrong decision increases), 0  1.

wihjout n  yih n ojut n , wiijnh n  1 rj n yiin n jh n , wihjh n  rj n yih n 1 jh n , uiijnz n  yiin n jz n , uihjz n  yih n 1 jz n ,  iijnr n  yiin n rj n ,  ihj r n  yih n 1 rj n ,  ojut n  f s ojut n y ojut n  d j  ,

 N2   jh n  g s hj n 1 z j n   whout n lout n  ,

jl  l1 

 N2   jz n  f  s zj n y hj n 1  g  s hj n  whout n lout n  , jl  l1   N(1) M  jr (n)  f (srj (n))   wihjh (n) yih (n 1)   winh (n) yiin (n)  hj (n) .

 i1 i1 ij 

Creation of a method for parametric identification of the

MGRU model based on multi-agent metaheuristic search

In this paper, we propose a method for parametric identification of the MGRU model based on simulated annealing particle swarm optimization (SAPSO).

The SAPSO method allows you to find a quasi-optimal vector of parameter values for the MGRU model and consists of the following blocks.

Block 1 – Initialization: ─ set the current iteration number n to one; ─ set the maximum number of iterations N ; ─ set swarm size K ; ─ set the dimension of the particle position M (corresponds to the number of the

MGRU model parameters); ─ position initialization xk (corresponds to the parameters vector of the MGRU model) xk   xk1,

, xkM  , xij   x mjax  x mjin U 0, 1  x mjin , k 1, K , where x mjin , x mjax are minimum and maximum values, U 0, 1 is function that provides the calculation of a uniformly distributed random variable on a segment 0, 1 ; ─ initialization of a personal (local) best position xbest k xbest  xk , k 1, K ; k ─ speed initialization  k ─ create an initial swarm of particles  k   k1,

, kM  ,  ij  0 , k 1, K ;

Q   xk , xkbest , k  ; ─ determine the particle from the current population with the best position (corresponds to the best parameters vector of the MGRU model in target function) k*  arg km1i,nK F  xk  , x*  xk* .

Block 2 – Modification of the velocity of each particle using simulated annealing r1k  r1k1,

, r1kM  , r1kj U 0, 1 , C 0, 1 , N 0, 1 , k 1, K , j 1, M ,

, r2kM  , r2kj U 0, 1 , C 0, 1 , N 0, 1 , k 1, K , j 1, M ,  k  wn k 1 n  xkbest  xk  r1 T  2 n  x*  xk  r2 T , k 1, K , 1 n   2 n   0 exp 1 T n ,  0   0  0.5  ln 2 , wn  w0 exp 1 T n , w0  w0  , T n   T n 1 , T 0  T0 ,   N  N11 , T0  N N 1 , N where N 0, 1 is function that provides the calculation of a random variable from standard normal distribution,

C 0, 1 is function that provides the calculation of a random variable from standard Cauchy distribution,

1  n is parameter controlling the contribution of the component  xkbest  xk  r1 T to the particle’s velocity at the iteration n ,

 2  n is parameter controlling the contribution of the component  x*  xk  r2 T to the particle’s velocity at the iteration n ,

w n is parameter controlling the contribution of the particle’s velocity at the iteration n 1 to the particle’s velocity at the iteration n ,  0 is initial value of 1  n and  2  n parameters, w0 is initial value of w n parameter, T  n is annealing temperature at the iteration n , T0 is initial annealing temperature,  is parameter that controls the annealing temperature.

The simulated annealing introduced in this work allow us to establish the inverse correlation between the parameters 1  n ,  2  n , w n and the iteration number, i.e. in the first iterations, the search is global, and in the last iterations, the search becomes local. In addition, in this work, a direct correlation between the parameters T0 ,  and the iteration number is established, which allows for automated selection of these parameters.

The choice of initial values of  0  0.5  ln 2 and w0  1 2 ln 2 isfies the conditions of a swarm convergence w  1 and w0  1 1  2  1 . 2 Block 3 – Modification of each particle’s position, considering the limitations is standard and satxk  xk  k , k 1, K , x mjin , xkj  x mjin  xkj  xkj , xkj   x mjin , x mjax  , k 1, K , j 1, M , x mjax , xkj  x mjax  kj ,  kj   x mjin , x mjax   kj   0,  kj x mjin , x mjax  , k 1, K , j 1, M .

Block 4 – Determining the personal (local) best position of each particle If F  xk   F  xkbest  , then xkbest  xk , k 1, K .

Block 5 – Determining the particle from the current population with the best position k*  arg min F  xk  .

k1, K Block 6 – Determining the global best position

If F  xk*   F  x*  , then x*  xk* .

Block 7 – Stop Condition If n  N , then increase the iteration number n by 1 and go to block 2.

The proposed method is intended for implementation through a multi-agent system. 6

Numerical study

N0  2 MaxLenLexem  LenCode ,

The parametric identification of the MGRU model was carried out for 10,000 training implementations based on the proposed multi-agent metaheuristic search.

Table 5 presents the forecast probabilities obtained for 1000 test implementations based on the proposed MGRU model and artificial neural networks’ traditional models.

Table 6 presents the number of parameters (link weights) for the proposed MGRU model and artificial neural networks’ traditional models, which is directly proportional to the computational complexity of parametric identification.

Criterion

Forecast probability

For a complete LSTM, GRU, MGRU, the number of neurons in the hidden layer is For JNN, ENN (SRN), BRNN, the number of neurons in the hidden layer is calcuFor LSTM, the number of memory cells is set as M  1 .

According to tables 5-6, MGRU and complete LSTM give the best forecast probability results, but MGRU, unlike LSTM, has fewer parameters, i.e. less computational complexity.

The increase in accuracy of MGRU prediction was made possible by introducing a multiplier (1 rj (n)) for the weighted sum of the neurons outputs in the input layer. This allows to more accurately control the share of information coming from the input layer and the hidden layer, as well as by using the metaheuristic determination of the MGRU models parameters.

The limitations of this work include the MGRUs full connectivity, the requirement for more parameters than in ENN (SRN), MGRU testing only on trigrams.

Like the BERT system, the proposed MGRU can work with context-free and context-sensitive grammars, but unlike BERT, it can be used not only for English.

The practical contribution of this work consists in the fact that it allows to predict alphabetic and / or phoneme sequences through an artificial neural network, the training of which is based on the proposed metaheuristics, which allows to increase the accuracy of the forecast and can be used as an intermediate stage in the speech understanding system. 7

Conclusions 1. To solve the problem of insufficient quality of the natural language sequences analysis, the corresponding neural network forecast methods were studied. To increase the efficiency of training neural networks, metaheuristic methods were studied. 2. The created model of the modified gated recurrent block allows for more precise control of the share of information coming from the input layer and the hidden layer, which increases the forecast accuracy. 3. The created method of parametric identification of the MGRU model based on simulated annealing particle swarm optimization reduces the probability of getting into local extremum and replaces batch training with multi-agent training, which increases the forecast probability and the training speed. 4. The proposed method for predicting natural language constructions based on a modified gated recurrent block can be used in various intelligent natural language processing systems.

References

1. Dominey , P.F. , Hoen , M. , Inui , T. : A Neurolinguistic Model of Grammatical Construction Processing . Journal of Cognitive Neuroscience . 18 ( 12 ), 2088 - 2107 ( 2006 ). doi: 10 .1162/jocn. 2006 . 18 .12.2088

2. Khairova , N. , Sharonova , N.: Modeling a Logical Network of Relations of Semantic Items in Superphrasal Unities . In: Proc. of the EWDTS . pp. 360 - 365 . Sevastopol ( 2011 ). doi: 10 .1109/EWDTS. 2011 .6116585

3. Lyubchyk , L. , Bodyansky , E. , Rivtis , A. : Adaptive Harmonic Components Detection and Forecasting in Wave Non-Periodic Time Series using Neural Networks . In: Proc. of the ISCDMCI'2002 . pp. 433 - 435 . Evpatoria ( 2002 ).

4. Du , K.-L., Swamy , K.M.S. : Neural Networks and Statistical Learning . Springer-Verlag, London ( 2014 ). doi: 10 .1007/978-1- 4471 -5571-3

5. Haykin , S.: Neural Networks. Pearson Education , NY ( 1999 ).

6. Sivanandam , S.N. , Sumathi , S. , Deepa , S.N. : Introduction to Neural Networks using Matlab 6.0 . The McGraw-Hill Comp ., Inc., New Delhi ( 2006 ).

7. Jordan , M.I. : Attractor Dynamics and Parallelism in a Connectionist Sequential Machine . In: Proc. of the Ninth Annual Conference of the Cognitive Science Society . pp. 531 - 546 . Hillsdale, NJ ( 1986 ).

8. Jordan , M. , Rumelhart , D. : Forward Models: Supervised Learning with a Distal . Cognitive Science . 16 , 307 - 354 ( 1992 ). doi: 10 .1016/ 0364 - 0213 ( 92 ) 90036 -T

9. Zhang , Z. , Tang , Z. , Vairappan , C. : A Novel Learning Method for Elman Neural Network using Local Search . Neural Information Processing - Letters and Reviews . 11 ( 8 ), 181 - 188 ( 2007 ).

10. Wiles , J. , Elman , J.: Learning to Count without a Counter: a Case Study of Dynamics and Activation Landscapes in Recurrent Networks . In: Proc. of the Seventeenth Annual Conference of the Cognitive Science Society . pp. 1200 - 1205 . Cambridge, MA ( 1995 ).

11. Schuster , M. , Paliwal , K.K. : Bidirectional Recurrent Neural Networks. IEEE Transactions on Signal Processing . 45 ( 11 ), 2673 - 2681 ( 1997 ). doi: 10 .1109/78.650093

12. Baldi , P. , Brunak , S. , Frasconi , P. Soda , G. , Pollastri , G.: Exploiting the Past and the Future in Protein Secondary Structure Prediction . Bioinformatics . 15 ( 11 ), 937 - 946 ( 1999 ). doi: 10 .1093/bioinformatics/15.11.937

13. Hochreiter , S. , Schmidhuber , J.: Long Short-Term Memory . Technical Report FKI-207-95 , Fakultat fur Informatik, Technische Universitat Munchen. doi: 10 .1162/neco. 1997 . 9 .8. 1735

14. Gers , F. : Long Short-Term Memory in Recurrent Neural Networks . PhD thesis , Ecole Polytechnique Federale de Lausanne.

15. Cho , K. , Merrienboer , van B. , Gulcehre , C. , Bougares , F. , Schwenk , H. , Bengio , Y. : Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation . In: Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) . pp. 1724 - 1734 . Qatar, Doha ( 2014 ). doi: 10 .3115/v1/ D14 -1179

16. Dey , R. , Salem , F.M. : Gate-Variants of Gated Recurrent Unit (GRU) Neural Networks . ( 2017 ). arXiv: 1701 . 05923

17. Jaeger , H.: A Tutorial on Training Recurrent Neural Networks , Covering BPPT , RTRL, EKF and the “Echo State Network” Approach . GMD Report 169 , Fraunhofer Institute AIS ( 2002 ).

18. Jaeger , H. , Lukosevicius , M. , Popovici , D. , Siewert , U. : Optimization and Applications of Echo State Networks with Leakyintegrator Neurons . Neural Networks . 20 ( 3 ), 335 - 352 ( 2007 ). doi: 10 .1016/j.neunet. 2007 . 04 .016

19. Maass , W. , Natschläger , T. , Markram , H.: Real-Time Computing without Stable States: a New Framework for Neural Computation Based on Perturbations . Neural Computation . 14 ( 11 ), 2531 - 2560 ( 2002 ). doi: 10.1162/089976602760407955

20. Jaeger , H. , Maass , W. , Prıncipe , J.C. : Special Issue on Echo State Networks and Liquid State Machines . Editorial. Neural Networks . 20 ( 3 ), 287 - 289 ( 2007 ). doi: 10 .4249/scholarpedia.2330

21. Talbi , El-G.: Metaheuristics: from Design to Implementation . Wiley & Sons, Hoboken, New Jersey ( 2009 ).

22. Engelbrecht , A.P. : Computational Intelligence: an Introduction . Wiley & Sons, Chichester, West Sussex ( 2007 ).

23. Zbigniew , J.C. : Three Parallel Algorithms for Simulated Annealing . In: Proceedings of the 4th International Conference on Parallel Processing and Applied Mathematics-Revised Papers (PPAM'01) . pp. 210 - 217 . Springer-Verlag, Berlin, Heidelberg ( 2001 ).

24. Loshchilov , I. : CMA-ES with Restarts for Solving CEC 2013 Benchmark Problems . In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC ' 2013 ). pp. 369 - 376 . Cancun, Mexico ( 2013 ).

25. Byrne , J. , Hemberg , E. , Brabazon , A. , O'Neill , M.: A Local Search Interface for Interactive Evolutionary Architectural Design . In: Proceedings of the International Conference on Evolutionary and Biologically Inspired Music and Art (Evo-MUSART ' 2012 ). pp. 23 - 34 . Springer, Berlin, Heidelberg ( 2012 ).