Neuronale Netze an Beispielen

[Behemoth]

Ich habe mich vor einiger Zeit mit Sungi ganz kurz über neuronale Netzwerke unterhalten, und wollte das hier nochmal ein bisschen aufgreifen. Das richtet sich hauptsächlich an Sungi, aber prinzipiell ist jeder eingeladen daran teilzuhaben.

Mein Problem damals war, dass ich mir noch nicht so richtig vorstellen konnte, wie neuronale Netze arbeiten. Ich denke ich habe die Grundlagen verstanden (im Prinzip Polynome von Polynomen dazu verwenden um Funktionen zu lernen). Was mich interessieren würde ist, wie man das denn jetzt genau einsetzt. Spontan fallen mir da zwei Fälle ein, in denen NN eingesetzt wurden, und ich fände es toll, wenn da jemand ein bisschen was dazu sagen könnte - muss jetzt nicht unbedingt eine genau Erklärung sein, aber paar Stichpunkte oder so wären cool.

1) Paar deutsche Stundenten haben einen Counter-Strike-Bot gebaut, dessen Wegfindungsroutinen NN benutzen. Man lässt den Bot einfach eine Weile in einer Map rumlaufen und irgendwann findet er sich dann darin zurecht. Wie geht das? ZB. wie würde denn ein passender Suchraum für sowas aussehen?

2) In Internetseiten/-shops, in denen Angebote der Form "Leute, die X mochten aber Y nicht, mochten auch Z." (beliebig viele X, Y und Z sozusagen). Ist das überhaupt ein Fall für ein NN? Und falls ja, wie setzt man da an?

Jo, keine Ahnung. Hab' da einfach nur hin und wieder drüber nachgedacht und bin nie so richtig drauf gekommen.

[Centurion]

Jetzt bin ich gespannt. Stand mit dem ganzen Machine-Learning-Krempel damals auch ziemlich auf Kriegsfuß, aber interessieren tut es mich auch sehr.

[Magic]

Finde ich prima, dass es dich interessiert, Jan. Zur Theorie der neuronalen Netze gibt es ja unglaublich viel zu sagen. Gehen wir einfach Schritt für Schritt vor, und bei weiteren Fragen, fragen. Mein Prof (NN ist sein Spezialgebiet) würde eh davon ausgehen, dass ich alles beantworten kann, also stelle ich mich dem gerne.

Ganz prinzipiell werden NNs für zwei Arten von Lernproblemen verwendet:
- lerne zu je einer Situation eine Bewertung, oder
- lerne zu je einer Situation einen "Vorschlag", typischerweise eine Aktion.

NNs mit Lernverfahren gibt's kostenlos zum download. Herausforderung bei der Verwendung von NNs ist, die gestelllte Aufgabe möglichst geeignet durch eine der beiden Varianten zu beschreiben (Stichwort: feature selection.) Je besser der Zusammenhang von Eingabe und Ausgabe ist und je kleiner der Eingaberaum (=Suchraum) ist, desto leichter lässt sich das Problem lernen - oder anders herum: desto kompliziertere Aufgaben lassen sich bei gleichem Zeitaufwand lernen.

NNs sind geeignet für Aufgaben, die nicht zu klein und nicht zu groß sind. Zu klein wäre beispielsweise Tic-Tac-Toe. Als Trainingsbeispiel zum Probieren zwar geeignet, in der Praxis würde sich aber eine vollständige Auflistung und Beantwortung aller Situationen aber empfehlen. Ein zu großes Problem ist z.B. die Wettervorhersage. NNs können zwar theoretisch jede mathematische Funktion erlernen, nach heutigem Wissensstand würde das Training einer Wettersimulation allerdings die Menschheit überdauern. Realistische herausfordernde Lernprobleme haben niedrig zweistellig viele reellwertige Eingaben.

Deine beiden Beispiele sind sehr passend, beinhalten zwei unterschiedliche Gründe, warum Fragestellungen komplex genug sein können, NNs zu bemühen. 1) hat viele, viele stetig zusammenhängende Eingaben (Position des Bots), bei denen kleine Unterschiede aber auch große Auswirkungen haben können (steht der Bot oben oder unten an einer Kante?). Eine vollständige Auflistung aller Situationen ist weder praktikabel noch sinnvoll. 2) hat dagegen diskrete, gut unterscheidbare Eingaben (A mag was, was B eben nicht mag). Die Anzahl der Situation steigt multiplikativ mit Anzahl Leute und Anzahl Güter. Sind diese zu klein, lohnt sich ein NN nicht.

Es gibt noch eine dritte Art von Lernaufgaben, z.B. mit einer Tennisball-Wurfanlage im Freien in einen Eimer treffen. Hier entsteht durch Wind eine Unsicherheit (Rauschen), so dass selbst bei gleichen Eingaben (Einstellungen der Maschine) unterschiedliche Ergebnisse erzielt werden. Die Komplexität der Aufgabe ist also durch das Rauschen erhöht. Mischformen sind natürlich üblich.

