Supervised Learning

Beim SL sind neben den Beobachtungen (Features) auch die daraus resultierenden Ergebnisse bekannt.

Wichtige „learning“ Algorithmen sind:

• k-Nearest Neighbors

• Linear Regression

• Binary Classification

• Logistic Regression

• Support Vector Maschines (SVMs)

• Decision Trees and Random Forests

• Neuronal networks

• Linear Regression (LR)

• Der Klassiker: supervised_learning_linear_regression

Binary Classification

Binary Classification ist die Aufgabe die vorhandenen Elemente in zwei Gruppen von Klassen einzuteilen. Beispiele:

• Medizin: Krebs ja / nein

• Qualitätssicherung: i.O / nich i.O.

• Bildsuche: Katzenbild ja/nein

Beispiel bei einer Bildklassifizierung:

Ziel ist die Entwicklung eines Klassifizierungsmodelles zur Bilderkennung, bspw. Katze ja/nein. Als Eingangsparameter wird das Bild verwendet. Das Ergebnis ist ein Labelvektor y (1=Katze, 0=keine Katze). Das Bild wird zu einem Feature Vector X umgewandelt, Beispiel: Bild hat die Farben (RGB): rot x grün x blau. Pixelgröße 64 x 64. Um daraus einen Feature Vektor X abzuleiten, wird die Pixelintensität (Wert zw. 0-255) als Vektor dargestellt mit der Dimension 1 Spalte x (64 x 64 x 3 (RGB)) = 12288 Zeilen

\(x = \begin{pmatrix} \color{Red}{255 \\ 12 \\ 128 \\ \vdots \\ } \color{Green}{86 \\ 172 \\ 255 \\ \vdots \\ } \color{Blue}{88 \\ 156 \\ 192 \\ \vdots} \end{pmatrix}\)

Zurück zu Supervised Learning

Logistic Regression

Quelle: Andrew Ng, Neural Networks and Deep Learning, Coursera, 2020

Bei der LR ist das Ergebnis entweder 1 oder 0. Ziel des LR ist die Minimierung des Fehlers zw. den Vorhersagedaten und Trainingsdaten.

Die Parameter in LR sind:

Bedeutung	Parameter oder Funktion
Feature Inputvektor	x
Training Label	y \(\in \; 0,1\)
Gewichtung	w
Bias (Threshold)	b
„Gelernter“ Output	\(\hat y = \sigma(w^Tx+b)\)
Sigmoid Funktion	\(\sigma(w^Tx+b)=\sigma(z)=\frac{1}{1+e^{-z}}\)

Abb. 1: Sigmoid Function (Abb. 1)

\((w^Tx+b)\) ist die lineare Funktion von (ax+b). Da nur nach der Wahrscheinlichkeit zwischen [0,1] bewertet wird, wird die Sigmoid Funktion verwendet, die die Werte auf einen Wertebereich zw. [0,1] normiert. Sie hat folgende Eigenschaften:

• wenn z sehr gross ist, dann ist \(\sigma(z) = 1\)

• wenn z sehr klein ist oder kleiner Null, dann ist \(\sigma(z)=0\)

• wenn z = 0 ist, dann ist \(\sigma(z) = 0.5\)

Loss Funktion

Die Loss Funktion berechnet den „Abstand“ zwischen den gelernten Outputwert \(\hat y^{(i)}\) und dem Traininglabel \(y^{(i)}\). Diesen gilt es anhand der Loss Funktion zu minimieren.

\(L(\hat y^{(i)},y^{(i)}) = 1/2 (\hat y^{(i)} - y^{(i)})^2\)

