Промежуточный отчет за I этап Машинное обучение




Скачать 63.47 Kb.
НазваниеПромежуточный отчет за I этап Машинное обучение
Дата публикации15.03.2013
Размер63.47 Kb.
ТипОтчет
vbibl.ru > Информатика > Отчет



Применение методов искусственного интеллекта в разработке управляющих программных систем

Промежуточный отчет за I этап

1.1.Машинное обучение


В настоящем подразделе излагается метод построения систем управления с помощью машинного обучения на основе работ [1, 2]. Здесь и далее под машинным обучением понимается обучение с подкреплением (Reinforcement Learning).

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

Целью является построение такой стратегии, которая максимизирует математическое ожидание некоторой целевой функции . В практических задачах наиболее часто используется модель бесконечного горизонта (Infinite horizon model):



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

Традиционным способом решения задач машинного обучения является алгоритм Q-learning [4]. Введем функцию , определяющую для каждой пары состояние-действие максимальную прибыль, которую получит агент, если, находясь в состоянии , выберет действие . Данная функция связана с оптимальной стратегией следующим образом:



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

Заметим, что функция удовлетворяет следующему реккурентному соотношению:



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

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

Классическим способом пересчета функции является метод одношаговой временной разности (Temporal Difference) [1]. При использовании этого метода выражение для пересчета функции принимает следующий вид:


Здесь – параметр, определяющий скорость изменения оценки функции.

Метод одношаговой временной разности является частным случаем метода временной разности (TD()) [1]. Метод временной разности учитывает не только последний шаг агента, все последние шаги. Можно определить временную разность как разность предсказания будущего значения функции ^ Q c реально полученным значением через i шагов. Ошибки предсказания на более давних шагах вносят меньший вклад по сравнению с ошибкой предсказания последнего на последнем шагу. Более формально, пересчет осуществляется по следующему правилу:

, где .

Методу одношаговой временной разности соответствует .

Заметим, что на ранних стадиях обучения значения оценки функции могут сильно отличаться от ее реального значения. Если при этом всегда использовать максимум для выбора следующего действия, то есть осуществлять жадный выбор, то конечные значения оценки могут не сойтись к реальным значениям функции. Этот недостаток частично разрешен в алгоритме SARSA (State-Action-Reward-State-Action) [5]. При использовании такого подхода выбор очередного действие агента осуществляется случайно. При этом учитываются текущая оценка значения функции — состояния с большим значением функции имеют большую вероятность быть выбранными. Правило для пересчета функции имеет следующий вид:



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

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

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

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



Здесь —градиент по , — одношаговая временная разность.

В работе [8] используются нейронные сети с архитектурой CMAC [9]. Нейронная сеть такого типа состоит из нескольких слоев. Этих слои представляют собой разбиение пространства состояний на некоторые гиперпрямоугольники (Error: Reference source not found).



  1. Разбиение на гиперпрямоугольники


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

В работе [10] функция аппроксимируется с помощью деревьев классификации (Regression Tree) ­– обобщения деревьев решений. В листьях дерева классификации хранится значение функции, в его внутренних узлах производится расщепление в зависимости от значений аргументов функции. Пример дерева классификации приведен на Error: Reference source not found.




  1. Пример дерева классификации


В работе [11] используется аппроксимация функции с помощью Kernel Regression – в качестве приближения функции используется взвешенное среднее с произвольным ядром , то есть


В табл. Таблица 1. приводится обзорное сравнение указанных работ.

  1. Сравнение работ, использующих машинное обучение

Название работы

Решаемая задача

Метод аппроксимации

Neuron-like elements that can solve difficult learning control problems

Задача балансировки шеста на тележке

дискретизация

Implementation details of TD(λ) procedure for case of vector predictions and backpropagation

Не указана

нейронные сети, пересчет производится с учетом временной разницы

Reinforcement Learning for Multi-linked Manipulator Control

Задача управления роботом

нейронные сети CMAC

Tree-Based Batch Mode Reinforcement Learning

Задача балансировки при управлении велосипедом

деревья классификации

Kernel-based Reinforcement Learning in Average-cost Problems

Выбор оптимального портфеля акций

Kernel Regression



Литература


  1. Sutton R. S. Learning to predict by methods of temporal differences, Machine Learning 1988, 3: pp. 9–44.

  2. Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. MIT Press, 1998.

  3. Bellman R. Dynamic Programming, Princeton, NJ: Princeton University Press, 1957.

  4. Watkins C. Learning from Delayed Rewards, University of Cambridge, 1989.

  5. Rummery G., Niranjan M. On-line Q-learning using Connectionist systems, technical report №166, University of Cambridge, Engineering Department, 1994.

  6. Bartо A. G., Sutton R. S., Anderson C. W. Neuron-like elements that can solve difficult learning control problems / IEEE Transactions on Systems, Man and Cybernetics, 1983, №13: pp. 835 – 846.

  7. Sutton R. S. Implementation details of TD(λ) procedure for case of vector predictions and backpropagation, TN87-509.1, GTE Laboratories, 1989.

  8. Tham C. K., Prager K. W. Reinforcement Learning for Multi-linked Manipulator Control, 1994.

  9. Albus J. S. Data Storage in the Cerebellar Model Articulation Controller (CMAC) / Journal of Dynamic Systems, Measurement and Control, 1975, pp. 228-233

  10. Ernst D., Geurts P., Wehenkel L. Tree-Based Batch Mode Reinforcement Learning / Journal of Machine Learning Research №6, pp. 503–556, 2005.

  11. Ormoneit D., Glynn P. Kernel-based reinforcement learning in average-cost problems / IEEE Transactions on Automatic Control, 2002, №47(10), pp. 624–636.

Добавить документ в свой блог или на сайт

Похожие:

Промежуточный отчет за I этап Машинное обучение iconКомпания Festo представляет последние проекты научно-исследовательского...
Тносятся такие области исследований, как функциональная интеграция, облегченные конструкции, автоконфигурация и машинное обучение....

Промежуточный отчет за I этап Машинное обучение iconКомсомольская правда, 20 мая 1994, с. 26. Света кузина может ли мужчина...
Природа-мать ему это дозволяет. Вот что непонятно: человек, будучи еще простейшей клеткой, начал усиленно работать над собой, чтобы...

Промежуточный отчет за I этап Машинное обучение icon2. Символьное обучение (обучение в пространстве понятий)
Обучение (в работах по ии): «любое изменение в системе, приводящее к улучшению решения задачи при ее повторном предъявлении или к...

Промежуточный отчет за I этап Машинное обучение iconРедуктор промежуточный

Промежуточный отчет за I этап Машинное обучение icon5. Программы отдельных учебных предметов, курсов
Начальная школа — самоценный, принципиально новый этап в жизни ребёнка: начинается систематическое обучение в образовательном учреждении,...

Промежуточный отчет за I этап Машинное обучение icon2. Проверочный расчет карданной передачи Карданная передача имеет...
Карданная передача имеет два вала – основной и промежуточный – и три жестких карданных шарнира на игольчатых подшипниках

Промежуточный отчет за I этап Машинное обучение iconЖилищное право. Информационно-справочное издание
Доступное и комфортное жилье гражданам России, рассчитанный на 6 лет (до 2012 г.). Он включает подготовительный этап (2005 г.), первый...

Промежуточный отчет за I этап Машинное обучение iconО классике фса замолвите слово Часть Творческий этап (часть 1, часть 2)
Творческий этап – это второй (после аналитического) ключевой этап, от которого зависит эффективность проведения функционально-стоимостного...

Промежуточный отчет за I этап Машинное обучение icon5 этап массовых соревнований по спортивному ориентированию "Березинский...

Промежуточный отчет за I этап Машинное обучение iconПояснительная записка к контрольно-курсовой работе по курсу «Человеко-машинное взаимодействие»
...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница