Wo stehen wir?

Wo stehen wir?

Lernverfahren: Top Down Induction of Decision Trees Begriffslernen kNN “ SVM “ Least general generalization “ Generalisierte -Subsumtion “– RDT, RDT/dm Regellernen– STT Lernen eines Verbands Apriori Finden häufiger Mengen FPgrowth “ Winepi (zeitlich) “ K-Means Clustering

Induktive Logische Programmierung

Bisher nur (gewichtete) Attribute – zur Beschreibung der

Beispiele (LE)– zur Beschreibung der

Begriffe (LH) Ausführbar ist das

Lernergebnis nur als Entscheidungsfunktion für das Erkennen.

Hintergrundwissen kann nur in der Vorverarbeitung z.B. durch gezieltes Sampling einbezogen werden.

Relationen und Beziehungen zwischen Relationen können nicht durch Attribute ausgedrückt werden.

Logische Programme können Entscheidungsfunktionen ausdrücken und mehr.

Auch Hintergrundwissen kann in logischen Programmen ausgedrückt werden.

Formulieren mit Attributen

Prinzipiell können Relationen bei einem endlichen Universum als Attribute formuliert werden, aber– unübersichtlich, schwer zu lesen– man kann dann nicht auf Relationen Bezug nehmen.

Attribute: mutter_bettina, mutter_berta, mutter_carla, mutter_christa,... gattin_doris, gattin_carla, gattin_christa... mutter_carla=gattin_carla?

bettina

carlos carla

dieter

berta

christa christoph

doris

Induktive Logische Programmierung ILP -- Vorteile

Relationen aus Datenbanken können direkt als logische Relationen genutzt werden.

ILP lernt logische Programme mit bestimmten Beschränkungen, d.h.– LH ist eine eingeschränkte Prädikatenlogik.

Lernen erhält eine wohl definierte Semantik. Hintergrundwissen kann einbezogen werden.

Anwendungen

Planung Robotik (Beziehung zwischen Wahrnehmung und

Handlung) Telekommunikation: Sicherheitsstrategien für den

Zugriff in offenen, verteilten Systemen Spracherwerb: Grammatiken können als logisches

Programm geschrieben werden. Bioinformatik: Beziehung zwischen chemischer

Struktur und Wirkung von Medikamenten Ingenieurswesen: Finite Element Mesh Design

Lernen als Suche

Spezialisieren, so dass negative Beispiele ausgeschlossen sind

Generalisieren, so dass positive Beispiele abgedeckt werden

Ordnung des Hypothesenraums ermöglicht sicheres Beschneiden:

Wenn C bereits ein positives Beispiel ausschließt, kann auch keine Spezialisierung von C dies Beispiel abdecken.

Wenn C bereits ein negatives Beispiel abdeckt, so kann auch keine Generalisierung von C dies Beispiel ausschließen.

Induktion als inverse Deduktion

Deduktion

Klausel:

mutter(X,Y) mutter(Y,Z) oma(X,Z)

Fakten:

mutter(doris, christa)

mutter(christa, berta)

Ableitung:

X\doris, Y\christa, Z\berta

oma(doris, berta)

InduktionBeispiele:mutter(doris, christa),

mutter(christa, berta), oma(doris, berta)

¬oma(christa,doris)mutter(detlef, carla),

mutter(carla, bettina), oma(detlef, bettina)

¬oma(bettina,carla) ...Lernergebnis:mutter(X,Y) mutter(Y,Z)

oma(X,Z)

ILP Lernaufgabe Begriffslernen

Gegeben positive und negative Beispiele E=E+ E- in einer Sprache LE, Hintergrundwissen B in einer Sprache LB, wobei B H nicht widersprüchlich ist,

Finde eine Hypothese H in einer Sprache LH, so dass– B, H, E sind widerspruchsfrei (Konsistenz)– B,H |= E+ (Vollständigkeit)– für kein e in E- gilt: B,H |= e (Korrektheit)

LH ist (eingeschränkte) Prädikatenlogik.

Logik

Deduktion: logische Folgerung durch Ableitung modelliert.

Hornlogik Eine Formel C ist eine Hornformel, wenn C in konjunktiver

Normalform ist und jedes Disjunktionsglied (Klausel) höchstens ein positives Literal enthält.C= (A v ¬B) (D v ¬A v ¬C) (¬A v ¬B) D ¬E (BA) (A C D) (A B f) (wD) (Ef) {A , ¬B} {D, ¬ A, ¬ C} {¬ A, ¬ B} {D} {¬E}

Eine Methode für die Ableitung in Hornlogik ist die Resolution.

Resolution Seien C1, C2 Klauseln. R ist Resolvent von C1 und

C2, wenn es ein Literal L in C1 gibt, dessen Negation in C2 ist. R=(C1-{L}) (C2-{L}).

Widerspruchsbeweis einer Aussage A durch Hinzufügen von deren Negation zu den bekannten Aussagen und Ableitung der leeren Aussage per Resolution.

C1= {A v B} C2= {B v C} C3={C}

L= B, L=B

R= {A v C} {C}

{A} {A}

Unifikation

Wenn das Literal, das herausgeschnitten werden soll, noch Variablen enthält, müssen diese erst so substituiert werden, dass L und ¬L bis auf das Vorzeichen gleich sind.

Nicht zu stark spezialisieren:

{p(X), ¬q(g(X))} {¬p(f(Y))} Klauseln variablendisjunkt!

X\f(Y) Unifikation zu p(f(Y))

{¬q(g(f(Y)))} nicht schon Y\a substituieren!

Unifikationssatz (Robinson): Jede unifizierbare Menge von Literalen besitzt auch einen allgemeinsten Unifikator.

Allgemeinster Unifikator (mgu)

Eine Substitution ist ein Unifikator einer endlichen Menge von Literalen L={L1, L2,...,Lk} gdw. L1=L2=...=Lk.

Ein Unifikator heißt allgemeinster Unifikator von L, wenn für jeden anderen Unifikator 1 von L gilt, dass es eine Substitution 2 gibt, so dass L2 = L1

{p(X), ¬q(g(X))} {¬p(f(Y))} = {X\f(Y)}

{¬q(g(f(Y)))} 1 ={X\f(Y), Y\a}

{¬q(g(f(a)))} 2 ={Y\a}

Unifikatoren

Die Unifikatoren sind nach Allgemeinheit geordnet. Dadurch sind auch unifizierbare Literale nach

Allgemeinheit geordnet:Das größte gemeinsame Unterelement (Infimum) von L1 und L2 ist L1 = L2 , wobei der mgu ist.

{L1, L2}

= j= i

L1 =L2

j

i

Unifikationsalgorithmus

Gegeben eine Menge L von Literalen.:={}while |L|>1 do

Suche in den Literalen in L von links nach rechts nach der ersten Position, an der zwei Literale sich unterscheiden.Wenn an der Position keine Variable steht, stop “nicht unifizierbar”. SonstWenn X die Variable und t der im anderen Literal beginnende Term ist,

wenn X in t vorkommt, stop “nicht unifizierbar”,

sonst := {X\t}

Beispiel

L={¬p(f(Z,g(a,Y)),h(Z)), ¬p(f(f(U,V),W),h(f(a,b)))} :={Z\f(U,V)}

L={¬p(f(f(U,V),g(a,Y)),h(f(U,V))), ¬p(f(f(U,V),W),h(f(a,b)))} :={Z\f(U,V),W\g(a,Y)}

L={¬p(f(f(U,V),g(a,Y)),h(f(U,V))), ¬p(f(f(U,V),g(a,Y)),h(f(a,b)))}

:={Z\f(U,V),W\g(a,Y), U\a}

L={¬p(f(f(U,V),g(a,Y)),h(f(a,V))), ¬p(f(f(U,V),g(a,Y)),h(f(a,b)))}

:={Z\f(U,V),W\g(a,Y), U\a, V\b}

L={ ¬p(f(f(U,V),g(a,Y)),h(f(a,b)))} |L|

Verband der Atome bzgl. Allgemeinheit1.Schritt: Unifikation

Sei A eine Menge von Atomen, dann gibt es für alle A, B in A ein größtes gemeinsames Unterelement G(A,B).

Wenn A oder B {} sind, ist G(A,B)={}. Wenn A all ist, ist G(A,B)=B, wenn B {} ist, ist G(A,B)=A.

Wenn A und B nicht unifizierbar sind, ist G(A,B)={}. Wenn A und B unifizierbar sind durch mgu , dann ist

G(A,B)=A=B.Nienhuys-Cheng, de Wolf (1997)

“Foundations of Inductive Logic Programmming”, Springer

Was wissen wir jetzt?

Ausdruckskraft: ILP hat als Hypothesensprache LH eine eingeschränkte Prädikatenlogik (logisches Programm).

Ausführbarkeit: Logische Programme sind ausführbar und nicht auf eine Erkennungsfunktion beschränkt. Lernergebnis kann in andere Klauseln eines Programms direkt eingebettet werden.

Die Lernaufgabe des Begriffslernens beinhaltet Hintergrundwissen.

Unifikation spezialisiert, der mgu liefert das Infimum im Verband der Atome.

Generalisierung

Wir suchen eine Hypothese, so dass H |= E+, verwenden also zum Prüfen die logische Folgerung.

Die Suche soll in einem nach Allgemeinheit geordneten Raum erfolgen.

