The problem of constructing regression models is that it is necessary to specify the structure of the model, in addition, in models of large dimensions, poor conditioning of the matrices is possible, which leads to an unstable solution. The paper considers methods of self-organization (methods of group accounting of arguments), which use an iterative procedure for the simultaneous synthesis of the structure of the model and the calculation of its coefficients. The advantages and disadvantages of the known methods of self-organization are analyzed. A self-organization method for the synthesis of a multiplicative model with linear private descriptions has been developed. The effectiveness of the method has been tested on test cases.
outputs of the object, a model of the object is constructed in the form of some analytical function Y' = f ( X ) that best approximates the output Y in the best way (in the polynomial is usually used: (1)
The concrete structure of the model (the number of factors and the maximum degree of the polynomial) is determined by the researcher, and the calculation of the model coefficients from the experimental data is carried out by the least squares method (LSM) [3].
The calculation of the coefficients of a polynomial by LSM is reduced to solving a normal system of linear algebraic equations with respect to unknown coefficients of the polynomial. With a significant number of input factors and an increase in the degree of the polynomial, the number of coefficients in (1) grows like an avalanche, which imposes increased requirements on the volume of the training sample (for the implementation of LSM, the number of experimental points should be significantly larger than the total number of coefficients).
In addition, in real data, as a rule, there are groups of strongly related features. In these conditions, the phenomenon of multicollinearity arises [2], which leads to poor conditioning and, in the extreme case, the degeneracy of the covariance matrix.
Herewith, the solution of a normal system of linear equations is not stable or a solution cannot be obtained.
Therefore, in practice, they are usually limited to linear regression models, although they are inaccurate and are used for a “rough” estimate in order to select the set of influencing factors of model X.
For the synthesis of regression models from a small number of experimental data, inductive methods of self-organization (GMDH) are effectively used [4-6], which simultaneously determine polynomials and its coefficients. 2
Self-organization methods use an iterative procedure for sequentially complicating a polynomial with choosing the best solutions at each step of the iteration.
Inductive algorithms are also known as polynomial neural networks [7-9]. GMDH
is used in such areas as data mining and knowledge discovery [10, 11], forecasting
[12, 13], modeling of complex systems [6, 14], optimization and pattern recognition
[
The methods of self-organization are based on the following principles of the
theory of heuristic self-organization: the principle of the external criterion and the
principle of non-final decision [
The principle of the external criterion is that the quality control of the predictive model (the accuracy of the experimental data approximation by the regression equation) is estimated using a criterion that is external to the criterion by which the coefficients are determined.
One of the options for the external criterion can be a breakdown of all experimental points into two parts, where the first of them, the training sample, is used to determine the coefficients using LSM, and the second part of the experimental points, the test (external) sample, is used to evaluate the accuracy of the regression equation.
The use of an external criterion makes it possible to obtain a model of optimal complexity.
The principle of inconclusiveness of the solution is borrowed from evolutionary
and genetic algorithms and lies in the fact that at each step of the iteration remains a
group of best solutions, that is, hopeless solutions are cut off, and only at the last step
the only best (optimal) solution among all equal solutions is selected [
The essence of self-organization algorithms is that a complete description of an
object of the form (1) is replaced by a set of private descriptions [
Yi ( xk , xl ) = a0i + a1i xk + a2i xl . (2) (3) (4) Private description with covariance
Yi ( xk , xl ) = a0i + a1i xk + a2i xl + a3i xk xl .
Quadratic private description
Yi ( xk , xl ) = a0i + a1i xk + a2i xl + a3i xk xl + a1i xk2 + a2i xl2 , where: xk , xl - factors that are included in the i-th model.
With the number of factors n, the number of private descriptions is equal to the number of possible combinations of factors as 2 – C 2 n
For each private description, the response values at all experimental points and the accuracy relatively to the external criterion are calculated.
The complication of the model (an increase of the number of variables and the degree of the polynomial) is performed during the transition to the next step of the iteration, and the responses of the best models of the previous step (relatively to the external criterion) are the initial factors of the next step of the iteration - a recursive substitution of the results of the i-1- th step into i- th.
Many self-organization algorithms are distinguished by the structure of private
descriptions, the external criterion (accuracy of the model in the points of the test
sequence, balance of coefficients), the method of obtaining the resulting model, etc. [
Thus, from the considered features of self-organization algorithms, we can conclude that each algorithm has its own field of application, but for all algorithms, an increase in the model dimension as a result of an iterative procedure automatically leads to a corresponding increase in the degree of the resulting polynomial. An exception is combinatorial algorithms with linear private descriptions, but they allow you to build only a linear multidimensional model.
Therefore, the use of well-known self-organization algorithms for constructing non-linear models of multidimensional objects of low dimension is not very effective. As almost all types of private descriptions are used in well-known algorithms, an approach based on changing the iterative model complication procedure is promising.
In this case, linear private descriptions of each iteration step can be obtained by a combinatorial algorithm, and the resulting model (instead of a recursive substitution) is synthesized in the form of a multiplicative model of linear partial descriptions of the previous i-1-th and current i-th iteration steps. 3
Let there be a vector of input actions X i = { x1i ,..., xni } and an output Yi of each ith instance i = 1, N of a training sample of volume N. Build a model of regression dependence of the form (1) using the basic principles of self-organization methods.
The aim of the work is to develop a method of self-organization in which the degree of the resulting regression equation increased minimally (by one) when moving to the next step of the iteration, and the number of factors can be maximum already in the first step. To achieve this aim, the following tasks are solved: ─ to develop a self-organization method for the synthesis of a multiplicative model with linear private descriptions; ─ to develop computational procedures for implementing the method; ─ to assess the effectiveness of the method on test cases. 4 • • • • •
In the developed method, all the principles of self-organization algorithms must be observed, therefore, in developing of the method, it is necessary to formalize the following stages of information conversion:
Generation of linear private description structures; Calculation of the coefficients of a private description of a given structure at the experimental points of the training sample; Calculation of responses of private descriptions at the points of the test sample and selection of the best solutions; Transition to the next step of iteration and implementation of the model complication procedure;
Formation of a stopping criterion and selection of the optimal solution. 4.1
As individual descriptions at any step of the iteration, linear polynomials from n variables (n is the dimension of the object) and the set of all possible polynomials from i variables i = 1, n − 1 with a different combination of non-repeating arguments are used. The number of possible polynomials is which is significantly more than the number of private descriptions in known algorithms.
In the software implementation of the generation of structures, an integer array of length n is used, each element of which contains 0 or 1 and is used as a mask of the structure (1-given factor is present in the description; 0-missing). For each value of i i = 1, n − 1 , i units are written to the beginning of the array, after which the last unit is shifted one position to the right, forming a new mask and so on until the end of the array. 4.2
The calculation of the coefficients of private description of given structure at the first step of the iteration does not present any problems and is performed by the least squares method at the points of the training sequence of input actions X = { x1 ,..., xn } and output Y.
The calculation of the responses of private descriptions at the points of the test sample and the selection of the best solutions are also carried out by known methods. For simplicity of the algorithmic implementation, the number of best solutions is chosen equal to the number of input factors n.
In order for the degree of the resulting regression equation to increase by one by passing to the next iteration step, the regression equation is constructed in the form of a multiplicative model of the form
k Pk ( X ) = Pi ( X ) , s
i=1 n N p = Cnj =2n −1 ,
j=1 where P i ( X ) - is the linear polynomial of the i-th step of the iteration.
It should be noted that in this method the polynomials of any iteration step use the input factor vector X as arguments. As was noted earlier, in the known methods, the vector X is used only at the first step of the iteration, at all other steps the input is the responses of the best decisions of the previous step.
Expression (6) shows that, in the process of complicating the model, Np (determined by (5)) of the polynomials of the current k-th iteration step are “built in” over each of the best solutions of the previous k – 1 th step. The decisions of the previous step are the “parents” of the decisions of the current step - the “descendants”. Thus, at each step of the iteration (except the first), the number of particular descriptions is equal to the product of n by Np. Of this set of particular descriptions, only n best ones are skipped to the next step.
The stop criterion is the “left corner” rule adopted in self-organization methods — an increase or stabilization of the error of the best private descriptions at the points of (5) (6) the verification sequence. In the last step of the iteration, the only model selected from the best is the result of the method. After opening the brackets in (6), a polynomial is obtained in the form (1).
Calculation of the coefficients of a private description of a given structure at the kth step of the iteration (k> 1). According to expression (6), the arguments of the polynomials of the k-th step is the vector of input factors. Then, in the classical application of LSM, the coefficients of these polynomials will be determined from the condition of minimizing the standard deviations between the responses of the analytic function P k ( X ) and the output value of Y. In this case, P k ( X ) approximates Y independently, without taking into account the results of the approximation of its “parent” in the previous step.
And the multiplicative convolution of the “parent” and “descendant” will give an unpredictable result.
Therefore, it is necessary to develop a system of linear algebraic equations for calculating the coefficients of polynomials by LSM taking into account the fact that in the expression (6) the coefficients of the “parents” of all the previous steps are already defined and their responses Y* are known. It is necessary to determine the coefficients of the last factor in (6).
We write the functional of the LSM
Nl F = (Yi − Psk ( X i ))2 → min ,
i=1 where Xi, Yi are the values of the input and output actions, respectively; Psk(Xi) is the response of the multiplicative model of the current iteration step, which is determined by (6): the summation is carried out over the points of the learning sequence of volume Nl.
We write linear polynomials of the current step in expanded
Taking into account (8), we replace the polynomials of the previous steps in the expression of the multiplicative model (6) with their responses Y* and substitute in (7) m Pk ( X i ) = a0 + a j x ji
j=1
Nl m F = (Yi − Yi* ( a0 + a j x ji ))2 → min , i=1 j=1 (7) (8) (9)
This functional in the space of parameters (polynomial coefficients) is a convex function and has one global minimum. To find the minimum, it is necessary to take the private derivatives with respect to each coefficient and equate them to zero. As a result, we get F a0 = 2(( Yi − Yi* ( a0 + a1x1i + ... + am xmi ))Yi* ) = 0 ;
i F a1 F am = 2(( Yi − Yi* ( a0 + a1x1i + ... + am xmi ))Yi* x1i ) = 0
i ………………………………………………………………………… = 2(( Yi − Yi* ( a0 + a1x1i + ... + am xmi ))Yi* xmi ) = 0 .
i
Having opened the brackets and performed simple arithmetic operations, we obtain a system of linear algebraic equations with respect to unknown coefficients ai i = 0,m of the form: ( Yi*2 )a0 + i ( Yi*2 x1i )a0 + i ... ( Yi*2 xmi )a0 + i ( Yi*2 x1i )a1 + i ( Yi*2 x1i x1i )a1 + i
... ( Yi*2 xmi x1i )a1 + i ... ... ... ...
( Yi*2 xmi )am = i ( Yi*2 x1i xmi )am = i
... ( Yi*2 xmi xmi )am = i ( Yi*Yi ) i ( Yi*Yi x1i ) i
... ( Yi*Yi xmi ) i (10)
Solving the system of equations (10) by any method, we obtain the coefficients of the polynomial, which gives a minimum of functional (7).
It should be noted that at the first step of the iteration, the previous solutions are absent; therefore Y * 1, the system of equations (10) turns into the classical system of equations of the LSM method for linear multifactor regression, which confirms the correctness of the above transformations. 5
To study the effectiveness of the developed method, test calculations were
performed. The calculations were performed using the mathematical package MATLAB
[
For comparative analysis, three types of equations are taken: 1) large dimension, small degree; 2) small dimension, small degree; 3) a large dimension, a large degree.
The equations are given in Table 1.
For each of the given equations, a table of initial data is generated. As values of the input vector, and also as values of the coefficients of the equations, pseudorandom numbers uniformly distributed over the interval [-2, 2] obtained using the standard function RAND.
The sample size is 100 points (50-training sequence; 50-verification).
Тable 1. Initial Functional Dependencies (11) where: Yi is the value of the output quantity;
Pk ( X i ) – predicted value of the output value by the model.
s
Further, according to the table of experimental data, the initial functional dependence
is restored using the most common self-organization algorithm with quadratic
quotients of the form (4), hereinafter referred to as Algorithm 1, and the developed
selforganization algorithm for the synthesis of multiplicative models with linear private
descriptions (Algorithm 2). A comparative analysis of the calculations is given in
Table 2.
From a comparative analysis of the data table. 2 by criteria [
To the previously noted results of the comparative analysis, we should add the simplicity of obtaining the resulting regression equation obtained by Algorithm 2.
The resulting regression equation in Algorithm 2 is the multiplication of linear private descriptions of the various iteration steps, but to obtain the resulting regression equation in Algorithm 1, it is necessary to do the step-by-step operation of substituting private descriptions of the previous iteration steps in the subsequent ones until we obtain the dependence of the output function Y from the input vector X.
As an example, we show the form of the best solution for approximating the output values of Y of the original equation 1, the form of which is shown in Table 1.
In accordance with the data Table 2, the results are as follows: • Algorithm 1: • error εv = 6,603% • the number of iteration steps r = 3; • the type of analytical expressions (in the induced expressions, the results of the previous iteration steps are indicated by new variables). • 3-rd step of iteration: • Y(z) = –0,0407+0,53z4+0,481z7–1,26z4z7+0,649z42+0,616z72 • 2-nd step of iteration: • z4(v) = 0,0349+0,938v1+0,16v6+0,283v1v6–0,077v12–0,288v62 • z7(v) = –0,017+0,885v2+0,558v6+0,298v2v6–0,168v22–0,175v62 • 1-st step of iteration: • v1(x) = 1,19–1,79x1+0,57x2+0,014x1x2+0,242x12+0,024x22 • v2(x) = 2,91–2,79x1–0,92x3+0,78x1x3+0,369x12–0,09x32 • v6(x) = –0,98+0,69x2–0,08x4–0,573x2x4+0,38x22+0,34x42 • Algorithm 2: • error εv = 1.34% • the number of iteration steps r = 2; • type of analytical expressions • 1-nd step of iteration: • Y(x) = 0,49–1,24x1+0,67x2–0,19x3+0,23x4+0,33x5 • 2-st step of iteration: • Y(x) = 1,12–0,01x1–0,25x3–0,04x4+0,11x5
The change in the average error εv of the best private descriptions while complicating the model for the previously considered functional dependences is given in Table3.
Analysis of the results of the Table 3 shows: • • compared with Algorithm 1 in Algorithm 2, the first step of the iteration makes a significant contribution to reducing the error εv, since already at the first step the algorithm selects the most significant factors. to obtain the resulting regression equation, Algorithm 2 requires no more iteration steps than Algorithm 1 for almost all types of equations.
№ equation
A self-organization method is developed in the work for the synthesis of a multiplicative model with linear private descriptions, in which the degree of the resulting regression equation increases minimally (by one) when moving to the next iteration step, and the number of factors can be maximum already in the first step. This distinctive property of the method cannot be implemented by well-known methods of selforganization, it determines the area of effective use of the method for constructing non-linear regression multifactor models of low-dimensional multidimensional objects. The stages of information conversion are formalized and computational procedures for the implementation of the noted stages are developed. The features of calculating the coefficients of polynomials of the current iteration step in the iterative procedure for the synthesis of the multiplicative model are considered, and analytical expressions are obtained for the first time to calculate the coefficients of linear polynomials by least squares taking into account the noted features. A software implementation of the method using the MATLAB package has been performed. The developed program was tested using test examples, which confirmed its operability, determined its effectiveness and scope. The prospect of further work is the development of a fullfledged software product and the processing of real data. 2. Radchenko S. G. (2011) Metodologiya regressionnogo analiza: Monografiya. [Regression analysis methodology: Monograph] Kiev «Kornijchuk», (in Russian) 3. Demidova O. A., Malahov D. I. (2019) Ekonometrika. Uchebnik i praktikum dlya prikladnogo bakalavriata [Econometrics. Textbook and workshop for applied baccalaureate]. Moscow, Publishing House Yurayt (in Russian) 4. Ivakhnenko A.G. (1982) Induktivny`j metod samoorganizaczii modelej slozhny`kh sistem. [Inductive method of self-organization of models of complex systems].
Kiev, Naukova Dumka (in Russian) 5. Ivakhnenko, A.G., Müller, J.A. (1992) Parametric and nonparametric selection procedures. Experimental Systems Analysis. In: Systems Analysis, Modelling and Simulation (SAMS), 1992, vol.9, pp 157-175 6. Stepashko V. S. (2016) Kontseptualnyye osnovy intellektualnogo modelirovaniya [Conceptual Foundations of Intelligent Modeling] In: Control Systems and Computers, 2016, 4, pp 3-15 (in Russian) 7. Schmidhuber, Jürgen. (2015) Deep learning in neural networks: An overview Neural Networks, 2015, vol. 61, pp 85-117. doi:10.1016/j.neunet.2014.09.003. – arXiv:1404.7828 8. Lytvynenko, V., Wojcik, W., Fefelov, A., Lurie, I., Savina, N., Voronenko, M., Boskin, O., Smailova, S. (2020) Hybrid Methods of GMDH-Neural Networks Synthesis and Training for Solving Problems of Time Series Forecasting Advances in Intelligent Systems and Computing, 1020, pp 513-531. doi: 10.1007/978-3-03026474-1_36 9. Kondrashova N. (2015) Network Structures Algorithms of Group Method of Data Handling. In: Inductive modeling of complex systems: Sat. sciences. works. Kyiv, IRTC ITS NAS and MES of Ukraine, 2015, 7, pp 21-38. 10. Anastasakis, L., and N. Mort. (2001) The development of self-organization techniques in modelling: A review of the group method of data handling (gmdh). Tech. Rep.; University of Sheffield Department of Automatic Control and Systems Engineering 11. Timashova L., Vitkovski T. (2015) Tehnologiya intellektualnogo proizvodstvennogo modelirovaniya virtualnyih predpriyatiy [Intelligent Manufacturing Technology for Virtual Enterprises]. In: Bulletin of NTU "KhPI". Series Informatics and Modelingб 2015, 32, pp 136-147 (in Russian) 12. Efimenko S.M. (2015) Prognozirovanie slozhnyih protsessov v klasse modeley vektornoy avtoregressii na osnove rekurrentno-parallelnogo algoritma СОМВІ MGUA [Prediction of complex processes in the class of vector autoregression models based on the recurrent-parallel algorithm СОМВІ MGUA]. In: Inductive modeling of complex systems: Sat. sciences. works. Kyiv, IRTC ITS NAS and MES of Ukraine, 2015, 7, pp 129-139. (in Ukrainian) 13. Srinivasan, D. (2008) Energy demand prediction using GMDH networks. In: Neurocomputing, 2008, 72, pp 625-629 14. Onwubolu, G. C. (2009) Hybrid self-organizing modeling systems, Vol. 211.
Springer, Ontario.