09. Dec 2020
Mit KI zum Bundesliga-Tippkönig – ein Deepdive
Wie wir mit Machine Learning die Ergebnisse des nächsten Bundesligaspieltags vorhersagen
Einleitung
Jedes Jahr stellen wir bei Accso in einer internen Bundesligatipprunde unser Fußballfachwissen unter Beweis. Die besten Accsonauten erwarten am Ende Ruhm und Ehre (und tolle Preise). Nachdem wir einzeln in den vergangenen Saisons mehr oder weniger erfolgreich am Tippspiel teilgenommen haben, hat sich die Machine Learning Community überlegt, eine Künstliche Intelligenz mit ins Rennen zu schicken. Unter dem Namen MILK (Machine Intelligence Learns Kicktipp) soll diese teilnehmen und für jedes Spiel das Endergebnis vorhersagen. Wie genau wir MILK erstellt haben, wo die Herausforderungen lagen und ob man mit den Vorhersagen von MILK bei Geldwetten reich werden kann, erfahrt ihr in diesem Artikel.
Ein grober Fahrplan
Im Laufe der kommenden Saison wollen wir testen, wie gut man bei einer Sportart wie Fußball den Ausgang eines Spiels vorhersagen kann. Es finden sich viele Beispiele, bei denen dies bei der Vorhersage der Tendenz (Sieg, Unentschieden oder Niederlage) gut funktioniert hat. Die Vorhersage von konkreten Ergebnissen ist durchaus komplexer und unterliegt vielen zufälligen Einflüssen. Zudem ist der Ergebnisraum bei diesem Ansatz viel größer, da es nicht nur drei mögliche Ausgänge gibt, sondern sehr viele und immer auch mal besondere Ausreißer (Man denke an die WM 2014: Deutschland gegen Brasilien ;)).
Zur Vorhersage von Spielausgängen brauchen wir ein Modell mit Ein- und Ausgabe. Für die Eingabe werden Informationen verwendet, über die wir vor Spielbeginn bereits verfügen. Wir gehen im weiteren Verlauf des Artikels genauer auf die Daten ein. Die Eingabe durchläuft das Modell in vielen Schritten. Am Ende erhalten wir eine Ausgabe – in unserem Fall den Spielstand zum Ende des Spiels.
Vorgehensweise nach CRISP-DM
Wie in fast jedem Machine Learning Problem haben wir uns am CRISP-DM (Cross Industry Standard Process for Data Mining) Prozess orientiert. Dieser beschreibt die typischen Stufen, die ein solches Projekt durchlebt. Im Business Understanding geht es darum die Problemstellung und den Businesskontext zu verstehen. Dieser Schritt ist in unserem Fall sehr intuitiv, sodass wir direkt mit dem Data Understanding beginnen konnten. Dies beginnt mit der Sammlung von Daten, bei denen wir davon ausgehen, dass sie für die Vorhersage der Spielergebnisse relevant sind. Anschließend gilt es, ein Verständnis dieser Daten zu erhalten. Gibt es bestimmte Muster, nach denen ein Team immer gewinnt oder lassen sich in bestimmten Fällen die Tore von einem bzw. beiden Teams zuverlässig vorhersagen? Da die Daten Fehler, Ausreißer oder auch Lücken enthalten können, müssen sie so verarbeitet werden, dass sie von einem Modell verwendet werden können. Dies geschieht im Schritt der Data Preparation. Danach werden im Modeling mehrere Modelle mithilfe der Daten trainiert. Diese Modelle müssen anschließend evaluiert werden. Sollte kein Modell in der Evaluation eine ausreichende Performance aufweisen, gibt es die Möglichkeit, mit dem bis hierher erlangten Wissen nochmal im Business- und Data-Understanding nachzuschärfen oder andere Ansätze für Data Preparation und Modeling zu verwenden. Modelle, die eine zufriedenstellende Performance liefern, können im nächsten Schritt im Deployment produktiv eingesetzt werden.
Data Understanding – Welche Daten haben wir verwendet?
Am Anfang verwendeten wir unterschiedliche APIs und heruntergeladene csv Dateien von Webseiten, um Daten über Spiele zu erhalten. Darunter waren neben den offensichtlichen Informationen wie Heim- und Auswärtsteam oder Datum auch die Spielerperformance. Durch die Heterogenität der Daten ergab sich für uns ein großes Problem. Wir hatten zwar eine große Menge an Daten, aber da z. B. die Teamnamen inkonsistent waren, ließen sie sich nicht ohne hohen manuellen Aufwand zusammenführen. Letztendlich haben wir uns für eine kostenpflichtige API entschieden. Diese API hat es uns ermöglicht, für über 650 Ligen und Turniere die Ergebnisse zu erhalten. Ab dem Jahr 2016 haben wir zusätzlich Informationen gesammelt, z. B. zum Spielverlauf (was wann genau im Spiel passiert ist (Tore, gelbe/rote Karten, Fouls)) oder zur Performance der Spieler am jeweiligen Spieltag.
Insgesamt liegen Daten zu ungefähr 500.000 Spielen vor. Aus diesen Informationen generierten wir im Rahmen der Data Preparation anschließend Features, die als Eingabe für das Modell dienen.
Data Preparation
Wir verwenden aktuell 56 unterschiedliche Features als Eingabe.
Zu den Features gehören unter anderem die Elo, Angriffs- und Verteidigungsstärke, die Performance, Tore und Gegentore der letzten sieben Spiele beider Teams sowie die Punkte in der Tabelle. Diese Werte werden übergreifend für alle Ligen und Turniere berechnet. Da es bei Turnieren zu Verlängerung und Elfmeterschießen kommen kann, werden Turnierspiele durch ein eigenes Feature gekennzeichnet.
Die drei Features, die wir im Folgenden genauer vorstellen wollen, sind die Elo sowie die Angriffs- und Verteidigungsstärke.
Elo
Der Begriff Elo kommt ursprünglich aus dem Schach und ist ein Bewertungssystem für Spieler. Wir verwenden die Elo für die Teams. Die Grundidee der Berechnung haben wir von der Fußballseite clubelo [1]. Bei der Berechnung wird zuerst geschaut, welches Team potenziell gewinnt (Team mit der höheren Elo). Da Heimteams öfter gewinnen, erhalten diese eine erhöhte Elo bei der Berechnung. Das Ergebnis (outcomeexpected) ist dabei eine Zahl zwischen 0 und 1. Diese Zahl gibt basierend auf der Elo die Wahrscheinlichkeit an, mit der das Heimteam gewinnt.
Sobald ein Spiel beendet ist, können wir den Wert für outcome_true setzen:
Des Weiteren wollten wir in Betracht ziehen, dass bei einem hohen Torunterschied die verlierende Mannschaft vermutlich nicht mehr ihr volles Potenzial gibt. Deswegen verringern wir den Elo Verlust pro zusätzlichem Tor nach zwei Toren Unterschied. Dies wird mithilfe der „Margin of victory“ abgebildet. Diese Idee haben wir von Stuart Lacy [2] übernommen. Die „Margin of victory“ ist dabei nicht nur abhängig von der Anzahl der Tore, sondern auch von der Elodifferenz. Wir haben die Formel mit fünf beispielhaften Elo Differenzen visualisiert und wie es aussehen würde, wenn wir nur die Tordifferenz nehmen würden. Bei hohen negativen Elodifferenzen kann es dazu kommen, das die ersten Tore höher gewichtet werden.
Zuletzt werden die berechneten Werte für outcome_expected, marginofvictory und elo_gain miteinander verrechnet, um den Elo-Gewinn/Verlust der jeweiligen Mannschaft zu berechnen. Wie in den meisten Fußballelo Implementierungen haben wir uns dafür entschieden, die Gewichtung eines Ligaspiels auf k = 20 zu setzen. Zusätzlich hat sich beim Analysieren der Daten gezeigt, dass es von Vorteil ist, Turnierspiele höher zu gewichten. Dies kann daran liegen, das beide Teams bei Tunierspielen ihr volles Potenzial geben, um nicht auszuscheiden.
Angriffs- und Verteidigungsstärke
Die Angriffs- und Verteidigungsstärke soll im Gegensatz zur Elo Aufschluss geben, wie torgefährlich (attack) / abwehrstark (defend) eine Mannschaft ist. Dafür wird dieses Feature ähnlich wie die Elo nach jedem Spiel aktualisiert und nicht komplett neu berechnet. Das heißt, der letzte Wert der Offensive dient als Basis für den neuen Wert und wird je nach der Performance des vorherigen Spiels erhöht oder verringert. Die genauen Formeln sind hier zusehen.
Alpha gibt an, wie stark der neu berechnete Anteil gewichtet werden soll. Ratio dahingegen beschreibt, zu welchem Teil die Offensive bzw. Defensive der anderen Mannschaft miteinbezogen wird. Attack wird dabei auf [0, ∞) und defend auf (-∞, 0] abgebildet. In beiden Fällen ist ein größerer Wert besser. Um das ganze etwas deutlicher machen, hier ein Beispiel:
Die Anzahl der geschossenen Tore des Teams war höher als ihr Attack-Score, weswegen der Offensiv-Wert steigt. Zudem hat das Team weniger Tore kassiert, weshalb der Defensiv-Wert auch steigt (beachten: Defensiv-Wert ist negativ).
Datennormalisierung / Standardisierung
Ein wichtiger Punkt der CRISP-DM Data Preparation Phase ist die Normalisierung und Standardisierung. Normalisieren bezeichnet das Skalieren der Variablen auf einen Zahlenbereich. Bei der Standardisierung werden die Daten so transformiert, das der Mittelwert gleich 0 und die Standardabweichung gleich 1 ist [3].
Wir probierten dabei unterschiedliche Methoden. Für das Normalisieren verwendeten wir min_max und tan-h und für die Standardisierung den Z-Score. Wir gehen im weiteren Verlauf des Artikels nicht weiter auf die Berechnung dieser Methoden ein, da sie für die folgenden Erklärungen nebensächlich sind. Welche Auswirkungen die unterschiedlichen Normalisierungen/Standardisierung auf die Daten haben, sieht man in den folgenden Grafiken. In diesem Beispiel bildet der minmax die Daten in Bereich 0 – 1 ab, tan-h auf 0,37 – 0,39 und der Z-Score auf -3,5 – 3,5. Für unseren Anwendungszweck hat der Z-Score die größte Genauigkeitssteigerung gebracht.
Bei jeder Methode mussten wir uns zusätzlich entscheiden, wie wir die Daten normalisieren. Möglichkeiten waren über alle Daten, über jede Saison, über jede Liga oder über jede Liga und Saison. Schnell ist uns aufgefallen, dass wir nicht für jede Saison normalisieren können, da ansonsten Saisons, die gerade erst angefangen haben, stark durch Ausreißer belastet sind (wie z. B. in der Saison 2020/21, Spieltag 1, Bayern gegen Schalke 8:0). Als wir über alle Daten normalisiert haben, wurden vor allem bei Ligen mit weniger Spielen die Vorhersage schlechter, da in diesen oft weniger Punkte erzielt werden. Deswegen entschieden wir uns letztendlich zur Normalisierung über alle Saisons einer Liga.
unnormalized | z-score , minmax | tan-h
Modelling
Aktuell verwenden wir als Modell ein Neuronales Netz (NN). Das NN ist vom menschlichen Gehirn inspiriert und besteht aus vielen verbundenen Einheiten (Neuronen). Diese Verbindungen können unterschiedliche Gewichte haben und werden beim Trainieren des Modells verändert. Das NN in Abbildung 7 besteht aus 4 Layern, einem Input und Output sowie zwei Hidden Layern. Die Anzahl der Layer und der Neuronen ist variabel.
Neuronale Netze waren nicht unsere erste Wahl, da sie große Datenmengen zum Trainieren benötigen und die Suche nach den optimalen Hyperparametern zeitintensiv ist. Zuerst haben wir versucht, die Daten mithilfe von DecisionTrees und RandomForest darzustellen. Diese führten zu keinen guten Ergebnissen. Auch Adaboost und k-Nearest Neighbors lieferten keine besseren Ergebnisse. Deswegen haben wir uns letztendlich für ein NN entschieden. Es gibt noch weitere Optionen wie z. B. LSTM oder Reinforcement Learning, welche im Rahmen einer zukünftigen Weiterentwicklung betrachtet werden könnten. Die durchschnittlichen Punkte, die wir pro Spiel in der Bundesligatipprunde mit den verschiedenen Modellen erhalten, sind hier zu sehen:
Ein Punktunterschied von 0.07 wirkt nicht groß, doch bei 306 Spielen erhalten wir mit NNs über 20 Punkte mehr gegenüber Adaboost.
Das neuronale Netz haben wir mithilfe von PyTorch erstellt. Um die optimalen Hyperparameter für unser NN zu finden, haben wir RandomSearch verwendet. Hyperparamter sind Parameter, die vor dem Trainieren des Modells eingestellt werden und sich während des Trainings nicht ändern. Unsere Hyperparameter waren die Anzahl der Hidden Layer, deren jeweilige Größe, der Optimizer und die Lossfunktion.
Zusätzlich verwendeten wir beim Trainieren Tensorboard, um einen besseren Überblick über die unterschiedlichen Modelle mit gleichen Hyperparameter zu erhalten. Im folgenden Bild ist ein Ausschnitt von Tensorboard zu sehen. In dem Bild sind die Goals_Acc, Loss, Score_2_3_4_5 und Winner_Acc zu sehen. Goals_Acc gibt an, wie oft wir den richtigen Torstand für ein Team vorhersagen. Loss stellt die Information über die Lossfunktion dar. Score_2_3_4_5 gibt Punkte an, die wir im Durchschnitt pro Spiel in unserer internen Bundesligatipprunde erhalten und Winner_Acc gibt an, wie oft wir den richtigen Gewinner vorhersagen. Jede Farbe steht für ein Model, dessen Performance hier sowohl auf dem Training Set (oberer Graph) als auch auf dem Validation Set (unterer Graph) dargestellt wird.
Ergebnisse
Nach Spieltag 10 befindet sich MILK auf Platz 11/31 in der internen Bundesligatipprunde von Accso. MILK hat 31 Punkte Abstand zum ersten Platz. Die richtige Tendenz, wer gewinnt, liegt bei 46.6 % und das exakte Ergebnis konnte bisher in 8 von 90 Spielen vorhergesagt werden. Zum Vergleich der erste Platz hat 15 von 90 Spielen korrekt vorhergesagt. Der genaue Platzierungsverlauf ist in Abbildung 9 zu sehen. In Abbildung 10 sind die Punkte pro Spieltag dargestellt. Aktuell liegt MILK, mit 11.1 Punkten pro Spieltag, 0.5 Punkte unter dem Durchschnitt von dem Validation-Set.
Es gibt einige verbesserungsbedürftige Aspekte, z. B. kann MILK keine 0 Tore vorhersagen. Weshalb wir bis zum 10. Spieltag in 24 Spielen nicht das korrekte Ergebnis vorhersagen hätten können, da mindestens ein Mannschaft kein Tor geschossen hat. Zwar sind die Ergebnisse ausreichend für unsere interne Kicktipprunde, doch wenn wir Geld wetten würden, würden wir langfristig Verluste einfahren.
In zukünftigen Versionen wollen wir uns vor allem den Einfluss der Spieler auf das Spielgeschehen genauer anschauen. Was passiert, z. B. wenn der wichtigste Spieler der Mannschaft sich verletzt hat oder nicht spielen kann? Diese Informationen sind zwar vor Spielbeginn bereits vorhanden, wurden aber von uns bisher nicht berücksichtigt.
Quellen:
[1] – http://clubelo.com/System
[2] – https://stuartlacy.co.uk/2017/...
