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

Новгородский государственный университет имени Ярослава Мудрого

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

Олейников Андрей Олегович

Нахождение оптимальных планов параллельного

управления в случайной среде в приложении к

обработке данных

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

и комплексы программ

ДИССЕРТАЦИЯ

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

Научный руководитель д. ф.-м. н., доцент А. В. Колногоров Великий Новгород – 2014 2 Оглавление Введение.................................... Глава 1. Теоретические основы..................... 1.1. Краткий обзор литературы...................... 1.2. Описание решаемой задачи...................... 1.3. Поиск минимаксных стратегии и риска как байесовских..... 1.4. Выводы к первой главе........................ Глава 2. Стратегия параллельного управления........... 2.1. Нахождение минимаксного риска для параллельной обработки с группами переменного объема.................... 2.2. Влияние размеров групп для параллельной обработки на мини­ максный риск............................. 2.3. Оптимизация размеров групп для параллельной обработки... 2.4. Результаты численной оптимизации................. 2.5. Сравнение обработки с группами равного и различного размера для одинакового числа этапов.................... 2.6. Сложность алгоритма......................... 2.7. Сравнение с другими алгоритмами................. 2.8. Возможные дальнейшие усовершенствования........... 2.9. Выводы ко второй главе....................... Глава 3. Упрощенные стратегии.................... 3.1. О стратегиях.............................. 3.2. Способы получения упрощенных стратегий............ 3.3. Об оптимизации поиска рисков................... 3.4. Результаты численной оптимизации................. 3.5. Упрощенные стратегии для параллельной обработки с группами различного размера.......................... 3.6. Выводы к третьей главе........................ Заключение................................... Список литературы............................. Введение Целесообразное управление в случайной среде. В настоящее время все бльшую практическую значимость приобретают задачи принятия решений о в условиях неопределенности. К таким задачам относятся задача о целесооб­ разном поведении в стационарной случайной среде [2, 35], задача адаптивного управления [20, 32] и задача о двуруком бандите [31, 40, 44].

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

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

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

Математические ожидания 1 и 2 заранее не известны ЛПР. Цель управления состоит в максимизации дохода в некотором смысле [10, 13].

Для достижения поставленной цели используется некоторая стратегия.

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

Среда, в которой ведется управление, может быть описана векторным параметром = (1, 2 ). При этом, если бы параметры среды были известны заранее, то оптимальная стратегия предписывала бы всегда выбирать действие, которому соответствует большее из значений 1, 2. Ожидаемый доход от применения такой стратегии составил бы max(1, 2 ). Если же параметр неизвестен, то функция характеризует потери вследствие неполноты информации. Здесь, обознача­ ет математическое ожидание по мере, порожденной стратегией и парамет­ ром [10].

Над аналогичными задачами работало несколько групп исследователей, поэтому для них существует несколько различных названий и подходов. В западной литературе у задачи появилось название «задача о двуруком банди­ те» [68]. Суть задачи: есть некоторый игральный автомат с двумя ручками.

За одну игру с автоматом игрок может дернуть одну из двух ручек. Автомат с какой-то вероятностью выдаст игроку единичный выигрыш. Вероятность выигрыша для каждой ручки постоянна, но не известна игроку. Цель — получить максимальный суммарный выигрыш за заданное количество игр.

Такая постановка задачи часто называется «бернуллиевским двуруким банди­ том» [10, 13, 39, 46, 52] из-за характера распределения доходов за применение ручек.

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

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

Изменим стратегию управления, а именно разобьем все данные на несколь­ ко групп, и ко всем данным в группе будем применять один и тот же способ обработки. Количество данных, обработанных успешно, в каждой группе в силу центральной предельной теоремы будет иметь распределение, близкое к нормальному. Поэтому для таких групп данных мы можем использовать описанную выше модель управления, используя количество успешно обрабо­ танных данных в качестве результата обработки группы. Разбиение данных на группы с одинаковым способом обработки может быть полезно в случае, если изменение способа обработки — дорогая операция, также оно позволяет ввести их параллельную обработку (что позволяет сократить время, необходимое для обработки). При этом важно, что при достаточно большом числе этапов управления (30 – 50) потери при параллельной обработке уже будут близки к потерям для обработки таких данных последовательно [10, 13].

Есть несколько подходов к данной задаче. Один из них — это минимакс­ ный подход. При таком подходе находится стратегия управления, приводящая к наименьшим потерям для наихудшего значения параметра среды. Нас будет интересовать множество допустимых параметров среды где — некоторая константа (0 < < ). В таком случае минимаксный риск будет равен:

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

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

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

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

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

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

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

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

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

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

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

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

3. Исследование способов упрощения стратегий и влияния упрощений на полученные доходы.

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

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

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

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

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

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

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

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

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

1. XIX научная конференция преподавателей, аспирантов и студентов НовГУ, 2 – 7 апреля 2012 г., Великий Новгород.

2. 8-я международная Петрозаводская конференция «Вероятностные мето­ ды в дискретной математике», 2 – 9 июня 2012 г., Петрозаводск.

3. 55-я научная конференция МФТИ «Проблемы фундаментальных и при­ кладных естественных и технических наук в современном информацион­ ном обществе», 19 – 25 ноября 2012 г., Долгопрудный, Московская обл.

4. XX Всероссийская Школа-коллоквиум по стохастическим методам/XIV Всероссийский симпозиум по прикладной и промышленной математике, 12 – 18 мая 2013 г., Йошкар-Ола.

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

6. 56-я научная конференция МФТИ «Актуальные проблемы фундамен­ тальных и прикладных наук в современном информационном обществе», 25 – 30 ноября 2013 г., Долгопрудный, Московская обл.

А также на следующих семинарах:

1. Семинар кафедры прикладной математики и информатики Новгородского государственного университета им. Ярослава Мудрого, 19 ноября 2013 г., Великий Новгород.

Публикации. Материалы диссертации опубликованы в 9 печатных рабо­ тах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК [16, 24], 1 статья в сборнике трудов конференций [21], 1 депонированная рукопись [15] и 5 тезисов докладов [17, 22, 23, 25, 26].

