Similarities between attribute grammars and logic programming especially in the context of machine learning

Lecturers:Kókai, G.
Coverage:2 SWS (4 ECTS)
Prerequisites:

Interessenten können sich per E-Mail bei kokai@informatik.uni-erlangen.de melden.

Topics:

Im Bereich der übersetzungsorientierten Sprachenimplementierung sind attributierte Grammatiken ein weit verbreiteter semantischer Formalismus. Attributierte Grammatiken können als eine Erweiterung der kontextfreien Grammatiken betrachtet werden, bei der die Attribute den Symbolen der Grammatik zugeordnet sind und die semantischen Regeln die Werte der Attribute definieren.

Die logische Programmierung hat ihren Ursprung im Bereich der automatischen Beweisführung. Ein logisches Programm besteht aus einer Menge von Axiomen oder Regeln, die die Beziehungen zwischen Objekten definieren. Die Berechnung eines logischen Programms ist die Ableitung von Folgerungen aus dem Programm. Ein Programm definiert eine Menge von Folgerungen, die seine Bedeutung sind. Die Kunst der logischen Programmierung liegt darin, kurze und elegante Programme zu konstruieren, die die gewünschte Bedeutung haben.

Das Ziel im ersten Teil des Seminars ist die Analyse der Beziehung zwischen attributierten Grammatiken und der Logik der Hornklauseln. Beide Formalismen wurden unabhängig voneinander und auf Grund verschiedener Motivationen entwickelt. Aber es gibt eine enge Beziehung zwischen der Notation eines definiten Programms und der Notation einer attributierten Grammatik. Diese gestattet uns, den einen Formalismus in den anderen zu transformieren und umgekehrt. Darüberhinaus wurden verschiedene Auswertungsschemata für attributierte Grammatiken entwickelt. Und es stellte sich heraus, daß einige dieser Schemata auch auf die Auswertung definiter Programme übertragen werden können. Ein weiterer Nutzen dieser "Übertragungstechnik" vom Bereich der attributierten Grammatiken in den Berech der logischen Programmierung (wenigstens beim Ansatz mittels Hornklauseln) ist, daß die Methoden für Korrektheitsbeweise von attributierten Grammatiken zu Methoden für Korrektheitsbeweise von definiten Programmen führen.

Im zweiten Teil des Seminars konzentrieren wir uns auf das Problem, wie attributierte Grammatiken und logische Programme gelernt werden können. Bei den Attribut-Wert Lernern (auch Vorschlagslerner genannt) wie ID3, AQ, LINUS, ASSISTANT, NEWGEM und CN2 werden die Objekte durch Ausdrücke über ihre globalen Eigenschaften beschrieben, d.h. durch Werte aus einer festen Menge von Attributen. Um Konzepte darzustellen, werden zum Beispiel Entscheidungsbäume in ID3 und wenn-dann Regeln in AQ benutzt. Die zwei wesentlichen Einschränkungen von Vorschlagslernern sind die begrenzte Ausdrucksfähigkeit der entsprechenden Formalismen und ihre begrenzte Fähigkeit, Hintergrundwissen zu berücksichtigen. Das Konzept, definite Programme zu lernen, basiert auf den Lernansätzen, die aus dem Bereich der induktiven logischen Programmierung (ILP) stammen. ILP ist eine neue Technik, die die Prinzipien des induktiven maschinellen Lernens mit der Darstellung logischer Programme kombiniert. Die neue Technik zielt darauf ab, allgemeine Regeln aufbauend auf bestimmten Beobachtungen und Hintergrundwissen zu schließen.

Die folgenden Themenbereiche werden behandelt:

  • Einführung in attributierte Grammatiken
  • Diskussion der Grundlagen logischer Programmierung unter Verwendung des Konzeptes des Ableitungsbaums
  • Beziehung zwischen attributierten Grammatiken und logischer Programmierung (Identifikation der Unterklassen attributierter Grammatiken und definiter Programme, die in einem wohl definierten Sinn äquivalent sind)
  • Ableiten von Beweistechniken für definite Programme aus Beweistechniken für attributierte Grammatiken
  • Eine kurze Stippvisiste über das mschinelle Lernen insbesondere induktive Lernalgorithmen
  • Lernen attributierter Grammatiken
  • Systeme zum Lernen attributierter Grammatiken (ID3, AQ, LINUS, ASSISTANT, NEWGEM and CN2)
  • Lernen definiter Programme
  • Systeme zum Lernen definiter Programme (FOIL, mFOIL, GOLEM, LINUS, Markus, MIS, MARVIN CLIENT CIGOL)
watermark seal