Maschinelles Lernen 1 – Zusammenfassung

  • Es gibt eine Vorlesungsaufzeichnung vom WS11/12 über den Streaming-Client der ATIS.
  • Einordnungskriterien ML
  • Die Inhalte dieser Zusammenfassung beziehen sich vorallem auf die Themengebiete von Herrn Professor Zöllner
  • Es besteht keinerlei Anspruch auf Vollständigkeit oder Richtigkeit

Allgemeines

  • Wahrscheinlichkeitsverteilung ist stationär wenn sich nicht über die Zeit ändert.

Einordnungskriterien von Lernverfahren

https://dl.dropboxusercontent.com/s/wqvtpc6hyzrsyx6/einordung.PNG?dl=1&token_hash=AAE7A4maJdsXOZg94v-zbBqnPki4Igror3vIyMDz1K5YjA&expiry=1399839031

Typ der Inferenz

  • Induktiv: Aus Trainingsbeispielen auf ein allgemeines, dahinter liegendes Konzept schließen (Version Space- Algrotithmus)
  • Deduktiv: Vorhandenes generelles Wissen wird eingesetzt um spezielle Regeln für Trainingsbeispiele zu bestimmen (Erklärungsbasierte Generalisierung)

Ebene des Lernens

  • Symbolisch: Ein Teil der Semantik der Daten erkennbar und Lernverfahren macht davon explizit Gebrauch (Entscheidungsbäume)
  • Subsymbolisch: Lernverfahren fasst Daten als Signale auf, z. Bsp. Reelle Zahlen (Neuronale Netze)

Lernvorgang

  • Überwacht: Trainingsbeispiele haben bereits zugehörige Klassen annotiert (k-Nearest Neighbor)
  • Unüberwacht: Ohne Klassenzugehörigkeit (k-Means)

