[PYTHON] Stärkung des Lernens 1 Einführungsausgabe

Aidemy　2020/11/15

Einführung

Hallo, es ist ja! Ich bin eine knusprige Literaturschule, aber ich war an den Möglichkeiten der KI interessiert, also ging ich zur KI-Fachschule "Aidemy", um zu studieren. Ich möchte das hier gewonnene Wissen mit Ihnen teilen und habe es in Qiita zusammengefasst. Ich freue mich sehr, dass viele Menschen den vorherigen zusammenfassenden Artikel gelesen haben. Vielen Dank! Dies ist der erste Beitrag zur Stärkung des Lernens. Freut mich, dich kennenzulernen.

• Dieser Artikel ist eine Zusammenfassung dessen, was Sie in "Aidemy" "in Ihren eigenen Worten" gelernt haben. Es kann Fehler und Missverständnisse enthalten. Bitte beachten Sie.

Was diesmal zu lernen ・ Was ist Bestärkungslernen? ・ Agent, Umgebung, Belohnung ・ Stärkere Lernpolitik

Was ist Bestärkungslernen?

・ Maschinelles Lernen kann grob unterteilt werden in __ "Lernen mit Lehrer", "Lernen ohne Lehrer" und "Verbessertes Lernen" __. ・ Von diesen ist das __ verbesserte Lernen __, das wir dieses Mal lernen werden, eine Methode, die darauf abzielt, __ "das optimale Verhalten unter gegebenen Bedingungen zu entdecken" __. Im Fall eines Spiels können Sie beispielsweise herausfinden, wie Sie gewinnen können, indem Sie das Lernen stärken.

Mehr über verbessertes Lernen

・ Verbessertes Lernen wird unter der Voraussetzung durchgeführt, dass __ "Agent" __ und __ "Umgebung (Phase)" __ miteinander interagieren. -Wenn sich ein agent __ im state s befindet und action a für environment ausführt, gibt die Umgebung reward R als Bewertung dieses Verhaltens aus. Im Gegenzug fährt der Agent mit der Aufgabe fort, während er den Übergang zum nächsten Zustand s ' wiederholt. ・ Im Fall von Super Mario führt der Agent "Mario" beispielsweise die Aktion "Ausweichen vor dem Feind (durch Springen)" in einer Umgebung durch, in der "vorgehen und auf das Ziel zielen, aber enden, wenn es den Feind trifft". Die Umgebung gibt die Belohnung "das Recht, weiter zu gehen (das Spiel endet nicht dort)" zurück. Indem Mario dies wiederholt, kommt er der Aufgabe des Ziels entgegen.

・ Bei der Stärkung des Lernens wird nicht nur die Belohnung vor Ort __ "sofortige Belohnung" __ maximiert, sondern auch die Belohnung __ "verspätete Belohnung" __, die danach __ "Gewinn" __ enthalten ist Es muss maximiert werden. ・ Im vorherigen Beispiel von Mario ist das Nehmen von Münzen eine wertlose Aktion vor Ort. Wenn Sie jedoch Wert darauf legen, 100 Teile zu sammeln und "die verbleibenden Maschinen zu erhöhen", können Sie die Belohnung maximieren. Man kann sagen, dass es besser ist, so viel wie möglich Münzen zu nehmen.

N-Arm-Banditenproblem

・ __N Armbanditenproblem __ ist ein Beispiel für die Stärkung des Lernens. "Ich kann" __ "nicht sehen." Wenn der Benutzer einen Slot in einem Versuch ziehen kann, wie kann ich die durchschnittliche Belohnung pro Anzahl von Versuchen maximieren? " Es ist ein Problem, darüber nachzudenken. ・ Die Idee ist, dass __ "mit der höchsten Wahrscheinlichkeit an der Plattform ziehen" __, aber es ist notwendig zu versuchen, diese Plattform zu finden (zu erraten) __. Das ist die Essenz dieses Problems. ・ Von nun an lernen wir anhand dieses Beispiels, wie man das Lernen stärkt.

Agenten erstellen

