Программа предсказания динамики частично наблюдаемого процесса
Методы на основе рекуррентных нейронных сетей. Управление в условиях частичной наблюдаемости. Существующие программные решения, обоснование выбора метода. Частично наблюдаемый Марковский процесс принятия решений. Использование награды как наблюдения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 10.12.2019 |
| Размер файла | 2,4 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
ПРАВИТЕЛЬСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ
«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»
Факультет компьютерных наук
Департамент программной инженерии
Выпускная квалификационная работа
на тему «Программа предсказания динамики частично наблюдаемого процесса»
по направлению подготовки 09.03.04 «Программная инженерия»
Москва 2019
РЕФЕРАТ
Задача предсказания динамики частично наблюдаемых процессов - важнейшая задача искусственного интеллекта, так как в общем случае позволит решать огромное количество прикладных задач. В работе разбирается принцип работы современных алгоритмов предсказания динамики таких процессов, предложена модификация одного из алгоритмов. В рамках данного дипломного проекта было реализовано приложение с графическим интерфейсом, с помощью которого пользователь может настроить алгоритм для извлечения информации о скрытом состоянии процесса из наблюдаемых данных, а также взаимодействовать с этим процессом таким образом, чтобы максимизировать суммарную награду, приходящую из процесса. Также программа позволяет пользователю сгенерировать отчёт-видео и отчёт-документ. В работе также описаны используемые программные инструменты.
Ключевые слова: частично наблюдаемые процессы, обучение с подкреплением, машинное обучение, фильтр частиц
ABSTRACT
Thetaskofprediction of dynamics of partially observable processes is a very important task of artificial intelligence, because it allows us to solve a huge number of practical problems. In the diploma the modern methods of dynamics prediction are investigated, a modification for one of the methods is proposed. Duringthediplomaagraphicalapplicationwasimplemented, which can be used by users to extract information about the hidden dynamics of the process from the observed data, and also to interact with the process to maximize total reward received from the process. Theprogramalsogivesuser an opportunity to generate video-report and pdf-report about the progress of training process. Thesoftwaretechnologiesthatwere used during the developing process are also described in the paper.
Keywords: state space models, reinforcement learning, machine learning, particle filter, auto-encoding sequential monte-carlo.
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ОБЗОР ИСТОЧНИКОВ И СУЩЕСТВУЮЩИХ ТЕХНОЛОГИЙ
1.1 Существующие методы
1.1.1 Методы на основе рекуррентных нейронных сетей
1.1.2 Вероятностные методы
1.1.3 Методы обучения с подкреплением
1.1.4 Управление в условиях частичной наблюдаемости
1.2 Существующие программные решения
1.3 Обоснование выбора метода
1.4 Задачи реализации программы
ГЛАВА 2. ИСПОЛЬЗУЕМЫЕ МЕТОДЫ
2.1 Частичнонаблюдаемыйпроцесс
2.2 Частично наблюдаемый марковский процесс принятий решений
2.3 Монте-Карло на последовательностях
2.4 Автокодирующий Монте-Карло на последовательностях
2.5 Обучение с подкреплением
2.6 Использоваине награды как наблюдения
2.7 Извлечение информации из картинки
ГЛАВА 3. ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМА
3.1 Используемые программные инструменты
3.2 Функциональность программы
3.2.1 Основной экран приложения
3.2.2 Редактирование файла конфигурации
3.2.3 Параметры алгоритма
3.2.4 Отчёт о работе алгоритма
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
ПРИЛОЖЕНИЕ
ОПРЕДЕЛЕНИЯ И СОКРАЩЕНИЯ
Частично наблюдаемый процесс - последовательность изменяющихся ненаблюдаемых состояний, каждый шаг генерирующая наблюдаемую переменную с помощью заданной функции.
Обучение с подкреплением - постановка задачи, в которой агент взаимодействует с окружающей средой, максимизируя получаем от среды награду
Свёрточная нейронная сеть - параметрическая функция, которая является композицией линейных преобразований, свёрток и нелинейных функций активации
Марковский процесс принятия решений - это цепочка последовательно меняющихся состояний, в которой изменение обусловлено на действие агента, которое поступает в процесс извне.
Агент - отображение из пространства состояний процесса в пространство вероятностных распределений на возможные действия.
“Importancesampling” - техниа, позволяющаясэмплировать из произвольного вероятностного распределения, заданного функцией плотности. Применяется для оценки какой-то величины по искомому распределению, так как производит взвешенные сэмплы.
Q-сеть - отображение из текущего состояния процесса в Q-функцию для всех возможных действий
Q-функция - величина, показывающая, какова ожидаемая взвешенная сумма будущих наград, при условии, что мы находимся в данном состоянии и совершаем данное действие.
ВВЕДЕНИЕ
Задача искусственного интеллекта сегодня обретает свою актуальность в сообществе инженеров и исследователей. У этого есть разные причины, но основных можно выделить две.
Во-первых, сегодня человечество собирает гигантские объёмы данных. Перемещения людей, их действия в интернете, покупки и многое другое. Такой объём информации таит в себе потенциальную возможность для заработка, так как можно эффективно рекламировать людям различные товары, предсказывать их поведение и так далее. Такой объём информации люди не в состоянии проанализировать вручную, поэтому необходимо разрабатывать автоматические методы для поиска закономерности в данных.
Во-вторых, многие люди сегодня занимаются простым трудом, требующим многократного повторения однообразных действий. Среди них кассиры, водители и другие. Если мы сможем автоматизировать их работу и позволим делать её машинам, то освободится большое количество рабочих рук, которые смогут применить себя в более интеллектуально-ёмких областях.
Однако, при решении реальной задачи анализа данных или оптимального управления алгоритм почти всегда сталкивается с феноменом частичной наблюдаемости. В рекомендательных системах мы не можем узнать истинные вкусы клиента, и поэтому мы пытаемся их вычислить по уже купленным товарам и поставленным о ценам. Управляя роботом, алгоритм не может знать всю необходимую ему информацию об окружающем мире, поэтому он вынужден предсказывать их на основе наблюдений.
Для формального описания задачи частичной наблюдаемости было придумано понятие StateStaceModel (далее частично наблюдаемый процесс). Такой процесс содержит истинную скрытую от наблюдателя динамику процесса, а также вероятностное отображение из скрытого состояния в то, что в данный момент может наблюдать робот или алгоритм.
Схематичную иллюстрацию частично наблюдаемого процесса можно увидеть на рис. 1. Буквами Z обозначены скрытые переменные, отражающие истинную динамику процесса. Алгоритм способен наблюдать только переменные, обозначенные буквами X. Стрелками показаны причинно-следственные связи в данном процессе. В частности, можно заметить, что текущее наблюдение зависит только от текущего состояния.
В задачах анализа данных мы наблюдаем набор характеристик объекта, будь то совершённые человеком покупки, фотографию его лица или что угодно, зависящее от контекста.
Рисунок 1 - Частично наблюдаемый процесс (State Space Model)
В стандартных задачах обучения с учителем для каждого объекта есть ненаблюдаемая характеристика, будь то его желание купить какой-то товар, возраст.
Алгоритм в такой задаче пытается узнать значение скрытой характеристики. Обладая набором данных, мы пытаемся восстановить зависимость между наблюдаемыми переменными и скрытой характеристикой, используя алгоритмы машинного обучения, такие как линейная регрессия или нейронные сети.
В задачах обучения с подкреплением алгоритм сталкивается с частичной наблюдаемостью другого рода. Взаимодействуя со средой шаг за шагом, алгоритм каждый раз получает разные наблюдения, которые генерируются одним и тем же частично наблюдаемым процессом - окружающим миром. В то же время алгоритм не обладает информацией о том, что и в какой ситуации ему нужно делать, и он должен самостоятельно искать решение, максимизурующее награду, методом проб и ошибок.
Текущее наблюдение содержит мало информации об окружающем мире. Если бы мы сфотографировали происходящее в оживлённом городе, по фотографии нельзя было бы понять даже такие простые вещи, как скорость перемещающихся машин и людей. По этой же причине робот не может принять оптимальное решение о своём следующем действии, опираясь только на текущие показатели сенсоров.
Однако, благодаря наличию последовательности предыдущих наблюдений, робот получает возможность извлекать информацию о ненаблюдаемых переменных, аккумулируя всю информацию о предыдущих наблюдениях. Видео длиной в несколько секунд содержит куда
больше информации о мире, чем только его последний кадр. Возникает простое желание дать алгоритму возможность делать предсказание на основе всех предыдущих наблюдений, но в этом случае всплывает проблема высокоразмерности пространства.
В данной работе рассматривается следующий вопрос - как нужно аккумулировать информацию о всех предыдущих наблюдениях таким образом, чтобы иметь возможность осуществлять оптимальное управление?
Целью работы является создание программного обеспечения для широкого круга IT-специалистов, позволяющего пользователям решать задачу предсказания скрытой динамики импортируемого в программу частично наблюдаемого процесса.
Для достижения этой цели необходимо решить следующие задачи:
Изучение работ о существующих алгоритмах извлечения информации о динамике частично наблюдаемого процесса.
Анализ ПО, реализующего такие алгоритмы.
Выбор задач для отладки, сравнения и тестирования алгоритмов извлечения динамики.
Выбор набора алгоритмов и их реализация.
Создание графического интерфейса программы.
Написание пакета технической документации.
В главе 1 содержится обзор существующих алгоритмов для извлечения скрытой динамики процесса, а также существующее ПО, реализующее данные алгоритмы. Во второй главе описан метод, реализованный в программе. Во третьей главе описываются технологии и программные инструменты, используемые для реализации программы. Кроме этого в ней описывается набор частично наблюдаемых процессов, использованных во время создания ПО для отладки алгоритмов. В четвёртой главе описываются полученные в ходе тестирования результаты. В заключении подводится итог - преимущества и недостатки разработанной программы, потенциал для будущего развития.
ГЛАВА 1. ОБЗОР ИСТОЧНИКОВ И СУЩЕСТВУЮЩИХ ТЕХНОЛОГИЙ
1.1 Существующие методы
1.1.1 Методы на основе рекуррентных нейронных сетей
До недавнего времени в задачах с многоразмерными наблюдаемыми и скрытыми переменными пытались решить с помощью рекуррентной нейронной сети. Перед сетью ставилась задача предсказания будущих наблюдений для данной последовательности предыдущих наблюдений. Она считывает последовательно предыдущие наблюдения по одному, обновляет значение своей внутренней памяти, а в конце оно подаётся на вход другой сети, предсказывающей следующий набор наблюдаемых переменных. Сеть обучается, минимизируя расстояние между фактическими будущими наблюдениями и предсказанными. Далее, на основе предположения о том, что информация в ячейке памяти рекуррентной сети содержит всю важную информацию, значение из ячейки используется как истинное скрытое состояние процесса.
Данная методика применялась для нахождения оптимальных действий в частично наблюдаемом Марковском процессе принятия решения. Например, полученное таким образом скрытое состояния подавалось на вход Q-сети, предсказывающую полезность каждого действия, совершенного в данном состоянии[1]. Альтернативный способ заключается в подаче такого скрытого состояния напрямую сети-политике, которая по данному состоянию генерирует вероятностное распределение на действия [2].
1.1.2 Вероятностные методы
Параллельно с этим подходом велась работа над вероятностными методами предсказания скрытой динамики. Впервые метод для обучения вероятностных моделей для сжатия данных на высоко-размерных объектах был представлен в работе 2014 года[3]. Он получил название вариационного автокодировщика. В методе были совмещены нелинейные методы отображения (подобные используемым в нейронных сетях) и байесовский вывод. Для стабилизации процедуры обучения был применён репараметризационный трюк, использовавшийся для генерации из высокоразмерных нормальных распределений.
Начиная с того момента, исследователи расширяли возможности использования вариационного автокодировщика, например, его обучали на временных рядах [4] и размеченных объектах [5]. Вносились также и модификации, касающиеся математически более точной процедуры обучения [6].
Несколькими годами ранее была изобретена техника под названием «Последовательный Монте-Карло», применённая для генерации последовательностей объектов из заданного вероятностного распределения[7]. Наивные методы генерации требуют слишком большого количества сэмплирований для того, чтобы получить выборку высоковероятных последовательностей. Достаточно одного маловероятного перехода, возникшего при сэмплировании, чтобы вся последовательность стала маловероятной. Авторы используют технику ресэмплирования для того, чтобы на каждом временном шаге оставлять только цепочки с наибольшим правдоподобием.
Позже авторы статьи [8] соединили идеи статей [4], [6], [7] и предложил новый метод, способный восстанавливать динамику частично наблюдаемого процесса. Данный метод применяется в ситуации, когда мы ничего не знаем о структуре скрытого состояния. В частности, мы не знаем функции перехода между скрытыми состояниями, которая используется в [7] для генерации цепочек состояний. Вместо этого функция перехода и функция наблюдения заменяются на обучаемые параметрические распределения.
В методе применяется фильтр частиц - техника сэмплирования переменной скрытого состояния среды. Полученные частицы подаются в обучаемые функции перехода и наблюдения для расчёта правдоподобия наблюдаемых переменных. В процессе оптимизации генератор частиц, функция наблюдения, функция перехода и другие параметрические функции меняются таким образом, чтобы правдоподобие было максимально.
Выше изложенный метод будет более строго введён в главе 2, так как являются частью финального алгоритма.
1.1.3 Методы обучения с подкреплением
Для выбора оптимального действия при данном состоянии среды используются методы обучения с подкреплением. Существует 2 больших группы методов - так называемые value-based и policy-based методы.
Value-based методы работают на основе обучения Q-функции - величины, показывающей, насколько много награды агент получит в будущем при условии совершения данного действия в данном состоянии. При небольшом количестве возможных действий нейронная сеть, считающая Q-функцию, за одно использование может рассчитать её для всех возможных действий. После этого будет выбрано то действие, которое принесёт наибольшую награду. В случае непрерывного пространства действий данный метод напрямую использовать нельзя, так выбрать оптимальное действие невозможно для произвольного вида Q-функции. Наиболее продвинутые работы в этой области совмещают свёрточные нейронные сети, а также память и другие техники улучшения стабильности обучения [9]
Policy-based методы ищут отображение из состояния среды в вероятностное распределение на действия. Такой метод можно применять при любом типе пространства действий. Для этого вводят функцию полезности агента, подсчитываемую как взвешенную сумму получаемых наград. Для этой функции можно посчитать градиент по параметрам агента, который используется для обновления этих параметров методом градиентного спуска. Последние предложенные методы опираются на умные обновления весов, которые резко не меняют политику агента между шагами [10]. Такой метод является частью финального алгоритма, и более строгое описание будет присутствовать в главе 2.
Рис. 2 - Постановка задачи обучения с подкреплением
1.1.4 Управление в условиях частичной наблюдаемости
В статье [11] авторы соединили идеи из статей [2] и [8], реализовав алгоритм, который с помощью методов Монте-Карло восстанавливает скрытое состояние, способное предсказывать будущее и прошлые наблюдения, а затем использует это скрытое состояния для расчёта оптимального действия агента. Алгоритм в статье применяют для 2 различных типов частичной наблюдаемости:
Мигающие кадры. В симуляторах игр Atari агент видит картинку из игры. В данной постановке каждый кадр с вероятностью 0.5 оказывается полностью чёрным.
Гауссовский шум. Эта среда представляет собой задачу перемещения в 2-мерном пространстве. Каждая точка в этом пространстве обладает своей высотой, за которую агента награждает, и агент должен максимизировать эту высоту. Частичная наблюдамость возникает за счёт того, что агент не наблюдает своё истинное положение на карте, а видит только зашумлённые нормальным шумом координаты.
1.2 Существующие программные решения
Авторы используемого мной метода, описанного в статье [11], выложили в открытый доступ свою реализацию алгоритма. Она не обладает графическим интерфейсом, а также не позволяет человеку, не являющимся узким специалистом в области частично наблюдаемых процессов, использовать достоинства данного метода. Других реализаций мной не было обнаружено.
1.3 Обоснование выбора метода
Используемый метод на сегодня обладает наилучшей производительностью среди предложенных методов для оптимального управления в частично наблюдаемых процессах.
Он показал наибольшее количество очков среди аналогов в наборе мигающих сред Atari, используемом всеми для валидации подобных алгоритмов.
Задачи реализации программы
Для реализации программы необходимо решить следующие задачи:
Анализ кода метода, предложенного авторами статьи [11]. Выявление ограничений, не позволяющих реализовать качественный интерфейс и расширять метод.
Создание новой реализации алгоритма
Внесение изменений в изначальный предложенный метод с целью повышения производительности
Тестирования измененного метода на наборе сред, предложенном авторами [11].
Создание графического интерфейса
ГЛАВА 2. ИСПОЛЬЗУЕМЫЕ МЕТОДЫ
Для описания используемого метода сначала требуется ввести дополнительные определения.
2.1 Частично наблюдаемый процесс
Положим частично наблюдаемый процесс как кортеж (Z, X, m, f, g), где Z это пространство внутренних состояиий, Х это пространство наблюдений, m это распределение над z0(скрытое состояние в начальный момент времени), f это функция перехода, zt+1 ~ f(zt+1 | zt), и g это функция наблюдения, xt ~ g(xt | zt). Этот теоретический концепт очень общий, и мы можем описать все процессы в мире, используя его. Мы предполагаем, что каждый процесс обладает своей внутренней динамикой, на основании которой меняется состояние процесса. В то же время, мы, как наблюдатели, не обладаем доступом к этому состоянию. Мы не можем видеть ни текущее значение z в любой момент, ни то, как это значение меняется со временем. Примером частично наблюдаемого процесса может служить человеческое поведение. Представим, что человек сел за компьютер и хочет заказать пиццу с помощью бота. Для компьютера человек - это частично наблюдаемый процесс, поскольку истинные мотивы и желания человека зашифрованы в мозгу несчитываемым образом. Однако, бот видит, что человек пишет, и слова человека являются в данном случае наблюдаемыми переменными. Бот может анализировать наблюдаемые переменные и на их основе решать какие-то задачи.
В постановке частично наблюдаемого процесса имеет смысл решать 2 задачи:
Несмотря на то, что в общем случае мы не видим внутреннюю динамику процесса, иногда мы можем знать функции m, f, g. В этом случае, мы пробуем найти распределения на возможные значения переменной z в какие-то моменты времени, используя наблюдения: q(zt| x1:t). Мы называем это задачей фильтрации.
Обычно мы не знаем функции m, f, g. Всё, что мы можем сделать в такой ситуации, это предсказывать будущие наблюдения: q(xt+1 | x1:t). Это задача намного более сложная и требует продвинутых методов стохастической оптимизации и обучения представлений.
2.2 Частично наблюдаемый Марковский процесс принятий решений
Положим частично наблюдаемый Марковский процесс принятий решений как кортеж (S, A, P, R, O, G, p0), где S это пространство состояний, А это пространство действий, Р это функция перехода состояний: st+1 ~ P(st+1 | st, at), R это функция наград: rt~ R(st, at, st+1), О это пространство наблюдений, G это функция наблюдения ot ~ O(ot | st), a первое состояние генерируется из распределения p0 (s0).
Реальное состояние процесса изменяется согласно распределениям p0 (s0) иP(st+1 | st,at). Агент взаимодействует со средой с помощью действий at. Этидействиягенерирютсяполитикойагентар: at ~ р(at, | a1:t-1, o1:t, r1:t-1) . Награда rt используется как индикатор успешной производительности агента в среде. Обычно агенты на каждом шаге пытаются максимизировать ожидаемую сумму будущих наград:
(1)
Чтобы это сделать, агент должен каким-то образом извлечь информацию о скрытой динамике процесса, используя предыдущие наблюдения o1:t и награды r1:t-1.
Влияние друг на друга различных переменных изображено на рисунке 3:
Рис. 3 - Влияние друг на друга элементов частично наблюдаемого Марковского процесса принятия решений
Затемнённые переменные O и R агент наблюдает и может их учитывать. Награда формально зависит от текущего состояния и совершенного действия, хотя на практике она не всегда зависит от совершенного в данный момент действия. Это обусловлено тем, что действия прежде всего влияют на изменения состояния. А уже каждое состояние обладает своей наградой, которую агент с запазданием и получает.
Выше упомянутый пример с роботом отлично подходит под данную постановку задачи. Действиями робота мы можем считать то, что он говорит человеку. Человек, учитывая слова робота, меняется своё внутреннее состояние. В свою очередь, от этого меняются его будущие слова. Наградой в данном случае может являться индикатор того, что человек сделал правильный заказ. Тогда робот, стремясь получить положительную награду, будет максимизировать вероятность того, что человек сделает правильный заказ.
Подобные системы уже существуют в зачаточном состоянии, к примеру, искусственный интеллект компании IBMWaston (рис. 4).
Другим примером частично наблюдаемого Марковского процесса принятия решения может служить набор игр Atari (рис. 5). Сегодня он широко используется в исследованиях для разработки алгоритмов, автоматически обучающихся взаимодействовать с частично наблюдаемыми процессами. Среди этих игр встречаются игры с разной природой частичной наблюдаемости, это обеспечивает честный тест для различных алгоритмов.
Рис. 4 - IBM Watson
Рис. 5 - Atari games
Монте-Карло на последовательностях
Предположим, что у нас есть последовательность наблюдений x1:T, сгенерированная частично наблюдаемым процессом (Z, X, m, f, g), и мы знаем функции m, f, g. Предположим, что Х и Z это многоразмерные пространства действительных чисел. Чтобы решить задачу фильтрации, нам нужно посчитать многоразмерный интеграл [7].Мы не можем взять его аналитически во всех случаях, кроме простейших, например в случае, когда функция перехода и наблюдения является отображением в нормальное распределение. Чтобы решить задачу в общем случае, нам нужно использовать метод Монте-Карло на последовательностях. Предположим, мы хотим просэмплировать скрытые состояния z1:t для данной последовательности наблюдений x1:t.. Мы можем посчитать функцию плотности совместного распределения p (z1:t, x1:t) в выбранной точке, используя следующее разложение:
(2)
Однако, несмотря на то, что мы знаем функцию плотности, мы не можем из неё сэмплировать, так как сэмплирование требует обратной функции распределения p (z1:t, x1:t).
При этом нам полезна сама функция плотности p (z1:t, x1:t), так как она равна p (z1:t | x1:t), умноженной на нормализующую константу p(x1:t) по формуле Байеса. Сейчас мы применим технику «importancesampling», чтобы получить взвешенные сэмплы из искомого распределения p (z1:t| x1:t). Пусть у нас есть предложное распределение q (z1:t | x1:t):
(3)
Это может быть любое распределение, из которого мы можем сэмплировать. Если оно похоже на р (z1:t | x1:t), то мы получим хорошую выборку. Чтобы посэмплировать, мы будем пользоваться данной процедурой:
Для каждого шага от 1 до Т:
Генерируем К частиц из (если это 1 момент времени, то сэмплируем из
Считаем вес данной частицы по формуле:
(4)
(5)
нейронный сеть решение наблюдение
Ресэмплируем частицы согласно данному распределению:
В конце мы получаем К взвешеннных сэмплов из распределения p (z1:t | x1:t), взвешенных весами W1:K. Взвешенные выборки используются тогда, когда нужно считать какое-то математическое ожидание по распределению p (z1:t | x1:t). Обладая взвешенным набором частиц, мы можем получить несмещённую оценку мат. ожидания.
Схематично данный алгоритм изображён на рис. 6.
Рис. 6 - Визуализация фильтра частиц
Сверху мы можем видеть, как из равномерного распределения генерируется много маленьких точек. Потом для каждой точки мы проверяем, чему равно значение плотности вероятности (она изображена в виде кривой). Те точки, которые обладают большим значением, становятся большими, а те точки, в которых плотность мала, становятся маленькими. После этого мы ресэмпилруем из этого распределения, учитывая полученные веса каждой точки. В результате мы видим под кривой выборку из белых точек. Можно считать этот набор из белых точек выборкой из того распределения, плотность которого изображена кривой. Смысл данного метода в том, что мы предполагаем, что не можем сэмплировать из распределения, из которого хотим. Так происходит почти во всех случаях, кроме простейших (например, нормальных распределений), поскольку для генерации выборки по распределению с заданной функций плотности нужно уметь инвертировать функцию распределения. В произвольном случае даже функцию распределения бывает посчитать невозможно, а тем более её обратить.
2.4 Автокодирующий Монте-Карло на последовательностях
В большинстве реальных ситуаций мы не знаем функции m,f,g, так что мы не можем решать задачу фильтрации. В этом случае, мы хотели бы построить модель, которая даёт максимальное правдоподобие наблюдаемой последовательности p(x1:T). Правдоподобием в данной ситуации мы считаем вероятность того, что наш модель сгенерирует данную выборку. Если правдоподобие нашей выборки будет низким для обученной модели, это обозначает, что у нас плохая модель, так как в реальности, если бы эта модель была правдивой, такая выборка не сгенерировалась бы.
Мы можем получить нижнюю оценку логарифма этого правдоподобия [4]:
(6)
Нижняя оценка - это выражение, которое всегда ниже, чем величина, которую она оценивает. Такая оценка является вариационной, поскольку в ней есть параметры функций qи, pииpц. Меняя параметры этих функций, мы будем получать разное значение оценки. Свойства этой оценки таковы, что существует такой набор параметров, при котором нижняя оценка совпадает по значению с оцениваемым логарифмом.
Здесь мы полагаем, что qи, pииpц- это обучаемые параметрические функции. Мы изменяем их в сторону увеличения данной нижней оценки, обучая их методом градиентного спуска.
Оптимизируя данную нижнюю оценку, мы приближаем обучаемые функции к своим реальным прототипам. pи- это функция перехода между скрытыми состояниями при условии не наблюдения последних видимых данных (xt). qи- это функция перехода между скрытыми состояниями при условии наблюдения последних видимых данных. pциспользуется в качестве функции наблюдения. Данное выражение напоминает формулу Байеса, обобщением которой на самом деле и является. pисимволизирует априорное распределение (то есть распределение на последнюю zбез знания о последней x), qи - апостериорное, и pц это условное правдоподобие.
Это обобщение идеи вариационного автокодировщика [2], но для работы с данными, зависимыми от времени, и с множественным сэмплирвоанием переменной z. Если представить, что T=1 и K=1, то мы получим в точности формулу нижней оценки для вариационного автокодировщика.
Чтобы получить нижнюю оценку, мы генерируем сэмплы z1:t, используя алгоритм, описанный в процедуре 2.3. Детальное описание всей процедуры и теоретические выкладки даны в [1].
Когда мы обучили модели qи, pи, pц, мы можем использовать их для аппроксимации распределения на zt, которые они сами себе выучили. Затем мы можем использовать эту информацию, чтобы считать какую-то функцию, зависящую от динамики процесса.
Чтобы это сделать, нам необходимо сначала сгенерировать выборку из перенных z, обусловленных на наблюдаемые данные. Затем делаем предположение, что распределение z- это всего лишь взвешенная смесь дельта-функций. Веса у этой смеси соответствует весам полученных частиц, а значения - значениям. Если мы можем для каждой частиц посчитать значение какой-то нужной нам функции, мы можем сложить результаты с весами и получит несмещённую оценку на искомое нами мат. ожидание.
Обучение с подкреплением
Даже если у нас есть процедура, которая позволяет приблизить распределение на скрытые состояния среды, мы хотим использовать это в задачах принятия решения, которые часто встречаются в реальных приложениях. Чтобы это сделать, мы используем алгоритмы обучения с подкреплением. Итак, пусть у нас есть частично наблюдаемый Марковский процесс принятий решений(S, A, P, R, O, G, p0).
Используя технику AESMC [1] (кратко описанную в 2.4), мы можем предположить, какое у среды состояние st в момент времени t. Оно не совпадает с истинным состоянием, поскольку мы не можем знать даже структуру st.. Однако, наша догадка в идеале должна содержать максимальное количество информации, которая поможет предсказывать будущее поведение процесса. Мы можем применить этот алгоритм к процессу напрямую, полагая наблюдения ot видимыми переменными. Предположим, что мы знаем истинное состояние st. Теперьмыможемприменитьалгоритмобучениясподкреплениемдляполностью наблюдаемых сред, например, PolicyGradient [6]. Предположим, что у нас есть политика ри(at, | st), зависящая только от состояния st (которое предполагается наблюдаемым). Затем мы можем оценить градиент функции полезности, описанной в формуле (1), по параметрам политики:
(7)
Используя этот метод, мы обновляем параметры политики в сторону максимизации функции полезности.
В нашем методе у нас нет знания о состоянии st, поэтому наша политика является смесью политик, которые получают на вход K частиц. Итоговая формула для расчёта политики выглядит следующим образом:
(8)
Более детальное описание алгоритма дано в [7].
Использование награды как наблюдения
Предыдущий метод [7] используем в качестве видимых переменных наблюдения ot, игнорируя награды rt. Награды в этом методе используются только для максимизациии функции полезности. Метод, реализованный в данной работе, отличается от предыдущего в этом плане. Награды являются точно такой же видимой переменной, как и наблюдения, поэтому их необходимо использовать при оценке скрытого состояния процесса. Фактически это означает, что в к в формуле (6) переменной x будет являться пара из переменных (o, r), а не только o. Как будет видно из результатов проведённых экспериментов в главе 3, данная информация может существенно помочь в ряде сред, особенно если ненулевые награды выдаются часто.
Извлечение информации из картинки
Для того, чтобы эффективно извлекать данные из высокоразмерных картинок, инженеры используют свёрточные нейронные сети.
Пример такой сети дан на рис. 7
Рис. 7 - Архитектура сети AlexNet
Этот инструмент широко используется в задачах распознавания или классификации картинок. В данной работе свёрточная нейронная сеть используется для того, чтобы эффективно сжать картинку до малоразмерного вектора, который затем будет подаваться в алгоритм, описанный в 2.4. Более детально, архитектура задана следующим кодом:
enc = nn.Sequential(
nn.Conv2d(n_input_channels_or_dim, cnn_channels[0], 8, stride=4),
nn.ReLU(),
nn.Conv2d(cnn_channels[0], cnn_channels[1], 4, stride=2),
nn.ReLU(),
nn.Conv2d(cnn_channels[1], cnn_channels[2], 3, stride=1),
nn.ReLU(),
)
ГЛАВА 3. ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМА
3.1 Используемые программные инструменты
Для реализации вычислительного графа, дифференцирования и оптимизации параметров использовалась библиотека Pytorch. Языком программирования, который был использован для написания программы, является Python. Среда разработки - Pycharm. Для создания графического интерфейса была использована библиотека Pyqt.
3.2 Функциональность программы
3.2.1 Основной экран приложения
Основной экран приложения показан на рисунке 8.
Рис. 8 - Основной экран приложения
Большую часть экрана слева занимает окно вывода. В него транслируется весь текстовый вывод, который генерируется в ходе обучения. В случае провального запуска модели, текст ошибки так же будет выведен в этом месте.
Вверху справа находится меню выбора режима работы программы. Режимов два - POMDPsolving и Analysis.
POMDPsolving - в этом режиме пользователь непосредственно обучает модель. В этом случае у него так же есть два режима работы.
Обучение модели с нуля - в этом случае пользователю не нужно ставить галочку напротив пункта “Loadmodel”.Чтобы задать параметры новой обучаемой модели, ему нужно выбрать файл конфигурации, нажав кнопку “Chooseconfigfile”. Откроется окно выбора файла операционной системы, и пользователю необходимо будет сделать выбор.
Дообучение модели - в таком случае пользователю надо будет выбрать не файл конфигурации, а папку с уже созданной первым способом моделью. Кнопка“Choose config file” заменится кнопкой“Choose model to load”.
Ниже расположена кнопка Choosesavedirectory-в выбранной директории будет сохраняться папка с обученной моделью.
Ниже в поле для имени модели человек вводит название папки, которая создаётся в выбранной директории для этой модели.
Под этим полем расположено ещё одно окно вывода, в котором выводится отчёт о совершенных пользователем в самой программе действий, таких как выбор конфига, выбор модели для загрузки, запуск обучения и так далее.
После выбора всех параметров и начала обучения программа выдаёт результат, подобный рисунку 9.
Рис. 9 - Основной экран в процессе обучения моде
После выбора всех параметров и начала обучения программа выдаёт результат, подобный рисунку 9.
В этом режиме пользователь обладает возможностью проанализировать результат обучения модели. Окно анализа модели показано на рисунке 10.
Рис. 10 - Экран анализа модели
Слева по-прежнему находится окно для вывода, в котором остался лог модели после её преждевременной остановки с помощью кнопки «Stop»программного интерфейса.
Анализ модели заключается в генерации документа-отчёта и видео, демонстрирующего работу обученного агента в среде.
Пользователю предлагается для генерации отчёта выбрать от 1 до 3 файлов с моделью с помощью кнопок «Choosefiletoload». После нажатия программа сгенерирует файлы с видео и файл с совместным отчётом для выбранных моделей.
3.2.2 Редактирование файла конфигурации
В режиме обучения модели пользователь может импортировать файл конфигурации, в том числе один из стандартных, идущих в комплекте с приложением. Кроме того, пользователь может отредактировать этот файл, нажав в приложении кнопку «Editconfig”.
ОС откроет в текстовом редакторе выбранный файл конфигурации, как на рисунке 11.
Рис. 11 - Текстовый редактор с открытым файлом конфига на фоне основного окна приложения
3.2.3 Параметры алгоритма
Ниже приведён список основных параметров, которые имеет смысл менять пользователю программы, если он хочет повлиять на поведение модели или процесс обучения в целом.
log_interval
Задаёт частоту, с которой метрики, характеризующие процесс обучения, выводятся в основное окно приложения. Задаётся в шагах обновлеиия параметров.
save_model_interval
Задаёт частоту, с которой обученная модель в виде файла с вычислительным графом сохраняется в папке с моделью. Задаётся в шагах обновлеиия параметров.
Lr
Параметр метода оптимизации, задающий скорость обучения. Слишкои малое значение может привести к слишком долгому процессу обучения, тогда как слишком большое может дестабилизировать процесс обучения. Обычно задаётся в диапазоне от 10-6 до
10-1
num_frames
Суммарное количество шагов, которое модель должна проделать в сумме по всем потокам. Для каждого частично наблюдаемого процесса необходимо своё количество шагов.
cnn_channels
Задаёт количество и размер слоёв в вычислительном графе. Список [64,64] означает, что в графе 2 слоя размерности 64
observation_type
Может принимать значение «fc», что означает «fully-connected», и сигнализирует о том, что среда выдаёт бесструктурный вектор чисел, который необходимо обрабатывать полносвязными слоями.
h_dim
Это размерность ячейки памяти, которая аккумулирует всю информацию о предыдущих наблюдениях.
action_encoding
Размерность представления, в которого кодируются совершаемые действий. Действия необходимо кодировать в более высокоразмерное пространство, поскольку между действиями нет отношения порядка, и нельзя просто подвать их в ячейку памяти.
detach_v
От этого зависит, пробрасываются ли градиенты через Value-функцию. В алгоритме Actor-critic, использующемся в данной работе, модель обучается предсказывать Value-функцию, то есть то, насколько много награды получит агент в будущем, находясь в данном состоянии. Эта функция обучается, используя квадратичную функцию ошибки, а на вход получает гипотезы о скрытом состоянии z. Может возникнуть ситуация, когда в случае пробрасывания градиентов по всему графу из-за зашкаливающих значений квадратичной функции ошибки процесс обучения дестабилизируется. Чтобы это предотвратить, у пользователя есть возможость запретить модели пробрасывать градиенты через z во время оптимизации value-функции.
z_dim
Размерность переменных z, которые генерируются алгоритмом.
Name
Название среды из библиотеки Gym, которая используется для обучения.
entry_point
В случае отсутствия среды она берётся из файла, указанного в данном параметре.
max_episode_steps
Ограничение сверху на количество шагов, которое делает алгоиритм в среде за 1 эпизод.
p_blank
Параметр для включения одного из видов частичной наблюдаемости - мигающего экрана. Задаётся числом от 0 до 1. С такой вероятностью каждый кадр, который видит агент, умножается на 0.
Параметры, специфические для среды MountainHike, которая используется в данном конкретном конфиге.
transition_std
observation_std
goal_reward
goal_position
goal_radius
goal_end
outside_box_cost
starting_position
starting_std
max_action_value
action_cost_factor
shaping_power
hill_height
box_scale
3.2.4 Отчёт о работе алгоритма
Отчёт состоит из 2 частей: видео и документа.
Рис. 12 - Документ-отчёт
Документ представляет собой pdf-файл, на каждой странице которого можно найти процесс изменения всех метрик, фиксируемых программой, в процессе обучения. На каждом графике находится 1 метрика, подписанная в верхнем правом углу страницы. Одновременно на одном графике находится от 1 до 3 моделей, выбранных пользователем.
Рис. 13 - Видео
На видео пользователь может увидеть пример работы обученного агента в среде. На экране можно увидеть кадр из среды MountainHike, в частности реальной положение агента (белая точка), и значение функции награды во всех точках двумерного пространства состояний (справа нарисована шкала «цвет-награда»)
ЗАКЛЮЧЕНИЕ
В результате проделанной работы было реализовано Python-приложение с графическим интерфейсом для создания и обучения агентов, взаимодействующих с частично наблюдаемыми Марковскими процессами принятия решений.
В ходе работы было проанализировано большое количество статей и методов, обнаружен ближайший аналог. Метод был изменён для учёта полученных наград во время предсказания динамики частично наблюдаемого Марковского процесса принятия решений.
Была разработана архитектура приложения и его графический интерфейс, для реализации графического интерфейса была выбрана библиотека Pyqt. Был реализован вычислительный граф, соответствующий предложенному алгоритму, с помощью библиотеки Pytorch.
Разработанное приложение содержит основной экран. На основном экране пользователь может выбрать режим работы - обучение модели или анализ полученных результатов, загружать ли предобученную модель для обучения или обучать новый вычислительный граф с нуля, а также выбрать конфигурацию алгоритма обучения и место сохранения модели. Кроме основного экрана, из приложения можно вызвать окно редактирования файла конфигурации.
В будущем планируется расширять библиотеку стандартных сред для обучения агентов, а также ввести функцию удалённого обучения моделей на сервере.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Mnih, Volodymyr, Kavukcuoglu, Koray, Silver, David, Graves, Alex, Antonoglou, Ioannis, Wierstra, Daan, and Riedmiller, Martin. Playing atari with deep reinforcement learning. In NIPS Deep Learning Workshop. [Электронныйресурс]: 2013 - Режимдоступаhttps://arxiv.org/abs/1312.5602, свободный. (датаобращения: 20.01.19)
2. Richard S. Sutton, David McAllester, Satinder Singh, Yishay Mansour. Policy Gradient Methods for Reinforcement Learning with Function Approximation. Advances in Neural Information Processing Systems [Электронныйресурс]: 2000 - Режимдоступаhttps://homes.cs.washington.edu/~todorov/courses/amath579/reading/PolicyGradient.pdf, свободный. (датаобращения: 20.01.19)
3. D. P. Kingma and M. Welling. Auto-Encoding Variational Bayes. In Proceedings of the International Conference on Learning Representations (ICLR)[Электронныйресурс]: 2014 - Режимдоступаhttps://arxiv.org/abs/1312.6114, свободный. (датаобращения: 20.01.19)
4. Junyoung Chung, Kyle Kastner, Laurent Dinh, Kratarth Goel, Aaron Courville, and YoshuaBengio. A recurrent latent variable model for sequential data.In Proc. NIPS[Электронныйресурс]: 2015 - Режимдоступаhttps://arxiv.org/abs/1506.02216, свободный. (датаобращения: 20.01.19)
5. AgustinusKristiadi. Conditional Variational Autoencoder: Intuition and Implementation[Электронныйресурс]: Report, 2016 - Режимдоступаhttps://wiseodd.github.io/techblog/2016/12/17/conditional-vae/, свободный. (дата обращения: 20.01.19)
6. Burda, Yuri, Grosse, Roger, and Salakhutdinov, Ruslan. Importance weighted autoencoders. InICLR, 2016. [Электронный ресурс]: - Режим доступа https://arxiv.org/abs/1509.00519, свободный. (дата обращения: 20.01.19)
7. Naesseth, Christian A, Linderman, Scott W, Ranganath, Rajesh, and Blei, David M. Variational sequential monte carlo. InAISTATS, 2018 [Электронный ресурс]: - Режим доступа https://arxiv.org/abs/1705.11140, свободный. (дата обращения: 20.01.19)
8. Le, Tuan Anh, Igl, Maximilian, Jin, Tom, Rainforth, Tom, and Wood, Frank. Auto-encodingsequentialMonteCarlo. In ICLR, 2018. [Электронныйресурс]:- Режимдоступаhttps://arxiv.org/abs/1705.10306, свободный. (датаобращения: 20.01.19)
9. Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, David Silver. Rainbow: Combining Improvements in Deep Reinforcement Learning. AAAI 2018. [Электронныйресурс]:- Режимдоступаhttps://arxiv.org/abs/1710.02298, свободный. (датаобращения: 20.01.19)
10. John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, Oleg Klimov. Proximal Policy Optimization Algorithms. [Электронныйресурс]: 2017 - Режимдоступаhttps://arxiv.org/abs/1707.06347, свободный. (датаобращения: 20.01.19)
11. Maximilian Igl, Luisa Zintgraf, Tuan Anh Le, Frank Wood, Shimon Whiteson. Deep Variational Reinforcement Learning for POMDPs. ICML, 2018. [Электронныйресурс]: Режимдоступаhttps://arxiv.org/abs/1806.02426, свободный. (датаобращения: 20.01.19)
Размещено на Allbest.ru
...Подобные документы
Анализ применения нейронных сетей для прогнозирования ситуации и принятия решений на фондовом рынке с помощью программного пакета моделирования нейронных сетей Trajan 3.0. Преобразование первичных данных, таблиц. Эргономическая оценка программы.
дипломная работа [3,8 M], добавлен 27.06.2011Нейронные сети как средство анализа процесса продаж мобильных телефонов. Автоматизированные решения на основе технологии нейронных сетей. Разработка программы прогнозирования оптово-розничных продаж мобильных телефонов на основе нейронных сетей.
дипломная работа [4,6 M], добавлен 22.09.2011Задача анализа деловой активности, факторы, влияющие на принятие решений. Современные информационные технологии и нейронные сети: принципы их работы. Исследование применения нейронных сетей в задачах прогнозирования финансовых ситуаций и принятия решений.
дипломная работа [955,3 K], добавлен 06.11.2011Исследование эффективности применения нейронных сетей в рамках отношений между людьми. Принцип работы с нейросимулятором. Составление обучающей выборки и проектирование персептронов. Анализ выбора супружеской пары с использованием нейросетевых технологий.
презентация [150,8 K], добавлен 19.08.2013Описание технологического процесса напуска бумаги. Конструкция бумагоделательной машины. Обоснование применения нейронных сетей в управлении формованием бумажного полотна. Математическая модель нейрона. Моделирование двух структур нейронных сетей.
курсовая работа [1,5 M], добавлен 15.10.2012Способы применения нейронных сетей для решения различных математических и логических задач. Принципы архитектуры их построения и цели работы программных комплексов. Основные достоинства и недостатки каждой из них. Пример рекуррентной сети Элмана.
курсовая работа [377,4 K], добавлен 26.02.2015Способы применения технологий нейронных сетей в системах обнаружения вторжений. Экспертные системы обнаружения сетевых атак. Искусственные сети, генетические алгоритмы. Преимущества и недостатки систем обнаружения вторжений на основе нейронных сетей.
контрольная работа [135,5 K], добавлен 30.11.2015Человеко-машинные комплексы, специально предназначенные для принятия решений. Процесс принятия решений и его этапы. Методы поиска новых вариантов решений: дерево решений, морфологические таблицы, конференции идей. Принцип математической оценки тенденций.
курсовая работа [272,1 K], добавлен 30.07.2009Методы решения проблем, возникающих на стадиях и этапах процесса принятия решений, их реализация в информационных системах поддержки принятия решений (СППР). Назначение СППР, история их эволюции и характеристика. Основные типы СППР, области их применения.
реферат [389,3 K], добавлен 22.11.2016Особенности нейронных сетей как параллельных вычислительных структур, ассоциируемых с работой человеческого мозга. История искусственных нейронных сетей как универсального инструмента для решения широкого класса задач. Программное обеспечение их работы.
презентация [582,1 K], добавлен 25.06.2013Изучение методов разработки систем управления на основе аппарата нечеткой логики и нейронных сетей. Емкость с двумя клапанами с целью установки заданного уровня жидкости и построение нескольких типов регуляторов. Проведение сравнительного анализа.
курсовая работа [322,5 K], добавлен 14.03.2009Математические модели, построенные по принципу организации и функционирования биологических нейронных сетей, их программные или аппаратные реализации. Разработка нейронной сети типа "многослойный персептрон" для прогнозирования выбора токарного станка.
курсовая работа [549,7 K], добавлен 03.03.2015Алгоритм декомпозиции графов и расчеты динамики логических сетей. Преобразование пространства булевых векторов. Описание блоков программной реализации и их взаимодействие. Разработка программы "слияния" статистик на основе алгоритма объединения.
дипломная работа [111,8 K], добавлен 07.03.2012Общее понятие файлообменной сети. Основные принципы работы файлообмена, его широкие возможности. Типы организации файлообменных сетей. Функционирование частично децентрализованных (гибридных) сетей. Устройство и особенности одноранговой сети, P2P.
презентация [685,6 K], добавлен 28.11.2012Простейшая сеть, состоящая из группы нейронов, образующих слой. Свойства нейрокомпьютеров (компьютеров на основе нейронных сетей), привлекательных с точки зрения их практического использования. Модели нейронных сетей. Персептрон и сеть Кохонена.
реферат [162,9 K], добавлен 30.09.2013Изучение назначения и основных задач, которые решает Project Expert - система поддержки принятия решений (СППР), предназначенная для менеджеров, проектирующих финансовую модель нового или действующего предприятия. Программные приложения, этапы работы.
реферат [30,7 K], добавлен 19.05.2010Разработка автоматизированной программы выбора оптимального решения с использованием критерия Гермейера и минимаксного критерия; блок-схема программы. Особенности подхода Гермейера к отысканию пригодных к компромиссу решений в области полиоптимизации.
контрольная работа [524,4 K], добавлен 05.07.2014Искусственные нейронные сети как одна из широко известных и используемых моделей машинного обучения. Знакомство с особенностями разработки системы распознавания изображений на основе аппарата искусственных нейронных сетей. Анализ типов машинного обучения.
дипломная работа [1,8 M], добавлен 08.02.2017Применение нейрокомпьютеров на российском финансовом рынке. Прогнозирование временных рядов на основе нейросетевых методов обработки. Определение курсов облигаций и акций предприятий. Применение нейронных сетей к задачам анализа биржевой деятельности.
курсовая работа [527,2 K], добавлен 28.05.2009Проведения анализа существующих генных сетей. Три типа вершин актуальных объектов для поточечной редукции: источники, стоки и проводящие вершины. Существующие методы декомпозиции. Алгоритм "walktrap" на основе случайных блужданий и определения смежности.
курсовая работа [2,6 M], добавлен 28.02.2012
