Обучение с подкреплением

Перевод Обучение умных игровых соперников в Unity методом игра с самим собой средствами ML-Agents

18.06.2020 14:14:33 |

Автор: admin

Привет, Хабр!

Как знают наши постоянные читатели, мы давно и успешно издаем книги по Unity. В рамках проработки темы нас заинтересовал, в частности, инструментарий ML-Agents Toolkit. Сегодня мы предлагаем вашему вниманию перевод статьи из блога Unity о том, как эффективно обучать игровых агентов методом игры с самим собой; в частности, статья помогает понять, чем этот метод эффективнее традиционного обучения с подкреплением.

Приятного чтения!

В этом после дается обзор технологии self-play (игра с самим собой) и демонстрируется, как с ее помощью обеспечивается стабильное и эффективное обучение в демонстрационной среде Soccer из инструментария ML-Agents Toolkit.

В демонстрационных средах Tennis и Soccer из инструментария Unity ML-Agents Toolkit агенты стравливаются друг с другом как соперники. Обучение агентов в рамках такого состязательного сценария порой весьма нетривиальная задача. На самом деле, в предыдущих релизах ML-Agents Toolkit для того, чтобы агент уверенно обучился, требовалась серьезная проработка награды. В версии 0.14 была добавлена возможность, позволяющая пользователю тренировать агентов методом обучения с подкреплением (RL) на основе self-play, механизма, имеющего принципиальное значение в достижении одних из наиболее высококлассных результатов обучения с подкреплением, например, OpenAI Five и DeepMinds AlphaStar. Self-play при работе стравливает друг с другом актуальную и прошлую ипостаси агента. Таким образом, мы получаем противника для нашего агента, который может постепенно совершенствоваться с использованием традиционных алгоритмов обучения с подкреплением. Полноценно обученный агент может успешно соперничать с продвинутыми игроками-людьми.

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

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

История игры с самим собой в играх

У феномена игры с самим собой долгая история, отразившаяся в практике разработки искусственных игровых агентов, призванных соперничать с человеком в играх. Одним из первых эту систему использовал Артур Сэмюэл, разработавший в 1950-е симулятор для игры в шахматы и опубликовавший эту работу в 1959 году. Эта система стала предтечей эпохального результата в обучении с подкреплением, достигнутого Джеральдом Тезауро в игре TD-Gammon; итоги опубликованы в 1995 году. В TD-Gammon использовался алгоритм работы по методу временных различий TD() с функцией игры самим с собой, чтобы обучить агент игре в нарды настолько, что он мог бы посоперничать с человеком-профессионалом. В некоторых случаях наблюдалось, что TD-Gammon обладает более уверенным видением позиций, чем игроки международного класса.

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

Игра с самим собой наделяет агентов определенной креативностью, не зависящей от творчества программистов. Агент получает лишь правила игры, а затем информацию о том, выиграл он или проиграл. Далее, опираясь на эти базовые принципы, агент должен сам выработать грамотное поведение. По словам создателя TD-Gammon, такой подход к обучению освобождает, в том смысле, что программа не стеснена человеческими склонностями и предрассудками, которые могут оказаться ошибочными и ненадежными. Благодаря такой свободе, агенты открывают блестящие игровые стратегии, совершенно изменившие представления специалистов-инженеров о некоторых играх.

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

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

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

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

Пример со средой Теннис из инструментария ML-Agents

Рассмотрим демо-пример ML-Agents Tennis. Голубая ракетка (слева) это обучающийся агент, а фиолетовая (справа) его соперник. Чтобы перекинуть мяч через сетку, агент должен учитывать траекторию мяча, летящего от соперника, и делать поправку угла и скорости летящего мяча с учетом условий среды (гравитации). Однако, в состязании с соперником перебросить мяч через сетку это лишь полдела. Сильный соперник может ответить неотразимым ударом, и в результате агент проиграет. Слабый соперник может попасть мячом в сетку. Равный же соперник может вернуть подачу, и поэтому игра продолжится. В любом случае, как следующее состояние, так и соответствующая ему награда зависят как от условий окружающей среды, так и от соперника. Однако, во всех этих ситуациях агент делает одну и ту же подачу. Поэтому как обучение в состязательных играх, так и прокачка сопернических поведений у агента это сложные проблемы.

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

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

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

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

Практические соображения

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

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

Реализация и детали использования

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

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

Игра с самим собой в среде Soccer

В последние релизы ML-Agent Toolkit не включается политика агентов для учебной среды Soccer, поскольку надежный учебный процесс в ней не выстраивался. Однако, задействовав игру с самим собой и проведя некоторый рефакторинг, мы сможем обучать агента нетривиальным вариантам поведения. Наиболее существенное изменение это удаление игровых позиций из числа характеристик агента. Ранее в среде Soccer явно выделялись вратарь и нападающий, поэтому весь геймплей выглядел более логично. В данном видео представлена новая среда, в которой видно, как спонтанно формируется ролевое поведение, при котором одни агенты начинают выступать в качестве нападающих, а другие в качестве вратарей. Теперь агенты сами учатся играть на этих позициях! Функция награды для всех четырех агентов определяется как +1.0 за забитый гол и -1.0 за пропущенный гол, с дополнительным штрафом -0.0003 за шаг этот штраф предусмотрен, чтобы стимулировать агентов на атаку.

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

Что дальше

Если вам доводилось пользоваться какими-либо новыми возможностями из этого релиза расскажите о них. Обращаем ваше внимание на страницу ML-Agents GitHub issues, где можно рассказать о найденных багах, а также на страницу форумов Unity ML-Agents, где обсуждаются вопросы и проблемы общего характера.

Подробнее..

Категории: Программирование , Алгоритмы , Разработка игр , Блог компании издательский дом «питер» , Unity , Rl , Self-play , Игры , Обучение с подкреплением , Ml-agents toolkit

Перевод Как искусственный интеллект играет в Змейку

28.09.2020 16:10:09 |

Автор: admin

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

С тех пор, как я посмотрела документальный фильм Netflix об AlphaGo, я была очарована обучением с подкреплением. Такое обучение сравнимо с человеческим: вы видите что-то, делаете что-то и у ваших действий есть последствия. Хорошие или не очень. Вы учитесь на последствиях и корректируете действия. У обучения с подкреплением множество приложений: автономное вождение, робототехника, торговля, игры. Если обучение с подкреплением вам знакомо, пропустите следующие два раздела.

Обучение с подкреплением

Принцип простой. Агент учится через взаимодействие со средой. Он выбирает действие и получает отклик от среды в виде состояний (или наблюдений) и наград. Этот цикл продолжается постоянно или до состояния прерывания. Затем наступает новый эпизод. Схематично это выглядит так:

Цель агента получить максимум наград за эпизод. Вначале обучения агент исследует среду: пробует разные действия в одном и том же состоянии. С течением обучения агент исследует всё меньше. Вместо этого он, основываясь на собственном опыте, выбирает действие, приносящее наибольшую награду.

Глубокое обучение с подкреплением

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

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

Определяем действия, награды и состояния

Чтобы подготовить игру для агента, формализуем проблему. Определить действия просто. Агент может выбирать направление: вверх, вправо, вниз или влево. Награды и состояние пространства немного сложнее. Есть много решений и одно будет работать лучше, а другое хуже. Одно из них опишу ниже и давайте попробуем его.

Если Змейка подбирает яблоко, ее награда 10 баллов. Если Змейка умирает, отнимаем от награды 100 баллов. Чтобы помочь агенту, добавляем 1 балл, когда Змейка проходит близко к яблоку и отнимаем один балл, когда Змейка удаляется от яблока.

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

Создаем среду и агента

Добавляя методы в программу Змейки, мы создаём среду обучения с подкреплением. Методы будут такими: reset(self), step(self, action) и get_state(self). Кроме того, нужно рассчитывать награду на каждом шаге агента. Посмотрите на run_game(self).

Агент работает с сетью Deep Q, чтобы найти лучшие действия. Параметры модели ниже:

# epsilon sets the level of exploration and decreases over timeparams['epsilon'] = 1params['gamma'] = .95params['batch_size'] = 500params['epsilon_min'] = .01params['epsilon_decay'] = .995params['learning_rate'] = 0.00025params['layer_sizes'] = [128, 128, 128]

Если интересно посмотреть на код, вы найдёте его на GitHub.

Агент играет в Змейку

А теперь ключевой вопрос! Научиться ли агент играть? Понаблюдаем, как он взаимодействует со средой. Ниже первые игры. Агент ничего не понимает:

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

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

Агент учится: его путь к яблоку не самый короткий, но он находит яблоко. Ниже тридцатая игра:

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

Поиграем с пространством

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

Без направлений: не сообщать агенту направления, в которых движется Змейка.
Состояние с координатами: замени положение яблока (вверх, вправо, вниз и / или влево) координатами яблока (x, y) и змеи (x, y). Значения координат находятся на шкале от 0 до 1.
Состояние направление 0 или 1.
Состояние только стены: сообщает только о том, есть ли стена. Но не о том, где находится тело: внизу, наверху, справа или слева.

Ниже графики производительности разных состояний:

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

Понятно, что когда пространство состояний имеет направления, агент учится быстро, достигая наилучших результатов. Но пространство с координатами лучше. Может быть, можно достичь лучших результатов, дольше тренируя сеть. Причиной медленного обучения может быть число возможных состояний: 20*2*4 = 1,024,000. Поле 20 на 20, 64 варианта для препятствий и 4 варианта текущего направления. Для исходного пространства вариантов 3*2*4 = 576. Это более чем в 1700 раз меньше, чем 1,024,000 и, конечно, влияет на обучение.

Поиграем с наградами

Есть ли лучшая внутренняя логика награждения? Напоминаю, Змейка награждается так:

Первая ошибка. Хождение по кругу

Что, если изменить -1 на +1? Это может замедлить обучение, но в конце концов Змейка не умирает. И это очень важно для игры. Агент быстро учится избегать смерти.

На одном временном отрезке агент получает один балл за выживание.

Вторая ошибка. Удар о стену

Изменим количество баллов за прохождение около яблока на -1. Награду за само яблоко установим в 100 баллов. Что произойдет? Агент получает штраф за каждое движение, поэтому двигается к яблоку максимально быстро. Так может случиться, но есть и другой вариант.

ИИ проходит по ближайшей стене, чтобы минимизировать потери.

Опыт

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

Ошибка 3. Нет опыта

Опыт действительно так важен? Давайте уберём его. И возьмём награду за яблоко в 100 баллов. Ниже агент без опыта, сыгравший 2500 игр.

Хотя агент сыграл 2500 (!) игр, в змейку он не играет. Игра быстро заканчивается. Иначе 10 000 игр заняли бы дни. После 3000 игру у нас только 3 яблока. После 10 000 игр яблок по-прежнему 3. Это удача или результат обучения?

Действительно, опыт очень помогает. Хотя бы опыт, учитывающий награды и тип пространства. Как много нужно переигрываний на шаг? Ответ может удивить. Чтобы ответить на этот вопрос, поиграем с параметром batch_size. В исходном эксперименте он установлен в 500. Обзор результатов с разным опытом:

200 игр с разным опытом: 1 игра (опыта нет), 2 и 4. Среднее за 20 игр.

Даже с опытом в 2 игры агент уже учится играть. В графе вы видите влияние batch_size, та же производительность достигается на 100 игр, если вместо 2 используется 4. Решение в статье дает результат. Агент учится играть в Змейку и достигает хороших результатов, собирая от 40 до 60 яблок за 50 игр.

Внимательный читатель может сказать: максимум яблок в змейке 399. Почему ИИ не выигрывает? Разница между 60 и 399, в сущности, небольшая. И это верно. И здесь есть проблема: Змейка не избегает столкновений при замыкании на себя.

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

Библиография

[1] K. Hornik, M. Stinchcombe, H. White, Multilayer feedforward networks are universal approximators (1989), Neural networks 2.5: 359366
[2] Mnih et al, Playing Atari with Deep Reinforcement Learning (2013)

Узнайте подробности, как получить востребованную профессию с нуля или Level Up по навыкам и зарплате, пройдя онлайн-курсы SkillFactory:

Курс по Machine Learning (12 недель)

Курс Математика и Machine Learning для Data Science (20 недель)

Продвинутый курс Machine Learning Pro + Deep Learning (20 недель)

Обучение профессии Data Science с нуля (12 месяцев)

Eще курсы

Профессия Веб-разработчик (8 месяцев)

Онлайн-буткемп по Data Analytics (5 недель)

Курс по аналитике данных (6 месяцев)

Профессия аналитика с любым стартовым уровнем (18 месяцев)

Курс Python для веб-разработки (9 месяцев)

Курс по DevOps (12 месяцев)

Профессия Java-разработчик с нуля (18 месяцев)

Курс по JavaScript (12 месяцев)

Профессия UX-дизайнер с нуля (9 месяцев)

Профессия Web-дизайнер (7 месяцев)

Подробнее..

Категории: Ненормальное программирование , Python , Машинное обучение , Блог компании skillfactory , Обучение с подкреплением , Глубокое обучение , Skillfactory , Змейка

ИИ снова победил пилота F-16 в воздушном бою

21.08.2020 14:20:51 |

Автор: admin

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

Это не первый раз, когда ИИ побеждает пилота-человека. Испытания 2016 года показали, что система искусственного интеллекта может победить опытного инструктора по боевым полетам. Но симуляция DARPA в четверг, возможно, была более значимой, поскольку она столкнула множество алгоритмов между собой, а затем против человека в сложных условиях. Помимо интеграции ИИ в боевые машины для повышения их боеспособности, подобные симуляции также могут помочь тренировать человеческих пилотов.

Начало

В августе прошлого года агентство Defense Advanced Research Project Agency (DARPA) выбрало восемь команд для участия в серии испытаний. В список попали Aurora Flight Sciences, EpiSys Science, Georgia Tech Research Institute, Heron Systems, Lockheed Martin, Perspecta Labs, PhysicsAI и SoarTech (как можно понять, наряду с крупными подрядчиками оборонной промышленности, типа Lockheed Martin вопросом занимались и небольшие компании, вроде Heron Systems).

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

Первый этап AlphaDogfight Trials проводился в ноябре 2019 года в лаборатории прикладной физики университета Джонса Хопкинса. На нем нейросетевые алгоритмы, созданные разными командами, вели воздушный бой с системой искусственного интеллекта Red, созданной специалистами DARPA. Бои между алгоритмами велись в режиме 1х1 на низком уровне сложности. Второй этап испытаний прошел в январе 2020 года. Он отличался от первого повышенной сложностью. Заключительный этап испытаний, состоявшийся 20 августа 2020 года, можно было посмотреть в прямом эфире на YouTube-канале DARPA.

Испытания проводились в авиационном симуляторе FlightGear с использованием программной модели динамики полета JSBSim. В первых двух этапах нейросетевые алгоритмы управляли тяжёлыми истребителями F-15C Eagle, а в третьем средними F-16 Fighting Falcon.

Как машина победила человека

На третьем этапе испытаний нейросетевые алгоритмы сперва провели воздушные бои друг с другом. Победителем всех боев была признана система, созданная компанией Heron Systems. Воздушные бои велись на ближней дистанции с использованием только пушечного вооружения.
Затем алгоритм Heron Systems провел воздушный бой с опытным летчиком-истребителем и инструктором ВВС США с позывным Banhger. Всего было проведено пять боев. ИИ-алгоритм одержал победу во всех. Стандартные приёмы воздушного боя, которые изучают летчики-истребители, не сработали, признал проигравший машине пилот. Но в последних раундах человек смог продержаться дольше.

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

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

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

Немного деталей

Ли Ритхольц, директор и главный архитектор искусственного интеллекта из Lockheed Martin, после испытаний рассказал журналистам, что попытка заставить алгоритм хорошо работать в воздушном бою сильно отличается от обучения программному обеспечению просто летать, то есть поддерживать определённое направление, высоту и скорость.

Изначально компьютерная программа не понимает даже самые элементарные вещи, что ставит её в уязвимое положение по сравнению с любым человеком. Вам не нужно объяснять пилоту, что он не должен врезаться в землю. Это базовые инстинкты, напрочь отсутствующие у машины. Преодоление этого незнания требует обучения алгоритма тому, что за каждую ошибку приходится платить. Обучение с подкреплением вступает в игру, когда алгоритм назначает веса [затраты] каждому маневру, а затем повторно определяет эти веса по мере обновления своего опыта.

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

Нет сомнений в том, что ИИ может учиться, и очень быстро. Используя локальные или облачные ресурсы для моделирования воздушных боёв, что он может повторять урок снова и снова на нескольких машинах. У Lockheed, как и у нескольких других команд, был пилот-истребитель. Они также могли запускать обучающие наборы на 25 серверах DGx1 одновременно. Но то, что они в конечном итоге производили, могло работать на одном GPU. Для сравнения, после победы Бен Белл, старший инженер по машинному обучению в Heron Systems, сказал, что их алгоритм прошёл не менее 4 млрд симуляций и приобрёл примерно 12 лет опыта.

В итоге DARPA поздравили с победой стартап Heron Systems, чей алгоритм сумел обойти разработки более крупных компаний вроде Lockheed Martin.

Что ещё интересного есть в блоге Cloud4Y

Сделай сам, или компьютер из Югославии
Госдепартамент США создаст свой великий файерволл
Искусственный интеллект поёт о революции
Какова геометрия Вселенной?
Пасхалки на топографических картах Швейцарии

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

Подробнее..

Категории: Научно-популярное , Искусственный интеллект , It-компании , Обучение с подкреплением , Блог компании cloud4y , Ии , Darpa , Самолёт

Music2Dance как мы пытались научиться танцевать

19.05.2021 08:16:04 |

Автор: admin

Всем привет! Меня зовут Владислав Мосин, я учусь на 4-м курсе бакалаврской программы Прикладная математика и информатика в Питерской Вышке. Прошлым летом вместе с Алиной Плешковой, магистранткой нашего факультета, я проходил стажировку в JetBrains Research. Мы работали над проектом Music2Dance, цель которого научиться генерировать танцевальные движения, подходящие под заданную музыку. Это может быть использовано, например, при самостоятельном обучении танцам: услышал музыку, запустил приложение, и оно показало движения, которые гармонично с этой музыкой сочетаются.

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

Из к/ф Криминальное чтиво

Существующие подходы

Идея генерации танца по музыке довольно стара. Наверное, самый яркий пример это танцевальные симуляторы типа Dance Dance Revolution, где игрок должен наступать на светящиеся в такт музыке панели на полу, и таким образом создается некоторое подобие танца. Также красивый результат в этой области это создание танцующих геометрических фигур или 2D-человечков.

Cуществуют и более серьезные работы генерация 3D-движений для людей. Большинство таких подходов основываются исключительно на глубоком обучении. Лучшие результаты на лето 2020 года показывала архитектура DanceNet, и мы решили взять именно её в качестве бейзлайна. Дальше мы обсудим их подход подробнее.

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

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

Музыка: onset, beats, chroma

Наверное, самый распространенный способ извлечение фичей из аудио это подсчет спектрограммы или мелграммы преобразование звука из амплитудного домена в частотный при помощи преобразования Фурье. Однако, в нашей задаче мы работаем с музыкой, а не произвольным аудиосигналом, и низкоуровневый анализ в данном случае не подходит. Нас интересуют ритм и мелодия, поэтому мы будем извлекать onset, beats и chroma (начало ноты, ритм и настроение мелодии).

Видео: извлечение позы человека

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

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

Синим отмечены ключевые точки

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

Важной особенностью этого метода является способ хранения положений ключевых точек. Например, если хранить просто абсолютные положения в 3D-пространстве, то возникает проблема нефиксированной длины костей: расстояние между голенью и коленом или плечом и локтем может изменяться от кадра к кадру, что не является ожидаемым поведением. Для избежания таких проблем фиксируется положение одной точки человека, а именно середины таза, а положение всех остальных задается через длину кости и угол поворота относительно предыдущей точки. Поясню на примере: положение кисти задается через длину лучевой кости, а также поворот относительно локтя.

Архитектура DanceNet

Архитектура DanceNet. Источник: https://arxiv.org/abs/2002.03761

Архитектура DanceNet cocтоит из нескольких основных частей:

Кодирование музыки;
Классификация музыки по стилю;
Кодирование кадров видео;
Предсказание следующего кадра по предыдущим и музыке;
Декодирование полученного кадра.

Рассмотрим немного подробнее каждую из частей:

Кодирование музыки. Предобратанный аудиосигнал кодируется при помощи сверточной нейросети с Bi-LSTM слоем.
Классификация музыки по стилю. Аналогично предыдущему пункту, сверточная нейросеть с Bi-LSTM слоем.
Кодирование-декодирование кадра. Маленькая двухслойная сверточная сеть.
Предсказание следующего кадра. Самая содержательная часть архитектуры, которая собственно и предсказывает следующую позу по предыдущим и музыке. Состоит из блоков из dilated (расширенных) сверток со скип-соединениями.

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

Наше решение

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

Архитектура решения. Эпоха тренировки

Наше решение состоит из четырех основных частей:

Датасет
Модель для предсказания следующего положения (DanceNet)
Модель для исправления следующего положения положения (RL модель)
Функция потерь

Датасет

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

DanceNet

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

RL модель

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

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

Структура алгоритмов обучения с подкреплением

В качестве алгоритмов обучения с подкреплением мы решили выбрать один алгоритм, использующий Q-Learning (наш выбор пал на TD3, как на наиболее стабильный и выразительный) и один не использующий (мы остановились на PPO).

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

Функция потерь

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

$L(S, S_{real},R)=-\parallel S-S{real} \parallel_2-R ,$

где S положение, S_real правильное положение, R награда среды.

Модель на фазе тестирования

Архитектура решения. Эпоха тестирования

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

Результаты

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

Наш грустный танец. Спасибо за ваш интерес!

Другие материалы из нашего блога о стажировках:

Как объединить 10 BERT-ов для задач общего понимания текста?
Беспилотное такси возит по городу желтых резиновых уточек! Модуль проверки задач для платформы Gym-Duckietown
Стажировки в Google: Цюрих, Лондон и Кремниевая долина

Подробнее..

Категории: Алгоритмы , Искусственный интеллект , Машинное обучение , Machine learning , Учебный процесс в it , Обучение с подкреплением , Вшэ спб , Блог компании питерская вышка , Музыка , Jetbrains , Стажировка , Танцы

Из песочницы Учим ИИ распределять пироги по магазинам с помощью обучения с подкреплением

21.07.2020 14:09:04 |

Автор: admin

Вступление

Как-то во время чтения книги Reinforcement Learning: An Introduction я задумался над дополнением своих теоретических знаний практическими, однако решать очередную задачу балансировки бруска, учить агента играть в шахматы или же изобретать другой велосипед желания не было.

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

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

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

Итак, представьте следующую картину:

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

Однако как лучше это делать так, чтобы было как можно меньше просроченной продукции (при условии, что срок годности пирогов составляет три дня), если мы имеем только три грузовика с вместительностью в 1, 2 и 3 тонны соответственно, в каждую точку продажи наиболее выгодно отправлять только один грузовик (ибо они расположены друг от друга достаточно далеко) и притом только раз в сутки после выпечки пирогов, да к тому же мы не знаем покупательской способности в наших магазинах (так как бизнес только запустили)?

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

Мы (условно) не знаем какой спрос на пироги в конкретный день в том или ином магазине будет, однако в нашей симуляции мы задаем его следующим образом для каждого из трех магазинов: 3 0.1, 1 0.1, 2 0.1.

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

Для решения данной задачи используем кастомную среду gym, а также Deep Q Learning (Keras имплементация).

Кастомная среда

Состояние среды будем описывать тремя действительными положительными числами остатками продукции на текущий день в каждом из трех магазинов. Действия агента это числа от 0 до 5 включительно, обозначающие индексы перестановки целых чисел 1, 2 и 3. Ясно, что наиболее выгодное действие будет под 4-ым индексом (3, 1, 2). Задачу рассматриваем как эпизодическую, в одном эпизоде 30 дней.

import gymfrom gym import error, spaces, utilsfrom gym.utils import seedingimport itertoolsimport randomimport timeclass ShopsEnv(gym.Env):  metadata = {'render.modes': ['human']}    # конструктор класса, в котором происходит  # инициализация среды  def __init__(self):    self.state = [0, 0, 0]  # текущее состояние    self.next_state = [0, 0, 0]  # следующее состояние    self.done = False  # флажок завершения эпизода    self.actions = list(itertools.permutations([1, 2, 3]))  # массив возможных действий агента    self.reward = 0  # текущая награда за действие    self.time_tracker = 0  # трекер дня эпизода        self.remembered_states = []  # очередь из трех последних состояний        # для стохастичности среды    t = int( time.time() * 1000.0 )    random.seed( ((t & 0xff000000) >> 24) +                 ((t & 0x00ff0000) >>  8) +                 ((t & 0x0000ff00) <<  8) +                 ((t & 0x000000ff) << 24)   )    # метод позволяет агенту выполнить одно действие (шаг) в среде  def step(self, action_num):    # проверяем не завершен ли уже эпизод    if self.done:        return [self.state, self.reward, self.done, self.next_state]    else:        # выбираем следующее состояние текущим        self.state = self.next_state                # запоминаем состояние        self.remembered_states.append(self.state)             # инкрементируем трекер        self.time_tracker += 1                # выбираем действие в соответствии с полученным индексом        action = self.actions[action_num]                # обновляем состояние, используя выбранное действие (добавляем пироги)        self.next_state = [x + y for x, y in zip(action, self.state)]                # генерируем сколько будет куплено        self.next_state[0] -= (3 + random.uniform(-0.1, 0.1))        self.next_state[1] -= (1 + random.uniform(-0.1, 0.1))        self.next_state[2] -= (2 + random.uniform(-0.1, 0.1))                # вычисляем награду за действие        if any([x < 0 for x in self.next_state]):            self.reward = sum([x for x in self.next_state if x < 0])        else:            self.reward = 1                    # если накопилась очередь из минимум трех состояний        # значит нужно убрать просроченные продукты        # при этом если ушли в минус (не хватило пирогов для покупателей),        # то также убираем данные отрицательные значения        if self.time_tracker >= 3:            remembered_state = self.remembered_states.pop(0)            self.next_state = [max(x - y, 0) for x, y in zip(self.next_state, remembered_state)]        else:            self.next_state = [max(x, 0) for x in self.next_state]                        # проверяем прошло ли уже 30 дней        self.done = self.time_tracker == 30                # возвращаем результат шага агента в среде        return [self.state, self.reward, self.done, self.next_state]    # метод перезагрузки среды  def reset(self):    # устанавливаем все параметры в изначальное положение    self.state = [0, 0, 0]    self.next_state = [0, 0, 0]    self.done = False    self.reward = 0    self.time_tracker = 0        self.remembered_states = []        t = int( time.time() * 1000.0 )    random.seed( ((t & 0xff000000) >> 24) +                 ((t & 0x00ff0000) >>  8) +                 ((t & 0x0000ff00) <<  8) +                 ((t & 0x000000ff) << 24)   )        # возвращаем изначальное состояние    return self.state    # метод рендера текущего состояния среды:  # сколько и в каком магазине пирогов  def render(self, mode='human', close=False):    print('-'*20)    print('First shop')    print('Pies:', self.state[0])    print('Second shop')    print('Pies:', self.state[1])    print('Third shop')    print('Pies:', self.state[2])    print('-'*20)    print('')

Главные импорты

import numpy as np # линейная алгебраimport pandas as pd # препроцессинг данныхimport gym # для средimport gym_shops # для своей кастомной средыfrom tqdm import tqdm # для прогресс бара# для графиковimport matplotlib.pyplot as pltimport seaborn as snsfrom IPython.display import clear_outputsns.set_color_codes()# для моделированияfrom collections import dequefrom keras.models import Sequentialfrom keras.layers import Densefrom keras.optimizers import Adamimport random # для стохастичности среды

Определяем агента

class DQLAgent():         def __init__(self, env):        # определяем параметры и гиперпараметры               self.state_size = 3 # размер входа нейронной сети        self.action_size = 6 # размер выхода нейронной сети                # эта часть для replay()        self.gamma = 0.99        self.learning_rate = 0.01                # эта часть для adaptiveEGreedy()        self.epsilon = 0.99        self.epsilon_decay = 0.99        self.epsilon_min = 0.0001                self.memory = deque(maxlen = 5000) # дек с 5000 ячейками памяти, если он переполнится - удалятся первые ячейки                # собираем модель (NN)        self.model = self.build_model()        # метод сборки нейронной сети для Deep Q Learning    def build_model(self):        model = Sequential()        model.add(Dense(10, input_dim = self.state_size, activation = 'sigmoid')) # первый скрытый слой        model.add(Dense(50, activation = 'sigmoid')) # второй слой        model.add(Dense(10, activation = 'sigmoid')) # третий слой        model.add(Dense(self.action_size, activation = 'sigmoid')) # выходной слой        model.compile(loss = 'mse', optimizer = Adam(lr = self.learning_rate))        return model        # метод для запоминания состояния    def remember(self, state, action, reward, next_state, done):        self.memory.append((state, action, reward, next_state, done))        # метод выбора действия    def act(self, state):        # если случайное число от 0 до 1 меньше epsilon        # то выбираем действие случайно (exploration)        if random.uniform(0,1) <= self.epsilon:            return random.choice(range(6))        else:            # иначе нейронная сеть предсказывает следующее действие на основе текущего состояния            act_values = self.model.predict(state)            return np.argmax(act_values[0])                    # метод для тренировки нейронной сети    def replay(self, batch_size):                # выходим из метода, если еще на накопили достаточно опыта в памяти        if len(self.memory) < batch_size:            return                minibatch = random.sample(self.memory, batch_size) # берем batch_size примеров рандомно из памяти        # обучаемся на каждой записи батча        for state, action, reward, next_state, done in minibatch:            if done: # если эпизод закончен - тогда у нас есть только награда                target = reward            else:                # иначе таргет формируем с помощью следующего состояния                target = reward + self.gamma * np.amax(self.model.predict(next_state)[0])                 # target = R(s,a) + gamma * max Q`(s`,a`)                # target (max Q` value) это выход из нейронной сети, которая принимает s` на вход            train_target = self.model.predict(state) # s --> NN --> Q(s,a) = train_target            train_target[0][action] = target            self.model.fit(state, train_target, verbose = 0)        # метод для уменьшения exploration rate,    # то есть epsilon    def adaptiveEGreedy(self):        if self.epsilon > self.epsilon_min:            self.epsilon *= self.epsilon_decay

Тренируем агента

# инициализация gym среды и агентаenv = gym.make('shops-v0')agent = DQLAgent(env)# устанавливаем параметры тренировкиbatch_size = 100episodes = 1000# начинаем тренировкуprogress_bar = tqdm(range(episodes), position=0, leave=True)for e in progress_bar:    # инициализируем среду    state = env.reset()    state = np.reshape(state, [1, 3])    # запоминаем текущий день симуляции, id выбранных действий и сумму наград за эпизод    time = 0    taken_actions = []    sum_rewards = 0    # симулируем эпизод среды    while True:        # выбираем действие        action = agent.act(state)        # запоминаем действие        taken_actions.append(action)        # выполняем шаг агентом в среде        next_state, reward, done, _ = env.step(action)        next_state = np.reshape(next_state, [1, 3])        # добавляем полученную награду к остальным        sum_rewards += reward        # запоминаем результат шага        agent.remember(state, action, reward, next_state, done)        # переходим к следующему состоянию        state = next_state        # выполняем replay        agent.replay(batch_size)        # обновляем epsilon        agent.adaptiveEGreedy()        # инкрементируем счетчик времени        time += 1        # выводим прогресс тренировки        progress_bar.set_postfix_str(s='mean reward: {}, time: {}, epsilon: {}'.format(round(sum_rewards/time, 3), time, round(agent.epsilon, 3)), refresh=True)        # проверяем не завершился ли эпизод        if done:            # выводим распределение выбранных действий в течении эпизода            clear_output(wait=True)            sns.distplot(taken_actions, color="y")            plt.title('Episode: ' + str(e))            plt.xlabel('Action number')            plt.ylabel('Occurrence in %')            plt.show()            break

Тестируем агента

import timetrained_model = agent  # теперь мы имеем натренированного агентаstate = env.reset()  # перезапускаем средуstate = np.reshape(state, [1,3])# следим за основными параметрами в течении тестового эпизодаtime_t = 0MAX_EPISOD_LENGTH = 1000  # для прогресс бараtaken_actions = []mean_reward = 0# симулируем тестовый эпизодprogress_bar = tqdm(range(MAX_EPISOD_LENGTH), position=0, leave=True)for time_t in progress_bar:    # выполняем шаг агентом в среде    action = trained_model.act(state)    next_state, reward, done, _ = env.step(action)    next_state = np.reshape(next_state, [1,3])    state = next_state    taken_actions.append(action)    # выводим результат шага    clear_output(wait=True)    env.render()    progress_bar.set_postfix_str(s='time: {}'.format(time_t), refresh=True)    print('Reward:', round(env.reward, 3))    time.sleep(0.5)    mean_reward += env.reward    if done:        break# выводим распределение выбранных действийsns.distplot(taken_actions, color='y')plt.title('Test episode - mean reward: ' + str(round(mean_reward/(time_t+1), 3)))plt.xlabel('Action number')plt.ylabel('Occurrence in %')plt.show()

Итого

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

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

Источники

Подробнее..

Категории: Python , Искусственный интеллект , Машинное обучение , Machine learning , Обучение с подкреплением , Reinforcement learning

Головоломка для ИИ

20.10.2020 00:16:52 |

Автор: admin

Как я учил агента собирать клетку 2048 в игре 2048

ИИ собирает клетку 2048

Привет! Меня зовут Ринат Максутов, я работаю в подразделении Intelligent Engineering Services департамента Technology российского офиса компании Accenture, и веду проекты по заказной разработке. За свою многолетнюю карьеру в Аксенчере я попробовал много разных областей: мобильная разработка, фронт-энд, бэк-энд и даже дата саенс с машлерном. Однако мой рассказ будет не про работу, а про хобби. Мне очень нравится учиться и исследовать новые области на собственных pet-проектах. Сегодня я расскажу об одном из них - как я учил Reinforcement learning (RL) агента играть в известную головоломку 2048. В статье намеренно не будет кода, математики, state-of-the-art подходов и новейших открытий в области, поэтому люди, хорошо знакомые с RL, ничего нового для себя не откроют. Эта статья - рассказ для широкой публики о том, как я поставил себе необычную цель и достиг ее.

Наша компания инвестирует значительные средства в постоянное обучение сотрудников. Например, в прошлом году была запущена программа, по которой сотрудники могут бесплатно пройти один из Nanodegree на Udacity (Nanodegree - набор из нескольких курсов с финальным проектом). Я уже проходил Deep Learning Nanodegree на этой платформе, поэтому в этот раз решил выбрать курс по обучению с подкреплением.

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

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

Чтобы закрыть этот пробел, я попытался решить какую-то задачу, которая раньше никем не решалась (по крайней мере, с помощью RL), и на ней изучить различные аспекты построения сред для агентов. В качестве такой задачи была выбрана простая в плане механики игра-головоломка 2048 (поиграть в браузере можно здесь: https://play2048.co/). В этой игре игроку, сдвигая клетки в одном из четырех направлений (вверх, вниз, вправо, влево), нужно объединять клетки с одинаковым значением, и попытаться собрать клетку с максимально возможным значением. Когда вы совершаете сдвиг, на случайной свободной клетке появляется новая двойка (с вероятностью 0.9) или четверка (с вероятностью 0.1). Игра заканчивается, когда на поле не останется пустых клеток, и игрок не может объединить никакие клетки.

Несмотря на название, 2048 не является максимально возможным значением клетки в игре. При должной тренировке, можно собрать клетки и 4096, и 8192, и так далее. Максимальное теоретически возможное - 131 072, то есть 2^17:

Источник: Wikipedia

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

Почему эта стратегия не гарантирует победу?

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

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

Небольшое введение в Reinforcement learning

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

Источник: https://medium.com/@dgquintero02/how-to-explain-machine-learning-to-your-family-77a3bac3593a

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

На Udacity есть интересный аналог с дрессировкой щенка. Вы даете ему команду, и поначалу он не понимает, что вы от него хотите. Он начинает совершать случайные действия в ответ на ваши команды: лаять, подпрыгивать, ложиться на спину, бегать. В тот момент, когда он случайно выбирает правильное действие, вы даете ему вкусняшку. Собака понимает, что скорее всего, вы хотите чтобы по этой команде она выполняла именно это действие. Так повторяется несколько раз - команда - действие - вкусняшка, после чего собака убеждается в правильности выбранного действия.

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

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

Дело в том, что традиционно машинное обучение используется для автоматизации задач, которые: 1) сложно алгоритмизируются, 2) легко выполняются достаточно обученным человеком, но 3) требуют от человека значительного времени на выполнение задачи. Например, в задачах распознавания образов человек может легко определить, есть на ней искомый объект или нет, но очень сложно написать достаточно надежный и более-менее универсальный алгоритм определения объекта, и при этом для большого количества изображений человек будет делать эту работу очень долго. Или, например, выявление мошенничества: тренированный человек по последовательности транзакций сможет выявить подозрительные операции, но их поиск и анализ будут занимать колоссальное количество времени, и эту задачу также сложно описать универсально заранее заданными наборами правил.

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

Грабли и велосипеды

Очередной мем с Боромиром

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

Поначалу все казалось довольно просто: берем готовый код, реализующий Deep Q-network из моих домашних заданий на Udacity, немного адаптируем под собственную среду, и все получится. Наивно.

Чтобы вы понимали, на что были потрачены 3 месяца экспериментов (если ничего не понятно, можно просто удивиться количеству буллитов и проскроллить дальше):

Область	Лучший вариант	Пробовал
Состояние среды	One-hot encoded вектор (16 клеток * 18 возможных состояний каждой)	Вектор со значениями клеток как есть Вектор с Log2 значениями клеток Матрица 4 на 4 для сверточной сети
Награда	Сумма log2 значений схлопнувшихся клеток на доске на текущем шаге минус штраф за сдвиг клетки и штраф за некорректный ход	Сумма значений клеток на доске Сумма значений схлопнувшихся клеток за все время Сумма log2 значений схлопнувшихся клеток за все время
Обучение	10 итераций обучения после каждой сыгранной партии, батчи размером 1024, начальный : 0.05, фактор уменьшения : 0.9999,	1, 3, 5, 20 итераций обучения после каждой сыгранной партии Различные значения (фактор рандомизации действий) от 1.0 до 0.01
Накопление и использование опыта	Буфер на 100 000 последних действий Случайное сэмплирование опыта (без приоритезации)	Буфер на 50 000 и 200 000 Приоритезация опыта по сумме на доске, максимальной клетке, величине ошибки, награды, в т.ч. сбалансированное по распределению действий
Помощь в обучении (читерство)	Никакое	Доигрывание с середины: каждые N эпизодов запускать агента в среду со случайно сгенерированными большими клетками, чтобы познакомить его со значениями, до которых он раньше не добирался сам Параллельные реальности: помимо одного выбранного шага рассчитываются и сохраняются в историю остальные 3 возможных шага, чтобы в обучении было больше сравнимых примеров
Что максимизировали	Дисконтированную награду на 2 шага вперед	Счет на следующем шаге Дисконтированный счет на всех последующих шагах Награду на следующем шаге
Нейронная сеть	5-слойная: 288-3х1024-4, активация ReLU и Adam optimizer	2, 4 скрытых слоя Другие оптимизаторы и активации 256, 512 нейронов в скрытых слоях Различные значения learning rate Сверточная сеть

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

Первое, с чем пришлось столкнуться - отсутствие прогресса в обучении агента ВООБЩЕ. И связано это было с тем, что именно агенту выдавала среда.

Среда для агента

Написать логику доски для игры оказалось довольно просто, и заняло пару часов. Несколько простых трюков с матрицами - и движок готов. Он производит схлопывание и сдвиг клеток в зависимости от выбранного действия, заполнение новой клетки и подсчет очков. Текущее состояние среды, таким образом, описывалось простой матрицей 4х4, где в каждой ячейке было значение соответствующей клетки. Поскольку я использовал обычную нейросеть из fully-connected слоев, то прежде чем отправить состояние среды в нейросеть, ее нужно было трансформировать в вектор 1х16:

И здесь меня поджидала первая проблема. Качество обучения переставало расти, когда агент добирался до клетки 512. Больше нее он не мог собрать, сколько бы я его ни обучал. Проблема здесь оказалась в значениях клеток, которые имеют колоссальный разброс: от 0 до сотни тысяч. Пусть меня простят специалисты, но далее будет очень вольное объяснение причины такого поведения: я намеренно упрощаю, чтобы была понятна общая идея.

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

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

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

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

И для агента значение имело бы только то, что a+a = b, b+b=c и т.д., а не то, какие значения скрываются за a, b и с. (+ в данном случае - не сложение, а то самое схлопывание). К чему это все? К тому, что значения клеток можно рассматривать не как числовые значения, а как категориальные. И поскольку мы знаем максимально возможное значение клетки, можно каждую клетку представить в виде one-hot encoded вектора. То есть для каждой клетки использовалось не ее значение, а вектор размерности 18, у которого все значения были нули, и только одно значение, позиция которого соответствует одному из наших возможных значений, равнялось единице. И таких векторов - по количеству клеток. Мне до сих пор не ясно, почему, но именно такое, а не числовое представление, помогло агенту гораздо быстрее достигать более высоких значений.

Награда

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

Возьмем очень простую игру, например, Space Invaders. На ней несколько лет назад Google тренировал своих агентов.

Space Invaders.

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

В 2048 такой подход не сработает. И вот почему. Допустим, у вас есть 2 клетки с одинаковыми значениями, стоящие рядом. Вы их схлопываете, и счет на доске не изменился. Потому что их значения по отдельности равняется значению новой клетки. То есть совершив правильное действие, агент не получит позитивного подкрепления и не узнает, что делать нужно именно так. Более того, после каждого действия заполняется новая случайная клетка, как я писал выше, значением 2 или 4. То есть какое бы действие ни совершил агент, он всегда будет получать в ответ значение, которое равняется [счет до шага + 2 или 4]. Очевидно, этой информации недостаточно, чтобы понимать, насколько хорошее действие агент выбрал. И именно из-за этого обучение практически не прогрессировало.

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

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

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

Штрафы

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

Распределение долей выбранных направлений ходов в каждой из игр.

На картинке видим, как постепенно менялась стратегия в правильную сторону: в первых играх направления сдвигов выбирались равномерно, но затем появились приоритетные - вправо и вниз.

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

Результат

The WOW signal

Зеленый график показывает максимальное значение клетки в каждой игре. Выброс - в одной из игр максимально полученное значение клетки - 2048.

Для того, чтобы собрать клетку 2048 агенту пришлось отыграть чуть больше 60 тысяч партий. Однако важная деталь в том, что однократное достижение еще не означает, что агент научился делать это стабильно. Посмотрите на начало зеленого графика, где видно, как агент учился доходить до клетки 1024. Сначала был такой же выброс, затем 1024 появлялось все чаще и чаще, и затем где-то после 30 тысяч игр агент уже довольно уверенно доходил до 1024. То есть если говорить о том, чтобы агент действительно научился собирать 2048, то, экстраполировав закономерность, можно прикинуть, что агенту потребуется более миллиона игр, чтобы закрепить этот навык, и устремиться к следующей цели - 4096.

Вы наверное уже устали читать, поэтому больше не буду грузить другими выкрутасами, которые я пробовал. Вместо этого вот вам 20-минутный видосик, где собирается клетка 2048 (начиная с отметки 16:40).

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

PS: Пользуясь случаем, нам в команду сейчас очень нужны back-end разработчики на Python и Java, и front-end на React. В Москве, Твери или Ростове-на-Дону. Также с удовольствием приглашу пообщаться людей, которые любят исследовать технологии, делать proof-of-concept и искать им применения в бизнесе. Откликайтесь на наши вакансии или, если не нашли подходящей, пишите в личку!

Подробнее..

Категории: Python , Искусственный интеллект , Машинное обучение , Обучение с подкреплением , Блог компании accenture

Кластерный анализ каждому

19.01.2021 20:18:31 |

Автор: admin

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

Источник изображения: commons.wikimedia.org

Почему это круто

Кластерный анализ неформально можно определить как разбиение множества объектов так, чтобы похожие объекты попали в одно и то же подмножество, а объекты из разных подмножеств существенно различались. От обычной классификации по заданным признакам кластерный анализ отличается тем, что не алгоритм, а человек выявляет критерий кластеризации данных. Эта задача относится к классу обучения без учителя (англ. unsupervised learning), так как размеченного набора данных или какой-то заведомо известной информации о нём не предоставляется.

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

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

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

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

Как определить меру качества

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

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

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

Сравниваем разбиения

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

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

Сравниваем меры качества

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

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

Критерий ранжирования нормированная функция расстояния между ранжированием разбиений, задаваемым мерой качества, и агрегированным ранжированием разбиений, задаваемым оценками на основе визуального восприятия. Область значения данной функции: [0, 1]; чем значение функции ближе к , тем рассматриваемая мера качества лучше.

Для наглядности давайте рассмотрим пример с собранным мною набором данных из двухсот двумерных наборов данных 2D-200. Для каждого набора данных из 2D-200 были сформированы 14 разбиений. Эти разбиения были оценены пятью асессорами и девятнадцатью мерами качества. В итоге на наборе данных 2D-200 выявлены лучшие меры качества с точки зрения критериев Adq иЗатем для каждой меры по всем элементам из 2D-200 были вычислены следующие величины:

$BestCVI_{Adq}$ соотношение числа раз, когда мера отвечала критерию адекватности Adq к общему числу экспериментов;

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

Значения $BestCVI_{Adq}$ и для всех мер качества на наборе данных наборов данных 2D-200 представлены в таблице ниже.

Мера	$BestCVI_{Adq}$	Мера	$BestCVI_{Adq}$
DB		Sym
Dunn		CI
Silhouette		DB*
CH		gD31
S_Dbw		gD41
SymDB		gD51
CS		gD33
COP		gD43
SV		gD53
OS

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

Однако эффективная рекомендация из девятнадцати мер качества требует значительно большего числа наборов данных, чем представлено в 2D-200. Поэтому я построил множество из четырех самых лучших мер с точки зрения AvgCVI_R среднего значения, вычисляемого на основе критерия ранжирования мер: мера Silhouette, мера Calinski-Harabasz, мера gD41 и мера OS. В таблице приведены значения для всех исследованных мной внутренних мер качества.

Мера		Мера
*gD41*	$\mathbf{0,312}$	gD53
gD43		S_Dbw
gD33		Dunn
OS	$\mathbf{0,342}$	gD51
CH	$\mathbf{0,369}$	CI
*Silhouette*	$\mathbf{0,370}$	CS
SV		DB
Sym		COP
gD31		DB*
SymDB

Классификатор, который рекомендует меру качества

Всякий раз производить данные вычисления довольно ресурсозатратно. Можно упростить задачу рекомендации меры качества, если свести её к задаче классификации. И я решил построить классификатор, который для нового набора данных предсказывает, какая из рассматриваемых мер качества будет лучше с точки зрения агрегированных оценок асессоров, если бы они действительно проходили описанный выше тест для этого набора данных. В качестве классификатора я использовал алгоритм случайного леса, который выбрал экспериментально, и который показывает качество классификации Интересно, что разработанный мета-классификатор сам по себе выступает новой мерой качества, назовём её Meta-CVI.

Как подобрать алгоритм

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

Эвристические алгоритмы

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

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

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

Давайте формализуем задачу. Пусть задан некоторый временной бюджет на поиск лучшего алгоритма Требуется разбить его на интервалы T = t_1 + t_2 + . . . + t_m таким образом, что при запуске процессов $\pi_j$ с ограничением по времени t_i получается значение меры качества такое, что:

$Q(A_{\lambda_j}^{j}) \xrightarrow{(t_1, t_2, \ldots, t_m)} \min_j,$

где $A^j \in A, \lambda = \pi(t_i, A^j, \emptyset),$ и $t_1 + \ldots + t_m = T, t_i \geq 0 \: \forall i.$

В этом случае каждой ручке бандита соответствует определённая модель алгоритма кластеризации из конечного множества вызову ручки на итерации процесс оптимизации гиперпараметров этой модели в течение времени В результате будет достигнуто качество кластеризации $Q(A_{\lambda_i}^{i}, D).$

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

Иллюстрация работы метода выбора и настройки эвристического алгоритма MASSCAH представлена на рисунке ниже:

Эволюционные алгоритмы

Одним из ключевых аспектов работы эволюционных алгоритмов является вычисление функции приспособленности. В нашем случае это внутренняя мера оценки разбиения. Важно научиться быстро её перерасчитывать, если структура кластеров изменилась. Переформулировать задачу можно так: пусть точка $x_{id}$ переместилась из кластера C_a в кластер C_b.

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

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

Мера	Полный пересчёт	Инкрементальный пересчёт	Точность пересчёта
Dunn	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	точный пересчёт
CH	$\mathcal{O}(n^2 \log(n))$	$\mathcal{O}(n)$	аппроксимация
CI	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
DB	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
Sil	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	точный пересчёт
gD31	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	точный пересчёт
gD33	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD41	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD43	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD51	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
gD53	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
CS	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
DB*	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация
Sym	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
SymDB	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
COP	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
SV	$\mathcal{O}(n^2)$	$\mathcal{O}(n)$	аппроксимация
OS	$\mathcal{O}(n^2 \log(n))$	$\mathcal{O}(n)$	аппроксимация
S_Dbw	$\mathcal{O}(n \log(n))$	$\mathcal{O}(n)$	аппроксимация

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

Эволюционный алгоритм кластеризации (1+1).

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

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

Calinski-Harabasz		OS		gD41		Silhouette
хуже	не хуже	хуже	не хуже	хуже	не хуже	хуже	не хуже

Сравнение алгоритмов

Интересно сравнить алгоритм на основе выбора и настройки эвристических алгоритмов кластеризации MASSCAH с алгоритмом настройки эволюционного (1+1) алгоритма кластеризации.

Я предположил, что два алгоритма получают одинаковые значения меры качества, если интервалы этих значений [ - , + ] пересекаются. То есть была использована квантиль уровня $84,13\%$ для нормального распределения. Временной бюджет алгоритма, запускаемого на определённых мере и наборе данных, задавался равным среднему времени работы автоматизированного эволюционного алгоритма на этих мере и наборе данных. Я запустил алгоритмы со всеми отобранными ранее четырьмя мерами качества: Silhouette, Calinski-Harabasz, gD41 и OS. Для каждой пары мера набор данных производилось 10 запусков алгоритма. Полученные количества удачных и неудачных запусков приведены в таблице ниже.

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

		$MASSCAH \approx Evo$
Мера CH
Мера OS
Мера Silhouette
Мера gD41
Все меры
Мера Meta-CVI

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

Как применить всё это на практике

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

Схема описания работы программного комплекса.

Этот программный комплекс состоит из нескольких пакетов. Пакет CVI_Predictor реализует алгоритм предсказания меры для конкретной задачи кластеризации на основе мета-обучения. Пакет RL_Clustering реализует различные алгоритмы на базе представленного в работе метода выбора и настройки эвристического алгоритма кластеризации. Пакет Evo_Clustering реализует эволюционный алгоритм кластеризации с параметрами, настраиваемыми при помощи мета-обучения. Пакет Incremental_CVI реализует инкрементальное вычисление мер качества разбиений. Весь комплекс можно скачать на GitHub.

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

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

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

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

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

Подробнее..

Категории: Блог компании университет итмо , Университет итмо , Машинное обучение , Обучение с подкреплением , Кластеризация , Кластеризация данных , Кластерный анализ , Эволюционные алгоритмы , Мета-обучение

World Models обучение в воображении

12.09.2020 08:21:14 |

Автор: admin

Обучение с подкреплением (Reinforcement Learning) плохо, а точнее, совсем не работает с высокими размерностями. А также сталкивается с проблемой, что физические симуляторы довольно медленные. Поэтому в последнее время стал популярен способ обойти эти ограничения с помощью обучения отдельной нейросети, которая имитирует физический движок. Получается что-то вроде аналога воображения, в котором и происходит дальнейшее основное обучение.

Давайте посмотрим, какой прогресс достигнут в этой сфере и рассмотрим основные архитектуры.

Идея использовать нейросеть вместо физического симулятора не нова, так как простые симуляторы вроде MuJoCo или Bullet на современных CPU способны выдавать от силы 100-200 FPS (а чаще на уровне 60), а запуск нейросетевого симулятора в параллельных батчах легко выдает 2000-10000 FPS при сравнимом качестве. Правда, на небольших горизонтах в 10-100 шагов, но для обучения с подкреплением этого часто бывает достаточно.

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

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

А уже к этой уменьшенной размерности Z можно применить любой классический алгоритм Reinforcement Learning. С маленькой размерностью он, возможно, уже будет способен справиться (ну да, ну да, надежда умирает последней). Кроме того, это также ускоряет расчеты.

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

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

World Models

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

Она собрала в себя ставшие теперь классическими элементы обучения в воображении: автоэнкодер для обучения нейросети-симулятора и обучение "мозгов" в получившемся воображении, причем в уменьшенной размерности Z. Все это работало достаточно быстро и показало отличный результат (по тем временам).

В качестве автоэнкодера бесхитростно использовался классический VAE:

Важный нюанс, результат автоэнкодера VAE дальше пропускался через рекуррентную нейросеть (разновидность MDN-RNN), чтобы отслеживать динамику. Так как VAE работает только с одиночными статичными картинками, а для динамичных задач нужно понимать движение. Обратите внимание, что RNN предсказывает сразу сжатое представление Z для следующего шага. Это пригодится в следующих усовершенствованиях этого алгоритма.

В итоге общая схема алгоритма получилась такой:

Здесь много стрелок, но суть очень простая: VAE(V) автоэнкодер выучивает модель мира и передает свое среднее значение с уменьшенной размерностью Z в нейросеть MDN-RNN(M) для отслеживания движения. Та выдает тоже сжатое Z, но уже для следующего шага в симуляции. Это позволяет этой рекуррентной нейросети MDN-RNN делать прогноз на несколько шагов вперед, передавая свой прогноз Z себе же на вход, и так несколько раз подряд.

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

В итоге получается, что основное обучение происходит в "воображении" (см. схему) по циклу между MDN-RNN и С (Controller основной "мозг", принимающий решения). Но если посмотрите на схему, то видно что из контроллера С, стрелка также возвращается в environment. Это значит, что время от времени обученный контроллер C взимодействует не только со своим воображением, но и с реальным симулятором. Чтобы пополнить базу автоэнкодера VAE(V).

Что за Controller , спросите вы? И правильно сделаете! В этой работе нейросети использовались только для создания механизма воображения, а решения принимала не отдельная нейросеть-"мозг", а именно этот Controller. Это штука, обученная на прогнозах рекуррентной нейросети обычным эволюционным алгоритмом. Точнее, более эффективной его разновидностью CMA-ES. У них это сработало, потому что уменьшенная размерность Z была настолько мала, что классический эволюционный алгоритм с ней справился. Подключать нейросети для обучения с подкреплением даже не понадобилось. Так что к нейросетевому обучению с подкреплением эта работа, ставшая родоначальником целого направления, строго говоря, отношения вообще не имеет.

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

PlaNet

Следующим значимым шагом стало появление алгоритма PlaNet. Обучение в воображении уже использовали все кому не лень (заменив, разумеется, Controller на полноценную нейросеть с настоящими алгоритмами из reinforcement learning), но PlaNet сумел применить этот подход к Model-Based обучению.

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

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

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

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

К сожалению, в реальных задачах такая система быстро вырождалась. Потому что генерировать картинки сложно и дорого. А небольшие случайные отклонения в пикселях уводили все это в разнос. Горизонт планирования на основе генерации картинок (т.е. полного state, если говорить в терминах Reinforcement Learning) заключался в единицах или, в лучшем случае, паре десятков шагов вперед. Для Model-Based это мало.

PlaNet, как World Models до этого, начал генерировать воображаемые последовательности не в виде картинок, а в виде сжатого состояния Z (здесь на схеме они обозначаются как S state).

При этом из каждого Z (простите, теперь S) с помощью декодера все еще можно, при желании, восстановить картинку. Но важно, что нейросеть-симулятор строит траектории именно в сжатом состоянии.

Это позволяет в сжатых состояниях S (все, прощай Z) сохранять только важные абстрактные вещи для решения задачи. Например, скорости объектов, их положение и так далее. А в картинках все это хранилось в шумных пикселях, из которых приходилось потом выдирать обратно.

Хранение в S только важной информации для решения задачи позволило строить прогнозы не на десяток шагов вперед, а на сотни и даже тысячи. Что резко улучшило качество Model-Based прогонов в нейросетевом симуляторе (то есть в "воображении"). Да и маленькая размерность тоже помогает.

Обратите внимание на схеме выше, что на каждом промежуточном шаге в модель, т.е. на вход нейросети-"воображения", добавляется случайное действие A. Здесь все как в обычном Model-Based прогоняем через симулятор случайные действия и выбираем лучший вариант. Отличие в том, что каждый промежуточный state S это сжатое представление. Поэтому чтобы получить из него награду R для расчета суммарной награды, из этого скрытого state S нужно предсказать награду, что делается отдельной небольшой нейросетью (синий прямоугольник на схеме). А вот генерировать из каждого промежуточного шага картинку декодером, что очень трудоемко в вычислительном плане, при работе совсем не нужно! (это делалось только при обучении автоэнкодера). Классическое Model-Based планирование, т.е. прогон случайных действий через симулятор и выбор лучшего, делается полностью в сжатых состояниях, лишь с небольшой помощью нейросети, получающей из S награду R. Это тоже значительно ускоряет расчеты по сравнению с предыдущими подходами, которые использовали идею World Models, но для генерации целых картинок.

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

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

Dreamer

Дальнейшим развитием PlaNet стала архитектура Dreamer. Являющаяся сейчас фактически последним словом в этой области.

Как и PlaNet, Dreamer делает прогнозы в сжатом состоянии S, содержащем важные для решения задачи сведения, и может делать эффективные прогнозы на тысячи шагов вперед. Но преимуществом Dreamer является использование Value нейросети, используемой для предсказания награды за пределами горизонта планирования. Эта сеть почти целиком взята из обычного Reinforcement Learning. На основе большой статистики взаимодействия со средой она учится предсказывать насколько хороша текущая ситуация. Можно ли из нее хотя бы потенциально получить в далеком будущем награду, даже если текущий горизонт планирования не показывает хорошей награды. В обычных Model-Based алгоритмах (и в предыдущем PlaNet) суммарная награда рассчитывается исключительно в пределах горизонта планирования.

Но что еще важнее, вместо прогона и проверки через симулятор случайных действий, для выбора какие действия надо проверять Dreamer использует Actor нейросеть, выдающую сразу оптимальные действия. Это очень близко к концепциям в Model-Free обучении с подкреплением, например в архитектуре actor-critic.

Но в отличие от actor-critic архитектур в Model-Free подходах, где actor учится выдавать оптимальные действия по градиенту, с которым critic предсказывает награду (или value, или advantage), в Dreamer actor нейросеть учится оптимальным действиям через обратное распространение градиента награды через всю последовательность сжатых представлений. Что невозможно для Model-Free подходов.

Это позволяет Dreamer'у понимать, как маленькие изменения действий отразятся на награде в будущем. И эффективно дообучать свою Actor нейросеть, чтобы выдаваемые ею действия вели к максимальному увеличению награды на каждом шаге (см. анимацию ниже). Совместно с Value нейросетью, заглядывающей за горизонт планирования, так как value и reward обе распространяются назад по последовательности.

По большому счету, Dreamer не является Model-Based подходом. Это скорее гибрид с Model-Free. Потому что технологию model-based с последовательностью предсказаний (в воображении, а не на реальном симуляторе) этот метод использует только для эффективного обучения Actor нейросети. А так Dreamer при работе сразу предсказывает оптимальные действия. Вместо долгого поиска, как делал PlaNet и все остальные Model-Based методы.

Благодаря этой комбинации, Dreamer обучается в 20 раз быстрее, чем другие методы, и при этом по качеству равен или превосходит лучшие Model-Free методы. Точнее, Dreamer требует в 20 раз меньше взаимодействий со средой, а по чистому времени обучения (без учета времени работы физического симулятора) примерно в два раза быстрее.

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

Plan2Explore

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

Что если можно было бы изучить мир, причем как-нибудь более эффективно, чем просто случайно блуждая по нему. А потом, когда потребуется выполнить какую-то задачу, можно было в своем воображении представить эту последовательность и обучиться чисто в воображении, не взаимодействия снова со средой. Ведь это позволило бы, после изучения мира, выполнять практически любые задачи! Работа Plan2Explore отвечает именно на эти вопросы.

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

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

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

Работа Plan2Explore состоит из двух частей: сначала исследуется мир, используя обучение в воображении для планирования куда двигаться. А после изучения мира, когда нужно выполнить какую-то конкретную задачу, обучение этой задаче тоже делается полностью в воображении. Используя обученную модель мира и не взаимодействуя больше со средой. Ведь все возможные типы взаимодействия были изучены в период исследования мира. Это zero-shot вариант обучения новым задачам. А если все же немного повзаимодействовать (совместно с обучением в воображении, см. как это было в World Models в самом начале статьи), то получается несколько улучшенный few-shot вариант.

Plan2Explore показывает качество, сравнимое с Dreamer и Model-Free методами, но при этом может использовать одну обученную модель мира в период исследования, чтобы выполнять разные действия. Для этого требуется лишь минимальное и очень быстрое дообучение в воображении, не взаимодействуя с реальной средой.

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

Подробнее..

Категории: Искусственный интеллект , Обучение с подкреплением , Reinforcement learning , World models

Как мы управляли поездами на соревновании NeurIPS 2020 Flatland

15.01.2021 12:16:15 |

Автор: admin

Всем привет! Мы команда из Питерской Вышки, и в этом году мы заняли первое место в RL треке соревнования NeurIPS 2020: Flatland. Цель Flatland разработать алгоритм, способный как можно лучше управлять трафиком движения поездов по сети железных дорог, при этом система должна принимать решения за ограниченное время.

О том, что это за соревнование и как нам удалось в нем победить (а на контест прислали большее 2000 решений из 51 страны) читайте под катом.

Наша команда

В команде JBR_HSE было пять участников: Константин Махнев (учится на 4-м курсе бакалаврской программы Прикладная математика и информатика) Олег Свидченко и Владимир Егоров (оба учатся в магистратуре Программирование и анализ данных), аспирант Дмитрий Иванов и заведующий Центром анализа данных и машинного обучения НИУ ВШЭ Санкт-Петербург Алексей Шпильман. Все, кроме Константина, также работают в лаборатории Агентных систем и обучения с подкреплением JetBrains Research отсюда и название команды. Во время участия в соревновании Костя стажировался в этой же лаборатории.

NeurIPS 2020: Flatland что это?

Flatland это соревнование, которое проходило с 10 июля по 15 ноября на основе платформы AIcrowd и при поддержке известной международной конференции NeurIPS. Цель соревнования разработать алгоритм, способный как можно лучше управлять железнодорожным трафиком. Важным ограничением было то, что решения нужно принимать за ограниченное время (5 секунд на один шаг симулятора), что не позволяло просто подбирать оптимальные действия.

В NeurIPS 2020: Flatland было два направления: общее и Reinforcement Learning (RL). Первое направление было открыто для любых решений, а второе только для тех, которые используют обучение с подкреплением.

Организаторы предоставили участникам симулятор Flatland, который представляет собой двумерную сетку, где каждая клетка имеет свой тип: дорога, поворот, развилка или непроходимая местность. Каждый поезд занимает ровно одну клетку на сетке и имеет направление, по которому он сейчас перемещается. Симуляция происходит пошагово, на каждом шаге для каждого поезда нужно определить, какое действие ему совершить: остановиться, ехать по самому левому пути или ехать по самому правому пути. Поскольку в текущей реализации полного перекрестка не предусмотрено, т.е. не бывает так, что можно поехать одновременно вперед, направо и налево, то и действие ехать вперед тоже не нужно. В случае, когда никаких поворотов нет, второе и третье действие эквивалентны. Поезда могут сталкиваться между собой получается deadlock. Задача соревнования заставить все поезда как можно быстрее доехать до их пунктов назначения. Решения оцениваются по сумме времени, которое потратили поезда на достижение цели. В случае, если поезд не доехал, его время равно максимальному времени симуляции.

Решение: как агент будет взаимодействовать с симулятором

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

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

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

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

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

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

Осталось определить только функцию награды для агента. После некоторого подбора, мы остановились на довольно простой: $0.01 \cdot \Delta d 5 \cdot \text{is\_deadlocked} + 10 \cdot \text{is\_succeed}$, т.е. награда отражает то, насколько изменилось расстояние $d$ до пункта назначения после принятия решения, с дополнительными наградой в случае успешного завершения эпизода и наказанием в случае попадания в дедлок.

Алгоритм PPO

Существует множество алгоритмов обучения с подкреплением, которые разработаны для решения мультиагентных задач. Однако в качестве baseline алгоритма мы решили использовать алгоритм PPO Proximal Policy Optimization, поскольку его код можно было бы переиспользовать для реализации алгоритмов multiagent RL (например, COMA). Позже, правда, оказалось, что PPO (с некоторыми модификациями) сам по себе решает задачу неплохо, а вот мультиагентные методы обучаются значительно хуже, поэтому PPO остался основной частью нашего финального решения.

Классический алгоритм PPO состоит из двух частей: актора и критика. Критик приближает value-function, а актор учит рандомизированную политику $\pi_\theta(a | s)$, которая максимизирует математическое ожидание суммарной награды.

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

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

Как решить, каким поездам когда стартовать?

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

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

Результаты соревнования

В результате наше решение заняло первое место в треке RL и восьмое место в общем зачете. Это значит, что на данный момент не-RL подход пока решает лучше, однако показывает, что у обучения с подкреплением есть потенциал. В нашем подходе довольно много слабых мест и нерешенных вопросов (например, серьезные проблемы с масштабируемостью на окружения большого размера), поэтому нам есть, над чем еще поработать. Сейчас мы вместе с организаторами соревнования готовим статью для отправки ее в competition book NeurIPS 2020.

Подробнее..

Категории: Машинное обучение , Machine learning , Транспорт , Учебный процесс в it , Обучение с подкреплением , Вшэ спб , Блог компании питерская вышка , Hse spb , Reinforcement learning , Соревнования по машинному обучению

	Русский
	English

Обучение с подкреплением

Обучение с подкреплением

Глубокое обучение с подкреплением

Определяем действия, награды и состояния

Создаем среду и агента

Агент играет в Змейку

Поиграем с пространством

Поиграем с наградами

Опыт

Начало

Как машина победила человека

Немного деталей

Существующие подходы

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

Музыка: onset, beats, chroma

Видео: извлечение позы человека

Архитектура DanceNet

Наше решение

Датасет

DanceNet

RL модель

Функция потерь

Модель на фазе тестирования

Результаты

Вступление

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

Кастомная среда

Главные импорты

Определяем агента

Тренируем агента

Тестируем агента

Итого

Источники

Небольшое введение в Reinforcement learning

Грабли и велосипеды

Среда для агента

Награда

Штрафы

Результат

Почему это круто

Как определить меру качества

Сравниваем разбиения

Сравниваем меры качества

Классификатор, который рекомендует меру качества

Как подобрать алгоритм

Эвристические алгоритмы

Эволюционные алгоритмы

Сравнение алгоритмов

Как применить всё это на практике

World Models

PlaNet

Dreamer

Plan2Explore

Наша команда

NeurIPS 2020: Flatland что это?

Решение: как агент будет взаимодействовать с симулятором

Алгоритм PPO

Как решить, каким поездам когда стартовать?

Результаты соревнования

Категории

Последние комментарии