© Prof. Dr. H. Gläser, Künstliche Intelligenz Automatisierung des Lernens

Automatisierung des Lernens

Inhalt:

• Problemstellung

• Prädikatenlogische Mittel

• Sequentielle Bedeckalgorithmen

• Induktive Logische Programmierung

• Induktion als invertierte Deduktion

• Erklärungsbasiertes Lernen

Problemstellung:

Lernen = Induzieren von Regeln aus Beispielen !

Viele Patienten mit Röteln haben rote Punkte

Alle Menschen mit roten Punkten haben Röteln

Attribute

Eigenschaften, die einen Wert annehmen könnenSpaltenbezeichnungen in einer Tabelle

TennisWirdGespielt Windstärke Feuchtigkeit Wetter

ja schwach normal sonnig

nein stark hoch regnerisch

Beispiel

eine Zeile der Tabelle

Regel:

IF <Vorbedingung> THEN <Nachbedingung>

Vorbedingung bzw. Nachbedingung:

Konjunktion (Verbindungen mit UND) vonAttribut / Wert Kombinationenz.B.Wetter=sonnig UND Feuchtigkeit=hoch UND ...

Aufgabe:

Es sollen Regeln gelernt werden, die ein Attribut (das Zielattribut) als Nachbedingung haben

z.B.IF Wind=schwach UND Feuchtigkeit=niedrig THEN TennisWirdGespielt=ja

Sequentieller Bedeckalgorithmus

while( noch nicht alle Beispiele abgedeckt )

ruft „Learn One Rule“ auf:

Learn-One_Rule liefert neue Regel„abgedeckte“ Beispiele werden beiseite gelegtRegeln = bisher gewonnene Regeln neue Regel

Learn-One-Rule(ZielAttribut, Attribute, Beispiele)

Learn One Rule - Algorithmus

Menge von Hypothese Kandidaten

Beste Hypothese

informierte „Tiefe zuerst Suche“ vom allgemeinen zum speziellen

HypotheseEine versuchsweise aufgestellte Regel

Während der Suche diejenige Hypothese, mit der besten Performanz,d.h. diejenige, die die Beispiele am besten beschreibt

Stapel noch nicht expandierter Knoten, d.h. noch nichtausgewerteter Kandidaten für Hypothesen

Alle Constraints

Neue Hypothese Kandidaten

Eine Menge von neuen Hypothese Kandidaten, die während derSuche gebildet werden

Menge aller Constraints, die in den Beispielen vorkommen

ConstraintAttribut / Wert Paar der Form Windstärke=stark

Problemzustand:= eine Regel-Hypothese mit dem Zielattribut

Operator:

jeder Constraint a=b aus „alle Constraints“ bildet einen Operator

beim Expandieren eines Problemzustands wird der neueConstraint der bisherigen Hypothese mit UND hinzugefügt:

alter Problemzustand:IF Windstärke=stark UND Wetter=regnerisch THEN TS = ja

Operator: Feuchtigkeit=hoch

neuer Problemzustand:IF Windstärke=stark UND Wetter=regnerisch UND Feuchtigkeit=hochTHEN TP = ja

Algorithmusidee:

es werden vorhandenen Constraints systematisch mit UND zuRegel-Vorbedingungen kombiniert, und deren Wirksamkeit in der Beschreibung der Beispiele gemessen (Performanz)= informierte Suche

Dabei beginnt man mit möglichst allgemeinen Hypothesen d.h.mit möglichst wenigen Constraints und expandiert diese zuspezielleren Hypothesen (mehr Constraints)

Performanzmaß

relative Häufigkeit

n = Zahl von Beispielen, die mit der Vorbedingung der Regel übereinstimmen

nc= Zahl von Beispielen aus n, bei denen das Zielattribut denWert des Zielattributs der Regel annimmt

Performanzmaß

Entropie:

S = Menge von Beispielen, die mit der Vorbedingung der Regel übereinstimmenc = Anzahl von verschiedenen Werten, die das Zielattributannehmen kann

pi= Anteil von Beispielen aus S, bei denen das Zielattribut den i-tenWert annimmt

iii ppSEntropie

