Книги по разным темам Pages:     | 1 | 2 | РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР СООБЩЕНИЯ ПО ПРИКЛАДНОЙ МАТЕМАТИКЕ В.В. СТРИЖОВ, В.В. ШАКИН ВЫБОР ОПТИМАЛЬНЫХ МОДЕЛЕЙ В ЗАДАЧАХ ВОССТАНОВЛЕНИЯ РЕГРЕССИИ Предварительная версия, рукопись ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР РАН МОСКВА, 2004 УДК 519.6 Ответственный редактор Описана процедура выбора оптимальной регрессионной модели фиксированной или произвольной структуры из множества синтезируемых моделей. Модели строятся в виде суперпозиции гладких функций из заданного множества с использованием алгоритов генетической оптимизации. Для нахождения параметров моделей используются методы нелинейной оптимизации. Для иллюстрации приведены несложные задачи, подкрепленные результатами измерений.

Работа поддержана грантом РФФИ 04-01-00401-а УРаспознавание и прогнозирование экстремальных ситуаций в сложных системах по многомерным временным рядам наблюденийФ.

Рецензенты:

Научное издание й Вычислительный центр им. А. А. Дородницына РАН, 2004 Введение Широкое практическое применение методов нелинейной оптимизации Левенберга-Марквардта [1] в регрессионном анализе подготовило базу для создания алгоритмов синтеза регрессионных моделей. Алгоритм, описанный ниже, построен на основе метода группового учета аргументов Ивахненко [2], и Байесовского подхода в нейронных сетях с анализом весовых коэффициентов нейронов, описанного статье Бишопа [3]. Предлагаемый алгоритм использует сильные стороны указанных методов, однако, не совершенно свободен от своих недостатков. Такое исследование производится нами впервые и поэтому подробное сравнение с ранее предложенными алгоритмами, многие из которых опубликованы на сайте [4], пока не завершено. Наиболее близкой публикацией является [5].

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

Первый раздел посвящен синтезу параметрической модели как композиции гладких функций одного или нескольких аргументов. Во втором разделе описан способ построения комбинированной модели с применением непараметрических преобразований значений свободной переменной. Поставим задачу нахождения регрессионной модели нескольких свободных переменных следующим образом. Пусть заданы обучающая выборка множество X = {x1,..., xn|x Rm} значений свободных переменных, множество Y = {y1,..., yn|y R} соответствующих им значений зависимой переменной и тестовая выборка X = {x,...x }, Y = {y1,..., yn }. Объединения множеств 1 n X X и Y Y мы будем рассматривать как результат измерений при проведении некоторого эксперимента, мо дель которого неизвестна. При разбиении экспериментальной выборки на обучающую и тестовую считаем, что пара (xi, yi) с вероятностью попадает в обучающую выборку или с вероятностью 1 - попадает в тестовую.

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

Также задано множество G = {g|g : R... R - R} гладких функций. Первый аргумент функции g вектор параметров, последующие переменные из множества действительных чисел, g = g(, , ,..., ). Функция g может иметь и только один аргумент.

Требуется найти композицию f = f(b, x) = g1 g2... qr. (1) Модель f имеет вектор параметров b, состоящий из присоединенных векторов-параметров функций g, то есть, b =...

.

1....., где. знак присоединения векторов. Индекс.2.

функции g обозначает номер вхождения в композицию (1).

Модель (1) должна отвечать условию (2):

min (y, f(b, x)), (2) f где b = arg min (y, f(b, x)).

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

Для нахождения вектора параметров регрессионной модели мы использовали распространенные методы нелинейной оптимизации с ограничениями: метод ЛевенбергаМарквардта [1] и метод доверительных областей [6, 7].

Метод Левенберга-Марквардта модификация метода Гаусса-Ньютона. Он заключается в нахождении минимума суммы квадратов нелинейных функций n F (x) = (di(x))2, где di = yi - f(xi).

i=Пусть J(x) якобиан функции di(x). Тогда направление поиска задано вектором s решением системы уравнений (JT J + I)s = -JT d, где вектор содержит неотрицательные числа, I единичная матрица. Для некоторого значения, соответствующего, вектор s является решением задачи с ограничениями ||Js + d||2, при условии ||s||2.