-__ Agent__ bedeutet genauer __ "Dinge, die Aktionen in der Umgebung bestimmen und die Umgebung beeinflussen" __. ・ Beim N-Arm-Banditenproblem ist der Agent user, der entscheidet, welche Maschine verwendet werden soll, eine Belohnung erhält und die nächste Entscheidung trifft. -Der Index __, wie die nächste Entscheidung aus den vom Agenten erhaltenen Belohnungen getroffen werden soll, heißt __ "Richtlinie" __. Wenn die Richtlinie in diesem Problem beispielsweise auf "immer 1" festgelegt ist, strebt der Agent immer eine Plattform an, auf der die Belohnung 1 beträgt. ・ Der Zweck dieser Zeit besteht darin, die optimale Richtlinie für diesen Agenten zu ermitteln.

-Der folgende Code ist eine Funktion __ "randomselect ()" __, die zufällig die Methode bestimmt __ "Welche Maschine soll ausgewählt werden" __. Dies gibt __ "slot_num" __ die zu wählende Einheit zurück.

Eine Umgebung schaffen

-__ Umgebung__ ist das Ziel __, auf das der __Agent reagiert. Seine Aufgabe ist es, Maßnahmen zu ergreifen, die Situation zu beobachten, Belohnungen an Agenten zu senden und einmal voranzukommen. -Die Umgebung in diesem Problem ist __ "Wenn ein Agent eine Tabelle zieht, hängt der Prozess des Schlagens oder Verlierens von der Wahrscheinlichkeit dieser Tabelle ab" __.

-Der folgende Code ist die Funktion __ "environment ()" __, die die Umgebung definiert. __ "coin_p" __ speichert die Wahrscheinlichkeit, jede Einheit in einem NumPy-Array zu treffen, und "results" ist __ "np.random.binomial (n, p)" __, die Anzahl der Versuche n und das Binomial der Wahrscheinlichkeit p Verwenden Sie die Funktion, um die Verteilung zu finden und das Ergebnis des Subtrahierens von Slots zu speichern. Dieses Mal ist die Anzahl der Versuche eins und die Wahrscheinlichkeit ist "coin_p", sodass Sie __ (1, coin_p) __ angeben können. Als Umgebungsfunktion sollte das Ergebnis der übergebenen "band_number" zurückgegeben werden, daher wird dies in "result" gespeichert und zurückgegeben.

Definition der Belohnung

-__ Belohnung__ ist ein Index __, der die Erwünschtheit einer Reihe von Aktionen des __Agenten bewertet. ・ Apropos Problem: Der Rückgabewert (0 oder 1) __, der durch Subtrahieren des Steckplatzes erhalten wird, ist die Belohnung, wie sie ist. Dies entspricht einer sofortigen Belohnung.

-Der folgende Code ist die Funktion __ "Belohnung ()" __, die die Belohnung definiert. Das zuvor von der Umgebungsfunktion erhaltene Ergebnis wird in "Ergebnis" gespeichert, und dies wird in der "Zeit" gespeichert, die die aktuelle Anzahl von Versuchen des als Argument übergebenen Array- "Datensatzes" angibt. -Auch in der Liste __ "Ergebnisse" __ ist dies __ [[(Anzahl der Einheiten), (Anzahl der Auswahlen), (Gesamtbelohnung), (Gesamtbelohnung ÷ Anzahl der Auswahlen)], ...] __ Speichern Sie jedes Ergebnis.

• Verwenden Sie außerdem diese Funktionen oder übergeben Sie den Wert selbst, um __ "zu verwendende Tabelle", "Treffer oder Fehler", "wie oft versucht werden" __ usw. und die Anzahl der Versuche für jede Maschine zu bestimmen Das Ergebnis wird ausgegeben und der Übergang der durchschnittlichen Belohnung wird unten dargestellt.

·Ergebnis