Beispielgebung

  • inkrementell: Trainingsbeispielle können einzeln in das System eingegeben werden und das System verfeinert mit jedem Beispiel seine Hypothese (bereits eingelernte Trainingsdaten müssen dafür nicht nochmal betrachtet werden (ID5R)
  • nicht inkrementell: Hinzunahme zusätzlicher Trainingsbeispiele erneut die ursprünglichen mitverarbeiten (ID3)

Umfang der Beispiel

  • umfangreich: vier/fünfstellige Zahlen (Neuronale Netze)
  • gering: eine Hand voll Beispiele (Case-Based-Reasoning)

Hintergrundwissen

  • empirisch: statistisch ausgewertetes Erfahrungswissen (SVMs)
  • axiomatisch: logischer Unterbau des Lernverfahrens mit echten formalen logischen Ableitungen (Erklärungsbasierte Generalisierung)

Definition Maschinelles Lernen

Ein System lernt aus Erfahrung E in Hinblick auf eine Klasse von Aufgaben T und einem Performanzmaß P, wenn seine Leistungen  bei Aufgaben aus T gemessen mit P durch Erfahrung aus E steigt.

Komponenten eines lernenden Systems

https://dl.dropboxusercontent.com/s/cn23d2ea13dc0jd/komponentenLernSystem.PNG

Inferenz

Deduktiver Schluss

Aus einer Menge von Formeln A folgt B <=> Es gibt eine Folge von Regeln, um B abzuleiten.

Abduktion

H folgt aus Hintergrundwissen B und Beobachtungen D abduktiv d.h. mit Ableiten der Prämisse aus Hintergrundwissen und Beispiel

Induktiver Schluss

Geg. eine Menge D von Grundbeispielen. Die Hypothese H folgt induktiv aus D und dem Hintergrundwissen B. Aus Hypothese einzelne Beispiele ableitbar, aber nicht umgekehrt

Wissensrepräsentation

  • Assoziative Paare bestehend aus Ein und Ausgangsvariablen
  • Parameter in algebraischen Ausdrücken z. Bsp. Gewichtsmatrix
  • Entscheidungsbäume
  • Formale Grammatiken
  • Produktionsregeln
  • Logik-basierte Ausdrücke
  • Graphen und Netzwerke
  • Frames, Schemata, Semantische Netze (größer als einzelne logische Ausdrücke/Produktionsregeln)
  • Prozedurale Kodierung z. Bsp Automatische Programmiersysteme, motorische Fähigkeiten
  • Taxonomischen (Hierarchische Klassifikation, Lernen durch Beobachtung.
  • Markov Ketten als Repräsentation von Hintergrundwissen.
  • Mischformen aus verschiedenen Repräsentationsarten

Lernprozess

https://dl.dropboxusercontent.com/s/232pszd6l8jv666/lernenAlsProzess.PNG

  • (1+2) Erkkennen der Aufgabe, Menge der gewünschten Aktivitäten spezifizieren, Datensammlung (Trainingssequenz)
  • (3) Segmentierung manuell durch Benutzer und Labelling
  • (4 + 5) Auswahl der SVM + Parameter, Eigentliches Training zur Bestimmung der Support Vektoren
  • (6 + 7) Bewertung anhand gelabelter Sequenzen und Erkennungsrate, Verfeinerung durch zusätzliche Sequenzen / Trainingsergänzung

Induktives Lernen

  • Was ist Induktion? Prozess des plausiblen Schließens vom Speziellen zum Allgemeinen.

Induktion vs. Deduktion

Induktion: Wahrheitserweiternd, Macht Lebewesen überlebensfähig, Plausibilität

Deduktion: Wahrheitserhaltend, Logischer Schlüss, Korrektheit

Induktive Lernverfahren

  • Induktive Lernhypothese: Jede Hypothese, die die Zielfunktion über einer genügend großen Menge von Trainingsdaten gut genug approximiert, wird die Zielfunktion auch über unbekannten Daten gut approximieren.
  • Instanzraum: X
  • Trainingsmenge D = x_1, .., x_n in X
  • Zielkonzept: c
  • Hypothesenraum: H
  • Konzept: Untermenge von Objekten/Ereignissen defniert auf größerer Menge (boolsche Fkt ob in Menge)
  • Konsistenz: Keine negativen Beispiele werden positiv klassifiziert.
  • Vollständigkeit: Alle positiven Beispiele werden als positiv klassifiziert.

https://dl.dropboxusercontent.com/s/og9ysjzz1n5v66b/konsistenzUndVollst%C3%A4ndigkeit.PNG

  • Konzeptlernen: Schließen auf die boolsche Fkt. aus Trainigsdaten

General to Specific

(Wird weniger behandelt)

  • Ausgangspunkt ist allgemeinste Hypothese &lt;?,..,?&gt;
  • Negative Beispiele: Spezialisierung
  • Positive Beispiele: werden nicht betrachtet

Specific to General

  • Ausgangspunkt ist speziellste Hypothese &lt;#,..,#&gt;
  • Negative Beispiele: werden nicht betrachtet
  • Positive Beispiele: Immer minimalste Verallgemeinerung anwenden

Bewertung

  • Wichtig
  • Für Menge der Hyopthesenräume, die durch Konjunktionen von Attributeinschränkungen beschrieben sind ist garantiert, dass das Verfahren die spezifischste Hypothese findet, die mit den positiven Trainingsbeispielen vereinbar ist.
  • Endhypothese ist mit negativen Trainingsdaten konsistent falls:
  • Trainingsdaten korrekt
  • Zielhypothese in H enthalten
  • Offen:
  • Trainingsdaten konsistent?
  • Endkonzept = korrektes Zielkonzept?
  • Warum spezifischste Hypothese?

Präzedenzgraphen

Ziele

  • Anwendung z. Bsp. bei Servicerobotern
  • Intuitive Benutzerschnittstelle (Vorführen, Beobachten, Lernen)
  • Umordnung von Teilaufgaben (Optimierung, Lernen von Vorrangsbeziehungen)
  • Lernen sequentieller Unabhängigkeiten
  • Mehrere Durchläufe
  • Identifikation äquivalenter Teiloperationen und deren (Un)abhängigkeiten

Definition

  • Codierung der Hypothesen
  • DAG (directed acyclic graph) P = (N,E)
  • Kanten = Vorrangsbeziehung (E = Edges)
  • Genereller-als-Beziehung

Version Space / Candidate Elimination Algorithmus

Paralleles Anwenden von General to Specific und Specific to General

Definition: Versionsraum (Version Space)

  • Menge von konsistenten Hypothesen, Intervall in der partiellen Ordnung „spezieller als“ auf dem Hypothesenraum
  • VS_{H,D} bezüglich des Hypothesenraums H und der Menge von Trainingsbeispielen D ist die Untermenge der Hypothesen von H, die mit den Trainingsbeispielen in D konsistent ist.

Algorithmus

  • Gespeichert werden folgende Mengen, die alle Beispiele abdecken (-> Hypothesen müssen nicht alle gespeichert werden):
  • Menge der speziellsten Hypothesen S, initial: S = {#}
  • Menge der allgemeinsten Hypothesen G, intitial: G = {?}
  • Beispiel b ist negativ Beispiel:
  • Lösche aus S die Hypothesen die b abdecken
  • Spezialisiere die Hypothesen in G soweit, dass sie b nicht abdecken und dass sie allgemeiner als eine Hypothese in S bleiben
  • Lösche aus G alle Hypothesen die spezifischer als eine andere Hypothese aus G sind.
  • Beispiel b ist positiv Beispiel:
  • Lösche aus G die mit b inkonsistenten Hypothesen
  • Verallgemeinere die Hypothesen in S soweit, dass die b abdecken und dass sie spezifischer als eine Hypothese in G bleiben
  • Lösche aus S alle Hypothesen, die allgemeiner als eine andere Hypothese aus S sind

Einordnung

https://dl.dropboxusercontent.com/s/cj1nd0jk9qrui3y/versionSapceEinordnung.PNG

Bewertung

  • Version Space konvergiert zur korrekten Hypothese (S = G)
  • Wenn Beispiele konsistent, korrekte Hypothese in H enthalten
  • Probleme:
  • Fehlerhafte Trainingsdaten (Rauschen)
  • Zielkonzept nicht von Hypothesenrepräsentation abgedeckt (-> Erweiterung via disjunkte Begriffe??)
  • Attributgeneralisierungsregeln maßgebend für Lernerfolg
  • Positiv:
  • Kein Speichern alter Beispiel notwendig
  • Stellt fest, wann genügend Beispiele gegeben wurden (S = G)

Induktiver Bias

  • Induktion bescheibt die Verallgemeinerung auf Basis von Beispielen, aber der Hypothesenraum spielt auch eine wesentliche Rolle (Beispiel mit einseitig schwarzem Schaf (Ziege)) -> Zielkonzept nicht im Hypothesenraum
  • Ein induktives Lernsystem, das keine a priori-Annahmen über die Identität des Zielkonzepts macht, hat keine rationale Basis, um unbekannte Instanzen zu klassifizieren. -> Funktioniert nicht ohne Vorannahme!

Bias (Vorzugskiterium)

Vorschrift nach der Hypothesen gebildet werden.

Mögliche Vorzugskriterien
  • Verständlichkeit (für Mensch)
  • Klassifikationsgenauigkeit
  • Messaufwand für die verwendeten Deskriptoren
  • Berechnungs- und Speicheraufwand für Hypothese

  • Hypothesenraumbias (h gehöre zu einem beschränkten Raum von Hypothesen)

  • Komplexität des Hypothesenraums
  • Beispiele
  • logische Konjunktion
  • lineare Schwellwertfunktion
  • Gerade, Polynome
  • x-Nearest Neighbour

  • Präferenzbias

  • Ordnung auf dem Raum der Hypothesen
  • Wähle Hypothese mit höchster Präferenz
  • Wähle h welcher möglichst viele Beispiele richtig Klassifiziert

Vergleich induktiver Lernsysteme anhand ihres inductive bias

  • Auswendiglerner: keine Vorannahme
  • Version Space: Zielkonzept kann im Hypothesenraum repräsentiert werden
  • Specific-to-General Lerner: Wie Version Space + alle Instanzen sind initial negative Instanzen bis Gegenteil bekannt

Je strenger Vorannahmen desto mehr können unbekannten Daten klassifiziert werden
Je strenger die Vorannahmen sind desto konsistenter ist die Klassifikationsentscheidung (-> weniger false-positives)

Lerntheorie

(Zöllner)

Löse nie ein Problem komplizierter als nötig, denn die einfachste, richtige Erklärung ist die Beste (Rasiermesser-Prinzip von Occam)

Lernen = Schätzen einer Abbildung (Hypothese) mit Hilfe von (bekannten) Beispielen (Lernbeispiele) generiert von einem (nicht bekannten) System mit der Wahrscheinlichkeit P.

Definition Lernmaschine

  • h_a Hypothese mit Parameter a
  • Lernende Maschine ist bestimmt aus
  • Hypothesenraum {h_a : a in A} (implementiert diesen)
  • Lernverfahren: Methode um a_opt mit Hilfe von Lernbeispieken zu finden (Fehlerfkt, Optimierung)
  • Resultierendes (Entscheidungs-) Modell M_opt gegeben durch
  • Auswertung der optimalen Hypothese h_a_opt die durch die lernen(den) Maschine(n) bestimmt wird

Welche Maschine wählen (Welches Lernverfahren)?

Welches Modell?

Lerntypen

  • Konzeptlernen: Attributmenge A_1, .., A_n -> true/false
  • Klassifikation (numerisch): R^N -> Klasse_1, .., Klasse_n
  • Regression (numerisch): R^N -> R

Probleme beim Lernen

  • Statistisches Problem: Bezügl. Trainingsdaten zu großer Hypothesenraum (mehrere Hypothesen gleichermaßen gut)
  • Komplexitätsproblem: Durch Komplexität kann Lernverfahren keine optimale Lösung innerhalb des Hypothesenraums garantieren -> zu rechenintensiv. (Bei speziellen Verfahren oder Heuristiken Gefahr einer suboptimalen Lösung)
  • Repräsentationsproblem: Hypothesenraum enthält keine ausreichend guten Approximationen der Zielfunktion/Konzept (gewünschter Approximationsgrad nicht lieferbar)

Fehler

  • Man versucht den Fehler der Hypothese mit E(h) zu schätzen, da nicht berechenbar.
  • Fehler lässt sich aus Vergleich der Hypothese mit tatsächlichen Wert bestimmen
  • Allgemein nicht berechnenbar -> Wahrscheinlichkeitsverteilung nicht bekannt, echter Zustand nicht bekannt aber schätzbar.

Fehlerdefinition

https://dl.dropboxusercontent.com/s/bdgxchp7g3j8tw9/fehlerfunktion.PNG?dl=1&token_hash=AAEXhiFfwztD3EDOGMFd49Yut3RSar2HgWCMQvbIA5DaRw&expiry=1399535772

  • P(x,y): Wahrscheinlichkeitsverteilung des zu lernenden Konzepts

Fehlermaßfunktion

https://dl.dropboxusercontent.com/s/jlxfxecb3ji59m7/fehlermassfunktion.PNG?dl=1&token_hash=AAF6-fbVJSoYi-l28LIh6LjWKxBoloFq-ODmqyM3mS2H0w&expiry=1399535807

  • Distanz l
  • Anzahl Missklassifikation (einfach, aber nicht sehr gut)
  • Abs. Fehler
  • Quad. Fehler
  • Probabilistisch

Realer & Empirischer Fehler

  • Realer Fehler (über alle real vorkommenden Daten) sind nicht berechenbar -> gute Schätzung nötig
  • Formel distanzbasierte Fehlemaßfunktion (s.o.)
  • Empirische Fehler auf Datenmenge D E_D(h) bestimmt (möglichst nahe an realen Fehler)
  • Lerndaten -> Lernfehler
  • Verifikationsdaten -> Verifikationsfehler
  • Testdaten -> Generalisierungsfehler (Da ja die Generalisierbarkeit mit den Testdaten getestet wird)

Fehlerminimierung

https://dl.dropboxusercontent.com/s/y1127vhr0s886s3/fehlerberechnung.PNG?dl=1&token_hash=AAEw4JgguO5_MSeyW0RcQiD-HJ5s57PEKU5YkDqVSPI4AQ&expiry=1399980730

  • Iterative Fehlerminimierung des Fehlers durch Gradientenabstieg auf der Fehlerfunktion
  • Start an beliebigen Punkt
  • Gradient wird bestimmt
  • Iterative Anpassung von α (Achtung α != a)
  • α wird mit negativer Änderungrate verschoben
  • Nicht ganz korrekt, nur empirischer Fehler dargestellt aber nicht der reale Fehler (empirischer Fehler stehlt nur einen Ausschnitt dar). Stimmt aber meistens hinreichend gut.
  • Nach Vapnik wird dadurch nur der erste Teil der SRM minimiert!
  • Realität oft problematisch: Mehre lokale Minima möglich

Overfitting

  • Tendenz der Maschine sich beim Lernen auf die Lernbeispiele zu spezialisieren (Auswendig lernen)
  • Lernfehler fällt, Testfehler steigt, Generalisierungsfähigkeit fällt

https://dl.dropboxusercontent.com/s/g8l56t9ubpau2sm/overfitting.PNG

  • Lernprozess muss angepasst werden wenn keine repräsentativen Daten vorliegen
  • Bildet Hypothesenraum überhaupt Zielkonzept ab?

Modellgüte – Validierung

  • Wenig komplexes Modell -> Repräsentationsproblem, da wenig Parameter
  • Komplexes Modell, da viele Parameter

Validierung

Trick der statistischen Auswertung auf verschiedenen Modellen auch mit relativ wenig Lerndaten evaluieren

cross-validation
  • Teile Daten wiederholt in Lern/Validierungsdaten (werden zufällig gezogen aus Ursprungsdatenmenge)
  • Bestimme darauf versch. Hypothesen
  • Berechne Generalisierung
  • Wiederholung
  • -> Damit recht gute Aussage darüber wie gut ein Modell ist (Güte/Varianz)
n-fold cross-validation:
  • Zerlege die Mege der Lerndaten in n Mengen
  • Trainiere jeweils auf n-1 Mengen, teste auf einer Menge
  • Wiederhole
leave one out (Spezialfall):
  • Jeweils ein Beispiel für das Lernen weggelassen
  • Addiere Fehler für weggelassene Beispiele
  • Wiederhole

Bootstrap (Ensemble Verfahren)

  • Dient nur zur Evaluation von Modellen baut kein neues (besseres) Modell
  • Mit einfachen Verfahren/Modellen komplexe Entscheidungen treffen durch Kombination
  • Anekdotischer Hintergrund: Paradoxon von Münchausen (am Schopf aus dem Sumpf ziehen)
  • Lernen
  • Ziehe zufällig mit Zurücklegen aus Daten D jeweils k = |D| Beispiele m Mal
  • Bestimme jeweils Modell-Parameter
  • Bestimme Mittelwert, Varianz der Parameter des Modells
  • -> Analyse der Güte/Stabilität
  • -> mit weiteren Ansätzen höhere Güte des Modells (z.Bsp. Bagging)
  • -> Ensemble von Modellen

Bagging (Bootstrap aggregation)

  • Bootstrapping
  • Verwende mehrere Modelle
  • Kombiniere die Modelle, z.B. gewichtete Summe
  • -> Höhere Güte, Stabiltätserhöhung
  • -> Aussage über Stabilität (Große Modellunterschiede = unstabil)

Boosting

  • D unterteilen in D_1, D_2, D_3
  • Wähle D_1 und bestimme M_1
  • Wähle D_2 aus D sodass 50% durch M_1 korrekt geschätzt werden und erstelle damit M_2
  • Wähle D_3 aus D sodass sie gegensätzlich zu M_1, M_2 sind und bestimme M_3
  • Kombiniere Modelle zu M = M_1, wenn M_1 = M_2 sonst M_3
  • Eine Art von Voting
  • Vorgänger von AdaBoost

AdaBoost (Adaptive Boosting)

Vergleich zu Boosting

  • Generelles Verfahren um Daten aufzuteilen und einfache Modelle zu Generieren
  • Lerndaten werden einzeln gewichtet gemäß des letzten Klassifikators

Aufbau

  • Lernmenge D mit n Beispielen
  • Gewichtung (Anfangs gleich gewichtet) der Lerndaten gemäß Klassifikationsergebnis des zuletzt generierten Klassifikators
  • Verringerung des Gewichts von korrekt klassifizierten Beispielen
  • Erhöhung des Gewichts von falsch klassifizierten Beispielen
  • Mit neuer Lernmenge mit Lernverfahren nächsten Klassifikator bestimmen
  • Klassifikatoren 1,..,k am Ende Mehrheitsentscheidung
  • Mehrere schlechte Klassifizierer werden kombiniert
  • Missklassifikationen vom vorherigen Klassifizieren werden durch nachfolgende verbessert/angesprochen
  • Solange die einzelnen Klassifizierer besser sind als Raten wird das finale Modell durch AdaBoost verbessert
  • Nicht so anfällig gegenüber Rauschen und Outliers

Algorithmus

https://dl.dropboxusercontent.com/s/lje3yn9dfjy1y5y/adaBosst.PNG?dl=1&token_hash=AAHlcTJhwZNdFMBed1WifN8jMSxyq5BiTQk-WiB7lHavDA&expiry=1399982435

  • α klein wenn Fehler groß
  • α für Gewichtung der Lernbeispiele
  • je größer der Fehler desto größer die Gewichtung für den nächsten Klassifikator

Viola Jones

  • Echtzeit Gesichtererkennung
  • Ist da ein Gesicht? Ja/Nein
  • Merkmalsbasiert (Haar-Filter): Summe der Pixel im weißen – Summe der Pixel im schwarzen Bereich
  • Sehr ineffizient wenn man alle Haar-Filter auf jeden zu untersuchenden Bereich anwendet.
Kaskadiertes AdaBoost-Verfahren
  • Kaskade von einfachen Klassifikatoren
  • Jeder Kaskade versucht möglicht viele Fehler rausfiltern
  • Rausfiltern von möglich positiven Teilmengen
  • Pro Kaskade immer mehr Filter
  • Jeder Klassifikator besteht wiederum aus Menge von Haar-Filter
  • AdaBoost für jeden Klassifikator
  • Ensemble von linearen Entscheidungen
  • Am Schluss nur noch (hoffentlich) richtig erkannte Daten
  • Erkennungsrate = Alle Positiv aber auch falsch-positiv-Daten enthalten

PAC Probably Approximate Correct

  • Was kann man über das Lernen aussagen?
  • Gegeben
  • Menge X von Instanzen der Länge n
  • Konzept C
  • Hypothesenraum H
  • Lerndatenmenge D

Kann in Hypothesenraum H eine Hypothese h gefunden werden die Instanzen aus X auf C richtig abbildet

  • Völlig aussichtslos ein korrektes und vollständiges Lernverfahren zu fördern. -> Nein, aber eine Probably Approximate Correct Lernen.
  • -> Approximation statt Identifikation
  • PAC ist eine Abschwächung, Begriffsklasse C ist PAC-lernbar wenn:
  • Hypothese hat Fehler e mit 0 &lt; ε &lt; 1/2 (approximate correct)
  • Wahrscheinlichkeit für ihre Auffindbarkeit 1-δ mit 0 &lt; δ &lt; 1/2 (probably)
  • Lösbarkeit in polynomieller Zeit abh. von 1/ε, 1/δ, n
  • Mit Speicheraufwand abh. von C

Stichprobenkomplexität

https://dl.dropboxusercontent.com/s/1jc09qb1g6lmh28/stichprobemkomplexit%C3%A4t.PNG?dl=1&token_hash=AAHTeE80MATCd6dA0yW9bunvwI4Y2iORjvZJjdTdrtHfSg&expiry=1399542779

Anzahl der benötigten Lerndaten hängt ab von

  • je größer die gewünschte Sicherheit
  • je kleiner der zulässige Fehler
  • je größer der Hypothesenraum

Desto mehr Daten werden benötigt.

  • Leider kann man das bei den meisten Lernmaschinen nicht so einfach bestimmen

Vapnik-Chervonenkis (VC) Dimension (für Klassifikation)

  • Maß für die Kapazität von lernenden Maschinen
  • C ist PAC-lernbar gdw. VC Dimension endlich
  • Maximale Anzahl von Datenpunkten die von H_α (Hypothese) beliebig separiert werden können (Hyperebenenbeispiel)
  • R^n = n+1

https://dl.dropboxusercontent.com/s/2m9x146vz5hpmr0/vc-beispiel.PNG?dl=1&token_hash=AAG6yyrTQMUxUK9yDqMhyULpvSmDlhgamWAI42YHn0N-Ew&expiry=1399543697

Abschätzung Stichprobenkomplexität

  • Bessere Abschätzung der Stichprobenkomplexität

https://dl.dropboxusercontent.com/s/9jpgwwzcpt70luo/vc-stichprobenkomplexit%C3%A4t.PNG?dl=1&token_hash=AAGJNGopM7Dqf0wu5Q3YZ0SaPxynLoA57SYTnArxOkVlXQ&expiry=1399543821

  • Statt Kardinalität die VC-Dimension
  • Problem VC Dimension ist nicht immer bestimmbar für jede Lernmaschine
  • Bei einigen Neuronalen Netzen zum Beispiel

VC-Dimension und Kapazität

  • Je höher die VC-Dimension desto höher die Kapazität einer Lernmaschine
  • Aber nicht je höher desto besser!

Abschätzung des Testfehlers

(Fragestellung welche VC Dimension hat eine optimale Lernmaschine?)

  • Mit W! 1-η (eta) gilt:

https://dl.dropboxusercontent.com/s/sfs4buaoex4j1g6/vc-fehlerabsch%C3%A4tzung.PNG?dl=1&token_hash=AAEYz28Db-GRDzztNhxmaVYHIIL7ouh9gycJXILrJ0UCFA&expiry=1399543972

  • Lernerfolg hängt von
  • Kapazität der lernenden Maschine: so gering wie nötig (VC(h_α))
  • Optimierungsmethode: so gut wie möglich (E_emp(h_α) so klein wie möglich)
  • Lernbeispiele: repräsentativ, so viele wie möglich (N)

-> Einfachste Erklärung ist die beste (Rasiermesser-Prinzip von Occam)

Schwierig berechenbar

Structural Risk Minimization

  • Ziel: Minimiere Summe nicht einzelne Summanden!

https://dl.dropboxusercontent.com/s/bsbk5fz1exky56m/optimumSRM.PNG?dl=1&token_hash=AAEtrJcVt18dKciv_nPrjXtfIOQnYk4mbjx14GQN-jy7iw&expiry=1399985595

  • Empirische Fehler minimieren, Lernmaschine fest, Trainingsdaten konstant
  • Realer Fehler wird bis zu einem gewissen Punkt minimiert (Overfittig ab einem gewissen Grad)
  • VC(h_α) variabel, damit Kapazität der Lernmaschine variabel, Trainingsdaten konstant
  • confidence term steigt mit steigender VC-Dimension an
  • Irgendwann ist die Lernmaschine zu komplex um Konzept richtig zu approximieren
  • Korrektes Lernen genau der Punkt an dem die Summe der beiden minimal ist (Optimum)

https://dl.dropboxusercontent.com/s/sdircr0f4vjzvv4/srm.PNG?dl=1&token_hash=AAFFVRWumzecKH_4G9bdigeEUmooeRLv090wZiejiJC6dQ&expiry=1399545837

Idee hinter Lösung
  • Strukturierung der Lernmaschine (Hypothesenraum) bestimmen
  • Steigende Kapazität der Lernmaschine (VC-Dim steigt)
  • Aber auch nicht einfach bestimmbar (analytisch)
  • Nicht für alle Lernmaschinen realisierbar
Frage wie kann man für eine Lernmaschine eine gute SRM hinbekommen?
  • Neuronale Netze: SRM via Cascade Correlation (MLNN) und DDA (RBF-Netze)
  • SVMs machen SRM direkt intern ohne sie explizit zu bestimmen

https://dl.dropboxusercontent.com/s/lwahx44ecai4ti7/strukturierung.PNG?dl=1&token_hash=AAGKhMOeE-WGy29ayo0FskTiMGunjsnbLOga9j3zBdGD0A&expiry=1399986525

  • Allgemein anerkanntes korrektes Lernen

Neuronale Netze

(Zöllner)

Vergleich Gehirn vs serieller Rechner

Einsatzfelder

Perzeptron

https://dl.dropboxusercontent.com/s/84a3nk1cf0mri7b/perceptron.PNG?dl=1&token_hash=AAHKIExXUDO84cg_eY1tTdr9eQW5GiQ_rNQ5GLCvlKK7aA&expiry=1399553680

Grundidee

  • Anlehnung an das Funktionsprinzip der natürlichen Wahrnehmung
  • Reaktion im Tierbereich
  • Kann nur lineare Trennfkt repräsentieren
  • Limitiert: XOR!

Aufbau

  • Eingabevektor x
  • Gewichtsvektor w
  • Target (Soll-Ausgabe) t
  • Output (Ist-Ausgabe) o

Bias-Trick: Schwellwert t in Input und mit x_0 = 1 und w_0 = - t

Lernverfahren

  • Lernen = Anpassen der Gewichte
  • Gesucht wird die beste Trennebene

Geometrische Interpretation

  • Daten werden in Positive und Negative unterteilt
  • Dimension wird um x_0 erweitert
  • Trennhyperebene (R²: Gerade)
  • Gewichte definieren diese Ebene (Normale)
  • Gewichtete Summe = Entscheidung -> Skalarprodukt

Lernalgorithmus

  • Algorithmus:
  • Start
  • Lerndatenmenge (Positive + Negative)
  • w(0) zufällig
  • t=0
  • Testen
  • Punkt x in P&N zufällig
  • Falls x in P und w(t)*x &gt; 0 -> Testen
  • Falls x in P und w(t)*x &lt;= 0 -> Addieren
  • Falls x in N und w(t)*x &lt; 0 -> Testen
  • Falls x in N und w(t)*x &gt;= 0 -> Subtrahieren
  • Addieren
  • Setze w(t+1) = w(t) + x
  • t++, -> Testen
  • Subtrahieren
  • Setze w(t+1) = w(t) - x
  • t++, -> Testen

  • Probleme

  • |w| >> |x| -> sehr langsame Anpassung an optimale Trennebene
  • Lösung: Normierung
  • Fast anti-parallele Vektoren -> springt immer hin und her
  • Lösung: Deltaregel (allgemein Gradientenabstiegsverfahren)

https://dl.dropboxusercontent.com/s/z46hf1ibzoeka4c/probleme-perzeptron.PNG?dl=1&token_hash=AAGOLvQfpj1HmZs6rLRgG5AqAlmeIaE5MG5fqUa-vubRzA&expiry=1399554354

Gradientenabstiegsverfahren – Fehlerfunktion

  • Muss ableitbar sein!
  • Fehlerfunktion Vergleich Soll/Ist-Wert

Kernelmethoden / Kerneltrick

  • Transformation in höherdimensionalen Raum der Eingangsdaten
  • Problem wird lineal trennbar -> Perzeptron verwendbar!

https://dl.dropboxusercontent.com/s/s359iyl4jpiyhyj/kernel.PNG?dl=1&token_hash=AAEb32rlx0IJ33BNDWHIDP6Op6sEosoZNW6UI3Y2h0xmQQ&expiry=1399554890

  • φ ist hier die Transformation von R_1 in R_2
Kernel Perceptron
  • Lineare Trennung im transformierten Raum führt zu komplexer Trennung im Ursprungsraum

https://dl.dropboxusercontent.com/s/n8j9a3z7as00oah/kernel-perceptron.PNG?dl=1&token_hash=AAEdr_Oonv-JYgcPTodk2FVJSxNlTyJ1nFBXUmDE-8rs_w&expiry=1399555013

Multi Layer Feedforward Neural Network (MLNN)

https://dl.dropboxusercontent.com/s/aelafbwgadcqkdn/mlnn.PNG?dl=1&token_hash=AAECd3gZr1gNh5tmCWVHEWdQ3TAgidJigUV1Zc8H2MZcOw&expiry=1399555123

Aufbau MLNN

  • Mehrschichtiges Neueronales Netz aus Neuronen bestehend
  • Gewichtete Verbindungen zwischen Schichten
  • Backpropagation Lernalgorithmus
  • Neu: Aktivierungsfunktion
  • Nichtlineare Aktivierungsfunktion (ableitbar, wichtig für BP-Algo!)
  • Sigmoid
  • tanh

Backpropagation Algorithmus

Ziel: Gesamtfehler auf Neuronen des Netzes aufteilen (Gewichtsbelegung anpassen entsprechend Fehleranteil)

Radial Basis Function (RBF) Netze

  • Vorwärtsgerichtetes, 3-Layer Netz (1 hidden Layer)
  • Neuronen der hidden layer lokale rezeptive Felder (mehrdimensional)
  • Aktivierung gemäß radialer Basisfunktion (Gauss Funktion mit Zentrum µ und Reichweite omega
  • Aktivierung (entsprechend oft Gauß-Glocken gewichtet)
  • Auch unsysmetrische Gaußfunktionen -> Rezeptive Felder möglich
  • BP-Algo immer noch möglich

TODO Formeln

Aufbau

http://www.neurocomputing.de/RBF/RBF.html

Beispiel

https://dl.dropboxusercontent.com/s/4d6t07xnfpkmpmo/rbfXOR.PNG

Probleme

  • Hoher Rechenaufwand durch nicht-lineare Funktionen
  • lokale Minima (mehrere)
  • Reichweite kann sher groß werden -> keine lokalen Fehler

Generelle Probleme

  • Fehlerflächen
  • a) Vorkommen lokaler Minima (werden als Ergebnis angenommen durch Konvergierungsalgorithmus)
  • b) Steigung der Fehlerfläche (Steigung mimimal -> konvergiert sehr langsam)
  • c) Ausprägung der lokalen Minima (Anspassung führt zum Sprung zurück und iteriert immer weiter)
  • d) Lernrate (man kann Mimimum überspringen wenn Lernrate zu hoch ist)

