WWW.PDF.KNIGI-X.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Разные материалы
 

«Робастное управление в случайных средах с различными дисперсиями применительно к параллельной обработке данных ...»

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

Лазутченко Алексей Николаевич

Робастное управление в случайных средах с

различными дисперсиями применительно к

параллельной обработке данных

05.13.18 – Математическое моделирование, численные методы и комплексы

программ

ДИССЕРТАЦИЯ

на соискание ученой степени

кандидата физико-математических наук

Научный руководитель

д. ф.-м. н., доцент

А. В. Колногоров

Великий Новгород – 2016

Содержание

Введение.................................... 4 Глава 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. Управление в случайной среде, использующее основную

–  –  –

В различных областях человеческой деятельности с каждым годом всё бльшую актуальность получают задачи управления в условиях неопределенно­ о сти. Это могут быть задачи целесообразного управления в случайных средах [3, 39, 40], адаптивного управления [29, 37, 61], о двуруком бандите [36, 48].

Управление в случайной среде — сравнительно молодое направление в науке. За рубежом оно возникло в 50-е годы в результате исследований американского статистика Г. Роббинса [59] и получило в дальнейшем название задачи о двуруком бандите [48]. Двурукий бандит — это игральный автомат с двумя ручками. Выбор любой из ручек сопровождается случайным доходом игрока, распределение которого зависит только от выбираемой в текущий момент времени ручки, фиксированы, но неизвестны игроку. Цель управления состоит в максимизации математического ожидания итогового дохода. В нашей стране это направление развивалось независимо в 60-х годах и прежде всего связано с именем советского кибернетика Цетлина, который рассматривал задачу целесообразного поведения биологических систем. Хорошим примером может являться поведение крысы в Т-образном лабиринте. При движении по лабиринту крыса может повернуть налево или направо. В конце лабиринта её в обоих случаях с некоторыми вероятностями ожидает слабый удар током.

Эти вероятности фиксированы. Эксперименты показали, что крысы обучаются поворачивать туда, где вероятность удара меньше.

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

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

Рассматриваемую в данной работе задачу можно описать следующим образом. Имеются два или более альтернативных действий, каждое применение которых ведет к получению некоторого дохода. Доходы являются случайными, их распределения фиксированы и зависят только от текущих применяемых действий, но неизвестны ЛПР. Цель управления состоит в получении макси­ мальной (в некотором смысле) величины математического ожидания полного дохода. Например, возможны минимаксная и байесовская цели управления.

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

Актуальность темы исследования. Наиболее известным приложени­ ем задач управления в условиях неопределенности является задача о лечении пациентов, когда имеются два альтернативных лекарства с фиксированными, но неизвестными эффективностями. Требует организовать лечение таким об­ разом, чтобы математическое ожидание выздоровевших в результате лечения пациентов было максимальным ([55, 62]). Другое известное приложение — оптимизация обработки данных двумя альтернативными методами с фикси­ рованными, но априори неизвестными эффективностями ([60]). Отметим, что при решении этих задач может использоваться параллельная обработка. В задачах лечения пациентов количество этапов параллельной обработки яв­ ляется небольшим, обычно два, редко три–четыре. В задачах же обработки данных допускается большое число этапов, например, 30–50. Так как данные при параллельной обработке суммируются, то в силу центральной предельной теоремы для управления используются нормально распределенные значения доходов. В зависимости от рассматриваемой постановки задачи дисперсии этих доходов могут иметь попарно одинаковые или различные значения.

Наиболее известными постановками цели управления являются минимакс­ ная и байесовская. Достоинством байесовского подхода ([36, 48]) является то, что он позволяет для любого априорного распределения найти байесовские стратегии и риск численными методами. Недостатком подхода является от­ сутствие ясных критериев выбора априорного распределения. Достоинством минимаксного подхода является его робастность, а недостатком — сложность нахождения робастных алгоритмов, поскольку прямые методы нахождения их отсутствуют. Примерами робастных алгоритмов являются алгоритм на основе метода стохастической аппроксимации ([29]) и алгоритм зеркального спуска ([5, 43]). Отметим, что версии этих алгоритмов, допускающие параллельную обработку, насколько нам известно, не разрабатывались.

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

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





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

Для достижения поставленных целей были решены следующие задачи:

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

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

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

4. Разработка комплекса программ, который позволяет численными метода­ ми находить минимаксные стратегии и риски.

Научная новизна. Научная новизна работы заключается в разработке модели групповой обработки данных, которая математически описывается как задача об управлении в случайной среде с доходами, имеющими нормальное распределение с произвольными дисперсиями. Известные стратегии групповой обработки допускали малое число этапов обработки: обычно два, редко три­ четыре. Предложенные в работе стратегии допускают бльшее число этапов, о например 30–50. Такое число этапов позволяет вести обработку практически без потери качества, то есть без увеличения минимаксного риска. Нахож­ дение минимаксных стратегий и рисков выполнено численными методами с использованием свойства инвариантности и основной теоремы теории игр, то есть минимаксные стратегии и риск ищутся как байесовские, соответствующие наихудшему априорному распределению.

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

Связь работы с научными программами, темами. Основные ре­ зультаты диссертации были получены в рамках выполнения исследований при финансовой поддержке Программы стратегического развития Новгородского государственного университета им. Ярослава Мудрого и Проектной части госу­ дарственного задания в сфере научной активности Министерства образования и науки Российской Федерации, проект № 1.949.2014/K.

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

1. Модель параллельной обработки данных, которая описывается управ­ лением в случайных средах с нормально распределенными доходами с произвольными дисперсиями.

2. Численный метод определения оптимальных параметров одно- и двухпо­ роговых стратегий управления.

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

4. Комплекс программ для моделирования двухальтернативных случайных сред с бинарными и нормально распределенными доходами с различны­ ми дисперсиями, разработанный для обработки численными методами данных, получения и применения стратегий управлений и решения вспо­ могательных задач, возникших при исследований.

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

Основные результаты диссертации докладывались на следующих конфе­ ренциях:

1. XVI, XVII, XVIII, XIX, XXIII научные конференции преподавателей, аспирантов и студентов НовГУ, 2009–2016 гг., Великий Новгород.

2. XIV Всероссийский симпозиум по прикладной и промышленной матема­ тике, 29 сентября — 5 октября 2013 г., Великий Новгород.

3. 57-я международная научная конференция МФТИ «Актуальные пробле­ мы фундаментальных и прикладных наук в современном информацион­ ном обществе», 24 — 29 ноября 2014 г., Долгопрудный, Московская обл.

4. 58-я научная конференция МФТИ с международным участием, 23 — 28 ноября 2015 г., Долгопрудный, Московская обл.

5. IX Международная Петрозаводская конференция «Вероятностные мето­ ды в дискретной математике», 30 мая — 3 июня 2016 г., Петрозаводск, Россия.

А также на семинарах кафедры прикладной математики и информатики Новгородского государственного университета имени Ярослава Мудрого.

Результаты исследований внедрены в учебный процесс Новгородского государственного университета имени Ярослава Мудрого в рамках дисциплины «Модели искусственного интеллекта».

Публикации. Материалы диссертации опубликованы в 11 печатных работах, из них 4 статьи в рецензируемых журналах, рекомендованных ВАК [17–20], 3 статьи в сборниках трудов конференций [21–23] и 4 тезиса докладов [24–27].

Комплексы программ:

Свидетельство о государственной регистрации программы для ЭВМ «Оп­ тимизация параметров пороговой стратегии управления в случайной среде»

№ 2012614942, зарегистрирована в Реестре программ для ЭВМ 1 июня 2012 г.

Свидетельство о государственной регистрации программы для ЭВМ «Мо­ делирование случайных сред с одно- и двухпороговой стратегиями управления в случайной среде» № 2013617255, зарегистрирована в Реестре программ для ЭВМ 06 августа 2013 г.

Свидетельство о государственной регистрации программ для ЭВМ «Рас­ чет байесовских рисков, потерь и стратегий управления для случайных сред с нормально распределенными доходами с произвольными дисперсиями»

№ 2016619416, зарегистрирована в Реестре программ для ЭВМ 18 августа 2016 г.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения и списка литературы.

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

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

Во второй главе рассматриваются пороговая и двухпороговая стратегии управления в случайных средах с бинарными и нормально распределенными доходами. Пороговая стратегия была предложена и исследована Фогелем [63].

В данной работе известная теоретическая верхняя оценка минимаксного риска улучшена численными методами для бинарной среды. Такая же оценка полу­ чена для сред с нормально распределенными доходами. Показано, что такие среды возникают при использовании параллельной обработки данных. Далее была предложена и исследована двухпороговая стратегия управления, которая минимизируют средние потери на заданном априорном множестве парамет­ ров сред с бинарными и нормально распределенными доходами. Обоснована целесообразность такой стратегии. Приводятся результаты численного моде­ лирования. С помощью метода Монте-Карло установлено, что минимаксная пороговая стратегия, полученная для сред с единичными дисперсиями, остается таковой и для сред с дисперсиями, не превосходящих единичную. Кроме того, рассмотрены два метода оптимизации алгоритма, направленные на снижение времени расчетов без уменьшения точности результатов.

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

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

В заключении представлен общий обзор результатов работы и некоторые обобщения.

Общий объем диссертации 96 страниц, включая 24 рисунка и 3 таблицы.

Список литературы включает 64 наименования.

–  –  –

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

После этого вводится общая постановка задачи по исследуемой в диссертации проблеме. Рассматриваются два подхода к решению этой задачи, минимаксный и байесовский. Также в этой главе рассмотрен важный вопрос, для каких сред достигаются наибольшие потери дохода. Показано, что для случайных сред с нормально распределенными доходами, математические ожидания которых значительно различаются, максимальные потери имеют порядок ln, где — горизонт управления. Если же они различаются мало, то потери имеют порядок 1/2.

1.1. Обзор литературы по теме 1.1.1. Автоматный подход Инициатором автоматного подхода, прежде всего, был советский киберне­ тик М. Л. Целина, который опубликовал ряд работ о целесообразном поведении в случайных средах, например [39, 40], позднее была издана книга [41]. Этот подход позднее развивался, например, в работах [3, 4, 15, 16, 34].

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

