Wissensbasierte Systeme KE 4 & 5

gibt keine allg. akzeptierte Definition

• zentral: Konstruktion einer Repräsentation

  • um Aufgaben schneller/ effizienter zu erledigen

  • Güte der Repräsentation schwer zu beurteilen

• nicht gezeigt: Kritikelement

  • sagt dem Lernelement, wie erfolgreich es ist

• auch nicht gezeigt: Problemgenerator

  • erzeugt Aufgaben, die zu neuen Erfahrungen führen sollen

1. Lernstrategie

   • was ist vorgegeben

   • was sind eigene Inferenzen

2. Repräsention von Wissen

   • die das System erlernt

3. Anwendungsbereiche

   • des Lernsystems

-> keine eindeutige Zuordnung

• in einem System von allem mehrere Ausprägungen möglich

mit jeder Stufe nimmt Aufwand des Lernenden zu und Aufwand des Lehrenden ab

1. Direkte Eingabe neuen Wissens und Auswendiglernen

   • Daten und Fakten speichern

     • z.B. einfache Datenbanksysteme

   • lernen durch Programmierung

2. Lernen durch Anweisungen

   • Lernender muss Wissen aufnehmen und intern verarbeiten

3. Lernen durch Deduktion

   • aus Wissen deduktiv Schlüsse ziehen

   • vorhandenes Wissen effektiver, effizienter organisieren

4. Lernen durch Analogie

   • vorh. Wissen an neue Situationen anpassen

5. Lernen aus Beispielen

   • Lernender muss Konzepte für Beispiele selbst erstellen

6. Lernen aus Beobachtungen und durch Entdeckungen

   • induktives Lernen

   • keine Steuerung durch den Lehrenden

   • mehrere Konzepte gleichzeitig lernen

1. 3 Arten - je nachdem woher die Beispiele kommen

   a) Beispiele kommen vom Lehrenden

   b) Beispiele kommen vom Lernenden

   c) Beispiele aus der Umgebung

2. 2 Arten - je nach Art der Beispiele:

   a) nur positive Beispiele

   • Konzepte werden ggf. zu allgemein

   • Minimalitätskriterien können helfen

   b) positive und negative Beispiele

3. 2 Arten - je nach Präsentation der Beispiele

   a) alle Beispiele gleichzeitig

   b) Beispiele inkrementell geben

   • Hypothesen später vielleicht ändern

2 Arten - je nach Interaktion mit Umgebung

• a) passive Beobachtungen

• b) aktive Experimente

1. Parameter in algebraischen Ausdrücken

   • Bsp. Schwellwerte in technischen Systemen

2. Entscheidungsbäume

   • Knoten = Attribute

   • Kanten = Ausprägungen der Attribute

   • Blätter = Mengen von Objekten einer Unterklasse

3. Formale Grammatiken

   • reguläre Ausdrücke

   • endliche Automaten

4. Regeln

   • if C then A

5. Ausdrücke basierend auf formaler Logik

   • für Beschreibung von Objekten

   • und für Bildung zu erlernender Konzepte

6. Begriffshierarchien

   • formalisiertes Wissen involviert Begriffe

   • die Begriffe als Taxonomien lernen/ ordnen

u.a.

• Graphen

• Netze

• Schemata

• Computerprogramme

1. Erzeugung

   • Regeln aus Umwelt nehmen oder selbst erstellen

2. Verallgemeinerung

   • Bedinungen aus Bedingungsteil der Regel fallen lassen

     -> Regel in mehr Situationen anwendbar

3. Spezialisierung

   • mehr Bedingungen in Bedingungsteil hinzunehmen

   • -> Regel passt zu weniger Situationen

4. Komposition

   • sequentiell angewandte Regeln zu einer zusammenfassen

   • nicht mehr notwendige Bedinungen und Folgerungen eliminieren

• einfachste Form induktiven Lernens

  • sehr erfolgreich in der Praxis

Aufgabe:

• Eingabe: Objekt = Attribut/Wert-Paare

• Ausgabe: Klasse des Objekts

• hier: Klasse "ja/nein" = boolsche Funktion

  • Blätter sind Wahrheitswert

  • Knoten sind Attribute

  • Kanten sind Ausprägungen der Attribute