https://dl.dropboxusercontent.com/s/fb4rkvzd78vxwfy/fehlerfl%C3%A4chen.PNG?dl=1&token_hash=AAGAYftA9rMHIS3YJg65FJPHwBCU8E1Ym3gPb31LVIIfrw

Optimierung des Gradientenabstiegs

  • Momentum Term:
  • Nicht nur aktuellen Gradienten wird betrachtet sondern auch letzte Gewichtsanpassung (wird gewichtet)
  • „Schwung wird mitgenommen“
  • Hilft bei Plateau-Fehlerfläche und Zirkulieren
  • Normierung der Schrittweite:
  • Nicht Betrag des Gradienten sondern Vorzeichen
  • Positiv: Nicht abh. von größe des Gradienten
  • Negativ: Nicht adaptiv an aktuell benötigte Schrittweite (Plateau: groß, d) klein)
  • Lernratenanpassung (RPROP)

RPROP (Resilient Propagation)

  • Individuelle Lernrate mittels Gradientenvergleich
  • Optimierung von BP-Algorithmus
  • Adaptiver Ansatz
  • Anpassung der Lernrate abhängig vom Gradientenvergleich
  • Wenn Gradient des letzten Schritts in gleich Richtung Zeit wird Schrittrate größer
  • Sonst kleiner
  • -> Beschleunigung auf flachem Plateau, langsam anpassen im Mimimum

