Machine Learning unter der Haube: Wie funktioniert das wirklich?

Mit Q im ML-Gym: Wie funktioniert der Q-Lernen-Algorithmus?
Keine Kommentare

Machine Learning verstehen: Was ist Q-Lernen und wie funktioniert das? Um das zu verstehen, gehen wir mit dem Algorithmus heute ins Gym.

Hier geht es nicht um die bekannte Figur aus den James Bond Filmen, sondern darum den Q-Lernen Algorithmus besser zu verstehen [1], [2]. Beim Q-Lernen geht es grob darum, dass ein Agent zunächst durch Probieren von Aktionen lernt, welche Aktionen in welchem Zustand welche Belohnung erfährt. Die Zuweisung des Rewards (Belohnung), bzw. der Erwartung davon, erfolgt an den Zustand und die Aktion, die dazu geführt haben den Reward zu erhalten.

Um dieses Prinzip besser zu verstehen, bedienen wir uns einer Simulation einer Umgebung mit zugehöriger Aufgabe aus dem Gym der OpenAI, siehe auch [3]. Open AI ist eine gemeinnützige Organisation (genauer: ‚non-profit AI research company‘), die u. a. Tools für die Entwicklung von AI-Algorithmen liefert, in unserem Fall ein Testszenario in Form eines simplen Computerspiels.

Wir nutzen dabei das Taxispiel, bei dem der Spieler belohnt wird, wenn er schnell einen Gast aufnimmt und auch möglichst zügig ans Ziel bringt. Jeder einzelne Schritt erzeugt ein Reward von -1, das erfolgreiche Absetzen ein Reward von 20. Für illegales Aufnehmen und Absetzen erhält der Agent ein ‚Reward‘ von -10.

In Abbildung 1 ist das leere Taxi gelb dargestellt (a) und bewegt sich auf das Feld ‚R‘ zu (b), das einen Passagier beherbergt, was an der blauen Farbe zu erkennen ist. Danach wird in (c) der Passagier aufgenommen, wodurch das Taxi gün dargestellt wird.

Abbildung 1: Die Taxi Simulation in verschiedenen Zuständen

Am besten probiert man die Interaktion selber einmal unter anderem mit dem Python Skript aus (Listing 1), wobei man natürlich Python und das gym installiert haben muss, letzeres z. B. mit ‚pip install gym‘.

# Kleines Programm zum manuellen Testen der Taxi Umgebung
import gym
env = gym.make("Taxi-v2")

env.reset()
states = env.observation_space.n
actions = env.action_space.n
print('Possible actions: ', actions, '   possible states: ', states, '\n')

state2= 0
action = 0
env.env.s = 114   # initialer Status, setzt auch die Passagierposition
env.render()
while action != 'exit':
    action = input('Choose next action: 0(South), 1(North),2(East), 3(West), 4(Pickup), 5(Dropoff)(type exit to end)\n')
    if 0 <= int(action) < 6:
        state2, reward, done, info = env.step(int(action))
    else:
        print('no valid command')
    env.render()
    print('Status: ', state2, '\n')

Dabei wird auch der Statuswert, der zwischen 1 und 500 liegt angezeigt. Dieser Wert wird gebildet aus der x- und y-Position des Taxis, Lokation des Passagiers und des Ziels des Passagiers. Da es insgesamt sechs mögliche Aktionen gibt, wird unserer Q-Tabelle sechs Spalten und 500 Zeilen enthalten.

Hinweis: die grafische Darstellung der Taxisimulation erfolgt nicht auf jedem Terminal so wie gewünscht. Gute Ergebnisse leiferten das in PyCharm enthaltene Terminal sowie die bash shell, die mit Github geliefert wurde. Getestet unter Windows 10 mit Python 3.64.

ML Conference 2018

Making Enterprises Intelligent with Machine Learning

with Dr. Sebastian Wieczorek (SAP)

