Hol' Dir diese Lernkarten, lerne & bestehe Prüfungen. Kostenlos! Auch auf iPhone/Android!

Mittlerer Quadratischer Fehler

1

Für ein Feature:



Für mehrere Features:
h_theta(x) = x^T * theta

m....Anzahl an trainingsdatensätzen
n....Anzahl an Eigenschaften (Features)
Die designmatrix X besteht aus den Eigenschaften (Features) der trainingsdaten (wobei immer ein x_0 = 1 dazu gehört) untereinander angeordnet.
Sie hat die dimension m x (n+1). D.h. m Zeilen mit n+1 spalten (von x_0 bis x_n).

= Ideale Parameter bis



Wichtigste Komponente
...Moore Penrose Pseudoinverse von
...design matrix
...output vector

Durch das einbinden der nicht-linearen eigenschaften in die Designmatrix . (design matrix with non-linear features)
Die Hypothese behält die gleiche Form aber die Werte in der Designmatrix ändern sich.
z.b.

Es wird eine nichtlineare Basisfunktion angewendet.

Das ist eine nichtlineare Regression bei der die Eigenschaften (Features) potenzen von x sind.

Das sind nichtlinear basisfunktionen bei denen Gaus'sche Glockenkurven verwendet wird.
Jede Basisfunktion hat einen Mittelpunkt im Eingangsraum.
Alle Basisfunktionen teilen sich ein sigma das die breite der Basisfunktion angibt.

Logistic regression ist eine Methode für binäre Klassifikation.

Logistic regression benutzt eine sigmoide basisfunktion. Diese ist gegenüber der Sprungfunktion ableitbar (für gradiant descent notwendig) und besitzt zusätzliche information über die sicherheit der vorhersage.

wenn y = 1 oder für y = 0
 
Mittelwert über Kostenfunktion:


Diese Funktion ist convex (d.h. einzigartiges lokales / globales minimum).

Bei einer adaptiven Lernrate wird die Lernrate leicht erhöht wenn sich der Wert der Kostenfunktion seit den letzten Parametern verringert hat.
Wenn der Wert der Kostenfunktion für die neuen Parameter höher ist als für die alten dann werden die neuen Parameter nicht übernommen und die Lernrate moderat verringert.

Um eine Hypothese zu bewerten werden die vorhandenen Datensätze in 2 Teile geteilt.
Ein Satz Trainingsdaten mit denen die Hypothese gebildet wird und ein Satz Testdaten (die nicht für die Hypothesenbildung verwendet werden) mit denen die Hypothese getestet wird.

Wenn die Hypothese zu stark an die Trainingsdaten angepasst ist (over-fitting) dann ist der fehler bei den Trainingsdaten zwar geringer aber der fehler bei den Testdaten hoch.

Wenn die Hypothese zu schwach an die Trainingsdaten angepasst ist (under-fitting) dann ist der fehler bei den Trainingsdaten und bei den Testdaten höher als er sein müsste.

Wenn die Hypothese genau richtig komplex ist dann ist der fehler bei Trainings und Testdaten minimal.

Wenn die Hypothese zu stark an die Trainingsdaten angepasst ist (over-fitting) dann ist der fehler bei den Trainingsdaten zwar geringer aber der fehler bei den Testdaten hoch.

Wenn die Hypothese zu schwach an die Trainingsdaten angepasst ist (under-fitting) dann ist der fehler bei den Trainingsdaten und bei den Testdaten höher als er sein müsste.

Wenn die Hypothese genau richtig komplex ist dann ist der fehler bei Trainings und Testdaten minimal.

Hier ist die Idee das man noch abstraktere Parameter einführt (komplexität des models, art des Lernalgorithmuses) und die Daten in 3 Teile teilt.
Trainingsdaten, Validierungsdaten und Testdaten.
Aus den Trainingsdaten werden die Hypothesen gebildet (für verschiedene abstrake Parameter).
Über die Validierungsdaten wird jene Hypothese ausgewählt die den geringsten fehler bei den Validierungsdaten hat.
Über die Testdaten wird die performance der ausgewählten Hypothese abgeschätzt.

Hier ist die Idee das man noch abstraktere Parameter einführt (komplexität des models, art des Lernalgorithmuses) und die Daten in 3 Teile teilt um verschieden Modelle zu testen.

Trainingsdaten, Validierungsdaten und Testdaten.
Aus den Trainingsdaten werden die Hypothesen gebildet (für verschiedene abstrake Parameter).
Über die Validierungsdaten wird jene Hypothese ausgewählt die den geringsten fehler bei den Validierungsdaten hat.
Über die Testdaten wird die performance der ausgewählten Hypothese abgeschätzt.

Hier ist die Idee das man noch abstraktere Parameter einführt (komplexität des models, art des Lernalgorithmuses) und die Daten in 3 Teile teilt um verschieden Modelle zu testen.

Trainingsdaten, Validierungsdaten und Testdaten.
Aus den Trainingsdaten werden die Hypothesen gebildet (für verschiedene abstrake Parameter).
Über die Validierungsdaten wird jene Hypothese ausgewählt die den geringsten fehler bei den Validierungsdaten hat.
Über die Testdaten wird die performance der ausgewählten Hypothese abgeschätzt.

Verschiedene lernalgorithmen werden also mit dem selben Trainingset gefüttert.
Daraus entstehen verschiedene Hypothesen.
Über die Validierungsdaten wird jene Hypothese ausgewählt die den niedrigsten validation error (kosten) hat.
Über die unabhängigen Testdaten wird der testfehler / testkosten der ausgewählten Hypothese bestimmt.

Es gibt biologische neurale Netzwerke (gehirn) und künstliche neurale netzwerke (ANN).

Bei den ANNs unterscheide man noch zwischen:

• Feedforward Networks
• Self Organizing Maps
• Recurrent Networks
• Spiking Neural Network

Artificial Neural Networks sind netzwerke aus Neuronen. Diese Neuronen erhalten gewichtete Eingangswerte und berechnen dann den Ausgang des Neurons über eine Aktivierungsfunktion (z.b. step-function, sigmoide Funktion etc...).

Ein künstliches Neuron besteht aus:
x....Input vektor (x0,...xn) (x0 = 1)
w...Weights (w0,...wn) (w0 = b)
b....bias / offset
f....Activation funktion
z...output

z = f(w^T*x)

Die Aktivierungsfunktion ist eine funktion die den Output (z) des Neurons basierend auf den gewichten (w) und dem eingang (x) berechnet.

Beispiele für Aktivierungsfunktionen sind:

• Step-function (für binäre Klassifikation)
• Lineare Funktion (für lineare Regression)
• Sigmoide-Funktion (für nichtlineare-regression und klassifikation)

Perceptron ist das einfachste neurale Netzwerk für die klassifikation linear trennbarer Daten. Es ist also ein linearer, binärer Klassifikator.
Perceptron besteht aus einem Neuron mit der Step-Funktion als Aktivierungsfunktion.

Wenn die Trainingsdaten linear trennbar sind dann konvergiert der Algorithmus.
Wenn die Trainingsddaten nicht linear trennbar sind dann konvergiert der Algorithmus nicht.

Wenn die Trainingsdaten linear Trennbar sind dann existieren gewichte w sodass
a = w^T*x^(i) < 0 für alle x^(i) in Klasse 0
a = w^T*x^(i) >= 0 für alle x^(i) in Klasse 1
f(a) = 0 für a < 0
f(a) = 1 für a >= 0

Wenn das Sample richtig klassifiziert wurde ändern sich die Gewichte nicht.
Wenn das Sample falsch klassifiziert wurde ändern sich die gewichte folgendermaßen:
w := w + eta*(y^(i)-z)x^(i)

Für jedes Sample x^(i) der Trainingsdaten:
keine Änderung der Gewichte wenn das Sample richtig klassifiziert wurde (also z = 0 für y^(i) = 0 und z = 1 für y^(i) = 1).


