автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Применение методов агрегации экспертов и регрессии на основе гауссовских процессов для построения метамоделей

На правах рукописи

Приходько Павел Викторович

Применение методов агрегации экспертов и регрессии на основе гауссовских процессов для построения метамоделей

Специальность: 05.13.17- теоретические основы информатики

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

7 НОЯ 2013

Москва 2013

005537611

Работа выполнена в Федеральном государственном бюджетном учреждении науки Институт проблем передачи информации им. A.A. Харкевича Российской Академии Наук (ИППИ РАН)

Научный руководитель:

кандидат физико-математических паук, доцент Е.В. Вурнаев Официальные оппоненты:

доктор физико-математических наук, профессор В.В. Вьюгин,

кандидат физико-математических наук, профессор А.Я. Червоненкис Ведущая организация:

Федеральное государственное бюджетное учреждение науки Институт проблем информатики Российской академии паук (ИПИ РАН)

Защита состоится 27 ноября 2013 г. в 10.30 на заседании диссертационного совета Д 212.156.04 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный, Московская обл.. Институтский пер., д. 9, ауд. 204 Нового корпуса. С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан 25 октября 2013 г.

Ученый секретарь диссертационного топ^^^Иг^ед^-«^ к.ф.-м.н. Х^ FHH л- В-

Общая характеристика работы

Актуальность проблемы. Последнее десятилетие с развитием вычислительной техники при проектировании инженерных объектов возник спрос на построение метамоделей (суррогатных моделей)1,2 для анализа данных экспериментов или сложных вычислительных кодов.

Спрос обусловлен следующей проблемой: инженеру требуется оптимизировать или исследовать поведение некоторой зависимости, являющейся функцией от ряда параметров3, однако, вычисление значения этой функции для новых значений параметров (в новой точке) затратно в смысле вычислительных ресурсов, времени или даже невозможно. Зачастую такое происходит, если данные получены из натурного эксперимента или для вычисления значения функции в новой точке требуется использовать "тяжелый" вычислительный код (например, обсчет модели конечных элементов даже на современных вычислительных мощностях может занимать несколько дней).

Для случаев, когда инженеру достаточно получить лишь приближенное решение задачи, одним из популярных подходов, позволяющих проанализировать зависимость, стало построение по имеющимся данным математической модели (метамодели), которая, насколько это вообще возможно, имитирует поведение рассматриваемой зависимости, однако, при этом может быть очень быстро вычислена в произвольных точках. При таком подходе, после того как метамодель построена, она полностью заменяет собой (аппроксимирует) исходную зависимость во всех последующих расчетах (по этой причине такие модели также иногда называют суррогатными моделями). Качество метамодели обычно определяется тем, насколько она хорошо воспроизводит поведение исходной зависимости в смысле некоторой заданной метрики, например, среднеквадратичной разности между предсказаниями метамодели и истинными значениями зависимости на некоторой репрезентативной выборке данных.

1 Kuleshov А.P., Bernstein A.V., B-urnaev E.V. Adaptive modela of complex systems based on data handling // Proceedings of the 3rd international Conference on Inductive Modelling, Kyiv, Ukraine, pp. 6Î-71, 2010.

2Forrester A., Sobester A., Keane A. Engineering Design via Surrogate Modelling. A Practical Guide. Wiley, 200S

^такжЕ в дальнейшем в том же смысле употребляются термины "признаки" и "входы"

Довольно часто на практике исходная зависимость существенно нелинейна, характер ее поведения неизвестен, а в наличии имеется только выборка пар "параметры"—"значение зависимости". В этом случае для построения метамоделей как правило применяются универсальные методы построения регрессионных моделей из статистики и машинного обучения, такие как: искусственные нейронные сети4 или регрессия на основе гауссовских процессов (кригинг)5. Соответствующие базовые метамодели (далее будем называть их также просто моделями), построенные с помощью таких методов, не предполагают априори какой-то специальный вид аппроксимируемой зависимости и их параметры могут быть настроены так, чтобы приблизить довольно широкий класс функций.

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

В работе рассматриваются такие надстройки для нескольких специальных случаев:

Недостаточная сложность модели. В ряде работ® показывается, что в случае "простой" базовой модели, точность аппроксимации может быть существенно повышена, если итоговая модель определенным образом строится как линейная комбинация (ансамбль) некоторого количества базовых моделей.

Кроме того, в случае использования искуственных нейронных сетей (ИНС) в качестве базовой модели на практике не всегда возможно заранее оценить сложность зависимости и соответственно подобрать адекватную ей сложность (определяемую количеством узлов) ИНС, что приводит к необходимости итеративного выбора структуры модели в соответствии с некоторым дополнительным критерием. В этом смысле построение ансамблей может быть альтернативой прямому увеличению сложности ИНС.

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

^Хайкин С. Нейронные сети: полный курс, второе издание Вильяме. 2006.

5Rasmussen С.Е., Williams G.K.I. Gaussian Processes for Machine Learning. MIT Press, 2006.

«IV. Ueda and R. Nakano. Generalization error of ensemble estimators, In Proceedings of International Conference on Neural Networks, pp. 90-95, 1996.

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

Для описания неоднородного поведения функции в работе рассматриваются следующие распространенные модели неоднородности:

1) данные порождены смесью нормальных распределений, у каждого элемента смеси свой характер зависимости7,

2) данные описываются набором областей, разделенных линейными гиперплоскостями, причем в каждой области наблюдается свой вид зависимости.

Первая модель неоднородности позволяет эффективно описывать случаи, в которых обучающая выборка неравномерно заполняет пространство признаков (пространство дизайна); вторая модель подходит для описания задач, в которых аппроксимируемая зависимость имеет разрывы.

Избыточность в признаках. Набор признаков обычно может быть избыточен в одном из следующих смыслов:

1) Входные признаки могут быть скоррелированы,

2) Функция слабо зависит или не зависит вовсе от некоторых исходных признаков,

3) Функция зависит только от проекции входов на некоторое подпространство.

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

7Имеется е виду, что, если для каждого элемента смеси построить базовую модель только по точкам, принадлежащим 9тому элементу смеси, то такая модель для данного элемента будет существенно точнее, нем модель, построенная по всей обучающей выборке.

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