Machine Learning 101++ using Python

with Dr. Pieter Buteneers (Robovision)

Listing 2 visualisiert, wie sich die Tabelle füllt und stabilisiert. Wir speichern die Q-Tabelle nach jeweils 1000 Episoden und spielen dann die einzelnen Snapshots in einem Film ab. Damit erhalten wir einen visuellen Eindruck, ob und wie sich das Lernergebnis stabilisiert. Die letzte zwei Spalten erhalten dabei weniger hohe Werte, was daran liegt, dass dies die Aktionen ‚Passagier aufnehmen‘ und ‚Passagier absetzen‘ sind, die weniger oft vorkommen, da sie nur in ganz bestimmten Situationen Sinn ergeben.

Neben der visuellen Darstellung in Abbildung 2, 3 und 4 exportieren wir noch die Q-Tabelle in ein Spreadsheet (‚test_q.xlsx‘), wo wir dann einzelne Werte herausnehmen können, um zu sehen, dass die Werte zu unseren Erwartungen passen. Nehmen wir dort den Status 418, dann sehen wir einen sehr hohen Wert (Abb. 5).

# Kleines Programm zum Verstehen und Experimentieren von Q-Lernen nach Watkins
# Watkins, C.J.C.H. (1989), Learning from Delayed Rewards (Ph.D. thesis), Cambridge University 
# Zur Simulation einer Umgebung nutzen wir die Taxi Umgebung
# Diese Umgebung wurde vorgestellt von
# Thomas G. Dietterich (2000): „Hierarchical Reinforcement Learning with the MAX Q Value 
# Function Decomposition“ in Journal of Articial Intelligence Research 13 (2000) 227-303
import random
import gym
import numpy as np
import matplotlib.pyplot as plt
import xlsxwriter

# Erzeugen der Umgebung
env = gym.make("Taxi-v2")

# Konstantendefinition
episodes = 100000
frames = 100
gamma = 0.99
alpha = 0.01

# Initialisierungen
current_frame = 0
epsilon = 1
counter = 0
reward = 0 # momentaner reward
G = 0      # aufsummierter reward
# initialisieren der Umgebung
env.reset()
# Setzen des initialen Status
env.env.s = 114

# hier sehen wir wieviele Schritte benötigt werden,
# um das erste Mal ein Reward von 20 zu bekommen
while reward != 20:
    state, reward, done, info = env.step(env.action_space.sample())
    counter += 1
    env.render()
    print('Reward:', reward, 'Anzahl der Schritte:', counter, '\n')

dummy = input('hit any key \n')

# Vorbereiten der Anzeige der Q Tabelle
fig, ax = plt.subplots()
data = np.zeros((frames +1, env.observation_space.n, env.action_space.n))

# Initialisieren der Q Tabelle
Q = np.zeros([env.observation_space.n, env.action_space.n])

# Funktion zur Bestimmung der nächsten Aktion
# zu Beginn muss stärker exploriert werden,
# und spaeter eher das Wissen genutzt werden
def getAction(state):
    if random.random() < epsilon:
        return env.action_space.sample()
    else:
        return np.argmax(Q[state])

# Für jede Episode erfaehrt die Umgebung ein Reset
for episode in range(1,episodes):
    done = False
    G, reward = 0,0
    state = env.reset()
    while done != True:
        action = getAction(state)   # bestimme nächste Aktion
        # führe die Aktion asu und bestimme Folgestatus und Reward
        new_state, reward, done, info = env.step(action) 
        # Update der Q Tabelle
        Q[state,action] += alpha * (reward + gamma*np.max(Q[new_state]) - Q[state,action])
        # Summiere den Reward
        G += reward
        epsilon -= 0.001     # Verringere die Exploration
        state = new_state    # der neue Status wird der jetzige Status
    # nach tausend Episoden lassen wir uns den Gesamt Reward ausgeben
    if episode % 1000 == 0:
        print('Episode {} Gesamt Reward: {}'.format(episode,G))
        data[current_frame] = Q # wir speichern uns den Stand der Q Tabelle
        current_frame += 1