Wenn das Sample falsch klassifiziert wurde ändern sich die gewichte folgendermaßen:
w := w + eta*(y^(i)-z)x^(i)

Wenn die Daten nicht linear trennbar sind dann kann kein linearer Klassifikator alle Daten richtig klassifizieren (also auch Perceptron nicht).

Bei Perceptron konvergiert der algorithmus nicht wenn die daten nicht linear trennbar sind.

Ja aber nur wenn man Perceptron erweitert (Kernel Perceptron). Normalerweise kann Perceptron nichtlineare Daten nicht korrekt klassifizieren.

Bei feed forward architektur besteht das Netzwerk auf verschiedenen Knoten (Neuronen) die miteinander verbunden sind.
In diesem Netzwerk gibt es keine Kreise oder Rückwärtsbewegung.
Die Inputinformation wird von den Inputneuronen zu den Outputneuronen ausgebreitet.

Das Hidden Layer ist eine (oder mehrere) Ebenen von Neuronen zwischen Input und Output Neuronen.
Diese haben die gewichteten Ausgänge der vorhergehenden Neuronen als Eingang.
Damit ist es möglich nichtlineare Funktionen und die kombination von Inputvariablen abzudecken.

Wenn die Output Neuronen eine sigmoide aktivierungsfunktion haben dann implementiert das ANN eine Klassifikation.

Wenn die Output Neuronen eine lineare Aktivierungsfunktion haben dann implementiert das ANN die Regression.

Perceptron kann XOR nicht lösen (nicht linear trennbar).
MLP kann XOR lösen.

Jede Bool'sche Funktion kann mit einem Hidden Layer abgebildet werden (benötigt aber eventuel exponentielle Anzahl an Hidden Neurons).

Jede begrenzte kontinuierliche Funktion kann mit beliebig kleinem Fehler von einem ANN mit einem Hidden Layer abgebildet werden.

Das credit assignment problem ist das Problem herauszufinden welcher Teil eines Systems / Gruppe wieviel zum Erfolg / Misserfolg beigetragen hat.
Im Falle von ANNs geht es darum herauszufinden wieviel jedes Neuron am Fehler 'schuld' ist.

Der backprop. Algorithmus besteht aus 2 Schritten.

Im ersten Schritt wird die Aktivierungsfunktion und der Output z aller Neuronen berechnet.

Im zweiten Schritt wird das Netzwerk vom Output Layer bis zum Input Layer rückwärts durchgegangen und der Fehler jedes einzelnen Neurons berechnet und nach hinten fortgepflanzt.

Für die Samples wird als Fehlerfunktion die Summe des quadratischen Fehlers verwendet.
E^(i) = 1/2 Summe von k = 0 bis K über (z_k - y_k)^2

Durch die Leistung moderner GPUs ist es backpropagation möglich spitzenresultate zu erziehlen.

Fehler für output neurons


Fehler für hidden neurons

Beim online learning wird nach jedem Sample der Fehlergradient berechnet und die Gewichte werden nach jedem Sample aktualisiert.

Beim batch learning werden die Fehelrgradienten aufsummiert und die Gewichte werden nach erst aktualisiert wenn alle Samples gesehen wurden.

ANN mit einem Hidden Layer.
Aktivierungsfunktion des Hidden Layers muss eine sigmoide Funktion sein.

Wenn die Aktivierungsfunktion im Output Layer ebenfalls eine sigmoide Funktion ist dann implementiert das ANN eine Klassifikation.

Wenn die Aktivierungsfunktion im Output Layer eine lineare Funktion ist dann implementiert das ANN Regression.

The margin of seperatio ist der Bereich um die Entscheidungsgrenze in der sich keine Samples befinden.
Eine große margin of seperation bedeutet eine sehr klare Trennung zwischen den (zwei) Klassen.

Supportvektoren sind:

• die nähesten Punkte (samples) zur Entscheidungsgrenze (Hyperebene)
• wichtig für die definition der optimalen Entscheidungsgrenze.

Support Vector Machine.
Es ist eine lernmethode bei der versucht wird eine optimale Seperationshypereben zu finden bei denen der Normalabstand der nähesten Samples zur Seperationsebene maximiert wird.

