Kurze Übersicht

Definition "Maschinelles Lernen"

Fähigkeit zu lernen, ohne explizit programmiert zu werden. (Arthur Samuel, 1959)

Arten des Lernens

• Überwachtes Lernen (e.g. Klassifizierung, Regression)
• Unüberwachtes Lernen (e.g. Clustering, Dimensionsreduktion)
• Bestärkendes Lernen (e.g. Schach spielen)

Formalisierung

• Zielfunktion $f$
• Merkmalraum (input space)
• Ausgaberaum (output space)
• Datensatz $\mathcal{D}$
• Hypothesenmenge $\mathcal{H}$
• Lernalgorithmus $\mathcal{A}$

Das Perzeptron

Ein einfaches Modell für die binäre Klassifizierung

• Bilde gewichtete Summe (Linearkombination) der Merkmale
• Vergleiche das Ergebnis mit einem Schwellenwert
  • Positiv, falls über dem Schwellenwert
  • Negativ, falls unter dem Schwellenwert
• Gewichte und Schwellenwert sind unbekannte Parameter des Modells, die es zu lernen gilt > siehe Perzeptron Lernalgorithmus

Kurze Übersicht

Formalisierung

• Ausgabe $y$ ist reelle Zahl aus einem stetigen Bereich (zum Beispiel Hauspreis)
• Die Hypothesenfunktion ist eine gewichtete Summe der Merkmale $x_i$ plus eine Konstante $w_0$: $$h(\mathbf{x}) = \mathbf{w}^T\mathbf{x} = w_0 + w_1x_1 + w_2x_2 + \ldots + w_nx_n$$
• Der Verlust (engl. loss) für einen Datenpunkt $\mathbf{x}$ ist das Fehlerquadrat: $$\mathcal{L} = (\hat{y} - y)^2 = (h(\mathbf{x}) - y)^2$$
• Die Kosten (engl. cost) sind der durchschnittliche Verlust über alle Datenpunkte: $$J = \frac{1}{2m} \sum_{i=1}^{m} (\hat{y} - y)^2 = \frac{1}{2m} \sum_{i=1}^{m} (h(\mathbf{x}) - y)^2$$

Der Gradient

• Der Gradientenvektor $\nabla J(\mathbf{w})$ setzt sich zusammen aus den partiellen Ableitungen der Kostenfunktion $J$ nach den Gewichten $w_i$ und zeigt in jedem Punkt $\mathbf{w}$ in die Richtung des steilsten Aufstiegs: $$\nabla J = [ \partial J / \partial w_0 \quad \partial J / \partial w_1 \quad \ldots \quad \partial J / \partial w_n]^T$$
• Schlussfolgerung: In die entgegengesetzte Richtung, i.e. in Richtung $-\nabla J(\mathbf{w})$ geht es am steilsten bergab!
• IDEE: Bewege $\mathbf{w}$ in Richtung $-\nabla J(\mathbf{w})$, um die Kosten $J$ möglichst schnell zu senken.

Der Gradientenabstieg (engl. Gradient Descent)

1. Starte mit zufälligen Gewichten $\mathbf{w}$
2. Berechne den Gradientenvektor im aktuellen Punkt $\mathbf{w}$
3. Gewichtsaktualisierung: Gehe einen kleinen Schritt in Richtung $-\nabla J(\mathbf{w})$ $$\mathbf{w} _{neu} := \mathbf{w} _{alt} - \alpha \cdot \nabla J(\mathbf{w} _{alt})$$ ($\alpha$: Lernrate/Schrittweite).
4. Wiederhole Schritte 2-3, bis das globale Minimum von $J$ erreicht ist.

Graphische Übersicht

• Lineare Regression
• Perzeptron

Kurze Übersicht

Formalisierung

• Ausgabe $y$ ist reelle Zahl aus dem stetigen Bereich $(0,1)$

• Die Hypothesenfunktion ist: $$h(\mathbf{x}) = \sigma (\mathbf{w}^T\mathbf{x}) = \sigma (w_0 + w_1x_1 + w_2x_2 + \ldots + w_nx_n) \tag{1}$$

• Der Kreuzentropie Verlust (engl. Cross-Entropy) für einen Datenpunkt $\mathbf{x}$: $$\mathcal{L}(a, y) = - y \log(a) - (1-y) \log(1-a)\tag{2}$$ wobei hier $a := \hat{y}$ die Vorhersage ist.