• es müssen nicht immer alle Attribute verwendet werden für Entscheidung

• Pfad von Wurzel zu Blatt ist logische if-then-Regel

• und-verknüpft

  (aber das ist egal, weil oder aufgespaltet werden müsste)

• aus Trainingsmenge = Menge von Beispielen

• trivial:

  • für jedes Beispiel einen Pfad

  • keine Generalisierung auf andere Beispiele

  • sondern overfitting

• Ziel:

  • möglichst kompakten Entscheidungsbaum finden

  • Occam's Razor: bevorzuge einfachste Hypothese, die konsistent mit allen Beobachtungen ist

    -> kleiner kompakter E-Baum, der konsistent mit allen Beispielen ist, ist wahrscheinlich korrekter als großer komplexer

• Heuristik:

  • nimm immer das wichtigste Attribut

    = das Attribut, das die aktuelle Beispielmenge am besten differenziert

  • rekursiv auf die Teilbäume anwenden

• Bewertung des Lernerfolgs

  • mit Testmenge

ist Top-Down Induction of Decision Trees

1. Beispielmenge ist leer

   • nimm Defaultwert oder Mehrheit der Klassifikation im Elternknoten = MajorityVal(E)

2. alle Beispiele eine Kategorie

   • die ausgeben

3. Atributmenge ist leer, Beispielmenge nicht

   • Fehlermeldung

   • entweder falsche Beispiele oder fehlende Attribute

4. positive und negative Beispiele, sowie nicht-leere Attributmenge

   • wähle bestes Attribut gemäß Wichtigkeit

1. ID3

• wählt Attribute nach absolutem Informationsgewinn

  • in bits gemessen

  • ein Bit ist Informationsgewinn einer ja/nein Antwort

    • wenn ja 50% wahrscheinlich

    • Bsp. Münzwurf: 1 bit

• 
  

  • H = Informationsgewinn

  • k verschiedene Antworten

  • v = Arten von antworten

  • P(v_i) = Wahrscheinlichkeit von Antwort i

• auch Entropie genannt

• bedingte mittlere Information

  • I(E | a bekannt)

• wählt Attribut mit max gain(a)

  • gain(a) = I(E) - I(E | a bekannt)

• Nachteil:

  • bevorzugt Attribute mit vielen Werten

    • bsp. nimmt Id -> maximaler Informationsgewinn bei med. Diagnose

1. C4.5

• nimmt normierten Informationsgewinn

  • gain ratio(a) = gain(a) / split info(a)

  • split info(a) ist Entropie des Attributs

• wählt maximales gain ratio

1. Kombination

• nach absolutem Informationsgewinn auswählen

• wenn relativer Informationsgewinn über Schwellnwert liegt

• beschreibt Teilmenge von Objekten, Ereignissen usw. über größerer Teilmenge

• Konzept kann durch charekteristische Funktion beschrieben werden

  -> durch boolesche Funktion identifizierbar

Ziel des Konzeptlernproblems:

• bestimme Konzept h \in L_C

  • heißt auch Hypothese

• mit h(e) = c(e)

= Suchvorgang im Raum aller möglichen Hypothesen

• induktives Lernen

man geht von Trainingsmenge aus

• mit Menge von Attributen

• und Zieltwert (hier wieder bool)

allgemeine Problemstellung

• Konzept teilt Obermenge in 2 Klassen

  • erfüllt

    • Menge der positiven Beispiele heißt "Extension"

  • nicht erfüllt

    • Menge aller negativen Beispiele

• völlige Übereinstimmung eines gelernten Konzepts h mit c kann nicht garantiert werden

1. Beispielsprache

   • für Beobachtungen als Eingabe

   • L_e (language of examples)

   • Tupel aller Beispiele mit Attributen (ohne Zielwert)

1. Konzeptsprache

   (Generalisierungssprache, Hypothesensprache)

   • für gelernte Generalisierungen

   • für Ausgabe

   • L_c (language for concepts)

   • Konzeptbeschreibung h \in L_c definiert Abbildung

     • h: L_E -> {0, 1}

   • Tupel der Attribute, aber auch mit leere Menge und ? (ebenfalls ohne Zielwert)