Wann ist eine Formel allgemeiner als eine andere?– Implikation

– Subsumtion

Generalisierung: Implikation

Genereller als:Eine Hornklausel D ist genereller als eine andere, C, gdw.D C

D ist genereller als C bezüglich B, gdw.

B, D C Äquivalenz:

Sei B eine Konjunktion von Hornklauseln, dann sind die Klauseln D und C logisch äquivalent bzgl. B gdw.

B, D C und B, C D Redundanz :

Ein Literal L ist redundant in einer Klausel C bzgl. B gdw.

C und C \ {L} sind äquivalent bzgl. B.

Beispiel Generalisierung

B: {append ([ ], C, C)}

C: {append ([1,2], [3], [1,2,3])}

D: {¬ append (B, C, E), append( [A | B], C, [A | E])}

D, B C

¬ append ([1,2], [3], [1,2,3]).

¬ append ([2 | [] ], [3], [2,3]).

¬ append ( [ ], [3], [3]).

append ( [A | B], C, [A | E]) , ¬ append (B, C, E).

{A/1, B/[2], C/[3], E/[2,3]}

append ( [A | B], C, [A | E]) , ¬ append (B, C, E).

{A/[2], B/ [], C/ [3], E / [3]}

append ([ ], C, C).

{C / [3]}

Beweis von C mithilfe von B und D

Beispiel Redundanz

