Поиск по дереву Монте-Карло квалифицируется как машинное обучение?

9

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

Это не похоже на машинное обучение, а скорее на путь обхода дерева. Однако я слышал, что AlphaZero использует MCTS, поэтому я в замешательстве. Если AlphaZero использует MCTS, то почему AlphaZero учится? Или AlphaZero провела какое-то машинное обучение, прежде чем сыграла какие-либо матчи, а затем использовала интуицию, полученную от машинного обучения, чтобы узнать, какие движения проводить больше времени, играя с MCTS?

Инерционное невежество
источник

Ответы:

6

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

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

Джон Дусетт
источник
6

Ответ Джона верен в том, что MCTS традиционно рассматривается не как подход к машинному обучению, а как алгоритм поиска по дереву, и что AlphaZero сочетает это с методами машинного обучения (глубокие нейронные сети и обучение с подкреплением).

Однако есть некоторые интересные сходства между самой MCTS и машинным обучением. В некотором смысле MCTS пытается «узнать» ценность узлов из опыта, полученного через эти узлы. Это очень похоже на то, как работает Reinforcement Learning (RL) (который обычно описывается как подмножество машинного обучения).

Некоторые исследователи также экспериментировали с заменами традиционной фазы обратного распространения MCTS (которую, с точки зрения RL, можно описать как реализацию резервных копий Монте-Карло) на основе других методов RL (например, резервных копий с разницей во времени) , Всеобъемлющий документ, описывающий эти виды сходства между MCTS и RL: « О поиске дерева Монте-Карло и обучении усилению» .

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


TL; DR : MCTS обычно не рассматривается как метод машинного обучения, но если вы внимательно изучите его, вы можете найти много общего с ML (в частности, обучение с подкреплением).

Деннис Соемерс
источник
1

Добро пожаловать в область семантических определений в AI! Согласно Encyclopedia Britannica ML - это «дисциплина, связанная с внедрением компьютерного программного обеспечения, которое может обучаться автономно». Есть множество других определений для ОД, но в целом они все эти расплывчатые, говоря что-то об «обучении», «опыте», «автономном» и т. Д. В различном порядке. Не существует общеизвестного определения эталонного теста, которое используют большинство людей, поэтому, если кто-то не хочет предлагать его, то все публикации по этому вопросу должны быть подтверждены ссылками.

Согласно определению Encyclopedia Britannica, случай, когда MCTS называют частью ML, достаточно силен (Chaslot, работа Coulom и др. С 2006 по 2008 год используется для ссылки на MCTS). В MCTS используются две политики: древовидная политика и политика моделирования. Во время принятия решения древовидная политика обновляет значения действий, расширяя древовидную структуру и создавая резервные копии значений из всего, что было найдено в результате поиска. Нет жесткого кодирования, на котором узлы должны быть выбраны / расширены; все это происходит от максимизации вознаграждения от статистики. Узлы, расположенные ближе к корню, кажутся все более интеллектуальными, поскольку они «учатся» имитировать распределения / состояния и / или значения действия из соответствующих значений из реальности. Можно ли назвать это «автономным» - вопрос одинаково сложный, потому что, в конце концов, именно люди написали формулы / теорию, которые использует MCTS.

Johan
источник