Künstliche Intelligenz Hornklauseln & Prolog Stephan Schwiebert WS 2007/2008 Sprachliche Informationsverarbeitung Institut für Linguistik Universität zu Köln Terminologie (A∧B∧C) → Rumpf einer Klausel E Kopf einer Klausel True → (A) Fakt/Tatsache Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorteile von Hornklauseln Einfach zu erzeugen, weil nur zwei (halbwegs intuitive) Typen von Klausel Einfach zu verketten Schnell (linear zur Größe der Wissensbasis) zu verarbeiten Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Inferenzalgorithmus für Hornklauseln Idee: Aus den bekannten Fakten (Zielklauseln) und den Implikationen der „Regeln“ (definite Klauseln) neue Fakten generieren und der Wissensbasis hinzufügen. Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Beispiel (Vorwärtsverkettung) Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 UND-ODER-Graph Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Algorithmus zur Vorwärtsverkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Prämissen von A∧ P → L Prämissen von A∧ B → L Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Vorwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Idee: Ausgehend von der „Frage“ (im Beispiel: Ist Q wahr?) den Wahrheitswert der betroffenen Regeln ermitteln. Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Rückwärts-Verkettung Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Hornklauseln: Fazit Hornklauseln ermöglichen es, eine Teilmenge der Aussagenlogik so zu behandeln, dass Die „Welt“ durch „Wissen“ und „Regeln“ (Implikationen) beschrieben werden kann Aus diesem Wissen neues Wissen generiert werden kann „Fragen“ beantwortet werden können Die Komplexität der Algorithmen in P liegt Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Prolog Die Programmiersprache Prolog („Programming in Logic“) basiert auf Hornklauseln, und besteht (fast) ausschließlich aus Implikationen und Fakten. Idee: Statt ein Problem durch ein selbst entworfenes Programm zu lösen, wird das Problem beschrieben und „löst sich selbst“. Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Beispiel: Sokrates in Prolog Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Beispiel: Sokrates in Prolog Prolog menschlich(sokrates). sterblich(X) :- menschlich(X). person(emma). weiblich(emma). elternteil(emma, otto). Formel m Hornformel m m⇒s ¬m ∨ s p w e p w e mutter(X) :- weiblich(X), elternteil(X, Y). w ∧ e ⇒ mu ¬(w ∧ e) ∨ mu ¬w ∨ ¬e ∨ mu Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Beispiel 2: Herakles Herakles war Mensch, aber unsterblich. Entsprechend muss die Definition von Sterblichkeit angepasst werden, z.B. so: sterblich(X) :- mensch(X), not(X=herakles). Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Syntax von Prolog Prolog-Fakten beschreiben Eigenschaften o.ä.. Es handelt sich um Klauseln ohne Rumpf: irgendwas. menschlich(sokrates). Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Syntax von Prolog Prolog-Fakten beschreiben Eigenschaften o.ä.. Es handelt sich um Klauseln ohne Rumpf: irgendwas. menschlich(sokrates). Prolog-Regeln sind Klauseln mit Rumpf und beschreiben Implikationen: sterblich(X) :- menschlich(X). Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Syntax von Prolog Prolog-Regeln können mehr als ein Element im Rumpf enthalten – diese werden durch Kommata per Konjunktion verbunden sterblich(X) :- menschlich(X), not(X = herakles). oder alternativ durch Semikola (Disjunktion) elternteil(X,Y) :- vater(X,Y); mutter(X,Y). Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Syntax von Prolog Durch Klein/Großschreibung des ersten Buchstabens wird unterschieden, ob es sich bei einem „Element“ um ein „Atom“ oder eine Variable handelt: % sokrates als Atom: menschlich(sokrates). % sokrates als Variable, die jeden Wert annehmen % kann: sterblich(Sokrates) :- menschlich(Sokrates). Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Syntax von Prolog Jede Klausel – egal ob Fakt oder Regel – muss mit einem Punkt beendet werden. Achtung: (SWI-) Prolog reagiert empfindlich auf „falsche“ Leerzeichen! Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 SWI-Prolog Ändern Sie die Einstellungen im Menu Settings>User Init File: Entfernen Sie den Kommentar (%) in der Zeile :- set_prolog_flag(editor, pce_emacs). Zum Erstellen eines neuen Programms: Speichern Sie eine neue Datei mit Endung .pl Schreiben Sie Ihr Programm und speichern Sie die Datei. Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 SWI-Prolog Wählen Sie beim ersten Ausführen „File->Consult“, anschließend Ihre Datei. Bei späteren Änderungen genügt der Punkt „Reload modified Files“. Erscheint die Ausgabe „c:/.... compiled in … sec“, ist alles ok, andernfalls ist ein Fehler in Ihrem Programm. Rufen Sie schließlich eines Ihrer Prolog-Prädikate auf, z.B. menschlich(sokrates). oder menschlich(X). Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Aufgabe: Stammbaum Abraham Kurt Brunhilde Peter Andrea Hans Petra Judith Otto Maria Gerd Theodor Uschi Silke Sebastian Paul Marianne Paula Torsten Kathi Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Aufgabe: Stammbaum Konstruieren Sie eine Wissensbasis, die den Stammbaum wiedergibt. Gehen Sie dabei nach folgendem Schema vor: elternteil(abraham,brunhilde). elternteil(abraham,theodor). … weiblich(brunhilde). weiblich(maria). … maennlich(X) :- not(weiblich(X)). … Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08 Aufgabe: Stammbaum Erstellen Sie Regeln für folgende Beziehungen: Vater oder Mutter Sohn oder Tochter Bruder oder Schwester Geschwister Opa oder Oma Tante oder Onkel Vorfahre Nachfahre Halbgeschwister (evtl. etwas schwierig!) Stephan Schwiebert - Sprachliche Informationsverarbeitung - WS 07/08
© Copyright 2024 ExpyDoc