• Die Kosten als durchschnittlicher Verlust über alle Datenpunkte $x^{(1)}, \ldots, x^{(m)}$: $$J = \frac{1}{m} \sum_{i=1}^m \mathcal{L}(a^{(i)}, y^{(i)})\tag{3}$$

Gradientenabstieg

• Der Gradient für einen Datenpunkt $\mathbf{x}$: $$\frac{\partial \mathcal{L}}{\partial w} = (a-y)x \tag{4}$$
• Der Gradient für alle Datenpunkte $X$ in Matrix-Notation: $$\nabla J = \frac{\partial J}{\partial w} = \frac{1}{m}X(A-Y)^T\tag{5}$$

Graphische Übersicht

• Logistische Regression
• Lineare Regression
• Perzeptron

Kurze Übersicht

Nichtlineare Modelle

• Einführung von neuen Merkmalen in Form von nichtlienaren Kombinationen der ursprünglichen Merkmale
• Erhöhung der Komplexität des Modells ermöglicht das Erfassen von nichtlinearen Beziehungen
• Bemerkung: Die Hypothesenfunktion bleibt linear in den Gewichten, es wird weiterhin logistische Regression in einem erweiterten Merkmalraum durchgeführt.

Überanpassung und Regularisierung

• Die Überanpassung (engl. Overfitting) ist eines der häufigsten und wichtigsten Probleme in ML und DL
• "Was im Bereich des maschinellen Lernens Professionelle von Amateuren unterscheidet, ist ihre Fähigkeit mit Überanpassung umzugehen." [AbuMostafa2012, S. 119]
• Anzeichen von Überanpassung sind geringe Trainingskosten und hohe Testkosten (Kosten auf nicht-gesehenen Daten).
• Regularisierung ist eine Maßnahme gegen Überanpassung. Man kann es sich als eine Reduktion in der Komplexität des Modells vorstellen.
• Der Regularisierungsparameter $\lambda$ ist ein Hyperparameter. Je größer der $\lambda$-Wert, desto größer der Regularisierungseffekt.
• Die Kostentenfunktion bei regulariserter logistischer Regression: $$J = \frac{1}{m} \left\lbrack \sum_{i=1}^m \left( -y^{[i]}log(a^{[i]})-(1-y^{[i]})log(1-a^{[i]}) \right) + \frac{\lambda}{2} \sum_{j=1}^n (w^2_j) \right\rbrack \tag{1}$$
• Die Gewichtsaktualisierung mit Regularisierungsterm: $$w_j := w_j - \frac{\alpha}{m} \left\lbrack \sum_{i=1}^m \left( ( a^{[i]} - y^{[i]} )x_j^{[i]} \right) + \lambda w_j \right\rbrack \tag{2}$$

Kurze Übersicht

Multilayer Perzeptron (MLP)

• Das Perzeptron kann nur linear separable Daten korrekt klassifizieren.
• Durch das Zusammenschließen von mehreren Perzeptronen kann man ein mehrschichtiges Perzeptron (engl. Multilayer Perceptron) aufstellen, das komplexere Funktionen modellieren kann.
• Ein MLP wird oft auch als Feed Forward Neural Network oder als Fully Connected Neural Network bezeichnet.
• Die "inneren" Schichten eines solchen Netzwerkes sind sogenannte versteckte Schichten (engl. hidden layer). Das sind alle Schichten ausgenommen die Eingangs- und Ausgangsschicht.

Graphische Übersicht und Vorwärtslauf

• Ein Multi-Layer Perzeptron Ein Vorwärtslauf (forward pass): $$a^{[1]} = ReLU \left( W^{[1]} \cdot \mathbb{x} + b^{[1]} \right) \tag{1}$$ $$\hat{y} := a^{[2]} = \sigma \left( W^{[2]} \cdot a^{[1]} + b^{[2]} \right) \tag{2}$$

Kurze Übersicht

Forwärts- und Rückwärtslauf

• Im Forwärtslauf (engl. forward pass oder forward propagation) wird ein einzelner Forwärtsschritt von Schicht $[l-1]$ auf Schicht $[l]$ wie folgt berechnet: $$Z^{[l]} = W^{[l]}A^{[l-1]} + b^{[l]} \tag{1}$$ $$A^{[l]} = g(Z^{[l]}) \tag{2}$$ Dabei bezeichnet $g$ die Aktivierungsfunktion (z.B. Sigmoid oder ReLU).

• Im Rückwärtslauf (engl. backpropagation) werden in einem einzelnen Rückwärtsschritt von Schicht $[l]$ auf Schicht $[l-1]$ die folgenden Gradienten berechnet:

  $$dZ^{[l]} := \frac{\partial J }{\partial Z^{[l]}} = dA^{[l]} * g'(Z^{[l]}) \tag{3}$$ $$dW^{[l]} := \frac{\partial J }{\partial W^{[l]}} = \frac{1}{m} dZ^{[l]} A^{[l-1] T} \tag{4}$$ $$db^{[l]} := \frac{\partial J }{\partial b^{[l]}} = \frac{1}{m} \sum_{i = 1}^{m} dZ^{[l](i)}\tag{5}$$ $$dA^{[l-1]} := \frac{\partial J }{\partial A^{[l-1]}} = W^{[l] T} dZ^{[l]} \tag{6}$$

  Dabei steht "$*$" für die elementweise Multiplikation.

• Beachten Sie:

  • Der Forwärtsschirtt übernimmt $A^{[l-1]}$ von dem vorherigen Schritt und gibt $A^{[l]}$ an den nächsten Schritt weiter.
  • Der Rückwärtschritt übernimmt $dA^{[l]}$ von dem vorherigen Schritt und gibt $dA^{[l-1]}$ an den nächsten Rückwärtsschritt weiter.

Parameteraktualisierung

• Die Aktualisierung der Parameter in Schicht $l$ erfolgt wie gewohnt durch: $$W^{[l]} = W^{[l]} - \alpha \text{ } dW^{[l]} \tag{7}$$ $$b^{[l]} = b^{[l]} - \alpha \text{ } db^{[l]} \tag{8}$$ Dabei bezeichnet $\alpha$ die Lernrate.

Kurze Übersicht

Training und Testing

• Der tatsächliche Erfolg eines Modells wird nicht durch niedrige Trainingskosten gemessen, sondern durch geringe Kosten auf ungesehenen Daten, d.h. hohe Vorhersagekraft, gute Generalisierung!

• Die Menge aller gelabelten Daten in Trainingsset und Testset aufteilen, Testset nicht während des Trainings einsetzen!.

  • $E_{in}$ bezeichnet den Fehler auf dem Trainingsset, auch in-sample error.
  • $E_{out}$ bezeichnet den Fehler auf dem gesamten Eingaberaum $X$, auch out-of-sample error. $E_{out}$ ist der eigentliche Indikator für den zukünftigen Erfolg des Modells, ist uns aber nicht zugänglich.
  • $E_{test}$ bezeichnet den Fehler auf dem Testset und ist eine Näherung für $E_{out}$.

  Analogie:
  $E_{in}$ : Erfolg in Übungsaufgaben und Probeprüfungen.
  $E_{test}$ : Erfolg in Endprüfung.

• Die Näherung $E_{test}$ sollte möglichst genau sein, damit es als ein verlässliches Gütesiegel dienen kann.

  • Das Testset sollte genug Daten enthalten. Üblicher Anteil an Testdaten:
    • bei $|D| \approx 100.000 \rightarrow$ ca. 20%
    • bei $|D| \approx 10.000.000 \rightarrow$ ca. 1%
    • Beispiel: Hat man 1000 Beispiele im Testset, wird $E_{test}$ mit $\ge 98\%$ Wahrscheinlichkeit in der $\pm 5\%$ Umgebung von $E_{out}$ liegen (für theoretische Grundlagen und Herleitung siehe [AbuMostafa2012, S. 39-69]).
  • Trainingsdaten und Testdaten sollten möglichst aus derselben Verteilung kommen, wie die zukünftigen Real-World-Daten.

• Wichtige Bemerkung:

  • Testdaten nicht anfassen, bis das Modell Einsatzbereit ist!
  • Die Testdaten dürfen in keinster Weise bei der Auswahl der endgültigen Hypothese eingesetzt werden, weder bei der Berechnung der Parameter (Training), noch bei der Bestimmung der Hyperparameter (Hyperparameter-Tuning).
  • Sobald der Testfehler die Auswahl der endgültigen Hypothese beeinflusst, kann sie nicht mehr als "Gütesiegel" eingesetzt werden.
    CHECK: Hätte man zufällig andere Testdaten gewählt, könnte sich dadurch die endgültige Hypothese ändern?

Validierung und Modellauswahl

