21 марта 2016 в 09:47

Deep Reinforcement Learning (или за что купили DeepMind)

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

Вот, собственно, главный артефакт (если вы это видео не видели, посмотрите обязательно, оно взрывает мозг)


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

Disclaimer: пост написан на основе изрядно отредактированных логов чата closedcircles.com, отсюда и стиль изложения, и наличие уточняющих вопросов.

Seminal paper, про то как это работает — https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

Итак, быстро и на пальцах про Q-learning


Пусть мы находимся в какой-то среде, у которой есть текущее состояние s, и мы в каждый момент можем выполнить действие a из дискретного набора. Это действие переводит систему в новое состояние (стохастически, т.е. в системе есть всякое случайное) и может выдать нам reward или закончить игру.

Вводится понятие cumulative return over time — это общее количество reward, которое мы можем получить от текущего момента до конца игры, причем будущие rewards уменьшаются на y за каждый тик времени, т.е. reward в следующий момент времени — это y*r, еще через один — y2*r

Так вот, оптимальное поведение можно описать некой функцией Q*(s,a), которая возвращает одно число.
Главное понять, что оно значит!

Значит оно следующее — если мы находимся в состоянии s, и предпринимаем действие a, какой у нас будет cumulative reward до конца игры, если мы после действия a будем действовать оптимальным образом?
Если такая функция дана свыше, с ее помощью легко играть оптимально — попробуем Q*(s,a) для всех a, выберем максимальный.

Всем понятно? Пойду чай поставлю.
Ну ладно, ваши проблемы.

Далее, есть ключевое рекуррентное уравнение для этой вот воображаемой Q* функции, так называемый Bellman Equation
image
Вот такой красивый.
Что он говорит!

Он говорит, что если мы знаем, с какими вероятностями s переходит в следующее состояние s` из-за действия a
То Q* для текущего состояния s должно быть равно максимуму из выбора дальнейший действий на следующем шаге.

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

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

О, чай вскипел.

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

Ну так вот. Идея собственно простая. Давайте представим эту Q-функцию как CNN! (в смысле, convolutional neural network)
Вот прям обычный такой, с пикселями на инпутах и с количеством нейронов в аутпуте равным количеству возможных действий. Более точно — на вход сети выдаются пиксели нескольких прошлых кадров эмулятора (в оригинальной реализации — 4-х кадров), то есть сеть может отследить движущиеся объекты.
На каждом нейроне последнего слоя сети — Q(s,a) для нужного a.

Как эту сеть натренировать?


Вот есть версия сети на текущем шаге, с некоторыми весами. Произошел новый шаг, мы узнали новый переход из s в s' в результате действия a и был ли reward.
Будем вот все такие туплы (s,s',a,r) сохранять, все какие мы видели за игру.

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

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

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

У самой нейросети памяти и стейта нет вообще, вся память системы — в натренированных весах. Если угодно, мышечная такая память.
(почему надо тренировать на случайном наборе из истории, а не на последних — чтобы не случалось positive feedback loop, т.е. чтобы система не приспосабливалась к последствиям конкретного недавнего выбора, а к данным в целом)

Маленькие детали — они еще используют так называемую e-greedy policy.
На каждом шаге с вероятностью e будет сделано тупо случайное действие, а с вероятностью (1-e) предсказанное текущим эстимейтом Q-функции.
От времени e, понятно, уменьшается.

image

Вот псевдокод алгоритма.
И все. Не делают больше ничего.

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

интересно, долго ли оно учится
Десятки и сотни часов

во, а ещё расскажи про experience replay (они там общими фразами обделались, а в коде все слишком просто).
Experience replay — это их название того, что нужно запоминать все переходы состояний, которые были за время работы и тренироваться на них всех.
Да, очень круто. Они я так понимаю не особо заморачивались выбором стратегии "забывания" (у них тупо по циклу "забывает" старое по факту перезаписи его).
Угу, сколько памяти хватает, столько и помнят.

по поводу препроцессинга — я правильно понимаю что пойнт упаковки четырех (трех) изображений в "фи" — тупо экономия вычислений, а не вовсе потуги как-то работать с локальной анимацией / направлением движения и т.п.?
Они дают на вход прошлые 4 кадра истории.
Мне кажется, это таки независимо от frame skipping для экономии ресурсов, так что это дает возможность сети посмотреть на анимацию, да.

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

вооот, и наконец тупой вопрос пока мы обсуждаем входные кадры и Главную Формулу с Гамма-Дисконтом Риворда
откуда они reward-то брали?
Из игры. Тупо scores. В изначальной версии просто смотрели на знак изменения scores.

"из игры" — это из эмулятора дополнительным хаком эмулятора?
Короткий ответ на вопрос и заодно на незаданные вопросы о кадрах на экране и как нажимать кнопки — используйте готовые библиотеки типа http://www.arcadelearningenvironment.org, иначе ваше исследование в области DQN быстро остановится.
Как хорошо что мы живем в ХХ1 веке! И риворды и end-of-game сигналы экстрактятся например этим самым ALE из более чем 50 атари игр.

Тут очень интересна связь с внешним миром, мне кажется. Чтобы этот весь deep reinforcement learning происходил — должно сойтись много всего. Прежде всего, должны быть игры.

Игры — главный двигатель прогресса (и видимо порно еще)


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

Для людей, которым код нравится читать больше, чем пейперы, вот неплохая реализация — https://github.com/spragunr/deep_q_rl
Семен Козлов @sim0nsays
карма
174,7
рейтинг 7,2
Пользователь
Похожие публикации
Самое читаемое Разработка

Комментарии (15)

  • 0
    Спасибо за обзор.

    Что интересно, несмотря на некоторую принципиальную ограниченность (нейронные сети не сказать что производят интеллектуальные действия, скорее тренируют рефлексы) — нейронные сети показывают весьма сильные результаты.
    • +1
      Тут интересно с другой стороны взглянуть – такие сложные устройства, как люди, проводят часы за играми, для прохождения которых достаточно собрать простенькую нейронку из спичек и желудей.
    • +1
      Существуют НС, полные по Тьюрингу (http://arxiv.org/pdf/1410.5401v2.pdf), т.ч. они ограничены не более, чем МТ.
      • 0
        Вот неплохая статья о RNN: http://karpathy.github.io/2015/05/21/rnn-effectiveness/

        Пример случайного кода сгенерированного нейросетью из сорцов ядра линукс (чуть подправить и в продакшен!):

        /*
         * Increment the size file of the new incorrect UI_FILTER group information
         * of the size generatively.
         */
        static int indicate_policy(void)
        {
          int error;
          if (fd == MARN_EPT) {
            /*
             * The kernel blank will coeld it to userspace.
             */
            if (ss->segment < mem_total)
              unblock_graph_and_set_blocked();
            else
              ret = 1;
            goto bail;
          }
          segaddr = in_SB(in.addr);
          selector = seg / 16;
          setup_works = true;
          for (i = 0; i < blocks; i++) {
            seq = buf[i++];
            bpf = bd->bd.next + i * search;
            if (fd) {
              current = blocked;
            }
          }
          rw->name = "Getjbbregs";
          bprm_self_clearl(&iv->version);
          regs->new = blocks[(BPF_STATS << info->historidac)] | PFMR_CLOBATHINC_SECONDS << 12;
          return segtable;
        }
        • +1
          Если придумать язык сверхвысокого уровня, программы на котором будут валидны и более-менее полезны при таком почти случайном объединении кусочков кода из других программ — успех ему будет гарантирован )
          • 0
            А у меня возникала идея генерировать код для граничных условий в каких-то алгоритмах. Поскольку именно на них тратиться больше времени, а возникают они реже.
    • 0
      Да, аналогия с рефлексами — по-моему, хорошая.
  • 0
    Есть еще интересный проект MarI/O. Там совсем простая сеть, однако ее хватает чтобы пройти пару уровней в игре Super Mario.
    • 0
      Unless вы про него что-то знаете, чего нет в видео на youtube, сложность и масштаб достижений не сравнимы.
      Во-первых, в MarI/O есть код, который распознает экран в уже готовый грид объектов — стен, монстров, итд, что принципиально облегчает задачу обучения из пикселей.
      Во-вторых, Марио детерминирован, поэтому сетка в MarI/O, насколько я понимаю, учит прежде всего уровень, а не игру вообще. Если уровни делать случайно, она ничему не научится.
      Собственно, это в каком-то виде понятно, сравнив количество нодов и нейронов в нейросетях. Десятки против сотен тысяч, кажется.
    • 0
      Вот кстати DQN пытается играть в случайные уровни Марио — http://youtu.be/wfL4L_l4U9A. Видно, что он к концу часа что-то научается делать, но явно играет плохо и валится на простых для человека местах. Впрочем, всего час тренировать — неспортивно, а героев, которые тренировали сотню часов на Марио нет :(
      • +1
        Там, кстати, в последнем кадре видна диаграмма, и на ней есть слой Encoded Symbolic State S1, очень похожий на тот что в MarI/O.
        • 0
          И действительно, кругом обман :(
          Надеюсь, хоть уровни честно рандомные
  • 0
    Никто не пробовал с этой технологией бота для какой-нибудь большой игры написать?
    • +1
      Ну вот как раз эти Deepmind после недавнего успеха AlphaGo вроде сказали, что следующим шагом может быть создание бота для старкрафта
    • +1
      Чем игра сложнее, тем хуже все это работает. Для игры должно быть достаточно исключительно состояния экрана и она должна играться на рефлексах.
      Но вот новая версия алгоритма уже в 3d что-то делает: https://www.newscientist.com/article/2076552-google-deepmind-ai-navigates-a-doom-like-3d-maze-just-by-looking/

      Это замечательно, что у нас столько прекрасных тренажеров есть :)

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