Ich schicke mal den Text ab und schreibe weiter.

[Magic]

Ein Lernmuster für Beispiel 2 könnte z.B. so aussehen:
- Eingabe: X mag Y1. X mag Y2. X mag Y3. X mag Y4 nicht. X mag Y5 nicht. (Binäre Eingabeneuronen.)
- Ausgabe: (X mag Y6)=1. (Reelles Ausgabeneuron.)

Noch eins:
- Eingabe: X mag Y1. X mag Y2 nicht. X mag Y3. X mag Y4 nicht. X mag Y5.
- Ausgabe: (X mag Y6)=0.

Auswertung des NNs: Wenn für
- Eingabe: X mag Y1. X mag Y2. X mag Y3. X mag Y4. X mag Y5 nicht.
- Ausgabe > 0.5, dann schreibe "Leute, die Y1 Y2 Y3 Y4 aber nicht Y5 mochten, mochten auch Y6."

Hier habe ich versucht, einen Zusammenhang von Y1-Y5 auf Y6 zu erklären. Warum aber nicht anders vorgehen?

- Eingabe: X mag Y1. X mag Y2. X mag Y3. X mag Y4 nicht. X mag Y5 nicht. X mag Y6 nicht. (Binäre Eingabeneuronen.)
- Ausgabe: Trifft auf 3% unserer Kunden zu. (Reelles Ausgabeneuron.)

- Eingabe: X mag Y1. X mag Y2. X mag Y3. X mag Y4. X mag Y5 nicht. X mag Y6 nicht.
- Ausgabe: Trifft auf 1% unserer Kunden zu.

Kunde hat bereits angegeben, dass er Y1 Y2 Y3 Y4 aber nicht Y5 mag. Wenn für
- Eingabe: X mag Y1. X mag Y2. X mag Y3. X mag Y4. X mag Y5 nicht. X mag Y6.
- Ausgabe > (0.5)^6, dann schreibe "Leute, die Y1 Y2 Y3 Y4 aber nicht Y5 mochten, mochten auch Y6."

[Behemoth]

Ok, ich glaube, so weit kann ich folgen. Wie ist denn das jetzt aber, wenn wir 100000 Benutzer X und 1000 Artikel Y haben? Angenommen jeder Benutzer hat nur ein paar (zB. 3 bis 5) Y angegeben, die er mag und ein paar, die er nicht mag. Jetzt möchte ich aus dem großen Pool das (oder mehrere) Y herauspicken, das er am ehesten auch mag. Sprich, die Eingaben überschneiden sich nur teilweise, wenn überhaupt. Ist das dann noch ein Fall für ein NN? Oder muss man da tricksen, wie zB. Musikrichtung statt tatsächlicher CD als Eingabe verwenden?

Prinzipiell hätte ich ja einen Suchraum mit 1000 Parametern, aber wie Du schon sagtest, ist das eher zuviel für ein NN. Wie kann man das reduzieren oder trotzdem verwenden?

[Magic]

Bei Beispiel 1 weiß ich nicht, wie diese Bots tatsächlich realisiert werden. Denkbar ist grundsätzlich etwas in der Form:
- Eingabe: Position des Bots, Position des Ziels
- Ausgabe: Bewege Bot in Richtung so und so.

Das Lernen ist in diesem Fall dadurch erschwert, dass der Bot auf Pfaden lernen muss, d.h. erst wenn er das Ziel tatsächlich erreicht, lassen sich die Einzelaktionen bewerten. Tatsächlich ist es dadurch oft so, dass als Ausgabe eben nicht die "beste Aktion" gelernt wird, sondern die Bewertung der Situation. Also:
- Eingabe: Position des Bots, Position des Ziels
- Ausgabe: Bewertung des Erreichen des Ziels.

Ist dann die Position des Bots und des Ziel konkret gegeben, lässt sich das NN fragen: Was sind die Bewertungen für die Folgesituationen auf all die folgenden Aktionen a1,a2,a3,...,a999? - Aha, dann nehme ich die Aktion mit der besten Bewertung.

Ist das dann noch ein Fall für ein NN? Oder muss man da tricksen, wie zB. Musikrichtung statt tatsächlicher CD als Eingabe verwenden?

Prinzipiell hätte ich ja einen Suchraum mit 1000 Parametern, aber wie Du schon sagtest, ist das eher zuviel für ein NN. Wie kann man das reduzieren oder trotzdem verwenden?