Die seperationshyperebene ist eine Mehrdimensionale Ebene (eine Dimension weniger als die Daten) mit der form:


Die Diskriminante bestimmt in welche Klasse eine Sample gehört mit der form:

Die Distanz eines Samples zur Hyperebene ist definiert als:

wobei die Euklidische Norm von ist.

Maximizing the margin is equivalent to minimizing .

SVMs funktionieren nur wenn die Daten linear trennbar sind (eventuell über Kernel Funktion).
Um mit Outlieren bzw. falschen Samples (mislabled) umgehen zu können ist die idee eine Slackvariable einzuführen und so auf die wichtigkeit von bestimmter Samples rücksicht nehmen zu können.

Kernelfunktionen sind funktionen die das innere Produkt zwischen Datenpunkten in einem Raum liefern.
Dadurch kann man in höherdimensionalen Impliziten Räumen arbeiten ohne explizit das mapping zu berechnen.
Dies ist oft schneller als die explizite Berechnung (dies wird als Kernel Trick bezeichnet).

Given a set of training data that is not linearely separable, one can with high probability transform it into a training set that is linearly separable by projecting it into a higher dimension space via non-linear transformation.

Der Kernel Trick ist die Tatsache das die implizite Rechnung über Kernelfunktionen (Inneres Produkt zwischen Datenpunkten in einem anderen Raum) oft schneller ist als die explizite Berechnung des mappings.

The kernel matrix must be symmetric positive definite.

Multiclass classification:
Jedes Sample gehört zu genau einer von N Klassen.

Multilable classification:
Jedes Sample hat eine Anzahl von Lables (mehrere Klassen).

Entweder classifier die direkt multiclass unterstützen:

• Decision trees
• Naive Bayes
• Multiclass SVM

oder binäre classifier mit verschiedenen Methoden für Multiclass adaptieren:

• One vs. All (OVA)
• One vs. One (OVO)
• Error Correcting Output Codes (ECOC)

One vs. All
Eine Methode mit der man mittels einem Binären Classifier Multiclass classification realisieren kann.
Dabei werden N Classifier trainiert wobei jeder einzelne Unterscheiden kann ob ein sample x in der Klasse n_i ist oder nicht.
Ein neues Sample wird dann von allen Classifieren einmal klassifiziert und es wird die Klasse mit der höchsten Zuversicht ausgewählt.
Class = arg max h_k ( x^(i))

Bei OVA (One vs. All) werden für N Klassen N Klassifier gelernt wobei jeder einen gegen alle anderen testet (ist x in Klasse n oder nicht).

Bei OVO (One vs. One) werden für N Klassen N * (N-1) / 2 Klassifier gelernt wobei jeder Klassifier Entscheidet ob ein Sample in Klasse A, in Klasse B oder weder noch ist.
Am Ende wird ein Sample jener Klasse zugeordnet für die es die meisten Stimmen erhalten hat.

Error Correcting Output Codes

Jede Klasse wird durch einen binären Code der Länge n repräsentiert.
Jedes Bit gehört zum Output eines Klassifiers.
1 Klassifier pro Bit.
Nachdem die Klassifier ihren Output produziert haben wird der näheste binärcode gesucht um so die Klasse zu entscheiden (nähe wird euklidische Norm, Manhattan o.a. bestimmt).

The confusion matrix tells us how often a sample that should have been x was classified as something different and it tells us what it was classified as.
From this it is easy to see if the classifier confuses two classes.
This can be used to improve the accuracy of the system by introducing new features to the classifier responsible for seperating specific classes.

Lazy Learning
The system tries to generalize the training data before receiving queries (-> Neural Networks)

• +target function approximated globally
• +deals with noise in the training data
• -unable to provide good local approximations

Eager Learning:
The system does not generalize until a guery is made to the system (-> k-NN)

• +target function approximated locally
• -large space requirements to store the entire training dataset
• -slow to evaluate

New problem instances are compared with instances seen in training phase (stored in memory) instead of performing explicit generalization (lazy learning).

