Klausur SS2009 Aufgabe 7 a)

Florian J.
Erstie
Erstie
Beiträge: 15
Registriert: 10. Apr 2010 10:48

Klausur SS2009 Aufgabe 7 a)

Beitrag von Florian J. »

Müssen bei dieser Aufgabe nicht auch noch die negierten Literale angegeben werden?


z.B. \+ q(X) und \+ q(Y)

So zumindest steht es im Skript und auch im Tutorium die eine Übung sah so aus.

Zudem wurde in der Tutoriums Aufgabe zum Select-And-Conquer Algorithmus auch noch der Gain für not male(X) berechnet, obwohl in der Datenbank als Hintergrundwissen nur male(X) gegeben war.

Ich finde das spricht auch noch mal dafür, das die Musterlösung der Klausur an dieser Stelle falsch ist.

Wie seht Ihr das ? Habe ich vielleicht einen Denkfehler gemacht?
Danke für Feedback.

milton
Neuling
Neuling
Beiträge: 5
Registriert: 25. Apr 2012 07:06

Re: Klausur SS2009 Aufgabe 7 a)

Beitrag von milton »

Ich denke die Negationen sind nicht mit aufgeführt, da in der Aufgabenstellung explizit nach der "nicht-rekursiven Defintion" gefragt ist. Das ist, meines Wissens nach, die klassische (aber auch schwächste) Mächtigkeit von Datalog, also ist auch keine Negation enthalten. SIehe Seite 35 der Datalog-Folien.

Wäre jedenfalls meine Erklärung

Florian J.
Erstie
Erstie
Beiträge: 15
Registriert: 10. Apr 2010 10:48

Re: Klausur SS2009 Aufgabe 7 a)

Beitrag von Florian J. »

Ah danke, ja das ergibt absolut Sinn.

martinl
Windoof-User
Windoof-User
Beiträge: 31
Registriert: 26. Apr 2012 20:40

Re: Klausur SS2009 Aufgabe 7 a)

Beitrag von martinl »

kurze Frage:
Was sind determinate Literale und wie hängen die mit dem positiven und negativen Head zusammen?
Aus der Erklärung der Folien werde ich nicht schlauer...

Florian J.
Erstie
Erstie
Beiträge: 15
Registriert: 10. Apr 2010 10:48

Re: Klausur SS2009 Aufgabe 7 a)

Beitrag von Florian J. »

Ich habe mir das so erklärt (bin mir aber auch nicht 100% sicher):

Determinate Literale sind Literale, die bezogen auf den Head der Regel (z.B. a(A):- ) neue Variablen einführen z.B. ( l(X,A,Y) , dann sind X und Y neue Variablen) und für diese Literale muss weiter gelten:

wenn es ein positiver Head ist ( a(A) ) dann darf es für alle möglichen Variablenkombination X,A,Y (die sich aus den Beispielen heraus ja ergeben) immer nur genau ein Fakt aus dem Hintergrundwissen geben, das die Kombination erfüllt.

z.B. wenn ich a(w) als Beispiel habe (sowohl pos. als auch neg. Beispiel müssen natürlich betrachtet werden) dann darf es nur ein Fakt l(...) geben z.B. l(q,w,e). (kein weiteres l(a,w,b) oder vergleichbar in der Faktenmenge)
Die Variablenbelegung muss also eindeutig sein für das gewählte A=w



wenn es ein negativer Head ist ( \+ a(A):- gleichbedeutend mit not ( a(A)) :- ) dann darf es für alle möglichen Variablenkombinationen höchstens eine Variablenkombination in den Fakten geben.


Determinate Literale verwendet FOIL, wenn es selbst kein Literal mehr auswählen kann, das einen ausreichenden GAIN ( 80% des theoretischen Optimus = alle positiven und kein neg. Beispiel abgedeckt) hat.
FOIL wählt also alle verfügbaren Determinaten Literale, die dann möglicherweise überhaupt keinen GAIN selbst liefern, aber wieder neue Variablen (X,Y) ins Spiel bringen. Diese dann von den anderen Literalen neu überprüft werden können, und über die man dann wieder auf einen besseren GAIN kommt.

FOIL löscht dann zum Schluss wieder alle nicht benötigten Determinaten Literale aus seiner Regel heraus, wenn es sie abgeschlossen hat (nicht benötigt = ich kann das Literal weglassen, ohne die Genauigkeit hinsichtlich der Abdeckung der Beispiele wieder zu verschlechtern).

Determinate Literale haben aufgrund der Eindeutigkeit der Variablenbelegung den Vorteil, dass sie den Suchraum nicht unnötigt aufblähen. Deswegen wählt man sie.

Sollte ich da etwas falsch verstanden haben bitte ich um Klarstellung.

Antworten

Zurück zu „Archiv“