Эксперименты показали, что крысы обучаются сворачивать в том направлении, где вероятность удара током меньше. Для описания такого поведения были использованы автоматы.

В работах Цетлина под случайной средой подразумевалась модель внеш­ него мира, в которой находилось тестируемое животное, реагирующий на один из двух типов реакции среды — благоприятный («не штраф») и неблагопри­ ятный («штраф»). Целесообразность поведения автомата — это увеличение числа благоприятных реакций и уменьшение числа неблагоприятных. Таким образом, рассматривался конечный автомат, описываемый каноническими уравнениями ( + 1) = ((), ( + 1)), (1.1) () = (()), где — дискретное время, — входная переменная, принимающая значения 0 и 1, интерпретируемые как проигрыш и выигрыш, () — выходная переменная — действия автомата, () — состояние автомата в момент времени.

Математическое ожидание выигрыша для автомата, совершающего действия равновероятно, независимо от реакции двухваринатной среды, можно выразить как () = (1 + 2 )/2, где 1, 2 — вероятности благоприятного исхода при выборе действия с номерами 1, 2. Автомат обладает целесообразным поведением, если его величина математического ожидания выше, чем ().

В дальнейших работах предлагались различные модификации автомата с целесообразным поведением в случайной среде: автомат с линейной тактикой [41], автомат Роббинса-Кринского [15] (стоит отметить, что постановка была получена авторами независимо друг от друга), автомат Крылова [16], автомат Пономарева [34], «автомат с переменной структурой» Варшавского и Воронцо­ вой [3].

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

1.1.2. Идентификационный подход

–  –  –

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

Из недостатков идентификационного подхода можно отметить отсутствие методов для применения в параллельном управлении.

1.1.3. Алгоритм зеркального спуска

–  –  –

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

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

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

1.1.4. Алгоритм UCB1

С развитием интернет-технологий появилась необходимость в новых эф­ фективных методах управления в случайной среде. Например, популярные порталы Mail.ru и Yahoo! содержат на своих домашних страницах множество ссылок. Цель состоит в определении ссылок, дающих максимальный CTR (click-through ratio, отношение кликов). Здесь каждый показ ссылки пользова­ телю соответствует применению ручки; каждый клик — успех, положительная реакция среды; не-клик — неудача. Задача алгоритма в том, чтобы как можно быстрее понять, что та или иная ссылка является наиболее посещаемой, и выводить её в заголовок страницы.

Одним из современных методов решения подобных задач является доста­ точно простой в реализации UCB1 [44, 45] (акроним Upper Confidence Bound, верхний доверительный предел).

Алгоритм следующий:

Применить каждую ручку один раз;

–  –  –

Данный подход используется, например, в [33], где разработан поиско­ вой робот (краулер), предназначенный для сбора исходящих гиперссылок с заданного целевого множества веб-сайтов. Адаптивное поведение краулера, заключающееся в том, что за ограниченное время он должен находить мак­ симально возможное суммарное количество гиперссылок, моделируется как задача о многоруком бандите. Такая постановка задачи позволила применить для её решения известные алгоритмы, эксперименты с которыми показали их зависимость от тематики целевого множества. В работе показано, что для научных сайтов алгоритм UCB1 показывает лучшие результаты по сравнению с «тривиальным правилом» и правилом, построенном с использованием индексов Гиттинса.

Недостатком UCB1 является отсутствие адаптированных для параллель­ ной обработки методов.

1.1.5. Минимаксный подход

Впервые минимаксный подход к решению рассматриваемых задач был предложен в работе Роббинса (H. Robbins) [59]. Рассмотрим задачу более подробно для среды с нормально распределенными доходами. Такую среду можно описать векторным параметром = (1, 2 ) математических ожиданий выигрышей на действиях. Обозначим через (, ) математическое ожидание

–  –  –

где — некоторая используемая стратегия, = (1, 2 ) — параметр управля­ емого процесса. Стратегия есть функция текущей предыстории процесса в момент времени, то есть полученных откликов среды на выбранные действия.

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

–  –  –

называется минимаксным риском, а соответствующая стратегия — мини­ максной стратегией. Ограничения на накладываются, исходя из условий:

= { : |1 2 | 2, 0, = 1, 2}. (1.2) Отметим важное свойство минимаксного подхода — его робастность. В нашем случае робастность подразумевает выполнение некоторого нужного нам свойства при всех допустимых значениях параметров. А именно, использование минимаксной стратегии обеспечивает ограниченность потерь, т.е. макси­ мальные потери не могут превышать величины минимаксного риска (, ) () при всех допустимых значениях параметра из (1.2). Несмотря на то, что работа Роббинса вышла в 1952-м году, до сих пор простого прямого способа нахождения минимаксных риска и стратегии для произвольного горизонта управления не найдено.

Тем не менее, в работе Фабиуса и ван Цвета (Fabius J., van Zwet W. R) [52] были получены точные минимаксные стратегии и риск для 4. Там же было показано, что вычисления для 4 являются слишком сложной задачей.

–  –  –

Оценка, полученная в [11], является менее точной, чем у Фогеля, но имеет тот же порядок 2 и использует более простое доказательство.

Для дальнейшего нам интересна оценка сверху, которая обеспечивается пороговой стратегией, предложенной в [63]. Далее в работе мы рассматриваем пороговые стратегии для таких же сред, а также для сред с нормальными рас­ пределениями доходов. Кроме того, рассматривается модификации пороговой стратегии Фогеля — двухпороговая стратегия.

1.1.6. Байесовский подход Для решения рассматриваемых задач широко используется байесовский подход (например, [6, 7, 36, 48, 55, 56]). Преимущества этого подхода в том, что он позволяет легко вычислять величины рисков и находить стратегии численными методами для произвольных априорных распределений. Недостат­ ком байесовского метода является отсутствие ясных критериев для выбора хорошего априорного распределения.

Рассмотрим подход на примере управления в двухвариантной случайной среды с нормальным распределением доходов. Как и ранее, (, ) есть ма­ тематическое ожидание потерь на горизонте управления, где — некоторая стратегия управления, = (1, 2 ) — параметр cлучайной среды. Байесовский подход подразумевает, что задано априорное распределение () на, которое может быть предложено по результатам некоторых предварительных оценок.

Далее следует усреднить (, ) по (), и полученную величину минимизиро­ вать по :

(()) = max (, )()d.

{} Величина (()) называется байесовским риском, а стратегия, его обеспечи­ вающая, — байесовской стратегией [8].

Несмотря на то, что байесовский подход подразумевает необходимость выбора априорного распределения, он широко используется в прикладных задачах (например, [50, 60]), так как позволяет легко вычислять риски и потери методами динамического программирования. Кроме того, как показано в [8, 12] байесовский риск совпадает с минимаксным на наихудшем априорном распределении, поэтому может быть использован для поиска соответствующей минимаксной стратегии. Далее в работе мы будет использовать этот подход, чтобы найти рекуррентные уравнения для нахождения байесовских рисков, потерь и стратегий для случайных сред с произвольными дисперсиями.

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

(пациент поправился) и «неудача» (состояние пациента в целом осталось прежним), то мы имеет бинарное распределение.

Особенностью такой постановки задачи является тот факт, что эффект от действия лекарства обычно наступает не сразу, а через некоторое время.

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

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

Из работ по параллельному управлению можно отметить, например, [54, 62].

1.2. Общая постановка задачи В настоящей работе исследуется модификация задачи о целесообразном поведении в случайной среде, известная также как задача адаптивного управ­ ления [37] и за рубежом как задача о двуруком бандите (two-armed bandit problem) [59].

Одно из ключевых рассматриваемых понятий является случайная среда — это управляемый случайный процесс, значения которого зависят только от выбираемых в текущие моменты времени действий и которые могут интерпретироваться как доходы. Здесь = 1,...,, — полное время управления средой (горизонт управления). В нашей постановке задачи горизонт управления известен и фиксирован. В общем случае случайная среда имеет действий, где = 1,..., — номера действий. В работе исследуется случай двухальтернативной случайной среды, т.е. = 2 и = 1, = 2 — действия среды.

Классические случайные среды, которые рассматривались, например, в [59, 63, 64], имеют бинарное распределение доходов, т.е. случайный процесс принимает только значения 1 и 0 (которые можно рассматривать как «успех»

и «неудача») и зависит только от выбираемых в текущий момент времени действий. Особенностью рассматриваемой в данной работе постановки задачи является тот факт, что распределение доходов фиксировано, но лицо, принима­ ющее решение (ЛПР), не знает, какое действие является более «доходным» (на каком действии больше вероятность получить выигрыш).

Таким образом, бинарную случайную среду можно описать следующим образом:

( = 1| = ) =, ( = 0| = ) =, (1.3) + = 1, = 1, 2, = 1,...,.

При этом среда задается вектором вероятностей = (1, 2 ).

Целью ЛПР является получить как можно больший ожидаемый выигрыш.

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

–  –  –

называется минимаксным риском [8]. Достоинство этого подхода состоит в том, что он обладает свойством робастности. Оно заключается в следующем:

использование минимаксной стратегии гарантирует, что при любых допу­ стимых параметрах среды максимальные потери будут ограничены величиной минимаксного риска ():

(, ) ().

Недостатком минимаксного подхода является отсутствие простого прямого способа нахождения минимаксных риска и стратегии для горизонта управления 4 [52].

Другой рассматриваемый в работе подход — байесовский. Если обозначить априорное распределение на множестве параметров среды как (), то байесовский риск можно искать по формуле

–  –  –

соответствующая стратегия — байесовская [8]. Плюсом подхода является возможность получения рисков и стратегий численными методами, минусом — необходимость задания априорного распределения.

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

Сначала рассмотрим потери для случая, когда математические ожидания достаточно удалены друг от друга, то есть 1 2 = 0. Будем считать, что 1 2. Горизонт управления, как и ранее, обозначим за.

