Vorlesung 2 - Induktives Lernen PDF

Preview

Summary

* Vorlesung von Professor Dillmann und Professor Zöllner
* Wintersemester...

Description

Zusammenfassung - Induktives Lernen Induktion und Deduktion Induktion  

Plausibles Schließen vom Speziellen zum Allgemeinen Basis: Große Anzahl zutreffender Beispiele

P ( x1) →Q ( x 1 ) 

P ( x2) →Q ( x 2 )

…

P ( xn) → Q ( x n )

—— —— —

P ( X ) → Q (X )

Warheitserweiternd

Deduktion   

Wahrheitserhaltend Logischer Schluss Korrektheit

Induktives Lernen 

 

Induktive Lernhypothese: Hypothese, die Zielfunktion über einer großen Menge von Trainingsdaten gut approximiert, wird die Zielfunktion auch über unbekannten Daten gut approximieren Instanzraum X , Trainingsmenge D , Zielkonzept c , Hypothesenraum H Gesucht: h ∈ H mit h ( x i ) =c ( x i ) , x i ∈ X

Konzept 

Konzept: Untermenge (vogel) von Objekten (Storch, Hase) definiert auf größerer Menge (Tiere), Boolesche Funktion über größere Menge (Tiere)

vogel: Tiere → { true , false }

vogel ( Storch ) =true

vogel ( Hase ) =false

 

Konzeptlernen: Schließen auf die boolsche Funktion aus Trainingsdaten Konsistenz: Keine negativen Beispiele werden positiv klassifiziert.



Vollständigkeit: Alle positiven Beispiele werden positiv klassifiziert.

Specific-To-General-Suche   

Ausgangspunkt ist speziellste Hypothese: ¿ ¿ , ¿ , … ,¿> ¿ Negative Beispiele: werden nicht betrachtet Positive Beispiele: Immer minimalste Verallgemeinerung anwenden

Algorithmus  

h mit spezifischster Hypothese in H (z.B. ¿ sonnig , warm , windig >¿ Für jedes positive Trainingsbeispiel x o Für jede Attributeinschränkung ai in h=¿ a0 , … , an >¿  Wenn ai von x i erfüllt → Nichts  Sonst: Ersetze ai durch nächstallgemeinere Einschränkung, die Initialisierung von

x

erfüllt

¿ sonnig , warm , windig >→¿

Versionsraum (Version Space) V S H , D bzgl. des Hypothesenraums H und der Menge von Trainingsbeispielen Untermenge der Hypothesen von H , die vollständig und konsistent sind.

D ist die

Candidate-Elimination-Algorithmus 





Gespeichert werden folgende Mengen, die alle Beispiele abdecken: o Menge der speziellsten Hypothesen S , initial: S={ ¿ } o Menge der allgemeinsten Hypothesen G , initial: G={? } Beispiel x ist positiv: o Lösche aus G die mit x inkonsistenten Hypothesen o Verallgemeinere die Hypothesen in S soweit, dass sie x abdecken und sie spezifischer als eine Hypothese in G bleiben o Lösche aus S alle Hypothesen, die allgemeiner als eine andere Hypothese aus S sind Beispiel x ist negativ: o Lösche aus S die Hypothesen die x abdecken o Spezialisiere die Hypothesen in G soweit, dass sie x nicht abdecken und sie allgemeiner als eine Hypothese in S bleiben o Lösche aus G alle Hypothesen die spezifischer als eine andere Hypothese aus G sind

Bias Induktiver Bias Annahmen, die ein Lernalgorithmus machen muss, um aus Trainingsbeispielen zu verallgemeinern. Keine Vorannahmen bedeutet Auswendiglernen (z. B. Datenbank).

Vorzugskriterium (Bias) Vorschrift nach der Hypothesen gebildet werden    

Verständlichkeit (für Mensch) Klassifikationsgenauigkeit Messaufwand für die verwendeten Deskriptoren Berechnungs- und Speicheraufwand für Hypothese

Hypothesenraumbias Hypothese gehöre zu einem beschränkten Raum von Hypothesen   

Logische Konjunktion Lineare Schwellwertfunktion Gerade, Polynome

Präferenzbias Ordnung auf dem Raum der Hypothesen, wähle  

h mit höchster Präferenz

Bevorzuge Hypothesen mit weniger Disjunktionen Bevorzuge kleinere Entscheidungsbäume...