Hypothesis

• Constructed on the fly directly from the training instances
• The complexity can grow with the data
• In the worst case it is a list of all training samples

Advantage

• Adapt the model to previous unseen data

k-NN stands for k nearest neighbors.
It is one of the simplest machine learning algorithm (instanced based learning).

For a new sample look at the k closest samples (use some distance metric like Euclidean).
Assign the new sample to the most frequent occuring class within those k samples.

If you only look at a small number of neighbors the decision boundary between classes is very distinct.
A large value of k reduces the effect of noise on the classification but the boundary between classses becomes less distinct.
The best choice of k depends on the data.

Training
Basically non-existing. Store the training samples and maybe perform some preprocessing to speed up queries (feature extraction, dimensionality reduction)

Testing
For classification look at the k nearest neighbors and pick the class with the most votes.

For regression average the values of the k nearest neighbors.

k-NN works best when there is lots of data avaiable and the data has a small amount of features.

Pros:

• Easy to implement
• Very fast training
• No information loss
• high classification accuracy if lots of data is avaiable
• Intuitive interpretation
• Can have very complex decision boundaries

Cons:

• Requires lots of memory to store all the data samples
• Slow query time
• Sensitive to the local structure of the data
• The parameter k needs to be tuned

Overfitting is the result of an overly complex models where the learned function h(x) essentially 'connects the dots' of the training data.
This results in a low training error but a high test error.

Use model selection to automatically select the right model complexity.
Use regularization to keep parameters small.

A Validation Set is a Set of Data used for model selection.
Model selection takes a number of Hypothesis' and a Validation Set and returns a selected hypothesis with the smallest error on the validation set.

Cross validation is the idea to take the avaiable Data and split it into multiple parts and then use some of those parts as the training data and some as validation data. This is done over multiple rounds with the parts used for training and the parts used for validation changing.
This gives us insight on ho wthe model will generalize to an independent dataset in order to limit problems like overfitting.

2-fold is the simplest methode where the data is split into two equal parts.
Train on the first fold and validate on the second and vice versa.

Leave-one-out cross-validation splits the data into k equal parts where k is the number of samples in the training set.
Use a single sample as a validatoin set and all the rest as training set (k times).

Bias is how accurate a model is across different training sets (how general a model is).

Variance is how sensitive a model is to small changes in the training set.

Error = Variance + Bias^2 + Noise
We want to minimize the bias and the variance of the model error.
High bias -> underfitting (model too simple)
High variance -> overfitting (model too complex)

To achieve good performance on data outside the training set a tradeoff must be made.

Regularization is a system to penalize models with extreme parameters values.
instead of minimizing the cost function we minimize

Weight decay
Early stopping

Überwachtes Lernen
Gegeben sind Daten x_1 ... x_n und Zielwerte t_1 ... t_n

Unüberwachtes Lernen
Hier sind nur Daten x_1 ... x_n gegeben aber keine Zielwerte. (z.b. Maximum-Likelihood Schätzer, Bayes Schätzer)

Reinforcement Lernen
Lernen ohne unmittelbare Rückmeldung ob die Zwischenschritte korrekt sind, nur das Resultat wird bewertet (z.b. Roboter sucht Würfel, feedback erst nachdem er das Objekt gefunden hat).

P(X,Y) = P(X | Y) P(Y)
            = P(Y | X) P(X)

Die Klassifikation erfolgt anhand der Warscheinlichkeit für Klasse t gegeben die Objektbeschreibung x. d.h. P(t | x) ist notwendig.
Wenn z.b. P(t = 1 | x) > P(t = 2 | x) ist dann wählt man Klasse 1.
Die posterior Wahrscheinlichkeit kann über den Satz von Bayes formuliert werden.



P(x | t) ... Likelihood
P(t)      ... prior Wahrscheinlichkeit
P(t | x) ... posterior Wahrscheinlichkeit

iid steht für independent identically distributed
idd heißt, dass die Samples x_1,...,x_n statistisch unabhängig sind und von der gleichen Wahrscheinlichkeitsverteilung stammen.

