Regression und (binäre Klassifikation) (Week 1-3)

Arten von ML

Es können zwei Grundsätzliche Arten von Machine Learning unterschieden werden:

  • Überwachtes Lernen (Supervised Learning)
  • Unüberwachtes Lernen (Unsupervised Learning)

Beide Arten versuchen, Informationen aus einem Haufen Daten zu gewinnnen. Das Vorgehen/die Fragestellung ist aber unterschiedlich:

Supervised Learning Unsupervised Learning
Fragestellung Ich kenne die möglichen Resultate und versuche, aus unbekanntem Input das Resultat zu ermitteln. Ich kenne die möglichen Resultate nicht und versuche stattdessen, aus unbekanntem Input Cluster aller Art aufgrund von gemeinsamen Merkmalen/Ähnlichkeit zu bilden
ML-Methoden
  • Regression
  • Klassifikation
  • Clusterbildung
ML-Algorithmen
  • lineare Regression
  • logistische Regression
  • neurale Netze
  • K-Means
  • PCA

Supervised Learning

Beim überwachten Lernen können wiederum zwei unterschiedliche Problemstellungen unterschieden werden:

  • Regressionsprobleme
  • Klassifikationsprobleme

Beide Problemstellungen versuchen, aufgrund von bekannten Daten (Trainingsset) Aussagen über unbekannte Daten zu machen. Die Art der Aussage (das Ergebnis) ist jedoch unterschiedlich:

Regressionsproblem Klassifikationsproblem
ML-Methode lineare Regression Logistic Regression
Neurale Netze
Support Vector Machines (SVM)
gelernte Eigenschaft Für zuvor nie gesehene Eingangsdaten wird eine ein kontinuierlicher Wert vorausgesagt.

Beispiel: Bestimmung des Verkaufspreises von Häusern aufgrund der Anzahl Zimmer.

Zuvor nie gesehene EIngangsdaten werden in Klassen unterteilt.

Beispiel: Handschriftenerkennung

 

Resultat Zahl (Beispiel: Verkaufspreis) Klasse (Beispiel: Ziffer aus dem Alphabet)

Modell/Hypothese

Um eine Aussage über den zu erwartenden Wert für unbekannte Daten machen zu können, muss ein optimiertes Model gebildet werden, welches aufgrund von Eigenschaften (z.B. Anzahl Zimmer, Grundstückgrösse, …) möglichst genaue Aussagen zu einer gesuchten Information (z.B. Verkaufspreis) machen kann. Ein Modell besteht aus:

  • Hypothese: In Form einer beliebigen Funktion (z.B. linear, polynomial, etc…). Die Hypothese enthält:
    • Features: Eigenschaften, von welchen auf die gesuchte Information geschlossen werden kann
    • Parameter: Werte/Gewichte der Eigenschaften. Pro Feature existiert 1 Parameter, dessen Wert den Einfluss der Eigenschaft auf die Zielinformation wiedergibt. Diese Parameter sind zunächst unbekannt. Für ein gutes Modell müssen optimale Werte für die Parameter gefunden werden, so dass die Hypothese möglichst genau zutrifft.
  • Trainingsset: Satz von Items, bei denen die Werte für die Features (Anzahl Zimmer, Grundstücksgrösse, …) sowie die Zielinformation (Verkaufspreis) bekannt ist. Auch die gesuchte Zielinformation muss pro Trainigsitem bekannt sein.
  • Kostenfunktion: Misst die Abweichung zwischen von der Hypothese berechnetem Wert und dem tatsächlichen (bekannten) Zielwert aus dem Trainingsset.

Modellbildung

Grundsätzliches Vorgehen bei Modellbildung:

Schritt Beschreibung Ergebnis/Aussage Symbol/math. Repräsentation
Daten für Trainingsset sammeln Daten mit bekannten Parametern und Ergebnissen Trainingsset mit i Elementen x^{(i)} (Eingabewerte)

y^{i} (Ergebnisse)

Hypothese bilden Die Hypothese ist eine beliebige Funktion (linear, Exponentialfunktion, Hyperbel, …) mit Parametern Vorhersage des gewünschten Wertes/Klasse. h(x) (Funktion)

\Theta (Parameter)

Kostenfunktion  Misst die Qualität der Hypothese durch Vergleich von (bekanntem) erwarteten Wert aus dem Trainingsset und von der Hypothese berechnetem Wert. Die Kostenfunktion ist eine Funktion von \Theta und bildet somit die Kosten für beliebige Werte von \Theta ab.

Eine beliebte Kostenfunktion ist der mittlere Quadrierte Wert (mean squared error), welcher die Qualität in Form des durchschnittlichen Gesamtfehlers ausgibt:

