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

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

Человеческие знания

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

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

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

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

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

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

Подходы к игре

Прорыв в области машинного обучения произошел в марте 2016 года, когда AlphaGo, алгоритм дерева поиска, основанный на опыте, смог победить лучшего в мире игрока в го Ли Седоля. В отличие от известных движков Go, AlphaGo использует предварительно обученные искусственные нейронные сети, чтобы упростить алгоритм поиска по дереву Монте-Карло, адаптируя стратегии экспертов-людей.

Чтобы стать более независимым от человеческих знаний, AlphaGo Zero, более общая версия AlphaGo, была запущена в октябре 2017 года. Вместо того, чтобы полагаться на заранее изученные стратегии, AlphaGo Zero запускается без предварительных знаний об игровой среде и постоянно улучшает поведение искусственного интеллекта. нейронной сети, изучая предложенные политики алгоритма поиска по дереву Монте-Карло. В декабре 2017 года алгоритм AlphaGo Zero был применен под названием AlphaZero к более широкому классу правил игры.

Без дополнительных параметров AlphaZero освоила игры в го, шахматы и сёги посредством самостоятельной игры, преодолев экстраординарные вычислительные возможности сильнейших в мире игровых движков, таких как Stockfish и IBM Deep Blue, которые опираются на тысячи правил и эвристик, созданных вручную. Однако именно стиль игры AlphaZero вызвал удивление. В шахматах, например, AlphaZero самостоятельно обнаружила и использовала общечеловеческие шахматные стратегии, такие как дебюты, защита короля и структура пешки. Кроме того, AlphaZero разработала свои собственные стратегии, дополняющие и переворачивающие многовековые шахматные знания с помощью широкого спектра инновационных игровых подходов.

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

(Гарри Каспаров — бывший чемпион мира по шахматам)

Поиск по дереву Монте-Карло

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

В шахматах, например, поиск по дереву Монте-Карло итеративно применяется для вычисления оптимального взаимодействия для заданного состояния доски путем моделирования различных будущих сценариев и выбора хода, гарантирующего наилучший возможный долгосрочный результат. Узлы в дереве поиска представляют определенные состояния доски, а каждое соединение между узлами иллюстрирует движение игровой фигуры. Таким образом, с математической точки зрения, конкретный узел (s, a) может быть определен комбинацией определенной ситуации на доске s и соответствующего хода aвыступал на нем.

Во время выполнения алгоритма каждому моделируемому узлу присваивается значение эффективности, указывающее, оказало ли сочетание состояния доски и выполненного хода положительное или отрицательное влияние на производительность текущего игрока. Обычно значение эффективности узла определяется как отношение между количеством симуляций N(s,a) и соответствующим количеством побед Q(s,a). . Например, если узел привел к победе только один раз, но был смоделирован четыре раза, значение эффективности равно ¼. Узлы с более высокими значениями эффективности, следовательно, более прибыльны и предпочтительны при выборе поддеревьев.

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

Выбор

Давайте немного подробнее. Начиная с корневого узла (sₒ,⋅ ), политика выбора дочерних элементов 𝜋 рекурсивно применяется к дереву поиска до тех пор, пока неконечное состояние доски sₖ с непосещенными дочерними узлами (sₖ, a) достигается. Самая популярная политика выбора дочерних элементов 𝜋 представлена ​​простыми и эффективными границами верхней достоверности, применяемыми к алгоритму деревьев (UCT), который гарантирует нахождение в пределах постоянного коэффициента наилучшей возможной границы. Функциональность алгоритма UCT описывается как независимая задача многорукого бандита, выбирающая оптимальное действие среди всех возможных решений путем максимизации следующей политики:

Учитывая текущее нетерминальное состояние платы sₘ и набор последующих состояний платы sₙ, каждое из которых подключено к узлу (sₘ,⋅ ) через соответствующий переместите a. Переменная N(sₘ,⋅ ) представляет общее количество исследований sₘ, а переменная N(sₘ, a) описывает количество посещений, связанных с каждым из последующих узлов (sₘ, a). Если конкретное значениеN(sₘ, a) равно нулю, значение UCT узла (sₘ, a) определяется как бесконечность. Это определение основано на дилемме исследования-эксплуатации, гарантируя, что непосещенные дочерние узлы рассматриваются по крайней мере один раз, прежде чем любой другой последующий узел будет расширен дальше. Кроме того, переменная Cₚ › 0 может быть увеличена или уменьшена, чтобы регулировать влияние последующего срока разведки. Отношение Q(sₘ, a) и N(sₘ, a) представляет собой значение эффективности узла (sₘ, a), которое считается лежащим в интервале от нуля до единицы. Если несколько узлов (sₘ, a) имеют одинаковое максимальное значение, действие выбирается случайным образом.

Расширение

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

Моделирование

На следующем шаге результат игры ∆ для вновь созданного конечного узла (sₘ, a) вычисляется путем моделирования последовательности случайных действий до тех пор, пока не будет достигнуто конечное состояние игры. В зависимости от области применения алгоритма поиска по дереву Монте-Карло сложность моделирования может различаться. Кроме того, ожидаемый доход ∆ может быть дискретным или непрерывным значением для более простых областей или вектором для более сложных многоагентных областей. Например, в среде, в которой набор возможных исходов определяется победой или поражением в игре, значение ∆ будет содержать либо 1, либо 0. >Поскольку каждый из созданных узлов генерируется без предварительного знания о пространстве поиска, сохраняется общность случайной выборки.