«Программа поиска оптимальных размеров групп данных для параллель­ ной обработки» из представленного комплекса программ зарегистрирована в Реестре программ для ЭВМ №2013614359 от 29.04.2013.

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

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

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

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

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

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

Общий объем диссертации — 111 страниц, включая 18 рисунков. Список литературы содержит 69 наименований.

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

1.1.1. Автоматный подход В 60-е годы инициатором развития автоматного подхода в Советском Союзе был М. Л. Цетлин, который написал ряд статей о целесообразном поведении в случайной среде, например [33, 34].

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

Под случайной внешней средой в данном случае понимается модель внешнего мира, в котором есть несколько возможных действий организма и все возможные реакции среды делятся на два класса: благоприятные («не штраф») и неблагоприятные («штраф»). Каждый из исходов (реакций среды) может случиться с какой-то вероятностью, априорно не известной организму.

Таким образом, рассматривается автомат, заданный каноническими урав­ нениями:

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

Целесообразным поведением обладает автомат, для которого математиче­ ское ожидание выигрыша выше, чем для автомата, который совершает свои действия равновероятно, независимо от реакции среды [2, 35]. Для такого автомата математическое ожидание доходов равно где — количество выходных сигналов автомата, называемых действиями, — вероятность благоприятного исхода при выборе -го действия.

К автоматному подходу относится термин «симметрический автомат»

— автомат, доходы которого не изменяются во всех средах, полученных из первоначальной всеми возможными перестановками параметров. Как правило, исследуются именно автоматы, являющиеся «симметрическими».

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

Различными исследователями было предложено несколько различных ва­ риантов автоматов. Один из них — автомат с линейной тактикой. В простейшем случае он имеет два состояния: «выбирать первое действие» и «выбирать второе действие». Если после выбора действия результат благоприятный — автомат остается в текущем состоянии, если нет — переходит в другое. В [35] показано, что даже такой автомат обладает целесообразным поведением.

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

Исследование зависимости целесообразности поведения таких автоматов от объема внутренней памяти показало, что при увеличении размера памя­ ти простого линейного автомата математическое ожидание выбора лучшего варианта также увеличивается. В [35] такая последовательность называется асимптотически-оптимальной последовательностью конечных автоматов.

Похожей структурой обладает автомат Роббинса-Кринского [19] («до­ верчивый» автомат). Отличительной особенностью такого автомата является поведение в случае благоприятного исхода. В этом случае он переходит в самое глубокое состояние на ветви состояний, в которых выбирается опробованное действие.

Как показали предыдущие исследования, увеличение размера памяти линейного и «доверчивого» автомата увеличивает вероятность благоприятной реакции. Однако такие автоматы нельзя просто наделить бесконечным количе­ ством состояний — в таком случае их поведение перестает быть целесообразным.

Например, автомат Роббинса-Кринского при благоприятной реакции должен будет сразу уйти в бесконечное состояние.

Одним из способов решения этой проблемы являются автоматы с расту­ щей памятью [9]. Емкость памяти таких автоматов растет вместе с увеличением номера этапа управления.

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

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

Целесообразность такого автомата была изначально проверена только при помощи моделирования на ЭВМ (хотя в статье [5] можно найти аналитические соображения по поводу целесообразности данного автомата в стационарной случайной среде). В более поздней работе [20] показано, что стохастический автомат Варшавского и Воронцовой (а также ряд других стохастических автоматов) не гарантирует с вероятностью 1 оптимального поведения в про­ извольной среде.

Автоматному подходу посвящено большое количество работ. Этот подход развит в различных направлениях, например [2, 35]:

1. Коллективное поведение автоматов (игры автоматов). В общем виде рассматриваются вопросы коллективного поведения автоматов, теория игр же используется как удобный аппарат для описания взаимодействия нескольких субъектов. Однако рассмотрение игр автоматов отличается от принятого в теории игр. Обычно в теории игр игроки заранее знают систему платежных функций игры и выбирают стратегию, пользуясь этой информацией и различными вычислительными методами. В описываемой же постановке рассматриваются игры, о которых у игроков нет априорной информации. Вследствие этого игроки вынуждены выбирать свою страте­ гию не заранее, а прямо во время игры. При этом предполагается, что игра состоит из многократно повторяющихся партий, таким образом автоматы могут получать данные о возможных результатах применения стратегий на основе предыдущих игр (игры автоматов также рассматриваются, например, в [4, 6]).

2. Поведение автоматов в средах, не являющихся стационарными. Например, поведение автоматов в составной случайной среде (среда, в которой значения параметров описываются цепью Маркова).

3. Задачи с непрерывным временем.

Инженерному применению автоматного подхода к прикладным задачам посвящена книга Д. А. Поспелова [30]. В ней рассмотрены вопросы синтеза автоматов с нужными свойствами и исследование поведения вероятностных автоматов в различных средах. Главная цель книги — описание применения вероятностных автоматов на практике.

В [30] также собраны некоторые возможные приложения автоматов. К ним отнесены: регулирование движения через автомобильный перекресток, распределение потока задач в мультипрограммной системе, система управления обслуживанием в периодическом режиме, система управления многокаскадной схемой коммуникации.

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

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

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

1.1.2. Адаптивное управление После автоматного подхода следует более общая теория, а именно теория адаптивного управления.

Направление адаптивного управления в нашей стране активно разви­ валось В. Г. Сраговичем [32, 64]. В [32] предлагается использовать иденти­ фикационный подход, основанный на идее оценки математических ожиданий доходов 1 и 2 за применение первого и второго действия соответственно.

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

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

При получении таких оценок появляется желание сразу же воспользовать­ ся стратегией «Play-the-leader». Данная стратегия предлагает сначала провести исследование действий, выбрав каждое по раз, а затем всегда выбирать то действие, которому соответствует бльшая оценка. Однако можно заметить, что такой вариант является неоптимальным если полное время управления неограничено.

Действительно, допустим что 1 > 2, однако на первых 2 шагах в силу случайности доходов среднее значение для первого действия оказалось меньше, чем 2 (1 < 2 ). В таком случае стратегия будет предписывать выбирать второе действие и оценка для него будет приближаться к действи­ тельному значению 2. Если 1 2, может получиться, что оценка для второго действия никогда не станет меньше оценки для первого и будет всегда выбираться субоптимальное действие.