Ich glaube, du hast es voll durchschaut. Tatsächlich wären bei so vielen Parametern die Anzahl der Stichproben wohl zu klein. Das "Tricksen" ist eben die feature selection, also nicht jede Eingabe dem NN präsentieren, so wie sie vorliegt, sondern ausgesuchte relevante Informationen.

[Magic]

Hast du denn vor, mal eins zu schreiben oder anzuwenden, Jan? Ich hatte es mir mal früher für NwN2 überlegt. Die interessanten Aufgabenstellungen waren damals aber viel zu groß.

Gerade letztens hatte ich die Idee, ein Skript zu schreiben, dass einen Feuerball (Flugzeit berücksichtigen) auf ein bewegliches Ziel feuert (Bewegung berücksichtigen). Wäre auch leicht mit einem NN zu lernen. Wenn das Ziel beliebig Geschwindigkeit und Richtung ändern darf, könnte das NN sogar bessere Ergebnisse liefern als ein selbstgeschriebener Zielalgorithmus.

[Behemoth]

Wenn, dann eher um zu kucken, "wie das denn jetzt wirklich geht". Habe keinen konkreten Anwendungsfall oder sowas.

[LiMuBei]

Ich kenn mich mit NNs zu wenig aus um wirklich mitzureden, aber zu den Bots würde ich doch mal eine Bemerkung fallen lassen. Ich kann mir in diesem Szenario nicht vorstellen dass die Pfadfindung über ein NN geschieht, Standard bei den Computerspielen ist da ja A*. Ich würde eher in die Richtung tippen, die Sungi schon angerissen hat, das NN entscheidet welche Aktion (also z.B. welches nächste Ziel, welcher nächste Gegner etc.) durchgeführt werden soll. Vermutlich würde man hier dem Bot verschiedene Skills verpassen ("laufe nach A", "attackiere B", "bewache C"), als Eingabe die aktuelle Spielsituation (Position eigenes Team, Position Gegner, etc.) verwenden und dann versuchen die beste Aktion auszuwählen.

Lässt sich ja sogar beobachten im Spiel, denn die CS-Bots die ich kenne tun in ähnlichen Situation immer genau das gleiche. Wobei diese Aussage eigentlich keinen Wert hat, da ich nicht weiß ob die mit NNs arbeiten...

[Centurion]

Ich kenn mich mit NNs zu wenig aus um wirklich mitzureden, aber zu den Bots würde ich doch mal eine Bemerkung fallen lassen. Ich kann mir in diesem Szenario nicht vorstellen dass die Pfadfindung über ein NN geschieht, Standard bei den Computerspielen ist da ja A*. Ich würde eher in die Richtung tippen, die Sungi schon angerissen hat, das NN entscheidet welche Aktion (also z.B. welches nächste Ziel, welcher nächste Gegner etc.) durchgeführt werden soll. Vermutlich würde man hier dem Bot verschiedene Skills verpassen ("laufe nach A", "attackiere B", "bewache C"), als Eingabe die aktuelle Spielsituation (Position eigenes Team, Position Gegner, etc.) verwenden und dann versuchen die beste Aktion auszuwählen.

Mit so einem Ansatz kann man schon auch Pfade planen (ähnliches Stichwort: Artificial Potential Fields) aber da ist das Problem halt, dass solche Verfahren sich gerne in lokalen Minima verlaufen.

Meiner Meinung nach gibt es schon auch gute Gründe, gerade in einem Spiel wie CS kein A* zu benutzen. A* ist ja prinzipiell ein Graph-Algorithmus und braucht daher diskrete Knoten / Wegpunkte um arbeiten zu können. Das sorgt dann halt dafür, dass die Bots immer auf genau den gleichen Pfaden laufen, weil sie halt in einer diskreten Welt planen. Wenn man oft dieselbe Map spielt fällt das mit Sicherheit irgendwann unangenehm auf. Ich wüsste gerne mal, inwieweit die Bahnplanungs-Algorithmen bei Spielen wirklich dem Standard-A* entsprechen.

[Behemoth]

Meiner Meinung nach gibt es schon auch gute Gründe, gerade in einem Spiel wie CS kein A* zu benutzen. A* ist ja prinzipiell ein Graph-Algorithmus und braucht daher diskrete Knoten / Wegpunkte um arbeiten zu können. Das sorgt dann halt dafür, dass die Bots immer auf genau den gleichen Pfaden laufen, weil sie halt in einer diskreten Welt planen. Wenn man oft dieselbe Map spielt fällt das mit Sicherheit irgendwann unangenehm auf. Ich wüsste gerne mal, inwieweit die Bahnplanungs-Algorithmen bei Spielen wirklich dem Standard-A* entsprechen.

Tatsächlich werden in den meisten Spielen Graphalgorithmen für die Bahnplanung verwendet, oft mit ein paar zusätzlichen kleinen Kniffen um es weniger offensichtlich werden zu lassen (zB. zufällige Wegewahl zwischen zwei oder drei Pfaden obwohl einer teurer ist als der andere) - Unreal ist hier ein ganz gutes Beispiel.

Ich habe in meinem Beispiel aber ganz explizit einen auf NN basierenden Bot für CS gemeint. Da CS standardmäßig ohne Bots daher kommt, gibt es eine Reihe verschiedener, von der Community entwickelter Bots dafür. Die meisten setzen auch wieder auf Graphen, erfordern dann aber von den Spielern, dass sie in jeder Karte Wegpunkte plazieren. Der von mir beschriebene Bot tut das eben nicht, sondern "lernt die Karte auswendig" indem er sich darin bewegt.

[LiMuBei]

Grade in CS bietet sich A* da doch an, da ja selbst die menschlichen Spieler immer auf den genau gleichen Wegen laufen

[Magic]

Ich habe in meinem Beispiel aber ganz explizit einen auf NN basierenden Bot für CS gemeint. Da CS standardmäßig ohne Bots daher kommt, gibt es eine Reihe verschiedener, von der Community entwickelter Bots dafür. Die meisten setzen auch wieder auf Graphen, erfordern dann aber von den Spielern, dass sie in jeder Karte Wegpunkte plazieren. Der von mir beschriebene Bot tut das eben nicht, sondern "lernt die Karte auswendig" indem er sich darin bewegt.

Jupp, sehr guter Punkt. Bevor ich meinen Text zum CS-Bot schrieb, dachte ich zuerst auch an Wegpunkte in der Karte, auf Wegen und Kanten. Ein lernender Bot kommt aber tatsächlich ohne die aus, braucht letztendlich nur seine Position. Die Karte erforscht er dann beim Lernen. Z.B. könnte er dadurch lernen, wie weit es von jedem Punkt aus bis zur nächsten Wand und Kante ist, ohne Levelinformationen.

Wenn, dann eher um zu kucken, "wie das denn jetzt wirklich geht". Habe keinen konkreten Anwendungsfall oder sowas.

Das ist genau richtig zum Einstieg, denke ich. Viele Anwendungen hatte ich auch noch nicht. Glaube auch nicht, dass es sich oft anbietet ohne Forschungsziel oder gar Produkt. Ein sinnvolles Lernziel für ein NN heißt ja, es ist zu schwer es auszurechnen, aber dennoch besteht aus irgendeinem Grund nachhaltiges Interesse, das Problem zu lösen.

Zur Frage, ob das Kaufverhalten ein geeignetes Problem für NNs ist, habe ich im Grunde zu wenig Kenntnis bzw. sehe so auch nicht recht, wie man das am besten angeht. Hängt vermutlich von den verfügbaren Daten hab. Würde aber auch eher nein sagen und ein regelbasiertes System verwenden.

[Behemoth]

Hast du denn vor, mal eins zu schreiben oder anzuwenden, Jan? Ich hatte es mir mal früher für NwN2 überlegt. Die interessanten Aufgabenstellungen waren damals aber viel zu groß.

Gerade letztens hatte ich die Idee, ein Skript zu schreiben, dass einen Feuerball (Flugzeit berücksichtigen) auf ein bewegliches Ziel feuert (Bewegung berücksichtigen). Wäre auch leicht mit einem NN zu lernen. Wenn das Ziel beliebig Geschwindigkeit und Richtung ändern darf, könnte das NN sogar bessere Ergebnisse liefern als ein selbstgeschriebener Zielalgorithmus.

Hätte da einen ähnlichen Fall. Hatte eventuell überlegt 'n kleines Spielchen zu machen, wo man mit mit so Panzern rumfährt und sich gegenseitig abschießen muss, so ähnlich wie Onslaught bei Unreal Tournament oder sowas.

Problem wäre sowas in der Art: Wo muss ich mit meiner Kanone hinschießen um mein Ziel zu treffen.

(Kleinbuchstaben sind Skalare in |R, Großbuchstaben Vektoren in |R³)

Pz = Position des Ziels relativ zu mir
Vz = Geschwindigkeit des Ziels
v = Geschwindigkeit des Geschosses
G = Gewichtskraft

Position des Geschosses nach Zeit t wäre damit (wir vernachlässigen einfach mal die eigene Geschwindigkeit):
Pg(t) = t v X + t² G

||X|| = 1

Gesucht: X

Kann man jetzt algebraisch lösen, aber wie könnte man das mit'm NN machen?

[Magic]

Hey hey hey, super. Hab schon befürchtet, dass das Interesse nachgelassen hat. Bei mir war's in den letzten Tagen ein Zeitproblem. Nun nicht mehr, also widme ich mich dem demnächst. Dieses Wochenende fahre ich nach Karlsruhe. Eventuell findet sich ja Gelegenheit, darüber zu quatschen.