02 Induktives Lernen Flashcards
Was ist Induktion
Prozess des plausiblen Schließens vom Speziellen zum Allgemeinen.
- Wahrheitserweiternd
- Grundansatz angelehnt an s.g. induktiven Lernhypothesen
- Plausibilität
P(x1) –> Q(x1)
P(xn) –> Q(xn)
——————–
P(X) –> Q(X)
Induktion ist ein sehr weit verbreiteter Lernansatz (angelehnt an biologischen Ansatz)
Was ist Deduktion
Prozess des korrekten Schließens vom Allgemeinen zum Speziellen (auf basis vorhandenen Hintergrundwissens)
- Wahrheitserhaltend
- Logischer Schluss
- Korrektheit
Definition: Induktive Lernhypothese
Jede Hypothese, die die Zielfunktion über einer genügend großen Menge von Trainigsbeispielen gut genug approximiert, wird die Zielfunktion auch über unbekannten Beispielen gut approximieren
Definition: Konzept
Beschreibt Untermenge von Objekten oder Ereignissen definiert auf größerer Menge
- Bool’sche Funktion definiert über größere Menge
Lernen von Konzepten
Gegeben:
Beispiele, die als Mitglieder oder Nichtmitglieder eines Konzepts gekennzeichnet sind
Gesucht:
Automatischer Schluss auf die Definition des zugrundeliegenden Konzepts
Definition Konzeptlernen:
Schließen auf eine Boolean-wertige Funktion aus Trainingsbeispielen ihres Inputs und Outputs
Definition: Konsistenz im Hypothesenraum
Keine negativen Beispiele werden positiv klassifiziert
Definition: Vollständigkeit im Hypothesenraum
Alle positiven Beispiele werden als positiv klassifiziert
Lernen als Suche im Hypothesenraum
Repräsentation der Hypothesen legt implizit Hypothesenraum fest.
Lernen als Suche im Raum der möglichen Hypothesen
Jeder Beschreibungsraum für Konzepte ist nach Generalität (halb) geordnet
Suche vom Allgemeinen zum Speziellen:
- Ausgangspunkt ist allgmeienste Hypothese
- Negative Beispiele Sezialisierung
- Positive Beispiele: werden nicht betrachtet
Suche vom Speziellen zum Allgemeinen:
- Ausganspunkt ist speziellste Hypothese
- Positive Beispiele: (minimale) Verallgemeinerung
- Negative Beispiele: werden nicht betrachtet
Version Space:
- paralleles Anwenden beider Methoden
Definition: Versionsraum (Version Space)
Der Versionsraum VS_(H,D) bezüglich des Hypothesenraums H und der Menge von Trainingsbeispielen D ist die Untermenge der Hypothesen von H, die mit den Trainigsbeispielen in D konsitent und vollständig sind.
Version Space Algorithmus
Ist n ein negatives Beispiel:
- Lösche aus S die Hypothesen, die n abdecken
- Spezialisiere de Hypothesen in G soweit, dass sie n 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
Ist p ein positives Beispiel:
- Lösche aus G die mit p inkonsitenten Hypothesen
- Verallgemeinere die Hypothesen in S soweit, dass sie p 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
Version Space: Beurteilung
Konvergiert zur korrekten Hypothese (S=G)
- Voraussetzung: Beispiele konsistent, korrekte Hypothese in Hypothesenraum enthalten
- Probleme fehlerbehaftete Trainingsdaten (rauschen), Zielkonzept nicht von Hypothesenrepräsentation abgedeckt
- -> konsistente Beispiele sind notwendig
- -> Attributgeneralisierungsregeln maßgebend für Lernerfolg
- -> Kein Speichern alter Beispiele notwendig
- -> Stellt fest, wann genügend Beispiele gegeben wurden (S=G)
- -> Unter umständen Art noch benötigter Beispiele erkennbar
Bias (Vorzugskriterium)
Vorschrift nach der Hypothesen gebildet werden
Mögliche Vorzugskriterien:
- Verständlichkeit (für den menschlichen Benutzer)
- Klassifikationsgenauigkeit
- Messaufwand für die verwendeten Deskriptoren
- Berechnungs- und Speicheraufwand für die Hypothese
Hypothesenraumbias
h gehöre zu einem beschränkten Raum von Hypothesen
- logische Konjunktionen
- leneare Schwellwertfunktionen
- Geraden, Polynome …
- 3-NN
- …
Präferenzbias
- Ordnung auf dem Raum der Hypotheen
- wähle h mit der höchsten Präferenz
- bevorzugte Hypothesen mit weniger Disjunktionen
- bevorzugte kleinere Entscheidungsbäume
- …