Пороговая стратегия будет заключаться в следующем. Мы применяем действия среды по очереди -раз, причем /2, накапливая доходы 1 и 2 на действиях = 1 и = 2 соответственно. При этом (1 ) = 1, (2 ) = 2, (1 ) = (2 ) =. При такой стратегии потери будут складываться из потерь за применение неоптимального действия = 2 на начальном этапе управления, когда = 0,..., 2, а также из возможных потерь на заключительном этапе = 2 + 1,...,, если на начальном этапе действие = 2 покажет лучшую доходность.

Формализируя вышесказанное, запишем формулу для вычисления потерь:

(, ) = (1 2 ) + (1 2 )( 2 ) (1 2 0). (1.4)

–  –  –

Рассмотрим теперь случай, когда 1 2 = 1/2, 0, т.е. мате­ матические ожидания достаточно близки. Получим оценку функции потерь снизу, рассматривая среды с избыточной информацией. Представим, что нам известны результаты управления, при котором оба действия = 1 и = 2 были применены по раз. При этом нам сообщили величины накопленных в результате такого управления доходов 1 и 2. Характеристики случайной среды в этом случае будут следующими: (1 ) = 1, (2 ) = 2, (1 ) = (2 ) =, (1 2 ) = 2. Потери будут иметь место только тогда, когда в результате управления действие = 1 покажет меньшую доходность, то есть 1 2. Запишем потери для этого случая как (, ) = (1 2 ) (1 2 0). (1.5)

–  –  –

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

–  –  –

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

Впервые пороговая стратегия в бинарных случайных средах рассматрива­ лась Фогелем [63, 64]. Им была рассмотрена минимаксная постановка задачи и были получены теоретические оценки минимаксного риска (). В данной главе эта оценка уточняется сверху с помощью метода Монте-Карло, используя прилагаемый комплекс программ. Кроме того, мы получаем численные зна­ чения параметров случайной среды, при которых обеспечивается найденная оценка.

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

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

2.1. Стратегия управления с одним порогом

Рассматривается бинарная случайная среда, описанная как (1.3):

( = 1| = ) =, ( = 0| = ) =, + = 1, = 1, 2, = 1,...,.

Задача задается в минимаксной постановке. Целью управления является ми­ нимизация максимальных потерь на множестве параметров среды = {} по множеству стратегий = {}. При этом величина

–  –  –

называется минимаксным риском. Такая цель реализуется с помощью порого­ вой стратегии, которая заключается в следующем. ЛПР применяет действия среды = 1, 2 по очереди, накапливая доходы () на каждом действии соответственно, где — текущее время управления, — горизонт управления.

После каждых поочередных применений действий вычисляется абсолютная разность между текущими накопленными доходами |1 () 2 ()|. Процесс продолжается до тех пор, пока не истечет время управления или эта величина в некоторый момент времени * не превысит порога ( )1/2, т.е.

|1 (* ) 2 (* )| ( )1/2.

где — пороговая константа, = 0,25 — максимальная дисперсия од­ ношагового дохода для бинарных случайных сред. Коэффициент перед рассматривается, исходя из свойства инвариантности функции потерь, как следует из [9]. Если 1 (* ) 2 (* ), то на заключительном этапе управления для оставшихся = * + 1,..., применяем действие = 1; если же 1 (* ) 2 (* ), то применяем = 2. При этом не исключается, что в результате управления может быть исключено и лучшее действие, особенно при близких параметрах среды (1 2 ). После этого вычисляется суммарный накопленный доход = + +, (2.1)

–  –  –

доход, накопленный за время управления * + 1,...,, а затем математическое ожидание суммарного дохода ( ). Далее вычисляются потери дохода, рав­ ные разности между теоретически максимально возможным значением дохода и математическим ожиданием дохода, полученным в результате управления:

–  –  –

Значения и, при которых ( ) = ( ), являются искомыми, а значение минимакса min max (, ) равно, например, ( ).

2.2. Решение задачи о «двуруком бандите» для бинарной случайной среды

–  –  –

В данном разделе оценка () уточняется численными методами с помо­ щью моделирования пороговой стратегии методом Монте-Карло. Результаты моделирований показывают, что найденная оценка является даже более точной.

Кроме того, в работе [63] доказано, что для рассматриваемой задачи существует седловая точка. В конце раздела это будет раскрыто более подробно.

Введем еще два обозначения, которые понадобятся нам для модели­ рования. Случайную величину, соответствующую потерям при однократной реализации стратегии для параметра, обозначим (, ), где

–  –  –

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

Теперь приступим к моделированию заданной пороговой стратегии. Мо­ делирование производится с помощью компьютерной программы TwoArmed, возможности которой рассмотрены более подробно в главе 4.

Заметим, что наша функция потерь зависит от двух параметров, следо­ вательно, может быть построена в виде трехмерного графика по заданным вычисленным точкам в специализированных компьютерных программах, на­ пример, Maple [42], в целях обеспечения наглядности.

Отыскание оптимальных параметров для случая «двурукого бандита»

проведем в три этапа. На первом этапе проведем расчеты для получения пред­ варительных данных. В качестве входных параметров рассмотрим горизонт управления = 10 000, количество моделирований = 1 000, пороговую константу = 0,1,..., 1 с шагом 0,1 и параметр среды = 0,..., 10 с шагом

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

Несмотря на то, что полученная поверхность имеет «бугристую» структуру, просматривается общая тенденция поведения функции при и, а именно, примерное местонахождение минимаксной точки min max (, ).

Поскольку теперь мы располагаем информацией о примерном нахождении минимаксной точки, на оставшихся этапах мы будем уточнять параметры. На втором этапе произведем аналогичные вычисления, но увеличим до 10 000, с целью продемонстрировать финальный вид функции потерь. Получившиеся значения (, ) оформим в виде таблицы 2.1. Здесь светло-серым цветом отмечены значения max (, ), а серым — значения min (, ). Точка, в которой max (, ) = min (, ), выделена темно-серым. Как видно, такая точка является единственной, и оптимальное значение для рассмотренных па­ раметров оказалось равным 0,6, при этом минимакс min max (, ), равный 0,753, соответствует = 4.

Для данных параметров множество значений функции (, ) представ­ Рис. 2.1. График функции потерь для случайной среды с бинарно распределенными доходами. = 10 000, = 1 000, = 0,1,..., 1 = 1,..., 10, предварительные расчеты Таблица 2.1. Поиск оптимальных значений порога и параметра для бинарной среды, «грубая» оценка 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 1 0,465 0,451 0,439 0,423 0,420 0,413 0,423 0,417 0,415 0,422 2 0,866 0,809 0,729 0,679 0,652 0,640 0,644 0,655 0,674 0,727 3 1,227 1,037 0,886 0,808 0,744 0,726 0,743 0,773 0,824 0,877 4 1,547 1,267 0,967 0,871 0,761 0,753 0,770 0,810 0,894 0,960 5 1,811 1,373 0,981 0,809 0,720 0,747 0,758 0,822 0,884 0,992 6 2,010 1,425 0,969 0,775 0,675 0,700 0,748 0,826 0,892 0,999 7 2,194 1,462 0,857 0,742 0,658 0,666 0,736 0,815 0,904 0,998 8 2,363 1,430 0,830 0,679 0,604 0,649 0,705 0,818 0,906 0,997 9 2,494 1,335 0,734 0,588 0,558 0,626 0,706 0,807 0,903 1,014 10 2,599 1,274 0,680 0,568 0,558 0,606 0,700 0,801 0,902 1,007 лено на рисунке 2.2. Здесь график в достаточной мере сглажен, и хорошо идентифицируется местоположение минимаксной точки.

Рис. 2.2. График функции потерь для случайной среды с бинарно распределенными доходами. = 10 000, = 10 000, = 0,1,..., 1 = 1,..., 10 Перейдем к третьему этапу и рассчитаем значения пороговой константы и параметра с заявленной точностью. Рассмотрим множество пороговых констант в диапазоне от 0,51 до 0,6 с шагом 0,01, а значение — от 3,5 до 4,5 с шагом 0,1. Время моделирования = 10 000, усредняющий коэффициент = 1 000 000. Полученные результаты оформим в виде таблицы 2.2 Обозначения в таблице аналогичны рассмотренным выше. Как видно, точка минимакса, как и ранее, является единственной, и оптимальное значение оказалось равным 0,57, при этом min max (, ), равный 0,748, соответствует = 3,8.

Вычисленные результаты согласуются с оценками, полученными в [63, 64].

Таким образом, оптимальная стратегия для = 10 000 выглядит следующим образом. Действия применяются по очереди, накапливая доходы 1 и 2. Если в некоторый момент времени = * величина |1 2 | превысит порог ( )1/2 = 28,5, то действие, которое к этому моменту показало лучшую доходность, применяется до конца управления для всех = * + 1,...,.

Таблица 2.2.

Поиск оптимальных значений порога и параметра для бинарной среды, точность 0,001 0,51 0,52 0,53 0,54 0,55 0,56 0,57 0,58 0,59 0,6 3,5 0,759 0,759 0,753 0,753 0,750 0,747 0,748 0,747 0,746 0,747 3,6 0,760 0,760 0,754 0,754 0,750 0,748 0,748 0,746 0,747 0,748 3,7 0,761 0,761 0,755 0,755 0,751 0,750 0,747 0,749 0,749 0,749 3,8 0,760 0,759 0,754 0,754 0,750 0,749 0,748 0,749 0,748 0,749 3,9 0,759 0,760 0,754 0,754 0,750 0,749 0,749 0,750 0,749 0,749 4 0,759 0,759 0,753 0,753 0,749 0,747 0,748 0,748 0,748 0,750 4,1 0,757 0,757 0,752 0,752 0,749 0,745 0,746 0,747 0,747 0,749 4,2 0,756 0,756 0,750 0,750 0,747 0,745 0,746 0,747 0,748 0,748 4,3 0,753 0,754 0,748 0,748 0,745 0,743 0,744 0,745 0,746 0,746 4,4 0,752 0,751 0,746 0,747 0,742 0,741 0,742 0,743 0,743 0,744 4,5 0,749 0,749 0,744 0,744 0,740 0,739 0,740 0,740 0,739 0,743 Напоследок отметим, что, как следует, например, из [1], в задачах ро­ бастного управления, реализуемых с помощью минимаксного подхода, в общем случае точка минимакса не является седловой точкой, т.е. перестановочные операции inf и sup могут дать несовпадающие результаты. В нашем случае говорить о термине «седловая точка» вполне уместно. Мы в целях самопро­ верки рассматриваем также максимин max min (, ), в предположении, что функция потерь (, ) имеет седловую точку. Это доказано в [63].

