ML_Geron_02 Flashcards
Was ist ein Greedy Algorithmus?
Ein gieriger Algorithmus möchte in jedem Teilschritt so viel wie möglich im Hinblick auf die Vorgabe erreichen, beispielsweise ein Maximum oder ein Minimum. Eine Anwendung eines solchen Greedy-Algorithmus im täglichen Leben ist die beispielsweise die Herausgabe von Wechselgeld.
Die Vorgabe lautet: Nimm jeweils immer die größte Münze unter dem Zielwert und ziehe sie von diesem ab. Verfahre derart bis Zielwert gleich null. Will man beispielsweise 79 Cent zurückgeben, fängt der Algorithmus sofort mit dem höchsten Münzwert an und macht weiter, bis er den niedrigsten Münzwert erreicht hat, falls das nötig ist: 79 = 50 + 20 + 5 + 2 +2.
In diesem Anwendungsfall klappt das ausgezeichnet. Greedy-Algorithmen berechnen jeweils ein „lokales Optimum“ in jedem Schritt und können daher eventuell ein „globales Optimum“ verpassen. Der Anwender muss also über den Tellerrand hinausschauen, so wie im folgenden Beispiel: Der Zielwert sei 15. Es stehen Münzen mit den Werten 1, 5 und 11 (!) zur Verfügung.
Das „globale Optimum“ lautet: 15 = 5 + 5 + 5. Mit dem Greedy-Algorithmus wird das Optimum verfehlt: 15 = 11 + 1+ 1 + 1 + 1. Erzielt wird zwar der gleiche Wert, aber mit zwei Teilschritten mehr.
Man sieht also, dass der gierige Algorithmus nicht immer das globale Optimum erzielt, aber eine „gierige Heuristik“ dennoch lokal optimale Lösungen liefern kann, die sich einer global optimalen Lösung innerhalb einer vertretbaren Frist annähern. Das rückt die Greedy-Algorithmen, die inzwischen entwickelt worden sind, in die Nähe des Approximationsalgorithmus.
Was ist die ungefähre Tiefe eines mit 1 Million Datenpunkten (ohne Restriktionen) trainierten Entscheidungsbaums?
Die Tiefe eines ausbalancierten Binärbaums mit m Blättern ist log2 (m)3 , aufgerundet. Ein binärer Entscheidungsbaum (der wie alle Bäume in Scikit-Learn nur binäre Entscheidungen trifft) ist nach dem Trainieren mehr oder weniger ausbalanciert und enthält ein Blatt pro Trainingsdatenpunkt, falls er ohne Einschränkungen trainiert wird.
Wenn also der Trainingsdatensatz eine Million Datenpunkte enthält, hat der Binärbaum eine Tiefe von log2 (106) = 20 (in der Praxis ein wenig mehr, da der Baum nicht perfekt ausbalanciert sein wird).
Ist die Gini-Unreinheit eines Knotens im Allgemeinen geringer oder größer als die seines Elternteils? Ist sie im Allgemeinen kleiner/größer oder immer kleiner/ größer?
Die Gini-Unreinheit eines Knotens ist im Allgemeinen geringer als die des Elternknotens. Dies liegt daran, dass die Kostenfunktion des CART-Trainingsalgorithmus jeden Knoten so aufteilt, dass die gewichtete Summe der GiniUnreinheiten der Kinder minimal wird. Es ist aber möglich, dass ein Knoten eine höher Gini-Unreinheit als der Elternknoten erhält, solange dies durch eine geringe Gini-Unreinheit seines Geschwisterknotens ausgeglichen wird.
Sollte man versuchen, max depth zu senken, wenn ein Entscheidungsbaum einen Trainingsdatensatz overfittet?
Wenn ein Entscheidungsbaum die Trainingsdaten overfittet, sollten Sie eventuell max_depth verringern, da diese Einschränkung das Modell regularisiert.
Sollte man versuchen, die Eingabemerkmale zu skalieren, wenn ein Entscheidungsbaum die Trainingsdaten underfittet?
Entscheidungsbäume scheren sich nicht darum, ob die Trainingsdaten skaliert oder zentriert sind, dies ist eine ihrer angenehmen Eigenschaften. Wenn also ein Entscheidungsbaum die Trainingsdaten underfittet, ist Skalieren der Eingabemerkmale reine Zeitverschwendung.
Wenn es eine Stunde dauert, einen Entscheidungsbaum mit 1 Million Datenpunkten zu trainieren, wie lange etwa wird das Trainieren eines weiteren Baums mit 10 Millionen Datenpunkten dauern?
Die Komplexität der Berechnung beim Trainieren eines Entscheidungsbaums beträgt O(n × m log(m)). Wenn Sie also die Größe des Trainingsdatensatzes mit 10 multiplizieren, verlängert sich die Zeit zum Trainieren um den Faktor K = (n × 10m × log(10m)) / (n × m × log(m)) = 10 × log(10m) / log(m). Bei m = 106 beträgt K = 11.7, Sie können also mit einer Trainingsdauer von etwa 11.7 Stunden rechnen.
Wenn Ihr Trainingsdatensatz aus 100000 Datenpunkten besteht, beschleunigt das Setzen von presort=True das Trainieren?
Vorsortieren der Trainingsdaten verkürzt das Training nur, wenn der Datensatz kleiner als einige Tausend Datenpunkte ist. Wenn er 100000 Datenpunkte enthält, wird das Trainieren mit der Einstellung presort=True deutlich langsamer.
Bias führt zu…
Underfitting
Bias is the difference between the average prediction of our model and the correct value which we are trying to predict. Model with high bias pays very little attention to the training data and oversimplifies the model. It always leads to high error on training and test data.
Varianz führt zu …
Overfitting
Variance is the variability of model prediction for a given data point or a value which tells us spread of our data. Model with high variance pays a lot of attention to training data and does not generalize on the data which it hasn’t seen before. As a result, such models perform very well on training data but has high error rates on test data.
Wenn Sie fünf unterschiedliche Modelle auf den exakt gleichen Trainingsdaten trainiert haben und für alle eine Relevanz von 95% erzielen, lassen sich diese Modelle kombinieren, um ein noch besseres Ergebnis zu erhalten? Begründen Sie Ihre Antwort.
Wenn Sie fünf unterschiedliche Modelle trainiert haben und alle eine Relevanz von 95% erzielen, können Sie diese zu einem Ensemble kombinieren, was häufig zu noch besseren Ergebnissen führt.
Wenn die Modelle sich sehr stark unterscheiden, funktioniert es noch besser (z.B. ein SVM-Klassifikator, ein Entscheidungsbaum, ein Klassifikator mit logistischer Regression und so weiter).
Durch Trainieren auf unterschiedlichen Trainingsdaten lässt sich eine weitere Verbesserung erzielen (darum geht es beim Bagging und Pasting von Ensembles), aber es funktioniert auch ohne, solange die Modelle sehr unterschiedlich sind.
Worin unterscheiden sich Klassifikatoren mit Hard und Soft Voting?
Ein Klassifikator mit Hard Voting zählt einfach nur die Stimmen jedes Klassifikators im Ensemble und wählt die Kategorie aus, die die meisten Stimmen erhält.
Ein Klassifikator mit Soft Voting berechnet den Durchschnitt der geschätzten Wahrscheinlichkeiten für jede Kategorie und wählt die Kategorie mit der höchsten Wahrscheinlichkeit aus.
Damit erhalten Stimmen mit hoher Konfidenz mehr Gewicht, was oft besser funktioniert. Dies gelingt aber nur, wenn jeder Klassifikator zum Abschätzen von Wahrscheinlichkeiten in der Lage ist (z.B. bei SVM-Klassifikatoren in Scikit-Learn müssen Sie probability=True setzen).
Ist es möglich, das Trainieren eines Ensembles mit Bagging zu beschleunigen, indem man es auf mehrere Server verteilt? Wie sieht es bei Ensembles mit Pasting, Ensembles mit Boosting, Random Forests oder Ensembles mit Stacking aus?
Es ist möglich, das Trainieren eines Ensembles mit Bagging durch Verteilen auf mehrere Server zu beschleunigen, da jeder Prädiktor im Ensemble unabhängig von den anderen ist.
Aus dem gleichen Grund gilt dies auch für Ensembles mit Pasting und Random Forests. Dagegen baut jeder Prädiktor in einem Boosting-Ensemble auf dem vorigen Prädiktor auf, daher ist das Trainieren notwendigerweise sequenziell, und ein Verteilen auf mehrere Server nutzt nichts.
Bei Stacking-Ensembles sind alle Prädiktoren einer Schicht unabhängig voneinander und lassen sich daher parallel auf mehreren Servern trainieren. Allerdings lassen sich die Prädiktoren einer Schicht erst trainieren, nachdem die vorige Schicht vollständig trainiert wurde.
Welchen Vorteil bietet die Out-of-Bag-Evaluation?
Bei der Out-of-Bag-Evaluation wird jeder Prädiktor in einem Bagging-Ensemble mit Datenpunkten ausgewertet, auf denen er nicht trainiert wurde (diese wurden zurückgehalten).
Damit ist eine recht unbeeinflusste Evaluation des Ensembles ohne einen zusätzlichen Validierungsdatensatz möglich. Dadurch stehen Ihnen also mehr Trainingsdaten zur Verfügung, und Ihr Ensemble verbessert sich leicht.
Wodurch werden Extra-Trees zufälliger als gewöhnliche Random Forests? Wobei hilft dieses zusätzliche Zufallselement? Sind Extra-Trees langsamer oder schneller als gewöhnliche Random Forests?
Beim Erzeugen eines Baums in einem Random Forest wird beim Aufteilen eines Knotens nur eine zufällig ausgewählte Untermenge der Merkmale berücksichtigt. Dies gilt auch bei Extra-Trees, diese gehen aber noch einen Schritt weiter: Anstatt wie gewöhnliche Entscheidungsbäume nach dem bestmöglichen Schwellenwert zu suchen, verwenden sie für jedes Merkmal zufällige Schwellenwerte.
Dieses zusätzliche Zufallselement wirkt wie eine Art Regularisierung: Wenn ein Random Forest die Trainingsdaten overfittet, könnten Extra-Trees besser abschneiden. Da außerdem Extra-Trees nicht nach dem bestmöglichen Schwellenwert suchen, lassen sie sich viel schneller trainieren als Random Forests. Allerdings sind sie beim Treffen von Vorhersagen weder schneller noch langsamer als Random Forests.
Falls Ihr AdaBoost-Ensemble die Trainingsdaten underfittet, welche Hyperparameter sollten Sie in welcher Weise verändern?
Wenn Ihr AdaBoost-Ensemble die Trainingsdaten underfittet, können Sie die Anzahl der Estimatoren steigern und die Regularisierung des zugrunde liegenden Estimators über dessen Hyperparameter verringern. Sie können auch versuchen, die Lernrate ein wenig zu erhöhen.