В [32] предложен -автомат. Упрощенно реализуемую им стратегию мож­ но описать так: на первом этапе каждое действие выбирается по раз, затем управление ведется в соответствии с полученными оценками. При этом с вероятностью будет выбираться действие, которому соответствует меньшая оценка. Действие, которому соответствует бльшая оценка, будет выбрано, соответственно, с вероятностью (1 ). После каждого шага оценка для выбранного действия корректируется.

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

В качестве усовершенствования предложен также -автомат. Он от­ личается применением действий с вероятностями и (1 ), где — номер шага. выбирается экспертом, при этом для того, чтобы -автомат был асимптотически оптимальным, необходимо, чтобы она соответствовала следующим условиям:

Важным преимуществом -автомата является возможность подстраи­ ваться под горизонт управления.

Одной из особенностей [32] является исследование поведения автоматов в очень широком перечне сред, например: применение автоматов в марковских процессах, стационарных процессах, цепях маркова с доходами. Также в [32] есть раздел, посвященный играм автоматов.

Другой подход к адаптивному управлению описан в книге А. В. Назина и А. С. Позняка [20]. Важным отличием этой работы от предыдущих работ по стохастическим автоматам (например [2]) являются строгие математические доказательства оптимальности предложенных решений при помощи метода стохастической аппроксимации. В [20] также получены оценки сходимости для работы различных автоматов в случайной среде. Кроме того, рассмотрены такие модификации задачи адаптивного выбора вариантов, как задачи безуслов­ ной минимизации потерь для небинарных сред с неограниченными потерями, условная минимизация, игры автоматов, управление конечными марковскими цепями.

Для решения задачи адаптивного управления с использованием ран­ домизированной стратегии в [20] предлагается использовать рекуррентные алгоритмы адаптивного выбора вариантов (действий), определяемые последо­ вательностями правил вида:

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

Порядок сходимости к нулю потерь при росте для одного из алгоритмов, предложенных в [20] — (1/3 ). Сам алгоритм:

где — длина шага, — числовой параметр, — оператор проектирования на -симплекс, { } — последовательность чисел из интервала (0; 1/ ), отделя­ ющая компоненты вектора от нуля [20].

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

При этом уровней иерархии может быть и больше двух.

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

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

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

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

= {(1, 2 ) : |1 2 | 2}. Обозначим через априорное распределение параметра на множестве. Величина называется байесовским риском, а соответствующая стратегия — байесов­ ской [10].

Среди книг, посвященных байесовскому подходу, в нашей стране можно отметить книгу Э. Л. Пресмана и И. М. Сонина [31]. Из зарубежных авторов можно отметить Берри (D. A. Berry) и Фристеда (B. Fristedt) [40], М. Де Гроота (M. H. DeGroot) [43] (есть перевод на русский язык — [7]). На примере этих книг видно, что байесовский подход имеет широкое применение в задачах последовательного управления в условиях неполноты информации.

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

При этом байесовский подход не обязательно должен применяться для дискретного времени, в работе [31] также описан и вариант с непрерывным временем.

Очень известна работа Фельдмана (Feldman) [45], в которой приведена следующая модификация задачи: известно, каковы вероятности выигрыша при выборе различных действий, но неизвестно, какому действию какой вы­ игрыш соответствует. Стратегия, предложенная Фельдманом, предписывает на каждом шаге выбирать действие, которому соответствует наибольшая апостери­ орная вероятность выигрыша (как будто каждый шаг является последним). Как оказалось такая «близорукая» стратегия обладает оптимальностью на любом горизонте управления в данной постановке задачи.

Байесовский подход также использовался в одной из первых (на это ука­ зывают, например [40], [56]) работ в области планирования последовательных экспериментов — статье Томпсона (W. R. Thompson) [66].

Асимптотическая байесовская теорема Лая-Роббинса [53, 55] описывает байесовские стратегии, которые при обеспечивают наименьшую скорость роста потерь. В статьях показано, как ведут себя асимптотические потери при для среды с действиями. Для примера рассмотрим среду с двумя действиями, нормально распределенными доходами и единичными дисперсиями. Для такой среды существуют стратегии, для которых асимпто­ тический рост потерь равен:

где (, ) — потери, 1 и 2 — математические ожидания реакции среды на выбор первого и второго действия соответственно. При этом для опреде­ ленности считаем, что 1 > 2 (хотя это и не известно ЛПР). (2, 1 ) — информационное число Куллбака-Лейблера (Kullback-Leibler), которое для случая двух действий равняется:

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

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

В [53] предложен способ нахождения верхней границы где функция () может быть, например, () = ln 1. С использованием (1.10) получаем следующую формулу для вычисления границы доверительного интер­ Несмотря на описанный недостаток (необходимость априорного распреде­ ления), байесовский подход активно используется в исследованиях, поскольку он предлагает удобный инструментарий для поиска стратегий управления в случайной среде (на это указывают в частности авторы [40]) и, в случае воз­ можности найти наихудшее априорное распределение, может быть использован для поиска минимаксной стратегии.

1.1.4. Минимаксный подход Первая работа, в которой предложено применять минимаксный подход, скорее всего — статья Роббинса (H. Robbins) [60].

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

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

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

Например, в статье Фабиуса (J. Fabius) и ван Цвета (W. R. Zwet van) [44] описан поиск минимаксного риска для задачи о двуруком бандите (с бернулли­ евским распределением), но авторам удалось найти минимаксный риск только для количества шагов меньшего 5. Для большего числа шагов поиск точного минимаксного риска является слишком сложной задачей.

Широко известна работа Фогеля (W. Vogel) [67], посвященная минимакс­ ному подходу. Фогель дает асимптотические оценки для минимаксного риска в задаче о двуруком бандите при количестве игр, стремящемуся к бесконечности.

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

Пороговая стратегия предложена в работе [68]. В стратегии, описанной в данной статье, использованы следующие ограничения: управление занимает шагов, при этом на первых 2 шагах мы используем каждое из двух действий по раз. На оставшихся 2 шагах мы используем только одно действие. Указано, что подобного рода стратегии не оптимальные, но могут быть использованы в реальных задачах, в случае, если, например, переключение с одного действия на другое — дорогая операция.