・ Wenn Sie sich dieses Ergebnis ansehen, ist "Welches Auto Sie wählen sollen" völlig zufällig (1/5), sodass die Häufigkeit, mit der __ Autos ausgewählt werden, gleich __ ist und die Trefferwahrscheinlichkeit fast gleich ist. Es ist geworden. Wie Sie in der Grafik sehen können, wird die durchschnittliche Belohnung bei etwa 0,5 gehalten.

Maßnahmen für N-Arm-Band-Problem

gierige Methode

• Da der Agent, die Umgebung und der Belohnungstyp bisher definiert wurden, besteht der nächste Schritt darin, über __Maßnahmen __ nachzudenken. "Wie kann ich die durchschnittliche Belohnung erhöhen?" ・ Grundsätzlich gibt es zunächst keine Informationen, daher bleibt keine andere Wahl, als eine Tabelle zufällig auszuwählen __. Nach einigen Versuchen und wenn Sie die Wahrscheinlichkeit erraten können, einen Tisch zu treffen, finden Sie den Tisch mit der höchsten Wahrscheinlichkeit und treffen die Wahl, diesen Tisch weiter auszuwählen. ・ Zu diesem Zeitpunkt wird das Sammeln von Informationen durch wiederholtes Wiederholen von Versuchen als __ "Suche" __ bezeichnet, und die weitere Auswahl der am besten geeigneten Plattform wird als __ "Verwenden" __ bezeichnet.

-Die einfachste Methode, um diese Richtlinie auszuführen, ist __ "gierige Methode" __. Dies ist eine einfache und unkomplizierte __ "Wählen Sie aus den bisherigen Ergebnissen diejenige mit dem höchsten erwarteten Wert aus" . ・ Führen Sie zuerst search durch. Zu diesem Zeitpunkt wird im Voraus entschieden, dass __ n Mal pro Einheit versucht wird, und dies wird für alle Einheiten durchgeführt. Wenn dies erledigt ist, berechnen Sie den erwarteten Wert von __ Belohnung $ u {i} $ zu diesem Zeitpunkt __ und wählen Sie den größten aus. -Der erwartete Wert $ u {i} $ wird berechnet durch __ "(Summe der Belohnungen von Maschine i) ÷ (Anzahl der Versuche von Maschine i)" __.

-Der folgende Code ist ein Beispiel für die tatsächliche Definition dieser Methode und die Verwendung der Funktion, die die Umgebung usw. definiert, die bis zum vorherigen Abschnitt erstellt wurde.

-Die Definition der gierigen Methode lautet __ "Lassen Sie slot_num in dieser Tabelle, bis die maximale Anzahl von Versuchen erreicht ist." __ und __ "Wenn alle Computer die maximale Anzahl von Versuchen erreicht haben, wird slot_num festgelegt. Machen Sie es zu dem mit dem höchsten erwarteten Wert an diesem Punkt. "__ Sie können es definieren.

• Für letztere besteht der Grund, warum der Code __ "np.array ()" __ sagt, darin, die Methode __ "argmax ()" __ zu verwenden, um den Maximalwert zu erhalten.

・ Üben Sie die gierige Methode, indem Sie einen Wert angeben

・ Ergebnis

・ Wie aus diesem Ergebnis hervorgeht, werden Versuche mit allen Einheiten bis zur Obergrenze der Anzahl der Versuche für eine bestimmte Suche durchgeführt __ "n = 100" __ und ab diesem Zeitpunkt mit dem höchsten erwarteten Wert __ Alle Versuche (9500 verbleibende) werden für "Tabelle 4" __ verwendet.

ε (Epsilon) -greedy-Methode