Probleme / Optimierung

  • Unterschiedliche Kapazitäten von Neuronalen Netzen
  • Perzeptron: Lineare Trennebene
  • MLNN: können mehr
  • Stellschraube: Organisation des Neuronalen Netzes
  • 3 Layer Netz:
  • Boolsche Funktion
  • kontinuierliche beschränkte Funktion
  • 4 Layer Netz:
  • beliebige Funktion mit beliebiger Genauigkeit

-> Schon geringe Tiefe ist ausreichend. Topologie spielt eine ausschlaggebende Rolle

  • Klassifikation eher SVM, Random Forest Trees
  • Regressionsaufgaben eher Gaußschen Netze

Verbesserung der Generalisierung von MLNN

  • Kapazität = Generalisierbarkeit
  • VC Dim. nicht trivial analytisch bestimmbar
  • Konstruktive Ansätze (DDA, Cascade Correlation), kleines Netz wird solange erweitert bis es die Daten lernen kann
  • Destruktive Ansätze (z. Bsp. Optimal Brain Damage: Lernen + löschen von Verbindungen), großes Netz wird verkleinert und so daran gehindert die Daten auswendig zu lernen.

Cascade Correlation

  • Normales 2 Layer NN
  • Algorithmus (Iterativ wiederholen bis max. Anzahl Neuronen oder Fehlerschranke unterschritten)
  • Trainiere Netz
  • Wenn Gesamtfehler E(w) > Fehlerschranke
  • Füge Neuron ein („Kandidat-Neuron“)
  • hidden, vor Ausgabeschicht
  • vollständig verbunden (mit Eingabe- und Ausgabeschicht)
  • Gewicht zu anderen vorher eingefügten Neuronen mit z. Bsp -1 als Gewicht
  • Trainiere neues Neuron (einmalig)
  • Trainiere Netz

<p></p>
https://dl.dropboxusercontent.com/s/k8w211hnzpxrna5/fahlmann.PNG?dl=1&token_hash=AAFZMfgozk_7sMUP8BRG3Y869VMLE6F734ztSDIm_255aw

  1. Fahlman: Komplex

* Hohe Ausgabe des Neurons wenn der Fehler des Gesamtnetz hoch ist
* (Ausgabe – Ausgabemittelwert) * (Fehler – Fehlermittelwert) maximieren (Lösen via Gradientenabstieg)
* Gewicht entsprechend anpassen
2. Duda & Hart: Vereinfachte Version
* Prinzipiell wie Fahlmann nur einfacher
* Verbindung zwischen neuen Neuronen mit -1 als Gewicht setzen
* Führt zu maximal unterschiedliche Ausprägung
* Immer dann wenn man in Neuron A kleine Aktivierung hatte hat man in Neuron B eine hohe Aktivierung
-> Bisherige Problemfälle des Netztes werden adressiert.
<p></p>
* Schnell, immer nur ein Neuron muss zusätzlich gelernt werden
* Inkrementelles, konstruktives Lernen
* Kapazität kann iterativ erweitert werden.

Dynamic Decay Adjustment (DDA)

Beispiel anschauen!

  • Konstruktiver Ansatz
  • Basiert auf RBF Topologie
  • Klasse A/B Neuronen
  • Zwei Schwellwerte
  • Beispiel: Trainieren von Laufverhalten von Laufmaschinen

Einsatz von MLNN

  • Was kann man in einem NN abbilden?
  • Subsymbolische Representation von Ein und Ausgabe
  • Auswahl von
  • Trainingsdaten
  • Lernverfahren
  • Topologien
  • Parametereinstellung

Vergleich Sigmoid-MLNN und RBF-NN

  • Sigmoid MLNN: Verteilt (global)
  • Änderungen wirken sich global aus
  • Generalisierung gut
  • RBF NN
  • Änderungen nur lokal
  • Generalisierung schlechter
  • Iterativeres Lernverfahren
  • Braucht aber extrem repräsentative Daten

Initialisierung der Gewichte

  • Wichtige Rolle
  • Gewichte müssen verschieden sein sonst funktionsgleiche Neuronen
  • -> Möglichst kleine, gleichverteilte Gewichte

Anpassen der Gewichte

  • Patternlearning
  • BP direkt nach jedem Lernbeispiel
  • schneller, kein echter Gradientenabstieg
  • Aber gute Approximation
  • Nachteil: Außerreiser bringen Netz eher in suboptimale Form
  • Epochlearning
  • Mittelung der Gewichtsänderung über alle Beispiele
  • Anpassung nachdem alle Beispiele propagiert wurden
  • „echter“ Gradientenabstieg
  • nicht anfällig für Ausreißer / falsche Lerndaten

Entscheidungstheorie / Entscheidungsbäume

Allgemein

  • Jeder Knoten repräsentiert einen Attributtest
  • Jeder Zeig entspricht einem bestimmten Attributwert
  • Jedes Blatt entspricht einer Klassifikation
  • Disjunktion von Konjunktionen von Bedingungen an die Attributwerte einer Instanz
  • Diskrete Werte kann man besser verarbeiten mit Entscheidungsbäumen (Realwertige Werte _Regressionsbäme)

Eignung

  • Instanzen lassen sich als Attribut-Wert Paare beschreiben
  • Zielfunktion besitzt diskrete Ausgabewerte
  • Disjunkte Hypothesen
  • Verrauschte bzw. Fehler-behaftete Daten

ID3

  • Nicht-inkremenntelles Verfahren
  • Suche im Hypothesenraum Simple-to-Complex (hill climbing) Algorithmus
  • Hypothesenraum ist vollständig -> Zielfunktion ist enthalten
  • Nur eine Hypothese wird vorgehalten
  • keine gezielte Abfrage von neuen Instanten zur Auswahl unter verbliebenen Hypothesen möglich
  • Kein Backtracking:
  • Lokale Minima können gefunden werden. (Wie bei allen climbing Algorithmen)
  • Nicht-inkrementelle, statistisch motivierte Suche:
  • Weniger anfällig gegenüber Fehlern in den Trainingsdaten

Top down Aufbau des Entscheidungsbaums

  1. A <- Das beste Entscheidungsattribut für den nächsten Knoten (beste = höchste Entropie)

* Weise A als Entscheidungsattribut für den nächsten Knoten
* Füge für jeden möglichen Wert von A einen Nachfolgeknoten ein.
* Verteile die Trainingsdaten gemäß ihrer Attributwerte auf die Nachfolgeknoten.
* Terminiere wenn die Trainingsdaten perfekt klassifiziert
werden, sonst iteriere über die Nachfolgeknoten.

Entropie

  • Maß der Homogenität der Trainingsdaten
  • Beispiel Münzwurf mit gezinkter Münze = 0, bei normaler Münze am höchsten
  • Anzahl der Bits die ich brauche um ein Problem/Lösung zu kodieren (Shannon)

https://dl.dropboxusercontent.com/s/0qm0t6hha2yuodr/entropie.PNG?dl=1&token_hash=AAEhZa6H4lsP1ZYDc9k-UPPARa-WymqGomlkRSPrgzq44w

Informationsgewinn

  • Gewinn(S, A)= Erwartete Reduzierung der Entropie durch die Einsortierung über Attribut A

https://dl.dropboxusercontent.com/s/9c3n6hggtsmmjb6/gewinnEntropie.PNG?dl=1&token_hash=AAG9CZ6V-izslVVdZtNP2T14cyWBakd31OYZFIRXvc9a8A

Bias

  • Induktiver Bias: Präferenz für kleine EB und solche, die Attribute mit hohem Informationsgewinn nahe der Wurzel besitzen.
  • Präferenzbias
  • Restriktionsbias

Occam’s Razor

Overfitting

Vermeidung von Overfitting

  • Frühzeitiges Stoppen des Baumwachstums
  • Kriterium für optimale Baumgröße
  • Sepearte Testdatenmenge -> Klassifikation anschauen -> optimale Größe bestimmen
  • Statistischer Test auf Trainingsdaten (x²-Test)
  • Maß für die Kodierungskomplexität der Trainingsbeispiele und des Entscheidungsbaums (Prinzip der minimalen Beschreibungslänge) -> Shannon
  • Nachträglichen „Pruning“ des Baumes
  • Reduced Error Pruning
  • Teile die Daten in Trainings- und Testdaten
  • Führe Pruning durch solange es sich nicht negativ auswirkt (Evaluation der Auswirkungen, Entfernen des Knotens der die Klassifikationsrate am meisten erhöht.)
  • Greedy Ansatz -> Liefert den kleinsten Baum der die Daten korrekt klassifiziert.
  • Problem: Bei wenigen Daten erhöht das Aufteilen der Daten die Fehleranfälligkeit noch weiter.

Kontinuierliche Attributwerte

  • Definition von Schwellwert um Klasseneinteilung zu erhalten
  • Problem: Wie definiere ich einen optimalen Schwellwert?
  • Sortierung der Beispiele gemäß ihrer Werte
  • Optimaler Schwellwert liegt in der Mitte zwischen zwei benachbarten Beispielen mit unterschiedlichen Klassenzugehörigkeiten

