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

Федеральное государственное бюджетное учреждение науки Вычислительный центра им. A.A. Дородницына Российской академии наук

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

СОЛОГУБ РОМАН АРКАДЬЕВИЧ

АЛГОРИТМЫ ПОРОЖДЕНИЯ И ТРАНСФОРМАЦИИ МОДЕЛЕЙ В ЗАДАЧАХ НЕЛИНЕЙНОЙ РЕГРЕССИИ

05.13.17 — теоретические основы информатики

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

1 б ОКТ 2014

Москва — 2014

005553504

Работа выполнена в федеральном государственном бюджетном учреждении науки Вычислительный центр им. А. А. Дородницына Российской академии наук.

Научный руководитель: кандидат физико-математических наук, Стрижов Вадим Викторович, Федеральное государственно бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук, научный сотрудник Отдела интеллектуальных систем.

Официальные оппоненты:

доктор физико-математических наук, Хачай Михаил Юрьевич, Федеральное государственное бюджетное учреждение науки Институт математики и механики им. H.H. Краковского "Уральского отделения Российской академии наук, заведующий Отделом математического программирования;

кандидат физико-математических наук, Гуров Сергей Исаевич, Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Московский государственный университет имени М.В. Ломоносова, доцент Кафедры атематических методов прогнозирования Факультета вычислительной математики и кибернетики.

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт системного анализа Российской академии наук.

Защита диссертации состоится 13 ноября 2014 г. в 15:00 на заседании диссертационного совета Д 002.017.02 при Федеральном государственном бюджетном учреждении Вычислительный центр им. A.A. Дородницына Российской академии наук, расположенном по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке федерального государственного бюджетного учреждения науки Вычислительный центр им. А. А. Дородницына Российской академии наук и на сайте http: //www.ccas.ru.

Автореферат разослал

Ученый секретарь диссертационного совета Д 002.017.02, д.ф.-м.н., профессор " '

Рязанов В.В.

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

Диссертационная работа посвящена проблеме порождения и трансформации моделей в задачах нелинейной регрессии.

Актуальность темы

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

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

Для создания адекватной модели измеряемых данных используются экспертно-заданные порождающие функции и набор правил порождения. Модель задается в виде суперпозиции порождающих функций. Правила порождения определяют допустимость суперпозиции и исключают порождение изоморфных моделей.

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

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

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

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

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

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

Важным этапом развития методов решения задач восстанов-

ления регрессии является ипользованпе нелинейной регрессии для решения прикладных задач. Данный подход широко описывается в работах Дж. Себера — рассматривается построение и оценка параметров нелинейных моделей. Для оценки моделей используется алгоритм Левенберга-Марквадта.

Для индуктивного порождения моделей в работых Дж. Козы и Н. Зелинки, связанных с генетическим программированием, используется символьная регрессия — метод построения регрессионных моделей путем перебора различных произвольных суперпозиций функций из некоторого заданного набора. Индуктивное порождение моделей рассматривается в приложении к задаче определения оптимальной формы антенны. В работах В. В. Стрижова идеи индуктивного порождения регрессионных моделей находят свое развитие в применении методов двухуровневого Байесовского вывода к процесу порождения и настройки моделей.

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

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

Основные положения, выносимые на защиту:

1. Разработан алгоритм направленного порождения моделей, исследованы свойства порождаемых суперпозиций (с. 3541).

2. Разработаны новые алгоритмы вычисления структурной

сложности порождаемых суперпозиций и алгоритмы вычисления расстояния между порождаемыми суперпозициями (с. 23-35).

3. Разработан метод обнаружения изоморфных суперпозиций. Разработан алгоритм поиска изоморфных подграфов, соответствующих порожденным суперпозициям (с. 47-68).

4. Введено формальное определение трансформаций графов, соответствующих суперпозициям. Доказана применимость трансформаций при использовании структуры двойного кодекартова квадрата (с. 51-62).

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

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

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались на:

• Интеллектуализация Обработки Информации ИОИ-08 (Украина, Алушта, 2008);