Расчеты показывают, что такая точка действительно существует, то есть min max (, ) = max min (, ). Кроме того, это наглядно демонстриру­ ет, например, рисунок 2.2. Поэтому в данной работе можно также оперировать и этим термином.

2.3. Решение задачи о «двуруком бандите» для среды с нормально распределенными доходами

–  –  –

В данном разделе мы переносим оценку (2.3) на случай сред с нормально распределенными доходами, для которых можно рассматривать единичные дисперсии доходов 1 = 2 = 1 за применение действий = 1 и = 2.

При этом значения пороговой константы и параметра среды переносятся с бинарно случая на рассматриваемый практически без изменений, а значения минимаксных рисков min max (, ) должно быть примерно одинаковыми.

Это следует из [9]. Формулы для нахождения порога и параметра среды соответ­ ствуют случаю бинарных доходов, учитывая единичные дисперсии. Случайная среда описывается вектором математических ожиданий = (1, 1 1/2 ), неизвестному ЛПР. Можно показать, что наибольшие потери для этого случая будут при 1 = 0. Аналогично определяются потери

–  –  –

где берется из (2.1).

Покажем, как формируются нормально распределенные доходы. Пусть = ·. Необходимо обработать объем данных, результат обработки которых имеет бинарное распределение с вероятностями 1 = 0,5 и 2 = 0,5 (/ ) 2, где = 1 (1 1 ) = 0,25. Разделим все данные на

–  –  –

Рис. 2.3. Графики функции потерь для случайной среды с бинарно распределенными доходами, простая и параллельная обработка. = 10 000, = 10 000, = 0,..., 10 Здесь также приведен график функции потерь, полученный для = 10000 без разбиения на группы. Как видно, групповая обработка показывает бльшие потери, которые начинают расти, начиная с достаточно больших.

о Расчеты показывают, что в области действия минимакса потери практически идентичны. В силу этого при моделировании случайной среды в этом разделе мы примем время управления = 100. При разбиении данных на бльшее о количество групп результаты становятся точнее. Отметим, что вопросу опти­ мального разбиения данных на группы посвящена работа [32].

Промоделируем теперь работу «двурукого бандита» с помощью програм­ мы Two Armed. Примем = 100, = 1 000 000. Остальные параметры взяты из тех соображений, что область минимаксной точки определена в результате предварительных вычислений: = 0,5,..., 0,6 с шагом 0,01, = 3,5,..., 4,5 с шагом 0,1. Для таких параметров получаем окончательные результаты вычис­ лений: min max (, ) = 0,761 при = 0,55, = 4. Как видно, полученные значения согласуются с аналогичными для случая бинарных доходов.

График функции потерь представлен на рисунке 2.4.

Рис. 2.4. График функции потерь для случайной среды с нормально распределенными доходами. = 100, = 1 000 000, = 0,35,..., 0,75 = 3,..., 5

2.4. Проверка гипотезы об оптимальности пороговой стратегии, найденной для единичной дисперсии, для сред с нормально распределенными доходами с попарно различными дисперсиями В предыдущем разделе мы рассмотрели управление в случайной среде с нормально распределенными доходами и единичными дисперсиями, где нашли оптимальную пороговую стратегию. В данном разделе мы предполагаем, что такая стратегия остается оптимальной не только для единичных дисперсий 1 = 2 = 1, но и для сред с дисперсиями 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. Значения функции потерь, полученные методом Монте-Карло при конкретных дисперсиях горизонт управления, — количество моделирований. Стоит отметить, что от напрямую зависит точность получаемых данных, поэтому эта величина не изменяется.

В данном разделе мы рассмотрим два метода оптимизации алгоритма, общие принципы которых были изложены в [26]. Сразу сделаем замечание.

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

Итак, суть первого метода состоит в следующем. Напомним, что для всех рассматриваемых пар (, ) доход вычисляется как = + +, где, — доходы, полученные на каждом из действий на начальном отрезке времени [1; * ], когда действия применяются по очереди, — доход на заключительном отрезке времени = * + 1,...,, когда применяется только то действие, которые показало лучшую доходность на первом этапе. Здесь * — момент времени, в который достигнут порог. Поскольку на втором этапе применяется только одно действие, причем время выполнения известно, то можно усовершенствовать алгоритм, не моделируя этот этап, а сразу вычисляя итоговый доход по формуле ^ = + + ( * ) ·.

(2.6) ^ В силу вышесказанного ( ) = ( ). Это позволяет нам сократить время моделирования в среднем в два раза.

Следующий метод оптимизации заключается в следующем. Напомним, что алгоритм работы «двурукого бандита» устроен таким образом, что в нем для каждой пары (, ) вычисляется доход,, и этот доход накапливается за все время моделирования при текущих,. Здесь [1, ], [1, ], — количество рассматриваемых при моделировании порогов, — количество пара­ метров среды. Алгоритм можно усовершенствовать, если для набора пороговых констант 1 2... и очередного зафиксированного параметра при достижении некоторого порога ( )1/2 текущий накопленный доход, не обнулять, а продолжать моделирование для следующего порога +1 ( )1/2, для которого доход +1, начинает накапливаться с величины,. После этого окончательный доход на -м действии рассчитывается по формуле (2.6). И так далее, до тех пор, пока не истечет время управления. Если время управления истекло при некотором, а наибольший порог ( )1/2 не достигнут, то для всех + 1,..., оставшимся доходам +1,,...,, присваиваются значения, равные текущему накопленному доходу.

Таким образом формируется двухмерный массив доходов,. Затем для каждой пары (, ) вычисления повторяются раз согласно формуле (2.5).

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

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

2.6. Модификация пороговой стратегии. Двухпороговая стратегия управления

В дальнейших разделах этой главы мы модифицируем пороговую стра­ тегию управления. Суть в том, что найденная при = 0,57 пороговая стратегия является оптимальной для рассматриваемого множества {}, но для достаточно больших значений средние потери можно уменьшить. В плане минимизации потерь теоретически оптимальным решением для каждого из рассматриваемого множества {} является нахождение своего оптимального порога. Это демонстрирует рисунок 2.6. На нем линии 2 соответствуют потери, рассчитанные для всех параметров [0; 30] при фиксированном пороге fix = 0,57. Здесь же линия 1 показывает потери, вычисленные для того же множества {}, при этом каждому соответствует свое оптимальное ().

Для того, что понять, как формируются потери и как их можно умень­ шить, рассмотрим случаи близких и удаленных распределений вероятностей выигрышей на действиях. Как следует из формулы (2.2), параметр опре­ деляет близость этих вероятностей, то есть параметр среды = (0,5, 2 = 0,5 (/ )1/2 ).

На рисунке 2.7 линия 1 показывает некоторую историю изменения ве­ личины разности доходов 1 2 с течением времени на начальном этапе Рис. 2.6. Графики значений функции потерь при 0 = 30 для бинарной случайной среды.

Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,57 управления. В качестве пороговой константы рассмотрено значение fix = 0,57, полученное ранее, и = 5. Здесь же пунктирной линией показано математическое ожидание изменения доходов (тренд). Для = 5, = 10 000 и = 0,25 параметр = (0,5, 0,475), то есть вероятности выигрышей достаточно близки.

Если же эффективность действий различается значительно (например, линия 2 на рисунке 2.8 показывает распределение величины 1 2 при = 50, что равносильно = (0,5, 0,25)), то лучшее действие для таких случаев определяется достаточно быстро. По рисунку видно, что линия тренда практи­ чески совпадает с распределением потерь. В данном случае нет необходимости рассматривать слишком большое значение порога.

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

Мы предлагаем компромиссное решение (рисунок 2.9). Идея в том, что можно ввести дополнительный порог s fix, действующий до определен­ ного времени s. Если вероятности выигрыша различаются значительно, то Рис. 2.7. Некоторое изменение величины 1 2 при близких параметрах двухвариантной бинарной случайной среды, = 5 Рис. 2.8. Некоторое изменение величины 1 2 при удаленных параметрах двухвариантной бинарной случайной среды, = 50 оптимальное действие определяется по достижении порога s (линия 1). Если же вероятности близки (линия 2), то на определение оптимального действия требуется больше времени, и, соответственно, бльший порог. Здесь и далее о обозначение «s» есть сокращение от «second», то есть второй порог. Назовем такую стратегию двухпороговой.

Рис. 2.9. Наглядное представление рассматриваемой проблемы определения оптимальных значений s и s

Здесь сразу возникают следующие вопросы:

какова должна быть оптимальная величина порога s для заданного мно­ жества параметров и какое время s переключения порогов необходимо рассмотреть?

какую численную выгоду мы в результате получим?

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

2.7. Формулировка цели управления Итак, рассматривается двухвариантная случайная среда, значения кото­ рой рассматриваются как доходы, зависящие только от выбираемых в текущие моменты времени действий, — горизонт управления. В зависимости от типов доходов рассматриваются бинарные среды и среды с нормальными распределениями доходов. Функция (, ) показывает потери, возникающие в процессе управления.

Пусть () — априорная плотность распределения на множестве {}.

Цель управления задается в байесовской формулировке:

–  –  –

2.8. Моделирование двухпороговых стратегий Моделирование в этой главе будет производиться с помощью программы TwoArmed, функции которой описаны в листингах в главе 4. Программа вычисляет значения функции потерь и записывает их в формат, понятный для обработки в программе Microsoft Excel, на основе которых далее строятся диаграммы.

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

