Содержание к диссертации
Введение
Глава 1. Теоретические сведения 13
1.1. Обзор литературы по теме 13
1.2. Общая постановка задачи 22
1.3. О потерях дохода при близких и удаленных математических ожиданиях 26
1.4. Выводы к первой главе 29
Глава 2. Пороговые стратегии управления 30
2.1. Стратегия управления с одним порогом 30
2.2. Решение задачи о «двуруком бандите» для бинарной случайной среды 33
2.3. Решение задачи о «двуруком бандите» для среды с нормально распределенными доходами 38
2.4. Проверка гипотезы об оптимальности пороговой стратегии, найденной для единичной дисперсии, для сред с нормально распределенными доходами с попарно различными дисперсиями 41
2.5. Оптимизация алгоритма «двурукого бандита» 41
2.6. Модификация пороговой стратегии. Двухпороговая стратегия управления 44
2.7. Формулировка цели управления 47
2.8. Моделирование двухпороговых стратегий 48
2.9. Моделирование двухпороговой стратегии в бинарной случайной среде 50
2.10. Двухпороговая стратегия управления в случайной среде с нормально распределенными доходами 53
2.11. Выводы ко второй главе 56
Глава 3. Управление в случайной среде, использующее основную теорему теории игр 58
3.1. Связь минимаксного и байесовского подходов и основная теорема теории игр 58
3.2. Вывод уравнений для вычисления байесовских рисков с попарно одинаковыми различными на действиях дисперсиями 59
3.3. Нахождение байесовских потерь и стратегий, численная оптимизация 62
3.4. Моделирование методом Монте-Карло 65
3.5. Проверка гипотезы об оптимальности байесовской стратегии, найденной для единичной дисперсии, для класса сред с различными дисперсиями 66
3.6. Случай попарно различных дисперсий 68
3.7. Численная оптимизация байесовских рисков при различных попарно разных дисперсиях 75
3.8. Выводы к третьей главе 75
Глава 4. Программный комплекс 77
4.1. Программа TwoArmed 77
4.2. Программ Bayes 84
4.3. Выводы к четвертой главе 87
Заключение 88
Литература
- О потерях дохода при близких и удаленных математических ожиданиях
- Проверка гипотезы об оптимальности пороговой стратегии, найденной для единичной дисперсии, для сред с нормально распределенными доходами с попарно различными дисперсиями
- Двухпороговая стратегия управления в случайной среде с нормально распределенными доходами
- Проверка гипотезы об оптимальности байесовской стратегии, найденной для единичной дисперсии, для класса сред с различными дисперсиями
Введение к работе
Актуальность темы исследования. Задачи управления в условиях неопределенности в последние годы получают всё большую актуальность в различных областях человеческой деятельности: медицина, web-поиск, интернет-реклама, компьютерные сети и др. Рассматриваемую в данной работе задачу можно описать следующим образом. Имеются два альтернативных действия, каждое применение которых ведет к получению некоторого дохода. Доходы являются случайными, их распределения фиксированы и зависят только от текущих применяемых действий, но неизвестны лицу, принимающему решения (ЛПР). Наиболее известным приложением является задача о лечении пациентов, когда имеются два альтернативных лекарства с фиксированными, но неизвестными эффективностями. Требуется организовать лечение таким образом, чтобы математическое ожидание количества выздоровевших в результате лечения пациентов было максимальным. Здесь можно отметить работы «Асимптотически эффективные адаптивные правила распределения» Т. Лая, Г. Роббинса (Lai T. L., Robbins H. Asymptotically Efcient Adaptive Allocation Rules, 1985) и «Модели многоруких бандитов для оптимального управления клиническими испытаниями: достоинства и недостатки» С. Виллар (Villar S. S. et al. Multi-armed bandit models for the optimal design of clinical trials: benefts and challenges, 2015). Другое известное приложение — оптимизация обработки данных двумя альтернативными методами с фиксированными, но априори неизвестными эффективностями. Такая задача рассматривалась, например, в работе «Современный байесовский взгляд на многоруких бандитов» С. Скотта (Scott S. L. A modern Bayesian look at the multi-armed bandit, 2010). Отметим, что при решении этих задач может использоваться параллельная обработка. В задачах лечения пациентов количество этапов обработки является небольшим, обычно два, редко три–четыре. В задачах же обработки данных допускается большое число этапов, например, 30–50. Так как данные при параллельной обработке суммируются, то в силу центральной предельной теоремы для управления используются нормально распределенные значения доходов. В зависимости от рассматриваемой постановки задачи дисперсии этих доходов могут иметь попарно одинаковые или различные значения.
Наиболее известными постановками цели управления являются минимаксная и байесовская. Байесовская постановка рассматривается, например, в работах «Последовательное управление по неполным данным» Э. Пресмана, И. Сонина, 1982 г. и «Проблемы бандитов. Последовательное распределение экспериментов» Д. Берри, Б. Фриштеда (Berry D. A., Fristedt B. Bandit problems. Sequential Allocation of Experiments, 1985). Достоинством байесовского подхода является то, что он позволяет для любого априорного распределения найти байесовские стратегии и риск численными методами. Недостатком подхода является отсутствие ясных критериев выбора априорного распределения. Достоинством минимаксного подхода является его робастность, а недостатком — сложность нахождения робастных алгоритмов, поскольку прямые методы нахождения их отсутствуют. Примерами робастных алгоритмов являются алгоритм на основе метода стохастической аппроксимации («Адаптивный выбор вариантов» А. Назина, А. Позняка, 1986 г.) и алгоритм зеркального спуска («Оценки для стохастического многорукого бандита» А. Юдицкого, А. Назина, А. Цыбакова, Н. Ваятиса (Juditsky A. B., Nazin A. V., Tsybakov A. B., Vayatis N. Gap-free Bounds for Stochastic Multi-Armed Bandit, 2008) и «Об эффективности одного метода рандомизации зеркального спуска в задачах online оптимизации» А. Гасникова, Ю. Нестерова, В. Спокойного, 2015 г.). Отметим, что версии этих алгоритмов, допускающие параллельную обработку, насколько нам известно, не разрабатывались.
Байесовский и минимаксный подход объединяет основная теорема теории игр, согласно которой минимаксные стратегии и риск ищутся как байесовские, соответствующие наихудшему априорному распределению. Эту теорему можно использовать, если такое распределение удается характеризовать.
Таким образом, актуальной является разработка робастных (минимаксных) алгоритмов, с помощью которых осуществляется параллельная многоэтапная обработка данных. Математически эта задача описывается как управление в случайной среде с нормально распределенными доходами, характеризуемыми различными дисперсиями. В качестве основного инструмента для нахождения минимаксных стратегии и риска используется основная теорема теории игр.
Цели и задачи диссертационной работы. Целью диссертационной работы является нахождение минимаксных стратегий и рисков в средах с бинар-
ными и нормально распределенными доходами, характеризуемыми различными дисперсиями.
Для достижения поставленных целей были решены следующие задачи:
-
Разработка математической модели оптимизации групповой обработки данных, если для обработки используются два альтернативных метода с фиксированными, но неизвестными эффективностями.
-
Исследование методами математического моделирования одно- и двухпо-роговых стратегий, обеспечивающих робастное управление в случайной среде, характеризуемое неулучшаемым по порядку величины максимальным значением функции потерь.
-
Разработка алгоритмов, позволяющих искать минимаксные стратегии и риски численными методами как байесовские, соответствующие наихудшему априорному распределению параметров среды c различными дисперсиями.
-
Разработка комплекса программ, который позволяет численными методами находить минимаксные стратегии и риски.
Научная новизна. Научная новизна работы заключается в разработке модели групповой обработки данных, которая математически описывается как задача об управлении в случайной среде с доходами, имеющими нормальное распределение с произвольными дисперсиями. Известные стратегии групповой обработки допускали малое число этапов обработки: обычно два, редко три-четыре. Предложенные в работе стратегии допускают большее число этапов, например 30–50. Такое число этапов позволяет вести обработку практически без потери качества, то есть без увеличения минимаксного риска. Нахождение минимаксных стратегий и рисков выполнено численными методами с использованием свойства инвариантности и основной теоремы теории игр, то есть минимаксные стратегии и риск ищутся как байесовские, соответствующие наихудшему априорному распределению.
Практическая значимость. Практические результаты, полученные в диссертации, могут быть использованы в различных задачах о лечении пациентов, для параллельной обработки данных и нахождения оптимальных
стратегий управления. Полученные результаты могут применяться в системах, предварительное тестирование которых либо невозможно, либо нецелесообразно в силу различных причин.
Методология и методы исследования. В диссертации используются: теория вероятностей, теория игр, адаптивное управление. Для численного моделирования и программной реализации разработанных алгоритмов применяются методы вычислительной математики и прикладного программирования.
Положения, выносимые на защиту: на защиту выносятся следующие положения:
-
Модель параллельной обработки данных, которая описывается управлением в случайных средах с нормально распределенными доходами с произвольными дисперсиями.
-
Численный метод определения оптимальных параметров одно- и двухпо-роговых стратегий управления.
-
Численный метод нахождения минимаксных рисков и стратегий как байесовских, соответствующих наихудшему априорному распределению, для случайных сред с различными дисперсиями.
-
Комплекс программ для моделирования двухальтернативных случайных сред с бинарными и нормально распределенными доходами с различными дисперсиями, разработанный для обработки численными методами данных, получения и применения стратегий управлений и решения вспомогательных задач, возникших при исследований.
Степень достоверности и апробация результатов. Данные расчетов, полученных в работе, соответствуют результатам проведенных численных моделирований. Кроме того, для ряда полученных результатов установлена согласованность с уже известными, полученными другими авторами.
Основные результаты диссертации докладывались на следующих конференциях:
1. XVI, XVII, XVIII, XIX, XXIII научные конференции преподавателей, аспирантов и студентов НовГУ, 2009–2016 гг., Великий Новгород.
-
XIV Всероссийский симпозиум по прикладной и промышленной математике, 29 сентября — 5 октября 2013 г., Великий Новгород.
-
57-я международная научная конференция МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе», 24 — 29 ноября 2014 г., Долгопрудный, Московская обл.
-
58-я научная конференция МФТИ с международным участием, 23 — 28 ноября 2015 г., Долгопрудный, Московская обл.
-
IX Международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 30 мая — 3 июня 2016 г., Петрозаводск, Россия.
А также на семинарах кафедры прикладной математики и информатики Новгородского государственного университета имени Ярослава Мудрого.
Результаты исследований внедрены в учебный процесс Новгородского государственного университета имени Ярослава Мудрого в рамках дисциплины «Модели искусственного интеллекта».
Публикации. Материалы диссертации опубликованы в 11 печатных работах, из них 4 статьи в рецензируемых журналах, рекомендованных ВАК [–], 3 статьи в сборниках трудов конференций [–] и 4 тезиса докладов [–].
Комплексы программ:
Свидетельство о государственной регистрации программы для ЭВМ «Оптимизация параметров пороговой стратегии управления в случайной среде» № 2012614942, зарегистрирована в Реестре программ для ЭВМ 1 июня 2012 г.
Свидетельство о государственной регистрации программы для ЭВМ «Моделирование случайных сред с одно- и двухпороговой стратегиями управления в случайной среде» № 2013617255, зарегистрирована в Реестре программ для ЭВМ 06 августа 2013 г.
Свидетельство о государственной регистрации программы для ЭВМ «Расчет байесовских рисков, потерь и стратегий управления для случайных сред с нормально распределенными доходами с произвольными дисперсиями» № 2016619416, зарегистрирована в Реестре программ для ЭВМ 18 августа 2016 г.
Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы. Общий объем диссертации 96 страниц, включая 24 рисунка и 3 таблицы. Список литературы включает 64 наименования.
О потерях дохода при близких и удаленных математических ожиданиях
Идентификационный подход к управления в адаптивных системах был предложен в книгах В. Г. Сраговича [37, 38, 61], в которых обобщены его результаты и результаты его учеников. Идея идентификационного подхода состоит в том, что вероятности выигрыша на действиях среды р\ и р2 в каждый момент времени оцениваются по формулам - 1 - ґ \ -Х-2 Т)л I ) = Т)сл I J = где ti, h — количество применений действий к моменту времени t = t\ + 2 (t\ + 2 = t), X\, X2 — текущие доходы за применение действий. Стратегией управления может являться следующая. Для получения начальной статистики каждое из действий применяется одинаковое количество п раз. При всех t 2п с вероятностью 1 — 5 применяется то действие, которому соответствует большая из текущих оценок вероятностей pi(t), P2{t), а с вероятностью 5 — меньшая из оценок. Здесь 6 0 — некоторое малое число. Чем меньше 5 0, тем предельный средний доход выше. Если вместо постоянного 5 0 рассмотреть последовательность 6t, такую что lim St = О, t—7 00 а 2 St = 00, то такая стратегия обеспечит максимально возможное значение предельного среднего дохода.
В работе [13] рассмотрены адаптивные стратегии, позволяющие достигать цели в условиях информационной неопределенности, основываясь на «обучении» в процессе взаимодействия с некоторым объектом. Работа посвящена теоретическим аспектам адаптивного подхода.
В более поздней статье [14] рассматривается пример практического применения теории адаптивного управления. А именно, приводится пример работы сервера, который на конечном числе процессоров выполняет задания, поступающие из случайного потока. Прием задания на обслуживание приносит доход, но сопряжен с возможным штрафом в случае невыполнения задания в срок. Сформулирована задача оптимизации доступа заданий в систему с точки зрения увеличения предельного среднего дохода.
Из недостатков идентификационного подхода можно отметить отсутствие методов для применения в параллельном управлении.
Алгоритм зеркального спуска представляет собой обобщение стандартного метода градиента для задач выпуклой оптимизации в условиях априорной неопределенности. В ряде случаев он имеет преимущество перед другими алгоритмами поиска экстремума при высокой размерности: его гарантируемая скорость сходимости значительно выше. Алгоритм находит применение в прикладных задачах, например: томография [47], классификация [43] и ранжирование [31].
Алгоритм зеркального спуска применяется для решения задач о двуруком бандите для неизвестного горизонта управления. Цели управления в целом те же, что и в других подходах, — уменьшение средних потерь полного дохода. В работе [53] получена оценка верхней границы потерь, равная: л/(Т + 1)К\пК Е(Фу) — amin 2сг , Т где Ф(Т) — средние потери доход, Е(Фу) — математическое ожидание средних потерь, amin — математическое ожидание потерь за применение лучшего возможного действия, К — количество действий случайной среды, Т — горизонт управления. Метод, описанный в [53], может быть применен для решения широкого круга задач, например, в [58] описано его применение к Марковскому процессу принятия решений. В [58] получена следующая оценка сверху для средних потерь: і (гп \ 1 1 \ 3 ґжлґл- лт От лтт — (Е(Фу) — 4mm) (Na \n(NK))3 In Т В работе [30] представлен алгоритм зеркального спуска, направленный на минимизацию средних потерь стохастической системы, функционирующей в непрерывном времени, c потерями, возникающими в случайные моменты скачков пуассоновского процесса с известной интенсивностью. Для алгоритма доказана явная верхняя граница превышения средних интегральных потерь над минимумом. Граница имеет вид , где — горизонт управления, — конкретная константа.
В статье [5] предложена рандомизированная онлайн версия метода зеркального спуска. Отличие от имеющихся версий заключается в том, что рандомизация вводится на этапе проектирования субградиента на единичный симплекс. В результате получается покомпонентный субградиентный спуск со случайным выбором компоненты, допускающий онлайн интерпретацию. Показано, что алгоритм может быть применен к решению задач о многоруких бандитах, взвешиванию экспертных решений и поиска равновесия в антагонистической матричной игре с разреженной матрицей.
С развитием интернет-технологий появилась необходимость в новых эффективных методах управления в случайной среде. Например, популярные порталы Mail.ru и Yahoo! содержат на своих домашних страницах множество ссылок. Цель состоит в определении ссылок, дающих максимальный CTR (clickhrough ratio, отношение кликов). Здесь каждый показ ссылки пользователю соответствует применению ручки; каждый клик — успех, положительная реакция среды; не-клик — неудача. Задача алгоритма в том, чтобы как можно быстрее понять, что та или иная ссылка является наиболее посещаемой, и выводить её в заголовок страницы. Одним из современных методов решения подобных задач является достаточно простой в реализации UCB1 [44, 45] (акроним Upper Confdence Bound, верхний доверительный предел).
Проверка гипотезы об оптимальности пороговой стратегии, найденной для единичной дисперсии, для сред с нормально распределенными доходами с попарно различными дисперсиями
В предыдущем разделе мы рассмотрели управление в случайной среде с нормально распределенными доходами и единичными дисперсиями, где нашли оптимальную пороговую стратегию . В данном разделе мы предполагаем, что такая стратегия остается оптимальной не только для единичных дисперсий \ = 2 = 1, но и для сред с дисперсиями \ = 2 1. Поясним, почему имеет смысл рассматривать такие среды. Дело в том, вероятности могут отличаться от рассматриваемой = 0,5. Например, Є [0,1; 0,9]. Поскольку максимальные потери достигаются при близких вероятностях, то можно считать, что дисперсии примерно равны. Для бинарных доходов = (1 — ), поэтому моделирование будем производить для попарно одинаковых дисперсий, выбираемых из условия 0,09 0,25 для множества параметров Є [0; 10]. В случае бинарных сред и горизонте управления = 10 000 максимальные потери будут достигаться при = (0,5,0,48). В случае сред с нормально распределенными доходами — при = 100 и = (0, —0,4).
Мы проверяем наше предположение с помощью моделирования методом Монте-Карло. На рисунке 2.5 приведены некоторые результаты вычислений при конкретных дисперсиях. Видно, что для таких значений стратегия также является минимаксной.
2.5. Оптимизация алгоритма «двурукого бандита»
Главной проблемой многих программ, использующих алгоритмы моделирования Монте-Карло, является их большое время выполнения. В нашем случае время моделирования прямо пропорционально величине , где — Рис. 2.5. Значения функции потерь, полученные методом Монте-Карло при конкретных дисперсиях
горизонт управления, N — количество моделирований. Стоит отметить, что от N напрямую зависит точность получаемых данных, поэтому эта величина не изменяется.
В данном разделе мы рассмотрим два метода оптимизации алгоритма, общие принципы которых были изложены в [26]. Сразу сделаем замечание. Все методы, рассмотренные здесь, не используют упрощенные вычисления, приводящие к потере точности получаемых данных. Другими словами, мы добиваемся лишь сокращения времени выполнения алгоритма ценой его модификации.
Итак, суть первого метода состоит в следующем. Напомним, что для всех рассматриваемых пар (а, /3) доход вычисляется как 1 О о Хт = Хт + Хт + Хт, где Ху, Xj — доходы, полученные на каждом из действий на начальном отрезке времени t Є [1; ], когда действия применяются по очереди, Xj, — доход на заключительном отрезке времени t = t + 1,... ,Т, когда применяется только то действие, которые показало лучшую доходность на первом этапе. Здесь t — момент времени, в который достигнут порог. Поскольку на втором этапе применяется только одно действие, причем время выполнения известно, то можно усовершенствовать алгоритм, не моделируя этот этап, а сразу вычисляя итоговый доход по формуле Хт = Хт + Хт + (Т — t ) ре- (2.6) В силу вышесказанного М(Хт) = М(Хт). Это позволяет нам сократить время моделирования в среднем в два раза.
Следующий метод оптимизации заключается в следующем. Напомним, что алгоритм работы «двурукого бандита» устроен таким образом, что в нем для каждой пары (ai,(3j) вычисляется доход Xij, и этот доход накапливается за все время моделирования при текущих i,j. Здесь і Є [1,7], j Є [1, J], І количество рассматриваемых при моделировании порогов, J — количество параметров среды. Алгоритм можно усовершенствовать, если для набора пороговых констант OL\ (12 оц и очередного зафиксированного параметра (3j при достижении некоторого порога ai(DT)1 2 текущий накопленный доход Xij не обнулять, а продолжать моделирование для следующего порога с + -ОТ)1 2, для которого доход Xi+ij начинает накапливаться с величины Xij. После этого окончательный доход на j-м действии рассчитывается по формуле (2.6). И так далее, до тех пор, пока не истечет время управления. Если время управления истекло при некотором і 7, а наибольший порог aj(DT)1 2 не достигнут, то для всех і + 1,...,/ оставшимся доходам JQ+ij,... ,XJJ присваиваются значения, равные текущему накопленному доходу.
Таким образом формируется двухмерный массив доходов Xij. Затем для каждой пары (i,j) вычисления повторяются N раз согласно формуле (2.5). Вычисления показывают, что при использовании этой оптимизации мы сокращаем время моделирования в среднем в два раза. Стоит упомянуть, что единственным минусом такого подхода является использование еще одного массива данных, который хранит промежуточные вычисления и занимает дополнительное место в оперативной памяти компьютера. Однако речь идет о килобайтах, что при текущем развитии компьютерной техники можно не принимать в расчет.
Таким образом, комбинируя вышеперечисленные методы оптимизации, мы сокращаем время выполнения алгоритма в среднем в четыре раза, при этом не теряя точности вычислений.
В дальнейших разделах этой главы мы модифицируем пороговую стратегию управления. Суть в том, что найденная при = 0,57 пороговая стратегия является оптимальной для рассматриваемого множества {}, но для достаточно больших значений средние потери можно уменьшить. В плане минимизации потерь теоретически оптимальным решением для каждого из рассматриваемого множества {} является нахождение своего оптимального порога . Это демонстрирует рисунок 2.6. На нем линии 2 соответствуют потери, рассчитанные для всех параметров Є [0; 30] при фиксированном пороге fix = 0,57. Здесь же линия 1 показывает потери, вычисленные для того же множества {}, при этом каждому соответствует свое оптимальное ().
Для того, что понять, как формируются потери и как их можно уменьшить, рассмотрим случаи близких и удаленных распределений вероятностей выигрышей на действиях. Как следует из формулы (2.2), параметр определяет близость этих вероятностей, то есть параметр среды = (0,5,2 = 0,5 — ( /)1/2).
Двухпороговая стратегия управления в случайной среде с нормально распределенными доходами
Можно отметить, что все результаты вычислений, полученные выше при 1 = 2 = 1, совпадают с [8]. При остальных дисперсиях проверку можно осуществить с помощью моделирования методом Монте-Карло.
Сделаем замечание. Точность методов численного моделирования, в частности метода Монте-Карло, зависит от количества проведенных испытаний. Под точностью метода в данном случае подразумевается численная разница между величинами потерь, полученных по формулам и при использовании метода Монте-Карло. Эта разница тем меньше, чем больше количество испытаний. Разумеется, при численном моделировании мы вынуждены ограничиться какой-то величиной количества испытаний. В данном случае количество мо 66 делирований бралось равным 1000 000, что позволяет говорить о точности по крайней мере 5 0,01.
Итак, рассчитаем значения функции потерь Іт((ї) при Т = 50 для 0 d 10 с шагом 0,1 и для дисперсий 0,2 D 1 с шагом 0,4. На рисунке 3.3 на одном графике объединены результаты вычислений методом Монте-Карло, а также по формулам (3.9)–(3.12). Видно, что для каждой дисперсии линия функции потерь, рассчитанная методом Монте-Карло, повторяет поведение линии функции потерь, вычисленной по формулам. Отметим, что при увеличении горизонта управления результаты становятся точнее.
В предыдущих разделах главы мы рассмотрели задачу о минимаксном управлении, использующую основную теорему теории игр в случае равных единичных дисперсий доходов, и нашли соответствующую оптимальную стра 67 тегию ст. В данном разделе мы предполагаем, что такая стратегия является минимаксной не только для рассмотренных сред, но также для класса сред с дисперсиями, отличными от единичной.
Мы проверяем наше предположение с помощью моделирования методом Монте-Карло [19]. В данном случае дисперсии доходов Di на действиях среды будут разными и могут принимать различные значения из множества Do Di 1, Do 0, = 1,2. Нам необходимо проверить, что при таких дисперсиях ни одно из значений maxLr( 7,в) при конкретных в = (ші,Ш2) не превысит соответствующего при D\ = D2 = 1. В качестве стратегии а используется стратегия, найденная для D\ = D2 = 1.
Итак, были вычислены значения Ьт(сг,в) для различных пар дисперсий Di Є [0,2; 0,9] с шагом 0,2 для горизонта управления Т = 50 для 0 d 10 с шагом 0,1, где d = \m\ —ГП2\. Некоторые результаты вычислений представлены в таблице 3.1.
В результате анализа вычисленных значений было выявлено, что наше предположение верно, и полученная в случае единичных дисперсий стратегия действительно является минимаксной для дисперсий, меньших, чем единичная. Для некоторых пар дисперсий значения (,) представлены на рисунке (3.4). Здесь же сплошной линией приведены значения при 1 = 2 = 1. Отметим, что при увеличении горизонта управления результаты становятся точнее, но требуют больших затрат времени на моделирование. Рис. 3.4. Значения Ьт(сг, в) для некоторых пар дисперсий, Т = 50
Выше мы рассмотрели случайные среды с произвольными, но попарно равными на действиях дисперсиями. В данном разделе мы рассматриваем похожую постановку задачи, но с обобщением на случай, когда дисперсии на действиях могут принимать попарно различные значения из множества Do D 1, Do 0. описывает плотность нормального распределения с математическими ожиданиями rri и дисперсиями D , = 1,2. Обозначим за Л(ші,Ш2) плотность априорного распределения на множестве параметров G = {в : \v\ С}, ti,t2 — текущие количества применений обоих действий = 1 и = 2 соответственно (t\ +І2 = і), Xi,X2 — текущие доходы на действиях. Пусть Xi = 0 при іц = 0. Апостериорная плотность распредения равна ожидаемые потери на оставшемся горизонте управления (T—t), если сначала применяется 1-е действие ( = 1,2), а затем управление ведется оптимально. Байесовская стратегия предписывает выбирать то действие, кото-рому соответствует меньшее из значений KT_t{-) и любое при их равенстве. На первых двух шагах действия следует применить по очереди.
Характеризация наихудшего априорного распределения Л основана на свойствах непрерывности и вогнутости байесовского риска. Лемма 1. Байесовский риск является вогнутой функцией априорного распределения, то есть для любых плотностей Х\, А2 и положительных чисел а\, а.2, таких что а\ + «2 = 1, справедливо неравенство RT{(1\\\ + СК2А2) (1\RT{\\) + О Ду ). (3.16) Доказательство. Свойство (3.16) следует из цепочки неравенств R {(i\X\ + СК2А2) = ini (aiLr(a", Ai) + «2 7(0", A2)) OL\ ini Lr(cr, Ai) + «2infs Lr(cr, A2) = «ii?y (Ai) + «2-Ry (A2). Свойство (3.16) означает, что если для некоторых плотностей А, А байесовские риски равны, т.е. R (X) = R (А), то байесовский риск на смеси плотностей не меньше исходного R ,(aX + аХ) R (А).
Проверка гипотезы об оптимальности байесовской стратегии, найденной для единичной дисперсии, для класса сред с различными дисперсиями
Моделирование стратегий с одиночным порогом производится с помощью соответствующих функций программы. Приведем здесь формальный алгоритм вычисления величины потерь для бинарной случайной среды, а также листинг соответствующей функции. Вычисление потерь в случае случайной среды с нормально распределенными доходами аналогичны.
Опишем формальный алгоритм получения величины потерь loss двухпо-роговой стратегии для двухвариантной бинарной случайной среды: 1. Передать в функцию значения: Т (горизонт управления), N (количество моделирований), а (пороговая константа), /3 (параметр среды), as (вторая пороговая константа), Ts (время переключения порогов) 2. Вычислить порог threshold! = 0,5 а у/Т 3. Вычислить второй порог threshold_jЧх = 0,5 as у/Т. 4. Присвоить threshold = threshold_fix При вычислении значений функции потерь программа автоматически создает файл _maple.txt, который можно открыть программой Maple и получить визуализированные результаты. Пример файла _maple.txt with(plots): datalist1 := [0.779, 0.706, 0.662, 0.639, 0.636, 0.649, 0.672, 1.020, 0.872, 0.783, 0.742, 0.743, 0.768, 0.809, 1.174, 0.942, 0.815, 0.765, 0.769, 0.807, 0.864, 1.259, 0.952, 0.801, 0.746, 0.759, 0.811, 0.881, 1.298, 0.921, 0.755, 0.714, 0.740, 0.801, 0.883, 1.298, 0.870, 0.708, 0.683, 0.720, 0.793, 0.879, 1.278, 0.812, 0.661, 0.654, 0.705, 0.787, 0.877, ]: data := [seq([seq([i/10.000 + 0.100, j/1.000 + 2.0, datalist1[i+7 j]],i = 1 .. 7)], j = 0 .. 6)]: F := (x, y) - x2+y2: s := surfdata(data, axes = frame, labels = [a, b, L], color = F, title = "Loss function, T = 100, N = 1000000 titlefont = [HELVETICA, BOLD, 18]): display(s);
Программа Bayes (рисунок (4.3)) представляет одностраничный Qt-виджет c элементами выбора режимов работы и полей для ввода числовой информации. Основные возможности программы: Расчет байесовских рисков. Расчет байесовских потерь. Нахождение оптимальных стратегий управления. Сохранение результатов вычислений в табличном формате, обрабатываемом программой Microsoft Excel. Опишем формальный алгоритм вычисления байесовского риска при конкретных параметрах.
Основными возможностями программы TwoArmed являются расчет значений функции потерь для бинарных сред с простым или двойным порогом, расчет значений функции потерь для сред c нормально распределенными доходами с простым или двойным порогом, сохранение результатов вычислений в табличном формате, обрабатываемом программой Microsoft Excel, сохранение результатов вычислений в формате 3D графика, обрабатываемом программой Maplesoft Maple.
Основные возможности программы Bayes: расчет байесовских рисков, расчет байесовских потерь, нахождение оптимальных стратегий управления, сохранение результатов вычислений в табличном формате, обрабатываемом программой Microsoft Excel. Заключение
В работе представлены результаты исследования задачи параллельной обработки данных в двухальтернативных случайных средах с бинарными и нормально распределенными доходами, имеющими произвольные дисперсии. Показано, что нормально распределенные доходы возникают при использовании параллельной обработки бинарных данных.
Один из разделов работы посвящен пороговой и двухпороговой стратегиям управления, реализующим минимаксный подход к рассматриваемой задаче, преимуществом которого является робастность. С помощью пороговой стратегии и моделирования методом Монте-Карло для бинарных случайных сред с были найдены величины минимаксного риска, соответствующие этим величинам параметры среды, а также оптимальные стратегии управления. Аналогичные величины были получены для случайной среды с нормально распределенными доходами и единичными дисперсиями. Показано, что соответствующая этому случаю оптимальная стратегия остается оптимальной и для сред с произвольными дисперсиями. Результаты моделирований представлены в графическом и табличном видах.
Также в работе представлены результаты исследований, базирующиеся на основной теореме теории игр. А именно, минимаксные стратегии и риски ищутся как байесовские, соответствующие наихудшему априорному распределению. Установлен вид этого распределения. Использован байесовский подход к задаче, который позволяет вычислять потери методами динамического программирования. Получены рекуррентные уравнения для вычисления байесовских рисков, потерь и оптимальных стратегий управления. Произведено численное моделирование этих стратегий и представлены результаты для сред с произвольными дисперсиями.
Разработан комплекс программ, состоящий из программ TwoArmed и Bayes, который позволяет: 1. Моделировать случайные среды с бинарными и нормально распределенными доходами с различными дисперсиями. 2. Вычислять минимаксные и байесовские риски, потери и стратегии управления в таких средах. 3. Выводить результаты моделирований в формате для последующей визуализации. Полученные в диссертации результаты могут быть развиты в следующих направлениях: модификация случайной среды для случая трех и более действий, стратегии управления с большим числом порогов, оптимизация размеров групп данных при параллельной обработке.