Данный результат был улучшен в статье Басера (J. A. Bather) [38]. А именно, улучшена оценка для минимальной границы минимаксного риска.

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

Однако в [38] не предлагается способа нахождения стратегии, которая со­ ответствовала бы такому риску. Там, так же как в [44], указано, что нахождение минимаксной стратегии для большого числа шагов — очень сложная задача.

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

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

В основе данного подхода лежат работы Гиттинса (J. C. Gittins), напри­ мер [48]. Индексы Гиттинса являются известным инструментом для решения задач, подобных задаче о планировании и задаче о многоруком бандите.

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

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

Обобщению индексов Гиттинса для применения к задачам о Марковском процессе принятия решений [8] и представлению «Elimination algorithm» — ре­ курсивного алгоритма для их вычисления, посвящена статья И. М. Сонина [63].

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

Несмотря на то, что первые работы по индексам Гиттинса относятся к концу 70-х годов, интерес к ним существует до сих пор, о чем свидетельствует книга, написанная коллективом авторов: Гиттинс, Глэйзебрук (K. Glazebrook) и Вебер (R. Weber) [47]. Данная книга является переизданием книги, написанной Гиттинсом в 1989 году. В книге приведено несколько вариантов доказательства оптимальности индексов Гиттинса.

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

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

1.1.6. Другие современные подходы Несмотря на большое количество приведенных работ, интерес к этой задаче не пропадает. Новые подходы продолжают появляться. К таким новым подходам можно отнести метод поиска решения для задачи о многоруком банди­ те с использованием алгоритма зеркального спуска. Данная идея развивается в работах Н. Ваятиса, А. В. Назина, А. Б. Юдицкого, А. Б. Цыбакова [50] и А. В. Назина и Б. Миллера [58].

Подход используется для решения задачи о многоруком бандите с неиз­ вестным горизонтом. Метод зеркального спуска известен с 70 годов, однако о его применении к данной задаче до этих работ автору не известно. Хотя рассматриваемая цель стратегии, как и во многих подобных работах, — умень­ шение средних асимптотических потерь (средних потерь при стремящемся к бесконечности количестве экспериментов), авторы также рассматривали возможность уменьшения потерь на ранних этапах управления. Полученные оценки верхней границы потерь составили:

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

Данный метод также может быть применен для решения широкого круга задач, например, в [58] описано его применение к Марковскому процессу принятия решений (используется конечная Марковская цепь).

Данные результаты развиты в [57], где описывается применение мето­ да зеркального спуска к задаче о многоруком бандите, которая описывает Марковский процесс принятия решений (основы применяемого метода описаны в [58]).

В статье Ауэра (Auer), Чеза-Бйанки (Cesa-Bianchi) и Фишера (Fischer) [37], продолжающей работу начатую в [36], предложен другой подход: описан про­ стой для реализации алгоритм поведения для стратегии управления в задаче о многоруком бандите — UCB1. Описанный алгоритм предназначен для неиз­ вестного заранее конечного числа шагов и очень удобен для применения на практике.

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

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

2. Выбираем ручку с наибольшим значением данной величины.

Также в [37] описаны модификации данного алгоритма, названные UCB и UCB1-NORMAL, приведены результаты численных экспериментов с приме­ нением указанных алгоритмов и -GREEDY. Название последнего взято из книги Саттона и Барто [65], описанному алгоритму соответствует -автомат Сраговича. Он используется для сравнения с разработанными алгоритмами. В итоге различные алгоритмы дают различные результаты на разных распреде­ лениях и нет возможности однозначно сказать, какой из них лучше в общем случае. Хотя стоит заметить, что UCB2 почти на всех предложенных тестах был немного хуже UCB1.

Популярным на западе названием для класса задач, подобных рассмат­ риваемой в данной диссертации, является «Reinforcement Learning» [51, 65].

На русский язык этот термин обычно переводят как «обучение с подкреплени­ ем». Такой способ машинного обучения отличается от «обучения с учителем»

(«Supervised learning»). В последнем случае обучение обычно проходит на за­ ранее подобранном наборе примеров и контролируется внешним наблюдателем («учителем»).

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

Однако среди них нет подходов, адаптированных для параллельного управле­ ния.

1.1.7. Параллельное управление В задачах о медицинских экспериментах (о лечении пациентов) часто применяется рассматриваемая задача именно в случае параллельной обработки.

Действительно, рассмотрим задачу о лечении пациентов. Есть пациентов и два лекарства, при этом неизвестно, какое из лекарств эффективнее. Как правило, предполагается, что результаты лечения можно разделить на два класса: «успешное» и «не успешное» (бинарное распределение).

Важная особенность данной задачи заключается в том, что лечение, как правило, длительный процесс, поэтому врач не может себе позволить лечить пациентов по одному (в таком случае лечение пациентов затянулось бы на неприемлемо долгое время). По этой причине врач просто вынужден применять параллельную обработку: давать одно и то же лекарство группе пациентов и наблюдать их общую реакцию. В простейшем случае такая постановка подразумевает два этапа управления: на первом этапе врач дает первое и второе лекарство первым двум (небольшим) группам пациентов, а на втором дает оставшимся пациентам лучшее лекарство. Но даже в более сложных схемах количество этапов не бывает слишком велико (как правило не больше, чем три – четыре) [12].

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

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

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

С другой стороны, в зарубежной литературе очень часто предлагается применение данного подхода к планированию медицинских экспериментов [38, 40, 42, 48, 54, 69].

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

Например, [56] и [62]. Последняя посвящена применению многоруких бандитов в веб-сервисах. Данная работа, как и многие другие современные работы прак­ тической направленности, основана на эвристических методах. Приведенная в работе эвристика основана на том, что действия выбираются случайным образом, а вероятность выбора конкретного действия зависит от вероятности того, что это действие — лучшее. Метод, который автор предлагает применять к задаче о многоруком бандите, — RPM (Randomized probability matching).

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

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

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

Также информацию о прикладном применении задачи о многоруком бандите можно найти в книге Чеза-Бйанки и Люгоси (G. Lugosi) [41], посвя­ щенной прогнозированию последовательностей в различных областях. В [41] указывается на множество возможных приложений прогнозирования в после­ довательностях, среди них проблемы сжатия и кодирования информации.

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

В данной диссертации предлагается применение к обработке данных.

Эта идея описана, например, в [10, 14]. Пусть имеется некий объем данных ( ) для обработки. Результат обработки каждой единицы данных является случайной бинарной величиной и равняется 1, если обработка успешная, и 0 — в противном случае. Возможные действия: использовать первый способ обработки и использовать второй способ обработки. При этом вероятность успешной обработки составляет 1 и 2 для первого и второго метода соот­ ветственно. Эти вероятности фиксированы, но заранее не известны. Целью является максимизация числа успешно обработанных данных. Такие данные можно разбить на пакетов по данных в каждом. При этом все данные в пакете будем обрабатывать, используя один способ. Результатом обработки пакета будет количество успешно обработанных данных. Это количество в силу центральной предельной теоремы будет иметь распределение, близкое к нормальному, поэтому для обработки пакетов можно применять подход, описанный во введении (управление в случайной среде с двумя действиями и нормальным распределением доходов).

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

Хотелось бы упомянуть о книге Э. Полака (E. Polak) [59]. Эта книга также переведена на русский язык [29]. В ней систематизирован большой объем различных алгоритмов оптимизации, к ним даны многочисленные коммента­ рии и рекомендации. Алгоритмы описаны на естественном языке, что было очень полезно при реализации данных алгоритмов для комплекса программ, используемого для исследований в данной диссертации (в частности, алгоритма наискорейшего спуска для поиска упрощенных стратегий). Также большое вни­ мание уделено анализу приведенных алгоритмов (а именно: доказательствам сходимости алгоритмов, сравнения их эффективности и т. д.).

Еще одна работа посвящена решению проблем при обучении нейронных сетей, вызванных необходимостью вычислять значение экспоненты очень часто (реализация данной функции в стандартной библиотеке языка Си является относительно медленной). Это статья Шрaудольфа (Schraudolph) [61], в которой он предлагает способ быстрого вычисления при помощи аппроксимации и использования знания о стандартах кодирования вещественных чисел IEEE 754, используемого в языке Си++.

Кроме того, при реализации комплекса программ использовалась книга Т. Кормена, Ч. Лейзерсона и других [18] (использовался перевод на русский язык). Это фундаментальная работа в области программирования, которая, кроме систематизации известных алгоритмов для самых разнообразных задач, также предлагает их строгий математический анализ, включает тщательный анализ их производительности. Книга содержит изложение математических основ приведенных алгоритмов (таких как теория множеств, комбинаторика, теория вероятности и т. д.). Также в ней даны ценные замечания по процессу разработки алгоритмов. Информация, приведенная в [18] использовалась, в частности, для оценки эффективности предлагаемого в диссертации алгоритма.

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

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

В статье [13] развернуто описание применения байесовского метода к параллельному управлению. Даны инвариантные рекуррентные формулы для нахождения рисков, описаны оптимизации для параллельной обработки аг­ регированных данных. Приведены результаты моделирования с применением агрегированных данных с распределением, отличным от нормального (бинар­ ным).

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

1.2. Описание решаемой задачи Исследуемая задача является модификацией задачи о целесообразном поведении в случайной среде [2, 35], также известной как задача о двуруком бандите [31, 40, 44] и задача адаптивного управления [20, 32]. Рассматривается некоторый управляемый процесс на конечном дискретном отрезке времени.

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

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

Модификация, применяемая в рассматриваемой задаче: доходы от приме­ нения действий имеют нормальное распределение, тогда как в литературе чаще всего рассматриваются бинарные среды (или так называемый бернуллиевский двурукий бандит [40]), в которых доход может быть 1 или 0 с какой-то веро­ ятностью. Интерпретация этих двух значений, как правило, «благоприятный исход» и «неблагоприятный исход».

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

Использование нормального распределения позволяет удобно применять данный подход к параллельной обработке. Такую обработку можно рассмотреть на примере обработки данных. Представим, что нам необходимо обработать большой объем данных, количество которых кратно горизонту управления в рассматриваемой задаче (например, · данных). Для обработки мы можем применять один из двух способов, доходы (результаты обработки) также имеют нормальное распределение с математическими ожиданиями 1 и 2 и единичными дисперсиями. Для таких данных мы можем ввести параллельную обработку, а именно разделить все данные на пакетов по данных и ко всем данным в одном пакете применить одинаковый способ обработки одновременно.

Затем по результатам процесса обработки бинарных данных мы можем найти результаты процесса [10]:

Также мы можем обрабатывать параллельно данные, результат обработки которых имеет бинарные распределения. Мы имеем два возможных результата:

1 «обработка успешная» и 0 «обработка неуспешная». Вероятность успешной обработки для первого способа обработки 1, для второго 2. При этом известно, что 1 и 2 близки к (0 < < 1). Разобьем эти данные на пакетов по данных, будем применять ко всем данным в пакете одинаковый способ обработки. В таком случае результат процесса будет равен:

где = (1 ). В силу центральной предельной теоремы распределение будет близким к нормальному [14].

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

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

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

Если бы параметры распределений были известны заранее, то оптималь­ ная стратегия предписывала бы просто выбирать на каждом шаге действие, которому соответствует большее математическое ожидание. Ожидаемый доход от применения такой стратегии составил бы (1 2 ). Однако в нашем случае параметры распределений заранее не известны и функция характеризует потери дохода вследствие неполноты информации. Здесь, обозначает математическое ожидание по мере, порожденной стратегией и параметром.

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

Существует несколько подходов к подобным задачам (имеется в виду задача об управлении в стационарной случайной среде). Один из них — минимаксный. При минимаксном подходе максимальные потери на множестве параметров среды минимизируются по множеству стратегий. Величина называется минимаксным риском, а соответствующая стратегия (если она суще­ ствует) — минимаксной стратегией [10]. Минимаксная стратегия обеспечивает робастное управление, так как ожидаемый доход для любой среды, описывае­ мой параметрами из множества, отличается от максимально возможного не более чем на величину минимаксного риска. Эта постановка рекомендована в работе [60], вызвавшей большой интерес к рассматриваемой задаче. Минусом такого подхода, как уже было описано выше, является высокая сложность вычисления точного минимаксного риска и поиска соответствующей страте­ гии. Вследствие этого существует не так много работ, в которых рассмотрен минимаксный подход. К основным можно отнести [10, 44, 60, 67]. Также минимаксному подходу посвящен раздел [40].

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

1.3. Поиск минимаксных стратегии и риска как байесовских В данной работе используется доказанная в [10] возможность поиска ми­ нимаксного риска как байесовского для наихудшего априорного распределения.

Ниже кратко опишем основные положения [10]. Ключевым моментом в доказа­ тельстве является аналог основной теоремы теории игр (задача рассмотрена как игра с природой, где — множество решений лица, осуществляющего управление, — множество решений природы):

Теорема 1. Рассматриваемая игра имеет цену и минимаксные стратегии обоих игроков. Иными словами, существуют наихудшее априорное распреде­ ление 0 на и минимаксная смешанная стратегия 0 на, такие что Распределения {} можно со сколь угодно высокой точностью считать имеющими плотности. Множества {} и совпадают, поэтому с учетом равенств sup{} (, ) = sup (, ), inf (, ) = () из (1.27) следует, что т.е. минимаксная стратегия и риск совпадают с байесовскими на наихудшем априорном распределении.

Здесь 0 — распределение решений природы (смешанная стратегия), — аналогичное распределение для решений лица, осуществляющего управление.

Поиск наихудшего распределения основан на следующих результатах:

Лемма 1. Перечисленные ниже преобразования априорной плотности рас­ пределения не меняют байесовский риск, т. е. () = ():