\(L(\hat y^{(i)},y^{(i)}) = -(y^{(i)}log(\hat y^{(i)})+(1-y^{(i)})log(1-\hat y^{(i)})\)

• wenn \(y^{(i)} = 1 \;:\;L=-log(\hat y^{(i)})\) wobei \(log(\hat y^{(i)}) \; und \; \hat y^{(i)}\) nahe bei 1 liegen sollen.

• wenn \(y^{(i)} = 0 \;:\;L=-log(1-\hat y^{(i)})\) wobei \(log(1-\hat y^{(i)}) \; und \; \hat y^{(i)}\) nahe bei 0 liegen sollen.

Die Kostenfunktion aller Trainingselemente ist der Durchschnitt der Loss Funktion eines jeden Trainingswertes. Ziel ist es diese Funktion J(w,b) zu minimieren:

\(J(w,b)=\frac{1}{m} \sum^{m}_{i=1} L(\hat y^{(i)},y^{(i)})= -\frac{1}{m} \sum^{m}_{i=1}[(y^{(i)}log(\hat y^{(i)})+(1-y^{(i)})log(1-\hat y^{(i)})]\)

Beispiel: Foreward and Backward - Propagation in a Network

Die Lösung eines LR Problems kann über das Gradient Descence Verfahren angegangen werden. Hierbei wird ein lokales Minimum gesucht durch Änderung der unabhängigen Variablen in einer Kostenfunktion.

Bsp.: Gegeben sei die Kostenfunktion J(a,b,c)=3(a+bc). u=bc, v=a+u und J=3v

Als Berechnungsgraph kann man das wie folgt aufschreiben:

Es wird nun die Änderung einer Variable in Abhängigkeit einer anderen Variable bestimmt, d.h. der Berechnungsgraph wird von rechts nach links berechnet. Im Beispiel: Änderungsrate von J, wenn v sich marginal ändert? Mathematisch \(\frac{dJ}{dv}\). In diesem Beispiel ist v=11 und J=33. Wenn sich v um 0.001 ändert, ändert sich J um 3 * 0.001 auf 33.003, d.h. \(\frac{dJ}{dv}=3\). J ist von v abhängig, während v von a und u abhängig ist. Wie ändert sich J, wenn a sich ändert \(\frac{dJ}{da}\)? a=5, wenn a=5.001, dann ist v=11.001 und J=33.003. Somit ist \(\frac{dJ}{da}=3\). Oder in anderen Worten: Wenn sich a ändert, ändert sich v, ändert sich J. Das ist die Chain Rule: \(\frac{dJ}{da}=\frac{dJ}{dv}\frac{dv}{da}\). Am Beispiel: a=5.001 => v=11.001 dv/da=1 und J=33.003 bzw. dJ/dv=3 und somit dJ/da=1 x 3 = 3.

Analog bei \(\frac{dJ}{du}\). u=6, wenn u=6.001, dann ist v=11.001 und J=33.003. \(\frac{dJ}{du}=\frac{dJ}{dv}\frac{dv}{du}=3 * 1 = 3\)

Für \(\frac{dJ}{db}\) gilt: b=3, b=3.001, u=6.002, v=11.002, J=33.006 oder \(\frac{dJ}{db}=\frac{dJ}{dv}\frac{dv}{du}\frac{du}{db}=3*1*2=6\)

Für \(\frac{dJ}{dc}=\frac{dJ}{dv}\frac{dv}{du}\frac{du}{dc}=3*1*3=9\)

Foreward and Backward - Propagation im LR Network

Im LR Netzwerk haben wir

• die lineare Funktion: \(z=w^Tx+b\)

• den gelernten Output: \(\hat y=a=\sigma(z)\)

• die Kostenfunktion: \(L(a,y) = -(y log(a) + (1-y)(log(1-a))\)

Als Berechnungsgraph:

\(Input: \; x_1,w_1,x_2,w_2,b \rightarrow z=w_1x_1+w_2x_2+b \rightarrow \hat y=a=\sigma(z) \rightarrow L(a,y)\)

Für die Backpropagation gilt dann: \(\frac{dL}{dz}=\frac{dL}{da}\frac{da}{dz}\)

Schritt 1: \(\frac{dL}{da}\)

\(L= -(y log(a) + (1-y)log(1-a))\)

\(\frac{dL}{da}=-y \times \frac{1}{a} - (1-y) \times \frac{1}{1-a}\times -1\)

Achtung: -1 am Ende, da für f‘ von ln(1-a) die Chain-Rule gilt!

\(\frac{dL}{da}=\frac{-y}{a} + \frac{1-y}{1-a}\)

\(\frac{dL}{da}=\frac{-y\times(1-a)}{a\times(1-a)} + \frac{a\times(1-y)}{a\times(1-a)}\)

\(\frac{dL}{da}=\frac{-y+ay+a-ay}{a(1-a)}\)

\(\frac{dL}{da}=\frac{a-y}{a(1-a)}\)

Schritt 2: \(\frac{da}{dz}\)

\(\frac{da}{dz}=\frac{d}{dz}\sigma(z)=\sigma(z)\times(1-\sigma(z))\)

Wir haben \(\sigma(z)=a\) definiert. So kann die Formel vereinfacht werden zu

\(\frac{da}{dz}=a(1-a)\)

Exkurs: Ableitung:

\(\frac{d\sigma(z)}{dz}=\frac{d}{dz}\frac{1}{1+e^{-z}}\)

Hier ist wieder die Chain Rule anzuwenden. Wir definieren \(u=1+e^{-z}\). Die Sigmoid Funktion kann nun als \(\sigma(u)=\frac{1}{u}\) geschrieben werden.

\(\frac{d\sigma(z)}{dz}=\frac{d\sigma(u)}{du}\frac{u}{dz}\)

Schritt 1:

\(\frac{d\sigma(u)}{du}=\frac{d}{du}\frac{1}{u}=-\frac{1}{u^2}=-\frac{1}{(1+e^{-z})^2}\)

Schritt 2:

\(\frac{du}{dz}=\frac{d}{dz}(1+e^{-z})=-e^{-z}\)

Schritt 3 zusammenbringen:

\(\frac{d\sigma(z)}{dz}=\frac{d\sigma(u)}{du}\frac{u}{dz}=-\frac{1}{(1+e^{-z})^2} \times (-e^{-z})\)

Schritt 4 vereinfachen:

Es ist \(\sigma(z)=\sigma=\frac{1}{(1+e^{-z})}\), daher gilt:

\(\frac{1}{(1+e^{-z})^2}=\sigma^2\)

Für \(e^{-z}\) gilt:

\(\sigma=\frac{1}{(1+e^{-z})} \Rightarrow \sigma(1+e^{-z})=1 \Rightarrow 1+e^{-z} = \frac{1}{\sigma} \Rightarrow e^{-z} = \frac{1}{\sigma}-1=\frac{1-\sigma}{\sigma}\)

Damit kann der Term vereinfacht werden zu:

\(\frac{d\sigma(z)}{dz}=\frac{1}{(1+e^{-z})^2} \times e^{-z} = \sigma^2 \times \frac{1-\sigma}{\sigma}=\sigma \times (1-\sigma)\)

Schritt 3: \(\frac{dL}{dz}\)

\(\frac{dL}{dz}=\frac{dL}{da}\times\frac{da}{dz}\)

\(\frac{dL}{dz} = \frac{a-y}{a(1-a)} \times a(1-a) = a-y\)

Vektorisierung der LR

Ziel ist die Überführung der ML Algorithmen in ein Modell, wo die Vekororen/Matrizenrechnung angewandt werden kann.

Bei LR wird jeder Vorhersagewert berechnet über

\(z^{(i)}=w^{(T)}x^{(i)}+b\)

\(a^{(i)}=\sigma(z^{(i)})\)

Die Inputwerte werden in der Matrix X zusammengefasst:

\(X=\begin{bmatrix} {\vdots \\ x^{(1)} \\ \vdots } {\vdots \\ x^{(2)} \\ \vdots } {\vdots \\ \dotsi \\ \vdots } {\vdots \\ x^{(n)} \\ \vdots } \end{bmatrix}\)

z errechnet sich demnach durch:

\(Z=[z^{(1)} \; \dotsi \; z^{(n)}]=w^TX+[b \; \dotsi \; b]=[w^Tx^{(1)}+b \; \dotsi \; w^Tx^{(n)}+b]\)

Bei Verwendung von numpy in Python: z=np.dot(w.T,X)+b.

Analog geht man bei a vor, d.h. die Matrix A errechnet sich aus Sigma(Matrix Z):

\(A=[a^{(1)} \; \dotsi \; a^{(n)}]=\sigma(Z)\)

Das Gradient Descence Verfahren kann ebenso vektorisiert werden. Es gilt:

\(dz^{(1)}=a^{(1)}-y{(1)} \; \; \; dz^{(2)}=a^{(2)}-y^{(2)} \; ...\)

Ebenso kann A als Vektor zusammengefasst werden (siehe oben) und Y für die Traingssets. Daraus ergibt sich:

\(dZ=[dz^{(1)} \; \dotsi \; dz^{(n)}] = A - Y\)

Implementierung Logistic Regression Algorithmus

Ohne Vektorisierung

J=0, dw₁ =0, dw₂ =0, db=0

for i = 1 to m

\(z^{(i)}=w^{(T)}x^{(i)}+b\)

\(a^{(i)}=\sigma(z^{(i)})\)

\(J +=-[y^{(i)}log(a^{(i)})+(1-y^{(i)})log(1-a^{(i)})]\)

\(dz^{(i)}=a^{(i)}-y{(i)}\)

\(dw_1 \; += \; x^{(i)}_1 dz^{(i)}\)

\(dw_2 \; +=\; x^{(i)}_2 dz^{(i)}\)

\(db \; += \; dz^{(i)}\)

J /= m, dw₁ /=m, dw₂ /=m, db/=m

Mit Vektorisierung

for i in range (Iteration) # Anzahl der durchzührenden Iterationen bei Gradient Descence

Z=np.dot(w.T,X)+b

\(A=\sigma(Z)\)

dz=A-Y

\(dw=\frac{1}{m}XdZ^T\)

\(db=\frac{1}{m}np.sum(dZ)\)

\(w := w-\alpha dw\)

\(b := b-\alpha db\)

Zurück zu Supervised Learning

Decision Trees

Bei einem Entscheidungsbaum werden die Daten in verschiedene Kategorien unterteilt. Dabei wird je Iteration ein neues Knotenpaar erzeugt, bis alle Traings-Daten einem Knoten zugeordnet sind. Aufgrund des Algorithmus neigt dieser zum „overfitting“, d.h. es wird ein Entscheidungsbaum in der Form aufgebaut, so dass alle Trainingsdaten im Extremfall einem Knoten zugeordnet sind. Die Testdaten müssen dann nicht zwingend genausogut in diese Kategorien fallen! In sklearn gibt es zwei Klassen:

DecisionTreeRegressor und DecisionTreeClassifier.

DecisionTreeRegressor sind nicht in der Lage Vorhersagen außerhalb des Gültigkeitsbereichs der Trainingsdaten zu machen!

Wichtige Begriffe:

• root – Ursprungsknoten, dieser beinhaltet alle Testdaten

• leaf – Endknoten (Blätter). Enthält der Leaf-Knoten alle den identischen Wert, wird auch von einem pure – leaf Knoten gesprochen.

In jedem Knoten gibt es eine Testbedingung, die zum nächsten „Ast“ verzweigt. Vermeidung von „Overfitting“ durch zwei Strategien:

1. pre-pruning – Angabe der maximalen Ebenen eines Entscheidungsbaumes. In sklearn implementiert über

   • max_depth: maximale Anzahl der Ebenen

   • max_leaf_nodes: maximale Anzahl der Leafs

   • min_samples_leaf: minimale Anzahl von Daten in einem Knoten, die vorhanden sein müssen.

2. post-pruning/pruning – Die letzte Ebene wird eleminiert, um ein „overfitting“ zu vermeiden. In sklearn nicht implementiert.

feature importance: in sklearn wird beim Aufbau eines Entscheidungsbaums auch ein Array feature_importance mit Werten gefüllt. Diese geben an, welches Feature (Spalte) am Relevantesten für den Aufbau des Entscheidungsbaums ist. Die Summe alle feature_importances ist 1.

Ziel des ML Algorithmus: Ziel ist der Aufbau eines Entscheidungsbaums, in der alle Daten nach einer Testentscheidung einem Knoten zugeordnet werden können.

Vorteile von DT: * Ergebnisse sind leicht zu visualisieren und leicht verständlich für nicht Experten * Daten müssen nicht erst in eine Standardnorm umgeformt werden.

Nachteile von DT: * Tendenz zum „Overfitting“. Die Trainingsdaten werden – ohne (pre-)pruning – zu 100% einem Knoten zugeordnet. Der Akzeptanztest für die Testdaten fällt in der Regel schlechter aus, daher gilt * eine geringere Generalisierungsmöglichkeiten des Modells

Um die Nachteile auszugleichen, verwendet man in der Praxis eher mehrere Decision Trees (→ siehe Random Forest) an.

Zurück zu Supervised Learning