Кроме того, снижение размерности данных, если при этом не теряется информация о зависимости, также эффективно уплотняет выборку (плотность точек в проекции на подпространство меньшей размерности получается выше, чем по всему пространству), что упрощает задачу аппроксимации.

В литературе присутствует множество процедур8, позволяющих находить проекцию входов на некоторое подпространство. Однако при использовании таких процедур, как правило, необходимо заранее указывать размерность сжатия, а также строить ядерные оценки зависимости (требующие подбора параметров, например, посредством кросс-проверки), которые работают хорошо лишь в случае малых размерностей. Указанные особенности делают эти методы малоприменимыми на практике.

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

В соответствии с поставленной целью были определены следующие задачи исследования:

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

2. Разработать методы построения моделей в случае, когда функция зависит лишь от некоторой проекции признаков на линейное подпространство.

8 Yingcun JCia, Howell Tong, W. К. Li, Li-Xing Zhu. An adaptive estimation of dimension reduction space // J. R. Statist. Soc. В (2002) 64, Part 3, pp. 363-410

3. Разработать методы агрегации базовых регрессионных моделей для случаев, когда

а) выборка неоднородна, присутствуют выраженные кластеры точек и требуется выделить в пространстве признаков области, для каждой из которых будет строиться своя локальная модель,

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

Общая методика исследования. Для решения поставленных задач в работе используются методы машинного обучения, статистики и статистической теории машинного обучения, языки Matlab и python для разработки прототипов предложенных методов. Также было проведено обширное экспериментальное исследование.

Научная новизна результатов, полученных в диссертации, заключа-

ется в том, что в ней предложен набор оригинальных процедур:

• Разработана процедура построения регрессионной модели в случае, если функция зависит лишь от проекции признаков на некоторое неизвестное линейное подпространство, что позволяет существенно улучшить качество модели при выполнении этого модельного предположения, а также дает возможность линейно снизить размерность данных. Кроме того, качество построенной модели становится устойчивым к повороту координатных осей пространства дизайна. Предлагается метод оценки размерности линейного подпространства, а также способ нахождения базиса в этом подпространстве.

• Разработана процедура построения ансамблей регрессионных моделей БегБуст. Получена верхняя граница на ошибку обобщающей способности процедуры.

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

Теоретическая и практическая значимость

Описанные в работе методы широко применяются для решения прикладных задач аэрокосмической отрасли в компании DATADVANCE. Кроме того, для метода построения ансамблей БегБуст получена верхняя граница на ошибку обобщающей способности. Развитые при этом теоретические подходы можно использовать при анализе других алгоритмов построения ансамблей.

Основные результаты, выносимые на защиту:

1. Процедура VEGA (Variable Extraction via Gradient Approximation) нахождения подпространства эффективной размерности для заданной функции по выборке.

2. Метод построения ансамблей регрессионных моделей БегБуст. Верхняя граница ошибки обобщающей способности метода БегБуст.

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

Апробация работы

Результаты работы докладывались и обсуждались на следующих российских и международных конференциях:

• "Интеллектуализация обработки информации" (2012, Будва, Черногория),

• 1st International Conference on Composites Structures Dynamics (2012, Аркашон, Франция). Было сделано два доклада, один из которых пленарный,

• Uncertainty in Computer Models 2012 Conference (2012, Шеффилд, Англия),

• "Математические методы распознавания образов" (2011, Петрозаводск, Россия),

• "Информационные Технологии и Системы" (2009, Бекасово, Россия; 2010, 2011 Геленджик, Россия; 2012, Петрозаводск, Россия),

• Third International Workshop on Surrogate Modelling and Space Mapping For Engineering Optimization (2012, Рейкьявик, Исландия),

• 9th International Conference "Computer Data Analysis and Modeling: Complex Stochastic Data and Systems" (2010, Минск, Белоруссия),

• 52-я, 53-я, 54-я научные конференции Московского физико-технического института (2009-2012, Долгопрудный, Россия),

• Sixth conference "Mathematical Methods in Reliability" (2009, Москва, Россия).

Полученные в работе результаты обсуждались на научных семинарах лаборатории структурных методов анализа данных в предсказательном моделировании МФТИ (2012, 2013) и иа семинарах секторов 5 и 8.1 Института проблем передачи информации им A.A. Харкевича.

Описанные в работе методы были реализованы в программном продукте MACROS, разработанном компанией DATADVANCE, и используются при решении практических задач такими компаниями как Airbus, Eurocopter. В диссертации приводится несколько примеров практических задач, где применение предложенных процедур позволило улучшить качество модели.

Публикации

По теме диссертации опубликовано 10 печатных работ, из них 3 работы — статьи в ведущих рецензируемых научных журналах, 7 работ в трудах ведущих российских и международных конференций.

Основные результаты представлены в работах [1], [2], [3]. В работах [1],[2] вклад автора был определяющим. В работе [3] автор отвечал за часть связанную с построением суррогатных моделей, в то

время как S. Grihon отвечал за запуск оптимизации и валидацию результатов.

Во всех работах Бурнаев Е.В., как научный руководитель, отвечал за глобальную постановку задачи, кроме того автор хотел бы выразить ему благодарность за огромную помощь в написании и правке текстов статей.

Диссертационная работа была выполнена при поддержке лаборатории структурных методов анализа данных в предсказательном моделировании МФТИ, грант правительства РФ дог. 11.G34.31.0073.

Объем и структура работы

Диссертация состоит из введения, четырех глав, заключения и приложения. Полный объем диссертации составляет 121 страницу с 24 рисунками и 1 таблицей. Список литературы содержит 54 наименования.

Содержание работы

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

Пусть задана обучающая выборка Sm = (Xm,Ym), Xm = {х'!',г = 1,..., m}, Ym = {y(l), г = 1,..., m}, такая, что

• входные вектора (входы) х'*' е X С RJ (X - произвольное компактное множество) порождаются независимым образом из некоторого неизвестного непрерывного распределения Р(х),х е X,

• между выходным значением (выходом) у^ £ Y С R1 и входным вектором х^ £ X есть некоторая неизвестная функциональная зависимость уW = / (хМ).