\frac{1}{2m} \sum_{i=1}^{(m)}  (h_\Theta(x_i)-y_i)^2

(Summe aller Abweichungen im Quadrat geteilt durch Anzahl Elemente)

Qualität der Funktion für bestimmte Werte für \Theta J(\Theta) (Kostenfunktion)
Minimisierung der Kosten Die optimalen Parameter für die Hypothese können gefunden werden, indem das globale Minimum der Kostenfunktion gefunden wird. Minimaler Fehler / beste Parameter

Minimierung der Kosten

Die Kosten können für jedes \Theta (Parameter-Set) berechnet werden. Die berechneten Werte können auch als Graph geplottet werden. Das optimale \Theta ist dasjenige mit den kleinsten Kosten. Deshalb wird das globale Minimum der Kostenfunktion gesucht. Dies kann auf zwei unterschiedliche Arten erreicht werden:

  • Gradientenabstieg
  • Normalengleichung

Gradientenabstieg

 

Lineare Regression: Kostenminimierung Gradientenabstieg
\Theta_j = \Theta_j - \alpha\frac{\partial}{\partial \Theta_j} J(\Theta)

Element Bedeutung
\Theta_j aktueller/neuer Parameterwert
\alpha Lernrate (konstant)
\frac{\partial}{\partial \Theta_j} Partielle Ableitung nach \Theta_j
J(\Theta) Wert der Kostenfunktion für das aktuelle Parameterset

Die Ableitung der Kostenfunktion ist wie folgt definiert:


Credit: coursera.org

Es wird an einem beliebigen Punkt die  Ableitung der Kostenfunktion gebildet.  Pro Parameter (\Theta_{0}, \Theta_{1}, \Theta_{2}, ...) muss eine partielle Ableitung gebildet werden. Danach wird geloopt:

\Theta_j := \Theta_j - \alpha \frac{1}{m} \sum_{i=1}^m (h_\Theta(x^{(i)}) - y^{(i)}) x_j^{(i)}

Mithilfe des Ausgangspunkt, einer konstanten Schrittweite \alpha (learning rate) und dem Wert der Steigung wird der nächste Punkt auf der Kurve berechnet. Dort wieder die Ableitung gebildet. Da bei einer positiven Steigung der zweite Teil der Gleichung negativ wird, verringert sich der Wert für das neue \Theta (bewegt sich nach links), für negative Werte vergrössert er sich (bewegt sich nach rechts).

Es muss darauf geachtet werden, für alle partiellen Ableitungen dieselben Parameterwerte zu verwenden (simultaneous update). Das wird so oft wiederholt, bis die Konvergenz erreicht ist. Die Konvergenz ist dann erreicht, wenn die Ableitung 0 ist oder der Unterschied zum vorherigen Wert nur sehr klein ist.

Wahl der Lernrate

Da die Ableitung rechts vom Minimum positiv und links vom Minimum negativ ist nächert man sich beim Gradientenabstieg immer in Richtung globales Minimum. Der Algorithmus konvergiert, auch wenn die Schrittweite konstant ist, da der Wert für die Ableitung kleiner wird, je näher man dem Minimum kommt.

Beim Gradientenabstieg ist zu beachten:

  • Eine zu grosse Lernrate kann dazu führen, dass das Resultat nicht konvergiert.
  • Eine zu kleine Lernrate kann die Berechnung extrem verlangsamen
  • Der Gradientenabstieg funktioniert nur bei konvexen Kostenfunktionen zuverlässig. Ansonsten besteht die Gefahr, nur ein lokales Minimum zu finden.

Kostenminimierung mit Normalengleichung

Alternativ zum Gradientenabstieg können die minimalen Kosten auch mithilfe der Normalengleichung berechnet werden. Dazu wird das Trainingsset von m Elementen mit jeweils n Features als Matrix X (Dimension: m \times (n+1)) und die bekannten Werte als Vektor y (Dimension: m) dargestellt:

Credit: coursera.org

Die Formel lautet dann:

Lineare Regression: Kostenminimierung durch Normalengleichung
\Theta = (X^TX)^{-1}X^Ty

Normalengleichung vs. Gradientenabstieg

Welche Methode man zur Berechnung der minimalen Kosten nimmt ist grundsätzlich egal. Je nach Ausgangslage hat eine Methode aber Vor- oder Nachteile gegenüber der anderen.