Attribut mit vielen Werten

  • Extrem viele unterschiedliche Klassen in den Daten
  • Auswahl von Attributen die weniger „splitten“
  • Attribute mit größerem Gewinn(S,A) werden bevorzugt

https://dl.dropboxusercontent.com/s/hynyiq2pt6qkwuz/Splitt.PNG?dl=1&token_hash=AAHYy0bAjo3IBZ8jclXDtyPCJiAv7zNbKsfAiCSwHcg3-Q

Unbekannte Attributwerte

  • Beispiel: Sensor geht kaputt -> fehlende Attributwerte
  • Lösung: Sortiere Beispiele wie gewohnt in den EB ein und
  • weise den fehlerhaften den häufigsten Attributwert der Beispiele diesem Knoten zu (gesamte Messdatenmenge)
  • weise den fehlerhaften den häufigsten Attributwert der Beispiele der zugehörigen Klasse zu (auf Klasse bezogen mit positiven bzw. negativen Klasse als Endergebnis)
  • weise jedem Wert die Wahrscheinlichkeit zu und verteile das Beispiel gemäß anteilig auf die Nachfolger
  • Klassifikation analog

Attribute mit Kosten

  • Beispiel mit medizinischer Diagnose
  • Bestrafungsfunktion Kosten werden mit einbezogen in den Gewinn

https://dl.dropboxusercontent.com/s/98rmt4pomgqzfby/gewinn.PNG?dl=1&token_hash=AAHoxdf_hHD8_MzGCW4mrH10QB9L1OMO7ySE5BAd4WCQaw

Windowing

  • Interessant bei großen Datenmengen
  • Algorithmus:
  • Wähle zufällige Untermenge („Window“)
  • Bestimme EB für Window
  • Klassifiziere restl. Daten mit Window-EB
  • Falls nicht alle Daten korrekt klassifiziert füge einen Teil der falsch klassifizierten zum Window hinzu und erstelle EB erneut

C4.5

  • Nicht-inkremenntelles Verfahren
  • Verbesserung des ID3 durch generalisierte Regeln (Pruning)
  • Dann mit verrauschten und fehlerhaften Daten umgehen
  • Wandelt den Baum in if-then-Regeln um, danach Pruning
  • Kommerzielles System

Rule Post-Pruning

  1. Baum aufbauen (Overfitting erlaubt)

* Umwandeln in if-then Regeln
* „Prune“ (Generalisiere) die Regeln so lange sich ihre Vorhersagegenauigkeit nicht verschlechtert (durch Entfernen von Vorbedingungen).
* Sortiere alle Regeln nach ihrer Klassifikationsgüte und verwende sie in dieser Reihenfolge.

Zusammenfassung

  • Regelgüte: Standardabweichung bestimmen, untere Schranke Konvidenzintervall = Regelgüte
  • Statistisch nicht einwandfrei aber Praxistauglich
  • Proprietär wenig bekannt
  • Vorteile
  • Unterscheidung zw. verschiedenen Kontexten in denen ein Entscheidungsknoten benutzt wird
  • Keine Unterscheidung zw. Attributen näher an  Wurzel und solchen näher an Blättern
  • Lesbarkeit

ID5R

  • Inkrementelles Verfahren
  • Ergebnis ist äquivalent zu ID3 Baum
  • Viele Zähler im Baum enthalten

Repästentation der EB

  • Messdatenmenge ist im Entscheidungsbaum enthalten
  • Antwortknoten:
  • Werden in Entscheidungsknoten umgewandelt wenn eine andere Klasse gezogen wird
  • Entscheidungsknoten:
  • Algorithmus:
  1. A

* B

Random Forests

  • Mehrere Einscheidungsbäume (10-1000 je nach Problemgröße)
  • viele kleine einfache,
  • unkorrelierte Bäume
  • Zufällige Wahl von Attributen
  • Jeder Baum sollte für sich ein guter Klassifikator sein
  • Entscheidung basierend auf Mehrheitsentscheid
  • Training und Evaluation sind parallelisierbar, da getrennt voneinander abarbeitbar.
  • Effizient bei großen Datenmengen
  • Overfitting wird ignoriert weil „die Masse machts“
  • Kein Pruning mehr
  • Randomisierungsmöglichkeiten:
  • Bootstrapping
  • n Beispiele mit zurücklegen aus n Trainingsdaten -> 63% der Größe der verglichen mit Ursprungsdatensatz
  • Über Attributmenge Teilmenge für Bäume definieren
  • „right kind of randomness“

Instanzbasiertes Lernen

Allgemeines

  • Lazy Learning (Rechenaufwand nicht während dem Lernen sondern während der Klassifikation -> teuer)
  • Lernen eigentlich nur Abspeichern der Trainingsdaten
  • Lokale Approximation der Zielfunktion, damit unterschiedliche Hypothesen
  • Komplexere symbolische Repräsentation für Instanzen
  • Komplexere Zeilfunktion möglich
  • Information aus Trainingsbeispielen geht nicht verloren
  • Hypothesenraum nicht so eingeschränkt als wie bei „Fleißigen“ Lern-Algos
  • Geneardliesierungsentscheiden erst bei Suchanfrage
  • Neue Instanzen werden analog zu „ähnlichen“ Klassifiziert
  • Was ist ähnlich?
  • Problem irrelevanter Eigenschaften
  • Müssen vorher bekannt sein

k-Nearest-Neighbor (k-NN)

  • Subsymbplisch, nicht inkrementell
  • N-Dimensionaler Instanzvektor
  • Nachbarschaftsbeziehung definiert durch Distanzfunktion
  • Euklidische Distanz
  • TODO Grafik Formel
  • Konzeptlernen: f: R^n -&gt; V, V =endliche Menge
  • Trainingsalgorithmus: Hinzufügen der Traininsbeispiele in Liste
  • Klassifikationsalgorithmus: Bestimmen der Klasse anhand der k nächsten Nachbarn
  • Tradeoff:
  • k zu groß: Einfluss von weit entfernten Instanzen
  • k zu klein: Descission-Boundary (Voronoi-Diagramm)

Normalisierung von Dimensionen

  • Verzerrung bei stark ungleichen Eingabedimensionen (Fehlgewichtung einer Dimension mit kleinerem Wertebereich)

TODO Grafik

Abstandgewichtung

  • Man kann noch nähere Nachbarn stärker Gewichten, wie weiter entfernte
  • Distanzbasierte Gewichtung

TODO Formel

Bewertung k-NN

  • Induktiver Bias: Klassifikation anhand benachbarter Instanzen
  • Vorteile
  • Robust bei verrauschten Daten (besonders gut wenn Gewichtung genutzt wird)
  • Nachteile
  • Distanzmaß basiert auf allen Attributen
  • Evtl nur Untermenge relevant (->PCA)
  • Curse of dimensionality
  • Speicherorganisation
  • Hauptzeitaufwand während Klassifikation

Case-based Reasoning (CBR)

  • Allgemeines (abstraktes) Framework
  • Kein direkt anwendbarer Algorithmus
  • Analoges Schließen (Beispiel: Sonnensystem und bohrsches Atommodell)
  • Basiert auf Erinnerung, Wiederverwendung alter Fälle
  • Adaption von vorhandenen Lösungsansätzen
  • Menschenähnliches Vorgehen

Definition Fall

  • Kognitionswissenschaften: Abstraktionen von Ereignissen begrenzt in Zeit und Raum
  • Technische CBR Sichtweise: Fall bereits real aufgetreten + bei der Bearbeitung gemachten Erfahrungen
  • Mindestens:
  • Problembeschreibung
  • Lösungs(-versuch)
  • Ergebnis
  • Zusätzlich:
  • Erklärung für Ergebnis
  • Lösungsmethode
  • Pointer auf andere Fälle
  • Güteinformation

CBR Zyklus

TODO cbrZyklus Bild

  1. Auffinden (Retrieve)

* Ähnlichkeitsmaß
* Organisation der Fallbasis
* Effizientes Auffinden von Fällen -> Indizes
* Manuell
* Check-Liste
* Differenzbasiert
* Kombination beider Methoden
2. Wiederverwendung (Reuse)
* Lösungsadaption
3. Anpassen/Überarbeiten (Revise)
* Evaluierung der Lösung
* Verbesserung bzw. Reparieren der Lösung
* (Potentiell Iterativ!)
4. Zurückbehalten (Retain)
* Bewahrung der gemachten Erfahrungen

Bewertung

Vorteile
  • Konzept einfach, trotzdem komplexe Entscheidungsgrenzen möglich
  • Relativ wenig Information notwendig (Geringer Beispielumfang notwendig)
  • Analog zu menschlichen Problemlösen
  • Lernen ist einfach („one-shot learning“)
  • Günstig für mit Regeln schlecht erfassbare Probleme
Nachteile
  • Gedächtniskosten
  • Klassifikation kann lange dauern (Repräsentationsabh.)
  • Problematisch bei komplexen Representationen
  • Problem: Irrelevante Eingeschaften (Müssen vorher bekannt sein)

Bayes Lernen

  • Gold-Standard für Beurteilung von (nicht-stat.) Lernverfahren
  • Praktische Probleme:
  • Initiales Wissen über W! notwendig
  • Nicht-inkrementelles Verfahren (gibt auch inkremmentelle)
  • Es werden seehr viele Trainingsdaten benötigt um Wahrscheinlichkeiten zu bestimmen
  • Subsymbolisch (Arbeiten mit W!)

Statistische Lernverfahren

  • Kombinieren vorhandenes Wissen (a priori W!) mit beobachteten Daten
  • Hypothesen können mit einer W! angegeben werden (vorher nur 0 oder 1) -> Gütemaß!
  • Jedes Beispiel kann Glaubwürdigkeit einer Hypothese verändern
  • z. Bsp. besser einsetzbar bei verrauschten Daten
  • -> Robuster
  • Mehrere Hyppothesen miteinander kombinierbar -> besser Ergebnisse

Theorem von Bayes

Maximum a posteriori (MAP) Hypothese

P(D) ist unanhängig von der Hypothese damit nicht weiter relevant

Maximum Likelihood (ML) Hypothese

  • Da man eine Gleichverteilung der Hypothesen annehmen muss (kein Wissen darüber), kann man P(h) weglassen
  • -> ist nur ein Skalierungsfaktor der bei allen Hypothesen gleich ist
  • Ohne Vorwissen ist MAP = ML

Brute Force Lernen von MAP-Hypothesen

  • Sehr teuer bis ummöglich

Konzeptlernen

  • Versionsraum VS (Enthält nur konsistente Hypothesen mit Testdaten)
  • Induktiver Bias: Menge aller Annahmen die getroffen werden müssen um die Ergebnisse eines induktiven Lerners dekduktiv abzuleiten
  • Anforderungen festgestellt die man braucht um Konzeptlernen durchführen zu können
  • Annahmen…
  • Ergebnis
  • Was würde passieren wenn die Trainingsdaten nicht nicht-verrauscht sind?
  • Verteilung kann auch Werte annehmen die nicht auf 0 oder konst. Wert fallen

Lernen einer reell-wertigen Funktion

  • Regression statt Konzept
  • Grundannahme lineare Funktion