• SIAM Conference on Financial Mathematics & Engineering 2008 (USA, New Bruinswick, 2008);

• Математика. Компьютер. Образование. 2009 (Россия, Пу-щино, 2009);

• EURO 2009 conference (Germany, Bonn, 2009);

• Математические Методы Распознавания Образов ММРО-14 (Россия, Суздаль, 2009);

• EURO 2010 conference (Portugal, Lisbon, 2010);

• EURO 2012 conference (Lithuania, Vilnus, 2012).

Публикации. Основные результаты по теме диссертации изложены в 6 печатных изданиях, 3 из которых изданы в журналах, рекомендованных ВАК, 3 — в тезисах докладов.

1. Сологуб P.A. Алгоритмы порождения нелинейных регрессионных моделей // Информационные технологии, 2013. No 5. С. 8 - 12.

2. Сологуб Р.А. Порождение регрессионных моделей поверхности волатильности биржевых опционов // Информационные технологии, 2012. No 8. С. 47 - 52.

3. Стрижов В.В., Сологуб Р.А. Индуктивное порождение поверхности волатильности опционных торгов // Вычислительные технологии, 2009. No 5. С. 102—113.

4. Sologub R., Strijov V. The inductive generation of the volatility smile models // SIAM Financial Modeling 08 conference proceedings. P. 21.

5. Sologub R. Inductive generation of foreign exchange forecast models // 23rd European Conference On Operational Research proceedings. P. 162.

6. Sologub R. Model generation for equity-futures spread forecasting // 24th European Conference On Operational Research proceedings. P. 168.

Личный вклад. Результаты получены автором самостоятельно при научном руководстве к.ф.-м.н. В.В. Стрижова. Личный вклад автора в работах с соавторами заключается в следующем: в работе [3] алгоритмы порождения моделей и экспериментальная часть работы созданы лично автором. Работы [1] и [2] выполнены автором целиком лично.

Объем и структура работы. Диссертация состоит из введения, четырех глав, заключения и приложения. Полный объем диссертации 92 страницы текста с 5 рисунками и 2 таблицами. Список литературы содержит 53 наименования.

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

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

Первая глава

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

Пусть задана выборка Ю = {(xn,yn)}n=i-. х £ IRm- Требуется построить функцию регрессии <p(x,w) >—>• у. Требуется определить модель / — отображение из декартова произведения множества свободных переменных х € Кп и множества параметров w е Rm в R1. Модель соответствует функции ip при заданном значении w = wq. Для модели оценивается набор параметров wo, доставляющие минимум внешнему критерию качества модели — квадратичной ошибке

S(w|S),/) = !|/(x,w)-y||2.

Задано множество G порождающих функций д(w, х). Для каждого элемента данного множества gi определены области аргументов w € Rm,x £ Rn и значений, при этом область значений принадлежит R1. В множество порождающих функций обязательно входит не имеющая аргументов функция id(x), значение которой тождественно значению свободной переменной, а также функция константы Const.

Искомую модель / мы будем искать среди множества супер-

позиций функций д е С. При этом накладываются ограничения на структуру суперпозиции:

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

1. Элементами суперпозици / могут являться только порождающие функции д] и свободные перменные х.

2. Количество аргументов элемента суперпозиции равно арности соответствующей ему функции д^.

3. Порядок аргументов элемента суперпозиции соотвествует порядку аргументов соответствующей функции д^.

4. Для элемента аргументом которого является элемент