Обратное распространение

На последнем шаге смоделированный результат ∆ вновь созданного конечного узла (sₘ, a) распространяется обратно через предыдущие узлы дерева для обновления статистики результата Q(s, a) каждого узла (s, a) в выбранном поддереве. Обновление обычно реализуется путем добавления ∆ к значению Q(s, a). Кроме того, количество посещений N(s, a) каждого узла увеличивается.

Прекращение

Обход алгоритма поиска по дереву Монте-Карло повторяется до тех пор, пока не будут удовлетворены ограничения по времени, памяти или итерации. Как только поиск завершается, одно из возможных действий a корневого узла sₒ выбирается как оптимальное решение исходной проблемы принятия решений. Как правило, существует четыре различных критерия для выбора наилучшего возможного действия:

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

Поиск по дереву на основе опыта

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

Например, в шахматах AlphaZero ищет только 60 тысяч позиций в секунду, по сравнению с примерно 60 миллионами для шахматного движка с открытым исходным кодом Stockfish. Для реализации алгоритма AlphaZero каждый узел (s, a) состоит из априорной вероятности успеха P(s, a), количества посещений N(s , a) и ожидаемый результат, снова представленный отношением Q(s, a)и N(s, a). Начиная с текущего состояния доски sₒ, алгоритм AlphaZero моделирует ситуацию с несколькими досками, итеративно выбирая взаимодействия с доской, которые максимизируют верхнюю доверительную границу, до тех пор, пока не посещенный дочерний узел (sₘ,⋅ ) встречается.

Затем положение обнаруженного непосещенного дочернего узла расширяется и оценивается с помощью модели искусственной нейронной сети fₔ для генерации как априорных вероятностей P(sₘ,⋅ ), так и прогнозируемых результаты V(sₘ) последующих дочерних узлов (sₘ, a).

Поскольку прогнозируемые результаты V(sₘ) ∈ {-1, 0, 1} уже сгенерированы моделью искусственной нейронной сети, для оценки последующих взаимодействий с доской не требуется никаких дополнительных симуляций. На следующем шаге прогнозируемые значения обнаруженного дочернего узла (sₘ, a) распространяются обратно через предыдущие узлы, чтобы обновить среднюю статистику результатов выбранных узлов пути, описанную Q( с, а) и N(s, а).

После 800 итераций алгоритм поиска по дереву Монте-Карло AlphaZero возвращает взаимодействие доски с наиболее посещаемым узлом (sₒ, a) как оптимальное решение текущей проблемы принятия решений sₒ. В качестве дополнительной отдачи количество посещений ветвей (sₒ, a) преобразуется в распределение вероятностей 𝜋, вычисляемое либо пропорционально, либо жадно по отношению к количеству посещений корневой узел (sₒ,⋅ ). Распределение 𝜋, представляющее последние выполненные поисковые запросы, затем используется для настройки параметров ɘ искусственной нейронной сети fₔ.

В начале алгоритма обучения с подкреплением для самостоятельной игры нейронная сеть инициализируется случайными весами ɘₒ. Во время игры AlphaZero использует управляемый алгоритм поиска по дереву Монте-Карло, чтобы найти оптимальное решение для каждой возникающей ситуации на доске. Результирующие распределения вероятностей 𝜋ₜ и соответствующая ситуация на доске sₜ сохраняются до завершения текущей игры. По определению игра завершается на этапе T, когда либо оба игрока пасуют, либо когда значение поиска падает ниже порога отказа, либо когда игра превышает максимальную продолжительность.

Возникающие на доске ситуации s затем передаются модели искусственной нейронной сети в виде стека входных изображений N×N×(M ⋅ T + L), объединяя наборы T из M плоскостей размером N×N. Каждый набор плоскостей представляет положение доски в определенный момент времени и ориентирован на перспективу текущего игрока. Плоскости признаков M состоят из бинарных плоскостей признаков, указывающих на присутствие фигур игрока, в то время как каждая из L дополнительных входных плоскостей с постоянными значениями предоставляет дополнительную информацию в терминах цвета игрока, общего количества ходов или ограничений, зависящих от игры.

Комбинация конечного результата z ∈ {-1, 0, 1}, распределения вероятностей 𝜋, прогнозируемых результатов v:=V(sₒ) , априорные вероятности p:=P(sₒ,⋅ ) и соответствующие ситуации на доске s затем используются для обновления параметров искусственной нейронной сети. модель fₔ путем минимизации следующей функции потерь l. В частности, параметры ɘ регулируются градиентом приличия, применяемым к среднеквадратической ошибке и перекрестной энтропии вероятности и выходного значения модели искусственной нейронной сети. Значение c вводится как параметр для управления уровнем регуляризации веса L2:

Чтобы изучить каждую игру, необученная модель искусственной нейронной сети играет с самой собой в миллионы игр. Сначала она играет совершенно случайно, но со временем система учится на выигрышах, проигрышах и ничьих, что повышает вероятность выбора выгодных ходов в будущем. Объем обучения сети, который требуется сети, зависит от стиля и сложности игры: примерно 9 часов для шахмат, 12 часов для сёги и 13 дней для го — часть времени, которое потребовалось бы нам, людям, чтобы освоить игровую механику. Аналогичные результаты можно наблюдать и в сравнении с сильнейшими в мире игровыми движками:

Исследования

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