Manche Daten sind nicht linear aber trotzdem simpel.

Bsp: Skifahrregionen und Zeiten

Einfache Klassifikation mit Entscheidungsbaum

Wie konstruieren wir den Entscheidungsbaum?

Wenn wir in Region $R_p$ sind suchen wir einen Split $S_p$:

\[ S_p(j, t) = (R_1, R_2) = \\( \{ x | x_j \leq t, x \in R_p \},\\ \{ x | x_j > t, x \in R_p \}) \]

Wie entscheiden wir was ein guter Split ist?

Idee: Loss Funktion $L(R)$ je Region.

Ein guter Split maximiert
$L(R_p) - \frac{|R_1|}{|R_p|} L(R_1) - \frac{|R_2|}{|R_p|} L(R_2)$

Welche Klasse sagen wir für eine Region vorher?

Immer die, welche die Mehrheit an Beispielen dort hat.

Was ist eine gute Loss Funktion?

Erster Ansatz: Missclassification Loss

Beispiel

$L(R_p) = \frac{1}{10}$, $L(R_1) = \frac{1}{8}$, $L(R_2) = 0$

$L(R_p) - \frac{|R_1|}{|R_p|} L(R_1) - \frac{|R_2|}{|R_p|} L(R_2)$

$= \frac{1}{10} - \frac{8}{10} \frac{1}{8} - 0 = 0$

Beispiel

$L(R_p) = \frac{1}{10}$, $L(R_1) = \frac{1}{5}$, $L(R_2) = 0$

$L(R_p) - \frac{|R_1|}{|R_p|} L(R_1) - \frac{|R_2|}{|R_p|} L(R_2)$

$= \frac{1}{10} - \frac{5}{10} \frac{1}{5} - 0 = 0$

Welcher Split ist besser?

Im zweiten Fall haben wir in $R_2$ mehr Beispiele fertig und weniger Aufwand für den nächsten Split.

Missclassification Loss ist zu ungenau

Nächste Idee: Cross Entropy Loss

$$ L_\text{cross} (R)= - \sum_c \hat p_c \log \hat p_c $$

Ähnlich wie bei logistischer Regression

$-\hat p_c \log \hat p_c$

$-\hat p_c \log \hat p_c - (1-\hat p_c) \log (1-\hat p_c)$

Missclassification Loss: $L_\text{missclass} = 1 - \max_c \hat p_c $

Gini Loss: $L_\text{gini} = \sum_c \hat p_c (1- \hat p_c)$

Regression Trees

In jedem Blatt des Entscheidungsbaums sagen wir den Durchschnitt der Elemente in der Region vorher: \[ \hat y_R = \frac{\sum_{i \in R} y_i}{|R|} \]

Loss Funktion für Regression Trees: \[ L_\text{squared}(R) = \frac{\sum_{i \in R} (y_i - \hat y_R)^2}{|R|} \]

Training des Entscheidungsbaums:

• Rekursiv für Teilregionen $R_p$:
• Für alle Feature $j$ und Tresholds $t$:
• Berechne Loss für Split $S_p(j, t) = (R_1, R_2)$
• Wähle Split mit bestem Loss

Training von Entscheidungsbäumen kann effizient implementiert werden.

Mit $m$ Beispielen, $n$ Features und Baumtiefe $d$:

• Laufzeit (Training): $O(m \cdot n \cdot d)$
• Laufzeit (Inference): $O(d)$

In der Praxis meistens sehr effizient.

Für kategorische Features lassen sich spezielle Splits implementieren

Beispiel: $x_i$ kann ein Element aus $\{\text{rot}, \text{grün}, \text{gelb}, \text{blau}, \text{türkis}\}$ sein.

Entscheidungsknoten $x_i \in \{\text{grün}, \text{türkis}\}$

Mit $q$ Kategorien gibt es $2^q$ mögliche Teilmengen - wir können also nur alle ausprobieren, wenn es wenige gibt.

Decision Trees

Vorteile

• Sehr leicht verständlich
• Hohe Interpretierbarkeit
• Schnell
• Guter Support für Kategorische Features
• Nicht linear

Nachteile

• Für manche Daten sehr schlecht geeignet
• Hohe Varianz

Manche Daten sind schlecht für Decision Trees geeignet

Decision Tree haben hohe Varianz