Прежде всего, нам понадобится вычислить значения для случаев, показанных на рисунке 2.6. Обозначим через minimax средние потери для линии

1. Это наименьшие средние потери. Формула для вычисления minimax вытекает из (2.9), учитывая, что s = 0, s = 0:

minimax = ((), )d, (2.10)

–  –  –

где fix = 0,57. Оба интеграла оцениваются методом трапеций с шагом = 1.

Рассчитаем теперь значения minimax и fix по формулам (2.10) и (2.11) при = 10 000, = 1 000 000 (здесь и далее будут использоваться эти же значения и ), = 0,1,..., 1 с шагом 0,1, 0 = 30.

0 выбрано по результатам предварительных оценочных расчетов:

minimax = 0,446, fix = 0,603.

Анализируя получившиеся значения, видим, что средние потери при 0 = 30 для случая с одиночным зафиксированным порогом увеличиваются на 35% по сравнению с наиболее оптимальным значением. Сразу отметим здесь, что если рассматривать более широкие диапазоны, то процентная величина разницы средних потерь будет расти. Очевидно, это связано с тем, что в первом случае функция потерь является убывающей, а во втором не меняет своего фиксированного значения. Ниже мы покажем это на примере 0 = 50.

2.9. Моделирование двухпороговой стратегии в бинарной случайной среде Итак, введем дополнительный порог 0 s fix. Стратегия будет выгля­ деть следующим образом. Начиная с некоторого времени = s текущий порог s заменяется на fix, после чего управление продолжается в обычном порядке.

Целью управления является нахождение значений s и s, удовлетворяющих условиям (2.8).

Очевидно, что используя дополнительный порог s, неоптимальное дей­ ствие при высоких значениях будет в среднем исключаться из рассмотрения быстрее. Вместе с тем, не совсем понятно, что будет происходить на этапе, где мало. Попробуем взять тестовые параметры s и s и проанализируем результаты. Рассмотрим, например, 0 = 30, s = 0,2, s = 2 000. Полученные результаты отобразим на рисунке 2.10.

Рис. 2.10. Графики значений функции потерь при 0 = 30 для бинарной случайной среды.

Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,57, линия 3 — потери для fix = 0,57 при s = 0,2, s = 2 000 Линия 3 показывает значения потерь при наших выбранных случайных параметрах. Как видно, параметры оказались удачны: ни одно из значений потерь не превышает вычисленной ранее величины гарантированных потерь полного дохода L, и при больших значениях потери имеют тенденцию снижаться, и по всей видимости, стремятся к потерям для случая простого порога.

Далее вычислим величину s по формуле (2.9), получаем

s = 0,524.

Как видно, введение второго порога s для таких «тестовых» параметров, которые мы рассматриваем, позволило снизить средние потери по сравнению с потерями fix = 0,603 на 15,1%, а по отношению к наименьшим потерям minimax = 0,446 эта величина выросла всего на 17,6%.

Далее был проведен полный расчет значений при 0 = 30, s = 0,05,..., 0,55 с шагом 0,05, s = 500,..., 9 500 с шагом 500. В итоге удалось достигнуть значения s = 0,47 при s = 0,3, s = 4 000. График это демонстрирует, потери при таких параметрах обозначены на рисунке 2.11.

Это позволяет судить о том, что двухпороговая стратегия для 0 = 30 позволяет снизить средние потери дохода по сравнению с одиночным фиксиро­ ванным порогом на 28,2%, а от минимально возможных они отличаются всего на 5,5%. Соответствующая оптимальная двухпороговая стратегия для 0 = 30 и = 10 000 выглядит следующим образом. Мы применяем действия по очереди, накапливая доходы. Если абсолютная величина разности доходов превышает первый порог s ( )1/2 = 15 в момент времени = * s = 4 000, то оптимальным является действие, показавшее лучшую доходность, после чего оно применяется оставшееся время = * + 1,...,. Если же абсолютная Рис. 2.11. Графики значений функции потерь при 0 = 30 для бинарной случайной среды.

Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,57, линия 3 — потери для fix = 0,57 при s = 0, 3, s = 4 000 разность превышает первый порог, но при s, либо не превышает вовсе, то моделирование продолжается для второго порога fix ( )1/2 = 28,5.

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

Например, проводя исследования для 0 = 50, вычислим значения minimax, fix и s по формулам (2.10), (2.11) и (2.9) соответственно. Полученные результаты отобразим на рисунке 2.12. Вычисления показывают, что

–  –  –

при s = 0,25 и s = 2 000.

Анализируя получившиеся значения, получаем, что потери s, соответ­ ствующие двухпороговой стратегии при 0 = 50, уменьшаются на 44,9% по сравнению с потерями, полученными при фиксированном пороге.

Рис. 2.12. Графики значений функции потерь при 0 = 50 для бинарной случайной среды.

Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,57, линия 3 — потери при фиксированных = 0,57, s = 0, 25, s = 2 000.

2.10. Двухпороговая стратегия управления в случайной среде с нормально распределенными доходами Проведем теперь численную оптимизацию средних потерь для случайных сред, доходы которых имеют нормальные распределения с плотностями ( ) (| ) = exp 2 и единичными дисперсиями.

Сначала рассчитаем значения потерь при минимальных для каждого и для fix = 0,55, которое было получено при отыскании минимакса для случайной среды с нормально распределенными доходами. Результаты показаны на рисунке 2.13 для 0 = 150. Мы намеренно рассматриваем такое большое значение, чтобы пояснить некоторые моменты.

Во-первых, найденная стратегия оказывается минимаксной при 0

40. Во-вторых, начиная с некоторого 90 значения функции потерь в обоих случаях продолжают расти вдоль одной и той же прямой. Эта прямая описывается уравнением () /. Дадим объяснение такому поведению функций. Причина в том, что пороговая стратегия предполагает применение Рис. 2.13. Графики значений функции потерь при 0 = 50 для случайной среды с нормально распределенными доходами. Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,55.

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

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

Итак, рассматривая 0 = 40 (рисунок 2.15), вычислим значения minimax и fix по формулам (2.10) и (2.11). Вычисления показывают, что

–  –  –

Рис. 2.14. Графики значений функции потерь без учета двух первых применений действий при 0 = 150 для случайной среды с нормально распределенными доходами. Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,55.

Рис. 2.15. Графики значений функции потерь при 0 = 40 для случайной среды с нормально распределенными доходами. Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,55.

Анализируя получившиеся значения, получаем, что средние потери для множе­ ства 0 = 40 для случая с fix = 0,55 увеличиваются на 26,3% по сравнению с minimax.

–  –  –

при s = 0,34, s = 55. Потери при таких параметрах обозначены на рисунке 2.16.

Рис. 2.16. Графики значений функции потерь при 0 = 40 для случайной среды с нормально распределенными доходами. Линия 1 показывает потери при оптимальных (), линия 2 — потери для fix = 0,55, линия 3 — потери для fix = 0,55 при s = 0,34, s = 55 Таким образом, средние потери дохода, рассчитанные с помощью двухпо­ роговой стратегии для 0 = 40, уменьшаются на 21,7% по сравнению с потерями при фиксированном пороге.

2.11. Выводы ко второй главе В данной главе рассмотрена минимаксная постановка задачи, исполь­ зующая пороговую стратегию управления в случайных средах с бинарными доходами. Известная теоретическая оценка минимаксного риска () улуч­ шена численными методами. Кроме того, рассмотрено обобщение на случай случайных сред с нормально распределенными доходами, для которых также получена оценка минимаксного риска.

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

Основные результаты первой главы были представлены на XVIII, XIX, XXIII научных конференциях преподавателей, аспирантов и студентов НовГУ, XIV Всероссийском симпозиуме по прикладной и промышленной математике, 29 сентября — 5 октября 2013 г., Великий Новгород, 58-я научной конференции МФТИ с международным участием, 23 — 28 ноября 2015 г., Долгопрудный, Московская обл., а также в работах [17, 18].

–  –  –

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

3.1. Связь минимаксного и байесовского подходов и основная теорема теории игр

В [8] установлена связь между минимаксным и байесовским подходом к решению рассматриваемой задачи. А именно, предлагается воспользоваться основной теоремой теории игр, согласно которой минимаксные стратегию и риск можно искать как байесовские, соответствующие наихудшему априорному распределению. Также указано, что такое распределение может быть выбрано симметрическим и асимптотически однородным. Ограничением рассмотренной в [8] постановки задачи является использование только единичных дисперсий 1 = 2 = 1.

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

В данном разделе подход, предложенный в [8], обобщается на случай, когда дисперсии доходов на действиях попарно одинаковы и могут принимать различные значения из множества 0 1, 0 0 [20]. Для этого случая выведены рекуррентные уравнения для вычисления байесовских рисков и по­ терь методами динамического программирования, а также проведена численная оптимизация на основе полученных формул. Показано, что в этом случае управление остается робастным, т.е. гарантируется ограниченность потерь на всем множестве, где = { : |1 2 | 2, 0, = 1, 2}.

Стратегии, использующие групповую обработку данных для групп посто­ янного размера, рассмотрены, например, в [10]. Случай с группами разного размера подробно рассмотрен в [32].

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

–  –  –

Обозначим через (; 1, 1, 2, 2 ) байесовский риск, рассчитанный для доходов с дисперсиями, отличными от единицы, относительно апостери­ орного распределения с плотностью. Справедлива следующая теорема.

–  –  –

Формула (3.2), справедливость которой доказана в теореме 1, позволяет вычислять байесовские риски при дисперсиях, отличных от единицы, используя формулы, выведенные в [8].

3.3. Нахождение байесовских потерь и стратегий, численная оптимизация

–  –  –

оказывать сильное влияние применение неоптимального действия на начальном этапе управления. Отметим, что для увеличения области действия оптимальной стратегии следует увеличить горизонт управления.

–  –  –

3.4. Моделирование методом Монте-Карло Можно отметить, что все результаты вычислений, полученные выше при 1 = 2 = 1, совпадают с [8]. При остальных дисперсиях проверку можно осуществить с помощью моделирования методом Монте-Карло.

Сделаем замечание. Точность методов численного моделирования, в част­ ности метода Монте-Карло, зависит от количества проведенных испытаний.

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

–  –  –

на одном графике объединены результаты вычислений методом Монте-Карло, а также по формулам (3.9)–(3.12). Видно, что для каждой дисперсии линия функции потерь, рассчитанная методом Монте-Карло, повторяет поведение ли­ нии функции потерь, вычисленной по формулам. Отметим, что при увеличении горизонта управления результаты становятся точнее.

–  –  –

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

Мы проверяем наше предположение с помощью моделирования методом Монте-Карло [19]. В данном случае дисперсии доходов на действиях среды будут разными и могут принимать различные значения из множества 0 1, 0 0, = 1, 2. Нам необходимо проверить, что при таких дисперсиях ни одно из значений max (, ) при конкретных = (1, 2 ) не превысит соответствующего при 1 = 2 = 1. В качестве стратегии используется стратегия, найденная для 1 = 2 = 1.

Итак, были вычислены значения (, ) для различных пар дисперсий [0,2; 0,9] с шагом 0,2 для горизонта управления = 50 для 0 10 с шагом 0,1, где = |1 2 |. Некоторые результаты вычислений представлены в таблице 3.1.

Таблица 3.1.

Значения (, ), вычисленные для некоторых дисперсий при фиксированной стратегии, найденной для 1 = 2 = 1 (1, 2 ) 1 2 3 4 5 6 7 8 9 10 (0,2, 0,8) 0,07 0,135 0,186 0,23 0,26 0,29 0,31 0,33 0,34 0,35 (0,8, 0,2) 0,115 0,216 0,305 0,38 0,46 0,496 0,54 0,57 0,59 0,606 (0,5, 0,5) 0,09 0,17 0,24 0,3 0,35 0,38 0,41 0,434 0,45 0,46 В результате анализа вычисленных значений было выявлено, что наше предположение верно, и полученная в случае единичных дисперсий стратегия действительно является минимаксной для дисперсий, меньших, чем единичная.

Для некоторых пар дисперсий значения (, ) представлены на рисунке (3.4).

Здесь же сплошной линией приведены значения при 1 = 2 = 1. Отметим, что при увеличении горизонта управления результаты становятся точнее, но требуют больших затрат времени на моделирование.

–  –  –

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

3.6.1. Постановка задачи

–  –  –

3.6.2. Характеризация наихудшего априорного распределения Характеризация наихудшего априорного распределения основана на свойствах непрерывности и вогнутости байесовского риска.

Лемма 1. Байесовский риск является вогнутой функцией априорного распре­ деления, то есть для любых плотностей 1, 2 и положительных чисел 1, 2, таких что 1 + 2 = 1, справедливо неравенство (1 1 + 2 2 ) 1 (1 ) + 2 (2 ).

(3.16)

–  –  –

() = ().

Доказательство. Замечая, что (1, 2 |1, 1, 2, 2 ) = (1 +, 2 + |1 + 1, 1, 2 + 2, 2 )

–  –  –

при любых 1, 1, 2, 2,. Следовательно, (; 1, 1, 2, 2 ) = (; 1 + 1, 1, 2 + 2, 2 ).

Требуемый результат получается при 1 = 2 = 0.

–  –  –

Теорема 2. Не уменьшающая байесовский риск плотность распределения при может быть выбрана в виде (, ) = ()(), (3.

17)

–  –  –

Рассмотрим теперь стратегию, которая в начале управления применяет действия по очереди, получая при этом полные доходы 1 и 2. Величины = (1 + 2 )/2, = (1 2 )/2 могут быть использованы для нахождения апостериорной плотности распределения (, |, ) = (|)(|),

–  –  –

Доказательство. Проверим справедливость первого уравнения (3.20). Умно­ жая левую и правую части первого уравнения (3.15) на (1, 1, 2, 2 ), получа­ ем

–  –  –

Очевидно, (1, 1, 2, 1, ), (1) (1 1, 1 ) соответствуют приведенным в (3.21), (3.22). Теперь заметим, что при 1 + 1, 2 величина пересчитывается по правилу (1 + )2 2 (1 + 1) = +, где = 2 2. Замечая, что 1 1 = 1 ( 1 ) и заменяя переменную интегрирования на в (3.19), получаем первое уравнение (3.15). Справедливость второго уравнения (3.15) доказывается аналогично. Формула (3.23) следует из (3.19) с учетом равенства (, 1, 1) = 2 ((, |, ))().

Таким образом, теорема 2 позволяет выбрать наихудшее априорное рас­ пределение, теорема 3 задает основу для численного поиска минимаксной стратегии как байесовской, а теорема 4 задает формулы для поиска рисков методами динамического программирования.

3.7. Численная оптимизация байесовских рисков при различных попарно разных дисперсиях Нахождение байесовских рисков для попарно различных дисперсий на дей­ ствиях осуществлялось по формулам (3.20)–(3.23). На рисунке 3.5 приведены графики значений функции рисков (), вычисленные при = 50, 0 10 с шагом 0,1 для некоторых дисперсий.

–  –  –

Также в целях самопроверки моделирование было проведено для попарно одинаковых дисперсий 1 = 2 = 1 и 1 = 2 = 0,6. Эти значения соот­ ветствуют полученным ранее. По графикам видно, что чем меньше дисперсии доходов, тем меньше потери полного дохода.

3.8. Выводы к третьей главе В третьей главе рассматривается подход к решению задачи о двуру­ ком бандите, использующий основную теорему теории игр. Минимаксные риски ищутся как байесовские, соответствующие наихудшему априорному рас­ пределению, на котором достигается максимум байесовского риска. Найден вид этого распределения, получены рекуррентные уравнения для вычисления байесовских рисков и потерь для случайных сред с произвольными диспер­ сиями. На основе этих уравнений с помощью комплекса программ найдены оптимальные стратегии для некоторых случайных сред с конкретными диспер­ сиями. Полученные результаты проверены методом Монте-Карло. Отмечено, что результаты в частных случаях при единичной дисперсии соответствуют известным.

Основные результаты данной главы докладывались на 57-й международ­ ной научной конференции МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе» (24 — 29 ноября 2014 г., Долгопрудный, Московская обл.), IX Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (30 мая — 3 июня 2016 г., Петрозаводск, Россия), а также опубликованы в работах [19, 20].

–  –  –

В этой главе описывается программный комплекс, состоящий из программ TwoArmed и Bayes, с помощью которых осуществлялись моделирование всех рассматриваемых в диссертации процессов и вычисление необходимых резуль­ татов. Программы были написаны на языке C++ с использованием библиотек графического интерфейса Qt и MFC. Выбор языка C++ обусловлен его вы­ сокой производительностью, а использование средств Qt и MFC позволило с максимальной простотой создать графический интерфейс пользователя.

4.1. Программа TwoArmed Программа TwoArmed (рисунок (4.1)) представляет диалоговое MFC-окно c элементами выбора режимов работы, полей для ввода параметров моделиро­ вания и консоли с выводимыми в результате вычисления результатами.

–  –  –

Основные возможности программы:

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

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

Сохранение результатов вычислений в табличном формате, обрабатывае­ мом программой Microsoft Excel.

Сохранение результатов вычислений в формате 3D графика, обрабатыва­ емом программой Maplesoft Maple.

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

Алгоритм вычисления величины потерь

–  –  –

4.1.2. Моделирование двухпороговых стратегий Опишем формальный алгоритм получения величины потерь двухпо­ роговой стратегии для двухвариантной бинарной случайной среды:

–  –  –

4.1.3. Визуализации данных расчетов в программе Maplesoft Maple При вычислении значений функции потерь программа автоматически создает файл *_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);

–  –  –

4.2. Программ Bayes Программа Bayes (рисунок (4.3)) представляет одностраничный Qt-виджет c элементами выбора режимов работы и полей для ввода числовой информации.

Основные возможности программы:

Расчет байесовских рисков.

Расчет байесовских потерь.

Нахождение оптимальных стратегий управления.

Сохранение результатов вычислений в табличном формате, обрабатывае­ мом программой Microsoft Excel.

–  –  –

11. Вычислить текущий индекс.

12. Для всех =,..., вычислить (границы выбираются из соображений наименьшей погрешности при вычислении интеграла):

1 = [1 + 1][2 ][].1 2 · (( 1 * ( ))/2, 1 ), 2 = [1 ][2 + 1][].1 2 · (( 2 * ( ))/1, 2 ).

13. Для всех = 0,..., 1. вычислить интегралы методом прямоуголь­ ников.

–  –  –

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

4.3. Выводы к четвертой главе В данной главе рассмотрен программный комплекс, с помощью которого проводились исследования и вычисления при написании диссертационной ра­ боты. Комплекс состоит из программ TwoArmed и Bayes. Приведены основные алгоритмы, лежащие в основе работы программы, а также некоторые листинги.

Основными возможностями программы TwoArmed являются расчет зна­ чений функции потерь для бинарных сред с простым или двойным порогом, расчет значений функции потерь для сред c нормально распределенными доходами с простым или двойным порогом, сохранение результатов вычислений в табличном формате, обрабатываемом программой Microsoft Excel, сохранение результатов вычислений в формате 3D графика, обрабатываемом программой Maplesoft Maple.

Основные возможности программы Bayes: расчет байесовских рисков, расчет байесовских потерь, нахождение оптимальных стратегий управления, сохранение результатов вычислений в табличном формате, обрабатываемом программой Microsoft Excel.

Заключение

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

Показано, что нормально распределенные доходы возникают при использова­ нии параллельной обработки бинарных данных.

Один из разделов работы посвящен пороговой и двухпороговой стра­ тегиям управления, реализующим минимаксный подход к рассматриваемой задаче, преимуществом которого является робастность. С помощью пороговой стратегии и моделирования методом Монте-Карло для бинарных случайных сред с были найдены величины минимаксного риска, соответствующие этим величинам параметры среды, а также оптимальные стратегии управления.

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

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

