Групповой метод обработки данных

Групповой метод обработки данных (GMDH) — это семейство индуктивных алгоритмов компьютерного математического моделирования многопараметрических наборов данных, которое обеспечивает полностью автоматическую структурную и параметрическую оптимизацию моделей.

GMDH используется в таких областях, как интеллектуальный анализ данных , обнаружение знаний , прогнозирование , сложных систем моделирование , оптимизация и распознавание образов . ^[1] Алгоритмы GMDH характеризуются индуктивной процедурой, которая осуществляет перебор постепенно усложняющихся полиномиальных моделей и выбор лучшего решения с помощью внешнего критерия . Последний раздел ^[2] содержит краткое изложение применения GMDH в 1970-х годах.

Другие названия включают «полиномиальную нейронную сеть прямого распространения», ^[3] или «самоорганизация моделей». Это был один из первых методов глубокого обучения , который использовался для обучения восьмислойной нейронной сети в 1971 году. ^[4]^[5]

Математическое содержание

Полиномиальная регрессия

Этот раздел основан на. ^[2]

Это общая проблема статистического моделирования данных: рассмотрим набор данных. $\{(x_{1},...,x_{k};y)_{s}\}_{s=1:n}$ , с $n$ точки. Каждая точка содержит $x_{1},...,x_{k}$ наблюдения и одна цель $y$ предсказать. Как лучше всего предсказать цель на основе наблюдений?

Сначала мы разделили полный набор данных на две части: обучающий набор и набор проверки. Обучающий набор будет использоваться для подбора все большего и большего количества параметров модели, а проверочный набор будет использоваться для принятия решения о том, какие параметры включать и когда полностью прекратить подгонку.

GMDH начинается с рассмотрения полинома второй степени от двух переменных. Предположим, мы хотим предсказать цель, используя только $i,j$ частей наблюдения и используя только полиномы степени 2, то максимум, что мы можем сделать, это следующее: $y\approx f_{a,b,c,d,e,h}(x_{i},x_{j}):=a+bx_{i}+cx_{j}+dx_{i}^{2}+ex_{j}^{2}+fx_{i}x_{j}$ где параметры $a,b,c,d,e,f$ вычисляются методом линейной регрессии . Теперь параметры $a,b,c,d,e,f$ зависит от того, какой $i,j$ мы выбрали, и мы не знаем, какой $i,j$ мы должны выбирать, поэтому мы выбираем их всех. То есть мы выполняем все ${\frac {1}{2}}k(k-1)$ такие полиномиальные регрессии: $y\approx f_{(i,j);a,b,c,d,e,h}(x_{i},x_{j}):=a_{i,j}+b_{i,j}x_{i}+c_{i,j}x_{j}+d_{i,j}x_{i}^{2}+e_{i,j}x_{j}^{2}+f_{i,j}x_{i}x_{j}\quad \forall 1\leq i<j\leq k$ получение ${\frac {1}{2}}k(k-1)$ полиномиальные модели набора данных.

Мы не хотим принимать все полиномиальные модели, поскольку они будут содержать слишком много моделей. Чтобы выбрать только лучшее подмножество этих моделей, мы запускаем каждую модель $f_{(i,j);a,b,c,d,e,h}$ в наборе данных проверки и выберите модели, среднеквадратическая ошибка которых ниже порогового значения. Мы также запишем наименьшую полученную среднеквадратическую ошибку как $minMSE_{1}$ .

Предположим, что после этого процесса мы получили набор $k_{1}$ модели. Теперь мы запускаем модели в наборе обучающих данных, чтобы получить последовательность преобразованных наблюдений: $z_{1},z_{2},...,z_{k_{1}}$ . Теперь тот же алгоритм можно запустить еще раз.

Алгоритм продолжается, давая нам $minMSE_{1},minMSE_{2},...$ . Пока каждый $minMSE$ меньше предыдущего, процесс продолжается, давая нам все более глубокие модели. Как только некоторые $minMSE_{L+1}>minMSE_{L}$ , алгоритм завершается. Последний установленный слой (слой $L+1$ ) отбрасывается, поскольку оно превысило обучающий набор. Предыдущие слои выводятся.

Возможны более сложные методы принятия решения о прекращении действия. Например, можно продолжить выполнение алгоритма еще на несколько шагов в надежде преодолеть временное повышение $minMSE$ .

В общем

Вместо полинома 2-й степени от двух переменных каждое подразделение может использовать полиномы более высокой степени от большего количества переменных: ^[1]