• Bei der gierigen Methode im vorherigen Abschnitt ist die Wahrscheinlichkeit, die falsche Plattform auszuwählen, umso höher, je kleiner n ist, dh je weniger Versuche für die Suche verwendet werden. Wenn andererseits n erhöht wird, erhöht sich die Möglichkeit, die optimale Plattform auszuwählen, aber die Suche erfordert eine große Anzahl von Versuchen, was zu einer großen Verschwendung führt. -Diese __ "ε-gierige Methode" __ kann dieses Problem lösen. Durch die Verflechtung von suche und Verwendung kann diese Methode die Suchkosten senken und gleichzeitig das Risiko verringern, weiterhin die falsche Plattform zu wählen. ・ Der Ablauf der ε-gierigen Methode ist wie folgt. ① Wenn es einen Stand gibt, den Sie noch nicht ausgewählt haben, wählen Sie ihn aus ② __ Wahrscheinlichkeit ε, zufällig aus allen Einheiten auszuwählen __ (Suche) ③ Wählen Sie die Maschine mit der höchsten durchschnittlichen Belohnung (erwarteter Wert) mit __ Wahrscheinlichkeit 1-ε __ (Verwendung)

Mit anderen Worten, diese Methode besteht darin, mit __ Wahrscheinlichkeit ε zu suchen und mit Wahrscheinlichkeit 1-ε für jeden Versuch zu verwenden.

・ Definitionsteil der ε-gierigen Methode

・ Ausführungsteil

・ Ergebnis

Optimistische Anfangswertmethode

・ Wenn bei der gierigen Methode beispielsweise "Tabellen A und B mit einer Wahrscheinlichkeit von 0,4 und 0,6 getroffen werden" und der erwartete Wert von "Tabelle von A" bis zu "0,8" vorhergesagt wird, wird zunächst die Tabelle von A verwendet. Durch einen Versuch ist es jedoch möglich zu erkennen, dass der erwartete Wert der A-Plattform niedrig zu sein scheint (konvergiert gegen 0,4) und auf die B-Plattform zu wechseln. ・ Wenn andererseits vorhergesagt wird, dass der erwartete Wert von "B-Stand" kleiner als "0,2" ist, ist die Situation, dass "B-Stand wird nicht versucht", dh "Nur ein Stand wird ausgewählt". Es gibt ein Problem, dass __ ich den Fehler __ nicht bemerken kann.

• Als Methode zur Reduzierung dieses Risikos wird __ "optimistische Anfangswertmethode" __ "höher geschätzt (optimistisch), wenn unsicher" verwendet. ・ Als konkrete Idee berechnen wir vor dem Lernen den erwarteten Wert, nachdem wir angenommen haben, dass der Maximalwert der Belohnung K-mal von jeder Maschine erhalten wird __.
• Daher ist es bei Verwendung dieser Methode erforderlich, __ "maximaler Belohnungswert (rsup)" __ und __ "anzugeben, wie oft der maximale Wert (K)" __ angenommen wird. ・ Der erwartete Wert jeder Einheit, die diese beiden verwendet, wird mit $ \ frac {R (N) + Kr_ {sup}} {N + K} $ berechnet. __R (N) __ gibt an, wie oft tatsächlich gemessen wurde (in der dritten Ergebnisspalte gespeichert), und N ist, wie oft tatsächlich gemessen wurde (in der zweiten Ergebnisspalte gespeichert). Der Code sieht also so aus:

-Ausführungsteil

・ Ergebnis

Soft-Max-Methode

-Der Nachteil der ε-gierigen Methode ist, dass bei der Suche, auch wenn sie eindeutig als die schlechteste angesehen wird, __ immer eine feste Anzahl von Versuchen versucht wird. Wenn zum Beispiel die Wahrscheinlichkeit eines Treffers 20% beträgt und es eine Tabelle gibt, die "1" ist, wenn sie getroffen wird, und "-100", wenn sie verloren geht, wird vorausgesagt, dass das Ziehen dieser Tabelle ein extrem schlechtes Verhalten ist, aber ε-gierig Das Gesetz kann dies nicht vermeiden und suchen. -Es ist __ "Soft-Max-Methode" __, die dies lösen kann. Dies ist __ "Es ist einfach, Aktionen auszuwählen, die einen hohen Wert zu haben scheinen, und es ist schwierig, Aktionen auszuwählen, die einen niedrigen Wert zu haben scheinen" . Das heißt, __ "jede Aktion gewichten" __ wird ausgeführt. ・ Das Gewicht wird nach der Formel $ \ frac {\ exp {Q {i} / \ tau}} {\ sum ^ i \ exp {Q {i} / \ tau}} $ berechnet. $ Q_i $ ist der erwartete Wert der Belohnung, $ \ tau $ (tau) ist der Parameter, und je kleiner $ \ tau $ ist, desto stärker ist die Tendenz der obigen Gewichtung. ・ Wenn im Fluss der Soft-Max-Methode keine __Daten vorhanden sind, werden alle Belohnungen als "1" __ angenommen, die Auswahlwahrscheinlichkeit jeder Einheit wird nach der obigen Formel berechnet und die Auswahl wird auf dieser Grundlage getroffen. , Aktualisieren Sie die Belohnungsfunktion, indem Sie eine Belohnung erhalten, und so weiter. Der spezifische Code lautet wie folgt.

