Qualifiziert sich die Monte-Carlo-Baumsuche als maschinelles Lernen?

9

Nach meinem besten Verständnis ist der Monte-Carlo-Baumsuchalgorithmus (MCTS) eine Alternative zum Minimax für die Suche in einem Knotenbaum. Es funktioniert, indem Sie einen Zug auswählen (im Allgemeinen den mit der höchsten Chance, der Beste zu sein) und dann während des Zuges ein zufälliges Playout durchführen, um das Ergebnis zu sehen. Dieser Vorgang wird für die zugewiesene Zeit fortgesetzt.

Das klingt nicht nach maschinellem Lernen, sondern nach einer Möglichkeit, einen Baum zu durchqueren. Ich habe jedoch gehört, dass AlphaZero MCTS verwendet, daher bin ich verwirrt. Wenn AlphaZero MCTS verwendet, warum lernt AlphaZero dann? Oder hat AlphaZero eine Art maschinelles Lernen durchgeführt, bevor es Spiele gespielt hat, und dann anhand der Intuition, die es durch maschinelles Lernen gewonnen hat, herausgefunden, welche Schritte erforderlich sind, um mehr Zeit mit MCTS zu verbringen?

Trägheitsunwissenheit
quelle

Antworten:

6

Die Monte-Carlo-Baumsuche wird normalerweise nicht als maschinelle Lerntechnik angesehen, sondern als Suchtechnik. Es gibt Parallelen (MCTS versucht in gewissem Sinne, allgemeine Muster aus Daten zu lernen, aber die Muster sind nicht sehr allgemein), aber MCTS ist wirklich kein geeigneter Algorithmus für die meisten Lernprobleme.

AlphaZero war eine Kombination mehrerer Algorithmen. Eines war MCTS, aber MCTS benötigt eine Funktion, um zu sagen, wie gut verschiedene Zustände des Spiels sein könnten (oder es muss ganze Spiele simulieren). Eine Möglichkeit, diese Funktion in einem Spiel wie Schach oder Go zu handhaben, besteht darin, sie durch Training eines neuronalen Netzwerks zu approximieren, wie es die Deep Mind-Forscher getan haben. Dies ist die Lernkomponente von AlphaZero.

John Doucette
quelle
6

Johns Antwort ist insofern richtig, als MCTS traditionell nicht als Ansatz des maschinellen Lernens angesehen wird, sondern als Baumsuchalgorithmus, und dass AlphaZero dies mit Techniken des maschinellen Lernens (Deep Neural Networks und Reinforcement Learning) kombiniert.

Es gibt jedoch einige interessante Ähnlichkeiten zwischen MCTS selbst und maschinellem Lernen. In gewissem Sinne versucht MCTS, den Wert von Knoten aus der durch diese Knoten erzeugten Erfahrung zu "lernen". Dies ist sehr ähnlich zu der Funktionsweise von Reinforcement Learning (RL) (die selbst normalerweise als Teilmenge des maschinellen Lernens beschrieben wird).

Einige Forscher haben auch mit Ersatz für die traditionelle Backpropagation-Phase von MCTS experimentiert (die aus RL-Sicht als Implementierung eines Monte-Carlo-Backups beschrieben werden kann), basierend auf anderen RL-Methoden (z. B. Temporal-Difference-Backups). . Ein umfassendes Papier, das diese Art von Ähnlichkeiten zwischen MCTS und RL beschreibt, lautet: Über Monte-Carlo-Baumsuche und Verstärkungslernen .

Beachten Sie auch, dass die Auswahlphase von MCTS normalerweise als eine Folge kleiner Probleme mit mehreren bewaffneten Banditen behandelt wird und diese Probleme auch starke Verbindungen zu RL haben.


TL; DR : MCTS wird normalerweise nicht als maschinelle Lerntechnik angesehen. Wenn Sie es jedoch genau untersuchen, können Sie viele Ähnlichkeiten mit ML feststellen (insbesondere Reinforcement Learning).

Dennis Soemers
quelle
1

Willkommen im Minenfeld der semantischen Definitionen innerhalb der KI! Laut Encyclopedia Britannica ist ML eine „Disziplin, die sich mit der Implementierung von Computersoftware befasst, die autonom lernen kann“. Es gibt eine Reihe anderer Definitionen für ML, aber im Allgemeinen sind sie alle so vage und sagen etwas über „Lernen“, „Erfahrung“, „Autonomie“ usw. in unterschiedlicher Reihenfolge aus. Es gibt keine bekannte Benchmark-Definition, die die meisten Leute verwenden. Wenn man also keine vorschlagen möchte, muss alles, was man dazu schreibt, durch Referenzen gesichert werden.

Nach der Definition von Encyclopedia Britannica ist der Fall, MCTS als Teil von ML zu bezeichnen, ziemlich stark (Chaslot, Couloms et al. Arbeit von 2006-8 wird für die MCTS-Referenz verwendet). In MCTS werden zwei Richtlinien verwendet, eine Baumrichtlinie und eine Simulationsrichtlinie. Zur Entscheidungszeit aktualisiert die Baumrichtlinie die Aktionswerte, indem sie die Baumstruktur erweitert und Werte von allem sichert, was sie bei der Suche findet. Es gibt keine feste Kodierung, auf welchen Knoten ausgewählt / erweitert werden soll. Alles hängt von der Maximierung der Belohnungen aus Statistiken ab. Die Knoten, die näher an der Wurzel liegen, erscheinen immer intelligenter, wenn sie „lernen“, Verteilungen / Zustände und / oder Aktionswerte von den entsprechenden Werten aus der Realität nachzuahmen. Ob dies als „autonom“ bezeichnet werden kann, ist eine ebenso schwierige Frage, da letztendlich die Menschen die Formeln / Theorien geschrieben haben, die MCTS verwendet.

Johan
quelle