Y(x_{1},\dots ,x_{n})=a_{0}+\sum \limits _{i=1}^{n}{a_{i}}x_{i}+\sum \limits _{i=1}^{n}{\sum \limits _{j=i}^{n}{a_{ij}}}x_{i}x_{j}+\sum \limits _{i=1}^{n}{\sum \limits _{j=i}^{n}{\sum \limits _{k=j}^{n}{a_{ijk}}}}x_{i}x_{j}x_{k}+\cdots

В более общем смысле, модель GMDH с несколькими входами и одним выходом представляет собой подмножество компонентов базовой функции (1):

Y(x_{1},\dots ,x_{n})=a_{0}+\sum \limits _{i=1}^{m}a_{i}f_{i}

где f _i — элементарные функции, зависящие от различных наборов входных данных, a _i — коэффициенты, а m — количество компонентов базовой функции.

Внешние критерии

Внешними критериями являются цели оптимизации модели, такие как минимизация среднеквадратической ошибки в наборе проверки, как указано выше. Наиболее распространенными критериями являются:

Критерий регулярности (CR) – наименьшие средние квадраты на проверочном наборе.
Наименьшие квадраты в наборе перекрестной проверки .
Критерий минимального смещения или согласованности - квадратичная разница между оцененными выходными данными (или векторами коэффициентов) двух моделей, подходящих для набора A и B, деленная на квадраты прогнозов для набора B. ^[1]

Идея

Подобно линейной регрессии, которая соответствует линейному уравнению по данным, GMDH соответствует полиномиальным уравнениям произвольно высокого порядка по данным. ^[6]^[7]

Для выбора между моделями используются два или более подмножества выборки данных, аналогично разделению train-validation-test .

GMDH объединила идеи: ^[8] моделирование черного ящика , последовательный генетический отбор парных признаков , ^[9] принцип Габора , «свободы выбора решений» ^[10] и Бера . принцип внешних дополнений ^[11]

Вдохновленный аналогией между построением модели из зашумленных данных и отправкой сообщений через зашумленный канал , ^[12] они предложили «помехоустойчивое моделирование»: ^[6] чем выше шум, тем меньше параметров должна иметь оптимальная модель, поскольку зашумленный канал не позволяет передавать больше битов.

Модель структурирована как нейронная сеть прямого распространения, но без ограничений по глубине имела процедуру автоматической генерации структуры модели, имитирующую процесс биологического отбора с парными генетическими признаками.

История

Автор ГМДГ – советский учёный профессор А.Г. Ивахненко.

Метод был разработан в 1968 году профессором Алексеем Георгиевичем Ивахненко в Институте кибернетики в Киеве .

Период 1968–1971 гг. характеризуется применением только критерия регулярности для решения задач идентификации, распознавания образов и краткосрочного прогнозирования. В качестве эталонных функций использовались полиномы, логические сети, нечеткие множества Заде и формулы вероятности Байеса. Авторов порадовала очень высокая точность прогнозирования при использовании нового подхода. Помехоустойчивость не исследовалась.

Период 1972–1975 гг . Решена проблема моделирования зашумленных данных и неполной информационной базы. Предложен многокритериальный отбор и использование дополнительной априорной информации для повышения помехоустойчивости. Лучшие эксперименты показали, что при расширенном определении оптимальной модели по дополнительному критерию уровень шума может быть в десять раз больше сигнала. Затем она была улучшена с использованием теоремы Шеннона об общей теории коммуникации.

Период 1976–1979 гг . Исследована сходимость многоуровневых алгоритмов GMDH. Показано, что некоторые многослойные алгоритмы имеют «ошибку многослойности» – аналогичную статической ошибке систем управления. В 1977 г. было предложено решение задач анализа объективных систем с помощью многоуровневых алгоритмов GMDH. Оказалось, что сортировка по ансамблю критериев позволяет найти единственную оптимальную систему уравнений и, следовательно, выявить элементы сложного объекта, их основные входные и выходные переменные.

Период 1980–1988 гг . Получено много важных теоретических результатов. Стало ясно, что полные физические модели нельзя использовать для долгосрочного прогнозирования. Доказано, что нефизические модели ГМДГ более точны для аппроксимации и прогнозирования, чем физические модели регрессионного анализа. Были разработаны двухуровневые алгоритмы, использующие для моделирования два разных временных масштаба.