• Das Ziel ist es, das Modell mit bester Generalisierung, also kleinstem $E_{out}$ zu bestimmen. $E_{out}$ ist jedoch unbekannt und die Näherung $E_{test}$ darf nicht bei der Modellauswahl eingesetzt werden.

• LÖSUNG: Einen weiteren Teil der Daten als Validierungsset (auch development set) beiseitelegen und nicht für das Training (i.e. Minimierung des Trainingsfehlers $E_{in}$) verwenden!

• Bemerkung:
  Das Wort Modell kann je nach Kontext unterschiedliche Bedeutungen annehmen.
  Ein Modell im aktuellen Kontext ist als ein Paar $(\mathcal{H},\mathcal{A})$ von Hypothesenraum (bzw. Modellarchitektur) und Lernalgorithmus definiert.

  • Die Auswahl eines Modells kann aus einer Menge von Modellen unterschiedlicher Art erfolgen (z.B. lineare Modelle, polynomiale Modelle, neuronale Netze), oder von Modellen derselben Art aber mit unterschiedlichen Hyperparametern (z.B. Neuronale Netze mit unterschiedlicher Anzahl von versteckten Schichten).
  • Außerdem kann dieselbe Modellarchitektur $\mathcal{H}$ mit unterschiedlichen Lernalgorithmen trainiert werden, was wiederum die endgültige Hypothese beeinflussen kann. Die Bestimmung der Hyperparameter von ${\mathcal{A}}$ (wie z.B. Optimierungsfunktion, Lernrate, Kostenfunktion, Regularisierungsparameter usw.) sind daher auch Teil der Modellauswahl.

• Der Validierungsfehler $E_{val}$ kann nun als Entscheidungsgrundlage an verschiedenen Stellen des Lernrpozesses eingesetzt werden, wie zum Beispiel:

  • Bei der Auswahl geeigneter Hyperparameter wie z.B. Anzahl Schichten, Anzahl Zellen/Schicht, Aktivierungsfunktion, Regularisierungsparameter (siehe Abbildung 1).

  

  • Bei der Auswahl der endgültigen Hypothese ($\rightarrow$ Parameterauswahl!): unter allen Hypothesen, die während des Trainings durchlafen werden, wähle jene mit kleinstem $E_{val}$ (siehe Abbildung 2).

  

  • Bei der graphischen Darstellung von Lernkurven für die Diagnose von Über- und Unteranpassung (siehe Abbildung 3).

  

• Übliche train/val/test Aufteilung der Daten (in Prozent):

  • bei $|D| \approx 100.000 \rightarrow$ ca. 60/20/20
  • bei $|D| \approx 10.000.000 \rightarrow$ ca. 98/1/1

• Bemerkung:
  Das Modell ist trainiert für gute Ergebnisse auf Trainingsdaten und "fine-tuned" für gute Ergebnisse auf den Validierungsdaten. Ergebnisse auf Testdaten werden mit hoher wahrscheinlichkeit schlechter ausfallen, als auf Validierungsdaten ($E_{val}$ ist eine zu optimistische Näherung).

• Sind Validierungs- und/oder Trainingsset zu klein, führt das zu schlechten Näherungen $E_{val}$ und folglich zu schlechten Entscheidungen.

  • Bei der Aufteilung muss ein gutes Trade-off gefunden werden.
  • Wenn kein Gütesiegel notwendig ist, kann man auf das Testset verzichten und die Daten in Trainings- und Validierungsset aufteilen.
  • Für eine bessere Näherung mit weniger Validierungsdaten kann k-fache Kreuzvalidierung eingesetzt werden (wenn genug Rechenkapazität vorhanden ist).

K-fache Kreuzvalidierung (engl. k-fold cross-validation):

• Das Modell $(\mathcal{H_m},\mathcal{A_m})$ wird $k$ mal trainiert und validiert, jedes mal mit unterschiedlichen Trainings- und Validierungsmengen:

  • Die Trainingsdaten werden in $k$ disjunkte Teilmengen $D_1, D_2, ..., D_k$ aufgeteilt.

  • Bei dem $i$-ten Training werden die Teilmenge $D_i$ für die Berechnung des Validierungsfehlers $e_i := E_{val}(h_m^{*(i)})$ und die restlichen $k-1$ Teilmengen für das Training verwendet.

  • Der Kreuzvalidierungsfehler des Modells $(\mathcal{H_m},\mathcal{A_m})$ ist der Durchschnitt der $k$ Validierungsfehler $e_1, e_2, ..., e_k$ (siehe Abbildung 4). $$E_{CV}(m) := \frac{1}{k} \sum_{i=1}^{k} e_i = \frac{1}{k} \sum_{i=1}^{k} E_{val}(h_m^{*(i)})$$

  