1. Zielkonzept c

   • das zu erlernen ist

2. Menge P \subseteq L_E positiver Beispiele

3. Menge N \subsetzeq L_E negativer Beispiele

Def. 5.14

• B eine Teilmenge von M mit positiven und negativen Beispielen

• c ein Konzept

• vollständig

  • wenn b positiv, dann c(b) = 1

  • alle positiven Elemente in B werden von c abgedeckt

• korrekt

  • wenn b negativ, dann c(b) = 0

  • kein negatives Beispiel wird von c abgedeckt

• konsistent

  • c ist vollständig und korrekt

1. Güte der Klassifikation

   = Prozentsatz der richtig klassifizierten Elemente der gesamten Grundmenge

2. Kosten der Fehlklassifikation

   = Summe der Kosten aller Fehlklassifikationen über gesamte Grundmenge

"Spezieller-als" Relation

• für partielle Ordnung auf Suchraum

• bezieht sich immer auf Elemente der Grundmenge

• zwei Konzepte

  • h_1, h2 \in L_E -> {0, 1}

1. h_1 ist spezieller als h_2

   • geschrieben h_1 \le h_2

   • gdw. \forall e \in L_E (h_1(e) = 1 => h_2(e) = 1)

   • auch "allgemeiner oder gleich"

   • Extension von h1 ist Teilmenge der Extension von h2

   • ist reflexiv, transitiv, antisymmetrisch

2. h_1 ist echt spezieller als h_2

   • geschrieben h_1 < h_2

   • gdw. h_1 \le h_2 und h_2 \not_le h_1

   • auch "(echt) allgemeiner"

Suchraum = Menge aller Konzepte

1. Kandidaten-Eliminations-Methode

• mit allen ausdrückbaren Hypothesen anfangen

• mit jedem Beispiel e, nicht passende Hypothesen entfernen

1. Suchrichtung speziell -> allgemein

• nutzt "spezieller-als"-Relation

• beginnt mit speziellster Hypothese h

• mit jedem positiven Beispiel e, h erweitern, dass es e abdeckt

1. Suchrichtung allgemein -> speziell

• mit allgemeinster Hypothese beginnen

• mit jedem negativen Beispiel e, h einschränken, dass es e ausschließt

Def. Versionenraum

• B ist die Menge der Beispiele

• V_B = { h \in L_c | h ist korrekt und vollständig bzgl. B }

nutzt 2 Suchrichtungen

• speziell -> allgemein

• und allgemein -> speziell

• -> also wie Kandidaten-Eliminationssuche

• repräsentiert Hypothesen aber kompakt

  • nämlich mit Begrenzungsmengen

    = die speziellsten und allgemeinsten Hypothesen

gibt alle möglichen konsisten Hypothesen aus

Versionenraum enthält alle Hypthesen zwischen S und G

• B eine Menge von Beispielen

• S = {h \in L_c | h ist speziellste Generalisierung von B }

• G = {h \in L_c | h ist allgemeinste Generalisierung von B }

• für V_B gilt:

  • V_B = { h \in L_c | \exists s \in S \exists g in G ( s \le h \le g) }

• gilt für alle Konzeptlernprobleme, weil es sich nur auf Beispielmenge bezieht

Konzept h ist speziellste Generalisierung der Beispielmenge B

• wenn h vollständig und korrekt bzgl. B

• es gibt kein konsistentes Konzept h' mit h' < h

Konzept h ist allgemeinste Generalisierung der Beispielmenge B

• wenn h vollständig und korrekt bzgl. B

• es gibt kein konsistentes Konzept h' mit h < h'

• inkrementelles Lernverfahren

  • beginnt mit S = {}

  • und G = {}