Gradientenabstieg Normalengleichung
Lernrate \alpha muss bestimmt werden und kann zu gross oder zu klein sein Lernrate \alpha wird nicht benötigt
iterativer Algorithmus keine Iteration
weniger komplex als Normalengleichung (O(kn^2) Komplexer als Gradientenabstieg (O(n^3)), da die Inverse von X^TX berechnet werden muss.
Feature Scaling von Vorteil kein Feature Scaling nötig

Weitere Algorithmen

Nebst dem Gradientenabstieg existieren weitere, bessere Algorithmen, um die Minimalen Kosten zu finden:

  • Conjugate Gradient:
  • BFGS:
  • L-BFGS:

Diese Algorithmen passen die Lernrate automatisch an und konvergieren somit rascher. Sie sind aber auch komplexer!

Regressionsprobleme

Für Regressionsprobleme wird ein linearer Wert berechnet. Die Hypothese hat die folgende Form:

Repräsentation der Hypothese für Regressionsprobleme
h_\Theta(x)=\Theta^Tx

Kostenfunktion

Die Kostenfunktion misst die Genauigkeit der Hypothese. Als Beispiel sei hier die Mean Squared Error Function angegeben.

Lineare Regression: Mean Squared Error Function
\displaystyle  J( \Theta) = \frac{1}{2m}\sum_{i=1}^{m} (h_0(x_i)-y_i)^2

Durchschnitt aller quadrierten Abweichungen vom Hypothesenwert zum bekannten Wert aus dem Trainingsset.

Regression mit mehreren Eigenschaften

Eine Hypothese kann beliebig viele Eigenschaften (multiple features) berücksichtigen. Pro Feature wird ein Parameter benötigt, welcher den Einfluss des Features auf die Hypothese gewichtet. Zusätzlich wird ein Parameter für das 0te Feature benötigt, welches den konstanten Wert 1 hat. Bei n Features werden also n+1 Parameter benötigt, wie beispielsweise bei folgendem Polynom:

h_0(x) = \Theta_0 + \Theta_1 x_1 + \Theta_2 x_2 + \Theta_3 x_3 + ... + \Theta_n x_n

Dies kann auch als Vektormultiplikation dargestellt werden:

h_\Theta (x) =  \begin{bmatrix}\Theta_0 && \Theta_1 && ... && \Theta_n \end{bmatrix}  \begin{bmatrix}x_0 \\ x_1 \\ ... \\ x_n\end{bmatrix}  = \Theta^T x

Die Minimierung der Kosten mittels Gradientenabstieg/Normalengleichung funktioniert genau gleich wie oben beschrieben. Beim Gradientenabstieg muss bei n Features einfach n-mal abgeleitet werden. Bei der Normalengleichung werden einfach die Matrixdimensionen grösser.

Optimierungsmassnahmen

Um die Berechnung der optimalen Parameter zu optimieren gibt es verschiedene Möglichkeiten:

  • Wahl einer passenden Funktion für die Hypothese: Je nachdem passt z.B. eine Exponentialfunktion besser auf die Trainingsdaten als ein Polynom
  • Kombination oder Weglassen von Features
    • Falls einige Features redundant sind können sie weggelassen werden.
    • Falls einige Features direkt abhängig von einem anderen Feature sind, können die Features zu einem einzigen Feature kombiniert werden, z.B. indem man sie miteinander multipliziert
  • Speziell für Gradientenabstieg: Beschleunigen der Konvergenz

Beschleunigen der Konvergenz (Gradientenabstieg)

Um das Konvergieren beim Gradientenabstieg zu beschleunigen gibt es zwei Techniken.

  • Mean Normalization: Vom Wert wird der  Durchschnitt aller Werte subtrahiert
  • Feature Scaling: Die Werte werden in einen ähnlichen Bereich gebracht, indem sie durch den Range geteilt werden

Beide Techniken werden kombiniert und durch folgende Formel repräsentiert:

x_i := \frac{x_i - \mu_i}{s_i}

Element Erklärung
\mu_i Durchschnitt aller Werte
s_i Range (Differenz zwischen grösstem und kleinstem Wert)

Klassifikationsprobleme

Bei Klassifikationsprobleme wird ein diskreter Wert (Klasse) berechnet.

Binäre Klassifikation

Bei die Klassifikation in zwei Zielklassen (binäre Klassifikation) existiert ein spezieller Algorithmus für die Modellbildung: Logistic Regression. Der Name ist ein wenig irreführend, da er eigentlich nichts mit Regressionsproblemen zu tun hat.

Die Hypothese hat die Form:

Repräsentation der Hypothese für Klassifikationsprobleme
\displaystyle  h_\Theta(x) = g(z) = \frac{1}{1+e^{-\Theta^Tx}}

g(z) ist die Sigmoid-Function (s.u.) für z= \Theta^Tx

Sigmoid Function

Bei der Logistic Regression wird der von der Hypothese berechnete Wert in einen Bereich zwischen 0 und 1 gebracht. Dazu wird eine Funktion (Logistic/Sigmoid Function) der folgenden Form verwendet:

Sigmoid Function (=Logistic Function)
\displaystyle  g(z) =\frac{1}{1+e^{-z}}

Der Input für die Sigmoid-Funktion (\Theta^Tx) muss dabei nicht unbedingt eine lineare Funktion sein, sondern kann z.B. auch eine Kreisfunktion sein!

Der berechnete Wert der Hypothese liegt somit immer irgendwo zwischen 0 und 1 und gibt die Wahrscheinlichkeit für die Zugehörigkeit zu einer bestimmten Klasse an. Deshalb gilt für binäre Klassifikation:

Wert für z= \Theta^Tx Resultierender Wert für h_\Theta(x) = g(z) Zielklasse y Bemerkung
\geq 0 \geq 0.5 \approx 1 Für sehr grosse Werte von z= \Theta^Tx strebt h_\Theta(x) = g(z) \rightarrow 1
<0 <0.5 \approx 0 Für sehr kleine Werte von z= \Theta^Tx strebt $latexh_\Theta(x) = g(z) \rightarrow 0$

Kostenfunktion

Die Kostenfunktion ist bei Klassifikationsproblemen (resp. Logistic Regression) eine andere als bei Regressionsproblemen (resp. Linear Regression).

Da die Sigmoid-Funktion nicht linear sondern wellenförmig ist, ist die Kostenfunktion nicht konvex sondern hat viele lokale Optima. Das hat zur Folge, dass beim Gradientenabstieg unter Umständen nur ein lokales, nicht aber das globale Minimum der Kosten gefunden werden kann. Deshalb werden für (binäre) Klassifikationsprobleme unterschiedliche Kostenfunktionen verwendet, je nachdem welchen Wert Sigmoid-Funktion ausgibt:

Logistic Regression: Kosten für einen einzelnen Element aus dem Trainingsset für bestimmte Paprameter
Berechneter Wert (h_\Theta(x) = g(z)) Gewählte Klasse y Kostenfunktion
\geq 0.5 y=1 Cost(h_\Theta(x),y)=-log(h_\Theta(x))
< 0.5 y=0 Cost(h_\Theta(x),y)=-log(1-h_\Theta(x))

Auf diese Weise werden maximale Kosten erzeugt, wenn die Hypothese 1 ausgibt, der tatsächliche Wert aus dem Trainingsset aber 0 ist – oder umgekehrt!

Beide Funktionen können zu einer einzigen Funktion zusammengefasst werden:

Cost(h_\Theta(x),y) = -y \cdot log(h_\Theta(x)) - (1-y) \cdot log (1-h_\Theta(x))

Die Durchschnittlichen Gesamtkosten für alle Daten aus dem Trainingsset können demnach wie folgt berechnet werden:

Logistic Regression: Durchschnittliche Gesamtkosten unter Berücksichtigung aller Werte aus dem Trainingsset für bestimmte Parameter
\displaystyle  J(\Theta) = -\frac{1}{m} \sum_{i=1}^{m}  \Big[  y^{(i)} log(h_\Theta(x^{(i)})) + (1 - y^{(i)}) log(1 - h_\Theta(x^{(i)}))  \Big]  + \frac{\lambda}{2m} \sum_{j=1}^{n} \Theta_j^2

Oder in vektorisierter Form:

J(\Theta) = \frac{1}{m} \cdot (-y^T \cdot log(h) - (1-y)^T \cdot log(1-h))

Falls y gegen 1 strebt wird der zweite Teil der Formel 0 und es bleibt die erste Formel von oben übrig. Falls y gegen 0 strebt wird der erste Teil der Formel 0 und es bleibt die zweite Funktion von oben übrig.

Minimierung der Kosten

Die Minimierung der Kosten kann über den Gradientenabstieg oder Normalengleichung erfolgen, also genau gleich wie bei der linearen Regression. Das vorgehen ist identisch, da aber die Defninition von h_\Theta(x) aufgrund der Anwendung der Sigmoid Funktion anders ist, sind die Ergebnisse nicht gleich.

Klassifikation mit mehreren Klassen

Falls mehrere Zielklassen existieren ist das Vorgehen grundsätzlich identisch bei der binären Klassifikation. Die Wahrscheinlichkeit wird einfach pro Klasse berechnet (diese Klasse vs. alle anderen Klassen, One-vs-All Ansatz). Es wird diejenige Klasse als Vorhersage verwendet, bei der die Wahrscheinlichkeit am grössten ist.

Over-/Underfitting

Es kann sein, dass das Modell sich aus unterschiedlichen Gründen nicht für unbekannte Daten eignet:

  • Overfitting: Das Modell orientiert sich zu stark am Trainingsset und lässt sich nicht für allgemeine Aussagen auf unbekannte Daten anwenden.
  • Underfitting: Das Modell orientiert sich zu wenig stark am Trainingsset und lässt so wichtige Aspekte ausser acht.

Um Overfitting zu verhindern kann folgendes unternommen werden:

  • Features reduzieren:
    • manuelles Auswählen/Weglassen
    • Modell-Selection-Algorithmus (später)
  • Regularisierung: Alle Features behalten aber die Magnitude der Parameter anpassen.

Regularisierung

Falls die Werte für die Parameter \Theta sehr hoch sind bedeutet das, dass das Model sehr stark auf die Trainingsdaten optimiert ist und die Gefahr von Overfitting besteht. Ziel ist es also zu verhindern, dass die Parameter-Werte zu hoch werden, indem der Kostenfunktion ein Term hinzugefügt wird, welche bei hohen Parameterwerten zu hohen Kosten führt und i.d.F. hohe Parameterwerte bestraft werden. Der Regularisationsterm enthält eine Variable \lambda welcher den Grad der Bestrafung bestimmt. Der Wert von Lambda hat also folgende Auswirkung:

Wert für \lambda Bedeutung Auswirkung Gefahr
klein Hohe Werte von \Theta werden kaum bestraft (wenig Regularisierung) Werte von \Theta sind sehr gross Overfitting (Varianz)
gross Hohe Werte von \Theta werden sehr stark bestraft (viel Regularisierung) Werte von \Theta sind sehr klein Underfitting (Bias)

Die Regularisierung kann sowohl für Regressionsprobleme (Linear Regression) als auch für Klassifikationsprobleme (Logistic Regression) angewendet werden. Das Vorgehen ist für Regressionsprobleme und Klassifikationsprobleme leicht unterschiedlich:

  • Regressionsprobleme: Regularized Linear Regression
  • Klassifikationsprobleme: Regularized Logistic Regression

Regularized Linear Regression

Um die Magnitude der Parameter möglichst klein zu halten müssen Parameter mit grossen Werten “bestraft” werden. Der erste Parameter (\Theta_0) ist davon jedoch nicht betroffen.

Gradientenabstieg

Für die “Bestrafung” wird für die iterative Berechnung der Parameter 1-n der folgende Term hinzugefügt:

Regularisierungsterm für Gradientenabstieg
\frac{\lambda}{m}\Theta_j
wobei j\in{1,2,...n}

Die Formel zur Berechnung von \Theta_1 bis \Theta_n ist demnach:

Lineare Regression: Regularisierter Gradientenabstieg
\displaystyle  \Theta_j := \Theta_j - \alpha \Bigg[  \Big(  \frac{1}{m} \sum_{i=1}^m  (h_\Theta(x^{(i)} - y^{(i)})x_j^{(i)}  \Big)  + \frac{\lambda}{m}\Theta_j    \Bigg]

oder etwas umgeformt:
\displaystyle  \Theta_j := \Theta_j(a- \alpha\frac{\lambda}{m})  -\alpha\frac{1}{m}\sum_{i=1}^m(h_\Theta(x^{(i)} - y^{(i)})x_j^{(i)}

Normalengleichung

Bei Verwendung der Normalengleichung wird eine zusätzliche Matrix L benötigt:

L=  \begin{bmatrix}  0 \\  & 1 \\  & & 1 \\  & & & \ddots\\  & & & & 1 \\  \end{bmatrix}

Die Formel zur Berechnung des optimalen \Theta ist dann:

Lineare Regression: Regularisierte Normalengleichung
\Theta=(X^Tx + \lambda\cdot L)^{-1}X^Ty

Regularized Logistic Regression

Bei Verwendung von Logistic Regression ist das Vorgehen ähnlich.

Gradientenabstieg

Wie bei Linear Regression wird bei der iterativen Berechnung der Kosten jeweils ein Regularisierungsterm hinzugefügt. Dieser ist jedoch leicht unterschiedlich von demjenigen bei Linear Regression:

Regularisierungsterm für Logistic Regression
\displaystyle  \frac{\lambda}{2m}\sum_{j=1}^n \Theta_j^2
wobei j\in{1,2,...n}

 

Leave a Reply

Your email address will not be published. Required fields are marked *