С 1989 г. были разработаны и исследованы новые алгоритмы (AC, OCC, PF) непараметрического моделирования нечетких объектов и SLP для экспертных систем. ^[13] Современный этап развития GMDH можно охарактеризовать как расцвет нейросетей глубокого обучения и параллельных индуктивных алгоритмов для многопроцессорных компьютеров. Такая процедура в настоящее время используется в сетях глубокого обучения . ^[14]

Нейронные сети типа GMDH

Выбрать заказ на рассмотрение частичных моделей можно разными способами. Самый первый порядок рассмотрения, используемый в GMDH и первоначально названный многослойной индуктивной процедурой, является наиболее популярным. Это перебор постепенно усложняющихся моделей, генерируемых из базовой функции . На лучшую модель указывает минимум внешней критериальной характеристики. Многоуровневая процедура эквивалентна искусственной нейронной сети с полиномиальной функцией активации нейронов. Поэтому алгоритм с таким подходом обычно называют нейронной сетью типа GMDH или полиномиальной нейронной сетью. Ли показал, что нейронная сеть типа GMDH работает лучше, чем классические алгоритмы прогнозирования, такие как Single Exponential Smooth, Double Exponential Smooth, ARIMA и нейронная сеть обратного распространения ошибки. ^[15]

Комбинаторная ГМДГ

Еще одним важным подходом к рассмотрению частичных моделей, который становится все более популярным, является комбинаторный поиск, который может быть либо ограниченным, либо полным. Этот подход имеет некоторые преимущества по сравнению с полиномиальными нейронными сетями, но требует значительной вычислительной мощности и, следовательно, неэффективен для объектов с большим количеством входных данных. Важным достижением комбинаторного GMDH является то, что он полностью превосходит подход линейной регрессии, если уровень шума во входных данных больше нуля. Это гарантирует, что в ходе исчерпывающей сортировки будет найдена наиболее оптимальная модель.

Базовый комбинаторный алгоритм выполняет следующие шаги:

Делит выборку данных как минимум на две выборки A и B.
Генерирует подвыборки из A в соответствии с частичными моделями с постоянно возрастающей сложностью.
Оценивает коэффициенты частичных моделей на каждом уровне сложности модели.
Рассчитывает значение внешнего критерия для моделей на выборке B.
Выбирает лучшую модель (набор моделей), указанную по минимальному значению критерия.
Для выбранной модели оптимальной сложности пересчитываем коэффициенты на всей выборке данных.

В отличие от нейронных сетей типа GMDH комбинаторный алгоритм обычно не останавливается на определенном уровне сложности, поскольку точкой увеличения значения критерия может быть просто локальный минимум, см. рис.1.

Алгоритмы

Комбинаторный (КОМБИ)
Многоуровневая итерация (MIA)
ГН
Объективный системный анализ (OSA)
Гармоничный
Двухуровневый (АРИМАД)
Мультипликативно-аддитивный (МАА)
Объективная компьютерная кластеризация (OCC);
Алгоритм кластеризации Pointing Finger (PF);
Комплексообразование аналогов (АК)
Гармоническая редискретизация
Алгоритм на основе многослойной теории статистических решений (MTSD)
Группа эволюции адаптивных моделей (ИГРА)

Реализации программного обеспечения

Проект FAKE GAME — с открытым исходным кодом. Кроссплатформенность.
ГЭвом — Бесплатно по запросу для академического использования. Только для Windows.
GMDH Shell — программное обеспечение для прогнозной аналитики и прогнозирования временных рядов на основе GMDH. Доступны бесплатная академическая лицензия и бесплатная пробная версия. Только для Windows.
KnowledgeMiner — Коммерческий продукт. Только для Mac OS X. Доступна бесплатная демо-версия.
Клиент PNN Discovery — Коммерческий продукт.
Научный РПФ! — Бесплатное ПО, с открытым исходным кодом.
wGMDH — плагин Weka , с открытым исходным кодом.
Пакет R – открытый исходный код.
Пакет R для задач регрессии – с открытым исходным кодом.
Библиотека Python алгоритма MIA — с открытым исходным кодом.
Библиотека Python основных алгоритмов GMDH (COMBI, MULTI, MIA, RIA) — с открытым исходным кодом.

Ссылки