• schau Beispiel e an

  • stimmt e mit h überein -> nichts tun

  • stimmt e nicht mit h überein -> 2 Fälle

    • 1) e ist falsch negativ

    • 2) e ist falsch positiv

  • Unterscheidungen:

    1. e ist falsch positiv für s

       • s ist zu allgemein

       • kann aber nicht weiter spezifiziert werden

       • also entfernen

    2. e ist falsch negativ für s

       • s ist zu speziell

       • s weiter verallgemeinern, um e abzudecken

    3. e ist falsch positiv für g

       • g ist zu allgemein

       • g weiter spezialisieren, um e nicht mehr abzudecken

    4. e ist falsch negativ für g

       • g ist zu speziell

       • g kann man nicht weiter verallgemeinern

       • also g entfernen

• 2 Beobachtungen:

  • 1) jedes h allgemeiner oder gleich einer Hypthose in S, deckt alle positiven Beispiele ab

  • 2) jedes h spezieller oder gleich Hypothese aus G, deckt kein negatives Beispiel ab

VS terminiert immer -> 3 Fälle

1. S und/ oder G ist leer

   • Versionenraum ist auch leere Menge

   • es gibt keine konsistenten Hypothesen für Trainingsbeispiele

     
     

2. S und G sind identische einelementige Mengen

   • S = G = {h}

   • h ist das einzige Konzept das bzgl. Trainingsmenge konsistent ist

3. alle Beispiele bearbeitet S und G unterschiedlich und nicht leer

   • alle Hypothesen im von S und G bestimmten Versionenraum sind konsistent bzgl. Trainingsmenge

1. jedes h allgemeiner oder gleich einer Hypthose in S, deckt alle positiven Beispiele ab

2. jedes h spezieller oder gleich Hypothese aus G, deckt kein negatives Beispiel ab

• wenn nur noch ein Element in Versionenraum, ist eindeutiges Zielkonzept gelernt

• Voraussetzungen:

  1. Trainingsmenge enthält keine Fehler

  2. es gibt eine Konzeptbeschreibung, die im Hypothesenraum L_c liegt und Zielkonzept vollständig und korrekt beschreibt

• induktive Hypthese

  • nur Konjunktionen zugelassen

  • Disjunktionen nicht ausdrückbar

• um Attributwerte hierarchisch zu strukturieren

  • sonst muss man bei Disjunktionen gleich zu ? gehen

• Attribute der Beispielsprache sind hierarchisch strukturiert in Bäumen vorgegeben

  • Attribute sind Blätter der Bäume

• S beginnt mit leerer Menge {[leer, leer]}

• G beginnt mit Wurzel der Bäume {[Wurzel1, Wurzel2]}

irgendwie synonym zu Data Mining

= knowledge discovery in databases

• = Prozess neues, nützliches und interessantes Wissen aus Daten herauszufiltern und in verständlicher Form zu präsentieren

  • neues Wissen

    = unbekannte Erkenntnisse

  • nützliches und interessantes Wissen

    • in Betrieben = durch BWL-Parameter (Umsatz, Gewinn) steuern

    • in Wissenschaft = Gütekriterien wie Spezifität und Generalität

  • verständliche Form

    = Nutzer soll Wert der Information erkennen können

    • Interaktion mit KDD-Wissensfindungsprozess

Ziel:

•  finde relevante Zusammenhänge in großen Datenmengen

• Relevanz-Begriff umsetzen in nachprüfbaren Kriterien

• Assoziationsregeln

  • .= probabilistische Wenn-dann Beziehungen zwischen verschiedenen Dingen/ Merkmalen

    
    

1. aus Daten Wissen generieren

   • schneller und besser als nur Experten

   • Experten können validieren

2. Menschen können die Datenmengen nicht ohne Unterstützung verarbeiten

3. bessere Informationen aus Daten

4. Aufgabe ist reizvoll

1. Hintergrundwissen und Zielsetzung

2. Datenauswahl

3. Datenbereinigung

4. Datenreduktion und -projektion

5. Modellfunktionalität

   • Klassifikation

   • Clustering

   • Regressionsanalyse

6. Verfahrensauwswahl

7. Data Mining

8. Interpretation

   
   

• ggf. rekursiv

• Data Mining (Muster in Daten finden) ist wichtigster Teil

Ziel = Muster, Strukturen, Abhängigkeiten in Daten finden

• wichtiges Gütekriterium: Skalierbarkeit

Komponenten:

1. Modell

   • Form der Präsentation der Erkenntnisse

   • 
     

