Kaggle – Ein Erfahrungsbericht. The Home of Data Science. So der selbstgewählte Titel der sich immer größerer Beliebtheit erfreuenden Website. Was sich dahinter verbirgt, sind ausgesuchte Herausforderungen auf dem Gebiet des maschinellen Lernens und der statistischen Datenanalyse, ein intellektuelles Kräftemessen mit Datenanalysten aus der gesamten Welt und, schafft man es unter die Besten drei, auch einer saftigen finanziellen Belohnung.
Kaggle bietet großen wie kleinen Firmen die Möglichkeit, ihre Daten in einem Wettbewerb den Analysten der Kaggle-Community zur Verfügung zu stellen. Diese werden auf eine bestimmte Frage hin untersucht, die Ergebnisse werden automatisch evaluiert und in eine Rangliste, das Leaderboard, eingetragen, so dass der Teilnehmer jederzeit sehen kann, wie er im Vergleich mit den Anderen sich gerade schlägt. Dabei finden sich unter Kaggles Kunden so bekannte Namen wie Facebook, Microsoft und General Electric.
A. Die Aufgabe
Wir stellten uns der Otto Group Product Classification Challenge. Unsere Aufgabe war die Einteilung von Produkten in die vom Otto Versand verwendeten neun Produktkategorien. Bisher wurde eine solche Einteilung für jedes neue Produkt manuell vorgenommen. Leider ergaben sich auf Grund der globalen Infrastruktur des Unternehmens hier einige Probleme. So wurden identische Produkte oftmals von verschiedenen Stellen innerhalb der Otto Group unterschiedlich klassifiziert. Eine Softwarelösung soll hier Abhilfe schaffen.
Die Daten
Gegeben waren zwei CSV-Dateien, eine, train.csv, welche die Trainingsmenge mit vorgegebenen Klassenlabels enthält, eine weitere, test.csv, als Testmenge ohne Labels. Wie der Name es schon nahelegt, dient die train.csv dazu, ein Modell zu trainieren und zu evaluieren, während die test.csv die Daten enthält, deren Klassenlabel vorhergesagt und zu Kaggle geschickt werden sollen. Auf Basis dieser Label wird dann die Güte der Lösung berechnet, und der entsprechende Score im Leaderboard eingetragen.
Jede Zeile der train.csv, welche jeweils ein Produkt repräsentiert, beginnt mit einer fortlaufenden Produktidentifikationsnummer, gefolgt von 93 natürlichen Zahlen, die jeweils Ausprägungen von 93 verschiedenen Eigenschaften repräsentieren. Was sich genau hinter diesen Eigenschaften verbirgt, und wie diese Zahlen semantisch zu verstehen sind, ist, genau wie die Bedeutung der einzelnen Klassenlabel, unbekannt. Damit ist es bedauerlicherweise nicht möglich, fachspezifisches Vorwissen in den Klassifikationsalgorithmus einzubringen, und wir müssen die Punkte als eine einfache Punktewolke in einem 93-dimensionalen reellen Vektorraum auffassen.
Die Metrik
Nehmen wir an, wir haben einen Algorithmus geschrieben, der uns zu jedem Produkt, also zu jeder Zeile der test.csv, ein Klassenlabel liefert. Die Güte unseres Algorithmus lässt sich nun ganz leicht bestimmen:
Wir zählen einfach, wie oft der Algorithmus das richtige Ergebnis geliefert hat, und teilen diese Zahl durch die Anzahl aller Ergebnisse, also durch die Anzahl aller Produkte. Dies liefert uns den relativen Anteil richtiger Antworten, die sogenannte Accuracy.
Die Otto Group Product Classification Challenge verlangte jedoch etwas anderes: Statt eines einzelnen Labels pro Produkt sollen neun relle Zahlen geliefert werden, die zu jeder Kategorie die Wahrscheinlichkeit angeben, dass das fragliche Produkt zu dieser Kategorie gehört.
Im obigen Beispiel würde das entsprechende Produkt mit einer Wahrscheinlichkeit von 0.41 zu Klasse 2, mit einer Wahrscheinlichkeit von 0.39 zu Klasse 3 gehören. Daraus lässt sich schließen, dass dieses Produkt am ehesten der Klasse 2 angehört, aber fast ebenso gut der Klasse 3 angehören könnte. Auch wenn dieses Beispiel rein hypothetisch ist, so zeigte sich in den Otto-Daten, dass auffallend viele Produkte der Klasse 3 über mehrere Modelle hinweg fäschlicherweise der Klasse 2 zugerechnet wurden. Somit leuchtet ein, dass diese Art der Klassifikation deutlich mehr Erkenntnisse über die Daten liefert als eine bloße Zuordnung.
Es stellt sich nun aber die Frage, wie wir die Güte einer solchen Antwort messen können. Eine Möglichkeit, dies zu tun, bietet sich auf den ersten Augenschein direkt an: Zu jeden Produkt wählen wir die Wahrscheinlichkeit, die der wahren Klasse entspricht, und summieren diese Wahrscheinlichkeiten auf. Anschließend teilen wir diese Summe durch die Anzahl aller Summanden, um einen über unterschiedlich große Mengen vergleichbaren Wert zu erhalten. Nehmen wir an, das oben abgebildete Beispielprodukt würde tatsächlich zu Klasse 3 gehören. Dann würde die zu Klasse 3 gehörige 0.39 in diese Summe mit einfließen.
Insgesamt erhalten wir so einen Score zwischen 0 und 1, wobei 1 bedeutet, dass die richtige Klasse bei jedem Produkt die Wahrscheinlichkeit 1 hat, und 0 bedeutet, dass die richtige Klasse bei jedem Produkt die Wahrscheinlichkeit 0 besitzt.
Dieser Ansatz hat leider einen bedeutsamen Mangel: Er verkennt die enorme Bedeutung einer fehlerhaften niedrigen Wahrscheinlichkeit. So würden wir bei obigem Beispiel vermuten, dass das Produkt zur Klasse 2 oder 3 gehört. Klasse 4, mit einer Wahrscheinlichkeit von gerade einmal 0.01, würden wir aber ausschließen. Sollte aber gerade dies die korrekte Klasse sein, so würde diese 0.01 in die evaluierende Summe eingehen. Wäre das Produkt ein Produkt der Klasse 2, der Klasse mit der höchsten Wahrscheinlichkeit, so würde der entsprechende Summand 0.41 sein. Damit beträgt die Differenz gerade einmal 0.4, was in einer Summe von Tausenden von Summanden keinen nennenswerten Unterschied macht. Wir müssen also einen Weg finden, einen solchen Fehler stärker zu gewichten. Eine Möglichkeit ist, statt der geschätzten Wahrscheinlichkeit deren Logarithmus zu betrachen.
Somit würde eine mit Wahrscheinlichkeit 1 richtig geschätzte Klasse mit dem Wert 0 in die Gesamtsumme eingehen, und niedrige Werte würden schnell stark in negative gehen. Zur Erinnerung: Es gilt log(1) = 0, und log(x) geht gegen minus unendlich wenn x gegen 0 geht. In diesem Fall würde also, wäre das Beispiel in Klasse 2, log(0.41) = -0.89 in die Summe eingehen, wäre das Beispiel in Klasse 4, log(0.01) = -4.6. Die Differenz dieser Werte beträgt nun -0.89 – (-4.6) = 3.71, was eine angemessenere Gewichtung darstellt.
Zum Schluss multipliziert man die so gebildete Gesamtsumme mit -1 um die ganzen unschönen Minuszeichen loszuwerden. So erhalten wir das sogenannte Multiclass Logloss, eine Zahl zwischen 0 und positiv unendlich, wobei eine 0 dem Ergebnis entspricht, indem jede korrekte Klasse mit Wahrscheinlichkeit 1 vorhergesagt wurde.
B. Die Tools
Nachdem wir nun wissen, welches Ziel erreicht werden soll, so müssen wir uns nun überlegen, welche Tools wir hierfür verwenden. Dabei haben wir uns für R und Julia entschieden. Azure Machine Learning, ein Cloud-basiertes Analysetool, welches von uns in operativen Anwendungen eingesetzt wird, schied aus lizenzrechtlichen Gründen aus.
R
R ist eine Programmiersprache und Umgebung für statistische Berechnungen, welche sich inzwischen als Standard in der Datenanalyse etabliert hat. Rs Stärken sind eine auf Datenmanipulation ausgelegte Syntax, freie Verfügbarkeit unter der GNU General Public License sowie ein Repository qualitativ hochwertiger Pakete für alle erdenklichen Aufgaben aus dem Bereich der Statistik und des maschinellen Lernens. Darüber hinaus ist R Standard in Forschung und Lehre, so dass eine große Anzahl statistischer Lehrbücher direkt mit R arbeitet.
Julia
Julia ist eine junge, aufstrebende Sprache für Scientific Computing. Ihre Syntax ähnelt Matlab, sie erreicht jedoch durch ihren auf dem LLVM-Framework aufbauenden JIT-Compiler eine Performance, die fast an C heran reicht. Im Gegensatz zu C bietet sie allerdings allen Komfort einer modernen Programmiersprache inklusive nativer Unterstützung von Parallelisierung und Cloud Computing, sowie einer komfortablen Kommandozeile, in welcher sich geschriebene Funktionen direkt ausprobieren lassen. Weiter lassen sich C- und Fortran-Funktionen ohne Wrapper direkt aus Julia heraus aufrufen.
C. Die Erfahrung
Jetzt, wo wir alles zusammen haben, können wir uns an die eigentliche Arbeit machen. Das heißt, wir wählen uns ein (am besten bereits in Software implementiertes) Klassifikationsverfahren, trainieren es auf den Daten mit bestimmten Parametern, evaluieren das so erhaltene Modell und versuchen dann, die Parameter zu optimieren.
Dem vorgebildeten Leser mag auffallen, dass ich hier zwei Punkte ausgelassen habe: das Vorverarbeiten der Daten, sowie die Kombination mehrerer Modelle. Die Vorverarbeitung der Daten hat sich im vorliegenden Fall, jedenfalls mit den Standardmethoden, als kontraproduktiv erwiesen, und für die Kombination mehrerer Modelle hat uns schlichtweg am Ende die Zeit gefehlt.
Auf zwei Verfahren, sowie ihre Implementierung, möchte ich hier genauer eingehen: die Support Vector Maschinen, sowie sie in libsvm implementiert sind, sowie geboostete Klassifikationsbäume, sowie sie in XGBoost implementiert sind.
libsvm
Kurz gesagt arbeitet einen Support Vector Maschine folgendermaßen: Sie bettet die gegebenen Datenpunkte (nichtlinear) in einen höherdimensionalen Raum ein, und trennt diese eingebetteten Punkte dann durch (lineare) Hyperebenen. Eine der zur Zeit beliebtesten Implementierungen dieses Verfahrens ist die C-Bibliothek libsvm.
Leider zeigte sich schnell das wesentliche Problem der SVMs: die Laufzeit. So benötigt libsvm zur trainieren auf nur einem Prozent der Datenmenge schon eine unangenehm lange Zeit; den Versuch, eine SVM auf allen Daten zu trainieren, haben wir nach 26 Stunden Rechenzeit abgebrochen. Zwar liefert libsvm auch ein Kommandozeilentool, welche zeitkritische Schritte über CUDA auf die CPU auslagert. Leider ist dieses Tool äußerst datenhungrig. Die Analyse des Quellcodes ergab, dass das Trainieren auf der gesamten Trainingsmenge etwa 60 GB an Arbeitsspeicher benötigen würde.
Die Support Vector Maschinen haben sich somit als für unsere Zwecke ungeeignet erwiesen.
XGBoost
Eine viel bessere Skalierbarkeit bietet XGBoost. Dieses Programmpaket verwendet geboostete Klassifikationsbäume zur Zuordnung der Klassen. Dahinter stehen zwei Konzepte: Klassifikationsbäume und Boosting.
Zunächst zu den Klassifikationsbäumen. Auch wenn über die Jahre mehrere Versionen dieses Konzepts ausgearbeitet wurden, so ist die grundlegende Idee doch immer die Gleiche: Wähle eines der Features, und trenne die Trainingsmenge an Hand der jeweiligen Ausprägung dieses Features in zwei Klassen. Dieses Splitting wird solange wiederholt, bis ein bestimmtes Abbruchkriterium erfüllt ist, mit welchem den aktuell betrachteten Datenpunkten eine Klasse zugeordnet wird. So erhalten wir einen binären Baum, dessen Blätter paarweise disjunkte Mengen von Datenpunkten enthalten und diesen eine Klasse zuordnen. Boosting ist eine Methode, einen weiteren Baum auf den Klassifikationsfehlern zu trainieren, und die so erhaltenen Bäume zu einem Gesamtmodell zu kombinieren.
XGBoost besitzt 6 verschiedene Parameter, deren Wahl für die Güte des Ergebnisses äußerst kritisch ist. Leider existieren zur Zeit meines Wissens nach keine Methoden, diese Parameter zu schätzen. Von daher bieten sich zwei Verfahren zur Parametersuche an: die Gridsuche und die manuelle Suche.
Gridsuche
Die Gridsuche ist denkbar einfach: Wir wählen für jeden der sechs Parameter einige Werte, und evaluieren jede der sich ergebenden Kombinationen. Offensichtlich ergeben sich so sehr schnell sehr viele Modelle. Will man seine Ergebnisse also in absehbarer Zeit erhalten kommt man um die Verwendung mehrerer Rechner nicht herum.
Eine solche Parallelisierung konnten wir durch die Verwendung von GNU Parallel erreichen. GNU Parallel koordiniert die Ausführung mehrerer Prozesse eines Programms mit unterschiedlichen Parametern auf mehreren Rechnern, und führt die jeweiligen Ausgaben zusammen. Dazu muss vorher ein passwortloser SSH-Zugang zu den entsprechenden Maschinen eingerichtet werden, welchen wir durch eine kryptographische public key authentication erreichen konnten.
Da die Rechenzeit in der Anzahl der Parameter exponentiell wächst, in der Anzahl der zur Verfügung stehenden Maschinen aber nur linear schrumpft, sollte das Augenmerk bei der Gridsuche auf der Bestimmung einer Größenordnung der Parameter liegen. So kann es sein, dass für Parameter 1 bei den vorliegenden Daten nur Werte zwischen 0 und 1 gute Ergebnisse liegen, Parameter zwei aber größer als 100.000 sein sollte. Nachdem die Größenordnungen bekannt sind kann man damit beginnen, die Parameter manuell zu tunen.
Manuelle Suche
Bei der manuellen Suche testen wir immer nur eine einzige Parameterwahl auf ihre Performance, und überlegen dann, wie wir die Parameter ein wenig verbessern können. Dazu ist es nötig, ihre Bedeutung genau verstanden zu haben. Eine genaue Diskussion der XGBoost-Parameter möchte ich hier jetzt niemandem antun. Einige erhöhen die Komplexität des Modells und machen es somit anfällig für Overfitting. Andere beschränken diese Komplexität und sorgen für robustere Vorhersagen. Wieder andere lassen die Komplexität unverändert, bilden aber eine zufällige Teilmenge der Trainingsdaten für jeden Boostingschritt und wirken so dem Overfitting entgegen.
D. Ergebnis
Am Ende erhielten wir einen Score von 0.44, welcher zwar immer noch ein gutes Stück vom besten Ergebnis, 0.38, entfernt war, uns aber bei den besten 20% auf dem Leaderboard platzierte.
Nach dieser Erfahrung können wir jedem, der sich an einer Klassifikation versucht, nur dazu raten, sich mit seinen Modellen vertraut zu machen. Ein bloßes drauf-los-Raten ist beim manuellen Feintuning zum Scheitern verurteilt.
Insgesamt lässt sich festhalten, dass sowohl R als auch Julia sich in der Praxis bewährt haben, wobei R allerdings nach wie vor das für derartige Datenanalysen führende Werkzeug darstellt.