^ Перейти обратно: ^а ^б ^с Мадала, HR; Ивахненко О.Г. (1994). Алгоритмы индуктивного обучения для моделирования сложных систем . Бока-Ратон: CRC Press. ISBN 978-0849344381 . Архивировано из оригинала 31 декабря 2017 г. Проверено 17 ноября 2019 г.
^ Перейти обратно: ^а ^б Фарлоу, Стэнли Дж. (ноябрь 1981 г.). «Алгоритм GMDH Ивахненко» . Американский статистик . 35 (4): 210–215. дои : 10.1080/00031305.1981.10479358 . ISSN 0003-1305 .
^ Николаев, штат Нью-Йорк; Иба, Х. (март 2003 г.). «Изучение полиномиальных нейронных сетей прямого распространения с помощью генетического программирования и обратного распространения ошибки» . Транзакции IEEE в нейронных сетях . 14 (2): 337–350. дои : 10.1109/ТНН.2003.809405 . ISSN 1045-9227 .
^ Ивахненко, Алексей (1971). «Полиномиальная теория сложных систем» (PDF) . Транзакции IEEE по системам, человеку и кибернетике . СМК-1 (4): 364–378. дои : 10.1109/TSMC.1971.4308320 .
^ Шмидхубер, Юрген (2015). «Глубокое обучение в нейронных сетях: обзор». Нейронные сети . 61 : 85–117. arXiv : 1404.7828 . дои : 10.1016/j.neunet.2014.09.003 . ПМИД 25462637 . S2CID 11715509 .
^ Перейти обратно: ^а ^б Ivakhnenko, O.G.; Stepashko, V.S. (1985). Pomekhoustojchivost' Modelirovanija (Noise Immunity of Modeling) (PDF) . Kyiv: Naukova Dumka. Archived from the original (PDF) on 2017-12-31 . Retrieved 2019-11-18 .
^ Ивахненко О.Г.; Лапа, В.Г. (1967). Кибернетика и методы прогнозирования (Современные аналитические и вычислительные методы в науке и математике, т.8 изд.). Американский Эльзевир.
^ Ивахенко А.Г.; Савченко Е.А.; Ивахенко Г.А. (октябрь 2003 г.). «Проблемы разработки будущих алгоритмов GMDH» . Системный анализ, моделирование . 43 (10): 1301–1309. дои : 10.1080/0232929032000115029 . ISSN 0232-9298 .
^ Ивахненко, Алексей Г. и Григорий А. Ивахненко. «Проблемы дальнейшего развития группового метода алгоритмов обработки данных. Часть I». Распознавание образов и анализ изображений ч/ц распознавания образов и анализа изображений 10.2 (2000): 187-194.
^ Габор, Д. (1971). Перспективы строгания. Организация экономического сотрудничества и развития . Лондон: Imp.Coll.
^ Бир, С. (1959). Кибернетика и управление . Лондон: Английский университет. Нажимать.
^ Иваненко, О.Г. (1982). Индуктивный метод самоорганизации моделей сложных систем (PDF) . Киев: Наукова думка. Архивировано из оригинала (PDF) 31 декабря 2017 г. Проверено 18 ноября 2019 г.
^ Ивахненко О.Г.; Ивахненко Г.А. (1995). «Обзор проблем, решаемых алгоритмами группового метода обработки данных (GMDH)» (PDF) . Распознавание образов и анализ изображений . 5 (4): 527–535. CiteSeerX 10.1.1.19.2971 .
^ Такао, С.; Кондо, С.; Уэно, Дж.; Кондо, Т. (2017). «Нейронная сеть типа GMDH с глубокой обратной связью и ее применение для анализа медицинских изображений МРТ-изображений мозга». Искусственная жизнь и робототехника . 23 (2): 161–172. дои : 10.1007/s10015-017-0410-1 . S2CID 44190434 .
^ Ли, Рита Йи Ман; Фонг, Саймон; Чонг, Кайл Вен Санг (2017). «Прогнозирование REIT и фондовых индексов: групповой метод обработки данных с помощью нейронной сети». Журнал исследований недвижимости Тихоокеанского региона . 23 (2): 123–160. дои : 10.1080/14445921.2016.1225149 . S2CID 157150897 .

Внешние ссылки

Дальнейшее чтение

АГ Ивахненко. Эвристическая самоорганизация в задачах инженерной кибернетики , Автоматика, т.6, 1970 — с. 207-219.
С. Дж. Фарлоу . Методы самоорганизации в моделировании: алгоритмы типа GMDH . Нью-Йорк, Базель: Marcel Decker Inc., 1984, 350 стр.
Х. Р. Мадала, А. Г. Ивахненко. Алгоритмы индуктивного обучения для моделирования сложных систем . CRC Press, Бока-Ратон, 1994.