Установлен вид этого распределения. Использован байесовский подход к задаче, который позволяет вычислять потери методами динамического программирова­ ния. Получены рекуррентные уравнения для вычисления байесовских рисков, потерь и оптимальных стратегий управления. Произведено численное модели­ рование этих стратегий и представлены результаты для сред с произвольными дисперсиями.

Разработан комплекс программ, состоящий из программ TwoArmed и

Bayes, который позволяет:

1. Моделировать случайные среды с бинарными и нормально распределен­ ными доходами с различными дисперсиями.

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

3. Выводить результаты моделирований в формате для последующей визуа­ лизации.

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

–  –  –

1. Афанасьев В. Н. Динамические системы управления с неполной информа­ цией. Алгоритмическое конструирование: // М.: КомКнига. 2006. 170 с.

2. Бусленко Н. П., Шрейдер Ю. А. Метод статистических испытаний и его реализация на цифровых вычислительных машинах // М.: ИФМЛ. 1961.

226 с.

3. Варшавский В. И., Воронцова И. П. Поведение стохастических автоматовс переменной структурой // Автоматика и телемеханика. 1963. Т. 24. № 3.

С. 353–360.

4. Варшавский В. И. Коллективное поведение автоматов // Москва: Наука.

1973. С. 408.

5. Гасников А. В., Нестеров Ю. Е., Спокойный В. Г. Об эффективности одного метода рандомизации зеркального спуска в задачах online оптимизации // Журнал вычислительной математики и математической физики. 2015. 55:4.

С. 582–598.

6. Де Гроот М. Оптимальные статистические решения // М.: Мир. 1974. 491 с.

7. Дынкин Е. Б., Юшкевич А. А. Управляемые марковские процессы и их приложения. М.: Наука. 1975. 338 c.

8. Колногоров А. В. Нахождение минимаксных стратегии и риска в случайной среде (задача о двуруком бандите) // АиТ. 2011. № 5. С. 127–138.

9. Колногоров А. В., Шелонина Т. Н. Об инвариантности функции потерь для пороговой стратегии поведения в случайной среде // Вестн. Новг. гос. ун-та.

2006. № 39. С. 18–21.

10. Колногоров А. В., Олейников А. О. Оптимизация параллельной многоэтап­ ной обработки в случайной среде // Вестник НовГУ. 2012. № 68. С. 67–69.

11. Колногоров А. В. О стратегии поведения в стационарной среде с неулучша­ емой гарантированной оценкой сходимости среднего дохода // АиТ. 1991.

выпуск 5. С.

183–186.

12. Колногоров А. В. Робастное параллельное управление в случайной среде (задаче о двуруком бандите) // АиТ. 2012. № 4. C. 114–130.

13. Коновалов М. Г. Об адаптивных стратегиях и условиях их существования // Информ. и ее примен., 2012, том 6, выпуск 4, 18–26

14. Коновалов М. Г. Об одной задаче оптимального управления нагрузкой на сервер // Информ. и ее примен., 2013, том 7, выпуск 4, 34–43

15. Кринский В. И. Асимптотичеси оптимальный автомат с экспоненциальной скоростью сходимости // Биофизика. 1964. Т. 9. вып. 4. С. 484–487.

16. Крылов В. Ю. Об одном стохастическом автомате, асимптотически-опти­ мальном в случайной среде // Автоматика и телемеханика 24. 1963. № 9.

17. Лазутченко А. Н. Использование двухпороговой стратегии управления в бинарной случайной среде // Современные проблемы науки и образова­ ния. 2013. № 3; URL: www.science-education.ru/109-9552 (дата обращения:

15.09.2015).

18. Лазутченко А. Н. Использование двухпороговой стратегии управле­ ния в случайной среде с нормально распределенными доходами //

Современные проблемы науки и образования. 2014. № 2; URL:

www.science-education.ru/116-12590 (дата обращения: 15.09.2015).

19. Лазутченко А. Н. Минимаксная стратегия управления для класса гауссов­ ских случайных сред с различными дисперсиями // Вестн. Новг. гос. ун-та.

Сер.: Физико-математические науки. 2015. № 3(86). часть 2. С. 25–28.

20. Лазутченко А. Н. О робастном управлении в случайной среде, характеризуе­ мой доходами с различными дисперсиями // КарНЦ. Сер.: Математическое моделирование и информационные технологии. 2015. № 10. С. 107–113.

21. Лазутченко А. Н., Колногоров А. В. О робастном управлении в случайной среде, характеризуемой нормальным распределением доходов с различны­ ми дисперсиями // Труды 57-й научной конференции МФТИ. Управление и прикладная математика. Т. 1. С. 114–116.

22. Лазутченко А. Н., Колногоров А. В. Минимаксный подход к решению одной из задач о двуруком бандите в случайной среде с нормально распределенными доходами // Труды 58-й научной конференции МФ­ ТИ; URL: http://conf58.mipt.ru/static/reports_pdf/214.pdf (дата обраще­ ния: 14.12.2015.

23. Лазутченко А. Н. Использование двухпороговой стратегии управления в бинарной случайной среде // Обозрение прикладной и промышленной математики. 2013. Т. 20. вып. 4. с. 557.

24. Лазутченко А. Н. Задача о целесообразном управлении в случайной среде // Тезисы докладов аспирантов, соискателей, студентов. Часть 3. Великий Новгород. 2009. с. 38.

25. Лазутченко А. Н. Задача о целесообразном управлении в случайной среде // Тезисы докладов аспирантов, соискателей, студентов. Часть 3. Великий Новгород. 2010. С. 39–40.

26. Лазутченко А. Н. Задача о целесообразном поведении в случайной среде // Материалы докладов аспирантов, соискателей, студентов. Часть 3. Великий Новгород. 2011. С. 59–62.

27. Лазутченко А. Н. Оптимизация параллельного управления в случайной сре­ де с нормально распределенными доходами и различными дисперсиями // IX Международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 30 мая — 3 июня 2016 г., Петрозаводск, Россия

28. Мазалов В. В. Математическая теория игр и приложения // СПб.: «Лань».

2010. 448 с.

29. Назин А. В., Позняк А. С. Адаптивный выбор вариантов // Москва: Наука.

1986. С. 288.

30. Назин А. В., Анулова С. В., Тремба А. А. Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком // Автоматика и телемеханика. 2014. № 6. С. 30–38.

31. Назин А. В., Поляк Б. Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче PageRank // АиТ. 2011. № 2. С. 131–141.

32. Олейников А. О. Нахождение оптимальных планов параллельного управ­ ления в случайной среде в приложении к обработке данных: Дис.... канд.

технич. наук. Петрозаводск. 2014. - 111 с.

33. Печников А. А., Чернобровкин Д. И. Адаптивный краулер для поиска и сбора внешних гиперссылок // Управление большими системами: сборник трудов. 2012. № 36. С. 301–315.

34. Пономарев В. А. Об одной конструкции конечного автомата, асимптотиче­ ски-оптимального в стационарной случайной среде // Биофизика 6. 1963.

№ 6.

35. Прохоров Ю. В., Розанов Ю. А. Теория вероятностей. Основные понятия.

Предельные теоремы. Случайные процессы // М.: Наука. 1967. 496 с.

36. Пресман Э. Л., Сонин И. М. Последовательное управление по неполным данным. М.: Наука. 1982. 256 с.

37. Срагович В. Г. Адаптивное управление // М.: Наука. 1981. 384 с.

38. Срагович В. Г. Теория адаптивных систем // М.: Наука. 1976. 320 с.

39. Цетлин М. Л. Конечные автоматы и моделирование простейших форм поведения // Успехи математических наук. 1963. Т. 18. № 4(112). С. 3–28.

40. Цетлин М. Л. О поведении конечных автоматов в случайных средах // Автоматика и телемеханика. 1961. Т. 22. № 10. С. 1345–1354.

41. Цетлин М. Л. Исследования по теории автоматов и моделированию биоло­ гических систем // Москва: Наука. 1969. С. 316.

42. Тихомиров А. С. Введение в Maple: учеб. пособие // сост. А. С. Тихомиров, И. С. Пашков; НовГУ им. Ярослава Мудрого. Великий Новгород. 2007.

121 с.

43. Юдицкий А. Б., Назин А. В., Цыбаков А. Б. и др. Рекуррентное агреги­ рование оценок методом зеркального спуска с усреднением // Проблемы передачи информации. 2005. Т. 41. № 4. С. 78–96.

44. Auer P. Using Confidence Bounds for Exploitation-Exploration Trade-offs // The Journal of Machine Learning Research. 2003. Vol. 3. P. 397–422.

45. Auer P., Cesa-Bianchi N., Fischer P. Finite-time Analysis of the Multiarmed andit Problem // Machine Learning. 2002. Vol. 47. P. 235–256.

46. Bather J. A. The Minimax Risk for the Two-Armed Bandit Problem // Mathematical Learning Models — Theory and Algorithms. 1983. Vol. 20.

P. 1–11.

47. Ben-Tal A., Margalit T., Nemirovski A. The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography // SIAM J. Optim.

2001. V. 12. No. 1. P. 79–108.

48. Berry D. A., Fristedt B. Bandit problems. Sequential Allocation of Experiments // London, New York: Chapman and Hall. 1985. P. 275.

49. G. E. P. Box, M. E. Muller. A Note on the Generation of Random Normal Deviates // Ann. Math. Stat. 1958. Vol. 29. № 2. P. 610–611.

50. Brochu E., Hoffman M., Freitas N. Portfolio Allocation for Bayesian Optimization // Uncertainty in Artificial Intelligence. 2011. P. 327–336.

51. Cesa-Bianchi N., Lugosi G. Prediction, Learning, and Games. New York:

Cambridge University Press. 2006. P. 394.

52. Fabius J., van Zwet W. R. Some remarks on the two-armed bandit // The Annals of Mathematical Statistics. 1970. Vol. 41. № 6. P. 1906–1916.

53. Juditsky A. B., Nazin A. V., Tsybakov A. B., Vayatis N. Gap-free Bounds for Stochastic Multi-Armed Bandit // Proceedings of the 17th World Congress The International Federation of Automatic Control Seoul. Korea. July 6-11. 2008.

