Experimental Verification of Internal Convergence of Iterative GMDH Algorithms
The availability of so-called internal convergence of some iterative GMDH algorithms is verified in this paper using computational experiments.
Збережено в:
| Дата: | 2012 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2012
|
| Назва видання: | Індуктивне моделювання складних систем |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/45956 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Experimental Verification of Internal Convergence of Iterative GMDH Algorithms / V. Stepashko, O. Bulgakova, V. Zosimov // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 38-42. — Бібліогр.: 2 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-45956 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-459562013-06-22T03:16:50Z Experimental Verification of Internal Convergence of Iterative GMDH Algorithms Stepashko, V. Bulgakova, O. Zosimov, V. The availability of so-called internal convergence of some iterative GMDH algorithms is verified in this paper using computational experiments. В статті за допомогою обчислювальних експериментів перевіряється наявність так званої внутрішньої збіжності деяких ітераційних алгоритмів МГУА. В статті за допомогою обчислювальних експериментів перевіряється наявність так званої внутрішньої збіжності деяких ітераційних алгоритмів МГУА. 2012 Article Experimental Verification of Internal Convergence of Iterative GMDH Algorithms / V. Stepashko, O. Bulgakova, V. Zosimov // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 38-42. — Бібліогр.: 2 назв. — англ. XXXX-0044 http://dspace.nbuv.gov.ua/handle/123456789/45956 681.5.015 en Індуктивне моделювання складних систем Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The availability of so-called internal convergence of some iterative GMDH algorithms is verified in this paper using computational experiments. |
| format |
Article |
| author |
Stepashko, V. Bulgakova, O. Zosimov, V. |
| spellingShingle |
Stepashko, V. Bulgakova, O. Zosimov, V. Experimental Verification of Internal Convergence of Iterative GMDH Algorithms Індуктивне моделювання складних систем |
| author_facet |
Stepashko, V. Bulgakova, O. Zosimov, V. |
| author_sort |
Stepashko, V. |
| title |
Experimental Verification of Internal Convergence of Iterative GMDH Algorithms |
| title_short |
Experimental Verification of Internal Convergence of Iterative GMDH Algorithms |
| title_full |
Experimental Verification of Internal Convergence of Iterative GMDH Algorithms |
| title_fullStr |
Experimental Verification of Internal Convergence of Iterative GMDH Algorithms |
| title_full_unstemmed |
Experimental Verification of Internal Convergence of Iterative GMDH Algorithms |
| title_sort |
experimental verification of internal convergence of iterative gmdh algorithms |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| publishDate |
2012 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/45956 |
| citation_txt |
Experimental Verification of Internal Convergence of Iterative GMDH Algorithms / V. Stepashko, O. Bulgakova, V. Zosimov // Індуктивне моделювання складних систем: Зб. наук. пр. — К.: МННЦ ІТС НАН та МОН України, 2012. — Вип. 4. — С. 38-42. — Бібліогр.: 2 назв. — англ. |
| series |
Індуктивне моделювання складних систем |
| work_keys_str_mv |
AT stepashkov experimentalverificationofinternalconvergenceofiterativegmdhalgorithms AT bulgakovao experimentalverificationofinternalconvergenceofiterativegmdhalgorithms AT zosimovv experimentalverificationofinternalconvergenceofiterativegmdhalgorithms |
| first_indexed |
2025-07-04T05:00:19Z |
| last_indexed |
2025-07-04T05:00:19Z |
| _version_ |
1836691198747607040 |
| fulltext |
Experimental verification of internal convergence
УДК 681.5.015
EXPERIMENTAL VERIFICATION OF INTERNAL CONVERGENCE OF
ITERATIVE GMDH ALGORITHMS
Volodymyr Stepashko1, Oleksandra Bulgakova2, Viacheslav Zosimov1
1. International Research and Training Centre for Information Technologies and Systems of the
NAS and MES of Ukraine. Akademik Glushkov Prospect 40, Kyiv, 03680, Ukraine
2. Mykolaiv V.O.Suhomlynsky National University
sashabulgakova1@gmail.com; stepashko@irtc.org.ua
В статті за допомогою обчислювальних експериментів перевіряється наявність так званої
внутрішньої збіжності деяких ітераційних алгоритмів МГУА.
Ключові слова: індуктивне моделювання, МГУА, багаторядний ітераційний алгоритм,
комбінаторний алгоритм, гібридний алгоритм
The availability of so-called internal convergence of some iterative GMDH algorithms is verified in
this paper using computational experiments.
Keywords Inductive modeling, GMDH, multilayered iterative algorithm, combinatorial algorithm,
hybrid algorithm
В статті за допомогою обчислювальних експериментів перевіряється наявність так званої
внутрішньої збіжності деяких ітераційних алгоритмів МГУА.
Ключевые слова: индуктивное моделирование, МГУА, многорядный итерационный
алгоритм, комбинаторный алгоритм, гибридный алгоритм
Iterative algorithms
In the classical multilayered iterative algorithm MIA GMDH [1] each partial
model ),( ji xxf ix is formed as a combination of input variables , , jx mji ,...,2,1, = ,
in initial layer and combination of model outputs obtained in the previous layer,
starting from the second. Typically linear, bilinear or quadratic polynomials of a pair
of arguments may be used as the partial descriptions:
1
2
1
10
−− ++= r
j
r
i
r
l yayaay , (1)
11
4
1
2
1
10
−−−− +++= r
j
r
i
r
j
r
i
r
l yyayayaay , (1a)
21
5
11
4
21
3
1
2
1
10 )()( −−−−−− +++++= r
j
r
j
r
i
r
i
r
j
r
i
r
l yayyayayayaay (1b)
Coefficients , ,…,0a 1a 5a are estimated in the training data set using the least
squares method. The best F models with respect to the value of an external selection
criterion are involved in the formation of model variants in a next layer. The process
is finished in the layer, after which the criterion minimum begins to grow. In this case
there is a possibility of essential arguments loss in the selection process because those
lost after the first layer fall out from the subsequent selection process.
In [2] we proposed the following types of hybrid algorithms:
Індуктивне моделювання складних систем, випуск 4, 2012 38
mailto:sashabulgakova1@gmail.com
mailto:stepashko@irtc.org.ua
Stepashko V., Bulgakova O., Zosimov V.
1. Combined Iterative Algorithm (CIA) – the algorithm with equal usage of
both intermediate and initial arguments:
),(),()1(
j
r
i
r
j
r
i
r
l xyfyyfy ∨=+ (2)
2. Combined Iterative Combinatorial Algorithm (CICA) – algorithm with
combinatorial optimization of partial descriptions complexity and adding the initial
arguments in each layer to avoid loosing the relevant ones
),(),()1(
j
r
iopt
r
j
r
iopt
r
l xyfyyfy ∨=+ (3)
Combinatorial optimization consists in that on each layer we consider the model,
for example linear:
1
32
1
2110),( −− ++= r
j
r
i
r
j
r
i ydaydadayyf , (4)
where are elements of the binary structural vector d that takes on a
value 1 or 0 (inclusion or non-inclusion of the proper argument):
, :
3,2,1, =kdk
}1,0{=kd ),,(),( opt
r
j
r
i
r
j
r
iopt dyyfyyf =
opt
r
j
r
i
r
j
r
i
r
j
r
i
r
j
r
i
f
CR
CR
CR
CR
CR
CR
CR
yayaaf
yayaf
yaaf
yaaf
yaf
yaf
af
min
7
6
5
4
3
2
1
1
2
1
107
1
2
1
16
1
105
1
104
1
13
1
12
01
111
110
101
011
100
010
001
⇒
⎪
⎪
⎪
⎪
⎭
⎪
⎪
⎪
⎪
⎬
⎫
++=→
+=→
++=→
+=→
=→
=→
=→
−−
−−
−
−
−
−
Internal convergence of iterative algorithms
An iterative algorithm holds an internal convergence if as a result of iteration
process with the selection criterion CR=RSS, where RSS is the residual sum of
squares on the entire sample W (without partition), the estimation of optimal model
parameters are converging to LSM estimates of the true structure model parameters.
The sample splitting to the training and testing sub-samples is not used in this
case (m=10, n=50). It is studying internal convergence of the three iterative GMDH
algorithms: classical MIA, combined CIA, and generalized CICA.
The true model is the following linear function of ten arguments:
10987654321 8,15,23427523 xxxxxxxxxxy +−+−+−+−+−=
o
. (5)
Table 1 and Fig. 1 shows the change of RSS values as dependent on the layer
number r of these algorithms with F = 20.
Індуктивне моделювання складних систем, випуск 4, 2012 39
Experimental verification of internal convergence
Table 1
RSS value in the layers for the three iterative algorithms
Layer, r RSS for CІА RSS for CICA RSS for MIA
1 416,15 416,15 416,15
2 194,25 121,75 346,52
3 44,02 9,20 309,34
4 5,10 0,98 238,12
5 1,47 0,53 201,7
6 0,70 0,27 144,78
7 0,65 0,11 113,12
8 0,59 0,003 113,06
9 0,36 0,0011 –
10 0,21 0,0010 –
11 0,13 0,0010 –
12 0,007 – –
13 0,0069 – –
14 0,0068 – –
15 0,0066 – –
16 0,0064 – –
0,001
0,01
0,1
1
10
100
1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
r
Ln
R
SS RSS for MІА
RSS for CІА
RSS for CICA
Fig. 1 Change of RSS values for the three iterative GMDH algorithms, F = 20
(logarithmic scale)
The constructed models are of form:
109876
54321CIA
003,1808,1514,2994,2997,3
988,1004,7015,1999,4978,1913,2
xxxxx
xxxxxy
+−+−+
+−+−+−=
(6)
109876
54321CICA
003,1801,1500,2999,2000,4
998,1004,7002,1999,4999,1001,3
xxxxx
xxxxxy
+−+−+
+−+−+−=
(7)
Індуктивне моделювання складних систем, випуск 4, 2012 40
Stepashko V., Bulgakova O., Zosimov V.
1098
65432MIA
437,0643,2278,1
726,4812,0266,5535,0334,5387,22
xxx
xxxxxy
+−+
+++−+−=
(8)
The first and second equations (6), (7) generally confirm the internal
convergence of the two iterative algorithms as values of the estimated parameters are
close to the true ones, see (5). The fig.1 shows that the generalized algorithm reaches
its minimum on the 9th layer and the combined one on the 12th, so the convergence
rate of CICA is much higher than CIA. The accuracy of the obtained models also
differs in favor of the generalized algorithm: for CICA RSS=0.001, for CІА
RSS=0.006. This demonstrates the effectiveness of the idea of partial models
optimization. In the classical multilayered algorithm MIA the convergence is
observed only by criterion but there is no internal convergence with respect to the
structure and parameters in view of the loss of true arguments х and х1 7, see (8).
Table 2 shows the change in the best models structure and parameters for CICA.
One can see that the true structure was found at 4 layer after which there was only
changing the values of the parameters being estimated.
Table 2
RSS value in the best models structure and parameters for CICA
Layer r RSS Model
1 416,15 42 581,6521,5806,15 xxy −= + +)
2 121,75 9642 988,1604,5286,5434,4220,7 xxxxy −+++−=)
3 9,20
1098
76542
905,0647,2177,2
412,3467,4073,1700,5782,4084,7
xxх
xxxxxy
+−+
+−+−++=)
4 0,98
109876
54321
962,0801,1492,2968,2016,4
008,2054,7019,1028,5953,1245,2
xxxxx
xxxxxy
+−+−+
+−+−+−=)
5 0,53
109876
54321
964,0801,1505,2968,2016,4
989,1986,6021,1987,4982,1121,3
xxxxx
xxxxxy
+−+−+
+−+−+−=)
6 0,27
109876
54321
965,0801,1505,2995,2004,4
995,1986,6015,1987,4982,1121,3
xxxxx
xxxxxy
+−+−+
+−+−+−=)
7 0,11
109876
54321
988,0801,1501,2997,2001,4
998,1005,7003,1997,4989,1011,3
xxxxx
xxxxxy
+−+−+
+−+−+−=)
8 0,003
109876
54321
003,1801,1501,2999,2000,4
998,1005,7003,1999,4999,1001,3
xxxxx
xxxxxy
+−+−+
+−+−+−=)
9 0,0011
109876
54321
003,1801,1501,2999,2000,4
998,1004,7002,1999,4999,1001,3
xxxxx
xxxxxy
+−+−+
+−+−+−=)
10 0,0010
109876
54321
003,1801,1500,2999,2000,4
998,1004,7002,1999,4999,1001,3
xxxxx
xxxxxy
+−+−+
+−+−+−=)
Індуктивне моделювання складних систем, випуск 4, 2012 41
Experimental verification of internal convergence
To confirm this results, 10 redundant arguments was added to the data sample,
hence m = 20, and true linear model corresponds to the same formula (5). When
doing so, only Combined Iterative Combinatorial algorithm was used. The following
models were obtained using LSM (regression analysis) and CICA:
2019181716
15141312
1110987
654321
00001,0000002,0000001,00000003,000001,0
0000001,00000003,000001,0000002,0
000001,0000,18,1498,23
999,32999,6998,423
xxxxx
xxxx
xxxxx
xxxxxxyREGR
+++−+
+++−+
+−+−+−
−+−+−+−=)
(9)
191310987
654321
000003,000001,0003,1801,1501,2999,2
000,4998,1004,7002,1999,4999,1001,3
xxxxxx
xxxxxxyCICA
+−+−+−
−+−+−+−=)
(10)
The model (9) built by LSM includes all 20 arguments, both true and redundant,
though with very small coefficients, and RSS = 0.0001 for it.
The model (10) confirms the CICA algorithm effectiveness even with 10
redundant (uninformative) arguments. This model includes redundant arguments x13
and x19 but with very small values of estimated parameters.
This means that the iterative algorithm CICA GMDH can be used not only for
structural and parametric identification but also as an iterative procedure of parameter
estimation of models by minimizing RSS.
Conclusion
The results obtained above illustrate, first, that the developed architecture of the
Combined Iterative Combinatorial GMDH algorithm allows investigating various
versions of iterative algorithms, and second, this algorithm demonstrates higher
performance in testing tasks.
The complex technique of analyzing the efficiency of iterative GMDH
algorithms using computational experiments allows a comparative study of various
iterative algorithms effectiveness.
The comparison of the hybrid CICA GMDH algorithm with other iterative
GMDH algorithms has been made based on study of the internal convergence
process. Executed experiments showed the best performance of the CICA algorithm.
References
[1] Ivakhnenko A.G. Group method of data handling as a competitor for the
method of stochastic approximation. – Soviet Automatic Control, 1968, No. 3. – P.
58-72.
[2] Stepashko V., Bulgakova O., Zosimov V. Modified multilayered GMDH
algorithm with combinatorial optimization of partial descriptions complexity //
Proceedings of the III Intern. Conf. on Inductive Modelling ICIM-2010, May 16-22,
2010, Yevpatoria, Crimea, Ukraine. – Kherson: KNTU, 2010. – P. 24-29.
Індуктивне моделювання складних систем, випуск 4, 2012 42
|