03 Lerntheorie

Question 1

Definition: Lernmaschine

Answer 1

Eine lernende Maschine wird bestimmt durch:

• Hypothesenraum {h_alpha : alpha € A}
• Lernverfahren: die Methode um alpha_opt mit Hilfe von Lernbeispielen zu finden. (benötigt Fehlerfunktion, Optimierungsmethode

Das resultierende Entscheidungsmodell M_opt ist i.A. gegeben durch die Auswertung der optimalen Hypothese, die durch die lernenden Maschienen bestimmt wird

Question 2

Probleme beim Lernen

Answer 2

Statistische Problem:

• das Verfahren betrachtet einen - gemessen an der Menge von Trainingsdaten - “zu großen” Hypothesenraum
• Auf Basis der Trainingsdaten eignen sich mehrere Hypothesen gleichermaßen gut

Komplexitätsproblem:

• Aufgrund der Komplexität des Problems kann das lernverfahren nicht das Finden einer optimalen Lösung innerhalb des Hypothesenraumes garantieren.
• Bei Verwendung von speziellen Verfahren oder Heuristiken besteht die Gefahr einer suboptimalen Lösung

Repräsentationsproblem:

• Der Hypothesenraum enthält keine ausreichend gut Approximationen der Zielfunktion / Konzept etc….
• Das Lernverfahren kann einen gewünschten Approximationsgrad nicht liefern.

Question 3

Lernen: Fehlerminimierung

Answer 3

Minimierung des empirischen Fehlers (absoluter Fehler nicht bestimmbar) :

Definiere h_alpha

Finde beste alpha_opt durch iterative Minimierung des empirischen Lernfehlers E_D(h_alpha)

zB Gradientenabstieg

häufiges Problem: empirische Fehlerminimierung führt zu Overfitting

Question 4

Overfitting

Answer 4

Die Tendenz der Maschine sich bei mLernen auf die Lernbeispiele zu spezialisieren (auswendig lernen)

problematisch u.A. bei verrauschten Lerndaten …

Folge: Lernfehler fällt, Testfehler steigt –> Generalisierung fällt

Question 5

Metriken: Fehler und Güte

Answer 5

Klassifiktionsfehler:
errors / total = (FP + FN)/(TP+FN+FP+TN)

Güte:
correct/total = (TP+TN)/(TP+FN+FP+TN)

Falsch Positiv Rate:
FPR = FP/(FP+FN)

Falsch Negativ Rate:
FNR = FN/(TP+FN) = 1-TPR

Question 6

Metriken: Recall und Precision

Answer 6

Precision:
P= TP/(TP+FP)

Recall (aka true positive rate)
R = TPR = TP/(TP+FN)

F1-Maß: harmonisches Mittel von Recall und Precision

F1 = 2/(1/R + 1/P)

Question 7

Bootstrap

Answer 7

Grundgedanke: “Wie kann man mit einfachen Verfahren mehr erreichen?”

Lernen

• ziehe zufällig (mit zurücklegen) aus D jeweils |D| Beispiele m Mal
• bestimme jeweils die Modell Parameter (optimale Hypothese)
• Wiederhole
• Bestimme den Mittelwert, Varianz, … der Metriken des Modells
• -> Analyse der Güte / Stabilität
• -> Nutzen um Modell mit höherer Güte zu finden

Question 8

Bagging

Answer 8

Variante des Boostrap

Verwende mehrere Lernmaschienen

• Verwende Boostrap Prinzip
• ziehe n < |D| Beispiele (mit zurücklegen)
• bestimme die jeweiligen Modelle

Kombiniere die Lernmaschienen (zB gewichtete Summe)

• -> höhere Güte des resultierenden MModells
• -> Aussagen über die stabilität des Modells

Question 9

Boosting für Klassifikation

Answer 9

Idee: Kombiniere “schwache” Modelle um ein gutes Modell zu erhalten

Grundansatz:

• Zerlege D in mehrere Datensätze, z.B. in D1, D2 , D3
• Wähle D1 und bestimme das Modell M1
• Wähle für D2 aus D neue Beispiele s.d. 50% durch M1 korrekt geschätzt werden und erstelle damit M2
• Wähle für D3 Beispiele bei denen M1 und M2 gegensätzlich sind und bestimme M3
• Kombiniere die Modelle:

M = {M1, wenn M1=M2
M3, sonst

Question 10

AdaBoost - Adaptive Boosting

Answer 10

Ausgangspunkt Lernmenge D mit n Beispielen

Iteratives Erstellen eines komplexen Klassifikators in k Stufen (aus k zusammengesetzten Klassifikatoren)

Ziehen von Lernbeispielen entsprechend definierter Gewichte

• Gewichtung der Lernbeispiele entsprechend dem Klassifikationsergebnis des zuletzt generierten „schwachen“ Klassifikators
• Verringerung des Gewichtes korrekt klassifizierter Beispiele
• Erhöhung des Gewichtes falsch klassifizierter Beispiele

Mit der neuen Lernmenge wird mit Hilfe eines Lernverfahrens der nächste Klassifikator bestimmt.

Die Klassifikatoren 1, . . . , k werden zu einem Ensemble zusammengefasst und legen durch gewichteten Mehrheitsentscheid die Klasse eines Beispiels fest

Question 11

PAC Lernbarkeit

Answer 11

PAC = Probably Approximate Correct

Methode zum Berechnen wieviele Lernbeispiele notwendig sind, um mit einer Wahrscheinlichkeit von delta eine Hypothese zu finden mit einem Fehler kleiner als Epsylon.

Kann eine korrekte Hypothese aus H gefunden werden?
–> nein, aber eine epsylon-genaue (approximate correct)

Kann diese sicher gefunden werden?
–> nein, aber mit beliebiger Wahrscheinlichkeit 1-delta

Das Problem (finden der Hypothese) ist lösbar in polynomieller Zeit abh. von 1/delta, 1/epsylon, n
mit Speicheraufwand abh. von C (Konzept)

Das heißt:

• je größer die gewünschte Sicherheit
• je kleiner der zulässige Fehler
• je größer der Hypothesenraum
• um so größer die Anzahl der benötigten Daten

Leider für komplexe Zielfunktionen und Maschinen nicht so leicht …

Question 12

Vapnnik-Chervonenkis (VC) Dimension

Answer 12

Die VC Dimension VC(h_alpha) vom Hypothesenraum H^alpha ist gleich der maximalen Anzahl von Datenpunkten (aus einer Menge S) die von H^alpha beliebig separiert werden können

Eine Hyperebene in R^n kann n+1 Werte separieren

Nutzen:

• Maß für die Datenkomplexität des Lernens (bessere Abschätzung als PAC)
• VC(h) = Maß für die Kapazität von lernenden Maschinen (wobei NICHT gilt, je höher desto besser #overfitting)