область определения соответствующей порождающей функции д{ содержит область значений порождающей функции аргумента ду. с1от(,%) Э со<1(<^);

Условимся считать, что каждой суперпозиции / сопоставлено дерево Tf, эквивалентное этой суперпозиции и строящееся следующим образом:

• В вершинах V, дерева Гу находятся соответствующие порождающие функции д

• Число дочерних вершин у некоторой вершины Vi равно арности соответствующей ей функции д^.

• Порядок дочерних вершин вершины соотвествует порядку аргументов соответствующей функции gj.

• Листьями дерева Г/ являются свободные переменные либо числовые параметры ш,;.

1 2 3 4 5 6 7 8 9 ?; (1)

(I

Заранее задается максимальная арность вершин атах. Максимальное дерево, которое можно построить при таком условии, будет иметь 1 вершину на первом слое, атах на втором, а^1ах на третьем и так далее. Пример координатной сетки для деревьев с отах = 3 представлен на диаграмме (1).

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

Определение 2. Дерево Го называется общим поддеревом деревьев Г] и Г2, если в них существуют поддеревья Г^ и Г2, изоморфные дереву Го-

Определение 3. Общее поддерево двух деревьев называется наибольшим, если в нем содержится наибольшее число вершин среди других общих поддеревьев. Наибольшее поддерево деревьев Г\(К) и Г^(У^) обозначается как Гу(Уу). Символом р будет обозначаться количество элементов в множестве V: = Щ = Рз, \Уц\ = Ра-

В работе будет использоваться функция расстояния г между Г» и Г,-, зависящая от их размеров и наибольшего общего подграфа,

Гц = Pi + Pj - 2pij. Теорема 1. Для функции Гц выполняются условия метрики.

Теорема 2. При замене в дереве Го(1^)) поддерева Гд(У0') поддеревом дерева T^Vi) получается дерево Г2(^).

Расстояния между деревьями г02 = г(Г0(14)). Г2(^)) и roi = r(ro(Vo), ri(Vi)):

Г02 <Ро + Ръ ri2 ^ Pi+Р0-Р'0-Pi-

