Group Method of Data Handling

Group Method of Data Handling (GMDH) is a family of algorithms for computer-based mathematical modeling and structural identification. Most of GMDH algorithms are characterized by inductive self-organizing procedure used for multi-parametric model obtaining. Specific behavior characteristics of GMDH enabled its successful use in such fields as data mining, knowledge discovery, forecasting, complex systems modeling, optimization and pattern recognition.

It is supposed an object investigated with GMDH is represented by multiple inputs and at least one output. Also it is supposed the object can be modeled by a certain subset of components of the base function (1):

Base function were x-inputs, Y-output, a - coefficients, f - elementary functions dependent on different sets of inputs, k - number of base function components.

GMDH algorithm has to consider some partial models - component subsets of the base function (1) and choose an optimal model structure that is indicated by the minimum value of an external criterion. The main advantage derived from such a procedure is that the identified model has an optimal complexity adequate to the level of noise in the input data (noise resistant modeling).

GMDH-type Neural Networks

There are many different ways to choose an order for partial models consideration. The very first consideration order used in GMDH and originally called multilayered inductive procedure is the most popular one. Multilayered procedure is equivalent to the Artificial Neural Network with polynomial activation function of neurons. Therefore the algorithm with such an approach usually referred as GMDH-type Neural Network or Polynomial Neural Network.

Combinatorial GMDH

Another important approach to partial models consideration that becomes more and more popular is a brute force combinatorial search that is either limited or full. This approach has some advantages against Polynomial Neural Networks but requires considerable computational power and thus is not effective for objects with more than 30 inputs in case of full search. An important achievement of Combinatorial GMDH is that it fully overperforms linear regression approach if noise level in the input data is greater than zero.

Basic combinatorial algorithm makes the following steps:

  1. Divides data sample onto parts A and B.
  2. Generates structures for partial models.
  3. Estimates coefficients of partial models using  Least Squares Method and sample A.
  4. Calculates value of external criterion for partial models using sample B.
  5. Chooses the best model (set of models) indicated by minimal value of criterion.

External criteria

Optimal model complexity by Pavel Kordik

External criterion is one of the key features of GMDH. Criterion describes requirements to the model, for example minimization of list squares. It is always calculated with a separate part of data sample that have not been used for estimation of coefficients. There are several popular criteria:

  • Criterion of Regularity (CR) - List Squares of a model at the sample B.
  • Criterion of Unbiasdness - Sum of CR value and special CR for which A is B and B is A. Ratio of sample lengthes must be 1:1 i.e. size of A must be the same as size of B.

If a criterion do not define the number of observations for external dataset then the problem of data dividing ratio appears because the forecasting abilities of identified model are very dependant on the dividing ratio.

History

The method was originated in 1968 by Prof. A.G. Ivakhnenko in the Institute of Cybernetics in Kyiv (Ukraine). This approach from the very beginning was a computer-based method so, a set of computer programs and algorithms were the primary practical results achieved at the base of the new theoretical principles. Thanks to the author's policy of open code sharing the method was quickly settled in the large number of scientific laboratories world wide. At that time code sharing was quite a physical action since the Internet is at least 5 years younger then GMDH. Despite this fact the first investigation of GMDH outside the Soviet Union had been made soon by R.Shankar in 1972. Later on different GMDH variants were published by Japanese and Polish scientists.

Period 1968-1971 is characterized by application of only regularity criterion for solving of the problems of identification, pattern recognition and short-term forecasting. As reference functions polynomials, logical nets, fuzzy Zadeh sets and Bayes probability formulas were used. Authors were stimulated by very high accuracy of forecasting with the new approach. Noiseimmunity was not investigated.

Period 1972-1975. The problem of modeling of noised data and incomplete information basis was solved. Multicriteria selection and utilization of additional priory information for noiseimmunity increasing were proposed. Best experiments showed that with extended definition of the optimal model by additional criterion noise level can be ten times more than signal. Then it was improved using Shennon's theorem of General Communication theory.

Period 1976-1979. The convergence of multilayered GMDH algorithms was investigated. It was shown that some multilayered algorithms have "multilayerness error" - analogical to static error of control systems. In 1977 solution of objective systems analysis problems by multilayered GMDH algorithms was proposed. It turned out that sorting-out by criteria ensemble allow to choose the only optimal system of equations and therefore to show complex object elements, their main input and output variables.

Period 1980-1988. Many important theoretical results were received. It became clear that full physical models cannot be used for long-term forecasting. It was proved, that non-physical models of GMDH are more accurate for approximation and forecast than physical models of regression analysis. Two-level algorithms which use two different time scales for modeling were developed.

Since 1989 the new algorithms (AC, OCC, PF) for non-parametric modeling of fuzzy objects and SLP for expert systems were developed and investigated. Present stage of GMDH development can be described as blossom out of twice-multilayered neuronets and parallel combinatorial algorithms for multiprocessor computers.

Algorithms

  • Combinatorial (COMBI)
  • Multilayered Iterative (MIA)
  • GN
  • Objective System Analysis (OSA)
  • Harmonical
  • Two-level (ARIMAD)
  • Multiplicative-Additive (MAA)
  • Objective Computer Clusterization (OCC);
  • Pointing Finger (PF) clusterization algorithm;
  • Analogues Complexing (AC)
  • Harmonical Rediscretization
  • Algorithm on the base of Multilayered Theory of Statistical Decisions (MTSD)
  • Group of Adaptive Models Evolution (GAME)

Software

Bibliography

  • A.G. Ivakhnenko. Heuristic Self-Organization in Problems of Engineering Cybernetics. Automatica 6: pp.207–219, 1970.
  • A.G. Ivakhnenko. Polynomial Theory of Complex System. IEEE Trans. on Systems, Man and Cybernetics, Vol. SMC-1, No. 4, Oct. 1971, pp. 364-378.
  • S.J. Farlow. Self-Organizing Methods in Modelling: GMDH Type Algorithms. New-York, Bazel: Marcel Decker Inc., 1984, 350 p.
  • H.R. Madala, A.G. Ivakhnenko. Inductive Learning Algorithms for Complex Systems Modeling. CRC Press, Boca Raton, 1994.

External Resources


Коротко про МГУА

Згідно сайту gmdh.net Метод групового урахування аргументів (МГУА) - це набір алгоритмів для вирішення різних задач. Його застосування було помічено у таких галузях, як data mining, knowledge discovery, прогнозування та моделювання систем, оптимізація, роспізнавання образів. Як правило, результатом використання МГУА є оптимальна багатопараметрична математична модель поліноміального типу побудована для деякої багатопараметричної вибірки даних, тобто для деякого набору спостережень.


Last modified by Gleb on 03/15/07 16:00:37 (5 years ago)