Prinzip der minimalen Beschreibungslänge (MDL-Hypothese)

  • Occam‘s Razor: Bevorzuge die einfachste Hypothese, die mit den Trainingsdaten übereinstimmt.

Klassifikation neuer Instanzen

  • Bisher: Hypothese mit höchster aposteriori W!
  • nicht MAP-Hypothese!

Optimaler Bayes-Klassifikator

  • Kein anderes Klassifikationsverfahren das bei gleichen Vorwissen im Durchschnitt besser abschneidet.
  • Aber: Sehr kostenintensiv bei großer Hypothesenanzahl!

Gibbs Algorithmus

Naiver Bayes-Klassifikator

  • Annahme der bedingten Unabhängigkeit von Attributen
  • Gilt eigentlich aber oft nicht
  • Trotzdem gute Werte
  • Klappt aber nicht immer

Bayes’sche Netze

  • Zwischenstufe zwischen Optimalen und Naiven Bayes-Klassifikator
  • Relativiert: Nur noch Untergruppen von Attributen sind bedingt unabhängig
  • Basiert auf gewichtetem DAG

Inferenzverfahren

Lernen

Drei Fälle:
1. Struktur bekannt, alle Vars beobachtbar: Naiver Bayes-Klassifikator
2. Struktur bekannt, nur einige Vars beobachtbar: Gradientenanstieg, EM
3. Struktur unbekannt: Heuristische Verfahren

Expectation Maximization (EM) Algorithmus

  • HMM ist Spezialfall von Bayesschen Netzen
  • Baumwelch-Algo Instanz von EM-Algo
  • Liefert nur ein lokales Optimum!
Vorgehensweise für gauß-mixtures
  • E (estimination) Schritt
  • M (maximum likelihood) Schritt
Allgemeines EM-Problem
  • Liefert Erwartungswert von logarithmierter MLverteilung approximieren

Support Vector Machines (SVMs)

(Zöllner)

  • Gehören zu den Kernel-Methoden
  • Occams Razor principle
  • SVMs kommen da sehr nahe heran
  • Klassifikations-Gold-Standard
  • SRM wird versucht zu erfüllen

Lineare Support Vektor Methode

https://dl.dropboxusercontent.com/s/gnrvuo8rdj00emy/svnliniea.PNG?dl=1&token_hash=AAGD5-_0QeImUj-DQNfT9x8AD3DSlQigxk-4gTYqzH2zNw&expiry=1400055988

  • Klassifikation, Trennung von zwei Mengen
  • Finde beste Trenngerade
  • Maximierung des Randes (Marging) <=> Maximierung der Generalisierung
  • In der Realität nicht so schön linear

Geometrische Interpretation und Formalisierung

  • Trennhyperebene ist nicht von allen Lerndaten abh. nur von nahen Punkten
  • α für weit entfernte gegen 0
  • Die nahen Punkte nennt man Support Vektoren

https://dl.dropboxusercontent.com/s/y2hd3fzojt94nfq/trennhyperebeneSVM.PNG?dl=1&token_hash=AAExK6hikaKzZa3hauztxl1sym2ZhpwsDAW9V7ZHJST3aw&expiry=1400159667

Lagrange Methode zur Minimierung
  • Lernen = Optimierungsproblem lösen
  • Minimierung von Optimierungsproblem mit Randbedingungen
  • Gesucht: Sattelpunkte
  • Duale Lagrange-Gleichung -> Duales Optimierungsproblem
  • Nur noch von Lagrange Multiplikatoren α abhängig
  • Einfacher zu lösen

Wird „nur“ angewendet nicht weiter hergeleitet

