Разница между политикой сети AlphaGo и сетью ценностей

25

Я читал обзор высокого уровня об AlphaGo от Google ( http://googleresearch.blogspot.co.uk/2016/01/alphago-mastering-ancient-game-of-go.html ), и я столкнулся с условиями "политика" сеть "и" сеть ценностей ". На высоком уровне я понимаю, что сеть политик используется для предложения шагов, а сеть ценностей используется для «уменьшения глубины дерева поиска [и оценки] победителя в каждой позиции вместо поиска всего пути к конец игры. "

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

Полный PDF-документ Google, опубликованный в журнале Nature, можно найти здесь: https://vk.com/doc-44016343_437229031?dl=56ce06e325d42fbc72.

Райан Зотти
источник
В качестве краткого примечания: целевой переменной для сети политик является распределение вероятностей. Из статьи: «Эта нейронная сеть (сеть ценностей) имеет архитектуру, аналогичную сети политик, но выдает единственное предсказание вместо распределения вероятностей»
Zimano
3
Если кто-то еще наткнется на этот старый вопрос, как я, вам будет приятно узнать, что преемник AlphaGo, «AlphaGo Zero», а также его преемник «AlphaZero» действительно избавляются от избыточности, только обучая ОДНУ сеть, результаты которой служат функциям как сети политик (дает распределение вероятностей по возможным ходам), так и сети ценностей (дает вероятность выигрыша на данной доске). Сообщение в блоге здесь: deepmind.com/blog/alphago-zero-learning-scratch и статья связана внутри.
Кевин Ван

Ответы:

11

Вкратце, каждая сеть имеет свое назначение, как вы упомянули:

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

В общем, вы можете использовать методы функции-значения, чтобы найти оптимальную политику, или напрямую искать в пространстве политик, чтобы оптимизировать параметризованную функцию политики (конечно, есть плюсы и минусы). Вы можете использовать функциональные аппроксиматоры (например, Deep Nets) в каждом случае. Я вижу, что в основном вы не понимаете политическую сеть, поэтому я сфокусируюсь на этом.

Сеть политики была первой:

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

Затем,

он был обучен играм с самим противником, чтобы оптимизировать ранее выученную политику. На этот раз его вес был обновлен с использованием алгоритма REINFORCE. Делая это, вы обновляете сетевые параметры для максимизации ожидаемого вознаграждения. В конце концов, у вас есть сеть, которая не только выбирает действия, как профессиональный игрок, но и ведет к победе в игре (однако она не может планировать!).

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

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

Наконец, вы можете использовать свой алгоритм планирования (MCTS) в сочетании с этими сетями. Почему мы предприняли все эти шаги? Вкратце, простая MCTS без какой-либо «интуиции» провалилась бы.

Константинос
источник
Я только что вернулся к этому вопросу, узнав об Actor-Critic и о том, как он компенсирует затраты / выгоды между методами, основанными исключительно на значениях и на основе политик. Я думаю, что этот ответ наиболее близок к объяснению этой детали, но он очень хорошо описан в лекции Дэвида Сильвера: www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/pg.pdf (лекция 7, также доступен на YouTube - youtube.com/… ).
Нил Слэйтер
Чисто подходы, основанные на MCTS, оказались успешными, поэтому в более широком контексте я бы не сказал, что это потерпело бы неудачу.
Зимано
1
Я имею в виду только случай игры в Го, а также достижение мастерского уровня игры. На самом деле Дэвид Сильвер (как и другие исследователи) работал над решением проблемы игры в Го с MCTS со времени его докторской диссертации. Но ничто не могло конкурировать на самых высоких уровнях до комбинации методов выше.
Константинос
9

Вот мой краткий мыслительный процесс в понимании двух разных сетей.

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

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

Теперь у нас есть два отдельных вопроса для разработки приближенного подхода.

Q1. Как мы можем пропустить или игнорировать некоторые ходы из N на позицию? (т.е. уменьшение дыхания)

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

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

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

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

Я просто надеюсь, что это поможет. Я знаю, что это все еще будет на высоком уровне.

Ветер П.
источник
Ваши два способа объяснения очень лаконичны.
Тим
6

Я думаю, что ОП путала насчет AlphaGo с альфа-бета. В альфа-бете вы действительно использовали бы сеть политик для помощи в сокращении, но не здесь. Опять же, отсечение отсутствует, поскольку алгоритм основан на поиске по дереву Монте-Карло (MCTS).

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

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

Пример:

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

  • Первый ход: вынужденная потеря для вас
  • Второй ход: вынужденная победа для вас

Оценочная сеть

Давайте предположим, что оценочная сеть, которую Google дает вам, идеальна. Он может отлично оценить любую позицию листа в нашем примере. Мы не будем менять нашу сеть стоимости в этом примере.

Чтобы упростить наш пример, давайте предположим, что наша сеть значений дает:

  • -1000 за любую позицию листа, что для вас потеря
  • +1000 за любую позицию листа, которая является победой для вас

Политика сети

Давайте предположим, что Google предоставляет вам две сети политик. Вероятности, сгенерированные для нашей позиции:

  • Политика 1: 0,9 за ход 1 и 0,1 за ход 2
  • Политика 2: 0,2 за ход 1 и 0,8 за ход 2.

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

Игра с первой политикой сети

AlphaGo должен сгенерировать симуляцию с Монте-Карло, и ему нужно выбрать ход 1 или 2. Теперь AlphaGo рисует случайную переменную с равномерным распределением и выбирает:

  • Переместите 1, если случайное число <= 0,9
  • Переместите 2, если случайное число> 0,9

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

введите описание изображения здесь

Это значение будет -1000, потому что это моделирование приведет к потере.

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

  • Наша предыдущая вероятность для второго хода составляет 0,1, а не ноль
  • AlphaGo рекомендуется пробовать ходы, которые мало изучены. В статье это делается с помощью этого уравнения:

введите описание изображения здесь

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

введите описание изображения здесь

введите описание изображения здесь

Это ключевое уравнение. Пожалуйста, посмотрите на это внимательно:

  • У него есть термин Pдля априорной вероятности (заданный сетью политики)
  • У него есть термин Qдля оценочных баллов (определяется сетью добавленной стоимости).

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

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

Наконец, ход, который AlphaGo решает сделать, (цитируется в статье):

По завершении поиска алгоритм выбирает наиболее посещаемый ход из корневой позиции.

Игра со второй политикой сети

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

замечания

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

Сводки

  • Политическая сеть используется для генерации априорных вероятностей, чтобы определить, какой шаг должен выбрать поиск Монте-Карло.
  • Сеть значений используется для генерации данных для проверки политики сети. Если сеть политик плохая, AlphaGo потребуется больше вычислительных ресурсов для конвергенции (если вообще когда-либо).
  • Вы можете думать об этом как о байесовском анализе
SmallChess
источник
Я думаю, что это дает гораздо более глубокое понимание внутренних механизмов. Я все еще не уверен, объясняет ли это, почему две сети. У меня есть проблема: «Предположим, сеть оценки ... идеальна». Если это так, то действительно политика сети является избыточной. Просто посмотрите на одно движение вперед (для всех возможных движений) и выберите тот, который лучше всего оценивает сеть. Конечно, сеть ценностей не идеальна, и я подозреваю, что она становится более точной по мере дальнейшего развития игры. , , но я не знаю, насколько это верно / полезно, или дополняет ли этот ответ.
Нил Слэйтер
@NeilSlater Хорошо. Сети не идеальны, но причины, которые у меня есть, все еще хороши, просто нам нужно больше симуляций MC.
SmallChess
@StudentT Хорошее объяснение некоторых ключевых уравнений. Я хотел бы сделать одно небольшое изменение: не имеет смысла говорить «Вам нужно увидеть десять шагов вперед», чтобы понять положение в поиске дерева Монте-Карло. MCTS - это поиск доказательств по числу глубин, и мы никогда не достигаем фиксированных глубин, как при итеративном углублении в шахматах. Даже несмотря на то, что сеть ценностей позволяет нам оценивать узлы до конца игры, мы по-прежнему не достигаем их в широком смысле, и нет минимальной оценки узлов и т. Д.
Имран,
@Imran Не стесняйтесь редактировать мой пост.
SmallChess
3

Сеть политик : Сеть, которая учится давать определенный результат, давая определенный вклад в игру, известна как сеть политик.

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

Лучшее понимание с помощью анимации. Перейдите по ссылке: Сети политики против сетей ценностей в обучении укреплению

введите описание изображения здесь

САГАР ШАРМА
источник
0

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

Чувствую себя обязанным исправить меня, если я ошибаюсь.

Джунатан Самуэль
источник
2
Вы не ошибаетесь, AFAIK, но я не думаю, что это отвечает на вопрос. OP, кажется, осознает разницу между моделью на основе значений или политикой в ​​RL. Два подхода действительно имеют разные результаты. Однако чаще встречается одна или другая, а не обе, и две модели обычно избыточны в том смысле, что «Value_maxarg (S ') == Policy_maxarg (S, A)», где S - текущее состояние, A - действие для принять, и S 'является результатом состояния. Т.е. две сети в более обычной настройке RL просто дадут один и тот же результат, даже если выходы разные.
Нил Слэйтер