Хайкин С. - Нейронные сети (778923), страница 156
Текст из файла (страница 156)
В этом контексте существуют два практических вопроса, которые нужно учитывать при выборе алгоритмов итерации по стратегиям и итерации по значениям для решения задачи динамического программирования. ° Проклятие размерности (спгзе ог П)шепз1опайГу). Во многих сложных реальных задачах количество возможных состояний и действий является настолько большим, что требования к вычислительным мощностям реализации алгоритма динамического программирования становятся просто нереальными. Для задачи динамического программирования, содержащей Ж возможных состояний и М возможных действий для каждого состояния, каждая итерация алгоритма требует АГзМ операций для стационарной стратегии. Это часто делает невозможным выполнение даже одной итерации алгоритма, если Аг достаточно велико.
Например, при игре в нарды (Ьас1сйапппоп) имеется 10зе возможных состояний. Это значит, что одна итерация алгоритма на среднем компьютере, осуществляющем 1 миллион операций в секунду, может занять около 1000 лет 199). ° Неполнота информации (!псошр!еге !и!оппаг1оп). Алгоритмы итераций по стратегиям и по значениям требуют наличия априорных знаний о соответствующем Марковском процессе принятия решений. Это значит, что для вычисления оптимальной стратегии требуется знать вероятности перехода между состояниями р„.
и наблюдаемые стоимости д(г, а, 2). К сожалению, априорные знания не всегда доступны. В свете любой из этих сложностей иногда приходится отказаться от поиска оптимальной стратегии и искать субоптимальную. В контексте данной книги интерес представляет субоптимальная процедура, которая включает в себя использование нейронных сетей и (или) моделирование с целью аппроксимации функции стоимости перехода г'*(г) для всех г ЕХ. В частности, для конкретного состояния 1 функция,У'(г) заменяется подходящей аппроксимацией ,7(г, зч), где зп — вектор параметров.
Функция 1(, зч) называется функцией отсчета (зсоге йгпсйоп) или приближенной функцией стоимости перехода (арргох1шаге созь Го-яо йзпсгюп). Сами значения,У(з, зч) называются отсчетами или приближенными затратами для состояния г. Таким образом, отсчет .1(г, зч) является откликом нейронной сети в ответ на подачу на вход состояния г. Здесь нейронные сети функционируют в качестве универсальных аппроксиматоров. Это одно из встроенных свойств многослойных персептронов и сетей на основе радиальных базисных функций. Нас интересуют те задачи динамического программирования, которые имеют большое количество состояний н в которых требуется найти такую функцию от- 12.6.
Нейродннамнческое программирование 779 Состоя ! Рис. 12.6. Нейронная сеть, предназначенная для аппроксимации оптимальной функции стоимости перехода л* счета .7(, тт), для которой вектор параметров е' имеет небольшую размерность. В этой форме аппроксимации, называемой компактным представлением (сошрас1 гергезептайоп), сохраюпотся только вектор параметров ту и общая структура функции отсчета 7(ч ту). Отчеты 7(т', и) для всех состояний г еХ генерируются только по мере необходимости. Требуется алгоритмически найти вектор параметров тк, такой, чтобы для данной структуры нейронной сети (иапример, для многослойного персептроиа) отсчет 3(т', тк) предоставлял удовлетворительную аппроксимацию оптимального зиачеиия 1*(г) для всех т Е Х.
Из материала по обучению с учителем, представленного в главах 4 — 7, известно, что для обучения нейронной сети, иезависимо от ее типа, требуется наличие миожества маркированных данных, являющегося представительным для своей задачи. Однако в контексте задач динамического программирования множества данных (т.е. пар примеров "вход-выход" ((г,,У*(г))), необходимых для оптимизации структуры сети в некотором статистическом смысле, ие существует (рис. 12.6).
Остается лишь возможность использования метода моделирования Монте-Карло (Моите Саг!о з(шц!айоп), в которой вместо фактической системы, характеризуемой Марковским процессом принятия решений, используется некоторая суррогатная модель. В результате формируется автономный режим работы процесса динамического программирования, который обладает следующими потенциальными преимуществами [126].
1. Использование моделирования для приближенной оценки оптимальной функции стоимости перехода является ключевой идеей, которая отличает методологию иейродииамического программирования от традиционных методов аппроксимации в динамическом программировании. 2. Моделирование позволяет использовать методы иейродииамического программироваиия для создания систем, точных моделей которых ие существует. Для таких систем традиционные приемы динамического программирования неприменимы (иапример, если невозможно оценить вероятности состояний и переходов). 3.
Посредством моделирования можно идентифицировать наиболее важные или иаиболее представительиые состояния системы, иапример те, которые при моделироваиии посещаются чаще других. Следовательно, функция отсчета, созданная нейронной сетью, будет являться хорошей аппроксимацией оптимальной функции стлоимостни нерехода для этих конкретных состояний. В итоге можно будет выработать хорошую субоптимальиую стратегию для сложиых задач динамического программирования. 780 Глава 12. Нейродинамическое программирование Однако важно помнить что при использовании аппроксимации нельзя ожидать сходимости функции отсчета,7(, и) к оптимальной функции стоимости перехода.
Причина этого заключается в том, что,7' ( ) может не принадлежать множеству функций, которые могут быть точно представлены выбранной структурой нейронной сети. В следующих двух разделах мы рассмотрим две процедуры приближенного динамического программирования, использующие аппроксимации функций стоимости перехода. Первая процедура, описанная в разделе 12.7, связана с приближением алгоритма итерации по стратегиям, предполагающего доступность Марковской модели системы. Вторая процедура, рассматриваемая в разделе 12.8, связана с так называемым О-обучением. Она требует достаточно мягких предположений.
12.7. Приближенный алгоритм итерации по стратегиям Предположим, что существует некоторая задача динамического программирования с довольно большим множеством допустимых состояний и действий, что делает непрактичным применение традиционных подходов. Пусть имеется модель системы, т.е. известны вероятности переходов р; (а) и наблюдаемые затраты о(г,а,з).
Для реализации алгоритма итерации по стратегиям предлагается использовать аппроксимацию, основанную на моделировании Монте-Карло и методе наименьших квадратов, что и будет описано далее (125). На рис. 12.7 показана упрощенная блочная диаграмма приближенного алгоритма итерации яо стратегиям (арргохппаге ро!(су йегайоп а18опбпп). Она аналогична диаграмме обычного алгоритма итерации по стратегиям, представленной на рис.
12.3, но имеет одно важное отличие: шаг вычисления точной оценки стратегии заменен вычислением приближенной оценкой. Таким образом, приближенный алгоритм итерации по стратегиям чередует два шага: шаг оценки приближенной стратегии и шаг улучшения стратегии 1. Шаг вычисления приближенной стратегии (арргохппа1е ро!(су еча!па1юп з1ер). Для данной стратегии )г вычисляется приближенная функция стоимости перехода У'(г, чк) для всех состояний г. Вектор и является вектором параметров нейронной сети, используемой для аппроксимации функции.
2. Шаг улучшения стратегии (ро11су ппргочешеп1 з1ер). С использованием приближенной функции стоимости перехода У'(г, чг) генерируется улучшенная стратегия )г. Эта новая стратегия должна быть жадной по отношению к У'(г, и) для всех г. 12.7. Приближенный алгоритм итерации по стратегиям 781 Приближенная егопмоета перехода Зхсб и) атегня р Рнс. 12.7. Упрощенная блочная диаграмма приближенного алгоритма итерации по стратегиям Для того чтобы приближенный алгоритм итерации по стратегиям давал удовлетворительные результаты, важно тщательно выбирать стратегию, используемую для инициализации алгоритма.
При этом необходимо использовать эвристики. В качестве альтернативы можно начинать с произвольного вектора и и использовать его для вывода жадной стратегии. Полученная стратегия затем будет применяться в качестве исходной. Теперь предположим, что в дополнение к знанию вероятностей переходов и значений стоимости в нашем распоряжении имеется следующая информация. ° Стационарная стратегия 1т,принимаемая в качестве исходной.
° Множество состояний Х, представительных для данной внешней среды. ° Множество примеров М(е) функций снгоимослги перехода У'(а) для всех состояний е Е Х. Каждый такой пример обозначим как к(г, га), где гл = 1, 2,..., М(а). Пусть У'(е,и) — приближенное представление функции стоимости перехода У'(а). Эта аппроксимация выполняется нейронной сетью (иапример, многослойным персептроиом, обучаемым с помощью алгоритма обратного распространения).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
