Rolf Anweiler
Den Wald vor lauter Bäumen nicht sehen: Machine Learning und die Fußball-Weltmeisterschaft
Die Fußball WM 2018 in Russland
Liebe Fußballfreunde, das ging jetzt schnell, der amtierende Weltmeister Deutschland hat die Vorrunde der Fußballweltmeisterschaft 2018 nicht überstanden. Dies ist ein historischer Tiefpunkt, zum ersten Mal scheidet die Mannschaft in einer WM Vorrunde aus. Doch die Weltmeisterschaft lief weiter, auch ohne Deutschland und wir gratulieren unserem Nachbarn Frankreich zum Weltmeistertitel. Wer hätte das geahnt? Doch eine Möglichkeit dies schon vor dem Finale zu beantworten, ist das Heranziehen von historischen Daten. So nutzen zum Beispiel Buchmacher wie Bwin statistische Methoden, um Vorhersagen über Spielergebnisse zu treffen. Dies ist die Benchmark gegen den Wettbegeisterte auf der ganzen Welt ihr Glück versuchen. Ein weiterer Ansatz ist die Nutzung von Machine Learning, einem Sammelbegriff für Methoden, die Muster und Gesetzmäßigkeiten in Daten erkennen und so Aussagen oder Vorhersagen treffen können. Für solche Methoden gibt es eine Vielzahl möglicher Anwendungsfelder, zum Beispiel Spracherkennung, Aufdeckung von Kreditkartenbetrug oder eben die Vorhersage von Spielergebnissen. Zur Vorhersage der WM 2018 bedienen sich Wissenschaftler um Andreas Groll von der TU Dortmund der Random Forests Methode, einer der weitverbreitetsten Machine Learning Ansätze. Diese wollen wir im Folgenden genauer vorstellen.
WM-Vorhersagen mit Random Forests
Um Random Forests zu verstehen, gilt es zunächst mit einzelnen Entscheidungsbäumen vertraut zu sein. Ein Entscheidungsbaum kann dabei helfen, einzelne Objekte (Kunden, Firmen, Nationalmannschaften) anhand von Attributen (Einkommen, Profit, Ballbesitz), vorausschauend zu kategorisieren (Ausfallquote, Umsatzpotential, Weltmeister-Wahrscheinlichkeit). Es werden also historische Daten genutzt, um zukünftige Ereignisse vorherzusagen. Diese Daten müssen bereits kategorisiert sein. Es ist also bekannt, ob eine Mannschaft mit einem bestimmten Ballbesitz später Weltmeister wurde. Jeder Entscheidungsbaum beginnt mit einem Wurzelknoten, von hieraus zweigen Äste ab, die zu weiteren Knoten führen. An jedem Knoten wird eine Entscheidung getroffen. Entscheidungsbäume können alle Arten von Daten beinhalten. Man stelle sich zum Beispiel vor, dass man Nationalmannschaften in Weltmeister-Kandidaten und Außenseiter unterteilen will. In Abbildung 1 wird hierzu am Wurzelknoten zwischen Mannschaften mit hohem und solchen mit niedrigem FIFA-Ranking unterschieden.Daraufhin werden Mannschaften mit niedrigem FIFA-Ranking anhand der Anzahl ihrer Champions League-Spieler kategorisiert, um Rückschlüsse auf die zugrundeliegende Qualität ihrer Mannschaft zu erhalten. Hoch gerankte Mannschaften hingegen werden anhand der Testspiele kurz vor der WM kategorisiert, um einen möglichst aktuellen Eindruck ihrer Spielstärke zu erhalten. Zum Schluss ordnet der Entscheidungsbaum jede Mannschaft entweder als Weltmeister-Kandidat oder als Außenseiter ein.
Dieses stark vereinfachte Beispiel veranschaulicht einige Probleme beim Erstellen von Entscheidungsbäumen. Zum einen stellt sich die Frage, wie man die Schwellwerte eines Attributes, wie hoher oder niedriger Weltranglistenplatz festlegen sollte. Weiterhin steht oft eine große Zahl möglicher Attribute zur Verfügung. Beispielsweise lässt sich über Nationalmannschaftskader die Größe des Landes, die Nationalität des Trainers, allerlei Torstatistiken und vieles mehr zusammentragen. Auf welche Attribute sollte man sich beschränken und in welcher Reihenfolge sollten diese abgefragt werden, um dabei möglichst effizient eine hohe Trennschärfe zu erreichen? Zur Beantwortung dieser Fragen kommt die Mathematik zur Hilfe. Für jede neue Unterteilung anhand eines Attribut-Schwellwertes (Bspw. Team durchschnittlich jünger oder älter als 25) lässt sich die Reduktion der Unordnung in den vorab kategorisierten Trainingsdaten berechnen. Diese Reduktion gilt es zu maximieren, so dass am Ende auch unbekannte Objekte hinreichend kategorisiert werden können. Allerdings würde es enorme Rechenkapazitäten benötigen, um von allen Attributen alle Schwellwerte durchzutesten und so den perfekten Entscheidungsbaum zu finden. Zur Lösung dieses Problems bietet die Random Forests Methode einen vielversprechenden Ansatz.
2.2. Random Forests
In einem Random Forest wird eine große Anzahl solcher Entscheidungsbäume erzeugt. Für jeden Baum wird eine Stichprobe der gesamten verfügbaren Trainingsdaten gezogen. Im Beispiel in Abbildung 2 von Nationalmannschaftskadern. Diese Kader sind danach kategorisiert, ob sie es in die Top 3 der WM an der sie teilgenommen haben geschafft haben (Grün ja, Orange nein). Solch eine Kategorisierung muss nicht binär sein, Objekte können in eine beliebige Anzahl an Kategorien unterteilt werden. Nun beginnt man an der Wurzel. Es werden zufällig einige Attribute gewählt, auf die die Stichprobe reduziert wird. In unserem Beispiel ist das die durchschnittliche Tordifferenz in relevanten Testspielen sowie die Anzahl Champions League-Spieler im Kader. So entstehen Koordinatenpunkte, die jeweils einen historischen Nationalmannschaftskader repräsentieren, der an einer historischen WM teilgenommen hat. Für diese Kader liegt die Kategorisierung bereits vor. Nun werden für jeden Kader der x und y Wert als Schwellwerte getestet, man testet also 5*2 = 10 Werte. Für jeden Schwellwert berechnet man die Reduktion an Unordnung. Der Attributwert, der die Unordnung am stärksten reduziert wird nun zum Entscheidungskriterium. Dies wird in Abbildung 2 sichtbar. Hier stellt die blaue Linie, also die x-Koordinate Champions League-Spieler = 3 die beste Trennung zwischen orangen und grünen Punkten da.
Ein erster Knoten ist entstanden, der die Daten anhand des Entscheidungskriteriums aufteilt. Dieser Prozess wird dann an den neu entstandenen Knoten wiederholt. So werden die Daten immer genauer kategorisiert, solange bis die gewünschte Trennschärfe unter Berücksichtigung der verfügbaren Rechenleistung erreicht ist. Dieser Prozess wird mit mehreren Stichproben wiederholt, solange bis ein Wald aus Entscheidungsbäumen entsteht.
Wenn man diesem Wald ein bislang unbekanntes Objekt zuführt, wie den deutschen Nationalmannschaftskader für die WM in Russland, gibt jeder Baum eine bedingte Wahrscheinlichkeit dafür an, dass dieses Objekt zu einer bestimmten Kategorie gehört (Zum Beispiel Weltmeister-Kandidat oder Außenseiter). Schlussendlich wird der arithmetische Durchschnitt aus diesen Wahrscheinlichkeiten gebildet, so wird einem bislang unbekannten Nationalmannschaftskader eine Wahrscheinlichkeit dafür zugeordnet, Weltmeister zu werden. Diese Methode hat sich in einer Vielzahl von Anwendungsfeldern bewährt. Dies liegt stark vereinfacht daran, dass die Varianz jedes Baumes zwar hoch ist, jedoch keine statistische Verzerrung vorliegt, also die Vorhersagen aus den Trainingsdaten nicht systematisch verfälschte Ergebnisse produzieren. Die Varianzen der einzelnen Bäume sind also unabhängig voneinander und heben sich dadurch gegenseitig auf, so entsteht eine zuverlässige Vorhersage.
2.3. Anwendungsbeispiel WM
Diese Methode wird von den Wissenschaftlern der TU Dortmund dazu genutzt, die Ergebnisse einzelner Spiele vorherzusagen und so den Verlauf der WM abzuschätzen. Hierfür verwenden sie eine große Menge Attribute für jeden Nationalmannschaftskader. Unter anderem werden für das Land jedes Kaders wirtschaftliche Faktoren, wie BIP oder die Einwohnerzahl, und für den Kader selbst FIFA-Rankings, Buchmacherquoten und Heimvorteile gesammelt.
Ein großer Vorteil der Random Forests-Methode ist ihre Nachvollziehbarkeit und Transparenz. So zeigen die Ergebnisse der Studie, dass insbesondere Rankings und Quoten aus anderen Statistiken von der FIFA und Buchmachern, große Bedeutung in der Entscheidungsfindung zukommt, weiterhin stellen Wirtschaftsleistung und Anzahl an Champions League Spielern wichtige Faktoren da. Unwichtig sind hingegen die Nationalität des Trainers und die Einwohnerzahl eines Landes.
Dieser Ansatz sagte Spanien mit einer Wahrscheinlichkeit von 17,8% als Weltmeister vorher. Allerdings zeigt eine genauere Analyse, dass der gesamte Vorhersageprozess extrem dynamisch ist. Wenn zum Beispiel Deutschland bis ins Viertelfinale gekommen wäre, dann wäre das deutsche Team zum Favoriten geworden. Letzten Endes haben sich die starken Franzosen Mitte Juli beim Finale im Luzhniki Stadion in Moskau durchgesetzt.
3. Großes Potential
Dieses Beispiel zeigt nur eines der unzähligen Anwendungsfelder von Machine Learning und der Random Forests-Methode. Um die stetig zunehmenden Menge an Daten sinnvoll nutzen zu können, werden diese Algorithmen immer wichtiger. So lassen sich allerlei Dinge vorhersagen, sowohl im Fußball als auch im Geschäftskontext. Welche Werbung sollte ich wann und wo nutzen? Welcher Kunde verspricht ein großes Umsatzpotential und welcher wird sich als Betrüger herausstellen? Auch die SHS Viveon prüft, wie Machine Learning ihre Produkte in Zukunft noch besser machen kann. Bis dahin werden wir als echte Fußball Fans auf jeden Fall weiterhin bei den Spielen mitfiebern und unseren internationalen Kollegen aus der Schweiz, Spanien, Polen und insbesondere Russland die Daumen drücken.