Теорема 3. Расстояние между исходным деревом Го(Ро) и порожденным деревом Г1 (Vi), |Vo| = |Vi| = ро, полученным с помощью операции замены одной верппшой дерева, не более чем 2(ро - где к — максимальное число аргументов среди

порождающих функций д, составляющих деревья Го и IV

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

Определение 4. Сложность С суперпозиции / равна сложности дерева Г, соответствующего ей, и определяется как сумма количества элементов во всех поддеревьях дерева Г.

Теорема 4. Сложность Сгх дерева Fi, полученного заменой в дереве Г0 поддерева Г(, на поддерево Г'х с корнем в вершине (d, i) . В случае подобной замены сложность Сгг дерева Ti будет равна

Cri=Cr0+d(Cri-Cr,o).

Вторая глава

Для решения прикладных задач машинного обучения недостаточно определить свойства моделей. Требуется указать ал-

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

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

F0 = {X, Const},

где X соответствует выборке 5), a Const соотвествует порождающей функции константы. Далее на каждом шаге для множества Fi построим вспомогательное множество Ui, состоящее из суперпозиций, полученных в результате применения функций gi & G к элементам fj 6 Fi-1:

Ui = {9i{fn, ■ ■ ■ fj J, | 9i e GUJ / € F<_i}. Тогда множество F{

Fi = Fi_i U Ui.

Теорема 5. Алгоритм J- породит любую допустимую суперпозицию ограниченной сложности за конечное число шагов.

Теорема 6. Справедлива следующая оценка количества суперпозиций, порожденных алгоритмом У после fc-ой итерации:

I j-fc| = о^"-1^-1^).

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

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

1. Некоторым методом оптимизации параметров минимизируются функции ошибки $1(10) для каждой модели /¿. Отыскиваются параметры w и вычисляется значение функции ошибки 5 каждой модели.

2. Заданы следующие правила построения производных моделей /у. Для модели ^ строится тождественная ей модель В дереве Г^-, соответствующем модели произвольно выбирается вершина г^. Выбирается произвольная модель /т из множества Р и произвольная вершина её дерева Гт. Модель модифицируется путем замещения в дереве Г^- поддерева, корнем которого является вершина функции у к на поддерево дерева Гт с корнем в вершине г,1;. Измененная модель /у добавляется в множество Р.

+

Ип

sqrt

1ш г

К

3. С заданной вероятностью ро каждая модель fj € Р подвергается изменениям. В дереве Г^, соответствующем модели в соответствии с некоторой заданной функцией распределения выбирается вершина Ук- Соответствующая ей порождающая функция д^ заменяется случайным образом выбранной функцией дт той же арности из множества

порождающих функций С.

4. Модели из множества Р сортируются в соответствии со значениями функции ошибки Заданная доля наилучших моделей используется в дальнейших итерациях.

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

Определение 5.

Схемой называется дерево, содержащее функции из множества Ои{—} и свободные переменные из множества Ту{=}, где С и Т — множества порождающийх функций и свободных переменных соответственно. Порождющая функция {=} означает произвольный символ, который может быть любой функцией или свободной переменной. Порядком схемы 0(Н) называется количество вершин в ней, не являющихся {=}•

Определение 6. Гиперсхемой называется дерево, содержащее функции из множества С?и{=} и свободные переменные из

множества Т(Л=, Порождющая функция {=} определяется также, как и для схемы, а свободная переменная {#} означает любое допустимое дерево.

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

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

Для данной операции формулируется аналог теоремы схем.

Теорема 7. Для операции гс замены поддерева с сохранением структуры оценивается вероятность сохранения схемы Н:

а(Я, г) = (1 - рх0)р(Н, Ь) + рх0ах0{Н, £),

где

/11 Н2 К ' 2' ¿еС(Л 1,^2)

при этом

РхО — вероятность проведения операции замены поддерева,

р(Н, £) — вероятность выбора вершины из схемы Н,

суммы проходят по всем деревьям из набора,

НС{к 1,/1г) — количество вершин с равной структурой родительских вершин,

Ь{Н, г) — гиперсхема, получаемая из Н заменой всех вершин от корня до вершины г вершинами типа =, а всех поддеревьев, выходящих из этих вершин — #,

11 (//, г) — гиперсхема, получаемая из Н заменой поддеревьев ниже точки г вершинами типа

Третья глава

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

Определение 8. Модель /2 с вектором параметров \У2 называется обобщающей для модели /1С вектором параметров лух, если для любого вектора найдется такой вектор что для любого хе £> значения функций /1^1, х) и /2(^2,х) равны:

ХбО^ Л(™-Ьх) = /2^2,X).

Определение 9. Модели /1 и /2 с векторами параметров и называются эквивалентными, если каждая из них является обобщающей для другой.

Алгоритм упрощения модели х) минимизирует слож-

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

Определение 10. Подграф Ь, удаляемый из графа С? в алгоритме упрощения, будет называться заменяемым подграфом.

Определение 11. Создаваемый подграф В,, помещаемый в граф С? в алгоритме упрощения, называется замещающим подграфом.

Для рассмотрения трансформации графов необходимо ввести понятие правила.

Определение 12. Правило — это тройка р = (Л, Ф, Ф), где Л и Ф являются заменяемым и замещающим подграфами и граф Ф является общей частью подграфов Ли Ф, то есть их пересечением. Заменяемый, или начальный подграф Л называется условием применения правила, замещающий, или конечный подграф Ф — итогом его применения. Подграф Ф описывает часть графа, необходимую для применения правила, но неизменную в процессе применения. Множество Л \ Ф является удаляемой частью графа, вместо неё создается множество Ф \ Ф.

Определение 13. Процедура поиска пг — отображение из Л в Г, ставящая в соответствие заменяемому графу эквивалентный ему подграф. При этом процедура ш сохраняет структуру графа Г.

Определение 14. Трансформация графа — это пара, элементами которой являются правило р и процедура поиска т. Процедура трансформации графа Г в граф П с помощью правила р и процедуры поиска т будет также обозначаться как Г О.

Сформулируем условие существования графов Ф и Д при трансформации графа. Для этого вводим следующие определ-ния:

Определение 15. Точки соединения — вершины и ребра в Л, которые не удаляются при применении правила р.

Определение 16. Точки обнаружения—вершины и ребра в Л, образы которых относительно пг имеют более одного прообраза.

Определение 17. Подвешенные вершины — вершины в Л, образы которых относительно т в Г имеют входящие или выходящие ребра, не содержащиеся в Л.

Теорема 8. Пусть дано правило р = (Л Ф -> Ф), граф Г и процедура поиска т : Л Г. Вершины графов обозначаются буквой V, ребра — Е. Тогда правило р с процедурой поиска ш удовлетворяет условию соединения если все точки обнаружения и подвешенные вершины также являются точками соединения.

Теорема 9. Любой трансформации t = (Лг, Ф4, Ф() графа соответствует набор правил р1 = (ЛР4, Фр(, Фр,), удовлетворяющих условию соединения, такой что любое применение трансформации £ аналогично применению одного из правил р

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

Определение 18. Две трансформации графов Г Р1Д'1 5Г2] и

т-1 Р2.ГП2 „

I —1 ¿2 являются параллельно независимыми, если все вершины и ребра, попадающие в образ обоих морфизмов поиска, являются соединительными:

т^ЛОПт^Ла) С пц^ФО) р|т2(г1(Ф2)). Теорема 10. Две трансформации графов-деревьев Г Р1-1>1

„ ТЧ Р2.ГО2

и 1 —» 5 ¿2 являются параллельно и последовательно независимыми, если образы корней VI и г>2 деревьев т^Лх) и тт^Лх) не принадлежат друг другу:

£ т2(Л2) ь2 & т^Лх).