#        print (Q)

# Anzeige der gemerkten Stände der Q Tabelle
for i in range(len(data)):
    ax.cla()
    my_img = data[i]
    ax.imshow(my_img, aspect = 'auto')
    ax.set_title("frame {}".format(i))
    if(i==99):
        input('press a key')
    plt.pause(0.2)  #

# Wir schreiben jetzt noch die Q Tabelle in eine XLSX Datei
workbook = xlsxwriter.Workbook('test_q.xlsx')
worksheet = workbook.add_worksheet()
worksheet.set_column('B:G', 12)
worksheet.add_table('B1:G501',  {'data': Q})
worksheet.write(0, 0, 'Status')
for i in range(env.observation_space.n):
    worksheet.write(i+1, 0, i)

workbook.close()

Abbildung 2

Abbildung 3

Abbildung 4: Darstellung der Q-Tabelle, die über die Zeit befüllt wird

Abbildung 5: Die finale Q-Tabelle wird zur Validierung auch in eine XLSX Datei gespeichert.

Das passt zu unserer Erwartung zum Status 418, wenn wir das Taxi-only Skript aufrufen, das in Abbildung 6 zu sehen ist. (Vorsicht: die Initialisierung muss gleich gewesen sein).

Das heißt, im Status 418, wo wir einen Passagier im Taxi haben (grün dargestellt) und wir an einer Ziellokation sind (das Y ist Magenta) sollte die richtige Aktion (Passagier absetzen, letzte Spalte) den höchsten Wert haben, was auch der Fall ist wie wir in dem Spreadsheet sehen.

Abbildung 6

Die Listings sollten hier nur als Anregung dienen, um selber zu experimentieren, da man so am besten einen Eindruck gewinnt. Wenn man das unten aufgeführte Skript ausführt, sieht man als erstes, wie der Agent sich rein zufällig bewegt und nur negativen Reward bekommt. Wenn der Agent dann das erste Mal rein zufällig richtig handelt, bekommt er ein Reward von 20. Damit wird dann die Kombination aus dem Zustand, wo das Taxi den Passagier noch hatte und der Aktion den Passagier abzusetzen, positiv bewertet, d. h. hier geht der Wert von ‚reward‘ ein. In späteren Versuchen wird dann auch die Aktion in diesen positiv bewerteten Zustand zu kommen, positiv bewertet, d. h. hier gibt es noch nicht den positiven Wert ‚reward‘, aber den gelernten (erwarteten reward): np.max(Q[new_state]). In dieser Weise setzt sich indirekt der Reward fort und die Q-Tabelle wird so befüllt.

Links & Literatur
Der Erfinder des Q-Lernens
[1] Watkins, C.J.C.H. (1989), Learning from Delayed Rewards (Ph.D. thesis), Cambridge University
Artikel zu Grundlagen des Maschinellen Lernens
[2] Bühlmeier, Andreas (2018), Die Wurzel des Machine Learnings – Mathematische Grundlagen für maschinelles Lernen, in Machine Learning, Entwickler Magazin Spezial Vol. 17, Software & Software Media GmbH
Taxi Umgebung zum Vergleich verschiedener Ansätze von Q-Lernen wurde vorgestellt in:
[3] Thomas G. Dietterich (2000), Hierarchical Reinforcement Learning with the MAX Q Value Function Decomposition, in Journal of Articial Intelligence Research 13 (2000) 227-303

Mehr zum Thema erfahren Sie im Entwickler Magazin Spezial vol. 17: Machine Learning

Entwickler Magazin Spezial Vol.17: Machine Learning

Unsere Redaktion empfiehlt:

Relevante Beiträge

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu:
X
- Gib Deinen Standort ein -
- or -