Содержание к диссертации
Введение
1. Обзор современных методик, алгоритмов и систем интеллектуального анализа данных 14
1.1. Математическое моделирование как основа интеллектуального анализа данных 14
1.2. Современные системы мета-обучения 16
1.3. Реализация систем мета-обучения: современные методы ИАД 23
1.4. Метод группового учета аргументов (МГУА)
1.4.1. Основные принципы и достоинства МГУА 28
1.4.2. Обзор алгоритмов МГУА: параметрические, непараметрические, многорядные 31
1.4.3. Обзор применений МГУА 41
1.5. Программные платформы интеллектуального анализа данных 50
1.5.1. Программные платформы для реализации систем мета-обучения 50
1.5.2. Обзор систем моделирования на основе МГУА 56
1.5.3. Обзор вычислительных архитектур, используемых для запуска алгоритмов интеллектуального анализа данных 59
1.6. Выводы по главе 1 и постановка задач диссертационного исследования 65
2. Архитектура системы интеллектуального анализа данных на основе мета-обучения 67
2.1. Методика ИАД на основе мета-обучения с поддержкой выбора оптимального алгоритма решения задачи и вычисления оптимальных параметров его функционирования 67
2.2. Алгоритмы обучения, использования и дообучения системы 74
2.2.1. Алгоритмы, соответствующие методике «одна мета-модель на алгоритм» 74
2.2.2. Алгоритмы, соответствующие методике «две мета-модели на алгоритм» 77
2.3. Идентификация мета-моделей с помощью алгоритма дважды многорядной полиномиальной сети МГУА 79
2.4. Вычислительный алгоритм идентификации полиномиально-гармонической модели оптимальной сложности 84
2.5. Разработка архитектуры программной платформы мета-обучения 91
2.6. Разработка архитектуры программной платформы МГУА 93
2.7. Выводы по главе 2 98
3. Реализация программной платформы 101
3.1. Выбор средств реализации 101
3.2. Обеспечение критерия гибкости 102
3.3. Обеспечение критерия производительности 107
3.4. Обеспечение критерия универсальности Ill
3.3. В ыводы по главе 3 113
4. Практическое применение результатов диссертационного исследования 114
4.1. Автоматическая система мета-обучения для решения задачи прогнозирования 114
4.1.1. Состав экспериментов 114
4.1.2. Набор тестовых выборок данных «МЗ Competition» 115
4.1.3. Нижний уровень системы: прогнозирующие модели и алгоритмы их обучения... 117
4.1.4. Нижний уровень системы: результаты идентификации прогнозирующих моделей 127
4.1.5. Верхний уровень системы (мета-уровень системы) 131
4.1.6. Верхний уровень системы: результаты идентификации мета-моделей 135
4.1.7. Результаты экспериментов по применению системы мета-обучения 138
4.2. Система прогнозирования нестационарных временных рядов 144
4.2.1. Структура системы прогнозирования нестационарных временных рядов 144
4.2.2. Результаты эксперимента по прогнозированию FX EUR/USD за 2009-2010 годы. 146
4.3. Экспериментальное исследование вычислительного алгоритма идентификации
полиномиально-гармонической модели оптимальной сложности 149
4.3.1. Точность расчета частот гармонической части модели 150
4.3.2. Качество идентификации моделей при ненулевой ошибке расчета частот гармонической части
4.4. Экспериментальная проверка эффективности распараллеливания вычислений 159
4.5. Выводы по главе 4 164
Заключение 166
Список литературы
- Реализация систем мета-обучения: современные методы ИАД
- Алгоритмы обучения, использования и дообучения системы
- Обеспечение критерия производительности
- Результаты экспериментов по применению системы мета-обучения
Реализация систем мета-обучения: современные методы ИАД
Задачей Интеллектуального Анализа Данных (ИАД, в англоязычной литературе используется термин «Data Mining») является обнаружение (извлечение) в доступных исследователю исходных данных ранее неизвестных, неочевидных, но практически полезных знаний [1;2,стр. 58-59]. При этом знания «представляют собой краткое обобщенное описание основного содержания информации, представленной в данных» [3,стр. 6].
В фундаментальных работах различных авторов [2,3] в качестве доминирующей формы представления знаний используются математические модели. С точки зрения операций, совершаемых над моделями в процессе ИАД, выделяются два основных направления [3].
1. Анализ доступных данных с использованием модели, которая известна априори с точностью до параметров. В этом случае задача ИАД сводится к задаче поиска оптимальных значений параметров модели, обеспечивающих максимизацию некоторого показателя качества модели, задаваемого исследователем (специалистом, участвующим в процессе ИАД). В литературе процесс решения данной задачи часто именуют «обучением модели».
2. Анализ доступных данных при отсутствии априорного выбора модели. В этом случае в процессе ИАД осуществляется выбор (построение) модели и ее параметров таких, которые максимизируют некоторый показатель качества решения конкретной задачи ИАД (зачастую с литературе используется термин «идентификация модели»).
Несмотря на очевидные различия, можно отметить, что неотъемлемой частью, основой обоих направлений является математическое моделирование.
В настоящее время существует большое количество алгоритмов искусственного интеллекта (включая машинное обучение), математической статистики, оптимизации и прогнозирования и пр., применяемых для решения задачи ИАД как в части обучения (первое направление), так и в части идентификации моделей (второе направление): искусственные нейронные сети, генетические алгоритмы, деревья решений, алгоритмы нечеткой логики, корреляционный и регрессионный анализ и т.д.
Каждый из существующих алгоритмов показал свою эффективность при решении разнообразных практических задач: распознавания образов, анализа и понимания изображений, прогнозирования сложных процессов, создания экспертных систем и т.п. Однако в работе [4] было показано, что не существует единственного алгоритма, способного максимально эффективно решать задачу ИАД во всех возможных практических применениях, поэтому решение каждой новой практической задачи требует привлечения некоторых экспертных знаний для выбора наиболее подходящего алгоритма из числа доступных.
В работе [5] была формализована методика выбора алгоритма (рисунок 1): на основании набора мета-характеристик (meta-features, MF) /(х)єі7 (F - пространство мета-характеристик) для выборки данных х из пространства проблем (задач) X функция Syf(x)} («selection mapping») производит выбор такого алгоритма а из пространства доступных алгоритмов А , что его эффективность р (а, х) («performance mapping») на выборке данных х максимальна ( р (я, х) - показатель эффективности, ПЭ).
Здесь под «мета-характеристиками» данных подразумевается некоторая априори доступная информация либо рассчитываемые характеристики заданной выборки данных («данные о данных», «знания о данных»). Термином «алгоритм» обозначена последовательность действий по осуществлению математического моделирования с целью решения конкретной задачи ИАД. А функция «selection mapping» отражает первый этап ИАД -выбор алгоритма решения конкретной задачи ИАД.
Методика, предложенная в работе [5], предполагает, что выполнение функции «selection mapping» возложено на эксперта в области ИАД, либо в качестве используется составленный экспертом набор правил (эвристик) выбора алгоритма. Очевидным недостатком применения методики является необходимость привлечения экспертов на стадии разработки системы ИАД либо на стадии ее использования. С одной стороны это требует дополнительных материальных и временных затрат, а с другой стороны ограничивает применение данного подхода в автоматических системах ИАД. Более того, возникает проблема эффективности накопления экспертных знаний и улучшения имеющихся эвристик выбора алгоритма, поскольку данные процессы основываются на увеличении уровня квалификации самого эксперта. Решение описанных проблем производится исследователями в рамках направления «мета-обучение» - области ИАД, изучающей способы увеличения эффективности «обучающихся систем» ИАД путем накопления знаний об эффективности обучения в таких системах, в том числе и в автоматическом режиме [6].
Реализация данного подхода, как правило, предполагает накопление данных об эффективности функционирования системы ИАД (с точки зрения некоторого задаваемого показателя эффективности), о характеристиках конкретных задач ИАД, об особенностях функционирования алгоритмов решения задач и т.д. Полученная таким образом информация позволяет на своей основе осуществить ИАД в форме математического моделирования с целью выявления полезных с точки зрения данного подхода знаний в виде так называемых «мета-моделей». С одной стороны, полученные мета-модели позволяют обнаружить некоторые практически полезные зависимости между эффективностью алгоритмов ИАД и характеристиками задачи ИАД. С другой стороны, они позволяют предсказать эффективность каждого алгоритма при решении конкретной задачи ИАД, а значит, и осуществить выбор оптимального алгоритма ИАД для решения этой задачи.
До настоящего времени было предложено множество вариантов построения систем интеллектуального анализа данных на основе мета-обучения (далее для обозначения подобных систем будет также использоваться сокращенное название «система мета-обучения»). Например, в аналитических обзорах каждой из 10 глав только одной книги [7], посвященной мета-обучению, упомянуты более 40 систем, разрабатываемых различными научными коллективами. Несмотря на то, что в публикациях по системам мета-обучения приводится аналитический обзор и сравнение с некоторыми существующими системами, выделяются лишь некоторые внешние критерии оценки систем, как то: результирующая точность, скорость принятия системой решений и т. д. Известна работа [7. стр.117-156], в которой сделана попытка описания строения систем мета-обучения, однако рассматривается лишь состав внутренних модулей без выделения общности в их организации.
В связи с этим автором было принято решение о разработке классификационных признаков, учитывающих внутреннюю организацию систем, с целью систематизации существующих систем мета-обучения. Ниже описаны сформулированные классификационные признаки, согласно которым в таблицах 1, 2 приводится информация для каждой из систем. 1. Класс разделяет приведенные системы на 4 группы по их предназначению: a. Algorithm Selection - для заданной выборки данных произвести выбор оптимального алгоритма из набора доступных (согласно задаваемому ПЭ); b. Parameter Tuning - для заданной выборки данных определить оптимальные значения параметров функционирования заданного алгоритма; c. Data Mining Assistant - выработать экспертные рекомендации, содействующие специалисту по ИАД в выборе оптимального алгоритма для заданной выборки данных; d. Multi-Level Data Mining - организовать процесс автоматического многоуровневого ИАД, при котором осуществляется не только перебор алгоритмов ИАД и их параметров, но и сравнение и выбор алгоритмов поиска оптимальных алгоритмов ИАД и оптимизации их параметров. 2. Режим распределяет ответственность за осуществление той или иной функции системы мета-обучения: «Р» - ручной, когда принятие решений полностью возложено на эксперта; «А» - автоматический, когда эксперт уведомляется о решениях, принимаемых системой мета-обучения. Знаком «-» отмечены случаи, когда функция не поддерживается системой. В таблицах 1 и 2 рассматриваются следующие функции систем мета-обучения: a. обучение - способность системы производить накопление мета-знаний об эффективности доступных алгоритмов ИАД, мета-характеристиках данных и их взаимосвязи (в терминах работы [5]: определение вида и/или построение функции «selection mapping» S ); b. использование - осуществление действий по выбору /рекомендации оптимального алгоритма ИАД и/или параметров его функционирования на основе анализа поставленной задачи - анализа заданной выборки данных (в терминах работы [5] для выбора алгоритма: вычисление мета-характеристик данных / и применение S для выбора алгоритма а ); c. выбор мета-характеристик (значимых) - определение подмножества заданных мета характеристик, отражающих лишь значимые свойства выборок данных, определяющих корректный выбор алгоритма для решения поставленной задачи. Иными словами, это исключение нерепрезентативных мета-характеристик; d. настройка параметров алгоритмов - определение таких значений параметров функционирования алгоритмов, при которых достигается максимизация ПЭ при решении поставленной задачи; e. проверка эффективности (лучшего алгоритма) - оценка допустимости применения выбранного системой алгоритма для решения поставленной задачи. Это необходимо для детектирования случаев, когда все доступные системе мета-обучения алгоритмы неудовлетворительно решают поставленную задачу, поэтому выбор лучшего из них не гарантирует ожидаемое высокое значение ПЭ.
Алгоритмы обучения, использования и дообучения системы
Система мета-обучения, реализующая методику, которая предложена в разделе 2.1, предполагает построение мета-моделей, отражающих взаимосвязь между оптимальными параметрами работы алгоритмов, входящих в состав системы ИАД, их эффективностью при решении задачи ИАД и мета-характеристиками данных. Действительно, на шаге 2.6 алгоритма обучения системы, реализующего методику «одна мета-модель на алгоритм», и на шагах 2.6 и 2.7 алгоритма обучения системы, реализующего методику «две мета-модели на алгоритм», требуется применение алгоритма ИАД для построения таких моделей.
В разделе 1.3 в результате проведенного аналитического обзора было показано, что наиболее подходящим для начальной реализации системы ИАД на основе мета-обучения является метод группового учета аргументов (МГУА).
Для построения мета-моделей выберем алгоритм дважды многорядной сети МГУА, описание которого приведено в разделе 1.4.2: листинг 6, стр. 40 (сеть типа «КИКА» [46]). Поиск оптимальной структуры мета-модели будем осуществлять в классе полиномиальных моделей.
Структура сети показана на рисунке 10. Незаполненными квадратами показан вход сети входные переменные xt заданной выборки данных
В соответствии с алгоритмом построения сети, на первом слое производится обучение нейронов, имеющих частное описание вида (обобщенный полином Колмогорова-Габора согласно формуле 4) где Xj - n переменных из числа N входных переменных выборки, подаваемые на вход нейрона (используется так называемый n-входовой нейрон); at, ау aijk параметры полиномиальной модели (коэффициенты полинома).
В частном случае, когда в сети используются двухвходовые нейроны с ограничением на вторую степень полинома, частное описание имеет вид множество коэффициентов полинома. Таким образом, на первом слое производится генерация всех возможных нейронов: для сочетании входных переменных строятся все возможные комбинации слагаемых исходного частного описания (S = 2 -1 = 63 комбинации). Обозначим общее количество сгенерированных нейронов W, а каждому индексу м = 1, W поставим в соответствие пару входных переменных с индексами / = 1,N и j = \,N (/ у ), а также s = l,S . Коэффициенты полиномов оцениваются на основе обучающей выборки данных UA a U по методу наименьших квадратов (МНК): где НА - множество индексов точек выборки U , формирующих обучающую выборку данных UA ; Уь выходное значение, соответствующее h -ой точке обучающей выборки UA .
Для случая линейной по параметрам модели, к которому относятся частные описания вида (12) и (13), решение задачи параметрической оптимизации (14) для двухвходового нейрона сводится к решению СЛАУ вида SAxxw а = YA ; вектор выходных значений обучающей выборки данных; $A,xx,w - матрица факторов, составляющих линейную по параметрам модель. Матрица факторов SAxxw генерируется на основе данных обучающей выборки данных для переменных / и j нейрона w и информации о виде его частного описания, соответствующего индексу s:
После обучения на вход каждого из W нейронов подается информация проверочной выборки данных UB a U с целью расчета значения задаваемого внешнего критерия качества С . Одним из примеров такого критерия является критерий среднеквадратического отклонения (MSE, Mean Squared Error), который рассчитывается следующим образом: Н в - размер проверочной выборки данных. На основании полученных значений критерия качества производится отбор Z лучших нейронов (при использовании критерия MSE - Z нейронов с наименьшим значением критерия), выходы которых yz (z = 1, Z ) подаются на вход следующего слоя сети.
Стоит отметить, что, поскольку на вход каждого из нейронов подается лишь подмножество входных переменных, в результате отбора Z лучших нейронов может оказаться, что не все входные переменные включены в частные описания отобранных нейронов, а лишь наиболее репрезентативные. В литературе эта особенность получила наименование «активные нейроны» [44].
Автоматический режим обучения. Требование удовлетворено, поскольку построение мета-моделей в виде полиномиальной сети МГУА осуществляется без необходимости привлечения экспертных знаний: структура сети строится автоматически с учетом параметров работы алгоритма МГУА, заданных экспертом на этапе проектирования системы. Как указывалось в разделе 1.4.2 (листинг 6, стр. 40), в состав параметров входят максимальное число слоев результирующей нейронной сети R, максимальное число нейронов в слое Z, вид частного описания нейрона (число входов, максимальная степень полинома), а также критерий качества моделей.
Автоматический режим выбора значимых мета-характеристик. Требование удовлетворено, поскольку в процессе построения сети на каждом слое автоматически отбираются лучшие нейроны (в смысле заданного критерия качества), на входе которых используются наиболее релевантные входные переменные, представляющие собой мета-характеристики данных.
Также, поскольку в результате работы алгоритма находится структура результирующей полиномиальной нейронной сети МГУА оптимальной сложности, можно считать требование В (стр. 20) выполненным. Требования С и D неприменимы к описанному выше алгоритму, поскольку имеют отношение к другим частям разрабатываемой системы мета-обучения.
Вычислительный алгоритм идентификации полиномиально-гармонической модели Полиномиальная часть представляет собой обобщенный полином Колмогорова-Габора (формула 4). Как правило, при построении моделей производят ограничение суммарной степени слагаемых полинома, а в слагаемые с частью отсутствующих входных переменных производят их включение в степени 0, поэтому удобнее рассматривать полиномиальную часть в следующем представлении
Обеспечение критерия производительности
В качестве алгоритма обучения модели используется ансамбль комбинаторного алгоритма МГУА (COMBI) и гармонического алгоритма МГУА (HARM). Данные алгоритмы подробно описаны в разделе 1.4.2 (соответственно, листинг 1 на стр. 32 и листинг 2 на стр. 33). Алгоритмы запускаются последовательно. На первом шаге комбинаторный алгоритм используется для выделения полиномиального тренда. На втором шаге гармонический алгоритм используется для обучения гармонической части, используя разность между входной временной последовательностью и трендом, полученным на первом шаге.
Построение прогнозных значений более чем на 1 шаг вперед предполагает итеративную процедуру, на каждом следующем шаге которой используется прогнозное значение с предыдущего шага: максимальная степень слагаемого, rp,w г , г - ограничения на количество слагаемых модели, W - число используемых моделью запаздывающих аргументов (размер окна). Алгоритм обучения модели
В качестве алгоритма обучения модели используется комбинаторный алгоритм МГУА (COMBI). Данный алгоритм подробно описан в разделе 1.4.2 (листинг 1, стр. 32). Параметры работы алгоритма, принятые в экспериментах: число запаздывающих аргументов W = 1..5 - устанавливалось системой мета-обучения; max і ограничение на степень полинома г = 1 - линейная модель; ограничение на степень было вызвано необходимостью уменьшить время, требуемое для обучения модели, поскольку с ростом W вычислительная сложность растет экспоненциально; без ограничений на число слагаемых (і311 = 0, Р = In/ ) - полный перебор от 1 до максимально возможного количества; обучающая выборка - первые 2/3 точек временной последовательности (стоит отметить, что обучающая выборка на W точек меньше, чем в случае модели тренда); проверочная выборка - последующие 1/3 точек; метод обучения модели (вычисления параметров ар)- МНК; внешний критерий селекции моделей - CR (суммарное квадратичное отклонение модели от данных на проверочной выборке); метка модели и алгоритма - «COMBI-r» («COMBI-r-pow[rmax]-[W]»).
В качестве алгоритма обучения модели используется алгоритм дважды многорядной полиномиальной сети МГУА (2ML PNN). Данный алгоритм подробно описан в разделе 1.4.2 (листинг 6, стр. 40), а также в разделе 2.3 при рассмотрении процедуры идентификации мета-моделей (сеть типа «КИКА» [46]). В качестве алгоритма обучения нейронов использовался комбинаторный алгоритм МГУА (COMBI).
Параметры работы алгоритма, принятые в экспериментах: число запаздывающих аргументов W = 1..5 - устанавливалось системой мета-обучения; max о ограничение на степень полинома г = 2 - квадратичное частное описание; без ограничений на число слагаемых (і311 = 0, Р = In/ ) - полный перебор от 1 до максимально возможного количества; число входов нейронов п = 2 - двухвходовые нейроны; r min 1 r max о с количество слоев неиросетевои структуры К = 1, К = 2..5 ; максимальное количество нейронов в одном слое Z = 2..5 ; обучающая выборка - первые 2/3 точек временной последовательности (стоит отметить, что обучающая выборка на W точек меньше, чем в случае модели тренда); проверочная выборка - последующие 1/3 точек; метод обучения модели (вычисления параметров ap)- МНК; внешний критерий селекции моделей - CR (суммарное квадратичное отклонение модели от данных на проверочной выборке); минимальное изменение внешнего критерия от слоя к слою 1СГ . метка модели и алгоритма - «PNN» («PNN-[R]x[Z]-[W]»). Сводная информация об используемых прогнозирующих моделях (МГУА) В таблице 19 представлена сводная информация о прогнозирующих моделях, их параметрах и алгоритмах их построения. В таблице параметры каждой из прогнозирующих моделей разделены на три группы.
1. Постоянные параметры устанавливаются исследователем на этапе проектирования системы мета-обучения при включении соответствующей прогнозирующей модели в состав системы. В режимах обучения и использования системы данные параметры не изменяются.
2. Перебираемые параметры с заданным множеством значений определяют независимые реализации прогнозирующих моделей, рассматриваемых системой независимо друг от друга. Например, в соответствии с информацией, приведенной в таблице 19, система осуществляет построение и использование четырех независимых полиномиальных моделей в виде нейронной сети, имеющих размер 2x2, 3x3, 4x4 и 5x5 (число слоев х число нейронов в слое).
3. Устанавливаемые системой параметры вычисляются системой на основании мета-характеристик выборки данных (временной последовательности) таким образом, чтобы эффективность (с точки зрения заданного показателя эффективности) конкретной модели (алгоритма) была максимальна. В таблице для каждого из таких параметров указан набор значений, использующихся системой в режиме обучения.
Алгоритмы сгруппированы по способу прогнозирования: представлено 7 алгоритмов построения тренда, 4 алгоритма скользящего окна, а также 5 реализаций экспертных систем.
Для каждого из алгоритмов в базе данных «МЗ Competition» хранятся прогнозы для каждой из представленных тестовых последовательностей (за исключением ААМ1 и ААМ2, прогнозы которых отсутствуют для годичных данных, но в данном случае это некритично, так как используются только месячные данные).
Верхний уровень системы (мета-уровень системы) Мета-характеристики временных последовательностей Были определены 8 мета-характеристик временных последовательностей, подробная информация по которым приведена в таблице 22. Для каждой из мета-характеристик приведен вид согласно классификации, введенной ранее в аналитическом обзоре систем мета-обучения (раздел 1.2, стр. 18), а также способ их вычисления.
На рисунке 18 представлены гистограммы распределений значений мета-характеристик, рассчитанные для всех 1428 выборок данных (N - число выборок, значение мета-характеристики которых попадает в соответствующий интервал гистограммы), а на рисунке 19 визуализированы значения линейного коэффициента их взаимной корреляции (более темный цвет означает более коррелированные значения, знаком «+» и «-» отмечены, соответственно, положительные и отрицательные значения корреляции). Гистограммы распределений для каждой мета-характеристики имеют различный вид, а абсолютное значение корреляции в среднем составляет 0.29, что свидетельствует о том, что мета-характеристики отражают независимые свойства временных последовательностей.
Результаты экспериментов по применению системы мета-обучения
Результаты экспериментов для первого набора параметров временной последовательности представлены на рисунке 33, для второго набора параметров - на рисунке 34. На рисунках приводится три горизонтальные группы по 3 графика, каждая из групп соответствует различным ограничениям на сложность модели (о = 1..3 ), о чем сделана соответствующая отметка в верхней части каждого графика. Точками отмечены экспериментальные значения, относящиеся к первому варианту ограничений на сложность модели (когда алгоритм производит выбор модели оптимальной сложности), а звездочками - ко второму (когда структура модели фиксирована, а алгоритм лишь производит оценку ее параметров).
В каждой группе из трех графиков слева отображены зависимости ошибки расчета периодов гармоник А от задаваемого уровня шума о . На графике, расположенном в центре приводятся экспериментальные зависимости точности прогноза (MSE) от уровня шума с . На графиках справа отмечена средняя сложность моделей на выходе алгоритма (усреднение по каждому из запусков), которая численно соответствует числу гармоник в результирующей прогнозирующей модели. Дробные значения корректны и соответствуют случаям, когда от запуска к запуску менялась последовательность случайных чисел на выходе генератора, что приводило к идентификации модели различной структуры. Оси всех трех графиков развернуты таким образом, чтобы оси с всех графиков были совмещены - для удобства группового анализа результатов эксперимента ( с - входной параметр экспериментов).
Из анализа графиков можно сделать следующие выводы.
1. Отклонение периодов гармоник от истинных значений практически линейно зависит от задаваемого уровня шума для моделей с фиксированной структурой, что верно исходя из способа задания частот гармоник в данном эксперименте. Нелинейная зависимость для моделей с вариативным выбором структуры (значения с от 0.1 до 0.3) объясняется наличием случаев выбора модели упрощенной структуры (это подтверждается и графиком S m(n- J , на котором скорость роста кривой резко изменяется в том же диапазоне о от 0.1 до 0.3).
2. Нулевая ошибка прогноза наблюдается только для прогнозирующих моделей истинной структуры (3 гармонических составляющих) при нулевой ошибке задания частот гармоник.
3. При значениях А, превышающих 2.0 для первого набора параметров временной последовательности и 1.8 для второго наблюдается резкое уменьшение скорости прироста ошибки прогноза с ростом ошибки задания частот гармоник для моделей с наличием свободы выбора структуры. Это объясняется упрощением структуры модели в результате работы алгоритма, связанным с уменьшением репрезентативности ее составляющих. Это упрощение структуры модели также прослеживается на графике S mdl-а - линия сильнее приближается к нулевому уровню (значения меньше 1 означают отсутствие гармоник в результирующей модели в некоторой части экспериментов). Схожая тенденция наблюдается и для модели с фиксированной структурой, но при значениях А, превышающих 3.5.
4. Вид графиков MSE-сг свидетельствует о высокой чувствительности алгоритма к ошибкам расчета частот (периодов) гармоник, что выражается в резком росте ошибки прогноза при возрастании ошибки по частотам. Для модели истинной структуры данный рост пропорционален росту ошибки расчета частот, для моделей с неистинной структурой возрастание ошибки прогноза достигает величин 370%.
Столь высокая чувствительность качества моделей к ошибкам расчета частот гармоник подтверждает обоснованность разработки вычислительной процедуры «Фурье+оптимизатор»: более высокая точность ее работы по сравнению с методом баланса ординат позволяет существенно улучшить качество результирующих моделей.
В качестве исходной информации для проведения индуктивного моделирования использовались данные предыстории нестационарного временного ряда обменного курса валют EUR/USD за 2009-2010 гг. - входная выборка данных размерности 3 (3 входных аргумента), состоящая из 100 точек. Для построения прогнозирующих моделей использовался комбинаторный алгоритм МГУА [30,стр. 32-38], осуществляющий полный перебор полиномиальных моделей (полиномов) максимальной степени 3 (общее количество моделей составляло 1048575). Параметрическая идентификация моделей проводилась с использованием метода Гаусса (асимптотическая сложность 0\п3)). В качестве внешнего критерия селекции моделей использовались критерий точности CR [25. стр. 44] и критерий минимума смещения BS [25. стр. 54]. Для обучения и селекции моделей выборка делилась на равные части по 50 точек. Для расчета значения CR каждая модель обучалась однократно на одной части, после чего с использованием данных второй части производился отбор 10 лучших моделей, каждая из которых обучалась дважды (на обеих частях выборки) для расчета ВS.
Эксперимент повторялся несколько раз для различного количества параллельных потоков вычислений (от 1 до 8). Измерялось время, затрачиваемое на вычисления, причем каждый эксперимент повторялся 10 раз с целью минимизации влияния на результаты случайных факторов, увеличивающих время расчета. Для проведения экспериментов использовались три различных аппаратных конфигурации МЯП. Вычисления на каждой из аппаратных конфигураций проводились с использованием вещественных чисел двойной точности (тип double), применялось выравнивание данных по границе, кратной размеру операнда (в соответствии с рекомендациями по оптимизации [99, 100]), векторизация вычислений осуществлялась с применением набора команд SSE2.
На рисунке 35 представлены результаты проведенных экспериментов. По оси абсцисс -количество параллельных потоков вычислений Р, по оси ординат - время вычисления tp. Сплошными линиями и пометкой «64-» обозначены эксперименты, проводимые с использованием 64-битной версии исполняемых файлов, пунктирными линиями и меткой «32-» - 32-битной. Аппаратные конфигурации МЯП, соответствующие меткам «А6», «р2» и «І7», приведены в таблице 26. Стоит отметить, что 32-битная версия исполняемого файла показала меньшую производительность, чем 64-х битная. Это может быть объяснено наличием большего количества регистров общего назначения, доступных приложениям в программной модели AMD64 по сравнению с х86 [103, стр. 1-8].
На рисунке 36а приведены графики прироста производительности тр (ось ординат) в зависимости от числа потоков вычисления Р (ось абсцисс) для различных аппаратных конфигураций. Наибольший прирост наблюдается для 6-ядерного процессора - в 3.96 раза. Что характерно, линейный характер увеличения производительности с ростом числа потоков исчезает при достижении количества аппаратно-доступных ядер.
Видно, что распределение вычислительной нагрузки производится неравномерно -некоторые потоки (с меньшими индексами) остаются «недозагруженными» вычислениями, поэтому определенную часть времени простаивают в ожидании завершения вычислений на других потоках. Причиной этому являются неточности в предсказании времени обучения моделей в текущей реализации алгоритма распределения моделей по независимым группам. Увеличение точности предсказания является задачей дальнейших работ. Тем не менее, на основании текущих экспериментальных данных можно произвести оценку максимальной производительности предложенного решения. Минимальное общее время расчета соответствует равномерному распределению вычислительной нагрузки. В этом случае каждый поток затратит время, равное среднему измеренному времени работы потоков. Графики прироста производительности и эффективности в этом случае для МЯП «р2» приведены на рисунке 36 и помечены «ideal» - для 6 потоков прирост составит 5.77, а эффективность - 0.96, что соответствует лучшим показателям программных систем индуктивного моделирования, рассмотренным выше (таблица 10).