• 2) Präferenz- und Gütekriterien

  • a) für Anpassung des Modells

  • b) für dessen Ziel

  • z.B. maximum likelihood

• 3) Suchalgorithmus

  • 2 Typen:

    • a) Parametersuche

      • Modell gegeben, beste Parameter gesucht

    • b) Modellsuche

      • durchsucht Raum aller betrachteten Modelle

• Modelle kommen von statistischer Datenanalyse und maschinellem Lernen

1. Klassifikation

2. Clustering

   = Gruppieren ohne vorgegebene Klassen

3. Modellierung von Abhängigkeiten

   • zwischen Variablen

   • quantitative Methoden geben auch Stärke der Abhängigkeiten

4. Assoziationen

   = Zusammenhänge zwischen mehreren Merkmalen

   • z.B. 80% der Kunden die Chips kaufen, kaufen auch Bier

5. Sequenzanalyse

   • Zeitreihen für Trends

nicht notwendig kausale Zusammenhänge

typisches Beispiel: Verkaufsdatenanalyse

Begriffe

• Items

  = Dinge, deren Beziehungen zueinander beschrieben werden sollen

  • I = endliche Menge Items

  • X = eine Teilmenge von I, heißt Itemmenge

  • k-Itemmenge hat k Elemente

• Transaktion

  • t

  • ist eine Itemmenge

• Datenbasis

  • Menge von Transaktionen

• Support und Konfidenz

  -> Support und Konfidenz sind bedingte relative Häufigkeiten

= Anteil Transaktionen mit X an Anzahl aller Transaktionen

support von X -> Y

• support( X -> Y ) = support( Vereinigung X, Y)

Konfidenz X -> Y

• relativer Anteil der X enthaltenen Transaktionen, die auch Y enthalten

• hat Form X -> Y

  • X, Y sind disjunkte Itemmengen

• Transaktion t erfüllt Assoziationsregel, wenn t alle in X und Y vorkommenden Items enthält

  • Vereinigung X, Y ist Teilmenge von t

klassische Suche nach Assoziationsregeln:

• finde Regeln mit einem minsupp Support und minconf Konfidenz

2 Teilprobleme:

1. finde große Itemmengen/ bzw. häufige Itemmengen

   • alle Itemmengen deren Support über minsupp-Schwelle liegt

2. finde in häufigen Itemmengen Regeln, deren Konfidenz über minconf liegt

• für 1 müsste man 2^n Teilmengen untersuchen

  • n = Anzahl der Items

  • nicht praktikabel

nutzt:

• alle Teilmengen einer häufigen Itemmenge sind auch häufig

• alle Obermengen einer nicht häufigen Itemmenge sind auch nicht häufig

• bei Konfidenz passt das auch

  
  

Vorgehen:

• zuerst suche häufige 1-elementige Itemmengen

• dann bestimme Häufigkeit der Obermengen

• k-te Iteration besteht aus 3 Schritten:

  1. aus häuifgen Itemmengen von Iteration k-1 mit AprioriGen häufige Itemmengen bestimmen

  2. für jede Kandidatenmenge c Anzahl Transaktionen mit c bestimmen

  3. in L_k Itemmengen aufnehmen mit support über minsupp

• Ergebnis von Apriori ist Vereinigung von Lk

Laufzeit: m Iterationen

• m = Anzahl Items in größter häufigen Itemmenge

• Mengen werden im Hash-Baum abgelegt, dass Vergleich effizient ist

• nimmt an, dass Items geordnet sind

• vereint nur Mengen, die sich im größten Element unterscheiden

  • alle anderen Elemente müssen gleich sein

• schaut, um Teilmengen häufig sind, sonst lässt es die Mengen weg

1. ApprioriTid

   • durchläuft Datenbank nur einmal

   • braucht aber mehr Speicherplatz

2. ApprioriHybrid

   • vereint Vorteile beider Ansätze

findet man in Hierarchien von Dingen

z.B. Hosen sind Kleidungsstücke

= Beispielanwendung von Apriori-Algorithmus

Modellbildung meist nicht nötig

• Regeln können isoliert betrachtet werden