-Für den obigen Code berechnen Sie zuerst den erwarteten erwarteten Wert der Belohnung __ "q" __. Siehe hierzu die vierte Ergebnisspalte. Wenn keine Daten vorhanden sind, ist der erwartete Belohnungswert "q" alle "1", dh ein Array mit allen Werten 1 wird mit __ "np.ones ()" __ erstellt. -Berechnen Sie die Auswahlwahrscheinlichkeit __ "Wahrscheinlichkeit" __ mit der obigen Formel unter Verwendung von "q" und "tau". Unter der Annahme, dass die Wahrscheinlichkeit die Wahrscheinlichkeit ist und das zu wählende Ziel die Nummer der Einheit ist, definiert __ "np.random.choice (Array, p = Wahrscheinlichkeit)" __, was ausgewählt wird.

-Ausführungsteil

・ Wenn man sich die obigen Ergebnisse ansieht, wird sie oft nach der Wahrscheinlichkeit ausgewählt, mit der die Tabelle getroffen wird. In diesem Versuch traf die Maschine Nr. 1 jedoch überhaupt nicht und wurde als "Maschine mit einer Wahrscheinlichkeit von 0" angesehen und danach nicht ausgewählt.

UCB1-Algorithmus

-Der __UCB1-Algorithmus __ ist eine verbesserte Methode der __ optimistischen Anfangswertmethode __. Insbesondere __ "Wie viel hat die Maschine getroffen (Erfolgsrate)" __ und __ "Wie viel wissen Sie über die Maschine (die Menge der zufälligen Datenschwankungen)" __ Durch ein Urteil ist es möglich, aktiv nach einer Tabelle zu suchen, die nicht so häufig durchsucht wurde, und die Tabelle mit der höchsten Gewinnwahrscheinlichkeit auszuwählen, wenn gleichzeitig Daten gesammelt werden.

• Berechnen Sie als Fluss zuerst die Differenz "R" __ zwischen den Maximal- und Minimalwerten von _Reward. Wenn es dann eine Einheit gibt, die noch nicht ausgewählt wurde, wählen Sie sie aus und berechnen Sie den erwarteten Wert (Erfolgsrate) __ "$ u {i} $" der Belohnung für jede Einheit aus den erhaltenen Ergebnissen.
• Berechnen Sie auch mit $ R \ sqrt {\ frac {2logT} {N}} $ unter Verwendung dieser die Größe der Datenvariation "$ x_ {i} " aufgrund der Wahrscheinlichkeit jeder Einheit. Zu diesem Zeitpunkt steht __ "T" __ für die Gesamtzahl der Spiele und __ "N" __ für die Anzahl der Spiele der Maschine i. ・ Bedenken Sie, dass die Plattform mit der maximalen __ Summe __ von " u_ {i} " und " x_ {i} $" am besten geeignet ist, und wählen Sie sie aus. ・ Das Obige kann wie folgt im Code ausgedrückt werden. (R = 1 für N-Arm-Streifen)