Support Vektoren

  • Nur von einigen Supportvektoren abh.
  • Liegen am nächsten zur Trennebene
  • w ist eine Linearkombination weniger Vektoren x (Supportvektoren)
  • w = Summe_i(α_i*y_i*x_i')
  • Die meisten α = 0 es reichen in 2D schon 3 Punkte
  • Damit sehr schnell berechenbar

Nichtlineare Support Vektor Methode

Soft-margin SVM

  • Genearlissierte optimimale Hyperebene
  • Einfürhung von Slack-Variabeln ξ >= 0 (aber klein)
  • Erlaube eine geringe Zahl von Missklassifikationen
  • Es dürfen Datenpunkte bis zu einem bestimmten ξ missklassifiziert werden
  • Aber es gibt auch Probleme die man nicht so trennen kann
  • Anpassung des Minimierungsproblems

https://dl.dropboxusercontent.com/s/hodbpn6jw4lw7fz/softmarginSVM.PNG?dl=1&token_hash=AAGZtQNyXcJrocmwL3c5o8YiW_oxCKUTTK_MJUIfzpUcXA&expiry=1400160266

  • Parameter C: Regulierungsparameter
  • C groß -> wenig Missklassifikation
  • C klein -> maximale Margins
  • Aussage von C
  • (Alle Vektoren x_i mit α_i > 0 = Support Vectoren)
  • α_i &lt; C: Supportvektor liegt am Rand Abstand 1/||w|| (margin vector)
  • α_i = C:
  • ξ_i &gt; 1 Fehlklassifikation
  • 0 &lt; ξ_i &lt;= 1 Richtig, geriner Abstand = margin error
  • ξ_i = 0 margin vector

Kernel Trick

https://dl.dropboxusercontent.com/s/2o5ooebj1waopht/IMG_20140515_151914.jpg?dl=1&token_hash=AAGlp6VDodgjOcyBhf73J-FW79uS16vXX79FdPK14W8s_w&expiry=1400163605

  • Idee: Transformiere die Daten in einen anderen Raum und versuche es dort zu lösen
  • Meistens einen Raum höherer Dimension
  • Nicht immer: z. Bsp: Zwei Spiralen in 2D in Polarkoordinaten transformieren (auch 2D)

http://www.37steps.com/wp-content/uploads/2013/02/spiral_fisher_full.png

  • Bei Klassifikation: Lineare Trennung in diesem Raum
  • Aber Rechnen in Hochdim. Raum sehr teuer
  • -> Dank Lagrange-Methode ist aber nur das Skalarprodukt, nicht komplette Transformation notwendig
  • Es kommt nie φ(x) alleine vor immer irgendwie als Skalarprodukt
  • Einzige Form in der die Daten vorkommen ist das Skalarprodukt
Beispiel Monomtransformation:

dl=1&token_hash=AAFJu4GFp7CnWFohZOoDnEYzZt-OObaCWhu84ubx_Dxopw&expiry=1400163996

Kernels

(Skalarprodukte)
TODO Formeln einbauen

Architektur

  • Gewisse Ähnlichkeit zu FF-NN mit Sigmoid-Schwellwert (tanh)
  • Lernen unterscheidet sich aber deutlich (vorallem bei BP-NNs) -> andere Ergebnisse
  • Vor allem weil Support Vektoren für den Rand zuständig sind?!

Version Space für SVM

  • Grund warum SVMs die SRM implizit umsetzen
  • Dualität zwischen feature space und hypothesis space
  • Generell sucht man w und b die die Randbedingungen am besten erfüllen
  • Man kann das Problem auch rum drehen
  • Jeder Datenpunkt erzeugt eine Trennebene in Hypothesenraum, die den Hypothesenraum einschränkt.
  • Jeder weitere Datenpunkt, der ein Supportvektor ist (also nahe genug an der Grenze zwischen den beiden Klassen liegt) verfeinert den möglichen Hypothesenraum weiter
  • Mittelpunkt dieser Hyperkugel ist die optimale Lösung
  • VC-Dim. hängt von Radius der Hyperkugel ab
  • -> Durch Hinzunahme bzw. Weglassen von (relevanten) Datenpunkten kann der Hypothesenraum/VC-Dim der Lernmaschine beeinflusst werden.
  • VC-Dim. h fällt stehtig h <= D²*|w|² (D = Radius der Hyberkugel)
  • -> Damit SRM während Lernen implizit!
  • -> Kleinste und beste Realisierung für w -> Occamsches Prinzip

https://dl.dropboxusercontent.com/s/s373krw61p1wfjm/dualit%C3%A4tSVM.PNG?dl=1&token_hash=AAHsoqBkocuziy9kTzmgf79ZsM3EAYeyZw8LLPZkIx_wZw&expiry=1400164417

Erweiterungen

  • reduced – RSVM
  • Kleine Anzahl (regulierbar) von Support Vektoren  Entscheidung wird anhand der Randregionen gefällt
  • Verfahren für multiple Klassifikation
  • Kombination von Einzelverfahren
  • Jeder gegen jeden
  • Einer gegen alle
  • Mehrfachzugehöhrigkeit mit verschiedenen Anteilen
  • -> Aber nicht wesentlich besser als Abstimmungsverfahren
  • Gewichtete SVM
  • Klassen werden einseitig mehr oder weniger gewichtet
  • So wie Soft-Margin Klassifikation (nur einseitig)
  • Dichte Träger Schätzung
  • Problem: Es gibt nur eine Art von Daten
  • Bereich im Raum wo die Daten sich Clustern
  • Suche nach Datenclustern
  • -> Trennhyberebene in transformierten Merkmalsraum
  • -> Analog zu Klassifikationsproblem (Optimierungsproblem)
  • Kernel Perceptron

Vergleich mit NNs

  • SVMs liefern immer eindeutige Lösung, was NN nicht leisten können
  • NNs nicht so stabil (Reihenfolge der Trainingsdaten, Initialisierung der Gewichte haben bei NNs Einfluss auf das Ergebnis)

Anwendungen

  • SVM Regression ist nicht so gut wie Gaußsche Ansätze
  • Bei Konzeptlernen besser

  • PCA mit SVM/Kerneltrick

  • Semiüberwachtes Lernen
  • Aktives Lernen
  • Klassifikation von Gesichtern
  • Blickrichtung
  • Geschlechter

Reinforcement Learning

(Zöllner)

  • Wurde extra nicht in die Kategorien eingeordnet
  • Spezielle Art des Lernens
  • Verstärkendes Lernen mit direktem Feedback
  • Bellmann Gleichung heißt eine rekursive Formel?!

Gesetz der Auswirkung

  • Biologisch motiviert
  • Tierwelt: Reaktionen werden stärker mit einer Situation verknüpft, die einen befriedigenden Zustand begleitet (bei unangeneme Zustände werden die Reaktionen/Situationen schwächer verknüpft)
  • Skinner Box (Maus, Käfig, Taste + Licht = Futter, Taste + kein Licht = Stromschlag)

Lernziel

  • Ziel: Maximale Bewertung von Aktionssequenz

Markov desicion process (MDP)

  • Zustandgetriebener Entscheidungsprozess zur Formalisierung
  • Markov-Bedingung: keine Abhängigkeit von der Vergangenheit
  • „Autonomer Agent & Umwelt“
  • a_t = (Aktorik) Einwirken auf die Umwelt durch Aktion
  • s_t = (Sensorik) Erfassung (partiell) von Zustand,
  • d(s_t, a_t) = s_{t+1} (Zustandsänderung)
  • Bewertung von Aktionen
  • r_t = Bewertung zum Zeitpunkt t
  • r(s_t, a_t) = r_t
  • Ziel: maximale Bewertung (reward)

https://dl.dropboxusercontent.com/s/hds99tpcg455gbc/mdp.PNG?dl=1&token_hash=AAHA_SB1iCqipSlrSRv9CqEGcUd1521PBuYOoiGdU_snKg&expiry=1399626796

Anwendungsbeispiele

  • Steuerung von Robotern (Post holen)
  • Spiele (Schach, Back-Gammon)
  • Optimierung und Planung (Fertigungsprozesse, Taxizentrale)

Strategielernen (Policy-learning)

  • Gesucht optimale Zielfunktion (target function)
  • sodass die akkumulierte Bewertung maximiert wird
  • State-Value-Function
  • Gewichtung der Bewertung (Diskontierungsfaktor) 0&lt;=γ&lt;=1
  • -> um in Zuknft liegende Bewertungen schwächer zu gewichten
  • 0: nur aktuelle Aktionsbewertung ist wichtig (1-step)
  • &gt;0: zukünftige (letzte) Bewertung werden brücksichtigt (n-step)
  • &lt;1: notwenidg für konvergente V Funktion
  • Ansonsten lange Aktionsfolgen unendlicher revert!
  • Ann: absorbierender Terminalzustand, dh.h. alle Aktionen führen konstenfrei wieder in den Zustand, damit Algo terminiert.

https://dl.dropboxusercontent.com/s/7gda5r8534f8021/statevaluefuction.PNG?dl=1&token_hash=AAHxvXS0HS9ldVYs8ClcbdOAXygGlBPkTX54HaBIDHSPqw&expiry=1399627271

Optimale Strategie

  • optimale Zielfunktion
  • Bekommt man aber leider nicht so einfach hin
  • max. akk. Bewertung
  • rekursive Definition (als Bellmann Gleichung)
  • Problem: Wie erhält man V*(s)?

Simple Temporal Difference Learning 1 (Simple Value Iteration)

  • Hartes Ersetzen
  • Basis aber sehr langsames Lernen für Praxis nicht anwendbar

Simple Temporal Difference Learning 2

  • Bruchteil der Differenz zwischen den beiden Zustandsbewertungen wird hinzugefügt
  • Schnellere Konvergenz als Version 1
  • Ähnlich zu Update-Funktion bei Neuronalen Netzen
  • Nach wie vor Probleme:
  • Erwarten in jedem Zustand einen revert r(s,a)-Funktion
  • Explizite d(s,a)-Funktion beim Lernen und auch um Policy auszuwerten
  • Aktuelle Schätzung durch die Policy bestimmt dadurch sehr langsames Lernen/Konvergenz

Problemdimensionen in RL

  • Zielfunktion: ??
  • Bewertung: direkt <-> verzögert (z.B. Back-Gammon, erst am Ende der Aktionskette klar ob Aktion x_i sinnvoll war)
  • Zustandsübergänge: deterministisch <-> stochastisch/nicht deterministische Prozesse
  • Zustand in der Realität nicht vollständig beschreibbar
  • Modell (Simulation) des Systems: vorhanden <-> nicht vorhanden
  • Zustandsraum und Aktionsraum (bekommt man mit RL aktuell noch nicht in den Griff):
  • eindimensional <-> hoch-dimensional
  • diskret <-> kontinuierlich

Deterministisches MDP

Q-Funktion (Action-Value Function)

  • Motivation: in der Realität gibt es keinen revert/Bewertung direkt durch die Aktion sondern oft erst am Ende einer Aktionskette
  • Zustandsübergangsfunktion ist nicht bekannt
  • Definiert maximale Bewertung für Zustands-Aktions-Paar
  • wenig Wissen über Zustandsübergänge nötig

https://dl.dropboxusercontent.com/s/qtzsibafh4m270v/q-funktion.PNG?dl=1&token_hash=AAEwsuG1eSStBZYNjgmI3DcKIIujQwsZJsN_vs7Xcy35Gg&expiry=1399639805

  • Idee Lerne ^Q(s,a) Wähle beste Aktion anhand einer Strategie:

https://dl.dropboxusercontent.com/s/xg7a8dkkglbkbyv/pi_q-funktion.PNG?dl=1&token_hash=AAED0GzPN-LKmhuXFPq1GV_RwGqMyXaofUmJVNQ59QV6Og&expiry=1399640119

Q-Lernalgorithmus

  • ^ heißt Schätzung
  • Konvergiert, beweisbar für deterministisches System
  • Initialisierung aller Q(s,a) mit 0
  • Zufällig über alle Zustände iterieren
  • Wähle Aktion a aus
  • r = direkte Bewertung
  • neuer Zustand s‘
  • update
  • Hartes Ersetzen gemäß Bellman-Gleichung für Q

https://dl.dropboxusercontent.com/s/uh9w2iqd5ddm3mm/q-algo.PNG?dl=1&token_hash=AAGx0QJ-z2ycjaT0GYdDDIxQjHJpmq6F_R2NCkRU6kmlPQ&expiry=1399640514

  • s <- s‘
  • Korrektheit und Konvergenz nach n Iterationen falls gilt:
  • |r(s,a)|<c
  • deterministisches System
  • wenn alle Paare (s,a) unendlich oft besucht werden

https://dl.dropboxusercontent.com/s/6vunijec1uf0lm0/q-konvergenz.PNG?dl=1&token_hash=AAET5KQfSUPWvesRQhcKQK4mbFiU9TEZNbt96EM3E2U-Mw&expiry=1399640770

  • Dauert noch länger als V zu schätzen!

Suchstrategien

  • Welche Aktion in Zustand s als nächstes gewählt werden könnte? (Besser als Raten)
  • -> Exploration und Exploitation
  • Probabilistische Modellierung für jede Aktion
  • k groß -> Q-Wert wichtiger -> Lokales Lernen
  • k klein -> Aktionen werden auch bei kleinen Q gewählt -> Alle Aktionen haben rel. große W! gewählt zu werden -> globales Lernen

https://dl.dropboxusercontent.com/s/9brkx2ybuukrq8d/probabilistischeModellierung.PNG?dl=1&token_hash=AAH2Rz4UPFvYt87xLNGn5Rst00h1U6nW7n24-qtEJ6Up_Q&expiry=1399641605

Exploration vs Exploitation
  • Während dem Lernen anfangs Exploration (globales Lernen) und dann wenn es Pfade gibt diese zu verbessert (lokales Lernen) durch eine Exploitation
  • Beste Lösung: Änderung der Suchstrategie von global zu lokal während des Lernprozesses
Optimierung
  • Kein hartes Update sondern Fehler bestimmen und gewichtet einfließen lassen
  • Abhängigkeiten der Q Werte untereinander zu speichern
  • Update von Paar (s,a) führt zu Update aller abh. Paare (s‘,a‘) die zu (s,a) führen
  • Ein Schritt passt mehre Werte von Q an
  • -> Schnellere Konvergenz
  • -> Mehr Speicheraufwand
  • Sinnvoll wenn: Aktionen benötigen hohen Zeitaufwand (Robotik)
  • Lernen mit adaptiven Modell
  • Meisten Lernschritte auf simulierter Umgebung
  • Ab und an Update aus Realität (wenig Interaktion)
  • Synchronisation, Anpassung des Modells
  • -> Schneller als in der Realität
  • Bsp. Dynamiksimulation aus Robotik, Spiele (Backgammon)

Repräsentation/Generalisierung

  • Problem: Kontinuierlicher Zustandsraum
  • Speichern der Q-Werte in Lookup-Tabelle unmöglich
  • sehr hohe Anzahl von Lerniterationen nötig
  • Kombination von RL mit Methoden höherer Generalisierung
  • z. Bsp Neuronale Netze (können gut Generalisieren, d.h. nicht explizit alle Werte in Lookup-Tabelle notwendig kann in NN gespeichert werden)
  • Ein Netz für alle Aktionen oder
  • pro Aktion ein Netz oder
  • direktes Lernen der besten Aktion
  • Update-Werte für Q(s,a) sind Lernbeispiele für das Neuronale Netz

https://dl.dropboxusercontent.com/s/nmxy3dlf50ltcgz/generalisierungrl.PNG?dl=1&token_hash=AAHdLU38sqqUmC_vS_1G-gxWoOMgfFqRcSEwxIPA7HdO2A&expiry=1399644675

Nichtdeterministische MDP

  • Folgezustand ist noch zusätzlich von einer gewissen Wahrscheinlichkeit abhängig
  • Umdefinition der Bellman-Gleichungen:
  • Nicht nur ein revert sondern Erwartungwert über alle möglichen Zustände
  • Nicht nur einen Q-Wert sondern das max. der möglichen Folgezuständen

https://dl.dropboxusercontent.com/s/or0q7seet16lv7y/ndmdp.PNG?dl=1&token_hash=AAFY5agYVB4FIv4PAQ0y8kHXk0CzM0M4sOXY7GnbqGanag&expiry=1399645048

Lernen von Aktionssequenzen

  • Unmittelbarer Revert beim Durchführen einer Aktion nicht anwendbar beispielsweise bei Spielen (Backgammon)
  • Revert kann erst am Ende einer Sequenz gelernt werden
  • Nachfolgende Aktionen können für den schlechten Ausgang verantwortlich sein

Temporal difference learning (TD)

  • Die Differenz folgender Schätzungen als Lernsignal für Q(s,a), V(s)
  • Vorwärts – Sicht (theoretisch)
  • Gewichtete Anpassung an direkt nachfolgender Schätzung (1-step) oder
  • Gewichtete Anpassung an n Schritte nachfolgender Schätzung (n-step)
  • Aber: Rückwärtige Sicht des TD-Lernen (praktisch)
  • Fehlersignale (temporal differences) in den Schätzungen werden nach hinten weitergegeben
Eligibility Traces
  • „Verantwortlichkeitsspur“
  • Zustände für die Zustandsbewertung -> V-Lernen
  • (Zustände/Aktion) für die Q-Wert Bewertung -> Q-Lernen
  • e_t(s) nimmt stetig ab außer es wurde der Zustand besucht
  • Zählt wie oft ein Zustand/Aktion/Zustand-Aktion-Paar in der Vergangenheit vorkam
  • Sie geben an wie Zustand/Aktion/Zustand-Aktion-Paar sie den Wert des jetzigen Zustands beeinflusst

https://dl.dropboxusercontent.com/s/rf2vygmol6903h8/EligibilityTraces.PNG?dl=1&token_hash=AAEOaUvNDTLX3cpqGFlIw9Gn3Gu69yJUUuwDF9tPWTP1QQ&expiry=1399647807

SARSA(λ)-Algorithmus
  • Erweiterung des Basisalgorithmus (Q-Lernen?!
  • (Bereits angepasst mit weichen Update)
  • Sofern es ein Revert gibt
  • Fehler bestimmen und
  • Eligibility erhöhen
  • Für alle (s,a) in der Zustandsfolge durchführen
  • Sonst kein Update der Werte
  • -> Schnellere Konvergenz

https://dl.dropboxusercontent.com/s/lp8kepgtl635idk/sarsa.PNG?dl=1&token_hash=AAGEkSKGLeZdzgzbLnJ3R88rygvKBSlm9T6YRBjh2pajmw&expiry=1399648109

Beispiele

  • Optimierung von Systemen
  • Fahrstuhlsteuerung, 4 Stück, Minimierung mittlere Wartezeit
  • Randbedingungen (Vorwissen) vereinfachen das Lernproblem (Lernraum)
  • Trotzdem Zustandsraum groß -> NN -> braucht relativ wenig Lernbeispiele

Hidden-Markov-Modelle (HMM)

Markov Logik Netze (MLN)

Evolutionäre Alogrithmen

(Zöllner)

  • Biologisches Evolutionsmodell nach Darwin:
  • Selektion = Treibende Kraft der Evolution
  • Evolution als Optimierung komplexer, künstlicher Systeme auf Basis von:
  • Selektion
  • Zufall
  • Es handelt sich oft um eine Parallelisierung eines Problems

Nomenklatur

  • Individuum: Eine mögliche Hypothese
  • Population (und  Generation): Menge von Hypothesen
  • Erzeugen von Nachkommen: Generierung von neuen Hypothesen
  • Rekombination
  • Mutation
  • Nachfolger: Kind, Nachkomme <- Neue Hypothese
  • Fitnessfunktion: Hypothesengüte, zu optimierendes Kriterium, Erfolgt auf Lernbeispielauswertung
  • Selektion der Besten: Auswahl der Hypothesen, welche die beste Problemlösung erzeugen
  • Welche Hypothese darf Nachfolger erzeugen?
  • Welche Hypothese überlebt?

Grundalgorithmus

https://dl.dropboxusercontent.com/s/2uh7qgjhx1ut276/evolution%C3%A4reAlgosGrundAlgo.PNG?dl=1&token_hash=AAE1vHDcru9y0Y_jMfMjA5lbyEZgzPW7DBWnQkv4NBLLyw&expiry=1399826390

Repräsentation

  • Wissen strukturiert repräsentiert
  • Kodierung via k-Alphabet
  • (k=2 Binär): Genetische Algorithmen
  • Reelle Zahlen: Evolutionäre Strategien
  • Programmcode: Genetisches Programmieren
  • Wie viel von dieser Strukturinformation soll genutzt werden?
  • Gibt keine goldene Regel dafür- Fallabh.

Generierung von Nachkommen

  • Exploration
  • Erforschung des Hypothesenraumes (globale Suche)
  • Je stärker und zufälliger Änderungen sind, um so geringer ist die Wahrscheinlichkeit, bessere Nachkommen zu erzeugen
  • Exploitation
  • Lokale Optimierung
  • Bei lokalen Verbesserungsmethoden ist die Gefahr der lokalen Minima gegeben
  • Wird im Laufe der Suche nach den besten Individuen angepasst von Exploration zu Exploitation

Mutation

  • hängt von einem Elternteil ab
  • Gene werden Mutiert (z.B. Bitinversion)
  • Unterschiedliche Mutationsoperatoren möglich
  • Zufällige Invertierungen an bestimmten Stellen/Bits
  • Herausnehmen und Einfügen an anderer Stelle
  • Invertiertes Einfügen einer Teilsequenz
  • Es müssen gültige Hypothesen generiert werden
  • Oft anwendungsspezifisch

Rekombination

  • Zwei Elternteile werden vermischt
  • Aber man muss aufpassen valide Hypothesen zu generieren
  • Diskrete Rekombination
  • Abwechseln aus Elternteilen
  • Intermediäre Rekombination (reelle Zahlen)
  • Funktionsdefinition
  • Crossover Rekombination
  • 2 Eltern -> 2 Nachkommen
  • Single-point crossover: Durchmischen an einer Stelle
  • Two-Point crossover: an zwei Stellen
  • Uniform crossover: Abwechselnd

Selektion

  • Selektion der Überlebenden Populationsmitglieder
  • Selektion der Eltern
  • Probleme:
  • Genetische Drift:
  • Individuen vermehren sich zufällig mehr als andere
  • Crowding, Ausreißerproblem:
  • „fitte“ Individuen und ähnliche Nachkommen dominieren die Population -> Lokale Minima
  • -> Langsame Konvergenz und Vielfaltseinschränkung
  • Lösungen
  • Verschiedene Populationsmodelle und Selektionsmethoden
  • Populationsgröße optimieren

Populationsmodelle

  • Aussuchen und kombinieren von Individuen
  • Inselmethode: Evolution getrennt (Inseln), manchmal Austausch von Individuen
  • Nachbarschaftsmodell (nahe Umgebung): Nur Fitte Nachbarn erzeugen Nachkommen
  • Einfache Menge (global): die global Besten entwickeln sich rasch weiter, andere Entwicklungslinien werden unterdrückt

Populationsmitglieder

  • Populationsgröße
  • Soll sie konstant bleiben (Populationsgröße µ)?
  • Wie viele neu erzeugte Nachkommen (Anzahl Nachkommen λ)?
  • Wie viele Eltern sollen verwendet werden (Wahrscheinlichkeit der Auswahl von Eltern p)?
  • Wie werden diese bestimmt

Mitgliederselektion

  • stochastisch ausgewählt -> die besten µ Individuen
  • (µ, λ) Strategie: Auswahl nur Nachkommen (bessere Exploration)
  • (µ + λ) Strategie: bezieht auch Eltern mit ein (die Besten werden berücksichtigt, Suche nach Eliten -> Exploitation, günstig bei gut berechenbaren Fitnessfunktionen)

Ersetzungsregel für Mitglieder

  • Generationsmodus
  • Geographische Ersetzung
  • Elitist Modus (Bestes Individuum überlebt)
  • Daumenregel
  • Das beste Viertel der Population sollte drei Viertel der Nachkommen erzeugen

Selektionsmethoden

  • Wahrscheinlichkeit p für Auswahl
  • Fitness Based Selection: Aber nach einiger Zeit nur noch geringe Fitnessunterschiede
  • Ranking Based Selection: Weniger abh. von Betrag von Fitness, besser Anpassbar an Exploration/Exploitation
  • Tournament Selection (Turnier)

Evolution

  • Wie kombiniere ich jetzt die Individuen?
  • Wird bei Neuronalen Netzen angewendet
  • Lamarksche Evolution
  • Individuen ändern sich nach der Erzeugung (lernen dazu)
  • Genotyp wird verändert und vererbt
  • Baldwinsche Evolution
  • Individuen ändern sich nach der Erzeugung (lernen dazu)
  • Nur zur Fitnessbewertung
  • Genotyp bleibt unverändert
  • Hybride Verfahren

Genetisches Programmieren

  • Erzeugung optimierter Programme
  • Individuen sind Programme
  • Repräsentation durch Bäume
  • Rekombination als Austausch von Teilbäumen
  • Fitness: Programmtest auf einer Menge von Testdaten

Unüberwachtes Lernen

Grundidee

  • Ausnutzen von Ähnlichkeiten in Trainingsdaten, um die Klassen / Ballungen zu erschließen
  • Beobachtet eine Folge von Objekten / Ereignissen
  • Formt dabei (hierarchische) Konzepte, die seine Erfahrungen zusammenfassen und organisieren

Verfahren

  • Klassische Verfahren (subsymbolisch)
  • k-means
  • Agglomerative Hierachical Clustering
  • Begriffliche Ballung (symbolisch)
  • Begriffshierachien
  • COBWEB
  • Lernen durch Entdecken

k-means-Clustering

  • subsymbolisch, unüberwacht, nicht-inkrementell
  • Klassifiziert eine Datenmenge in eine a-priori vorg. Anzahl von Ballungen
  • Definieren eines Mittelpunkts (Vorläufig) für jeden Cluster
  • Iterative Anpassung / Verbesserung
  • Optimalitätskriterium: Minimierung der Abstände aller Datenpunkte von ihrem Ballungsmittelpunkt
  • Minimierung von
    https://dl.dropboxusercontent.com/s/l2fdxgx4uiy5pef/kmeans.PNG?dl=1&token_hash=AAENP0OTG3yXTbM2GJhxRmTHKyMaUY5HcNg7TFrT96LFtQ

Algorithmus

  • Platziere k Ersten Datenpunkte (Ballungszetrumsmittelpunkte)
  • Klassifiziere Datenpunkte nach minimalen Abstand zu den Ballungszentren
  • Mittelpunkte werden gemäß den Ballungen verschoben zum neuen Zentrum

Bewertung

  • Lösung hängt stark von initialer Belegung ab
  • Suboptimale Lösung kann gefunden werden
  • Mögliche Lösung: Algo mit unterschiedlichen Startpunkten anstoßen
  • Resultate hängen stark von der verwendeten Metrik als Distanzmaß ab
  • Curse of Dimensionality
  • Resultate hängen von der korrekten Wahl von k ab
  • Keine fundierten theoretischen Lösungen
  • Ergibt sich k aus der Domäne?
  • k<<n -> sonst Overfitting!

Fuzzy-k-means-Clustering

  • Beim normalen k-means: jeder Datenpunkt in genau einem Cluster
  • Abschwächung: jeder Datenpunkt x_i hat eine abgestufte / „unscharfe“ Zugehörigkeit zu jedem Cluster X_j

Hierarchische Ballungsanalyse

  • k-means: kann nur flache Datenbeschreibung
  • Ballungen können Sub-Ballungen haben (beliebig tief)
  • Iteratives Vereinen von (Sub-)Clustern zu größeren Clustern
  • Dendogramm

https://dl.dropboxusercontent.com/s/9gb4k2mx616wog2/dendogramm.PNG?dl=1&token_hash=AAHeGYUas8El3O0422QgI10nyH8njR0CFw-vY3-0fdncKw&expiry=1399837608

Agglomerative Hierarchical Clustering

  • Erzeugt Dendogramm wenn t = maxdist xi
  • O(n3): n mal jeden Cluster mit jedem Vergleichen
  • Distanzmaß (zw. Clustern)
  • Nearest Neighbor: Absoluter Abstand zwischen zwei nächsten Nachbarn der beiden Cluster
  • Farthest Neighbor: Zwei Punkte die am weitesten von einander entfernt sind = Abstand von beiden Clustern
Bewertung
  • Einfach
  • Besser geeignet als k-means Clustering, wenn k nicht bekannt, aber gewisse Aussagen über die Form der Cluster getroffen werden können (d, t)
  • Unabh. von Initialwerten

COBWEB

  • Begriffliches Ballungsverfahren
  • kontextsensitives Verfahren (klassische kontextfrei)

https://dl.dropboxusercontent.com/s/us857f48iuhfr5m/begrifflicheBallung.PNG?dl=1&token_hash=AAFVkFCknLqYLEXFKq0GazYTGj6_edOpfcRPlp3gAIINkQ&expiry=1399840884

  • Ziel: Wie können Beispiele in Klassen bezüglich ihrer Ähnlichkeit
    geordnet werden?
  • Aber trotzdem: keine Klasseninformationen gegeben
  • Lernen durch inkrementelles Aufbauen und Anpassen eines Strukturbaums

Grundprinzip

  • Nur nominale Attribute
  • Repräsentation der Begriffshierarchie als Baum, Blätter sind die speziellsten Begriffe
  • Jede Verzweigung innerhalb des Baumes steht für eine Einteilung der Unterbäume in verschiedene Kategorien

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.