2) (2) (1, 2 ) = (1 +, 2 + ) (для всех 1, 2 и любого фиксирован­ Хорошо известно также свойство вогнутости байесовского риска:

Лемма 2. Если 1, 2 0 и 1 + 2 = 1, то выполняется неравенство:

Изменим параметризацию, а именно: положим 1 = +, 2 =.

Тогда = ( +, ), = { : || }. В новых переменных апри­ орную плотность распределения обозначим (, ). Из леммы 1 следует, что байесовский риск не изменяется при следующих преобразованиях априорного распределения:

Отсюда следует, что наихудшее априорное распределение всегда может быть выбрано симметрическим, т. е. (, ) = (, ). Действительно, в случае, если (, ) является наихудшим, но не является симметрическим, то 0,5((, ) + (, )) является симметрическим и в силу леммы 1 и леммы выполняется следующее неравенство:

Аналогично плотность 0,5((+, )+(, )) не уменьшает байесовский риск по сравнению с (, ), но является более однородной по, чем (, ).

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

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

Теорема 2 позволяет написать уравнения для вычисления байесовского риска. Вычисления основаны на рекуррентном вычислении рисков 1,2 (), Теорема 3. Пусть (, ) выбрана из условия (1.33) и. Тогда Байесовский риск вычисляется по формуле:

Теорема 2 дает основу для численного поиска минимаксной стратегии как байесовской, а теорема 3 задает формулы для поиска рисков методом динамического программирования. Будем считать, что плотность () вырож­ денная, и она сосредоточена в двух точках = ± 1/2 с вероятностями 1/2. Такое предположение позволяет провести поиск наихудшего распределения при помощи численного моделирования. Действительно, у нас получается множество где = 1/2. характеризующее все априорные распределения на множестве, удовлетворяющие нашему предположению. Таким образом, каждое распре­ деление характеризуется только параметром. Теперь для поиска наихудшего распределения достаточно применить какой-нибудь метод численной однопара­ метрической оптимизации.

Рис. 1.1. Риски для различных априорных распределений На рисунке 1.1 показаны результаты вычисления байесовского риска для = 15 и различных (сплошной линией). Здесь — приведенный байесовский риск, = 1/2. На графике видно, что существует такое, при котором риск максимальный. Это значение и характеризует наихудшее априорное распре­ деление. На том же графике видно, что наихудшее распределение зависит от ограничения на допустимые значения параметра. Действительно, при = 5,5, которому соответствует график на рисунке 1.1, наихудшее распределение имеет место при = 5,5, однако при уменьшении до 4,3, наихудшему распределению будет уже соответствовать = 1,7.

Объяснение поведения графика зависимости потерь от величины сле­ дующее: когда становится слишком большой, общие потери в основном определяются потерями на первых двух шагах. Если же достаточно мала, то общие потери определяются потерями на всем горизонте управления. Поэтому нас больше интересуют среды, для которых не слишком велико (например, не выше 4,3 для описанного случая).

Данный факт может быть проиллюстрирован пунктирной линией на рисунке 1.1. Этой линией показаны риски для всех шагов, кроме первых двух. Видно, что при увеличении такие риски достаточно быстро начинают убывать, и имеют максимум в точке = 1,7.

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

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

Стратегия, соответствующая максимуму байесовского риска, может быть за­ помнена.

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

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

Соответствие полученной стратегии и ожидаемых потерь может быть про­ верено другой программой комплекса — demoRtest. Одна из функций этой про­ граммы — проверка стратегий описанного в этом разделе вида. Проверка про­ изводится при помощи моделирования методом Монте-Карло. Эксперименты показали, что для того, чтобы получить достаточно близкий к расчетному график потерь, необходимо повторить эксперимент порядка 107 раз. Однако этот факт позволяет значительно ускорить время проверки за счет параллель­ ной обработки. Действительно, каждое повторение эксперимента не зависит от другого и может быть выполнено параллельно. Для организации параллельных вычислений использован пакет openNP, который позволяет достаточно про­ сто распараллеливать однопоточные программы. Пример работы программы demoRtest показан на рисунке 1.3. Сплошной линией показаны потери, вычис­ ленные при помощи динамического программирования байесовским методом.

Пунктирной линией показаны результаты моделирования применения получен­ ной стратегии. Проведение необходимого количества тестов на ноутбуке автора (Intel Core Duo T2600 с тактовой частотой 2,16 ГГц) потребовало около минут.

r 0, Рис. 1.3. Сравнение вычисленных и полученных при помощи моделирования потерь Отметим, что все программы из представляемого программного комплек­ са были написаны на языке C++ для ОС Linux с использованием библиотек boost (для обработки параметров командной строки) и glib (используется генератор случайных чисел из данной библиотеки). boost является кроссплат­ форменной библиотекой, поэтому при необходимости можно адаптировать все программы для ОС Windows, поменяв способ получения случайных чисел.

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

Язык С++ был выбран в качестве основного по причине хорошего быстродействия написанных на нем программ и большого количества суще­ ствующих библиотек для данного языка. Также среди преимуществ следует отметить возможность использования написанного кода для разработки парал­ лельных/распределенных решений для поиска стратегий управления с бльшим горизонтом управления. Из минусов данного языка отметим большее время разработки и сложность отладки, отсутствие встроенных средств для визуа­ лизации. Также некоторые известные численные методы были реализованы заново с использованием описания алгоритмов из [29, 61]. Возможно, при использовании какого-либо специализированного языка (такого как Octave) в этом не было бы необходимости. Графики для данной диссертации были построены с использованием программы gnuplot.

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

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

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

Показан пример работы программы из комплекса программ, реализующей описанный подход. Показаны преимущества и недостатки выбранного для реализации языка программирования C++: из положительных сторон можно отметить скорость работы написанных программ, из отрицательных — время, необходимое для их написания.

Основные результаты первой главы были представлены на XIX научной конференции преподавателей, аспирантов и студентов НовГУ (2 – 7 апреля 2012 г., Великий Новгород), а также опубликованы в работах [15, 21].

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

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

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

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

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

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

2.1. Нахождение минимаксного риска для параллельной обработки с группами переменного объема Рассмотрим следующую стратегию: все реакции среды, = 1...

разобьем на группы размерами, где = 0..., > 0 так, что будет выполняться равенство 20 + 1 + 2 + · · · + =. В начале управления применим оба действия к группам объемом 0. На -м этапе одно и то же действие будем применять к группе объемом.

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

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

В данном случае ясно, что остается справедливой теорема 2 и наихудшее априорное распределение будет иметь вид: (, ) = ()(), где () — постоянная плотность при || ; () = () — симметричная плотность;

Соответствующий байесовский риск:

Обозначим через (| ) = (2)1/2 {( )2 /(2)} плотность нормального распределения с математическим ожиданием и дисперсией, а через (1, 2 ) — плотность априорного распределения на множестве параметров. Пусть предыстория процесса к моменту времени описывается набором (1, 1, 2, 2 ), где 1, 2 — полные количества применений обоих вариантов, причем 1 + 2 =, а 1, 2 – полные доходы за применение первого и второго варианта соответственно. Будем считать, что = 0 при = 0. Плотность апостериорного распределения определяется как Если положить (|) = 1 при = 0, то эта формула останется справедли­ вой и при 1 = 0 и/или 2 = 0.

Обозначим через (1 +2 ) (; 1, 1, 2, 2 ) байесовский риск на по­ следних (1 + 2 ) шагах, вычисленный относительно апостериорного распределения с плотностью (1, 2 |1, 1, 2, 2 ). Пусть + = max(, 0).

Тогда где 0 (·) = 0 (·) = 0, Здесь (1 +2 ) (·) – ожидаемые потери на оставшемся отрезке времени, если сначала выбирается -ый вариант, а затем управление ведется оптимально ( = 1,2). Байесовская стратегия предписывает выбирать вариант, которому соответствует меньшее из значений (1 +2 ) (·), (1 +2 ) (·), при их равен­ стве выбор может быть произвольным.

Приведем уравнения для вычисления байесовского риска. Они получают­ ся из уравнений (2.3) - (2.6), если формально считать априорную плотность постоянной по, что дает правильные выражения для апостериорных плотно­ стей при 1 0, 2 0. Кроме того, уравнения получаются проще для Обозначим через 1,2 () байесовский риск на последних (1 + 2 ) шагах относительно текущего апостериорного распределения, через 1,2 () — аналогичный риск, вычисленный при условии, что сначала раз выбирается -ое действие, а затем выполняется оптимальное управление (1 0, 2 0, = 1,2).

Дадим рекуррентное уравнение для вычисления байесовского риска, соот­ ветствующего стратегии параллельного управления:

Теорема 4. Пусть (, ) = ()(), где () — постоянная плотность при ||, плотность () = () — симметрическая на отрезке || и. Тогда справедливо рекуррентное уравнение:

При этом байесовский риск вычисляется по формуле:

Доказательство. Проверим формулу (2.9). Умножим левую и правую части (2.4) на 1,2 (1, 2 ). Тогда Здесь 1,2 (1, 2, ) нужно вычислять, считая априорное распределение по­ стоянным при всех (, +), то есть где = /, = 1,2. Функция ( ) не зависит от априорного распределения:

Очевидно, 1,2 (1, 2, ),, ( ) соответствуют приведенным в формулировке теоремы. Далее, при 1 +, 2 статистика пересчитывается по 1 1 = 1 ( 1 ), то после замены переменной интегрирования на получаем формулу (2.9). Формула (2.10) доказывается аналогично.

Математическое ожидание потерь можно найти при помощи аналогичных рекуррентных формул:

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

вычисляется по формуле При этом риски для конкретного значения параметра среды из могут быть найдены при помощи динамического программирования [1] и рекур­ рентных формул (2.8) – (2.12). Поиск осуществляется для заранее заданных значений. Методы нахождения параметров наихудшего априорного распре­ деления аналогичны описанным в первой главе: на множестве допустимых значений параметра (1.40) выбирается такое значение, при котором байесов­ ский риск максимальный.

На рисунке 2.1 байесовский риск, соответствующий применению парал­ лельной обработки с различными размерами групп, показан сплошной линией.

Пунктирной линией для сравнения показан риск, соответствующий примене­ нию обработки с одинаковыми размерами групп. Вычисления производились для = 16, для стратегии с различными размерами групп использовалось следующее разбиение на группы: 0 = 1, 1 = 2, 2 = 2, 3 = 2, 4 = 2, 5 = 2, 6 = 4. Таким образом, количество этапов управления для стратегии с одинаковыми размерами групп было больше. На графике видно, что зависимость байесовского риска от характеристики среды похожа для обработки с одинаковыми и обработки с различными размерами групп.

Все замечания по поводу нахождения наихудшего априорного распределения Рис. 2.1. Риски для различных априорных распределений для стратегии с параллельной обработкой с различными размерами групп из предыдущей главы актуальны и для данного графика. Находить риски и стратегии для таких распределений — одна из возможностей программы demoRStep1, входящей в состав комплекса программ. Также она может на­ ходить ожидаемые потери для таких стратегий по формулам (2.20) – (2.22).

Для тестирования же стратегий при помощи метода Монте-Карло может быть использована программа demoRtest.

2.2. Влияние размеров групп для параллельной обработки на минимаксный риск На основе описанных в предыдущем разделе сведений можно начать ис­ следование влияния размеров групп данных на минимаксный риск. Обозначим через 0,..., текущее разбиение. При этом > 0 для 0. Будем считать фиксированной константой, то есть менять будем только размеры групп данных, но не их количество.

Возьмем для примера = 16, = 6. Результаты для одного из разбиений с такими параметрами и уже представлен на рисунке 2.1.

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

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

На рисунке видно, что даже небольшое изменение разбиения может сильно изменять байесовские риски. Однако следует отметить, что столь значительные изменения являются следствием изменения первой группы (0 ).

Действительно, стратегия для (2) предписывает в начале управления выбрать Рис. 2.2. Риски для различных разбиений на группы для параллельной обработки каждое действие по два раза, и если разница между математическими ожида­ ниями достаточно высока — потери на первых двух этапах обработки уже не смогут быть компенсированы за счет дополнительной информации, полученной на них. На рисунке мы видим, что потери растут почти линейно с увеличением разницы математических ожиданий.

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

2.3. Оптимизация размеров групп для параллельной Как сказано в предыдущем разделе, рекуррентные формулы (2.8) – (2.12) позволяют найти байесовский риск для заданных размеров групп. Основная же задача в поиске оптимальных планов параллельной обработки — это нахождение оптимальных размеров таких групп.

Методика нахождения минимаксных стратегии и риска для заданного разбиения данных на группы 0, 1,..., как байесовских показана вы­ ше. Такой минимаксный риск можно обозначить как (0, 1,..., ) при Задача состоит в поиске оптимального разбиения Получившаяся задача является задачей условной оптимизации. Из-за достаточно сложных ограничений на переменные (ограничения на сумму и на дискретность изменений) для решения этой задачи была использована модификация алгоритма покоординатного спуска.

Для начала рассмотрим применение предлагаемого алгоритма на примере.

Пусть нам необходимо найти оптимальное разбиение для = 8, = 3.

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

Итак, для нашего примера первым разбиением, которое необходимо проверить, будет 0 = 1, 1 = 2, 2 = 2, 3 = 2 (соответствует первой итерации на рисунке 2.3).

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

Это означает, что мы закончили перебор размеров 0 и теперь должны выбрать лучший вариант из итераций 1 – 2. Пусть для определенности это будет результат первой итерации. Найденное на предварительном этапе лучшее равняется единице.

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

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

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

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

Опишем основной этап алгоритма более формально:

1. Принять 0.

2. Принять 1.

3. Вычислить — количество данных, оставшееся для распределения по 4. Если <, то перейти к шагу 9.

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

6. Найти минимаксный риск для данного разбиения.

7. Если найденный риск меньше, чем наименьший найденный — запомнить текущий минимаксный риск как минимальный, а разбиение 0,..., как лучшее.

8. Принять + 1 и перейти к шагу 3.

9. Восстановить все значения, где = 0,..., из сохраненного лучшего разбиения.

10. Если < 1, то принять + 1 и перейти к шагу 2.

11. Значения в, где = 0,..., определяют результат основного этапа поиска оптимального разбиения.

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

Алгоритм проверок неформально можно описать следующим образом:

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

Формально алгоритм дополнительных проверок можно описать так:

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

Рис. 2.4. Пример списка разбиений для дополнительной проверки 3. Задать итератор, обозначающий номер разбиения в списке, принять 4. Найти минимаксный риск для разбиения из списка с номером.

5. Если текущий найденный риск меньше, чем наименьший из найденных до этого — запомнить текущий минимаксный риск как минимальный, а 6. Если меньше, чем количество разбиений в списке, принять + 7. Если = то перейти к шагу 1. Таким образом, данных цикл будет повторяться до тех пор пока в очередной раз все раз­ биения из списка для дополнительной проверки не будут хуже текущего.

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

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

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

Таким образом, переходя только в состояние, которое лучше текущего (т.

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

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

Теперь опишем алгоритм получения списка разбиений для дополнитель­ ной проверки формально. Данный алгоритм получает на вход текущее разбие­ 1. Подготовить пустой список для будущих разбиений. Получить на вход 2. Принять 0 ( определяет группу для уменьшения).

3. Если >, перейти к шагу 13 (выйти из цикла в случае, если все разбиения уже получены).

4. Принять 0 ( определяет группу для увеличения).

5. Если >, то принять + 1 и перейти к шагу 3 (Если из текущей -й группы единица уже перенесена во все возможные -е группы, переходим к следующей группе для уменьшения).

6. Если = 1 или =, то принять + 1 и перейти к шагу (Если нет возможности уменьшить текущую -ю группу или если группа для уменьшения совпадает с группой для увеличения — переходим к следующей группе для увеличения).

(Отдельная проверка для случая, если группа для увеличения — первая.

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

8. Скопировать текущее 0,..., разбиение в новое 0,..., (мы готовы сформировать новое разбиение, подготовим заготовку для него).

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

10. Принять +1, если = 0 и +2, если = 0 (увеличиваем -ю группу. В случае, если мы уменьшаем 0, группа для увеличения должна быть увеличена на 2).

11. Добавить новое разбиение 0,..., к списку разбиений для дополни­ тельной проверки.

12. Принять + 1 и перейти к шагу 5.

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

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

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