-Für den obigen Code kann "eine Maschine, die noch nicht ausgewählt wurde" so umformuliert werden, dass sie in der ersten Spalte (Anzahl der Versuche) der Ergebnisse 0 enthält. Zusätzlich kann die "Gesamtzahl der bisherigen Versuche (Zeiten)" erhalten werden, indem alle diese Teile mit "sum ()" addiert werden. -Die Größe der Datenvariation aufgrund des Zufalls jeder Einheit "xi" kann gemäß der obigen Formel beschrieben werden, aber die Wurzel ist __ "math.sqrt ()" __, __ "math.log ()" __ Jedes Protokoll kann mit ausgedrückt werden.

・ Ausführungsteil

-Für dieses Ergebnis wurden alle Maschinen so oft wie möglich getestet, aber die Maschinen mit einer geringen Wahrscheinlichkeit wurden nicht so oft getestet, und __ Abfall wird reduziert.

Über die Methode bisher

・ Bisher haben wir die fünf Methoden __ "gierige Methode", "ε-gierige Methode", "Soft-Max-Methode", "optimistische Anfangswertmethode" und "UCB1-Algorithmus" __ gesehen, aber es gibt keine klare Überlegenheit oder Unterlegenheit. Das Wichtigste ist, __ je nach Problem __ zu verwenden. ・ Als Voraussetzung für das verstärkte Lernen kann gesagt werden, dass __ "Suche und Verwendung in einer Kompromissbeziehung stehen" __. Das heißt, wenn die Anzahl der Suchvorgänge erhöht wird, wird die Anzahl der anderen als der optimalen Versuche erhöht, was die Verschwendung erhöht, und wenn die Anzahl der Verwendungen erhöht wird, erhöht sich das Risiko, nicht den besten auszuwählen.

• Wenn beispielsweise die Gesamtzahl der Versuche klein ist, ist die Suchrate groß __ "ε-gierige Methode" __ usw., da es einfach ist, die optimale Plattform zu finden, ist die Belohnungsrate tendenziell hoch. Wenn andererseits die Anzahl der Versuche groß ist, wird die Verschwendung der Suche groß. Die Suche kann intelligenter durchgeführt werden und die Anzahl der Verwendungen steigt. __ "UCB1-Algorithmus" __ hat tendenziell eine höhere Belohnungsrate. ・ Wenn alle Wahrscheinlichkeiten von Anfang an veröffentlicht wurden, muss der Agent nur die am besten geeignete ausprobieren, dh es besteht keine Notwendigkeit zu suchen, aber die Belohnung zu diesem Zeitpunkt und die oben genannten fünf Methoden wurden verwendet. Der Unterschied in den Belohnungen heißt __ "Bedauern" __.
• Von den fünf Methoden ist __ "UCB1-Algorithmus" __ diejenige, die das Bedauern minimieren kann.

・ Diagramm mit den Ergebnissen der einzelnen Methoden (im Fall eines N-Arm-Bandproblems)

Zusammenfassung

・ __ Stärkung des Lernens__ ist eine Methode, mit der unter bestimmten Bedingungen ein optimales Verhalten ermittelt werden soll. -In Verstärkungslernen gibt es einen Schauspieler __ "Agent" __. __N Problem mit Armbändern __ Führt die Aktion "Auswahl einer Plattform" aus. -Es gibt auch __ "Umgebung" , für die der Agent Maßnahmen ergreift. Die Umgebung ist in diesem Fall "der Prozess der Rückgabe, ob die Plattform ein Hit oder ein Miss ist". - "Belohnung" __ ist ein Index, der die Erwünschtheit der Aktionen des Agenten bewertet. Der Zweck des verstärkenden Lernens besteht darin, die Höhe dieser Belohnung zu maximieren.

• Als Methode zur Maximierung dieser Belohnung gibt es __ "gierige Methode", "ε-gierige Methode", "Soft-Max-Methode", "optimistische Anfangswertmethode" und "UCB1-Algorithmus" __. Bei jeder Methode wird zuerst __ "Suche" __ durchgeführt, um die Wahrscheinlichkeit jeder Plattform abzuschätzen, und dann wird __ "Verwendung" __ durchgeführt, um die optimale Plattform aus dem Ergebnis auszuwählen.

Diese Zeit ist vorbei. Vielen Dank für das Lesen bis zum Ende.