[r1-1] Перейти обратно: ^а ^б ^с Мадала, HR; Ивахненко О.Г. (1994). Алгоритмы индуктивного обучения для моделирования сложных систем . Бока-Ратон: CRC Press. ISBN 978-0849344381 . Архивировано из оригинала 31 декабря 2017 г. Проверено 17 ноября 2019 г.

[:0-2] Перейти обратно: ^а ^б Фарлоу, Стэнли Дж. (ноябрь 1981 г.). «Алгоритм GMDH Ивахненко» . Американский статистик . 35 (4): 210–215. дои : 10.1080/00031305.1981.10479358 . ISSN 0003-1305 .

[3] Николаев, штат Нью-Йорк; Иба, Х. (март 2003 г.). «Изучение полиномиальных нейронных сетей прямого распространения с помощью генетического программирования и обратного распространения ошибки» . Транзакции IEEE в нейронных сетях . 14 (2): 337–350. дои : 10.1109/ТНН.2003.809405 . ISSN 1045-9227 .

[iva1971-4] Ивахненко, Алексей (1971). «Полиномиальная теория сложных систем» (PDF) . Транзакции IEEE по системам, человеку и кибернетике . СМК-1 (4): 364–378. дои : 10.1109/TSMC.1971.4308320 .

[5] Шмидхубер, Юрген (2015). «Глубокое обучение в нейронных сетях: обзор». Нейронные сети . 61 : 85–117. arXiv : 1404.7828 . дои : 10.1016/j.neunet.2014.09.003 . ПМИД 25462637 . S2CID 11715509 .

[r3-6] Перейти обратно: ^а ^б Ivakhnenko, O.G.; Stepashko, V.S. (1985). Pomekhoustojchivost' Modelirovanija (Noise Immunity of Modeling) (PDF) . Kyiv: Naukova Dumka. Archived from the original (PDF) on 2017-12-31 . Retrieved 2019-11-18 .

[7] Ивахненко О.Г.; Лапа, В.Г. (1967). Кибернетика и методы прогнозирования (Современные аналитические и вычислительные методы в науке и математике, т.8 изд.). Американский Эльзевир.

[8] Ивахенко А.Г.; Савченко Е.А.; Ивахенко Г.А. (октябрь 2003 г.). «Проблемы разработки будущих алгоритмов GMDH» . Системный анализ, моделирование . 43 (10): 1301–1309. дои : 10.1080/0232929032000115029 . ISSN 0232-9298 .

[9] Ивахненко, Алексей Г. и Григорий А. Ивахненко. «Проблемы дальнейшего развития группового метода алгоритмов обработки данных. Часть I». Распознавание образов и анализ изображений ч/ц распознавания образов и анализа изображений 10.2 (2000): 187-194.

[10] Габор, Д. (1971). Перспективы строгания. Организация экономического сотрудничества и развития . Лондон: Imp.Coll.

[11] Бир, С. (1959). Кибернетика и управление . Лондон: Английский университет. Нажимать.

[r7-12] Иваненко, О.Г. (1982). Индуктивный метод самоорганизации моделей сложных систем (PDF) . Киев: Наукова думка. Архивировано из оригинала (PDF) 31 декабря 2017 г. Проверено 18 ноября 2019 г.

[13] Ивахненко О.Г.; Ивахненко Г.А. (1995). «Обзор проблем, решаемых алгоритмами группового метода обработки данных (GMDH)» (PDF) . Распознавание образов и анализ изображений . 5 (4): 527–535. CiteSeerX 10.1.1.19.2971 .

[14] Такао, С.; Кондо, С.; Уэно, Дж.; Кондо, Т. (2017). «Нейронная сеть типа GMDH с глубокой обратной связью и ее применение для анализа медицинских изображений МРТ-изображений мозга». Искусственная жизнь и робототехника . 23 (2): 161–172. дои : 10.1007/s10015-017-0410-1 . S2CID 44190434 .

[15] Ли, Рита Йи Ман; Фонг, Саймон; Чонг, Кайл Вен Санг (2017). «Прогнозирование REIT и фондовых индексов: групповой метод обработки данных с помощью нейронной сети». Журнал исследований недвижимости Тихоокеанского региона . 23 (2): 123–160. дои : 10.1080/14445921.2016.1225149 . S2CID 157150897 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]