12log)(

(Formel wie sie im beschriebenen Algorithmus verwendet wird)

(bessere Regeln habenhöhere Werte)

(mißt die Gleichförmigkeit der Zielattribut Wertefür den Satz S an Beispielen)

0 0,2 0,4 0,6 0,8 1 1,2

Reihe1

ii pp 2log

(Fortsetzung des Algorithmus)

Initialisieren der Beste Hypothese mit der allgemeinsten Hypothese

while (Menge von Hypothese Kandidaten nicht leer)

1. Erzeuge die nächst-spezifischeren Hypothese Kandidatend.h. die Neue Hypothese Kandidaten:

for jede Hypothese h in Menge von Hypothese Kandidaten

for jeden Constraint c in Alle Constraints

neue Spezialisierung durch Hinzufügen von c zu h

2. for jede Hypothese h aus Neue Hypothese Kandidaten: if Performanz(h) > Performanz(Beste Hypothese) h wird Beste Hypothese

Entferne alle Hypothesen, die doppelt, inkosistent, nicht maximalspezifisch

(Fortsetzung des Algorithmus)

3. die k besten Hypothesen aus Neue Hypothese Kandidaten bilden nun Menge von Hypothese Kandidaten

(Ende von while über Menge von Hypothese Kandidaten )

return Regel: IF Beste Hypothese THEN Nachbedingungwobei Nachbedingung: Zielattribut=Wertwobei Wert der häufigste Wert vom Zielattribut unter den Beispielen,die Beste Hypothese beschreibt

Beispiel für „Sequentielle Bedeckung + Lerne_Eine_Regel“

TennisWirdGespielt Wetter Luftfeuchtigkeit Windstärkeja sonnig gering geringnein regnerisch hoch geringnein regnerisch hoch geringnein sonnig gering hochnein regnerisch hoch geringnein sonnig gering hochnein sonnig gering hochja sonnig gering geringnein sonnig gering hochnein sonnig gering geringja sonnig gering geringja sonnig gering geringnein regnerisch hoch geringja sonnig gering hochja regnerisch hoch geringja regnerisch hoch geringja sonnig gering hoch

Alle Constraints :{Wetter=sonnig,Wetter=regnerisch,Luftfeuchtigkeit=gering, Luftfeuchtigkeit=hoch,Windstärke=gering,Windstärke=hoch}

Kandidaten Hypothesen: IF THEN TennisWirdGespielt = ?

Neue Kandidaten Hyphothesen:

IF Wetter=sonnig THEN TennisWirdGespielt = ?IF Wetter=regnerisch THEN TennisWirdGespielt = ?IF Luftfeuchtigkeit=gering THEN TennisWirdGespielt = ?IF Luftfeuchtigkeit=hoch THEN TennisWirdGespielt = ?IF Windstärke=gering THEN TennisWirdGespielt = ?IF Windstärke=hoch THEN TennisWirdGespielt = ?

IF Wetter=sonnig THEN TennisWirdGespielt = ?Gesamtbsp.: 11; pja=6/11; pnein=5/11; Entropie=-0,99IF Wetter=regnerisch THEN TennisWirdGespielt = ?Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92IF Luftfeuchtigkeit=gering THEN TennisWirdGespielt = ?Gesamtbsp.:11; pja=6/11; pnein=5/11; Entropie=-0,99IF Luftfeuchtigkeit=hoch THEN TennisWirdGespielt = ?Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92IF Windstärke=gering THEN TennisWirdGespielt = ?Gesamtbsp.:11; pja=6/11; pnein=5/11; Entropie=-0,99IF Windstärke=hoch THEN TennisWirdGespielt = ?Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92

Bewertung mit Entropie:

Kandidaten Hypothesen (k = 1)

Neue Kandidaten Hypothesen

IF Wetter=regnerisch THEN TennisWirdGespielt = ?Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92

IF Wetter=regnerisch UND Wetter=sonnig,IF Wetter=regnerisch UND Wetter=regnerisch,IF Wetter=regnerisch UND Luftfeuchtigkeit=gering,IF Wetter=regnerisch UND Luftfeuchtigkeit=hoch,IF Wetter=regnerisch UND Windstärke=gering,IF Wetter=regnerisch UND Windstärke=hoch

IF Wetter=regnerisch UND Wetter=sonnig,widersprüchlich !IF Wetter=regnerisch UND Wetter=regnerisch,doppelt !IF Wetter=regnerisch UND Luftfeuchtigkeit=gering, kein Beispiel IF Wetter=regnerisch UND Luftfeuchtigkeit=hoch,Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92IF Wetter=regnerisch UND Windstärke=gering,Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92IF Wetter=regnerisch UND Windstärke=hoch kein Beispiel

Wetter=regnerisch,Luftfeuchtigkeit=hoch, Wetter=sonnig,Wetter=regnerisch,Luftfeuchtigkeit=hoch, Wetter=regnerisch,Wetter=regnerisch,Luftfeuchtigkeit=hoch, Luftfeuchtigkeit=gering, Wetter=regnerisch,Luftfeuchtigkeit=hoch, Luftfeuchtigkeit=hoch,Wetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=gering,Wetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=hoch

IF Wetter=regnerisch UND Luftfeuchtigkeit=hoch,Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92

TennisWirdGespielt Wetter Luftfeuchtigkeit Windstärkeja sonnig gering geringnein regnerisch hoch geringnein regnerisch hoch geringnein sonnig gering hochnein regnerisch hoch geringnein sonnig gering hochnein sonnig gering hochja sonnig gering geringnein sonnig gering hochnein sonnig gering geringja sonnig gering geringja sonnig gering geringnein regnerisch hoch geringja sonnig gering hochja regnerisch hoch geringja regnerisch hoch geringja sonnig gering hoch

Wetter=regnerisch,Luftfeuchtigkeit=hoch, Wetter=sonnig,widersprüchlich !Wetter=regnerisch,Luftfeuchtigkeit=hoch, Wetter=regnerisch,doppelt !Wetter=regnerisch,Luftfeuchtigkeit=hoch, Luftfeuchtigkeit=gering, widersprüchlich !Wetter=regnerisch,Luftfeuchtigkeit=hoch, Luftfeuchtigkeit=hoch,doppeltWetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=gering,Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92Wetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=hochkein Bsp.

IF Wetter=regnerisch UND Luftfeuchtigkeit=hoch,Gesamtbsp.:6; pja=2/6; pnein=4/6; Entropie=-0,92

Beste Hypothese

Wetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=gering,

häufigste Belegung des Zielattributs mit dieser Vorbedingung:TennisWirdGespielt = nein (4 von 6)

=> 1. Regel:IF Wetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=gering THENTennisWirdGespielt = nein

Entfernen der beschriebenen Beispiele aus dem Beispielsatz:

TennisWirdGespielt Wetter Luftfeuchtigkeit Windstärkeja sonnig gering geringnein sonnig gering hochnein sonnig gering hochnein sonnig gering hochja sonnig gering geringnein sonnig gering hochnein sonnig gering geringja sonnig gering geringja sonnig gering geringja sonnig gering hochja sonnig gering hoch

Learn_One_Rule beginnt von vorne:

Alle Constraints :{Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=gering,Windstärke=hoch}

Kandidaten Hypothesen: IF THEN TennisWirdGespielt = ?

Neue Kandidaten Hyphothesen:

Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=gering,Windstärke=hoch

Wetter=sonnig,Gesamtbsp.: 11; pja=6/11; pnein=5/11; Entropie=-0,99Luftfeuchtigkeit=gering, Gesamtbsp.: 11; pja=6/11; pnein=5/11; Entropie=-0,99Windstärke=gering,Gesamtbsp.: 5; pja=4/5; pnein=1/5; Entropie=-0,72Windstärke=hochGesamtbsp.: 6; pja=2/6; pnein=4/6; Entropie=-0,92

Windstärke=gering UND Wetter=sonnig,Windstärke=gering UND Luftfeuchtigkeit=gering, Windstärke=gering UNDWindstärke=gering,Windstärke=gering UND Windstärke=hoch

IF Windstärke=gering

Windstärke=gering UND Wetter=sonnig,Gesamtbsp.: 5; pja=4/5; pnein=1/5; Entropie=-0,72Windstärke=gering UND Luftfeuchtigkeit=gering,Gesamtbsp.: 5; pja=4/5; pnein=1/5; Entropie=-0,72 Windstärke=gering UNDWindstärke=gering,doppeltWindstärke=gering UND Windstärke=hochwidersprüchlich

Da bei allen Bsp. sonnig und Luftfcht. = gering:

Beste Hypothese

Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=gering

häufigste Belegung des Zielattributs mit dieser Vorbedingung:TennisWirdGespielt = ja (4 von 5)

=> 2. Regel:IF Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=gering THENTennisWirdGespielt = ja

TennisWirdGespielt Wetter Luftfeuchtigkeit Windstärkenein sonnig gering hochnein sonnig gering hochnein sonnig gering hochnein sonnig gering hochja sonnig gering hochja sonnig gering hoch

=> 3. Regel:IF Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=hoch THENTennisWirdGespielt = nein

Regeln geben zwar Aussagen für alle BeispieleSie treffen aber nicht unbedingt immer zuPerformanzwert gibt Aussage über Wahrscheinlichkeit

=> 1. Regel:IF Wetter=regnerisch,Luftfeuchtigkeit=hoch, Windstärke=gering THENTennisWirdGespielt = nein

=> 2. Regel:IF Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=gering THENTennisWirdGespielt = ja

=> 3. Regel:IF Wetter=sonnig,Luftfeuchtigkeit=gering, Windstärke=hoch THENTennisWirdGespielt = nein

Learn One Rule

positive Beispiele:

(Name1=Sharon, Mother1=Louise, Father1=Bob, Male1= False, Female1=True,Name2=Bob, Mother2=Nora, Father2=Victor, Male2=True, Female2=False,Daughter1,2=True)

while (noch Attribute übrig) Daughter1,2=True (ohne Vorraussetzung)

Daughter1,2=True Voraussetzung 1 neues AttributAttribut / Wert Kombinationen Wirksamkeit in Bedeckung der BeispieleRangliste

Prädikatenlogische Mittel

prädikatenlogischer Ausdruck =

Literalsymbol, Prädikatsymbol,Funktionsymbol,

M = Greater_than( age( Mary ), x )

Konstantensymbol, Variablensymbol

Horn Clause

nLLH 1

KopfKörper

IF Parent(x,y) THEN Ancestor(x,y)

KopfKörper

Ergebnis Regel propositional:

Nachteil Propositionen: Keine Beziehung zwischen den Attributwerten

Lösung: Horn clause:

TrueFemaleBobNameBobFatherIF 121

TrueDaughterTHEN 2,1

1. Ordnungsregel

),()(),( yxDaughterTHENyFemalexyFatherIF

Induktive Logische Programmierung

innere Schleife des sequentiellen Bedeckalgorithmus:

(input: Prädikate, die auch in den Beispielen vorkommen, z.B Father, Female)

GrandDaughter(x,y) (ohne Vorraussetzung)

Regel:

Es wird nur nach Regeln für GrandDaughter(x,y)=True gesucht !

while (es werden noch negative Bindungen abgedeckt)

Kandidatenbildung:),(),(),,(),,(),,(),,(),,(),,( yFemalexFemaleyzFatherzyFatherxzFatherzxFatherxyFatheryxFather

).,(..),,( yxEqualBzwieNegationendieundyxEqual

Bewertung anhand der Beispiele

GrandDaughter(x,y) bisherige Regel bester Kandidat

Ergebnis: )(),(),(),( yFemalexzFatherzyFatheryxterGrandDaugh

Algorithmus zur induktiven logischen Programmierung

Eingabe: (Ziel_Prädikat, Prädikate, Beispiele)

Prädikate: Prädikatsnamen, wie sie auch in den Beispielen vorkommen, hier also Father, Female

Beispiele: Beispielprädikate mit Konstanten z.B.

GrandDaughter(Victor, Sharon) Father(Sharon, Bob) Father(Tom, Bob)Female(Sharon) Father(Bob, Victor)

),( yxterGrandDaugh

Victor, Sharon, Bob, Tom 16 Kombinationen mit x,y

1 positive Bindung: SharonyVictorx /,/

StartRegel: die reine Nachbedingung (am allgemeinsten)

15 negative Bindungen

Bilanz:

Closed World Assumption:alles was nicht explizit wahr ist,ist falsch.

Dies führt zu negative Bindungen von x, y

),( VictorVictorterGrandDaugh),( BobVictorterGrandDaugh),( TomVictorterGrandDaugh

),( VictorSharonterGrandDaugh),( SharonSharonterGrandDaugh

),( BobSharonterGrandDaugh),( TomSharonterGrandDaugh

),( VictorBobterGrandDaugh),( SharonBobterGrandDaugh

Implizite negative Beispiele:

),( BobBobterGrandDaugh),( TomBobterGrandDaugh

),( VictorTomterGrandDaugh),( SharonTomterGrandDaugh

),( BobTomterGrandDaugh),( TomTomterGrandDaugh

),( yxterGrandDaugh

Die Regel

bedeckt auch diese negativen Beispiele !(Denn sie besagt: „ Alle sindEnkelin von allen, auch von sich selbst“) d.h. die Regel sagtz.B. Victor ist Enkelin von Victor, dies ist aber wegen der Closed World Assumptionnicht wahr. -> Spezialisierung mussweitergehen

nächster Schritt:

Bisher vorkommende („alte“) Variablen:

Neue Regel = Alte Regel ^ neues Literal

Neue Variablenmenge (mit einer ergänzten Variable):

x, y, z

Kandidatenbildung für neues Literal: - Alle möglichen Kombinationen der Prädikate (von der Eingabe) sowie equals mit den Variablen aus der Variablenmenge. - Dabei muß in der Variablenliste jedes Kandidatenliterals mindestens ein Variable, die schon in der Regel existiert ! vorkommen (bei equals nur Variablen die schon in Regel existieren) ! - Dazu kommen alle Negationen dieser neuen Literale !

Prädikate der Eingabe: Father, Female

Alle möglichen Kombinationen:Father(x,y) Father(x,z) Father(y,x)Father(y,z)Father(z,x)Father(z,y)

Female(x)Female(y)Female(z)

equals(x,y)equals(x,z)equals(y,x)equals(y,z)equals(z,x)equals(z,y)

identisch

Bewertung der Kandidaten:

),(),( yxFatheryxterGrandDaugh

16 Möglichkeiten der Bindung der 4 Konstanten an x,y

Keine positive Bindung !

),(),( zyFatheryxterGrandDaugh

43 Möglichkeiten der Bindung der 4 Konstanten an x,y,z

)(),( yFemaleyxterGrandDaugh

42 Möglichkeiten der Bindung der 4 Konstanten an x,y

Eine positive Bindung !

Zwar gibt es 43 Möglichkeiten der Bindung der 4 Konstanten an x,y,zaber nach wie vor 1 positives Beispiel für das Zielprädikatund 15 negative Beispiele für das Zielprädikat.

Auswahl des Literals „Father(y,z)“

Durch Hinzunahme des Literals „Father(y,z)“ wird die Anzahlbedeckter negativer Beispiele des Zielprädikats geringer:Es gelten nur GrandDaughter Beispiele, die als zweiten Parameter dieselbe Person haben, wie ein Father Prädikat als erste Person !

(Es darf immer noch x==y und/oder x==z und/oder y==z sein)

Es gibt zwei Father Beispiele: Father(Sharon,Bob), Father(Tom,Bob)positive Belegung:

),(),( BobSharonFatherSharonVictorterGrandDaugh

negative Belegungen

),(),( BobTomFatherTomBobterGrandDaugh

d.h. es existiere nur noch zwei negative Belegungen

),(),( VictorBobFatherBobVictorterGrandDaugh

GrandDaughter(Victor, Sharon) Father(Sharon, Bob) Father(Tom, Bob)Female(Sharon) Father(Bob, Victor)

Beste Hypothese:

Kandidatenbildung für neues Literal:- Alle Literale aus dem vorherigen Schritt- zusätzlich:

Neue Variablenmenge (mit einer ergänzten Variable):

x, y, z, w

Father(z,w)Father(w,z)Father(y,w)Father(w,y)Father(x,w)Father(w,x)

Female(z) equal(z,x)equal(z,y)

Nächste Iteration:

),(),(),( wzFatherzyFatheryxterGrandDaugh

Neue Hypothesen:

u.s.w.mit „alten“ Literalen

),(),(),( yxFatherzyFatheryxterGrandDaugh

),(),(),( zxFatherzyFatheryxterGrandDaugh

),(),(),( xyFatherzyFatheryxterGrandDaugh

u.s.w.

),(),(),( xzFatherzyFatheryxterGrandDaugh

Es gibt nur ein Femal Beispiele: Female(Sharon)

positive Bedeckung:)(),(),( SharonFemalBobSharonFatherSharonVictorterGrandDaugh

negative Bedeckung:

d.h. es existiert keine negative Belegung: Learn One Rule bricht ab, keine weitere Spezialisierung derVorbedingung

Beste Hypothese

Es werde „Female(y)“ gewählt

Für die echte Regel fehlt es an Beispielen

Herausfinden der besten Kandidaten

12 loglog),(_

ptRLGainFoil

p = Zahl positiver bedeckter Beispiele, n= Zahl negativer bedeckter Beispiele0 = vor Erweitern der Regel um Literal L, 1= nach Erweitern der Regelt = Zahl der positiven Bindungen der Regel R die noch bedeckt werden, nachdem L hinzugefügt wurde

Foil_Gain = Verminderung notwendiger Bits um positive Bindungen von R zu kodieren.

Bewertung der Kandidaten:

),( yxterGrandDaughR =

Kandidaten für L

),(),( yxFatheryxterGrandDaugh p0=1 n0=15

neues R z.B. (mit Father(x,y))

4 mögliche Konstanten: Victor, Sharon, Bob, Tom

p0 n01 15

p1 n1 t Gain(L,R)Father(x,y) 0 16 0 #ZAHL!Father(x,z) 0 64 0Father(y,x) 0 16 0Father(y,z) 1 63 1 -2Father(z,x) 0 64 0Father(z,y) 0 64 0Female(x) 0 16 0Female(y) 1 15 1 0equals(x,y) 0 16 0

Negationen binden nur negative Beispiele

Übung zur induktiven logischen Programmierung-- zum Selberrechnen - versuchen Sie‘s selbst

)(),(),(),( xWeiblichzxKindyzSchwesteryxNichte

)();,(

);,();,(

SusanneWeiblichSusannePaulaKind

ElfriedeSusanneSchwesterElfriedPaulaNichte

Eine Anwendung des maschinellen Lernens:Data Mining- Schürfen im Datenbergwerk

Data Mining

Entdeckung vonMustern

Vorhersage

Suche nach Besonderheiten

Wenn Dann Regeln

Zusammenhänge

Trends

Suche nach Informationsmustern in Daten

Zwei unterschiedliche Strategien

logisch

Gleichungen

Daten werden„destilliert“

Data bleibenerhalten

Nächster Nachbar

Entscheidungsbaum

Induktion von Regeln

Statistik

Neuronale Netze

Nächster Nachbar Methode

Vorhersage von Eigenschaften

Beispiel: Ist ein neuer Bankkunde eventuell an Aktienfonds interessiert ?

Attribute von vorhandenem Kunden werden mit Attributen von neuem Kunden verglichen

Hat „ähnlichster“ Alt-Kunde Aktienfonds ?

Werbematerial nicht zusenden.

Werbematerial zusenden.

Ja Nein

Speicheraufwand! -> Datensatz auf Typische einschränken

logisch

Gleichungen

Daten werden„destilliert“

Data bleibenerhalten

Nächster Nachbar

Entscheidungsbaum

Induktion von Regeln

Statistik

Neuronale Netze

Entscheidungsbaum

Beispiel:Wann ist der Gewinn einer deutsche Firma im Ausland hoch ?

Entscheidungsbaum

Land Hersteller Produkt Farbe Gewinn China Schmidt blau Hoch

Japan Schmidt grün Niedrig Niederlande Alberts blau Hoch Japan Alberts rot Niedrig Niederlande Jung grün Mittel China Jung rot Mittel

Start Niederlande

Mittel

Alberts

Jung Mittel

Niedrig

Schmidt

Entscheidungsbaum

Problem:In welcher Reihenfolge werden die Attribute angewandt ?

Start grün Japan

Niederlande Mitt

Niedrig

China Mitt

Niedrig

Induktion als invertierte Deduktion

Nur Regeln erzeugen, die auf Beispiele passen

)()( ii xfhxB

CCC 21

B: Hintergrundwissenh: Hypothesexi: Beispiel

f: Zielprädikat

LLCCC ))(( 12

Konstruktion von C2

Erklärungsbasiertes Lernen

Jedes Beispiel wird anhand von Hintergrundwissen mit Blickauf das Zielkonzept erklärt.

z.B. es ist sicher x auf y zu stapeln, da y nicht zerbrechlich ist Beispiel: Glas auf einen Holzklotz zu stapeln ist sicher. Holzklotz ist nicht zerbrechlich. Holzklotz ist braun.

Mit dieser Erklärung werden die relevanten von den nicht relevantenEigenschaften getrennt.

Mit Hintergrundwissen wird der Hypothesenraum deduktiv verringert

„Domänentheorie“: SafeToStack x y Fragile y( , ) ( )

SafeToStack x y Lighter x y( , ) ( , )

Lighter x y Weight x wx Weight y wy LessThan wx wy( , ) ( , ) ( , ) ( , )

Weight x w Volume x v Density x d Equal w times v d( , ) ( , ) ( , ) ( , ( , ))

Weight x Type x Endtable( , ) ( , )5

Fragile x Material x Glass( ) ( , )

On(Obj1,Obj2) Owner(Obj1,Fred)

Type(Obj1,Box) Owner(Obj2,Louise)

Type(Obj2,Endtable) Density(Obj1,0.3)

Color(Obj1,Red) Material(Obj1,Cardboard)

Color(Obj2,Blue) Material(Obj2,Wood)

Volume(Obj1,2)

positives Beispiel:

Zielkonzept: SafeToStack(x,y)

SafeToStack(Obj1, Obj2)

=Hintergrundwissen

Konstanten groß geschriebenVariablen klein geschrieben

Anwendung von PROLOG

Das Beispiel wird aus dem Hintergrundwissen erklärt

Das Zielkonzept wird (irgenwie) aus den anderen Prädikaten des Beispiels deduktiv abgeleitet

Erklärungsbaum

SafeToStack(Obj1,Obj2)

Lighter(Obj1,Obj2)

Weight(Obj1,0.6) Weight(Obj2,5)

Volume(Obj1,2) Density(Obj1,0.3) Equal(0.6,2*0.3) LessThan(0.6,5) Type(Obj2,Endtable)

Prolog

),()3.0,()2,(),( EndtableyTypexDensityxVolumeyxkSafeToStac

Verallgemeinerung

•Durchgehen des Erklärungsbaums von der Wurzel aus Ebene um Ebene

•Geltungsbereich der Variablen der Literale ausdehnen,

soweit es die Regeln der Domänen Theorie zulassen

SafeToStack(Obj1,Obj2)

Lighter(Obj1,Obj2)

Weight(Obj1,0.6) Weight(Obj2,5)

Volume(Obj1,2) Density(Obj1,0.3) Equal(0.6,2*0.3) LessThan(0.6,5) Type(Obj2,Endtable)

SafeToStack x y Volume x vx Density x dx( , ) ( , ) ( , )

Equal wx times vx dx LessThan wx( , ( , )) ( , ) 5

Type y Endtable( , )

Verallgemeinerung

Maschinelles Lernen

Lösung: Man fängt mit dem allgemeinsten Zielprädikat an,und spezialisiert pro „Regelkopf zu Regelkörper Schritt“ gerade nursoviel, wie irgend nötig.

Suchen nach dem Unifikator von zwei Prädikaten:

Term = Konstante; Variable; Funktion;

Wie kann man die Erklärungskette verallgemeinern ??

-> Unifikation von Regelkopf mit Regelkörper

Bsp.: abgeben(x,Geld) und abgeben(Otto,y) was ist das allgemeinste Prädikat „abgeben(v,w)“ das sich aus denobigen Prädikaten gerade noch ableiten läßt ??

Wenn man x durch Otto und y durch Geld ersetzt-> Unifikator = {Otto/x, Geld/y} -> abgeben(Otto, Geld)

Maschinelles Lernen

Variable x: Werte können aus dem gesamten Wertebereich kommenFunktion f(x): Werte kommen aus einem Teil des WertebereichsKonstante a: Ein Wert des Wertebereichs

Mögliche Ersetzungen bei denen P wahr bleibt:

P(x) zu P(f(x))P(x) zu P(a)P(x) zu P(y) wenn x und y aus der gleichen Wertemenge kommen

Ersetzungen, bei denen man nicht garantieren kann, das P wahr bleibt:

P(f(x)) zu P(a) a ist möglicherweise nicht in der Menge ,die durch die f(x) gebildet wird

g(x) und f(x) beschreiben nicht die gleiche MengeP(f(x)) zu P(g(x))

Maschinelles Lernen

_ _ _ _ _ _ ... _ _ _ _ _ _ ...

Position k = 1

Zeichen an Position k vergleichen - k weiterrücken bis Ende

Sobald verschiedene Zeichen:Wenn in C1 (bzw. C2) eine Variable an Position k beginnt, wirdsie durch den an k beginnende Term von C2 (bzw. C1) ersetzt

Position k = 1

Die Ersetzung wird in einer Liste vermerkt

Wenn verschiedene Zeichen, aber keine Variable => nicht unifizierbar

Maschinelles Lernen

Beispiele:

{P(x,f(z)), P(h(a),y)}

Unifikator: {h(a)/x, f(z)/y}

y wird durch f(z) ersetzt

{P(h(g(u))), P(g(h(x)))}

nicht unifizierbar

{P(x, f(a,b), h(a)), P(f(z,v),x,h(z))}Unifikator {f(a,b)/x, a/z, b/v}

{P(x, f(z,x), h(a)), P(f(a,b),x, h(x))}nicht unifizierbar

z, x, y Variablena, b Konstanten

SafeToStack(Obj1,Obj2)SafeToStack(x,y)

Ligther(Obj1,Obj2)Ligther(x,y)

Weight(Obj1,0.6)Weight(x,wx)

LessThan(0.6,5)LessThan(wx,wy)

Weight(Obj2,5)Weight(y,wy)

Weight(y,wy)LessThan(wx,wy)Equal(0.6,2*0.3)Equal(wx,vx*dx)

Density(Obj1,0.3)Density(x,dx)

Volume(Obj1,2)Volume(x,vx)

LessThan(wx,5)Equal(wx,vx*dx)Density(x,dx)Volume(x,vx)

Type(Obj2,Endtable)

Type(y,Endtable)

zugehörige Regel=

),(),( yxLighteryxkSafeToStac

Literal aus der Regel

Literal aus der „Frontlinie“

z.B. weight(x,w) aus )),(,(),(),(),( dvtimeswEqualdxDensityvxVolumewxWeight

z.B. weight(y,wy)

1. Schritt

zugehörige Regel=

),(),( yxLighteryxkSafeToStac

)2,1()2,1( ObjObjLighterObjObjkSafeToStac

Unifikation von Literal der Frontlinie mit Kopf der Regel :{x/x, y/y}

Kopf wird durch Regelkörper ersetzt: „Frontlinie“ wird verändert

Frontlinie: ),( yxLighter

Literal der Frontlinie: SafeToStack(x,y)

Ersetzung wird in der ganzen Frontlinie durchgeführt: nichts zu tun

2. Schritt

zugehörige Regel=

„Frontlinie“ erweitert: Literal wird durch Regelkörper ersetzt:

Frontlinie:

),(),(),(),( wywxLessThanwyyWeightwxxWeightyxLighter

)5,6.0()5,2()6.0,1()2,1( LessThanObjWeightObjWeightObjObjLighter

Literal der Frontlinie: ),( yxLighter

Unifikation von Literal der Frontlinie mit Kopf der Regel :{x/x, y/y}

),(),(),( wywxLessThanwyyWeightwxxWeight

Ersetzung wird in der ganzen Frontlinie durchgeführt: nichts zu tun

4. Schritt

zugehörige Regel=

„Frontlinie“ erweitert: Literal wird durch Regelkörper ersetzt:

),2()5,2( EndtableObjTypeObjWeight

Literal der Frontlinie: ),( wyyWeight

Unifikation von Literal der Frontlinie mit Kopf der Regel :{y/y, wy/5}

)5,()5,()*,(),(),( yWeightwxLessThandxvxwxEqualdxxDensityvxxVolume

Ersetzung wird in der ganzen Frontlinie durchgeführt:

),()5,( EndtableyTypeyWeight

),()5,()*,(),(),( EndtableyTypewxLessThandxvxwxEqualdxxDensityvxxVolume

2. Beispiel

abgeben(Mary, Geld); zeigtMitGewehrAuf(John, Mary); verlangtGeldVon(John, Mary)

zugehörige Domänentheorie:

),,()],(),([,

)],(),,(),([,,

GeldLebenysenXOderabgebenMüsyxldverlangtGeyxwehrAufzeigtMitGeyx

yzabgebenyxzsenXOderabgebenMüsyxmehrWertzyx

yLebenmehrWertTRUEy

„Schliess-Baum“abgeben( Mary , Geld)

mehrWert (Leben,Geld) abgebenMüssenXOder (Mary ,Leben,Geld)

zeigtMitGewehrAuf (John,Mary) verlangtGeld (John,Mary )

verallgemeinerter Ausdruck passende Regel (laut „Schliess-Baum“)

abgeben(x,y) mehrWert(x‘,y‘)abgebenMüssenXOder(z‘,x‘,y‘) abgeben(z‘,y‘)

Unifikation des Regelkopfs mit dem verallgemeinerter Ausdruck :(das allgemeinere wird durch das speziellere ersetzt. x und x‘ sind gleich allgemein, y und y‘auch -> es ist egal wie ersetzt wird, nur es muss AUCH in der LiteralFront ersetzt werden !!) {neu / alt}

{x/z‘, y/y‘} unifizierte Regel: mehrWert(x‘,y)abgebenMüssenXOder(x,x‘,y) abgeben(x,y)

„Front der Literale“

mehrWert(x‘,y)abgebenMüssenXOder(x,x‘,y) abgeben(x,y)

ersetzen von Literalen mitHilfe von Regeln

verallgemeinerter Ausdruck

mehrWert(x‘,y)

passende Regel (laut „Schliess-Baum“)

TRUE mehrWert(Leben,x‘‘)

Unifikation des Regelkopfs mit dem verallgemeinerter Ausdruck :(Leben ist spezieller als x‘, y und x‘‘sind gleich allgemein)

{Leben/x‘, y/x‘‘} unifizierte Regel: TRUE mehrWert(Leben,y)

„Front der Literale“ (nach Unif. und ersetzen des Literals durchden Regelkörper)

ersetzen von Literalen mitHilfe von Regeln

TRUEabgebenMüssenXOder(x,Leben,y) abgeben(x,y)

verallgemeinerter Ausdruck passende Regel (laut „Schliess-Baum“)

abgebenMüssenXOder(x,Leben,y) zeigtMitGewehrAuf(x‘‘‘,y‘‘‘) verlangtGeld(x‘‘‘,y‘‘‘) abgebenMüssenXOder(y‘‘‘,Leben,Geld)

Unifikation des Regelkopfs mit dem verallgemeinerter Ausdruck :(das allgemeinere wird durch das speziellere ersetzt. y‘‘‘ und x sind gleich allgemein, Leben undLeben sind gleich (sonst wäre gar keine Unifikation möglich, denn beides sind Konstanten !), Geld istspezieller als y ) {neu / alt}

{x/y‘‘‘, Geld/y} unifizierte Regel: zeigtMitGewehrAuf(x‘‘‘,x) verlangtGeld(x‘‘‘,x) abgebenMüssenXOder(x,Leben,Geld)

„Front der Literale“ (nach Unif. und ersetzen des Literals durchden Regelkörper)

TRUE zeigtMitGewehrAuf(x‘‘‘,x) verlangtGeld(x‘‘‘,x) abgeben(x,Geld)

Keine weiteren Regeln mehr im „Schliess-Baum“

TRUE kann weggelassen werden, wegen UND Verknüpfung

zeigtMitGewehrAuf(x‘‘‘,x) verlangtGeld(x‘‘‘,x) abgeben(x,Geld)

Aus dem Beispiel gelernte Regel lautet:

© Prof. Dr. H. Gläser, Künstliche Intelligenz Automatisierung des Lernens

Documents

Wolfgang´s Powerpoint Präsentation Zwei Gläser gefüllt

Künstliche Intelligenz

INTELLIGENTE ROBOTIK UND KÜNSTLICHE … IST „ROBOTIK UND KÜNSTLICHE INTELLIGENZ“ ? “ Robotik und Künstliche Intelligenz ist die Wissenschaft von der Erforschung intelligenter

Prinzip kooperativen Lernens Nach Brüning/Saum. Prinzip kooperativen Lernens Denken (Think) Austauschen (Pair) Vorstellen (Share)

LEARNTEC 2020 | 28. Internationale Fachmesse und Kongress · DENK DIGITAL „Die Zukunft des Lernens, Künstliche Intel - ligenz, Modern Workplace Learning – das sind Themen, die

Künstliche Wasseradernkreuzung IIa

Einführung in die Künstliche Intelligenz - Informatik · Vorlesung: Künstliche Intelligenz Fachbereich Mathematik/Informatik –AG Künstliche Intelligenz 1) Definition und Geschichte

Emotionale Voraussetzungen des Lernens

IBM Speicherkonzepte für Künstliche Intelligenz · 2019-12-18 · 6 IBM – Speicherkonzepte für Künstliche Intelligenz IBM – Speicherkonzepte für Künstliche Intelligenz 7

Ihre Traumhochzeit - saentisbahn.ch¼re.pdf · Komplett (mit Gläser) pro Person 8.00 Apérogedeck (Gläser, Papierservietten, kleiner Teller) pro Person 2.50 Kaffeegeschirr (Tasse,

Künstliche Besamung Fleischrind

Farbprogramm organische Gläser - nkungen... · PDF fileFarbprogramm organische Gläser Suntints – Physio Tint technology // Modefarben keine Einschränkung nicht nachtfahrtauglich

Andreas Gläser - Pauschal ins Paradies

Aspekte des Maschinellen Lernens

Künstliche Neuronale Netze

Während des Lernens

Einführung in die Künstliche Intelligenz · ... Einführung in die Künstliche Intelligenz Einführung in die Künstliche Intelligenz Homepage

Saubere Gläser ein Duschenleben lang! - artweger.at · Saubere Gläser ein Duschenleben lang! Normales Glas ARTCLEAR GLAS ARTCLEAR GLAS ist ein neues, dauerhaft pﬂ egeleichtes

Vorlesung: „ Künstliche Intelligenz · SSAA SSVV. Vorlesung Künstliche Intelligenz Fachbereich Mathematik/Informatik – AG Künstliche Intelligenz Inhaltliche Planung für die

Sonya Baum, Ulrich Gläser, Nicole Klukas, Ursula Stahl