B: {member( X, [ X| Y])} C: {member ( X, [ Y|Z]), ¬member (X, Z), ¬member( Y, (Y |Z]). C': C \ {¬member( Y, (Y | Z])} ist äquivalent zu C bzgl. B.

B, C C' und B, C' C B beschreibt den Fall, dass das Element am Anfang

der Liste steht. C' beschreibt den Fall, dass das Element im Rest der

Liste steht. C beschreibt beide Fälle.

Nachteile

Um für eine Menge von Beispielen die Generalisierung zu finden, müssen wir die Klausel(n) finden, die alle Beispiele impliziert!Dies ist zu aufwendig! (Semi-Entscheidbarkeit der logischen Folgerung in der Prädikatenlogik.)

Der Hypothesenraum ist nicht so strukturiert, dass bei jedem Generalisierungsschritt der Ausschnitt der erreichbaren Hypothesen kleiner wird.

Also ist die Implikation als Generalisierungsbeziehung nicht geeignet.

Generalisierung: Subsumtion

Eine Hornklausel D ist genereller als eine andere, C, gdw.D subsumiert C.– Ein Literal L1 subsumiert ein Literal L2 gdw.

L1 = L2.– Eine Klausel D subsumiert eine andere, C, gdw.

D C

Die Subsumtion ist eine korrekte, aber nicht vollständige Ableitung, d.h.„C1 subsumiert C2“ |= „C1 impliziert C2“, aber nicht umgekehrt.

Beispiel Generalisierung

D: {member ( X, [ Y| Z]), member(X,Z)}C: {member ( 3, [1,2,3]), member(3, [2,3]), member(3, [3])}: { X/3, Y/1, Z/ [2,3] }

Dkopf = member (3, [1 | [2,3]) = Ckopf

Dkörper = member (3, [ 2, 3]) Ckörper

Nicht alles, was unter der Implikation eine Generalisierung ist,ist es auch unter der Subsumtion!B: {append ([ ], C, C)}D: {append( [A | B], C, [A | E]), append (B, C, E)}C: {append ([1,2], [3], [1,2,3])}B, D C aberD subsumiert nicht C, denn hier kann Generelleres nicht länger sein

als Generalisiertes. Die Subsumtion berücksichtigt B nicht.

echt genereller

Zwei Klauseln D und C sind äquivalent, wenn gilt:

D subsumiert C und C subsumiert D.

Eine Klausel D ist echt genereller als eine andere, C, gdw.

D subsumiert C und D ist nicht äquivalent C.

Redundanz

Ein Literal L in der Klausel C ist redundant, wenn gilt:C subsumiert C \ {L}.

Eine Klausel heißt reduziert, wenn sie keine redundanten Literale enthält.

Algorithmus, der eine Klausel C reduziert (Plotkin):1. Initialisiere D mit C.2. Finde ein Literal in D und eine Substitution , so dass

D D \{L}.Gelingt dies nicht, STOP.

3. D:= D, gehe zu 2. Die reduzierte Form einer Klausel ist eindeutig.

Beispiel Redundanz

C1: {member(X, [Y | Z ]), member(X, Z), member (X, U)}

={U/Z}

C1 C1' \ { member (X, U) }

C1 : {member(X, [Y | Z ]), member(X, Z)} =

C1 \ { member (X, U)}: {member(X, [Y | Z ]), member(X, Z)}

Vor-/ Nachteile

Vorteil:Der Hypothesenraum wird schrittweise eingeschränkt.

Nachteile:– Hintergrundwissen wird nicht berücksichtigt.

– Die Reduktion ist exponentiell in der Anzahl der Literale (alle möglichen Teilmengen der Klausel müssen gebildet werden).

Least General GeneralizationGordon Plotkin

LGG (C1, C2): Für alle Paare von Literalen L1i C1, L2i C2,

suche die mit gleichem Prädikatensymbol und gleichem Vorzeichen heraus --

bilde LGG ( L1i , L2i )

Die Generalisierung von C1 und C2 ist die Vereinigung aller generalisierten Literale.

Aus dieser Generalisierung werden alle redundanten Literale entfernt.

Generalisierung von LiteralenAnti-Unifikation

Zwei Literale mit demselben Prädikatsymbol und Vorzeichen

p(s1, ..., sn) p (t1, ...., tn) von links nach rechts durchgehen

LGG (si, ti) = X, falls si, ti konstante Terme oder Variablen ungleich X sind;

LGG (f(s1, ..., sn), f(t1, ..., tn)) = f ( LGG(s1, t1), ..., LGG(sn, tn) )

LGG (f(s1, ..., sn), g(t1, ..., tm)) = X

Beispiel

L1: unterhalt (ulf, maria, alimente(ulf, 1000))

L2: unterhalt(udo, marion, alimente(udo,300))

LGG(L1, L2): unterhalt (X, Y, alimente(X, V))

1:{X\ulf, Y\maria, V\1000}

2:{X\udo, Y\marion, V\300}

Für jede andere Generalisierung G(L1, L2) gibt es eine

Substitution, so dass G(L1, L2) = LGG(L1, L2).

Verband der Atome bzgl. Allgemeinheit 2. Schritt: Anti-Unifikation

Sei A eine Menge von Atomen, dann gibt es für alle A, B in A ein kleinstes gemeinsames Oberelement LG(A,B).

Wenn A oder B all sind, ist LG(A,B)=all. Wenn A {} ist, ist LG(A,B)=B, wenn B {} ist, ist LG(A,B)=A.

Wenn A und B verschiedene Prädikatensymbole haben, ist LG(A,B)=all.

Wenn A und B gleiche Prädikatensymbole haben, dann ist LG(A,B)=LGG(A,B).

Nienhuys-Cheng, de Wolf (1997) “Foundations of Inductive Logic Programmming”, Springer

Beispiel Unifikation, Anti-Unifikation

A=p(a,X,f(X)) B=p(Y,f(b),f(f(b)))

LG(A,B)=p(Z1,Z2,f(Z2))

G(A,B)=p(a, f(b), f(f(b)))

LGG (C1, C2)

C1: {member(2, [1,2]), ¬member (2, [2])}

C2: {member (c, [a, b, c]), ¬member(c, [b,c]), ¬ member (c, [c])}

alle Paare:[¬ m(2, [2]), ¬ m(2, [2]), ¬m(2, [2]), m(2, [1,2]), m(2, [1,2]), m(2, [1,2]) ]

[¬ m(c, [b,c]), ¬ m((c, [c]), m(c, [a, b, c]), ¬m(c, [b,c]), ¬m((c, [c]), m(c, [a, b, c]) ]

LGG ( ¬m(2, [2]), ¬m(c, [b,c]) ) = ¬m(A, [C|D])LGG ( ¬m(2,[2]), ¬m(c, [c]) ) = ¬m(A, [A])LGG ( m(2, [1,2]), m(c, [a, b, c]) ) = m( A, [B, C|D])

LGG (C1, C2) = {m( A, [B, C|D]), ¬m (A, [C|D]), ¬m (A, [A]).Bei jedem Literal probieren, ob es weggelassen werden kann, ohne zu generalisieren. Dieser Schritt ist leider NP-schwierig, weil der Subsumtionstest NP-schwierig ist.

Eigenschaften des LGG

kommutativlgg ( e1, e2 ) = lgg ( e2, e1 )

assoziativlgg ( lgg ( e1, e2 ), e3) = lgg ( e1, lgg ( e2, e3 ) )

idempotentlgg ( e, e ) = e

Das bedeutet auch: reihenfolgeunabhängiglgg ( e1, e2, ..., en ) = lgg ( ... lgg ( lgg ( e1, e2 ), e3 ), ... en)

und eindeutig. In einem Verband von Äquivalenzklassen von Klauseln

ist das Supremum zweier Klauseln ihr LGG.

Aufwand

Die gute Nachricht: Die Länge des LGG ist linear in der Anzahl der Selektionen. Der Aufwand der Generalisierung ist linear in der Anzahl der

Selektionen.

Die schlechte Nachricht: Hat die längste Klausel in den Beispielen m Literale und

gibt es n Klauseln als positive Beispiele, dann gibt es höchstens mn Selektionen.

Es werden also exponentiell viele Selektionen in linearer Zeit bearbeitet.

Und dann kommt die Reduktion, die für jedes Literal noch einmal den aufwändigen Subsumtionstest braucht...

Was wissen wir jetzt?

Wir wollten eine Allgemeinheitsordnung zwischen Klauseln, um Lernen als Suche zu modellieren.– Über die Implikation war die Ordnung zu aufwändig.– Über die Subsumtion ist die Allgemeinheitsordnung

gegeben. Wir haben den Verband über den Literalen (bzw.

Atomen) vervollständigt:– das Infimum zweier Atome ist über die Unifikation

gegeben– das Supremum zweier Atome ist über die Anti-

Unifikation gegeben. Der lgg ist ein Operator, der die Subsumtion für die

Generalisierung ausnutzt.

Hintergrundwissen

Einer der Vorteile von ILP sollte die Berücksichtigung von Hintergrundwissen sein.

Bisher haben wir – aus zwei positiven Beispielen deren Generalisierung

gelernt,

– entschieden, ob eine Klausel genereller als eine andere ist.

Jetzt wollen wir entscheiden, ob eine Klausel bzgl. Hinergrundwissen allgemeiner ist als eine andere.

HintergrundwissenB: haustier (X), tier(X), im_haus (X)

D: kuscheltier (Z), flauschig (Z), tier (Z), im_haus (Z).

C: kuscheltier (Y), flauschig (Y), haustier (Y).

D ist genereller als C, denn B, C |- D

B: C:

haustier, ¬ tier, ¬ im_haus kuscheltier, ¬ flauschig, ¬ haustier

D:

kuscheltier, ¬ flauschig, ¬ tier, ¬ im_haus

Semantik

D ist genereller als C bzgl. B, wenn in jeder Interpretation I, die B wahr macht, für alle Atome A gilt:

wann immer C auf A zutrifft, trifft auch D auf A zu.

Subsumtion bzgl. HintergrundwissenPlotkin

D ist genereller als C bezüglich einer Theorie B, gdw.

B, D |-- Cwobei D in der Ableitung höchstens einmal vorkommt.

B: kuscheltier (X), ¬flauschig (X), ¬klein (X), ¬haustier (X).

haustier (X), ¬katze (X).

D: klein (X), ¬katze (X).

C: kuscheltier (X), ¬flauschig (X), ¬katze (X).

Nachteil: D handelt von anderem als C!

Ableitung

{kuscheltier (X), ¬ flauschig (X), ¬ klein (X), ¬ haustier (X)}

{haustier (X), ¬ katze (X)}

{kuscheltier (X), ¬ flauschig (X), ¬ klein (X), ¬ katze (X)}

{klein (X), ¬ katze (X)}

{kuscheltier (X), ¬ flauschig (X), ¬ katze (X)}

B

B

D

C

Generalisierte SubsumtionBuntine

D ist genereller als C bzgl. B, gdw. es gibt eine Substitution , so daß Dkopf = C kopf

es gibt eine Skolemsubstitution , die alle Variablen in C durch neue Konstanten ersetzt

es gibt einen Klauselkörper D mit den Substitutionen, so dass

B Ckörper |= (Dkörper)

Die generalisierte Subsumtion entspricht dem Resolutionsbeweis von B,D |-- C, wenn D genau einmal im ersten Resolutionsschritt verwendet wird.

Beispiel 1

{¬ flauschig (b), ¬ haustier(b)} :{Z/b} 1: {X/b}

B: {haustier (X), tier (X), im_haus (X)}

C: {kuscheltier (Z), flauschig (Z), tier (Z), im_haus (Z)}

D: {kuscheltier (Y), flauschig (Y), haustier (Y)}D ≥ C bzgl. B ?

{¬ tier (b), ¬ im_haus(b), ¬ flauschig (b)} = D körper

Dkopf = C kopf

kuscheltier (Y) = kuscheltier (Z) mit = {Y/Z}

B, C körper |= (D körper

:{Z/b}

{haustier(X), ¬ tier (X), ¬ im_haus (X)}B

ja!

Beispiel 1 cont’edB: {haustier (X), tier (X), im_haus (X)}

C: {kuscheltier (Z), flauschig (Z), tier (Z), im_haus (Z)}

D: {kuscheltier (Y), flauschig (Y), haustier (Y)} C ≥ D bzgl. B ?

Ckopf = D kopf

kuscheltier (Z) = kuscheltier (Y) mit = {Z\Y}

B, D körper |= (C körper

:{Y/b}

{haustier(X), ¬ tier (X), ¬ im_haus (X)}B

{¬ flauschig(b), ¬haustier(b)} ={Y\b} 1={X\b}

{¬flauschig(b),¬ tier(b), ¬im_haus(b)} = Ckörper ja!

SkolemisierungB: haustier (X):- tier (a), im_haus (X).

D: kuscheltier (Y):- flauschig (Y), tier(a), im_haus(Y).

C: kuscheltier (Z):- flauschig(Z), haustier (a).

D soll nicht

genereller sein als

C

B

{haustier (X), ¬ tier (a), ¬ im_haus (X)}

{¬flauschig (b), ¬ haustier (a)} : {Z/b} 1: {X/a}

{¬ flauschig (b), ¬ tier(a), ¬ im_haus(a)} ≠ {¬ flauschig(b), ¬ tier(a), im_haus(b)} Dkörper

Dkopf = C kopf

kuscheltier (Y) = kuscheltier (Z) mit = {Y/Z}

B, C körper |-- D körper

C körper

Generalisierte Subsumtion operational

Gegeben zwei Mengen von funktionsfreien Hornklauseln.

Zu zeigen ist, dass eine Menge genereller als die andere ist.

Vergleich aller einzelnen Klauseln der Mengen. D ist genereller als C, wenn D zu C gemacht werden

kann durch:– Variable in D durch Konstante oder andere Terme

ersetzen,– Atome dem Körper von D hinzufügen– Atom aus dem Körper von D mit B resolvieren.

Vorteile der generalisierten Subsumtion

Nicht nur Literale zählen – wer mehr hat, ist spezieller.

Berücksichtien der Verbindung zwischen Literalen durch das Hintergrundwissen.

Substitutionen sorgen dafür, dass keine unzusammenhängenden Objekte einbezogen werden.

Nachteile der generalisierten Subsumtion

Es gibt unendlich viele Generalisierungen zu einer Klausel bezüglich des Hintergrundwissens.

Es gibt auch viele für die -Subsumtion. Dort hat man aber die Reduktion, die alle diese Generalisierungen auf eine Klausel zurückführt. Ein entsprechender Schritt fehlt bei der generalisierten Subsumtion.

Wenn wirklich die logische Folgerung zwischen den Klauselkörpern geprüft werden muss, ist dies nur semi-entscheidbar.

Wenn man Rekursion verbietet und die Länge der generalisierten Klausel beschränkt, können nicht mehr unendlich viele Generalisierungen erzeugt werden.

Hintergrundwissen in Beispiele hineinrechnen und dann LGG bilden

LE: Grundfakten LB: Grundfakten Beispiele werden saturiert:

– eneu = {e, K}, wobei K die Konjunktion aller (negierten) Fakten aus dem Hintergrundwissen ist.

– ggf. werden die neuen Beispiele auf verbundene Klauseln beschränkt.

Eine Klausel heißt verbunden, wenn alle ihre Literale verbunden sind.

Ein Literal heißt verbunden, wenn mindestens einer seiner Terme verbunden ist.

Tiefe von Termen

Ein Term heißt verbunden mit der Tiefe 0, wenn er im Kopf der Klausel vorkommt. Ein Term heißt verbunden mit der Tiefe d+1, wenn ein anderer Term desselben Literals mit der Länge d verbunden ist.

oma (X, Z) :- mutter (X,Y), vater (Y, Z). X, Z haben die Tiefe 0, Y die Tiefe 1.

LH: funktionsfreie, nicht rekursive KlauselnDann ist die -Subsumtion eine korrekte und vollständige Ableitung!

Beispiel

Beispiele neu:

oma(anna, christof):- mutter (anna, bernd), vater(bernd,christof).

oma(anita, cecilie):- mutter (anita, bruno), vater (bruno, cecilie).

LGG:

oma (A, C) :- mutter (A, B), vater (B, C).

Beispiele:

oma(anna, christof).

oma(anita, cecilie).

Hintergrundwissen:

mutter(anna, bernd). vater (bernd, christof).

mutter (anita, bruno). vater (bruno, cecilie).

= generalisierte Subsumtion?

Dkopf = Ckopf

={A/anna, C/christof}

B: mutter(anna, bernd). vater (bernd, christof).

|=

¬ Ckörper : mutter(anna, bernd). vater (bernd, christof).

Ist

D: oma (A, C) :- mutter (A, B), vater (B, C).

Generalisierung von

C: oma(anna, christof).

bzgl.

B: mutter(anna, bernd). vater (bernd, christof).

? Trivialerweise: JA.

Und wenn LB Klauseln sind?

Funktionsfreie Klauseln:Jedes Argument eines Prädikats ist entweder einer Variable oder eine Konstante -- Funktionen sind ausgeschlossen.

Generative Klauseln (bereichsbeschränkt):Jede Variable im Klauselkopf kommt auch im Körper vor.oma ( X,Z) :- mutter (X,Y), vater (Y, Z).

Wenn man alle Variablen im Hintergrundwissen durch die in den Beispielen vorkommenden Konstanten ersetzt, so wird das Hintergrundwissen variablenfrei.

Wenn LB auf funktionsfreie, generative Klauseln beschränkt ist, so kann man durch einen (tiefenbeschränkten) Ableitungsprozess ebenfalls variablenfreies Hintergrundwissen herstellen.

Und dann kann man das Hintergrundwissen in die Beispiele hineinrechnen und den LGG bilden.

Beispiel

Beispiele neu:

oma(anna, christof):- mutter (anna, bernd), vater(bernd,christof).

oma(anita, cecilie) :- mutter (anita, bruno), vater (bruno, cecilie).

Beispiele:

oma(anna, christof).

oma(anita, cecilie).

Hintergrundwissen:

vater(Y,Z) :- kind (Z, Y), mann (Y).

kind(christof, bernd). mann(bernd).

kind(cecilie, bruno). mann (bruno).

mutter(anna, bernd). mutter (anita, bruno).

SaturierungRouveirol

Sei C1 die Klausel {H1, B1} undC2 die Klausel {H2,B2}, wobei B2 subsumiert B1.

Dann ist die elementare Saturierung von C1 durch C2

Dkopf: H1 Dkörper: B1, H2

C1: oma(anna, christof):- mutter(anna, bernd), kind (christof, bernd), mann (bernd).

C2: vater(Y,Z) :- kind (Z, Y), mann (Y).

D: oma(anna, christof):- mutter (anna, bernd), kind (christof,bernd), mann(bernd), vater(bernd,christof).

Was wissen wir jetzt?

Wir kennen verschiedene Methoden, Hintergrundwissen zu berücksichtigen:– Plotkins relative Subsumtion

– Buntines generalisierte Subsumtion

– Erweiterung der Beispiele durch Hintergrund, das als Grundfakten vorliegt

– Rouveirols Saturierung Die Frage ist, ob dadurch das Lernen leichter oder

schwieriger wird?

Sprachbeschränkungen

Deterministische Klauseln (bzgl. des Hintergrundwissens):jede Variable in jedem Literal hat eine eindeutige Substitution durch das Hintergrundwissen.

Klausel: oma(anna, Z):- mutter(anna, X), vater(X, Z).

Hintergrundwissen: mutter(anna, bernd). vater (bernd, christof).

hier: nur {X/ bernd, Z/christof}

Aber wenn Hintergundwissen:

mutter(anna, bernd). vater(bernd, christof). vater (bernd, christiane).

dann ist die Klausel indeterministisch, weil es zwei Substitutionen für Z gibt.

ij-deterministisch Ein Term aus dem Klauselkopf K ist mit einer Kette 0

deterministisch verbunden. Für den Klauselkörper nehmen wir an, daß die Literale nach

Verbundenheit mit dem Klauselkopf geordnet sind:

{ ¬ L1, ..., ¬ Lm, ¬ Lm+1, ..., ¬ Ln } Ein Term t aus Lm+1 ist genau dann durch eine deterministische

Kette der Länge d+1 verbunden, wenn– alle Terme im Klauselkopf und in {¬ L1, ..., ¬ Lm } verbunden

sind durch deterministische Ketten, die höchstens d lang sind,– es für jede Substitution , die K mit einem Beispiel und die

ersten Literale mit dem Hintergrundwissen unifiziert (K E+ und { {¬L1}, ..., {¬ Lm}} B ) höchstens eine Substitution gibt, so dass Lm+1 B.

Die minimale Länge der deterministisch verbindenden Ketten ist die deterministische Tiefe eines Terms.

Eine Klausel mit maximaler deterministischer Tiefe i und maximaler Stelligkeit j heißt ij-deterministisch.

Beispiel

oma(X, Z) :- mutter (Y, Z) , mutter (X, Y)

oma(X, Z) :- vater (Y, Z), mutter (X, Y)

oma(X, Z) :- mutter (X, Y), elternteil (Y, Z)

tante(X1, Z) :- geschwister (X1, Liste),

member (X2, Liste),

elternteil (X2, Z).

tante(X, Z) :- mutter (Y, Z), schwester (X, Y)

tante(X, Z) :- vater (Y, Z), schwester (X, Y)

12-deterministisch

indeterministisch, insofern eine Mutter mehrere Kinder haben kann und ein Kind 2 Elternteile hat.

indeterministisch, insofern als die Liste mehr als ein Element enthalten kann und X2 nicht im Kopf gebunden ist.

12-deterministisch

Lernbarkeit

Sei – LE Grundfakten mit höchstens t Termen,– LB Grundfakten mit m verschiedenen Prädikaten, die

höchstens f Terme enthalten,– LH ij-deterministische Klauseln, mit festen i und j,

so werden Hypothesen mit höchstens O( (t f m)ij) Literalen gelernt.

Wegen der Tiefenbeschränkung ist die Länge der Klauseln also nicht mehr exponentiell.

Indeterministische Klauseln sind auch bei Tiefenbeschränkung nicht polynomiell lernbar.

Beschränkte Klauseln

Eine Klausel ist beschränkt, wenn alle Variablen aus dem Klauselkörper auch im Klauselkopf vorkommen.

Spezialfall der ij-deterministischen Klauseln mit i = 0. Polynomiell lernbar, PAC-lernbar. Nicht ausdrucksstärker als Aussagenlogik.

k- lokale Klauseln

Bestehe eine Klausel D aus einem deterministischen Teil DDET und einem indeterministischen Teil DNONDET. Kopf D0 .Sei vars eine Funktion, die alle Variablen einer Klausel findet.

Als lokalen Teil LOC einer Klausel bezeichnen wir die Literale aus DNONDET, für die gilt: (vars (LOC) \ vars({D0, DDET })) vars (DNONDET \LOC) = { }

Minimaler lokaler Teil für eine Konstante kk-vlokal gdw. k ≥ | vars(LOC) \ vars({ D0, DDET }) | nicht lernbark-llokal gdw. k ≥ | LOC | lernbar

Aufwand von subsumes(D,C): O(|D|*|DDET|*|C|+|LOC1,...,LOC n|2 + n(kk*|C|))

Kietz 1997

Beispiel

geschwister(X, Z) :- mutter (Y1, X), mutter (Y1, Z),

mutter (Y1, Y2),

elter (Y2, Y3).

vars ( {D0, DDET }): X, Y1, Z

vars ( DNONDET ): Y1, Y2, Y3

LOC 1: mutter (Y1, Y2)

LOC 2: elter (Y2, Y3)

LOC 3: mutter (Y1, Y2), elter (Y2, Y3)

Geschwister, deren Mutter Oma ist:

(vars (LOC) \ vars ( {D0, DDET })) vars ( DNONDET \LOC) = { }

LOC1:

( {Y1, Y2 } \ {X, Y1, Z}) vars({mutter(Y1,Y2),elter(Y2,Y3)}\{mutter(Y1,Y2}) = {Y2} {Y2,Y3} { }

LOC2:

( {Y2, Y3} \ {X, Y1, Z}) ({Y1, Y2}) = {Y2, Y3} {Y1,Y2} { }

LOC3:

({Y1, Y2, Y3} \ {X, Y1, Z}) ({ }) = {Y2, Y3} { } = { } 2-vlokal, 2-llokal

Grenzen der Lernbarkeit:deterministische Hornformeln

Konsistenzproblem (|--, LH, LE, LB): gibt es eine Hypothese, die das Begriffslernproblem löst?

Das Konsistenzproblem ist PSPACE-schwierig für– LH: deterministische, funktionsfreie Hornformeln

• selbst wenn LE variablen- und funktionsfrei und kein Hintergrundwissen!

Deshalb ist auch das Begriffslernproblem PSPACE-schwierig.

Kietz 1997

Grenzen der Lernbarkeit:indeterministische Hornformeln

Das Konsistenzproblem ist NP-schwierig für

– LH: indeterministische, 1-vlokale funktionsfreie Hornformeln

• selbst wenn es kein Hintergrundwissen gibt oder LE und LB Grundfakten sind.

Die Konsistenzprobleme(subsumes, k-llokal, funktionsfrei, kein B) und(subsumes, k-llokal, Grundfakten, Grundfakten)sind polynomiell lösbar.

Auch die entsprechenden Begrifflernprobleme sind polynomiell lösbar.

Das ist die maximale Erweiterung der Ausagenlogik, die wir noch effizient lernen können. Kietz 1997

Was wissen wir jetzt?

Lernen in Prädikatenlogik ist zu schwierig, insbesondere mit Hintergrundwissen. Deshalb wird der Formalismus eingeschränkt:– LH als ij-deterministische Klauseln macht das in

polynomiellem Aufwand (hoch i hoch j!) lernbar.

– LH als k-llokale (indeterministische) Klauseln macht das Lernen in polynomiellem Aufwand lernbar.

Der Haken ist das Testen der Hypothesen, also der deduktive Teil...

ILP Lernaufgabe Regellernen

Gegeben eine Menge von Beobachtungen E in LE und Hintergrundwissen B in LB

gesucht wird eine Menge von Regeln H in LH, für die gilt:

1. Gültigkeit: M+(B E) M(H) H gilt in allen minimalen Modellen von E und B.

2. Notwendigkeit: für alle h in H gibt es ein e in E, so dass B,E\{e} |=/= e und B, E\{e}, h |= e.

3. Vollständigkeit: falls h in LH Bedingungen 1. und 2. erfüllt, so gilt H |= h

4. Minimalität: es gibt keine echte Teilmenge in H, die die Bedingungen 1.-3. erfüllt.

(minimales) Modell

Gegeben eine Interpretation I für eine Menge von Formeln F.

I ist ein Modell von F, M (F), wenn alle Formeln von F in I wahr sind.

Wenn es keine Interpretation I' gibt, mit I' I und I' ist ein Modell von F,

ist I ein minimales Modell für F, geschrieben M+(F).

Deklarative Beschränkung von LH

Da wir wissen, dass die Lernbarkeit durch die Hypothesensprache LH gegeben ist, können wir diese auch anwendungsspezifisch einschränken.

Das System RDT (Kietz, Wrobel 1991, aufbauend auf Emde, Habel, Rollinger 1983) verwendet Regelschemata, deren Instanzen Regeln sind – und die werden auf Gültigkeit in den Beobachtungen (eingeschänkt auf Grundfakten) geprüft.Q(X)P1(X,Y) wird mit ={Q\q,P1\p} zuq(X)p(X,Y) und mit ={X\a, Y\b} zuq(a)p(a,b)

Ordnung der Regelschemata

Wenn es eine Instanziierung R eines Regelschemas R gibt und R ist genereller als R’, dann gibt es eine Instanziierung R’ und subsumes(R, R’). Dabei darf keine unterschiedlichen Prädikate zusammenfallen lassen!

kann generalisieren ( nur spezialisieren): P1(X,Y), P2(X,Y)=P1(X,Y) bei ={P2\p, P1\p}

Ordnung der Literale im Regelschema über die Tiefe der Terme.

Suche in der Hierarchie der Regelschemata

Testen:gilt für alle Grundfakten, die -Instanzen eines -instanziierten Regelschemas sind, – dass die Konklusion (Kopf) nicht negiert vorkommt?– dass für alle Prämissen das dem Kopf entsprechende

Fakt gegeben ist? Breitensuche erlaubt sicheres Beschneiden:

– Wenn es negierte Konklusionen gibt, wird das Regelschema spezialisiert.

– Wenn nicht hinreichend viele -Instanzen gefunden werden (Benutzerkriterium) wird nicht spezialisiert.

RDT Algorithmus

rdt(q/arity)

RS:={ }, aktuell:={ }

für alle Regelschemata R

if Kopf C von R unifizierbar ist mit q/arity,

RS:= RS R, ={C\q}

while RS =/= {}

nimm generellstes R aus RS

instanziiere und teste R’: “R gilt” v “R zu allgemein”

entferne alle Spezialisierungen für “R gilt” aus RS,

füge alle echt verschiedenen Spezialisierungen von “R zu allgemein” RS hinzu

Kietz 1997

RDT Regeln lernen

Regeln Fakten

Sortenverbandabstrahierter Regelgraph

Regelmodelle

r(a,b)p (b)q (a)

r(X,Y) & p(Y) --> q(X)

--> Q(X)P(X) --> Q(X) R(X,Y)--> Q(X)

R(X,Y) & P(Y) --> Q(X)

{R/r,P/p,Q/q}

{X/a, Y/b}

(Emde, Kietz, Klingspor, Morik, Wrobel)

Eigenschaften von RDT

Durch die Regelschemata wird der Hypothesenraum drastisch verringert (z.B. von 1040 auf 105).

Dabei kann der Benutzer angeben, welche Art von Regeln ihn interessieren.

Durch die Allgemeinheitsordnung können große Teile es Hypothesenraums sicher herausgeschnitten werden.

Innerhalb des gegebenen Hypothesenraums ist RDT vollständig: es findet alle generellsten gültigen Regeln!

KDD mit ILP und direktem Datenbankzugriff

Rule Discovery Tool (Kietz, Wrobel 1992) RDT/db (Brockhausen,Morik 1997) RDT/dm (Münstermann 2002) Gültigkeit von Regeln wird mithilfe von SQL-Anfragen

über der Datenbank getestet. Akzeptanzkriterium wird vom Benutzer gegeben. Abbildung der Datenbankrelationen und –attribute auf

Prädikate wird unter Einbeziehung des Benutzers halbautomatisch durchgeführt.

Akzeptanzkriterien

Bausteine:

pos(H): Prämisse und Konklusion kommen gemeinsam vor

neg(H): Prämisse und Negation der Konklusion kommen gemeinsam vor

concl(H): Konklusion kommt vor

pred(H): Konklusionsprädikat ist anwendbar, kommt aber nicht vor

unc(H): Instanzen der Konklusion, die von Prämisse nicht abgedeckt sind

total(H): pos(H) neg(H) pred(H)

absolut

Bayes: a posteriori > a priori

8,0)(

)(

)(

)( Hconcl

Hneg

Hconcl

Hpos

)()(

)(

)()(

)(

HpredHconcl

Hconcl

HnegHpos

Hpos

Abbildungen von Datenbank auf Prädikate (alternativ)

Jede Datenbanktabelle ist ein Prädikat, ihre Attribute sind die Argumente (mapping 1).customer (Person, Income, Customer)

Auswahl interessanter Attribute:Vorauswahl bei sehr vielen Datenbankattributen– Jedes Datenbank-Attribut wird ein Prädikat, der Schlüssel

und der Attributwert die Argumente (mapping 2).income (Person, Income), ..., wife (Husband, Wife )

– Jeder Wert eines Datenbankattributs wird Prädikat, Schlüssel das Argument (mapping 3).customer (Person), inc_10_20 (Person)

– Sinnvolle Intervalle in Attributwerten vorher finden und diese zu Prädikaten machen (mapping 4).

Größe des Hypothesenraums

r Anzahl der Regelschemata

p Anzahl der Prädikate

k max. Anzahl von Literalen in einem Regelschema

Bei Konstantenlernen:

c Anzahl der zu lernenden Konstanten

i max. Anzahl von Werten für eine Konstante

Je nach gewählter Abbildung ist die Größe des Hypothesenraums sehr unterschiedlich.

r p ic k

Experiment mit der Filmdatenbank

Was charakterisiert die besten Filme? Gegeben die Datenbank filmdb (bei Postgres heißt

das “catalog”), – ausgewählt für das mapping 3 die Tabellen

imdb_movie mit den Spalten year und type,imdb_genre mit der Spalte name

– ausgewählt für das mapping 4 die Tabelleimdb_actor mit der Spalte pos

Lerne Regeln, die bezüglich der top 250 Filme wahr sind!

RDT/dm

Einmal angeben:module add export/rdtdminit rdtdm

Dateien:– rdtdmsystem.xml beschreibt die mapping types 1 – 4 und die

Akzeptanzkriterien. Die Klasse DBMapperTabType1.java implementiert z.B. das Interface DBMapperTabType.

– userfilmdb.xml beschreibt die Regelschemata, Optionen und das Zielattribut. Als database user muss der usr des Pools (mlrnxxx) angegeben werden. Das target predicate muss als Präfix mlrnxxx_rdt_ enthalten.

Starten: ~usr/rdtdm/bin/startMain.sh – mcf /home/usr/rdtdm/Config/rdtdmsystem.xml – ucf /homeusr/rdtdm/Config/userfilmdb.xml

Experimente

Daimler Benz AG

2,6 Gigabyte Datenbank: alle Fahrzeuge und ihre Garantiefälle

40 Tabellen mit je bis zu 40 Attributen

1. Unterschiedlich großer Hypothesenraum:

4913 ≤ Größe ≥ 2,8 E 41

2. Unterschiedlich großer Datenbankauszug:

max. 23 Tabellen

max. 750 000 Tupel

3. Verwendung von Hintergrundwissen

4. Vergleich mit anderen ILP-Verfahren

Verwendung von Hintergrundwissen

Gegeben:elektronisch verfügbares Werkstattbuch für PKW mit allen Fahrzeugteilen

Finde:Gruppen von Teilen, die räumlich, funktional oder bzgl. ihrer Schadensart zusammenhängen

Umformen der Datei in einstellige Fakten, wobei das Fahrzeugteil als Argument, der Zusammenhang als Prädikat ausgedrückt ist

Verwendung von STT (Kietz 1989) zum Finden einer Subsumtionshierachie

Klassen von Fahrzeugteilen der Datenbank hinzufügen

Einige Lernergebnisse

rel_niveauregulierung (FIN) beanstandet (FIN)

motor_e-typ (FIN, Typ) & mobr_cyl (Typ, 6) beanstandet (FIN)

rel_garantie (X1, X2, RB, X4, X5, X6, X7, Konfig, Teil) & rel_garantie_benzman (X1, X2, RB, X4, X5, X6, X7, FIN) & rel_motor_typ (FIN, 206) & italien(RB) class_419 (Konfig, Teil)

rel_garantie ( X1, X2, X3, X4, X5, X6, X7, Konfig, Teil) & class_35 (Konfig, Teil) kostbean_0_500 ( X1, X2, X3, X4, X5, X6, X7)a priori Wahrscheinlichkeit: 0,84 a posteriori Wahrscheinlichkeit: 0,89

Bergiffslernen mit RDT

Hinreichende Bedingungen für einen Begriff:z.B. für verkehrsSuende(E)autoGeparkt(E,P),parkverbot(P)verkehrsSuende(E)autoGeparkt(E,P),parkuhr(P),unbezahlt(E) verkehrsSuende(E)

Komplexere Begriffe (polymorph) darstellbar! Notwendige Bedingungen:

z.B. für verkehrsSuende(E)verkehrsSuende(E) geldstrafe(E, 20)verkehrsSuende(E) ordnungswidrigkeit(E)verkehrsSuende(E), widerspruch(T,E) gericht(E)

Wrobel 1994

Beispiele zusammenstellen

Grundfakten für Konklusion als positive Beispiele des Begriffs

Negierte Grundfakten für Konklusion als negative Beispiele des Begriffs

Instanzen des Begriffs in Prämissen

Alles andere erledigt RDT mit Hilfe der Regelschemata, die nun teilinstanziiert sind.

Lokale Muster statt globaler Modelle

Globale Modelle – lokale Muster– Ausnahmen– nicht abgedeckte Beobachtungen– Ausreißer

Unterschiedliche Lernstrategien– Großer Hypothesenraum für kleine Beispielmengen– Höhere Dimensionaliät für lokale Muster

Beispiel Filmbewertungen:– das globale Modell– lokale Muster

Morik 2002

Ausnahmen in globalen Modellen

Daten bereinigen:Produktionsdatum vor Verkaufsdatum eines Autos – bis auf einige Ausnahmen (falsch eingetragen)

Missbrauch:Rechnungen werden bezahlt – bis auf einige Kunden

Fehlende Attribute:Ein Medikament soll den Blutdruck senken – außer bei Patienten mit Herzrhythmusstörung...

Globales Modell in Logik

Logisches Programm: Menge von Regeln Answer set des Programms: aus den Regeln

ableitbare Fakten. Das Model ist vollständig, wenn alle positiven

Beispiele im answer set sind. Das Model ist korrekt, wenn kein negatives Beispiel

im answer set ist.

Answer set und Beispiele

HLogic

Program

uncoveredpredicted pos

+

neg

¬

Answer set Q Set of instances S

Filmdatenbank imdb.com

Ranking der Filme:

v: Anzahl der Stimmen für Film, k: Schwellwert für vX: durchschnittliche Filmbewertung, C: durchschnittliche Bewertung aller Filme

68 der top 100 Filme und 82 der schlechtesten 100 Filme sind amerikanisch,

40 der top 100 sind amerikanische Dramen, aber nur 7 der schlechtesten 100.

kv

kC

kv

vXrank

globales Modell lernen

Top 100 (positive Beispiele), bottom 100 (negative Beispiele) gemäß der Abstimmung – Klassifikation (globales Modell)

22 Prädikate 2 Regelschemata mit maximal 2 Literalen 2 * 222 = 968 Hypothesen der Form:

P1(X1) P2(X1) P3(X1) oder

P1(X1, X2) P2(X2) P3(X1)

Gelernte Regeln

h1 : usa(X) drama(X) top(X)

h2 : director(X,Y) topDir(Y) top(X)

h3 : actor(X,Y) topActor(X) top(X)

h4 : director(X,Y) notbotDir(Y) top(X)

h5 : actor(X,Y) notbotActor(Y) top(X)

14 negative Beispiele covered,

15 top Filme uncovered.

Lernen lokaler Muster

14 negative Beispiele abgedeckt Können wir daraus lernen? Größerer Hypothesenraum:

286 keywords, 2544 Namen von Schauspielern und Regisseuren als Konstanten C2 zusätzliche Regelschemata

P1(X1) P2(X1) P3(X1) P3(X1)

P1(X1, C) P2(X1) P3(X1)

1017 4 * (330 * 2544)3

6.0)()(

)()(

hneghpos

hneghpos

Lernergebnisse

h8 : actor(X,53) botPerson(53) notop(X)

h9 : actor(X,17) botPerson(17) notop(X)

h10 : actor(X,30) botPerson(30) notop(X)

h11 : usa(X) drama(X) musical(X) notop(X)

Schauspieler 53, 17, 30 spielten in „Police Academy“

Nur 6 der 14 Ausnahmen abgedeckt.

Abschwächen des Akzeptanzkriteriums führt zu rein zufälligen Regeln.

Lernen lokaler Muster aus nicht abgedeckten Beispielen

22 Prädikate 4 Regelschemata 4 * 223 = 42592 Hypothesen

h6 : italy(X) drama(X) top(X)

h7 : denmark (X) drama(X) top(X)

Vergrößern des Hypothesenraums

Zusätzlich die keywords verwenden! 4 * 3303 = 143 748 000 Hypothesen

h12 : europe(X) key_family(X) top(X)

h13 : europe(X) key_independent(X) top(X)

h14 : europe(X) key_bicycle(X) top(X)

h14 : drama(X) key_love(X) top(X)

11 der 15 Filme abgedeckt durch 6 Regeln.Übrig bleiben: Das Boot, Lord of the rings, Shrek, Det Sjunde inseglet.

Finden lokaler Muster in 1 Schritt

Akzeptanzkriterium a la Binomialtest

Größe von ext(h) bzgl. Gesamtgröße der Beispiele gewichtet das Verhältnis zwischen der Verteilung in h und der Gesamtverteilung.

Wieder wurden h6 und h7 gefunden -- und die „Amerikanischen Regeln“(h1 – h5).

Aber es wurden auch noch viel mehr Regeln gefunden, die dieselben Beispiele abdecken.

Verschärft man das Kriterium hat man nur h1 – h5.

05.0)()(

)()()(

negconclconcl

concl

hneghpos

hpos

negconclconcl

hneghpos

2-stufiges Vorgehen sinnvoll

Globales Muster lernen, bezüglich dessen die interessanten Beispiele bestimmen

Lokale Muster an Hand der interessanten Beispiele finden.

Analoges Vorgehen auch für SVM erfolgreich (Rüping 2006)

Was wissen wir jetzt?

Der Hypothesenraum kann vom Benutzer auf Schemata für Regeln eingeschränkt werden.

RDT ordnet Regelschemata nach Allgemeinheit. Daher ist bei Breitensuche sicheres Pruning möglich. Innerhalb des Hypothesenraums findet RDT alle allgemeinsten

gültigen Regeln. Sie können den Algorithmus skizzieren. Die Regellernaufgabe kann zur Begriffslernaufabe spezialisiert

werden: ein Prädikat in der Konklusion, entsprechendes Akzeptanzkriterium.

Sie kennen einige Anwendungen und wissen, was lokale Modelle sind.

Verband der Sorten lernen

Jede Argumentstelle eines Prädikats hat bestimmte -Instanzen in der Menge der Grundfakten. Dies ist die Extension der Sorte dieses Arguments.

Logik mit Sorten schließt schon in der Signatur der Logik unsinnige Belegungen aus.– Üblich für die Unterstützung von Benutzern bei der Eingabe

neuer Fakten, z.B. geldstrafe(<Ereignis>,<Betrag>)– RDT verwendet die Sorten, um keine Instanziierung einer

Prädikatsvariable zu versuchen, die nicht kompatibel mit den Sorten ist.

STT lernt die Sorten aus vorhandenen Fakten!

Kietz 1988

Deklaration von Sorten

hinweis(<symptom>,<krankheit>)

ursache(<krankheit>,<symptom>)

lindern(<wirkstoff>,<symptom>)

enthalten(<pille>,<wirkstoff>)

Verband der Sorten

Extension der Sorten für Argumente Äquivalenzklassen der Sorten Extension der Äquivalenzklassen Partielle Ordnung zwischen Äquivalenzklassen der

Sorten Schnittsorten Verband der Äquivalenzklassen

Extension der Sorten

Sei SN eine Menge verschiedener Sortennamen und T die Menge aller Terme in der Menge F der Grundfakten, dann istext: SN Pot(T) mit ti ext(arg_sort(i,p)) gdw.

(p(t1 ,..., ti ,...,tn) F v p(t1 ,..., ti ,...,tn) F)

SNAB

CD

{a,b,c,d}

{a,b,c} {a,b,d} {a,c,d} {b,c,d}

{a,b} {a,c} {a,d} {b,c} {b,d} {c,d}

{a} {b} {c} {d}

{ }

Pot(T)

ext

Beispiel

FB={ p(a,b), p(b,c), p(c,a), r(a,b),r(a,d)}

SN={A,B,C,D}

A=ext(arg_sort(1,p))={a,b,c} C=ext(arg_sort(1,r))={a}

B=ext(arg_sort(2,p))={a,b,c} D=ext(arg_sort(2,r))={b,d}

SNAB

CD

{a,b,c,d}

{a,b,c} {a,b,d} {a,c,d} {b,c,d}

{a,b} {a,c} {a,d} {b,c} {b,d} {c,d}

{a} {b} {c} {d}

{ }

Pot(T)

ext

Äquivalenzklassen der Sorten

Zwei Sortennamen sind äquivalent, wenn ihre Extension gleich ist:

Sei SN/ die Menge aller Klasse von Sorten gleicher Extension und CN eine Menge eindeutiger Klassennamen. Dann seicn: SN/ CN die bijektive Funktion, die den Äquivalenzklassen eindeutige Namen zuordnet.

Die Funktion class: SN CN gibt für jede Sorte ihre Klasse an.

212121 )(:, sextsextssSNss

212121 )(:, sssclasssclassSNss

Extension der Äquivalenzklassen

Die Funktion cext: CNPot(T) ordnet den Klassen die Extension zu, so dass cext(class(s))=ext(s).

SN/ all

[A,B] [D]

[C] {}

CN

C1

C2 C3

C4 C6

{a,b,c,d}

{a,b,c} {a,b,d} {a,c,d} {b,c,d}

{a,b} {a,c} {a,d} {b,c} {b,d} {c,d}

{a} {b} {c} {d}

{ }

SOR Pot(T)

cn cext

Hierarchie

Die Teilmengenbeziehung von Pot(T) wird durch cext an CN weitergegeben.

c1 c2 cext(c1) cext(c2)

– supers: CN Pot(CN) mitsupers(c1):={c CN | c1 c c c1 }

– subs: CN Pot(CN)subs(c1):={c CN | c c1 c c1 }

Supremum (c, c1): Infimum(supers(c1) supers(c))

Das Infimum gibt es evtl. nicht. Es kann aber durch Schnittmengen gebildet werden.

Schnittsorten

Schnittsorten IS sind alle Paare von Klassen, die sich extensional überschneiden, aber nicht in Teilmengenbeziehung stehen. IS=

Die Extension von IS ist iext: IS Pot(T)

Aufwändig: bei n Klassen gibt es womöglich 2n IS. ISN := SN IS

21122121, ccextccextccccCNcc

212121 ,:, ccextccextcciextIScc

Verband der Äquivalenzklassen

Jetzt haben wir einen Ausschnitt aus T, der selbst wieder ein Verband ist!

SOR Pot(T) mit– {} SOR, T SOR, s SN: ext(s) SOR

– m1, m2 SOR m1 m2 SOR

– es gibt keine anderen m SOR.

Infimum m1,m2: m1 m2

Supremum von m1,m2: Infimum(supers(m1) supers(m2))

Beispiel

arg_sort(2, affectPos){soreThroat,flu}

arg_sort(1, indicate)arg_sort(2, cause){soreThroat} int(pastille,medizin)

{inspirol}

arg_sort(1,contains){inspirol, aspirin}

arg_sort(1, suck){john,fred}

arg_sort(2, suck){vivil,inspirol}

arg_sort(1, affectPos){aspirin,inspirol,asa,bc}all

irritation person pastille substanz

symptom krankheit wirkstoff medizin

{ }arg_sort(2, indicate)arg_sort(1, cause){flu}

arg_sort(2,contains){asa, bc}

pille

Weitere Arbeiten

MOBAL: Werkbank für Erwerb, Verarbeitung und Revision von Wissen beinhaltet RDT, CLT, STT, KRT und eine Inferenzmaschine mit 4wertiger Logik.Katharina Morik, Stefan Wrobel, Jörg-Uwe Kietz, Werner Emde (1993) “Knowledge Acquisition nd Machine Learning”, Academic Press

STT ist fast schon das Erlernen von Description Logic aus Grundfakten – entsprechend weiterentwickelt zu Kluster.Katharina Morik, Jörg-Uwe Kietz (1994) “A Polynomial Approach to the Constructive Induction of Structural Knowledge”, Machine Learning Journal

Was wissen wir jetzt?

STT lernt aus Grundfakten einen Verband von Sorten. Damit es ein Verband wird müssen – Äquivalenzklassen für Sorten gleicher Extension und

– Schnittsorten zwischen Äquivalenzklassen

gebildet werden. STT zeigt zugrunde liegende Begriffstrukturen. Das

ist günstig für Benutzer – und für RDT. STT entspricht einem inkrementellen,

beschreibenden Begriffslerner, kann zum Lernen von Ontologien (DL) leicht erweitert werden.

Lernen operationaler Begriffe zurRoboternavigation

Repräsentation Lernen Planung und Planausführung Experimente

Repräsentation

Lernen

Planung Wahrnehmung

Repräsentation

Relationale Repräsentation

Nähe zu menschlicher Kommunikation Zeitrelationen Kombination verschiedener Sensoren Integration von Hintergrundwissen Integration von Wahrnehmung und Handlung Hierarchie von Repräsentationen

Zeitrelationen

Zeitpunkt: Eintreffen eines Sensorwertes Zeitintervall: Gültigkeit des Sensormerkmals Relationen zwischen, direkt nach, während... abstrakte Zeitpunkte -- Flexibilität keine zusätzliche Kontrollschleife bei der

Planausführung (gilt Wahrnehmung noch?)

along_door( T1, T4, SClass, PDir):-stable( Orient,S, T1, T2, Gradient1), no_measurement( Orient,S,T2, T3, Gradient2),stable( Orient,S,T3, T4, Gradient3).

Kombination verschiedener Sensoren

Sensorarten (Ultraschall, Kamera, Laserscanner) verknüpfen

along_door( T1, T2, PDir):-sonar_along_door( T1, T2, SClass, PDir),vision_ along_door( T1, T2, PDir).

towards_stairs(T1, Ts,ahead):- sonar_towards_stairs(T1,T2, ahead).

towards_stairs(T1, Ts,ahead):- vision_towards_stairs(T1,T2, ahead).

Hintergrundwissen

Anordnung der Sensoren an PRIAMOS bildet Klassen von Sensoren

Berechnung der Wahrnehmungsrichtung der Sensoren gemäß der Bewegungsrichtung

Mehrheitsentscheidung von Sensoren derselben Klasse

along_door( T1, T4, side, PDir):-stable( Orient,S, T1, T2, Gradient1), no_measurement( Orient,S,T2, T3, Gradient2),stable( Orient,S,T3, T4, Gradient3),sclass(S, T1, T4, side).

Richtungsrelationen

Gleiche Richtung -- gleiche Variable Prädikate zu räumlichen Relationen

along_door( T1, T2, PDir), move(T2, T3, backwards),opposite(PDir, OppDir), along_door(T3,T4,OppDir).

Integration von Handlung und Wahrnehmung

Wahrnehmung stets auf Handlung bezogen Wahrnehmungsregeln in Merkmale transformieren

moving( T1, T2, along_door):-move(T1, T2), along_door( T3, T4),T1 ≤ T3 < T4 ≤ T2.

time_interval_perception( T1, T2, along_door):- along_door(T1,T2).

time_point_perception( T1, T2, beside_wall):-beside_wall(T1, T2).

Operationale Begriffe

durch die Tür fahren, neben die Tür stellen,entlang der Tür (Wand) fahren

crossing_door(T1, T4):-standing(T1, T2, to_door, PDir). %Vorbedingungmoving( T2, T3, through_door, PDir), %Handlungstanding( T3, T4, to_door, rear). %Nachbedingung

Hierarchie

Basismerkmale

Sensor-merkmale

Sensorgruppen-merkmale

Wahrnehmungs-merkmale

Handlungs-merkmale

WahrnehmungsintegrierendeHandlungsmerkmale

Operationale Begriffe

Wahrnehmung und Handlung

Basiswahrnehmungsmerkmale

Zeit

Distanz

1m

2 m

3m

•• •

•

• • •

• • •

1 4 5 7 10 12

increase(s1,90,1,4,0.7)incr_peak(s1,90,4,5,3.2)decrease(s1,90,5,7,-0.3)no_measurement(s1,90,7,10,_)stable (s1,90,10,12,0.01)merkmal(S, Orient, T1, T2, Grad)

Hierarchische Programme

Jede Ebene des Programms kann einzeln gelernt werden.

Inferenz kann auf sequentielle Inferenzen der Tiefe 1 reduziert werden.

Wurden alle Inferenzen einer Ebene abgearbeitet, brauchen sie nicht revidiert zu werden.

Lernen in Logik

Sensormerkmale, Sensorgruppenmerkmale Wahrnehmungsmerkmale

wurden aus 20 Fahrten in 2 Räumen gelernt.

13746 Basiswahrnehmungsmerkmale

3360 Sensormerkmale

480 Sensorgruppenmerkmale

100 Wahrnehmungsmerkmale

Lernergebnisse

5 Fahrten zum Lernen,15 zum Testen

Unterste Ebene hand-klassifiziert: Zeitintervalle, in denen entlang d.Wand (Tür), durch d.Tür gefahren wurde

Obere Ebene durch Lern-ergebnisse d. unteren Ebene klassifiziert!

Sensormerkmale:coverage:25.7 %(along-wall)- 93.5% (beside_door)accuracy:27.1% (along_door)74.7% (through_door)

Sensorgruppenmerkmale:29.6%-100% coverage48.9% - 100% accuracy

Pareto-Optimum beim Lernen der Wahrnehmungsmerkmale

along_wallcoverage: 95 %, accuracy: 54.3 %

along_doorcoverage: 91.7 %, accuracy: 50.5 %

beside_doorcoverage: 80 %, accuracy: 67.4 %

through_doorcoverage: 100 %, accuracy: 93.8 %

SHARC (Volker Klingspor 1998)

Objekterkennung Planverfeinerung- undausführung

Planung Kommunikation mit Menschen

Kommunikation mit Roboter

Scheduling

Synchronisierung

Planung

Ziel: Nachbedingung eines operationalen Begriffs Start: Menge aktuell ermittelter

wahrnehmungsintegrierender Handlungsmerkmale Planung: alternative Folgen operationaler Begriffe,

die zum Ziel führen

Abstrakter Planbaum

crossing_door

rotate_beside_door

move_beside_door

move_beside_door

move_along_door

rotate_in_corner

move_into_corner

move_along_door

rotate_beside_wall

move_closer_to_wall

Ausführung

Planverfeinerung und -ausführung

Konkretisierung des abstrakten Planbaums durch die (gelernten) Regeln

standing(T3, T4, to_door, rear). %Nachbedingungmoving( T2, T3, through_door, right_left), %Handlungstanding( T1, T2, to_door, small_side). %Vorbedingung

Ausführungslisten

Rückwärtsverkettung gemäß der Regel für ein Wahrnehmungsmerkmal über alle Ebenen bis zur niedrigsten Ebene

[move( med_speed, front), time_interval_perception(T2, T3, through_door, right, large_side)]

vorwärts fahren und dann through_door wahrnehmen

Reaktive Steuerung

Beim Eintreffen eines wahrnehmungsintegrierenden Handlungsmerkmals:– Notfall? -- speziellsten mit aktueller Wahrnehmung

unifizierbaren Plan ausführen!

– sonst: Liste der Wahrnehmungen erweitern Beim Eintreffen eines Merkmals der niedrigsten

Ebene:– im Planbaum weiterrücken, Ausführungsliste

verschicken

Experimente

25 Fahrten, davon 18 Fahrten in Räumen, die nicht zum Lernen verwendet wurden

Ziel: Durchfahren der Tür 23 Fahrten erfolgreich 21 Fahrten: alle Wahrnehmungsmerkmale korrekt

erkannt 2 Fahrten: Hindernis nicht erkannt! along_door einmal nicht und einmal fälschlich

erkannt.

Performanz

Realzeit (Millisekunden vergangener Zeit)von Übertragung der Sensorwerte bis zur endgültigen Verarbeitung (inclusive Handlung) ≤ 500 msec, ≤ 4500 msec. bei 9 Sensorwerten

Rechenzeit der Planverfeinerung und -ausführung: ≤ 10 msec. bei 96.8 % Eingaben, ≤ 20 msec. bei 3.2 % Eingaben.

Was wissen wir jetzt?

Logikbasiertes Vorgehen in der Robotik keine Karten notwendig keine konkreten Abmessungen, Zeitpunkte,

sondern Intervalle und Unifikation Handlung, solange oder bis ein

Wahrnehmungsmerkmal gilt lernbare Repräsentation auf allen

Abstraktionsebenen leichte Kommunikation mit Menschen.

Entwicklungen von kindlichen Erklärungen des Tag/Nacht-Zyklus’ als Wissensrevision

Katharina Morik

Informatik LS 8

Universität Dortmund

Schwerpunkt am LS8

Eine gute Theorie ist die beste Praxis! Maschinelles Lernen

– Stützvektormethode (support vector machine)

– Induktive logische Programmierung

– Merkmalsextraktion und –generierung

– Clustering (verteiltes Ontologielernen) Wissensentdeckung in sehr großen

Datensammlungen (Datenbanken, WWW, Multimediasammlungen)

Lebenszyklus der Forschung

Stützvektormethode zur Textklassifikation:– Formales Modell TCat– Schranke des erwarteten

Fehlers

Thorsten Joachims 2002

Induktive logische Programmierung:– Obere und untere

Lernbarkeitsschranke gemäß LE, LB, LH

– Schnellster Beweiser für eingeschränkte Hornlogik

Jörg-Uwe Kietz 1996

Lernen von optimalen Merkmalsextraktionen aus Musikdaten (Mierswa, Morik 2005) Clustering für verschiedene Communities (Mierswa, Morik, Wurst 2006)

Theorieentwicklung

Wie entwickeln Kinder ihre Alltagstheorien? Wie beeinflussen Aussagen von Erwachsenen diesen

Prozess? Gibt es eine der Theorie inhärente Reihenfolge, in

der Begriffe erworben werden? Gibt es eine optimale Folge von Aussagen, die zum

Erwerb der wissenschaftlichen Theorie führt? Wie erfolgt der Übergang von einer Theorie zur

nächsten?

Empirische Untersuchung

Vosniadou, Brewer 1992, 1994– 60 Kinder im Alter von 6 – 11,

1., 3., 5. Klasse

– Fragen der Art “Where is the sun at night?”,“How does this happen?” undschematische Zeichnungen “Now make it so it is day for the person!”

– 9 Erklärungstypen (valide Modelle) Formalisierung Martin Mühlenbrock 1994

Zeichnungen von Kindern

Modell 1 Modell 4 Modell 5

Formalisierung eines Modells

Fakten:infinite(earth, down), infinite(earth, left),

infinite(earth, right)on(me, earth)opaque(cloud)stationary(me, e1), stationary(earth, e1) not

stationary(cloud, e1)night(me,s1)Regeln:

not between(Cloud, Sun, Me, S1),invisible(Sun, Cloud, Me, S2), state_seq(S1, E, S2), not stationary(Cloud, E) covers(Cloud, Sun, Me, E)

…

sun

cloud

me

earth

Fragen an das Modell

Fakten:infinite(earth, down), infinite(earth, left),

infinite(earth, right)on(me, earth)opaque(cloud)stationary(me, e1), stationary(earth, e1)not stationary(cloud, e1)night(me,s1)Regeln:

not between(Cloud, Sun, Me, S1),invisible(Sun, Cloud, Me, S2), state_seq(S1, E, S2), not stationary(Cloud, E) covers(Cloud, Sun, Me, E)

…

Fragen:

Where is the sun at night?

:- in(sun, X,Y,Z), night(me,Z)

in(sun, up, cloud, s1)

in(sun, up, earth, s1)

in(sun, up, me, s1)

Aussagen, die zum Widerspruch führen

Fakten:infinite(earth, down), infinite(earth, left),

infinite(earth, right)on(me, earth)opaque(cloud)stationary(me, e1), stationary(earth, e1)not stationary(cloud, e1)night(me,s1)Regeln:

not between(Cloud, Sun, Me, S1),invisible(Sun, Cloud, Me, S2), state_seq(S1, E, S2), not stationary(Cloud, E) covers(Cloud, Sun, Me, E)

in(sun, up, earth, s1)

in(sun, up, me, s1)

Input:

not opaque(cloud)

in (sun, left, earth, e0)

in (sun, right, earth, e1)

in (sun, down, earth, s1)

Simulation

Regeln:Bedeutungspostulatefür Prozesse, räumliche Relationen

Beispiele aus dem Alltag

FaktenModell 1

FaktenModell 9

FaktenModell 1’

FaktenModell 8’

Kontroll-modell 1’

Kontroll-modell 9

Widersprüche zu Modell 9

Minimale Menge wahrer Eingaben

Wissensrevision

Notwendig, wenn nicht mehr abgeleitet werden kann, dass man am Tag die Sonne sieht, nicht aber in der Nacht .

Ausgelöst durch Widersprüche zwischen Eingaben und Modell.

Behandelt durch Stefan Wrobels minimale Basisrevision (Wrobel 1994).

Die revidierten Modelle werden klassifiziert – welchem kindlichen Erklärungstyp entsprechen sie?

Mögliche Theorieentwicklungen

FaktenModell 1

FaktenModell 2

FaktenModell 3

FaktenModell 4

FaktenModell 5

FaktenModell 6

FaktenModell 7

FaktenModell 8

FaktenModell 9

Kosten der Übergänge

FaktenModell 1

FaktenModell 2

FaktenModell 3

FaktenModell 4

FaktenModell 9

Mehr als 4 Eingaben(6 – 9)

Jede Eingabe erfordert gleich viel Aktionen (Fakten löschen bzw. neu ableiten).

Nie mehr als 4 Eingaben erforderlich

FaktenModell 1

FaktenModell 2

FaktenModell 3

FaktenModell 4

FaktenModell 5

FaktenModell 6

FaktenModell 7

FaktenModell 8

FaktenModell 9

Moral von der Geschicht’

Magic number 4? Falsche Zwischenmodelle erleichtern das Lernen. Die Wahl eines günstigen (falschen)

Ausgangsmodells erleichtert das Lernen. Kognitionswissenschaft und Komplexitätstheorie

haben mehr gemeinsam, als man denkt!

Was wissen Sie jetzt?

Lernverfahren: Top Down Induction of Decision Trees Begriffslernen kNN “ SVM “ Least general generalization “ Generalisierte -Subsumtion “ RDT, RDT/dm Regellernen STT Lernen eines Verbands Apriori Finden häufiger Mengen FPgrowth “ Winepi (zeitlich) “ K-Means Clustering

Was wissen Sie jetzt? cont’ed

Lernaufgaben: Klassifikation Regression Häufige Mengen finden– Subgroup detection– Multikriterielle Optimierung Regellernen Clustering

Paradigmen der Lernbarkeit (Lerntheorie) Lernen als Suche Induktive Logische Programmierung PAC-learning Statistische Lerntheorie

Zu jedem Punkt gibt es noch viel mehr!

Was wissen Sie jetzt? cont’ed

AnwendungenBodeneignung für PflanzenAbverkauf von Artikeln Therapie in der Intensivmedizin (on-line monitoring) TextklassifikationGarantiefälle von Autos FilmbewertungenMobile RoboterKognitionswissenschaft

- Musik klassifizieren