• Neigen zu Overfitting
  • Im Extremfall nur je ein Beispiel je Blatt
• Leicht andere Daten können zu komplett anderem Entscheidungsbaum führen.

Regularisierung

• Minimale Anzahl an Beispielen je Blatt
• Maximale Tiefe
• Maximale Anzahl Knoten
• (Minimale Loss Verringerung je Ebene)
• (Pruning auf Validation Set)

In sklearn:
sklearn.tree.DecisionTreeClassifier

Auch mit Regularisierung sind einzelne Decision Trees meistens recht schlechte Classifier.

Angenommen wir haben $n$ unabhängige, identisch verteilte Zufallsvariablen $X_i$, $\text{Var}(X_i) = \sigma^2$.

$\text{Var}(\bar X) = \text{Var}(\frac{1}{n}\sum X_i) = \frac{\sigma^2}{n}$

Viele unabhängige Informationsquellen verringern die Unsicherheit meiner Schätzung.

Intelligenz der Masse

Francis Galton ließ 800 Leute das Gewicht eines Ochsen schätzen.

• Wahres Gewicht: 1198 Pfund
• Mittlere Schätzung: 1207 Pfund

Was, wenn die $X_i$ nicht unabhängig sind?

Korrelation $0 \leq \rho \leq 1$.

$\text{Var}(\bar X) = \rho \sigma^2 + \frac{1 - \rho}{n} \sigma^2$

Für eine gute Vorhersage wollen wir:

• Viele Modelle / Vorhersagen (großes $n$)
• Möglichst unabhängige Modelle (kleines $\rho$)

Wie kommen wir zu möglichst unabhängigen Ensembles?

Idee: Verschiedene Klassifikationsalgorithmen verwenden.

Nachteil: Schwierig 100 verschiedene Algorithmen zu finden.

Bagging (Bootstrap Aggregation)

Idee: Wähle zufällige Teilmenge der Trainingsdaten

Ziehe Menge $Z$ aus $\mathcal{D}_\text{train}$ (mit zurücklegen).
(Bootstrap Sample)

Ziehe, z.B. bis $|Z| \geq \frac{2}{3} |\mathcal{D}_\text{train}|$

Wir ziehen insgesamt $M$ verschiedene Samples $Z_1, \ldots, Z_M$.

Auf jedem Sample $Z_i$ trainieren wir einen Classifier $h_i$.

Vorhersage ist das Ensemble Modell $$h(x) = \frac{1}{M} \sum_{i=1}^M h_i(x)$$

Durch die Bootstrap Samples wird das $\rho$ kleiner
(ohne bekämen wir immer das gleiche Modell)

$\rho \sigma^2 + \underbrace{\frac{1-\rho}{M} \sigma^2}_{\to 0}$

Durch ein großes $M$ bekommen wir weniger Varianz, aber etwas mehr Bias, da jedes Modell weniger Trainingsdaten hat.

Meistens ein guter Tradeoff

Decision Trees + Bagging

Decision Trees sind "low bias" und "high variance". Daher profitieren sie besonders von diesem Tradeoff.

Wie können wir $\rho$ weiter verringern?

Idee: Für jeden Split betrachten wir nur eine zufällige Teilmenge der Features als mögliche Kriterien.

Dadurch haben wir noch etwas mehr Zufall in jedem einzelnen Decision Tree und weniger Korrelation zwischen verschiedenen.

Decision Trees + Bagging + Zufällige Feature Sets = Random Forest

Random Forests sind häufig die stärksten Modelle für tabellarische Daten.

In sklearn:
sklearn.ensemble.RandomForestClassifier

Alternative zu Bagging: Boosting (AdaBoost)

Idee: Gewichte Fehler einer Klassifikation stärker und trainiere nochmal.

Jeder spätere Classifier fokussiert sich auf die Beispiele, die bisher schlecht klassifiziert werden.

Dadurch sind sie insgesamt natürlich schlechter.

Für das Ensemble bestimmen wir für jeden Classifier $h_i$ ein Gewicht $\alpha_i$

$$\alpha_i = \frac{1}{2} \log (\frac{1 - \text{err}_i}{\text{err}_i})$$

$$h(x) = \sum_i \alpha_i h_i(x)$$

In sklearn:
sklearn.ensemble.AdaBoostClassifier