Der EM-Algorithmus ist ein iterative Algorithmus zum Lernen von Gaußschen Mischverteilungen.
Zuerst werden die Parameter initialisiert.

Im E-Step können auf Grund der Parameter die Zugehörigkeitswahrscheinlichkeiten berechnet werden.

Im M-Step (maximierender Schritt) werden die Parameter und unter Zuhilfename von neu berechnet.

Der E und der M-Step werden abwechselnd durchgeführt bis die log-Likelihood-Funktion konvertgiert.

1. Initialisierung
2. E-Step: Klassenzugehörigkeit ausrechnen
   
3. M-Step: Berechnen der Parameter
4. Evaluieren
   
      -> falls konvergiert Abbruch
      -> falls nicht konvergiert => E-Step

Das Ziel von K-means ist es die Daten in Cluster einzuteilen.
K ist dabei die Anzahl der Cluster.
Der K-means Algorithmus ist eine modifikation des EM-Algorithmus für Gaussian Mixture Models (GMMs).

Unterschiede zwischen EM und K-means:

• d.h. kann vernachlässigt werden da es nicht modifiziert wird.
• Es werden alle Komponenten durch die gleiche sphärische Kovarianzmatrix dargestellt.
• Jedes Sample wird von einer Komponente modelliert.

1. Initialisierung: Wähle K Samples zufällig für die Clusterzentren aus
2. Step 1: Klassifikation der Samples zu den Komponenten
3. Step 2: Neuberechnung der Mittelwertvektoren (Schwerpunkt der Cluster)
4. Evaluierung der kumulativen Distanz
    falls Distanz konvergiert dann sind die optimalen Clusterzentren gefunden
    falls Distanz nicht konvergiert => Step 1

Unigramm Grammatik Modell
Hier wird die Anname getroffen, dass keine Abängigkeit zwischen den Wörtern besteht. d.h. die Wörter sind iid.
Das Problem ist das P(Ich gehe einkaufen) = P(einkaufen ich gehe) ist. Grammatikalisch richtige haben also keine höhere Wahrscheinlichkeit als gramatikalisch falsche.

Bigramm Modell
Hier handel es sich um ein Markov Modell 1. Ordnung. Hier wird jeweils das Anfangswort und die Übergangswahrscheinchkeit zwischen einem Wort und seinem Nachfolger berücksichtigt.

Trigramm Modell
Dies ist ein Markov Modell 2. Ordnung, der Kontext wird auf 2 vorangegangene States ausgeweitet, wärend bei einem Markov Modell 1. Ordnung nur ein vorgegangener State berücksichtigt wird.

Das Markov Modell ist zur Modellierung von Sequenzen geeignet, d.h. es modelliert explizit die Abhängigkeit zwischen den Samples.
Die iid Anname wird zum Teil vernachlässigt.

Das Markov Modell besteht aus einer Menge der Zustände, den Anfangswahrscheinlichkeiten und den Übergangswahrscheinlichkeiten .
Die Übergangswahrscheinlichkeiten sind in der Übergangsmatrix A zusammengefasst.

Ein Problem für das Markov Modell ist die Tatsache das die Anzahl an Wahrscheinlichkeiten exponentiell mit der Satzlänge N steigt. Bei 1000 States (z.b. Wörter) und einer Satzlänger von N= 10 gibt es bereits 1000^10 Wahrscheinlichkeiten.
Durch das Einführen des Kontext kann man sich hier abhilfe schaffen. Dbaei werden nur Sequenzen bestimmter länger zusammen bewertet.

Im Unterschied zum Markov Modell ist beim Hidden Markov Modell der State nicht direkt beobachtbar (=hidden).
Es gibt aber Beobachtungen X_n die stochastisch mit dem State Q_n zum selben Zeitpunkt n zusammenhängen.

Das HMM hat zusätzlich zu den Parametern des MMs noch die Beobachtungswahrscheinlichkeit B.


Desweiteren gilt das die Beobachtung nur zum State abhängt.