• Bemerkung: Die Kreuzvalidierung wird nur bei der Modellauswahl eingesetzt: es liefert verlässlichere Näherungen für $E_{out}$ und führt daher zu besseren Entscheidungen. Das zuletzt ausgewählte Modell wird danach wie gewohnt auf den gesamten Trainigsdaten (ausgenommen Testdaten) trainiert und zum Schluss mit den Testdaten evaluiert.

Kurze Übersicht

Performanzmetriken für Klassifizierungsprobleme

Wahrheitsmatrix (engl. Confusion Matrix)

• Gibt eine Übersicht über die Anzahl von richtig und falsch klassifizierten Datenpunkten (bei binärer Klassifizierung)
  • $TP =$ # True Positives $=$ Anzahl richtiger 1-Vorhersagen
  • $FP =$ # False Positives $=$ Anzahl falscher 1-Vorhersagen
  • $FN =$ # False Negatives $=$ Anzahl falscher 0-Vorhersagen
  • $TN =$ # True Negatives $=$ Anzahl richtiger 0-Vorhersagen
• Bei Klassifizierungsproblemen mit $N$ Klassen hat man eine $N \times N$ Matrix, die in Position $(i,j)$ die Anzahl der Klasse-$j$-Beispiele enthält, die als Klasse-$i$ vorhergesagt wurden.

Treffergenauigkeit (engl. Accuracy)

• Anzahl richtig klassifizierter Datenpunkte, Erfolgsrate (engl. correct rate) $$Accuracy = \frac{TP+TN}{TP+TN+FP+FN}$$

• Accuracy vermittelt ein falsches Bild des Erfolges bei unausgewogenen Datensätzen
  Beispiel:

  • Klasse 1 hat 10, Klasse 0 hat 990 Beispiele.
  • Ein Modell, das immer 0 ausgibt, hat $990/1000 = 0.99$ Treffergenauigkeit, ist aber offensichtlich kein gutes Modell!

Precision

• Positive Predictive Value (PPV)
• Antwort auf: Von allen positiven Vorhersagen, wie viele sind richtig? $$Precision = \frac{TP}{TP + FP}$$
• Wahrscheinlichkeit, dass ein positiv klassifiziertes Beispiel auch tatsächlich positiv ist.
• Je näher an 1, desto besser.
• Accuracy of positive predictions.

Recall

• True Positive Rate, auch Sensitivität (engl. Sensitivity)
• Antwort auf: Von allen positiven Beispielen, wie viele wurden richtig klassifiziert? $$Recall = \frac{TP}{TP + FN}$$
• Wahrscheinlichkeit, dass ein positives Beispiel tatsächlich als solches erkannt wird.
• Je näher an 1, desto besser.
• Accuracy of positive examples.

Precision-Recall Trade-off

• Ein gutes Modell sollte hohe Precision und zugleich hohes Recall haben.
• Man kann die Precision eines Modells beliebig erhöhen (durch das Vergrößern des Schwellenwertes bei der Klassifizierung), jedoch wird dabei der Recall abnehmen.
• Genau so kann man den Recall eines Modells beliebig erhöhen (durch das Verkleinern des Schwellenwertes bei der Klassifizierung), jedoch wird dabei die Precision abnehmen.
• Es gilt ein gutes Trade-off zu finden.
• Eine Zwei-Zahlen-Metrik erschwert den Entscheidungsprozess bei Evaluierung und Modellauswahl.

$F_1$-Score (Harmonisches Mittel)

• Fasst Precision (P) und Recall (R) in einer Metrik zusammen (Harmonisches Mittel von P und R): $$F_1-Score = \frac{2}{\frac{1}{P} + \frac{1}{R}} = 2 \cdot \frac{PR}{P + R}$$
• Der $F_1$-Score wird nur dann hoch sein, wenn P und R beide hoch sind.
• Je näher an 1, desto besser.
• Sehr kleine P und R Werte ziehen den $F_1$-Score sehr stark herunter. In dieser Hinsicht gibt diese Metrik ein akkurates Bild über den Erfolg eines Modells.