Теорема 11. Две трансформации графов Г и

Г являются параллельно независимыми, если существу-

ют морфизмы г: Ах —> Ау и : Л2 —» Ах, такие что /2 о г = Ш1 и = т2:

ф!

Фг

? I1А

»-Л1 - - - - л2

Л " ~

Чп

Г

Ш2

/2

к2 ч. +

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

Определение 19. Шаблон в — гиперсхема, обладающая наименьшей сложностью среди всех гиперсхем, таких что при их взаимном замещении получаемые модели оказываются эквивалентными. Сложность гиперсхемы определяется как сложность суперпозиции при замещении всех символов {=} и {#}, означающих соответствено произвольную независимую переменную и произвольное поддерево, на константы.

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

1. Все поддеревья Г^ в выбранном дереве Г проверяются на эквивалентность шаблонам из 0 согласно заданным правилам.

2. Если какое-либо поддерево Г^- в дереве эквивалентно дереву из 0, данное поддерево заменяется соответствующим элементом из 0.

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

функций вводится алфавитное упорядочение для ветвей, выходящих из вершины 7; дерева Г, соответствующей коммутативной порождающей функции д^.

Четвертая глава

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

Заключение

Основные результаты диссертационной работы.

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

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

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

4. Разработан новый метод порождения экспертно-интерпретируемых моделей. Создана базовая библиотека правил порождения экспертно-интерпретируемых моделей.

Публикации автора по теме диссертации

1. Сологуб Р.А. Алгоритмы порождения нелинейных регрессионных моделей // Информационные технологии, 2013. No 5. С. 8 - 12

2. Сологуб Р.А. Порождение регрессионных моделей поверхности волатильности биржевых опционов // Информационные технологии, 2012. No 8. С. 47 -52

3. Стрижов В.В., Сологуб Р.А. Индуктивное порождение поверхности волатильности опционных торгов // Вычислительные технологии, 2009. No 5. С. 102—113.

4. Sologub R., Strijov V. The inductive generation of the volatility smile models // SIAM Financial Modeling 08 conference proceedings. P. 21.

5. Sologub R. Inductive generation of foreign exchange forecast models // 23rd European Conference On Operational Research proceedings. P. 162.

6. Sologub R. Model generation for equity-futures spread forecasting // 24th European Conference On Operational Research proceedings. P. 168.

7. Стрижов B.B., Сологуб Р.А. Индуктивное построение регрессионных моделей волатильности // сборник трудов конференции МКО-2009. С. 58.

8. Стрижов В.В., Сологуб Р.А. Индуктивное порождение регрессионных моделей волатильности // Сборник трудов конференции ИОИ-2008. С. 215-216.

Подписано в печать:

01.10.2014

Заказ № 10253 Тираж - 100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru