Концептуальное и понятное объяснение

Фон

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

Очарованный документальным фильмом, в котором лишь кратко затрагивается наука, стоящая за AlphaGo, я обратился к исследовательским работам¹ ², опубликованным DeepMind, чтобы понять методы машинного обучения, используемые для разработки AlphaGo (а также AlphaGo Zero, версии AlphaGo с более высокой производительностью). Исследовательские статьи были хорошо написаны, но, возможно, были слишком техническими для человека, не знакомого с глубоким обучением с подкреплением и поиском по дереву Монте-Карло. Тем не менее, это не должно мешать кому-либо понять интересные концепции и наблюдения, представленные в этих статьях, поскольку широко признано, что AlphaGo и AlphaGo Zero представляют собой новаторские приложения для машинного обучения.

Эта статья написана с целью объяснить науку, лежащую в основе AlphaGo и AlphaGo Zero, на языке, понятном людям, которым интересно понять, как они научились играть в игру го на сверхчеловеческом уровне, но их может отпугнуть такая терминология, как подкрепление. Обучение или поиск по дереву Монте-Карло.

Простое правило игры, сложный игровой процесс

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

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

Математически это количество возможных последовательностей ходов («пространство поиска») составляет примерно 250¹⁵⁰. Это связано с тем, что для определения победителя в игре Го между игроками разыгрывается примерно 150 раундов¹, в среднем примерно 250 допустимых позиций¹ на каждый ход в данном раунде. Это число состоит из 360 цифр, основанных на приведенном ниже коде Python.

print(len(str(250**150)))

Постановка проблемы фактически сводится к поиску способов уменьшить пространство поиска, чего DeepMind достиг следующим образом:

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

Политика

Как упоминалось ранее, политика необходима для того, чтобы направлять компьютерную программу на поиск последовательности ходов, которые стоит изучить, чтобы она в основном имитировала игру в этих последовательностях. Для AlphaGo эта Политика была обучена путем наблюдения за игрой профессиональных игроков на основе 30 миллионов игр с KGS Go Server. По сути, эта Политика (Политика А) позволяла AlphaGo имитировать профессиональные игры людей.

Результатом политики А является вероятностное распределение возможных ходов. Чтобы объяснить это на простом примере, предположим, что мы делаем следующий ход белым камнем на игровом поле ниже. Политика А может предложить два возможных хода, ход 1 и ход 2, с вероятностью 60% и 40% соответственно. 60% и 40% были бы основаны на истории профессиональных игр людей, согласно которой, учитывая текущее состояние игры (то есть доска с одним черным камнем), профессиональные игроки-люди делали ход 1 60 из 100 раз ( и ход 2 40 из 100 раз).

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

Можно задаться вопросом, как это улучшает работу Политики. Используя тот же пример, что и выше, компьютерная программа А может решить сделать ход 1, в то время как компьютерная программа Б может выбрать тот же ход или выбрать исследование хода 2, поскольку Политика А должна изначально направлять компьютерную программу. чтобы сделать ход 1 60 из 100 раз и ход 2 40 из 100 раз. Поскольку это происходит на каждом ходу игры, может оказаться, что ход 2 (или, в более общем смысле, ходы, не обязательно имеющие наивысшие вероятности в соответствии с Политикой А) в конечном итоге приведет к победе компьютерной программы В, и в этом случае вероятности для затем два хода могут быть обновлены. В этом случае 60% вероятность сделать ход 1 уменьшается, и одновременно увеличивается 40% вероятность сделать ход 2 с учетом исхода игры. Тот же процесс многократно повторяется для миллионов игр с самим собой, пока не будет сформирована политика B, близкая к оптимальной. Теоретически, чем выше «выученная» вероятность распределяется на ход с помощью Политики B, тем лучше исход игры, к которому приводит этот ход.

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

Предсказатель

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

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

Делаем ход — AlphaGo

Напомним, что на данный момент мы обучили следующее:

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

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

Для AlphaGo в конкретной симуляции n последовательность симулируемых движений в основном регулируется:

  1. Количество посещений определенной последовательности
  2. Предыдущий опыт выигрыша за определенную последовательность ходов

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

Для текущей симуляции AlphaGo распознает, что последовательность хода 1, за которой следует ход 4, уже была посещена, затем он будет управлять симуляцией, чтобы с большей вероятностью использовать другие последовательности, которые ранее не посещались, такие как ход 2 или ход 1, за которым следует ход. 3. Это было сделано для поощрения исследований.

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

Из вышеизложенного вытекает ряд интересных следствий, которые я хотел бы выделить:

  • В начале игры, когда у игрока гораздо больше вариантов, куда поместить следующий камень, AlphaGo поощряет поиск к исследованию, поскольку предшествующий выигрышный опыт не определен из-за обширного пространства для поиска следующие лучшие ходы, даже если они руководствуются Политикой.
  • Напротив, когда доска достаточно заполнена камнями, предыдущий опыт выигрыша от Полиса или Предсказателя становится более влиятельным, поскольку AlphaGo настаивает на последовательности ходов, которые приводят к состоянию или позиции на доске с наивысшей уверенностью. победы. Это использует предыдущий опыт, полученный от людей-профессионалов, а также собственные игры.
  • Мне кажется интересным, что исследование в симуляции обычно руководствуется Политикой А, а не Политикой Б, поскольку человеческий интеллект считается более разнообразным и не может быть полностью изучен машинами. Основное использование политики B для AlphaGo заключается в обучении Predictor.

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

Делаем ход — AlphaGo Zero

Короче говоря, AlphaGo Zero — это улучшенная версия AlphaGo, где «Zero» подчеркивает отделение от профессионального игрового процесса человека.

Хотя общая (обучающая) структура AlphaGo Zero в значительной степени соответствует AlphaGo, ее ключевые отличия заключаются в следующем:

  1. Политика и предиктор от AlphaGo Zero были полностью обучены самостоятельным играм. То есть при обучении AlphaGo Zero не использовался человеческий вклад, такой как профессиональные игры людей.
  2. Архитектура AlphaGo использовала ряд «ручных» функций. Примерами являются количество пустых соседних точек и количество захваченных камней. Они удалены в AlphaGo Zero, которая использует в качестве входных данных только необработанные позиции доски.
  3. Alpha Go Zero сочетает в себе большую часть моделей Policy и Predictor. То есть они тренировались вместе.
  4. Количество раундов в симуляции еще больше сокращается благодаря Predictor, обученному AlphaGo Zero. Это отчасти ускорило обучение AlphaGo Zero.

В целом, AlphaGo Zero — это более широкое применение машинного обучения с более простой структурой и меньшим количеством человеческих взаимодействий по сравнению с AlphaGo. DeepMind признал, что человеческое знание в игре Го может быть изучено (и превзойдено) с помощью самостоятельных игр в одиночку, инициированных случайной Политикой. Фактически, AlphaGo Zero потребовалось всего 40 часов тренировок, чтобы превзойти производительность AlphaGo.

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

Чтобы продемонстрировать на другом простом примере, в состоянии игры, как показано на изображении ниже, давайте предположим, что оптимальная политика имеет распределение вероятностей (100%, 0%), то есть выполнение первого хода определенно приводит к выигрышу. Кроме того, предположим для простоты, что игра заканчивается в одном шаге от текущего состояния. Чтобы узнать оптимальную политику, если мы начнем со случайной политики (50%, 50%) для хода 1 и 2 соответственно, путем взаимодействия самостоятельных игр, случайная политика всегда будет сходиться к оптимальной политике, так как в каждом игра с самим собой, Политика будет обновлена, чтобы увеличить вероятность хода 1, когда разыгрывается ход 1, и наоборот для хода 2.

В AlphaGo случайная политика, с которой мы начинаем самостоятельную игру (50%, 50%) выше, возможно, была ближе к оптимальной политике (например, (90%, 10%)) в политике A, поскольку она была сформирована на основе человеческие профессиональные геймплеи. Однако AlphaGo Zero продемонстрировала, что независимо от того, как мы инициируем Политику, машина всегда может научиться итеративно улучшать Политику, играя против предыдущей версии Политики, и в конечном итоге найти близкий прокси для оптимальной Политики.

Изучение человеческой интуиции

Как показано в исследовательской работе DeepMind², во время обучения AlphaGo Zero научился играть ряд «общих угловых последовательностей», которые представляют собой стратегии, разработанные и часто используемые людьми, без необходимости «наблюдать», как люди-профессионалы играют, как это делала AlphaGo. Удивительно то, что через несколько часов после того, как эти стратегии были обнаружены, некоторые из них были проигнорированы, поскольку были найдены новые и предположительно лучшие варианты.

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

Краткое содержание

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

Есть ряд наводящих на размышления замечаний о том, как работают AlphaGo и AlphaGo Zero, которые я хотел бы еще раз подчеркнуть:

  • Хотя AlphaGo Zero не полагалась на человеческие знания (т. е. Политику A, несмотря на Политику B), они оказали большее влияние на поиск следующего лучшего хода AlphaGo, поскольку люди склонны выбирать «разнообразный пучок многообещающих ходов», особенно в ранние этапы игры, когда игроки склонны больше исследовать.
  • Выбор ходов для Alpha Go и AlphaGo Zero регулируется Политикой, но в то же время поощряет исследование вопреки рекомендациям Политики. На философском уровне это учит нас тому, что иногда мы не должны бояться идти по пути, который выводит нас из нашей зоны комфорта, что может оказаться более полезным.
  • Моделирование или выборка последовательности ходов помогло сформировать оптимальную политику. Это не отличается от преимущества алгоритма случайного леса по сравнению с одним деревом решений. Вы никогда не знаете, что вы можете найти, путешествуя по неизведанному пути!

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

Совершенство против практичности

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

Во многих коммерческих приложениях предельная выгода от достижения 100-процентной точности (по сравнению, скажем, с 95-процентной точностью) для определенных задач может не перевешивать затраты на уменьшение отдачи. Например, обучение модели для повышения точности на 0,05 или 5% может занять в 10 раз больше времени. Другой пример: имеет ли значение победа над Ли Седолем со счетом 4–1 или 5–0 при определении победителя профессионального турнира.

Руководство против инструкций

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

Как менеджер по персоналу, я иногда имел субъективное представление о том, как лучше всего выполнить задачу, исходя из моего собственного опыта, и, как правило, предоставлял и применял такие инструкции к своим непосредственным подчиненным на основе этого мнения. Инструкции могут быть в большей степени ориентированы на процесс, в то время как успех AlphaGo и AlphaGo Zero научил меня тому, что более эффективно руководить, сосредоточившись на конечной цели (или вознаграждении на языке машинного обучения), позволяя людям «искать» и изучать лучшее. способы выполнения задания.

Исследование и разработка

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

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

Ссылка

[1] Сильвер Д., Хуанг А., Мэддисон С. и др. Освоение игры в го с помощью глубоких нейронных сетей и поиска по дереву. Nature 529, 484–489 (2016), https://storage.googleapis.com/deepmindmedia/alphago/AlphaGoNaturePaper.pdf, по состоянию на 25 января 2022 г.

[2] Сильвер Д., Шриттвизер Дж., Симонян К. и др. Освоение игры в го без участия человека. Nature 550, 354–359 (2017). https://doi.org/10.1038/nature24270, по состоянию на 26 января 2022 г.