Thema

Material

Übung

 

 

 

Logisches Programmieren
Datalog
Operatoren und Fixpunkte

“Deductive Databases” (verteilt), Skript

Exercise 24.1-24.5, Seite 842, ohne SQL (also einfach in Datalog schreiben).

Begrifflernen

ILP-Buch, Kap. 1,2

Uebung 2 siehe unten

ILP: logische Grundlagen

ILP-Buch, Kap. 3

keine Uebung heute

FOIL und verwandte Systeme

ILP-Buch, Kap. 4, 5

siehe Uebung 3 unten

Anwendungen des ILP, umgekehrte Resolution

ILP-Buch, Kapitel 6.1, 6.2, 6.3, 6.5, 12, 14.1

siehe Uebung 4 unten

Anwendunges des ILP, Progol.

ILP-Buch, Kap. 3, “A Tutorial Introduction to Cprogol 4.4” (verteilt)

 

ILP und Auswerten von Datenbanken (data mining, knowledge discovery)

Material aus “Learning Relational Models” (verteilt)

Kap.4.1, 4.2, 5.1,5.2, 5.4,5.5, 5.6 (minus 5.6.3), 5.7.

 

 

 

Uebung 2. Wird besprochen am 2. Juni.

 

1. Betrachten Sie den Hypothesenraum im Lernproblem mit der Klasse EnjoySport. Wir haben die folgenden Attribute:

 

Attribut

moegliche Werte

 

 

Sky

Sunny, Cloudy, Rainy

Temp

Warm, Cold

Humidity

Normal, High

Wind

Strong, Weak

Water

Warm, Cool

Forecast

Same, Change

 

Jede Hypothese ist eine Konjunktion von Beschraenkungen von der Form Attribut = wert oder Attribut = ?. Zum Beispiel haben wir die Hypothese <Temp = Warm and Wind = Weak and Water = ?>. Auszerdem erlauben wir die leere Hypothese, die alle Instanzen als negativ klassifiziert.

 

Wie grosz ist der Hypothesenraum (d.h., wieviele Hypotheses enthaelt er?). Allgemein gesprochen, wie vergroeszert sich der Hypothesenraum, wenn wir ein neues Attribut A mit k moeglichen Werten hinzufuegen?

 

2. Das AI Exploratorium bietet eine Java-Benutzeroberflaeche fuer ID3, ein Algorithmus, der Entscheidungsbaeume von Daten lernt. Sie werden ein Java plug-in brauchen; fuer einen PC gibt es den bei Netscape. Die Grundideen von ID3 sind die Vorlaeufer von FOIL und CN2, zwei wichtigen Systemen fuer ILP. Bringen Sie ID3 zum Laufen, und experimentieren Sie: a) mit dem EnjoySport Problem b) mit demselben Problem, aber weniger Daten, c) mit demselben Problem und mehr Daten, d) mit einem anderen Lernproblem (z.B. play ball).

 

Uebung 3. Wird besprochen am 16. Juni.

 

1. In Mitchells Buch, Kapitel 3, Seite 77/78, Exercise 3.2, 3.4 (a)

 

2. Betrachten Sie die folgenden Klauseln.

 

A: Mother(x,y) :- Father(x,z), Spouse(z,y).

B: Mother(x, Louise) :- Father(x, Bob), Spouse(Bob, y), Female(x).

 

Zeigen Sie, dasz A die Klausel B theta-subsumiert.

 

Betrachten Sie die folgenden Klauseln.

 

A: Elephant(father_of(x)) :- Elephant(x).

B: Elephant(father_of(father_of(y))) :- Elephant(y).

 

a. Impliziert die Klausel A die Klausel B (d.h., ist es der Fall dasz Klausel B wahr ist, sofern Klausel A wahr ist?).

b. Theta-subsumiert die Klausel A die Klausel B?

 

Uebung 4. Praktische Uebungen mit FOIL. Wird besprochen am 23. Juni.

 

Foil unter UNIX installieren

 

1. Foil Shell-Datei herunterladen -> Datei "foil6_sh"

 

2. Beim UNIX prompt "sh foil6_sh". Das sollte alle Dateien entpacken.

 

3. Beim Unix prompt "make foilgt".

 

4. Zum Testen: "foil6 -n -v3 < member.d".

 

Weitere Informationen in den Dateien foil6_sh, README und MANUAL.

 

Zwei oder drei praktische Experimente mit FOIL

 

a. Experimentieren Sie mit der member.d Datei.

-         Verlegen Sie einige Daten von Trainingsdaten zu Testdaten und schauen, welche Regeln gelernt werden und ob die Testergebnisse genauso gut sind wie mit mehr Daten.

b. Experimentieren Sie mit einer anderen Datei.

-         Sie koennten eine von den anderen .d Dateien zum Laufen bringen und das Ergebnis interpretieren, z.B. die sort.d Datei zum Sortierproblem. Sind die Regeln vollstaendig und korrekt oder brauchen wir noch mehr Trainingsbeispiele?

-         Als Alternative koennten Sie einen Datensatz von Anfang erstellen, zum Beispiel das Experiment zu den Familiendaten von 16.1 reproduzieren oder unser Play Tennis von Foil analysieren lassen (ein Datensatz ist auf den Folien beschrieben und auch im AIExploratorium abrufbar, s.o.). Wie verhaelt sich das Ergebnis von FOIL zu dem von ID3 (siehe Folien oder AI Exploratorium)?

 

Uebung 5. Praktische Uebung mit Progol. Etwas Theorie zu FOIL. Wird besprochen am 30. Juni.

 

Progol unter Unix installieren.

 

1. anonymous ftp to ftp://ftp.cs.york.ac.uk/pub/ML_GROUP/progol4.4/

2. Die 5 Dateien herunterladen in ein Verzeichnis, z.B. progol4.4.

3. Beim Unix prompt: „sh expand.sh“.

4. Dann sollten Sie 4 neue Verzeichnisse sehen: examples4.2, example4.4, man, source.

5. „cd source“, „progol“ -> Progol sollte laufen.

6. Zum Testen: kopieren Sie die Datei: examples4.2/aunt.pl in das Verzeichnis source. Dann geben Sie ein „progol aunt“. Die Ausgabe sollte so sein, wie sie im Aufsatz von Muggleton und Firth beschrieben ist. Der Aufsatz von Muggleton und Firth ist auch in der Datei man/tutorial4.4.ps zu finden. Zu empfehlen sind auch die folgenden Dateien: README und die Anleitung fuer Progol 4.2. Diese Anleitung ist um einiges einfacher zu lesen als der Aufsatz von M und F und bringt noch mehr Beispiele.

 

Progol Uebungen

 

1. Bringen Sie den Befehl „progol aunt.pl“ zum Laufen. Verfolgen Sie die Bearbeitung dieser Datei (Tabelle 7.2 in M und F):

a. Was ist das erste positive Beispiel, das bearbeitet wird?

b. Was ist der „most specific clause“ fuer dieses Beispiel?

c. Progol untersucht vier Klauseln, die die spezifischste Klausel verallgemeinern. Was sind die vier Klauseln? Bestaetigen Sie, dasz die spezifischte Klausel tatsaechlich diese vier Klauseln theta-subsumiert.

d. Die Ausgabe von Prolog ist schlieszlich aunt_of(A,B) :- parent_of(C,B), sister_of(A,C). Fuer die vier Parameter p_s, n_s, c_s, h_s, f_s, die auf S.175 in M&F definiert werden, finden Sie die Werte fuer aunt_of(A,B) :- parent_of(C,B), sister_of(A,C) (mit Hilfe der Ausgabe von Progol). Fuer die Parameter p_s, n_s, vollziehen Sie nach, wie es zu diesen Werten kommt.

e. Zum Vergleich mit FOIL: Fangen wir mit der allgemeinen Klausel aunt_of(A,B) an. Was ist der FOIL-Gain von aunt_of(A,B) :- parent_of(C,B) im Vergleich zu aunt_of(A,B)? Was ist der FOIL-Gain von aunt_of(A,B) :- parent_of(C,B), sister_of(A,C) im Vergleich zu aunt_of(A,B) :- parent_of(C,B)? Progol laeuft mit „posonly“ – nehmen Sie also zum Vergleich fuer FOIL an, dasz die Welt abgeschlossen ist (closed world assumption).

 

2. Bringen Sie den Befehl „progol grammar.p“ zum Laufen. Achtung – diese Datei ist anders als die, die in M&F besprochen wird. Verfolgen Sie die allgemeine Struktur der Bearbeitung:

a. Welche drei positiven Beispiele werden bearbeitet?

b. Fuer jedes dieser drei positiven Beispiele, was ist die spezifischste Klausel?

c. Welche positiven Beispiele deckt die erste Klausel ab, die Progol findet (aunt_of(A,B) :- parent_of(C,B)), welche positiven Beispiele die zweite, und welche die dritte?