P. 11560–11563.

54. Kuleshov V., Precup D. Algorithms for multi-armed bandit problems // CoRR, arXiv:1402.6028, 2014.

55. Lai T. L., Robbins H. Asymptotically Efficient Adaptive Allocation Rules // Advances in Applied Mathematics. 1985. Vol. 6. P. 4–22.

56. Lai T. L., Levin B., Robbins H., Siegmund D. Sequential medical trails (stopping rules/asymptotic optimality) // Proceedings of the National Academy of Sciences of the USA. 1980. Vol. 77. № 6. P. 3135–3138.

57. Li L., Chu W., Langford J., Schapire R. E. A contextual-bandit approach to personalized news article recommendation // Proceedings of the 19th

international conference on World wide web. WWW ’10. New York. NY. USA:

ACM. 2010. P. 661–670. URL: http://doi.acm.org/10.1145/1772690.1772758.

58. Nazin A. V., Miller B. The Mirror Descent Control Algorithm for Weakly Regular Homogeneous Finite Markov Chains with Unknown Mean Losses // Proceedings of 50th IEEE CDC ECC, Orlando, Florida, USA, 2011. December 12-15. 2011. P. 5.

59. Robbins H. Some aspects of the sequential design of experiments // Bulletin AMS. 1952. Vol. 58(5). P. 527–535.

60. Scott S. L. A modern Bayesian look at the multi-armed bandit // Applied Stochastic Models in Business and Industry. 2010. Vol. 26. № 6. P. 639–658.

61. Sragovich V. G. Mathematical Theory of Adaptive Control // World Scientific.

Interdisciplinary Mathematical Sciences. New Jersey. London. v. 4. P. 473

62. Villar S. S. et al. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges // Statistical Science. 2015. V. 30. №. 2.

C. 199–215.

63. Vogel W. An asymptotic minimax theorem for the two-armed bandit problem.

// Ann. Math. Stat. 1960. V. 31. P. 444–451.

64. Vogel W. A sequential design for the two armed bandit. // Ann. Math. Stat.



Похожие работы:

«УДК. 621.879:69.002 АНАНИН ВЛАДИМИР ГРИГОРЬЕВИЧ, докт. техн. наук, профессор, Avg@tsuab.ru МУРАВЛЕВА НАТАЛЬЯ НИКОЛАЕВНА, старший преподаватель, natalyants05@mail.ru ЭМИЛОВ АХМЕТ БАКЫТБЕКОВИЧ...»

«Акционерное общество Типовая форма № 01.02.03.ДО.01 Банк «Северный морской путь» «Договор об осуществлении перевода денежных средств» УТВЕРЖДЕНА Приказом ОАО «СМП Банк» от 06 декабря 2013 г. № 3666 и введена в действие с 10.12.2013 ДОГОВОР № ОБ ОСУЩЕСТВЛЕНИИ ПЕРЕВОДА ДЕНЕЖНЫХ СРЕ...»

«обоРудование коллективного пользования в учРеждениях дво Ран ИНСТИТУТ КОСМОФИзИЧЕСКИХ ИССЛЕДОВАНИй И РАСПРОСТРАНЕНИЯ РАДИОВОЛН ДВО РАН Ответственный за оборудование: Б ы ч к о в Василий Валентинович Тел.: 8-909-838-50-82..: E-mail:ikir@ikir.kamchatka.ru vasily.bychkov@gmail.com Адрес: 684034, Камчатская обл., Елизовский район, пос....»

«Всероссийский конкурс юношеских учебно-исследовательских работ Российского общества историков-архивистов «ЮНЫЙ АРХИВИСТ» Муниципальное бюджетное общеобразовательное учреждение «Хохряковская средняя общеобразовательная школа» Завьяловского района Удмуртской Республик...»

«WW 10 ноября 2014 г. ТЕХНИЧЕСКИЙ АНАЛИЗ Роман Османов +7 (495) 777-10-20, доб. 77-47-83 Глобальные рынки Osmanovr@psbank.ru S&P 500: недельный график. Положительный сантимент привел рынок к новым историческим высотам. Р...»

«Путов Антон Викторович АВТОМАТИЗИРОВАННЫЙ МОБИЛЬНЫЙ ЭЛЕКТРОМЕХАНИЧЕСКИЙ КОМПЛЕКС ДЛЯ НЕПРЕРЫВНОГО ИЗМЕРЕНИЯ ФРИКЦИОННЫХ СВОЙСТВ АЭРОДРОМНЫХ И АВТОДОРОЖНЫХ ПОКРЫТИЙ Специальность: 05.09.03 – Электротехнические компле...»

«УДК 330.3 Правоохранительная деятельность как государственная услуга: борьба с организованной преступностью и коррупцией Быков В.Н. pro1@gunipt.spb.ru Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики. Институт холода и биотехноло...»

«МЕЖГОСУДАРСТВЕННЫЙ СОВЕТ ПО СТАНДАРТИЗАЦИИ, МЕТРОЛОГИИ И СЕРТИФИКАЦИИ (МГС) INTERSTATE COUNCIL FOR STANDARDIZATION, METROLOGY AND CERTIFICATION (ISC) ГОСТ МЕЖГОСУДАРСТВЕННЫЙ 31809СТАНДАРТ БАРДА КОРМОВАЯ Технические условия Издание официальное Москв...»

«АНТОН КАЛИНИН Контакты Тел: +7(925)-705-25-95 E-mail: anton.m.kalinin@gmail.com LinkedIn: http://www.linkedin.com/pub/anton-kalinin/1b/62b/440 Профиль Опытный менеджер с 8 годами экспертизы в S...»

«ДОГОВОР №_ на техническое обслуживание и ремонт автотранспортных средств г. Барнаул «» _ 2014 г. ООО «АлтайСкан», именуемый в дальнейшем «Исполнитель», в лице Управляющего Индивидуального предпринимателя Рубан Андрея Григорьевича, действующего на основании Договора передачи полномочий единоличн...»

«МО Л ОТ О В С К И Й ОБЛАСТНОЙ З Е М Е Л Ь Н Ы Й О Т Д Е Л П. С. ЩЕРБИНА КАК НА ПАСЕКЕ ПОЛУЧИТЬ БОЛЬШЕ ВОСКА Гор. Мо л о т о в 1944 г sv* * 7 4 j :r ( м е л о т о в с к и й ОБЛАСТНОЙ з емельный о т д е л П. С. Щ ЕРБИНА КАК НА ПА...»

«Том 7, №3 (май июнь 2015) Интернет-журнал «НАУКОВЕДЕНИЕ» publishing@naukovedenie.ru http://naukovedenie.ru Интернет-журнал «Науковедение» ISSN 2223-5167 http://naukovedenie.ru/ Том 7, №3 (2015) http://naukovedenie.ru/index.php?p=vol7-3 URL статьи: http://naukovedenie.ru/PDF/102PVN315.pdf DOI: 10.15862/10...»

«Григорян Альвина Ивановна студентка Дзанагова Татьяна Яковлевна старший преподаватель Институт сервиса, туризма и дизайна (филиал) ФГАОУ ВПО «Северо-Кавказский федеральный университет» г. Пятигорск, Ставропольский край...»

«ЧЕЛОВЕК И СРЕДА ОБИТАНИЯ УДК 504.75:33: 621.564 Мазурин И.М.*, Королёв А.Ф.**, Уткин Е.Ф.***, Герасимов Р.Л.**** И.М. Мазурин А.Ф. Королёв Е.Ф. Уткин Р.Л. Герасимов Глобальная природоохранная гипотеза, создавшая глобальный кризис в выборе хладагентов. Часть 1 _ *М...»

«ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ АССОЦИАЦИЯ МОСКОВСКИХ ВУЗОВ СПЕЦИАЛИЗИРОВАННЫЕ ОБРАЗОВАТЕЛЬНЫЕ МАТЕРИАЛЫ Современные технологии обучения персон...»

«БОЕВЫЕ ИСКУССТВА В РЕГИОНАХ УКРАИНЫ БОЕВЫЕ ИСКУССТВА В РЕГИОНАХ УКРАИНЫ ДНЕПРОПЕТРОВСКАЯ ОБЛАСТЬ Днепропетровская область образована 27 февраля 1932 г. Регион является основной металлургической и машиностроительной базой Украины. Край металлургов силён...»

«Компьютерная алгебра (курс лекций) Игорь Алексеевич Малышев Computer.Algebra@yandex.ru (С) Кафедра «Компьютерные системы и программные технологии», Санкт-Петербургский государственный политехнический университет Лекция 13 Факторизация полиномов Курс КОМПЬЮ...»

«РЕГИОНАЛЬНАЯ ИННОВАЦИОННАЯ СИСТЕМА Минеев И.В., Мигунова Г.С. Орловский филиал Финансового университета при Правительстве РФ Орел, Россия REGIONAL INNOVATION SYSTEM Mineev I.V., Migunova G.S. Orel branch of the Financial University under the Government of the Russian Federation Orel, Russia...»

«ЗАХАРЧЕНКО Антон Сергеевич ОБОСНОВАНИЕ И РАЗРАБОТКА ТЕХНОЛОГИЙ ЗАКЛЮЧИТЕЛЬНОЙ ОТДЕЛКИ ТЕКСТИЛЬНЫХ МАТЕРИАЛОВ С ИСПОЛЬЗОВАНИЕМ ОТЕЧЕСТВЕННЫХ СТИРОЛМЕТАКРИЛОВЫХ И УРЕТАНОВЫХ ПОЛИМЕРОВ 05.19.02 – Технология и первичная обработка текстильных материалов и с...»

«Приложение 05.13.01 Системный анализ, управление и обработка информации ПРОГРАММА КАНДИДАТСКОГО ЭКЗАМЕНА Приложение к рабочей программе по дисциплине Системный анализ, управление и обработка информации, направленной н...»










 
2017 www.pdf.knigi-x.ru - «Бесплатная электронная библиотека - разные матриалы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.