01 semi-supervised learning Flashcards
Grundannahmen
Gleichmäßigkeit für überwachtes lernen (smoothness assumption):
–> Wenn zwei Datenpunkte x1, x2 „nahe“ beieinander sind dann sollten auch die Ausgaben y1, y2 „ähnlich“ sein
Gleichmäßigkeit für Semi-überwachtes Lernen:
–> Wenn zwei Datenpunkte x1, x2 in einer dichten Region „nahe“ beieinander sind, dann sollten auch die Ausgaben y1, y2 „ähnlich“ sein
Cluster oder Dichte Annahme (Klassensicht):
–> Wenn zwei Datenpunkte im selben („dichten“) Cluster sind, dann sind sie in derselben Klasse. Eine Trennung sollte in einer Region niedriger Dichte (zw. den Clustern) liegen
Manigfaltigkeit-Annahme (Manifold Assumption):
–> Hochdimensionale Daten haben eine Abbildung in einen i.A. anders dimensionalen Raum (Manigfaltigkeitsraum) in dem sich ihre Strukturen abbilden (unterscheiden/ erhalten). Dieser Raum kann dann für die Berechnung des geodäsischen Abstand benutzt werden. –> approximative Implementierung der Gleichmäßigkeitsannahme
2 untere Güte-Schranken
SSL kann und sollte verglichen werden mit (und besser sein als):
- Ergebnis des überwachten Lernens mit ausschließlich gelabelten Daten
- Ergebnis des unüberwachten Lernens mit allen Lerndaten (ohne Labels)
Induktiv vs. Transduktive
Induktives Lernen:
Ziel ist das Schätzen einer Hypothese
ℎ ∶ X → Y
Die auch unbekannte Daten „gut“ abbildet (d.h. generalisiert)
Transduktives Lernen:
- Ziel ist das Labeln der ungelabelten Daten (kann! auch das Labeln neuer Daten sein)
- Das Finden einer Hypothese ist nicht das Ziel (kann aber erfolgen)
Ansatz: Selbst-Lernen (klassifikation)
- Weit verbreitet und vermutlich ältester SSL – Ansatz (1965 -70)
- Wrapper Algorithmus anwendbar für alle überwachten Lernmethoden
- Startet auf gelabelten Daten
- In jeder Iteration werden ungelabelte Daten gelabelt, abh. von der Entscheidungsfunktion
- Kann effektiv sein
- Nicht methodisch festgelegt, welche Annahmen über das Problem getroffen werden
- Es ist nicht definiert, wie das Ergebnis ist (und abhängig von unterschiedlichen Faktoren wie Initialisierung, Anzahl der neuen Daten, Lernmethode für überwachtes Lernen, …)
Vor- / Nachteile Selbst-Lernen Ansatz
Vorteile:
- Sehr einfache semi-überwachte Lernmethode
- Wrapper – passend zu existenten auch komplexen Klassifikatoren /etc…
- Oft angewandt in realen Anwendungen wie z.B. Sprachanalyse
Nachteile:
- Frühe Fehlentscheidungen können sich verstärken
- -> Heuristische Lösung: Daten „un-labeln“ sofern ihre Konfidenz unter einen Schwellwert fällt
- Generelle Analyse kompliziert
- ->Nur für Spezialfälle ist eine geschlossen, formale Analyse möglich
- -> In Spezialfällen entspricht Selbst-Lernen dem EM – Ansatz (siehe Generative Modelle)
Ansatz: Mit-Lernen (Co-Training)
- verwende den Wrapper – Ansatz
- 2 unabhängige Klassifikatoren werden auf je einer Featuremenge trainiert und auf die ungelabelteten Daten angewendet
- Wenige Daten hoher Konfidenz (mit oder ohne Übereinstimmung der Klassifikatoren) werden zu dem jeweilig anderen Lerndatensatz hinzugenommen
- Neutrainieren der Klassifikatoren mit dem erweiterten Datensatz Wiederholen …..
Erweiterung
- Demokratisches Co-Training: Erweiterung zu mehr als 2 Basisklassifikatoren
- -> Mehrheitsentscheidung um neue Daten hinzuzufügen
Vor-/Nachteile Co-Training
Vorteile
- Wrapper Methode – anwendbar auf alle existierenden Klassifikatoren
- Weniger anfällig für Fehlentscheidungen als Selbstlernen
Nachteile
- „Natürliche“ Featureaufteilung ggf. nicht vorhanden
- Modelle die die vollständige Featuremenge benutzten erreichen oft bessere Ergebnisse
Co-Training Varianten
Fake Feature Split
* Zufällige, künstliche Aufteilung der Merkmale Co-Training wie bisher
Multi-View-Ansatz
- Kein Feature Split
- Trainiere mehrere Klassifikatoren
- Klassifizierung der ungelabelten Daten mit allen Klassifikatoren
- Verwende Mehrheitsentscheidung für neue Labels
CO-EM
* Nutzung aller Daten
* Jeder Klassifikator labelt die Daten Xu probabilistisch
Daten (x, y) werden probabilistisch gewichtet genutzt, mit Gewicht p(y|x)
Generative probabilistische Modelle (Generative Probabilistic Models)
Generative Algorithmen nutzen eine Schätzung der Verteilung der Daten für die Klassen
Zusätzliche Information der Verteilung der Daten sind sinnvoll !! Ausgehend davon, dass Klassen kohärente Daten enthalten z.B. normalverteilt –> Geschätzte Entscheidungsgrenze wandert je nach Verteilung der Daten
Zunächst (iteratives) Schätzen eines probabilistischen, parametrisierten Verbundmodells,
p(x, y|θ)
dann Klassifikationsentscheidung unter Verwendung des Modells
Im Gegensatz dazu schätzen (nutzen) die diskriminativen Verfahren direkt: p(y|x) (z.B. SVM)
Generative probabilistische Modelle – SSL Grundverfahren
- Wähle ein generatives Modell
- Finde Maximum likelihood Schätzung (MLE) auf gelabelte und ungelabelte Daten (Expectation Maximization)
- Bestimme Klassenzugehörigkeit entsprechend der Bayes‘schen Regel
Generative Modelle: Vor-/Nachteile
Grundsatz
- Maximierung von p(Xl,Yl,Xu | θ)
- Verwende optimales Modell für die Trennung
- EM ist nur eine Variante, andere Methoden existieren
Vorteile
- Klares, wohl definiertes Framework
- Kann sehr effektiv sein WENN das Modell korrekt ist
Nachteile
- Verifikation der Korrektheit des Modell meist nicht möglich
- EM – kann zu lokalen Minima führen
- Ungelabelte Daten können schaden wenn das Modell nicht korrekt ist
Dichte Trennung (Low – density separation) mit semi-überwachter SVM
Ziel in SSL: Trennung in einer Region niedriger Dichte
–> lässt sich mit SVM gut umsetzten
Annahme: Ungelabelte Daten unterschiedlicher Klassen werden mit großem Rand getrennt – aber wie?
Naiver Ansatz:
- Alle 2^u Möglichkeiten der Labels betrachten
- Trainiere SVM für alle Möglichkeiten
- Wähle SVM mit größtem Rand a–> Sehr aufwändig – nicht möglich
Besser: Integriere ungelabelte Daten in das Optimierungsproblem
Das neue Optimierungsproblem ist aquivalent damit, dass die Trennung f(x) = 0 in einer Region ohne gelabelte und ungelabelte Daten liegt
Die Transduktive SVM hat ein nicht-konvexes Optimierungsproblem:
–> Finden einer Lösung ist komplizierter (NP-hart) und insbesondere nicht mehr eindeutig
SVM light
Heuristisches, iteratives „Labeln“ mit Ausbalancierung
Trainiere SVM auf (X_l, Y_l)
Labeln der Daten aus X_u
- Trainiere Modell
- tausche alle, die switchable sind
- Trainiere Modell
- tausche alle, die switchable sind
…
bis keine switchable labels.
S3VM
probabilistische Sicht Erweiterung für SSL …
Funktioniert nicht immer. Insbesondere wenn die Grundannahme (–> Trennung niedrige Dichte) falsch ist:
Vor-/Nachteile semi-überwachte SVM
Vorteile
- Anwendbar wenn SVM anwendbar
- Klar formuliertes mathematisches Rahmenwerk
Nachteile
- Optimierungsproblem nicht mehr konvex
- Optimierung – kompliziert
- Lokale Minima
- Schwächere Annahme (Dichte) als generative Modelle oder graphbasierte Methodene –> möglicherweise schlechtere Ergebnisse