Задача восстановления неизвестной зависимости у = f(x) состоит в построении по обучающей выборке Sm регрессионной зависимости (аппрок-симатора) /(.г) = / (;r|Sm) такой, что её обобщающая способность, т.е.

величина (риск) erpj (/) = Е (/(г) - /(*)) = /х (/(х) - />)) dP{x) мала с вероятностью, близкой к единице. Здесь Е обозначает математическое ожидание по распределению Р{х).

На практике распределение Р{х) неизвестно, поэтому вместо erpj yfj подсчитывают среднеквадратичную ошибку (эмпирический риск) ersm

II "И2

||/~ /|| > гДе выборочная норма ||г>||х,„ функции v определяется как

IMIxm =

Будем называть базовым аппроксиматором функцию д = Train(Sm, w). порождаемую некоторым методом обучения Train(-), применённым к обучающей выборке Srn и, возможно, зависящим от некоторого набора гиперпараметров w £ i! (например, случайной инициализации начальных значений параметров базового аппроксиматора).

В качестве метода обучения могут быть использованы многие алгоритмы машинного обучения, такие как: линейная регрессия, регрессия на основе гауссовских процессов (кригинг), регрессия на основе опорных векторов, искуственные нейронные сети (ИНС), регрессионные деревья (CART).

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

Как вариант решения проблемы предлагается метод построения ансамблей регрессионных моделей БегБуст. На примере применения к ис-куственным нейронным сетям при некоторых дополнительных предположениях доказывается сходимость метода, а также проводится его сравнение с основными подходами к построению ансамблей, описанными в литературе.

В разделе 2.1 приводится постановка задачи построения ансамблей.

Под построением ансамбля базовых аппроксиматоров для решения задачи восстановления неизвестной зависимости на основе данных понимается способ получения аппроксиматора /(х) в виде некоторого функционала /(х) = fn(gi(x),.. .,дп(х)), где гу,(х), г = являются базовыми аппроксиматорами из некоторого заданного класса G, построенными на основе данных Sm. Рассматривается случай, когда ансамбль /„ линеен

ПО <71,...,т.е.

п ¿=1

для некоторых коэффициентов {«¿}"=1.

Таким образом, алгоритм построения ансамбля сводится к описанию того, как построить базовые модели (/!,..., дп и задать веса

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

В разделе 2.3 приводится описание предложенной методики.

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

Допустим, что ансамбль после п шагов имеет вид /п = £ 52^=1Зj{yL): т.е. фактически является усреденением п базовых моделей. Необходимо строить модели д^, ] = п 1,п 2,... последовательно, минимизируя эмпирический риск на обучающей выборке 8т так, чтобы ансамбли /п+1. /п+2, - • • сохранили структуру усреднения.

Предложенный способ построения ансамбля позволяет добиться отрицательной скоррелированности каждой следующей базовой модели с предыдущими, что, как известно, улучшает обобщающую способность, при этом веса {а;}"=1 в ансамбле не требуют подстройки, поскольку фиксируются равными

В разделе 2-4 приводятся основные теоретические результаты, полученные для метода БегБуст.

В определенных предположениях удается доказать, что ошибка егр1/(/п) аппроксимации метода БегБуст, реализующего описанную выше идею, сходится к нулю.

Обозначим через

• <9 — некоторое подмножество функционального гильбертова пространства Н с функциональной нормой || • ||;

• co(G) ={g : g = °чди a. > 0. a< = 1. g¡ G G, n > 1} — выпуклую оболочку множества G\

• co(G) — замыкание выпуклой оболочки co(G). Положим

£к = érSk (дк) - inf érSk (д),к = 1, 2,..., g<EG

£fclax = гпахк=1,..,п{£к}■ В дальнейшем будут использоваться следующие предположения

• Ai. Подмножество G имеет вид

G = {а ф(-, 0)| |а| < В, в € ©} С L2(X,P), (2)

где а 6 R1, в) — сигмоидальная функция активации, множество значений параметров в 6 0 С Rd+1 (0 — произвольное компактное множество), 0 < В < оо — заданная константа.

• Ат. Неизвестная функция / принадлежит co(G).

• Аз. Для некоторого е > 0 при к > 1 выполнено, что

£к < £. (3)

Пусть Д = В2 — -—Y^íLx (у(,))2 > 0. При введенных предположениях Ai и А2 возможно доказать следующую лемму.

Лемма 1. Для любой f 6 co{G), фиксированной выборки Sm, h Е co(G) и а £ [0,1] справедливо, что

miners^ {ah 4- (1 — 0)17) < a2ersm (h) + (1 — a)2 ( max ||(7||x — e>sm(0) ) .

geG \geG m J

Следствие. Для любой f 6 cd(G), фиксированной выборки Sm, h G co(G) и a S [0, lj справедливо, что

rninerSm (a/i + (1 - a)g) < a2érSm (h) + (1 - а)2Д.

g£G

На основании приведенной леммы при выполнении предположений Ai и Á.2 может быть доказана следующая теорема.

Теорема 1. Для фиксированной выборки Sm и любого к = 1,2,... выполнено, что

Д +

ërSm (Л) < а + *к ,

Следствие. Если на каждом шаге алгоритма БегБуст при построении базового аппроксиматора дь достигается минимум ошибки erg^ (gk)> к = 1,2,..., т.е. еь = 0, то ошибка ers,„ (/я) убывает как

Данная теорема дает оценку сверху ошибки приближения построенной модели для произвольной выборки, следующая теорема. Проведенные эксперименты показывают, что теорема выполняется на практике (рис. 1).

Рис. 1. Зависимость ошибок на обучающей (черная сплошная линия) и проверочной (серая штриховая линия) выборках от числа итераций для обучающей выборки объема т = 100 (слева) и т = 1000 (справа), функция Вгашп. Для сравнения приведена кривая £ (черная пунктирная линия). СКО — средне-квадратичная ошибка.

Используя предыдущую теорему, также можно получить ограничение сверху на обобщающую способность:

Теорема 2. Пусть выполняются предположения Ах, А2 и Аз, тогда для любой / е со(0), для всех 7 € (0,1) и р > 0, если алгоритм БегБуст применяется к выборке вт размера по крайней мере тп(р, 7) = ^ (1п А + % 1п , где Сх = 2С2 = 5 • 214(<г+3)В4 и С3 =

то с вероятностью не менее 1 — 7 через п = шагов алгорит-

ма БегБуст ошибка аппроксимации ансамбля /„ будет удовлетворять неравенству егр(/п) < р.

В разделе 2.5 приводится сравнение предложенного и представленных в литературе методов построения ансамблей на наборе искусственных за-

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

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

По этой причине автором были предприняты попытки улучшить качество оценок проекции, результатом которых стало создание алгоритма VEGA (Variable Extraction via Gradient Approximation, Выделение Переменных Основанное на Аппроксимации Градиентов), который позволяет находить центральное среднее подпространство регрессии точнее, чем найденные автором в литературе подходы.

В разделе 3.1 приводится детальное описание алгоритма VEGA.

Пусть аппроксимируемая функция имеет следующую структуру

где В искомая матрица, задающая подпространство сниженной размерности, то есть, как и говорилось выше, функция / зависит только от проекции х на некоторое подпространство, заданное матрицей В.

Будем предполагать, что функция /(х) является реализацией некоторого гауссовского процесса9, тогда структуру типа (4) можно достаточно удобно описать, предположив, что ковариационная функциая гауссовского процесса имеет вид

9Rasmussen C.B., Williams C.K.I. Gaussian Processes for Machine Learning. MIT Press, 2006.

у = /(x) = Л(хВ),

(4)

fc(x, x') = ctq exp(—dist(x., x')),

(5)

где расстояние Махаланобиса

йиЛ{х, х') = (х - х')тА(х - х') = (х - х')ВЛВт(х - х')Т, (6)

В - ортогональная матрица в. х р, р < с/, Л — диагональная матрица размера р х р с элементами Ах > Аг > ... > Ар > 0 на диагонали. При такой параметризации матрица В осуществляет поворот осей координат, а диагональная .матрица Л регулирует ширину ядер вдоль новых повернутых осей.

Если матрица В фиксирована и известна, то аппроксимацию / можно искать в виде /(х) = /г(хВ), где к - апостериорное среднее значение гауссовского процесса к с функцией ковариации (5), в которой у расстояния Махаланобиса (6) А = Л, то есть нет поворота осей координат. В этом случае достаточно оценить только р гиперпараметров ковариационной функции, т.е. элементы матрицы Л.

Если же матрица Л фиксирована и известна, то матрицу В можно оценить из следующих соображений.

ПустьМ{ = 3,1 = 1,...,сг},к(х) = »= 1,...,т},

^ = ^ИХ=Х(0' К° = {*(*(0.*Ш), ьз = 1,- • -М-

Пусть Г = {Гь...,Гт} = Г - неиз-

вестные истинные значения градиентов / в точках выборки Э,,,. Тогда выполнены следующие

Утверждение 1. Матрица градиентов /(х) в точках выборки Зт имеет апостериорное распределение

где Г г = ^ % = Mi- ^ К^1 Л,

Утверждение 2. Пусть данные Бт порождены гауссовским процессом с ковариационной функцией (о) и расстоянием Махаланобиса (6) с параметрами А = ВТЛВ, тогда

• Е,™ 1 £ТГг = А СТСг) А,

где Сг = Y^K01k(x^') (еТх^ — Хт); е — вектор из единиц размерности й.

• XX1 ^ = А - АЕ;А, где % = (етх<<> - Хт)Т к(х<'>)тКо ^(хМ) (етХ('> - Хт)

. Г = Е^^ГГГ^Э™) = ЕИ^ГГ^ + М^ЛГКо1^), где Е -среднее значение по апостериорному распределению рассматриваемого гауссовского процесса.

Следствие. Пусть данные порождены гауссовским процессом с ковариационной функцией (5) и расстоянием Махаланобиса (6) с параметрами А = ВТЛВ, тогда Е лежит в подпространстве, натянутом на столбцы матрицы В.

Кроме того эксперименты показывают, что качество итоговой оценки матрица В может быть заметно улучшено через многократное итеративное вычисление В, т.е. когда па (г — 1)-ом шаге построена оценка В,_х, то можно оценить В, как собственные вектора матрицы Е, которая строится по новой выборке ¡5т, содержащей преобразованные входные вектора х = хВ,;_1. В таком случае итоговая оценка матрицы В записывается как В = П;В;.

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

В разделе 3.2 приводится обзор методов оценки размерности центрального среднего подпространства.

В результате, как наиболее удобный алгороитм оценки размерности предлагается использовать отбор по собственным числам матрицы кова-риации градиентов Е, в котором пороговое значение оценивается либо с помощью бутстрепа, либо с помощью метода складного ножа (или аналогичного метода оценки стабильности собственных подпространств).

При прямом вычислении собственных чисел на каждой итерации метода складного ножа пришлось бы заново обращать матрицу ковариации (что имеет сложножность О (т:!) и является довольно затратной операцией для больших выборок). Однако, можно сэкономить время и сделать обращение не для каждой итерации, а лишь единожды, используя

Утверждение 3. Пусть данные порождены гауссовским процессом с ковариационной функцией (5) и расстоянием Махалапобиса (6) с параметрами А = ВТЛВ, тогда апостериорное среднее и матрицу ковариации градиента при условии, что известна только выборка = которая получается из 8т выкидыванием г-го наблю-

дения, можно записать следующим образом

Г^ = У£Кк(х<*>) (етх^ - Хт) А, Е^ =аоА + А (еТх^ - Х,П)Т к(х«)тКк(х«) (етх<<> - Хт) А, где К = Кц 1 + "Л;, ' , здесь (Кд . - г-я строка матрицы, а мат-

v 0 )и _ 1

рица К получается из матрицы К занулением 1-ой строки и 1-го столбца.

В разделе 3.3 проводится обширное экспериментальное сравнение с другими методами эффективного снижения размерности из литературы. Демонстрируется, что метод позволяет обеспечить инвариантность качества аппроксимации к повороту координатных осей.

Кроме того, для иллюстрации описывается решение задача аппроксимации энергозатрат вертолета от параметров маневра, включающих 51 параметр: масса, моменты вращения, углы, высота и т.п. Эффективная размерность данных, оцененная с помощью статистического теста, составила от 15. Сокращение числа параметров в ~ 4 раза за счет выделения наиболее значимых направлений с помощью предложенного алгоритма позволило существенно уменьшить сложность задачи и при этом улучшить качество аппроксимации.

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

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

Рассматриваются следующие распространенные модели неоднородности:

1) данные порождены смесью нормальных распределений,

2) данные описываются набором областей, разделенных линейными гиперплоскостями.

У каждого элемента смеси или области предполагается свой вид зависимости.

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

В разделе 4-1 приводится обзор методов построения смесей экспертов.

В разделе 4-2 рассматривается ситуация, когда данные заполняют пространство неравномерно, образуя несвязные облака точек.

В этом случае удобно и просто предположить, что данные были сгене-рированны смесью нормальных распределений. Предполагается, что точки (х, у) 6 порождены в соответствии с распределением

лг,

Ьа\у(х, у) = ^ &к), (7)

к=1

где Цк и <Эк — среднее и матрица ковариации к-го нормального распределения смеси для выборки 8т. Соответственно, если рассматривать только входной вектор х, то

ЛГ*

Ьа\у(х) = &к.х),

к=1

где и ®к,х — подвектор средних значений вектора Цк и подматрица ковариаций матрицы соответственно, задающие безусловное распределение вектора входов х € X.

Параметры гауссовской смеси задают разбиение X = и^^Хд... Действительно, определим расстояние в метрике Махалонобиса от центра к-го кластера до точки х в соответствии с формулой

<4(х) = (х - ¿а.)3:)т (©м-) (х - цк,х),

тогда множество Х/ь = {х е X : с4(х) < х2П1 (р)} ; где (р) является а\-квантилью распределения х'2 с Р степенями свободы. Локальные аппрок-симационные модели д^ € С? для каждой подобласти Хд, строятся по под-выборкам Б*"' = {(х, у) е Б,,, : х 6 X*}, к = 1,..., ЛГХ.

Степень вхождения точки х в к-й кластер можно определить согласно формуле

2\ \ xl,(r)-xlM)

где Ха2(р) и Xni(р) являются си2 и а\ квантилями распределения х2 с р степенями свободы соответственно (в экспериментах брались значения а2 = 99% и щ = 97%).

Таким образом классификатор, определяющий степень принадлежности точки х к к-му кластеру, может строиться в соответствии с формулой

-/Fi \ w(kfx)

№{fc|x) = E^)- (9)

Эксперименты показывают, что такой подход оказывается надежнее чем подход, где в качестве весов (9) используются апостериорные вероятности ¿'(fcjx) = P(jfc|x) точки х принадлежать соответствующим кластерам10.

В разделе 4-3 рассматривается случай, когда функция / имеет разрывы вдоль линейных гиперплоскостей ("линейные" структура разрывов).

Один из способов моделировать такую функцию с разрывом в точке в вдоль направления v состоит в том, чтобы описать разрыв функцией-ступенькой <т ^(х — в)т v^ (такой, например, как функция хевисайда или логистическая функция), а по обе стороны от него задать гладкие базовые модели gi (х) и до (х), определив итоговую модель как

Дх) = (7 ((х - в)Т v) 91 (х) + (l - а ((х - в)т v)) д2 (х), (10)

или

/(x) = Ef=lWl(x)5i(x), (11)

10 Bettebghor D., Bartoli N., Grihon S., Morlier J., Samuelides M. Surrogate modeling approximation using a mixture of experts baaed on EM joint estimation, Structural and Multidisciplinary Optimization, pages 1-17, SOU, Springer.

где 1 = 2, (х) = 1 и и, (х) — вес г-й модели в точке х. В этом

случае по одну сторону от разрыва функция будет вести себя как д\, а по другую как </2> "резкость" перехода будет контролироваться ||у||.

Для описания разрывов, имеющих более сложную, чем линейная, структуру, можно, сохранив форму модели (11), усложнить ее следующим образом. Поставим в соответствие модели / бинарное дерево, на листах которого находятся базовые модели д,,1 = 1,...,/, а каждая ветвь, выходящая из вершины </, имеет в точке х вес = а ((х — б1./) V./), если это левая ветвь, или ф^Ы) = (1 — сг ((х — #,/) V.;)), если правая. При вычислении /(х) вес съ',(х) может быть найден как произведение весов I = 1,2 по всем ветвям, ведущим от г-го листа к корню дерева.

Экспериментально показывается, что предложенная форма весов о>,(х) позволяет моделировать функции с разрывами, имеющими более сложную, чем линейная, структуру.

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

Качество базовой модели на г-м листе будем оценивать как

т 2

^еа/ = Е(у(П)-л(х(П))) ^(Х<П))' (12)

п=1

где и>'п(ц(п)) - произведение весов <^М'(х'п') по всем ветвям, ведущим от г-го листа к корню дерева.

Качество подбора параметров вJ, VJ на ветвях выходящих из вершины 3 при фиксированных базовых моделях д.]1 и г/./2 будем оценивать как

тп

71=1

(х(")))2^(х(">), (13)

где ¿¡^(х^) - произведение весов ф\М\у.^) по всем ветвям, ведущим от 7-й вершины к корню дерева (в корне дерева принимается, что (х'"') = !)•

Построение дерева производится итеративно и заключается в том, что на каждой итерации выбирается лист с наибольшим значением Еиа/ и из

него пускаются две ветви с новыми листьями (на первой итерации вместо листа с наибольшим Etea.f берется корень дерева).

Нахождение параметров vj и 0j весов ветвей выходящих из вершины J и соответствующих базовых моделей д,;1 и g,i2 на листах производится следующим образом:

1) v./ и 6j инициализируется некоторым начальным значением,

2) для текущих значений vj и и 9j через минимизацию Ef¿aj и E¡^aj находятся g.¡l и g.¡2,

3) для найденных gjl и g,j.2 через минимизацию E¿Krtex подбираются параметры vj и 9j

4) шаги 2 и 3 повторяются до сходимости оценок.

Проводится экспериментальное сравнение различных методов подбора параметров vj , Oj и показывается, что приведенная выше методика обеспечивает наилучшее качество построения f в смысле точности приближения /.

Отличие рассмотренной процедуры от встречающихся в литературе подобных подходов11 состоит в том, что вместо того, чтобы на каждой вершине проводить оптимизацию только по точкам, лежащих по одну сторону от гиперплоскости, заданной параметрами v и 9 на вершине выше, вводятся веса и используются все точки выборки. В экспериментах показывается, что введение гладких весов значительно уменьшает артефакты на разрывах и в целом повышает точность построенных моделей.

В случае, если в качестве используются линейные модели, то для функционала E„ertcx на каждом шаге оптимизации 3) можно выписать выражение для ошибки скользящего контроля (то есть то, ка-

кое значение Eflcrti:T было бы в точке х'"' обучающей выборки Sm при фиксированных vj, в j и ¿r'(x), если бы мы строили базовые модели gj'1 и по обучающей выборке с исключенным п-м наблюдением).

Доказывается, что выполнено

11 с. Hametner and S. Jakubek, NeurO'fuzzy modelling using a logistic discriminant tree, American Control Conference, 2007. ACC 07, pp. 86Í-869.

Утверждение 4. Пусть Н/ = (Х^С^Х,,,) \ где X = [Хет], С1> =

йгад (х'1') ,..., (х'т') ^. Тогда ошибка скользящего контроля для функционала Е„еНсх может быть записана как

Е,,г (ех(1оо) = ¿^ 2-, Ф\ >)~-.(П, , и .. > • (14)

1 -0Г(х(т°) (х(п)) Н/х(»)/

здесь х = (х, 1), gJi — линейные модели, построенные по всей выборке Хт минимизацией

Использование вместо Е^ет(вх при нахождении весов на но-

вых ветвях может уменьшить переобучение модели.

На рисунке 2 показан пример работы метода при аппроксимации разрывной функции, в качестве базовых моделей использовались линейные модели.

Истинная функция Аппроксимация

Рис. 2. Настоящая функция (слева), аппроксимация смесью линейных экспертов (справа)

В разделе 4-4 описывается сравнение предложенных методов с методами из литературы. Приводится пример успешного применения предложенной методологии к задаче построения суррогатных моделей ограничений для оптимизации веса обшивки корпуса самолета.

В заключении сформулированы основные результаты диссертационной работы:

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

в пространстве дизайна.

2. В случае, если базовая модель слишком проста для воспроизведения искомой зависимости, разработанный метод построения ансамблей базовых моделей БегБуст позволяет улучшить качество аппроксимации. При выполненных предположениях на зависимость для алгоритма БегБуст также получена верхняя граница ошибки обобщающей способности.

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

Список публикаций

1) Бурнаев Е.В., Ерофеев П.Д., Приходько П.В. Выделение главных напрвлений в задаче аппроксимации на основе гауссовских процессов // Труды МФТИ. 2013 Т. 5. No. 3. С. 24-35.

2) Бурнаев Е.В., Приходько П.В. Об одной методике построения ансамблей регрессионных моделей // Автоматика и телемеханика. 2013. Т. 10, С. 36-54.

3) S. Grihon, Е. Burnaev, P. Prikhodkoet al. Surrogate Modeling of Stability Constraints for Optimization of Composite Structures // Surrogate-Based Modeling and Optimization Engineering applicaitons / Ed. by S. Koziel, L. Leifsson. 2012. P. 359-391.

4) Burnaev E., Prikhodko P., Struzik A. Surrogate models for helicopter

loads problems // Proceedings of 5th European Conference for Aerospace Sciences, 2013, 11 P.

5) Бурнаев E.B., Приходько П.В. Эффективное снижение размерности на основе гауссовских процессов / / Сборник докладов конференций ИОИ-9. 2012. С. 188-192.

6) Grihon S., Alestra S., Burnaev E., Prikhodko P. Surrogate Modelling of Bucking Analysis of approximation based on linear Expansions in parametric dictionaries // Proceedings of 1st International Conference on Composite Dynamics, Arch anon, France, 2012.

7) Grihon S., Alestra S., Betebghor D., Burnaev E., Prikhodko P. Comparison of different techniques for surrogate modeling of stability constraints for composite structures // Proceedings of 1st International Conference on Composite Dynamics, Archanon, France, 2012.

8) Бурнаев E.B., Приходько П.В. Теоретические свойства процедуры построения регрессионного ансамбля на основе беггинга и бустинга // Тр. конф. Информационные Технологии и Системы. 2011. С. 438443.

9) Ерофеев П.Д., Приходько П.В. Эффективное снижение размерности на основе аппроксимации гауссовскими процессами и его применение при оптимизации крыла самолета // Труды 54-й научн. конф. МФТИ. Долгопрудный, ФУПМ, 2011. С. 82-83.

10) Burnaev. E.V., Belyaev M.G., Prikhodko P.V. Approximation of

multidimensional dependency based on an expansion in the parametric functions from dictionary // Proc. of 9th International Conference "Computer Data Analysis and Modeling: Complex Stochastic Data and Systems". Vol. 2. 2010. pp. 223-226.

Подписано в печать 25.10 13 Тираж 100 экз. Отпечатано: отдел оперативной полиграфии МАРХИ 107031, г. Москва, ул. Рождественка, 11/4, корп.З Тел.: 8(495) 621-15-66

На правах рукописи

Федеральное государственное бюджетное учреждение науки Институт Проблем Передачи Информации им. А.А.Харкевича

04201450220

Приходько Павел Викторович

Применение методов агрегации экспертов и регрессии на основе гауссовских процессов для построения

метамоделей

Специальность: 05.13.17 — «теоретические основы информатики»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель: кандидат физико-математических наук.

доцент, Бурнаев Е.В.

Москва - 2013

Оглавление

Введение 7

Основные положения ..................................................12

Научная новизна........................................................13

Теоретическая и практическая значимость..........................14

Апробация работы......................................................14

Публикации..............................................................16

1 Задача восстановления зависимости и основные определения 19

1.1 Базовый аппроксиматор..........................................20

1.1.1 Искуственные Нейронные Сети (ИНС)..................21

1.1.2 Регрессия на основе гауссовских процессов............22

1.2 Представление экспериментальных

результатов........................................................26

1.2.1 Кривые Долана-Мора....................................26

2 Слишком простой класс базовых моделей 28

2.1 Постановка задачи построения ансамбля регрессионных моделей ................................................................28

2.2 Основные подходы к построению

ансамблей..........................................................30

2.3 Процедура БегБуст для построения

ансамблей аппроксиматоров......................................35

2.3.1 Необходимые предположения............................36

2.3.2 Алгоритм БегБуст........................................38

2.3.3 Оценка скорости сходимости ............................39

2.3.4 Проверка справедливости теоретических предположений ..........................................................42

2.3.5 Сравнение теоретических свойств алгоритмов SquareLev.R и БегБуст..................................43

2.4 Заключение по главе..............................................45

3 Избыточность в признаках 46

3.1 Выделение значимых направлений с помощью аппроксимации градиента......................................................46

3.2 Эффективное снижение размерности на основе гауссовских процессов..........................................................50

3.2.1 Задача эффективного снижения размерности..........51

3.2.2 Сравнение точности методов эффективного снижения размерности................................................52

3.2.3 Оценка эффективной размерности данных............53

3.2.4 Эксперименты по оценке размерности..................56

3.3 Заключение по главе..............................................57

4 Неоднородность в данных 59

4.1 Обзор методов построения смесей

экспертов..........................................................62

4.1.1 Одновременное параллельное построение

экспертов..................................................63

4.1.2 Последовательное построение экспертов................66

4.2 Предложенные процедуры........................................68

4.2.1 Неравномерная выборка..................................68

4.2.2 Приближение разрывных функций......................73

4.3 Заключение по главе..............................................78

Заключение 80

Литература 81

А Приложение 87

А.1 Доказательства....................................................87

А. 1.1 Доказательство Леммы 1 ................................87

А. 1.2 Доказательство Теоремы 2 ..............................89

А. 1.3 Доказательство Теоремы 3 ..............................90

А. 1.4 Доказательство Утверждения 1..........................92

А.1.5 Доказательство Утверждения 2..........................93

А.1.6 Доказательство Утверждения 3..........................94

А.1.7 Доказательство Утверждения 4..........................95

А.2 Экспериментальные результаты ................................96

А.2.1 Экспериментальные результаты по методу Бег Б уст . 96

А.2.2 Экспериментальные результаты по методу VEGA . . 100

А.2.3 Экспериментальные результаты по смесям экспертов 109

А.2.4 Оптимизация веса обшивки корпуса самолета.....110

Список иллюстраций 118

Список таблиц

Список обозначений

В работе используются следующие обозначения:

• X — матрица размера m х d,

• х^ — вектор, i-я строка матрицы X или i-e наблюдение, i = 1,... ,т,

• х^ — j-й компонен'т вектора х(1\ или г j-й элемент матрицы X, j = 1

• [X, 1] — расширенная матрица X, к которой добавлен столбец из единиц размера rn х 1,

• для простоты везде далее предполагается, что вектор выходов у^ одномерный, поэтому вместо у(г) будем писать у(1\

• если номер наблюдения не важен для изложения, а речь идет только о некотором входе и соответствующем ему выходе, то будут использоваться сокращенные обозначения х и у соответственно.

Введение

Последнее десятилетие с развитием вычислительной техники при проектировании инженерных объектов возник спрос на построение метамоде-лей (суррогатных моделей) [23,35] для анализа результатов экспериментов или сложных вычислительных кодов.

Спрос обусловлен следующей проблемой: инженеру требуется оптимизировать или исследовать поведение некоторой зависимости, являющейся функцией от ряда параметров1, однако, вычисление значения этой функции для новых значений параметров (в новой точке) затратно в смысле вычислительных ресурсов, времени или даже невозможно. Зачастую такое происходит, если для вычисления значения функции в новой точке требуется проводить натурный эксперимент или использовать "тяжелый" вычислительный код (например, обсчет модели конечных элементов даже на современных вычислительных мощностях может занимать несколько дней).

Для случаев, когда инженеру достаточно получить лишь приближенное решение задачи, одним из популярных подходов, позволяющих проанализировать зависимость, стало построение по имеющимся данным математической модели (метамодели), которая, насколько это вообще возможно, имитирует поведение рассматриваемой зависимости, однако, при этом может быть очень быстро вычислена в произвольных точках. При таком под-

1 Также в дальнейшем в том же смысле употребляются термины "признаки" и "входы".

ходе построенная метамодель полностью заменяет собой (аппроксимирует) исходную зависимость во всех последующих расчетах (по этой причине ме-тамодели также иногда называют суррогатными моделями). Качество ме-тамодели обычно определяется тем, насколько она хорошо воспроизводит поведение исходной зависимости в смысле некоторой заданной метрики, например, среднеквадратичной разности между предсказаниями метамодели и истинными значениями зависимости на некоторой репрезентативной выборке данных.

Довольно часто на практике исходная зависимость существенно нелинейна, характер ее поведения неизвестен, а в наличии имеется только выборка пар "параметры"—"значение зависимости". В этом случае для построения метамоделей как правило применяются универсальные методы построения регрессионных моделей из статистики и машинного обучения, такие как: искуственные нейронные сети |12| или регрессия на основе гаус-совских процессов (кригинг) [411. Соответствующие базовые метамодели (далее будем называть их также просто моделями), построенные с помощью этих методов, не предполагают априори какой-то специальный вид аппроксимируемой зависимости, и их параметры могут быть настроены так, чтобы приблизить довольно широкий класс функций.

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

В работе рассматриваются такие надстройки для нескольких специальных случаев:

Недостаточная сложность модели. В ряде работ |45| показывает-

ся, что в случае "простой" базовой модели, точность аппроксимации может быть существенно повышена, если итоговая модель определенным образом строится как линейная комбинация (ансамбль) некоторого количества базовых моделей.

Кроме того, в случае использования искуственных нейронных сетей (ИНС) в качестве базовой модели на практике не всегда возможно заранее оценить сложность зависимости и соответственно подобрать адекватную ей сложность (определяемую количеством узлов) ИНС, что приводит к необходимости итеративного выбора структуры модели в соответствии с некоторым дополнительным критерием. В этом смысле построение ансамблей может быть альтернативой прямому увеличению сложности ИНС.

Случай неоднородной выборки. Методы построения регрессионных моделей обычно неявно предполагают, что в выборке данных значения входов равномерно заполняют пространство дизайна, а сама функция ведет себя достаточно однородно в том смысле, что она не содержит разрывы или области с качественно разным поведением (то есть для выбранного типа базовой модели можно задать такой набор параметров, что модель будет хорошо приближать рассматриваемую зависимость на всей области определения). Нарушение этого условия может приводить к проблемам при построении моделей, таким как низкая точность в определенных областях пространства дизайна, вырождение модели и т.п.

Для описания неоднородного поведения функции в работе рассматриваются следующие распространенные модели неоднородности:

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

2 Имеется в виду, что. если для элемента смеси построить базовую модель только но тем дай-

2. данные описываются набором областей, разделенных линейными гиперплоскостями, причем в каждой области имеется свой вид зависимости.

Первая модель неоднородности позволяет эффективно описывать случаи, в которых обучающая выборка неравномерно заполняет пространство признаков (пространство дизайна); вторая модель подходит для описания задач, в которых аппроксимируемая зависимость имеет разрывы.

Избыточность в признаках. Набор признаков обычно может быть избыточен в одном из следующих смыслов:

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

2. Функция слабо зависит или не зависит вовсе от некоторых исходных признаков,

3. Функция зависит только от проекции входов на некоторое подпространство.

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

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

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

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

В литературе присутствует множество процедур [47], позволяющих находить проекцию входов на некоторое подпространство. Однако при использовании таких процедур как правило необходимо заранее указывать размерность сжатия, а также строить ядерные оценки зависимости (требующие подбора параметров, например, посредством кросс-проверки), которые хорошо работают лишь в случае малых размерностей. Указанные особенности делают эти методы малоприменимыми на практике.

Работа имеет следующую структуру

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

• В главе 2 рассматривается случай, если базовая модель слишком проста для того, чтобы описать неизвестную зависимость, приводится описание специального разработанного алгоритма построения ансамблей базовых моделей.

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

• И, наконец, в главе 4 обсуждается ситуация, когда выборка неоднородна и/или аппроксимируемая зависимость имеет разрывы.

• Каждая из глав 2-4 устроена следующим образом:

— дается формулировка решаемой проблемы,

— проводится обзор существующих в литературе решений,

— описывается авторская процедура,

— проводится теоретический анализ и экспериментальное сравнение методов.

• В Заключении собраны основные выводы, полученные в работе.

• В Приложение вынесены доказательства теорем и утверждений, а также результаты некоторых экспериментов.

Основные положения

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

На защиту выносятся следующие положения:

1. Метод VEGA (Variable Extraction via Gradient Approximation) нахождения подпространства эффективной размерности для заданной функции по выборке. Вычислительно эффективный способ оценки матрицы ковариаций градиентов зависимости.

2. Метод БегБуст построения ансамблей базовых метам одел ей.

3. Верхняя граница ошибки обобщающей способности метода БегБуст.

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

Научная новизна

Научная новизна результатов, полученных в

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

• Разработана процедура построения метамодели в случае, если функция зависит лишь от проекции признаков на некоторое неизвестное линейное подпространство, что позволяет существенно улучшить качество модели при выполнении этого предположения, а также дает-возможность линейно снизить размерность данных. Кроме того, качество построенной модели становится устойчивым к повороту координатных осей пространства дизайна. Предлагается метод оценки размерности линейного подпространства, а также способ нахождения базиса в этом подпространстве.

• Разработана процедура БегБуст построения ансамблей базовых метамоделей. Получена верхняя граница на ошибку обобщающей способности процедуры.

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

Теоретическая и практическая значимость

Описанные в работе методы широко применяются для решения прикладных задач аэрокосмической отрасли в компании DATADVANCE. Кроме того, для метода построения ансамблей БегБуст получена верхняя граница на ошибку обобщающей способности. Развитые при этом теоретические подходы можно использовать при анализе других алгоритмов построения ансамблей.

Апробация работы

Результаты работы докладывались и обсуждались на следующих российских и международных конференциях:

• "Интеллектуализация обработки информации"(2012, Будва, Черногория):

• 1st International Conference on Composites Structures Dynamics (2012, Аркашон, Франция). Было сделано два доклада, один из которых пленарный.

• Uncertainty in Computer Models 2012 Conference (2012, Шеффилд, Англия)

• "Математические методы распознавания образов"(2011, Петрозаводск, Россия);

• "Информационные Технологии и Системы"(2009, Бекасово, Россия; 2010, 2011 Геленджик, Россия; 2012, Петрозаводск, Россия);

• Third International Workshop on Surrogate Modelling and Space Mapping For Engineering Optimization (2012, Рейкьявик, Исландия);

• 9th International Conference "Computer Data Analysis and Modeling: Complex Stochastic Data and Systems" (2010, Минск, Белоруссия)

• 52-я, 53-я, 54-я научные конференции Московского физико-технического института (2009-2012, Долгопрудный, Россия)

• Sixth conference "Mathematical Methods in Reliability"(2009, Москва, Россия)

Также полученные в работе результаты обсуждались на научных семинарах лаборатории структурных методов анализа данных в предсказательном моделировании МФТИ (2012, 2013), а также на семинаре сектора 8.1 Института Проблем Передачи Информации им А.А.Харкевича.

Описанные в работе методы были реализованы в программном продукте MACROS, разработанном компанией DATADVANCE. и используются при решении практических задач такими компаниями как Airbus. Eurocopter и др. В диссертации приводится несколько примеров приклад-

ных задач, в которых применение предложенных процедур позволило существенно улучшить качество соответствующих метамоделей.

Публикации

По теме диссертации опубликовано 11 печатных работ, из них 4 работы - статьи в ведущих рецензируемых научных журналах, 7 работ в трудах ведущих российских и международных конференций.

1. Бурнаев Е.В., Приходько П.В. Методология построения суррогатных моделей для аппроксимации пространственно неоднородных функций // Труды МФТИ. Т. 5, No. 4. 2013. С. 122-132.

2. Бурнаев Е.В., Ерофеев П.Д., Приходько П.В. Выделение главных на-првлений