Содержание к диссертации
Введение
Глава 1. Теоретические основы 12
1.1. Краткий обзор литературы 12
1.2. Описание решаемой задачи 35
1.3. Поиск минимаксных стратегии и риска как байесовских 38
1.4. Выводы к первой главе 47
Глава 2. Стратегия параллельного управления 48
2.1. Нахождение минимаксного риска для параллельной обработки с группами переменного объема 49
2.2. Влияние размеров групп для параллельной обработки на минимаксный риск 55
2.3. Оптимизация размеров групп для параллельной обработки . 58
2.4. Результаты численной оптимизации 67
2.5. Сравнение обработки с группами равного и различного размера для одинакового числа этапов 71
2.6. Сложность алгоритма 76
2.7. Сравнение с другими алгоритмами 79
2.8. Возможные дальнейшие усовершенствования 82
2.9. Выводы ко второй главе 83
Глава 3. Упрощенные стратегии 84
3.1. О стратегиях 84
3.2. Способы получения упрощенных стратегий 89
3.3. Об оптимизации поиска рисков 94
3.4. Результаты численной оптимизации 96
3.5. Упрощенные стратегии для параллельной обработки с группами различного размера 99
3.6. Выводы к третьей главе 101
Заключение 103
Список литературы 105
- Поиск минимаксных стратегии и риска как байесовских
- Влияние размеров групп для параллельной обработки на минимаксный риск
- Возможные дальнейшие усовершенствования
- Упрощенные стратегии для параллельной обработки с группами различного размера
Введение к работе
Актуальность темы исследования. На практике часто встречаются задачи, требующие принятия решений на основе неполных данных. При решении таких задач лицо, принимающее решения, (ЛПР) пытается в процессе управления обеспечить достижение целей, не зная заранее, какие действия приведут к их достижению. Хорошо, если есть возможность предварительно изучить среду, в которой ведется управление, определить ее реакцию на различные действия ЛПР. В таком случае можно было бы заранее задать последовательность действий, ведущую к достижению целей управления. Но что делать, если предварительное изучение системы невозможно, например из-за временных или экономических соображений? В таком случае оценка параметров системы перестает быть самостоятельной задачей и становится лишь вспомогательной процедурой в процессе достижения цели управления.
Упрощенно можно описать рассматриваемую модель управления следующим образом: есть несколько шагов, на каждом из которых ЛПР необходимо выбрать одно из двух действий. На выбор каждого из действий ЛПР получает реакцию среды, интерпретируемую как доход. При этом реакция является случайной величиной и зависит только от выбранного на данном шаге действия. Аналогичные модели описываются в задачах о целесообразном поведении в стационарной случайной среде, двуруком бандите и в задаче адаптивного управления.
Алгоритмы, решающие такие задачи, могут быть использованы для получения стратегий управления в случае зашумления результатов экспериментов или недостоверной информации о среде. При этом главной целью управления является получение максимального «дохода», а не уточнение параметров среды.
В данной диссертации рассматривается оптимизация размеров групп при применении таких задач к параллельной обработке данных, а также способы упрощения получаемых стратегий управления.
Представим, что нам необходимо обработать очень большой объем данных. Для обработки имеется два способа, которые с вероятностями 1 и 2 соответственно приводят к успешной обработке. Разбив данные на группы и применяя ко всем данным в группе один и тот же способ обработки, мы можем использовать количество успешно обработанных данных в качестве дохода. При использовании параллельной обработки мы можем уменьшить необходимое количество этапов, при этом не сильно потеряв в качестве обработки.
Стратегии, получение которых описано в данной диссертации, имеют пороговый характер и для их хранения требуется некоторый объем памяти. Применение такой пороговой стратегии — простая задача, которая может быть реализована даже на устройствах с очень ограниченными ресурсами. Для применения в подобных устройствах полезным может оказаться минимизация объема памяти, требующегося для хранения стратегии.
Исходя из вышесказанного, работу можно назвать актуальной.
Степень разработанности темы исследования. В настоящее время существует множество методов решения задачи об оптимальном управлении для последовательного варианта с конечным и бесконечным горизонтом. Для рассматриваемой стационарной случайной среды имеются результаты по нахождению минимаксных стратегий как байесовских для наихудшего априорного распределения.
Цели и задачи диссертационной работы. Целью диссертационной работы является получение оптимальных стратегий для параллельной обработки данных в двухальтернативной среде. Для достижения поставленной цели решены следующие задачи:
-
Создание модели параллельной обработки данных с использованием групп различного размера.
-
Создание численного метода нахождения оптимальных размеров групп для параллельной обработки данных.
-
Исследование способов упрощения стратегий и влияния упрощений на полученные доходы.
-
Разработка комплекса программ для исследования параллельной обработки.
Научная новизна. В диссертации описывается два усовершенствования для алгоритма параллельной обработки данных в двухальтернативной среде, а именно: параллельная обработка с различными размерами групп и применение упрощенных стратегий. Описанные усовершенствования и результаты экспериментов по их применению являются новыми результатами.
Теоретическая и практическая значимость. Результаты, изложенные в диссертации, могут быть использованы для обработки данных, определения наилучшей стратегии поведения при наличии двух альтернативных вариантов обработки. Данные результаты могут быть полезны в системах, которые не позволяют тестировать различные варианты управления до эксплуатации (например, из-за невозможности достаточно точно смоделировать реальные условия), но при этом позволяют проводить несколько экспериментов одновременно, то есть применять параллельную обработку.
Методология и методы исследования. В диссертационной работе используются: теории игр, теория вероятностей и теории адаптивного управления. Также использованы численные методы для реализации предложенных алгоритмов.
Положения, выносимые на защиту. На защиту выносятся следующие положения:
-
Модель двухальтернативной параллельной обработки данных с группами различного размера.
-
Численный метод поиска оптимальных размеров групп для параллельной обработки данных.
-
Численные методы упрощения стратегий параллельной обработки данных.
-
Комплекс программ для поиска минимаксных стратегий и рисков для обработки данных (параллельной и нет), моделирования применения полученных стратегий и решения вспомогательных задач, возникающих при их исследовании.
Степень достоверности и апробация результатов. Достоверность результатов подтверждается корректными математическими выкладками и согласованностью результатов расчетов и численного моделирования. Также о достоверности результатов свидетельствует их согласованность с оценками и результатами, полученными другими авторами.
Основные результаты диссертации докладывались на следующих конференциях:
-
XIX научная конференция преподавателей, аспирантов и студентов НовГУ, 2 – 7 апреля 2012 г., Великий Новгород.
-
8-я международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 2 – 9 июня 2012 г., Петрозаводск.
-
55-я научная конференция МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе», 19 – 25 ноября 2012 г., Долгопрудный, Московская обл.
-
XX Всероссийская Школа-коллоквиум по стохастическим методам/XIV Всероссийский симпозиум по прикладной и промышленной математике, 12 – 18 мая 2013 г., Йошкар-Ола.
-
XIV Всероссийский симпозиум по прикладной и промышленной математике, 29 сентября – 5 октября 2013 г., Великий Новгород.
6. 56-я научная конференция МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе», 25 - 30 ноября 2013 г., Долгопрудный, Московская обл.
А также на следующих семинарах:
1. Семинар кафедры прикладной математики и информатики Новгородского государственного университета им. Ярослава Мудрого, 19 ноября 2013 г., Великий Новгород.
Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК [, ], 1 статья в сборнике трудов конференций [, 1 депонированная рукопись [ и 5 тезисов докладов [-. Получено свидетельство на разработанную программу для ЭВМ [].
Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы. Общий объем диссертации — 111 страниц, включая 18 рисунков. Список литературы содержит 69 наименований.
Поиск минимаксных стратегии и риска как байесовских
В данной работе используется доказанная в [10] возможность поиска минимаксного риска как байесовского для наихудшего априорного распределения. Ниже кратко опишем основные положения [10]. Ключевым моментом в доказательстве является аналог основной теоремы теории игр (задача рассмотрена как игра с природой, где Е — множество решений лица, осуществляющего управление, G — множество решений природы):
Теорема 1. Рассматриваемая игра имеет цену и минимаксные стратегии обоих игроков. Иными словами, существуют наихудшее априорное распределение А0 на О и минимаксная смешанная стратегия /т на Е, такие что
Распределения {Л} можно со сколь угодно высокой точностью считать имеющими плотности. Множества {/І} и Е совпадают, поэтому с учетом равенств supi-д-і L( 7, Л) = sup0 Ь (а, в), inf L/v( 7, Л) = R (A) из (1.27) следует, что т.е. минимаксная стратегия и риск совпадают с байесовскими на наихудшем априорном распределении.
Здесь Л — распределение решений природы (смешанная стратегия), /І — аналогичное распределение для решений лица, осуществляющего управление. Поиск наихудшего распределения основан на следующих результатах:
Лемма 1. Перечисленные ниже преобразования X априорной плотности распределения X не меняют байесовский риск, т. е. R (X) = R (X):
Изменим параметризацию, а именно: положим mi = и + г , Ш2 = и — У. Тогда в = (и + v,u — v), О = {в : \v\ с}. В новых переменных априорную плотность распределения обозначим v(u,v). Из леммы 1 следует, что байесовский риск не изменяется при следующих преобразованиях априорного распределения:
Отсюда следует, что наихудшее априорное распределение всегда может быть выбрано симметрическим, т. е. іу(и,у) = v(u,—v). Действительно, в случае, если и(и у) является наихудшим, но не является симметрическим, то 0,Ь(іу(и,у) + v(u, —v)) является симметрическим и в силу леммы 1 и леммы 2 выполняется следующее неравенство:
Аналогично плотность 0,5(z/(w+m, v)+v(u, У)) не уменьшает байесовский риск по сравнению с v(u,v), но является более однородной по и, чем v(u,v). Окончательно свойства наихудшего априорного распределения могут быть сформулированы в виде теоремы.
Теорема 2. Не уменьшающая байесовский риск плотность распределения при а — оо может быть выбрана в виде где ka(u) — постоянная плотность на отрезке \и\ а, а р(у) — симметрическая плотность (т.е. р(—у) = p(v) ) на отрезке \у\ с. Теорема 2 позволяет написать уравнения для вычисления байесовского риска. Вычисления основаны на рекуррентном вычислении рисков R1,2{Z\
Теорема 2 дает основу для численного поиска минимаксной стратегии как байесовской, а теорема 3 задает формулы для поиска рисков методом динамического программирования. Будем считать, что плотность () вырожденная, и она сосредоточена в двух точках = ± 1 2 с вероятностями 1/2. Такое предположение позволяет провести поиск наихудшего распределения при помощи численного моделирования. Действительно, у нас получается множество где = 1 2. характеризующее все априорные распределения на множестве , удовлетворяющие нашему предположению. Таким образом, каждое распределение характеризуется только параметром . Теперь для поиска наихудшего распределения достаточно применить какой-нибудь метод численной однопара-метрической оптимизации.
На рисунке 1.1 показаны результаты вычисления байесовского риска для = 15 и различных (сплошной линией). Здесь — приведенный байесовский риск, = -1/2. На графике видно, что существует такое , при котором риск максимальный. Это значение и характеризует наихудшее априорное распределение. На том же графике видно, что наихудшее распределение зависит от ограничения на допустимые значения параметра . Действительно, при = 5,5, которому соответствует график на рисунке 1.1, наихудшее распределение имеет место при = 5,5, однако при уменьшении до 4,3, наихудшему распределению будет уже соответствовать = 1,7.
Объяснение поведения графика зависимости потерь от величины следующее: когда становится слишком большой, общие потери в основном определяются потерями на первых двух шагах. Если же достаточно мала, то общие потери определяются потерями на всем горизонте управления. Поэтому нас больше интересуют среды, для которых не слишком велико (например, не выше 4,3 для описанного случая).
Данный факт может быть проиллюстрирован пунктирной линией на рисунке 1.1. Этой линией показаны риски для всех шагов, кроме первых двух. Видно, что при увеличении такие риски достаточно быстро начинают убывать, и имеют максимум в точке = 1,7.
Заметим, что при увеличении горизонта управления можно снизить влияние первых двух шагов на общие потери и увеличить границу значений , при которых потери зависят от управления на всем горизонте управления.
Для каждого значения байесовский риск может быть найден методами динамического программирования с использованием рекуррентных формул, описанных в теореме 3. Наихудшему априорному распределению должно соответствовать значение , для которого байесовский риск максимальный. Стратегия, соответствующая максимуму байесовского риска, может быть запомнена.
Следующий шаг состоит в вычислении ожидаемых потерь от применения данной стратегии. График зависимости приведенных потерь от значения в сравнении с рисками показан на рисунке 1.2. Сплошной линией показаны байесовские риски для различных значений , пунктирной линией — ожидаемые потери при применении полученной стратегии. Как видно из графика, ожидаемые потери не превосходят значения максимального байесовского риска при всех исследованных , и только в точке, соответствующей наихудшему распределению, байесовский риск равен ожидаемым потерям (это подтверждает, что найденная стратегия является минимаксной).
Влияние размеров групп для параллельной обработки на минимаксный риск
На основе описанных в предыдущем разделе сведений можно начать исследование влияния размеров групп данных на минимаксный риск. Обозначим через Mo,... , Mk текущее разбиение. При этом МІ 0 для 0 і к. Будем считать к фиксированной константой, то есть менять будем только размеры групп данных, но не их количество.
Возьмем для примера N = 16, к = 6. Результаты для одного из разбиений с такими параметрами N и к уже представлен на рисунке 2.1. При этом на том же рисунке показано сравнение байесовских рисков, соответствующих параллельной обработке с различными размерами групп, и рисков, соответствующих обработке с равными размерами групп. Теперь для большей наглядности покажем на рисунке 2.2 результаты вычисления байесовского риска для разбиений М 1 (показаны сплошной линией) и М 2 (показаны пунктирной линией): MQ = 1, М[ = 2, М2 = 2, М% = 2, М\ = 2, Mg = 2, MQ = 4 и MQ = 2, М\ = 2, М\ = 2, М% = 2, М\ = 2, Mg = 2, MQ = 2.
Видно, что М 2 — это самое простое из возможных разбиений: в каждой группе одинаковое количество данных. М 1 — простая попытка усовершенствовать предыдущее разбиение. Действительно, есть предположение, что линейный характер роста рисков при увеличении d вызван потерями при обработке первых двух групп данных. Для нашего первого разбиения М 2 мы вынуждены как минимум два раза использовать худшее действие. Попробуем изменить это и уменьшим размер первых двух групп. Освободившиеся данные необходимо поместить в какую-то другую группу. Интуитивно кажется, что наилучшего результата мы добьемся, увеличивая размер групп с увеличением достоверности информации о среде (доходах за применение действия). По этой причине переместим освободившиеся данные в последнюю группу, таким образом, мы получим разбиение М 1 .
На рисунке видно, что даже небольшое изменение разбиения может сильно изменять байесовские риски. Однако следует отметить, что столь значительные изменения являются следствием изменения первой группы (MQ). Действительно, стратегия для М 2 предписывает в начале управления выбрать
Риски для различных разбиений на группы для параллельной обработки каждое действие по два раза, и если разница между математическими ожиданиями достаточно высока — потери на первых двух этапах обработки уже не смогут быть компенсированы за счет дополнительной информации, полученной на них. На рисунке мы видим, что потери растут почти линейно с увеличением разницы математических ожиданий.
Таким образом, мы видим, что различным разбиениям на группы будут соответствовать различные минимаксные стратегии и риски даже в случае одинакового числа групп. Возникает закономерная цель — найти такое разбиение, значение минимаксного риска для которого было бы минимальным. 2.3. Оптимизация размеров групп для параллельной обработки
Как сказано в предыдущем разделе, рекуррентные формулы (2.8) - (2.12) позволяют найти байесовский риск для заданных размеров групп МІ. Основная же задача в поиске оптимальных планов параллельной обработки — это нахождение оптимальных размеров таких групп.
Методика нахождения минимаксных стратегии и риска для заданного разбиения данных на группы Мо, Мі,..., М& как байесовских показана выше. Такой минимаксный риск можно обозначить как Д(Мо, Mi,..., Mk) при 2Мо + + Mk = N. Этот риск зависит от с и от разбиения Mo, Mi,... , Mk. Задача состоит в поиске оптимального разбиения
Получившаяся задача является задачей условной оптимизации. Из-за достаточно сложных ограничений на переменные (ограничения на сумму и на дискретность изменений) для решения этой задачи была использована модификация алгоритма покоординатного спуска.
Для начала рассмотрим применение предлагаемого алгоритма на примере. Пусть нам необходимо найти оптимальное разбиение для N = 8, к = 3. Вся работа алгоритма делится на два этапа: основной этап и дополнительные проверки. На основном этапе размеры каждой из групп последовательно перебираются среди всех возможных значений. Это означает, что для каждого М , начиная с Мо, будут перебираться все возможные размеры, начиная с 1. При этом все М , где і больше номера обрабатываемой в данный момент группы, будем пытаться сделать равными (в случае, если это невозможно, будем делать необходимое количество последних групп больше на единицу). Итак, для нашего примера первым разбиением, которое необходимо проверить, будет Мо = 1, Мі = 2, М2 = 2, М3 = 2 (соответствует первой итерации на
На данном рисунке показано, как будет проводиться перебор для описанного примера. Обведены размеры групп, которые перебираются на соответствующей итерации. Итак, после проверки первого разбиения мы должны построить второе. Для этого увеличиваем размер 0 на единицу. Поскольку 0 определяет размер первых двух групп, сумма размеров остальных групп должна быть уменьшена на единицу (как это показано на рисунке). Дальше увеличивать 0 невозможно, поскольку в таком случае размер какой-то из оставшихся групп будет равен нулю, что исключено постановкой задачи.
Это означает, что мы закончили перебор размеров 0 и теперь должны выбрать лучший вариант из итераций 1 – 2. Пусть для определенности это будет результат первой итерации. Найденное на предварительном этапе лучшее 0 равняется единице.
Возможные дальнейшие усовершенствования
Можно предложить следующие пути улучшения данных результатов:
1. Улучшение алгоритма для возможности применения для большего числа шагов.
2. Модификация для ограниченных возможностей параллельного выполнения (ограничение на максимальное количество одновременно обрабатываемых данных).
3. Изучение применимости данного алгоритма оптимизации размеров групп для параллельной обработки к другим подходам к задаче о целесообразном поведении (двуруком бандите).
Первый вариант связан с уже указанной выше проблемой — на данный момент на некотором этапе применения алгоритма производится полный перебор вариантов для количества шагов в группе. Данное решение применимо в основном за счет небольшого числа шагов и групп и при их увеличении скорее всего придется искать более оптимальное решение.
Вторая идея состоит в следующем: в текущей реализации ограничением для оптимизации является только количество групп. Однако для практического применения может быть интересен также случай, когда возможности для параллельной обработки ограничены (действительно, как правильно приходится иметь дело с конечным числом «обработчиков»). В таком случае было бы логично иметь также возможность проводить оптимизацию с учетом этого ограничения. Возможно также рассмотрение задачи, в которой существует ограничение на количество одновременно обрабатываемых данных и поставлена задача за минимальное количество этапов управления достичь заданных ожидаемых потерь.
Что касается третьей идеи, то действительно, текущая версия использует наработки по минимаксному подходу. Однако, возможно, его также можно применить к другим подходам и способам поиска стратегий. Несмотря на важность этой задачи, применение его к другим подходам или использование описанного метода при обработке данных с распределениями результатов, чьи суммы далеки от нормального (не выполняется закон больших чисел), в данной работе не рассматриваются.
Вторая глава была посвящена описанию общих идей параллельного выбора действий в задаче об управлении в случайной среде и применения предложенных приемов для параллельной обработки данных. Основная идея — разбить все шаги управления на заранее заданное количество групп и внутри каждой группы применять ко всем шагам одно и то же действие одновременно. Описаны алгоритмы, позволяющие искать оптимальное разбиение шагов на группы для параллельной обработки, и приведены результаты работы программы, реализующей данные алгоритмы.
Полученные результаты соотносятся с асимптотическими оценками минимаксного риска Фогеля [67], Фабиуса и ван Цвета [44].
Приведено описание программ из состава комплекса программ, которые занимаются предложенными и вспомогательными задачами.
Основные результаты второй главы были представлены на 8-ой международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (2 – 9 июня 2012 г., Петрозаводск) и 55-ой научной конференции МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе» (19 – 25 ноября 2012 г., Долгопрудный, Московская область), а также опубликованы в работах [16, 24].
Упрощенные стратегии для параллельной обработки с группами различного размера
Во второй главе описан способ получения минимаксных стратегий для параллельной обработки с группами различного размера. В данной главе описаны различные способы получения упрощенных стратегий для обработки, где управление можно менять на каждом шаге (что соответствует нормальному распределению или бинарным результатам в группах одинакового размера). Логично проверить, насколько идеи про упрощение стратегий подходят к стратегиям из второй главы.
Действительно, стратегии для параллельной обработки в случае различных размеров групп выглядят похожим образом с одним отличием. Пороговые значения существуют только для тех шагов, на которых в очередной раз необходимо принимать решение. Таким образом применимы все представленные в третьей главе методы упрощения.
Для примера показано упрощение стратегий, полученных для параллельного управления на 30 шагах с различными размерами групп (всего 15 групп). Применялись все модификации первого метода упрощения. Потери, полученные при моделировании полученных стратегий, представлены на рисунке. Из рисунка видно, что ситуация практически не изменилась из-за применения параллельного управления с различными размерами групп, упрощения по прежнему незначительно ухудшают стратегию.
На рисунке 3.7 показано сравнение потерь, полученных при моделировании точной и упрощенных стратегий для параллельного управления с различными размерами групп. На рисунке сплошной линией показаны потери при применении точной минимаксной стратегии. Пунктирными линиями показаны потери для упрощенных стратегий, в порядке уменьшения длины штриха: упрощенная при помощи второй модификации, третьей модификации и первой модификации первого способа получения упрощенных стратегий. Размеры групп для всех стратегий были одинаковы (их получение описано в предыдущей главе) и составляли: 0 = 1, 1 = 2, 2 = 1, 3 = 2, 4 = 1, 5 = 1, 6 = 2, 7 = 1, 8 = 2, 9 = 2, 10 = 2, 11 = 3, 12 = 3, 13 = 6. Упрощенные стратегии были получены на основе минимаксной для данного разбиения на группы. Как видно из рисунка, упрощение стратегий практически не повлияло на их качество. Разница между худшими результатами для точной и упрощенных стратегий не превышают 1,3%.
Необходимо также отметить, что эффективность таких упрощений также будет на уровне стратегий для = 15, а именно 26 точек для упрощенной стратегии против 42 для точной, то есть меньше чем в два раза.
Третья глава была посвящена более подробному описанию рассматриваемых стратегий управления, способам их представления и связанных с ними способам получения и хранения упрощенных стратегий. Также были рассмотрены проблемы, возникшие при реализации алгоритмов упрощения, и пособы их решения.
Описанные способы получения упрощенных стратегий позволяют табулировать стратегии с использованием меньшего количества информации и при этом получать приемлемое ухудшение результатов управления. Также данные эксперименты показывают, что найденные по рекуррентным формулам из [10] стратегии обладают устойчивостью к небольшим изменениям. Для = 15 и = 30 не найдено упрощенных стратегий, имеющих максимальные потери меньшие, чем у точной стратегии, что согласуется с теорией.
Основные результаты третьей главы были представлены на XX Всероссийской Школе-коллоквиуме по стохастическим методам/XIV Всероссийском симпозиуме по прикладной и промышленной математике (весенняя сессия, 12 – 18 мая 2013 г., Йошкар-Ола), XIV Всероссийском симпозиуме по прикладной и промышленной математике (осенняя сессия, 29 сентября – 5 октября 2013 г., Великий Новгород.), 56-й научной конференции МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе» (25 – 30 ноября 2013 г., Долгопрудный, Московская обл.).