Метод доверительных областей в настоящее время является одним из самых результативных при решении прикладных задач оптимизации. Его основной идеей является аппроксимация минимизируемой функции некоторой несложной функцией, которая адекватно описывает в окрестности (доверительной области) Nb точки b. Пробный шаг s вычисляется в области Nb как s = arg min{(s)|s Nb}.

Вектор начального приближения b заменяется вектором b + s при выполнении f(b + s) < f(b). В противном случае область N изменяется, и пробный шаг повторяется.

Квадратичная аппроксимация определена первыми двумя членами ряда Тейлора, приближающего в точке b;

область N сферической формы. Пробный шаг s = arg min{ sT Hs + sT g| ||Ds||2 }, где g градиент в точке b, H гессиан, D диагональ1 ная матрица и - = 0.

||s||Вторая подзадача нахождение наилучшей регрессионной модели f решается с использованием генетических оптимизационных алгоритмов [8]. Модификация классического алгоритма заключается в следующем.

На каждой итерации существует N конкурирующих моделей. Модель представлена в виде дерева Ti, i = 1,..., N с нумерованными вершинами t. Каждая вершина задает поддерево {t}. Шаг итерации состоит в том, что kN пар деревьев однократно обмениваются поддеревьями, причем номера вершин получены случайно. Эта операция соответствует операции обмена хромосомами. Обмен считается успешным, если результирующее число вершин не превосходит заданное.

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

1. Синтез параметрической модели Регрессионная модель как композиция функций одного или нескольких аргументов имеет вид f = g1(b1, g2(b2, g3(b3,...,...),...), gr(br)). (3) Структура модели может быть как произвольной, так полностью или частично фиксированной. Сложностью модели f(b, x) мы считаем общее число параметров, необходимых для построения модели заданного качества, другими словами число компонент вектора параметров b. Это число ограничивается при решении прикладной задачи.

Модель с фиксированной структурой Ниже описывается пример построения регрессионной модели фиксированной структуры. Объектом моделирования является кривая одной свободной переменой, представленная набором измерений. На рис. 1 сплошной кривой показаны исходные данные. По оси абсцисс отложено значение свободной переменной, по оси ординат значение зави measure data regression 0.0.0.0.0.0.0.0.0.-0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 x Рис. 1. Исходная и восстановленная выборка симой переменной. Всего выборка содержит четыре тысячи отсчетов.

Алгоритм построения модели работает следующим образом (см. рис. 2).Даны обучающая и тестовая выборки, назначенное экспертами множество G гладких функций и набор моделей начального приближения. Эти модели могут назначаться экспертами исходя из характера прикладной проблемы либо генерируется случайным образом, как это сделано в данном примере. Множество функций G, из композиции которых построены регрессионные модели, приведено в таблице 1. Оно организовано в виде набора записей, с полями:

1) порядковый номер модели, 2) имя функции в реализации Matlab, y Рис. 2. Схема построения модели 3) начальное значение вектора параметров.

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

Зафиксируем структуру модели в виде линейной комбинации функций из нижней части таблицы 1, тогда модель f представима как сумма r f = w0 + gi.

i=Обозначим параметры i-й функции из таблицы 1 через вектор-строку i. Тогда вектор параметров этой модели будет b = [1,..., r]T, a модель f = g1(1, x) +... + gr(r, x).

Для выбора лучшей композиции используется генетический оптимизационный алгоритм. Он получает популяцию из N индивидов, каждый из которых соответствует своей модели. Индивид это запись, состоящая из r полей и содержащая список функций, включенных в модель. Каждое поле содержит номер функции из G. Популяция матрица из N строк и r столбцов. Количество строк и столбцов задаются перед запуском алгоритма. Алгоритм выполняет следующие шаги:

1) генерация начальной популяции (или получение ранее сгенерированной), № Функция Описание Параметры Функции двух переменных аргументов, y = g(, x1, x2) 1 plus y = x1 + x2 - 2 minus y = x1 - x2 - 3 times y = x1x2 - x4 divide y = - xФункции одного переменного аргумента, y = g(, x) 5 mult y = ax a 6 add y = x + a a 7 gaussian y = exp -(x-),, 8 linear y = ax + b a, b 9 parabolic y = ax2 + bx + c a, b, c 10 cubic y = ax3 + bx2 + cx + d a, b, c, d 11 logsig y = + a,,, a 1+exp(-(x-)) 12 tansig y = + a,,, a 1+exp(-2(x-)) Таблица 1. Множество G базовых функций 2) оценка качества каждого индивида популяции (вычисление ошибки ), 3) выбор индивидов для скрещивания (обмена значениями полей), 4) мутация полученных, в результате скрещивания, индивидов (случайное изменение номера функции), 5) оценка качества новых индивидов, 6) добавление новых индивидов в существующую популяцию, выбор N наилучших индивидов для дальнейших шагов, 7) переход к третьему шагу, до тех пор, пока не будет получена модель заданного качества, либо пока не будет выполнено заданное количество шагов.

Более подробно работа алгоритма описана в [9].

Настройка параметров и оценка качества модели на рис. 1 показана в виде двух нижних блоков. Для настройки параметров алгоритм нелинейной оптимизации принимает описание модели в виде индивида и декодирует его в модель. Начальные параметры алгоритма он получает из библиотеки моделей. Алгоритм возвращает значение ошибки и настроенные параметры. Для оценки качества модели был использован функционал среднеквадратичной ошибки n = (yi - f(xi))2. Время настройки параметров одi=ной модели в этом примере составляло около минуты, то есть искомая модель автоматически построена в приемлемое время (один-два дня) одним компьютером.

Для получения модели выборки использовались линейные комбинации из 2,..., 6 функций. В таблице 2 показаны Модель Число пара- (1) (2) (3) g(, ) метров ggctll 19 0.009 0.002 0.ggctt 16 0.013 0.003 0.ggplll 18 0.013 0.003 0.gggc 13 0.015 0.003 0.ggg 10 0.016 0.004 0.ggll 13 0.016 0.004 0.ggn 15 0.016 0.004 0.ggl 10 0.023 0.006 0.gg 7 0.024 0.007 0.gp 6 0.049 0.015 0.Легенда: g gaussian, n linear, p parabolic, c cubic, t tansig, l logsig Таблица 2. Оценка качества моделей различной сложности Рис. 3. Отношение сложности модели и ошибки регрессии несколько лучших полученных моделей. Первая колонка содержит названия включенных в модель функций; вторая колонка число параметров используемых при настройке модели, включая веса; третья, четвертая, пятая колонки среднюю относительную ошибку на всей выборке. Усреднение проводилось по ста реализациям кривой на всех указанных в таблице моделях () = (l).

l=Первая метрика среднеквадратичная относительная ошибка n 1 yi - f(xi) 1 =, n max(yi) i=вторая средняя относительная ошибка n 1 |yi - f(xi)| 2 =, n max(yi) i=третья максимальная относительная ошибка |yi - f(xi)| 3 = max.

i=1,...,n max(yi) Рисунок 3 показывает соотношение сложности и качества модели. По оси абсцисс отложено число параметров модели, а по оси ординат ее качество. Для дальнейшей работы экспертами была выбрана модель ggg (восстановленные регрессионные значения показаны на рис. 1 прерывистой кривой), как наиболее простая и доставляющая удовлетворительное, для данного эксперимента, качество.

Ее развернутый вид i (x - i)y = w0 + exp -.

2i 2i i=Модель со свободной структурой Для вышеописанных данных построены модели (3) со свободной структурой. Использованы функции одного и двух аргументов из таблицы 1.

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

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

По этой причине итерационный алгоритмов нелинейной оптимизации может не сойтись. Для решения этой проблемы № модели 1 2 Число пара- 20 16 метров + Описание g + + + l x g g g x x p + x x x g g g x g g + x x g g x x x x x № модели 4 5 Число пара- 16 16 метров + + + Описание g g + + l x x x g x x + + + g g g x + g c x x x g m t x x x x g x t x x Легедна: g gaussian, p parabolic, c cubic, l logsig, m muliply, t tansig, + plus, times, divide Таблица 3. Описание выбранных моделей используются алгоритмы стохастической оптимизации, в частности, оптимизация отжига. Для контроля качества работы производился неоднократный запуск алгоритма нелинейной оптимизации с небольшим случайным изменением значений параметров.

Pages:     | 1 | 2 |    Книги по разным темам