Kolloquium/Ringvorlesung des Graduiertenkolleg Wissensrepräsentation

Autonomous agents reason frequently about preferences such as desires and goals. We propose a logic of desires with a utilitarian semantics, in which we study non-monotonic reasoning about desires and preferences based on the idea that desires can be understood in terms of utility losses (penalties for violations) and utility gains (rewards for fulfillments). Our logic allows for a systematic study and classification of desires, for example by distinguishing subtly different ways to add up these utility losses and gains. We propose an explicit construction of the agent's preference relation from a set of desires together with different kinds of knowledge. A set of desires extended with knowledge induces a set of `distinguished' utility functions by adding up the utility losses and gains of the individual desires, and these distinguished utility functions induce the preference relation.

Im Anfangsteil wird herausgearbeitet, dass die primäre Bedeutung von abduktiven Schlussmustern in ihrer Rolle als Suchstrategien für explanativ gehaltvolle Hypothesen liegt, und weniger in der Rolle von per se bereits wahrscheinlichkeitsverleihenden Schlussmustern. Das klassische Peirce-Schema des retrodiktiven Schliessens ist ein nützlicher Ausgangspunkt, aber viel zu eng. Das Konzept der "Inference to the Best Explanation" ist sehr breit, aber strategisch kaum nützlich. Im Anschluss werden eine Reihe strategisch nützlicher abduktiver Schlussmuster vorgestellt und diskutiert, mit einer abschliessenden Klassifikation und Übersicht, nämlich:

1. Fakten-Abduktion (1.1: Beobachtbare-Fakten-Abduktion, 1.2 Nichtbeobachtbare Fakten-Abduktion, 1.2.1 Historische-Fakten-Abduktion, 1.2.2 Theoretische Fakten-Abduktion, 1.3 Existentielle Abduktion 1. Stufe),
2. Gesetzes-Abduktion,
3. Existentielle Abduktion 2. Stufe (3.1 Mikrostruktur-Abduktion, 3.2 Analogische Abduktion, 3.3 Missing-Link-Common Cause-Abduktion, 3.4 Fundamentale Common Cause Abduktion, 3.4.1 Theoretische-Konzept-Abduktion, 3.4.2 erkenntnistheoretische Realitäts-Abduktion).

Seit etwa zwei Jahrzehnten gibt es ausgearbeitete logische Theorien der Wissensrevision. Solche Theorien entwickeln präzise Methoden für die Umgestaltung einer "Wissensbasis", oder genauer: eines Korpus von Daten, Überzeugungen oder Meinungen im Angesicht von (möglicherweise mit diesem Korpus inkonsistenter) Neuinformation. In den klassischen Modellen ging es um das unhinterfragte Akzepieren und Integrieren der Neuinformation in den bestehenden Korpus. Seit etwa fünf Jahren werden vermehrt Modelle für "nichtpriorisierte" Revisionen entwickelt, in denen sich der Agent gegebenenfalls rationalerweise weigern kann, die Neuinformation zu akzeptieren. Nach einer Einführung in diese Modelle wird im Vortrag eine alternative, gemeinsam mit Eduardo Fermé entwickelte Methode skizziert, mit der eine Meinungsänderung durch Vergleich der relativen Plausibilitäten verschiedener Sätze vorgenommen werden kann. Wie die vorgenannten Modelle ist diese Methode dabei rein qualitativ, d.h. sie macht keinen Gebrauch von (notorisch schwer zu interpretierenden) numerischen Werten.

Der Vortag behandelt Metakomplexitätstheoreme für ein bestimmtes Konzept von logischer Programmierung. Logische Programme, die in ein bestimmtes Schema passen, können mit einer durch die Theoreme garantierten Komplexität ausgeführt werden. Hierbei werden Entsprechungen zwischen fundamentalen logischen und algorithmischen Konzepten identifiziert und ausgenutzt. Es wird gezeigt, dass viele Algorithmen für Programmanalyse, aber auch Graphalgorithmen allgemein, in das Programmierschema passen. Für diese Algorithmen liefern bereits sehr abstrakte Formulierungen eine kompetitive Komplexität in derselben Größsenordnung, wie die besten bekannten Algorithmem besitzen.

The principle approach to the construction of approximating formulas is discussed. We suggest the generalized definition of normal forms in fuzzy logic and show the conditional equivalence between a formula and each of its normal form.

Based on this and the fact that most of the known approximating schemes are special cases of normal forms, we can say that fuzzy logic can serve as a logical foundation of the approximation theory.

In the lecture, the main concepts and results of fuzzy logic in narrow sense with evaluated syntax will be shortly presented. Among them, e.g. the concept of fuzzy theory, consistency, deduction theorem, completeness, Herbrand theorem, outlines of model theory. Possibilities for its use including the ability to model the sorites paradox will also be discussed.

Die Theorie der granularen Partitionen ist ein neues Werkzeug für die Wissensrepräsentation, das als Alternative zur Mengentheorie aufzufassen ist. Eine granulare Partition is eine Weise, ein gewisses Stück Wirklichkeit aufzuteilen, zu klassifizieren, oder kartenmäßig darzustellen. Beispiele von granularen Partitionen sind: die periodische Tabelle der chemischen Elemente, das Leipziger Telefonbuch, oder eine Landkarte von den USA. Partitionen können auf zwei Ebenen charakterisiert werden. Erstens, sind Partitionen Systeme von Zellen und Subzellen, zweitens haben sie sozusagen durch ihre Zellen ein Bezug zur Wirklichkeit. Wir spezifieren die Bedingungen der Wohlgeformheit für Partitionen, und wir definieren was es heisst, dass die Zelle einer Partition sich auf Objekte in der Wirklichkeit bezieht. Partitionen können dann nach verschiedenen Kriterien bewertet werden: u. a. nach dem Grad der Vollständigkeit ihrer Korrespondenz zum entsprechenden Stück Wirklichkeit und nach dem Grad, in dem sie die Ganz-Teil-Strukturen dieser Wirklichkeit abbilden können.

A novel logic program like language, weight constraint rules, is developed for answer set programming purposes. It generalizes normal logic programs by allowing weight constraints in place of literals to represent, e.g., cardinality and resource constraints and by providing optimization capabilities. A declarative semantics is developed which extends the stable model semantics of normal programs. A decidable fragment of the language allowing restricted use of variables and function symbols is introduced. For ground programs the computational complexity of the language is shown to be similar to that of normal programs under the stable model semantics. A simple embedding of general weight constraint rules to a small subclass of the language called basic constraint rules is devised. The language has been implemented in the Smodels (http://www.tcs.hut.fi/Software/smodels/) using a two level architecture. A front-end compiles general weight constraint rules to basic constraint rules for which an efficient search procedure computing stable models has been developed.

Ontologien haben sich als eine geeignete Methode zur Wissenskommunikation erwiesen. Mit ihrer zunehmenden Verwendung stellt sich jedoch das Problem der Anpassung überlappender Ontologien. In dem Vortrag wird die Methode FCA-Merge vorgestellt, die basierend auf der Formalen Begriffsanalyse einen strukturellen Ansatz zur Fusion von Ontologien bietet. Ausgehend von den Startontologien und einer Menge von Instanzen oder Dokumenten erzeugt FCA-Merge einen Begriffsverband, der dann interaktiv in die Zielontologie überführt wird.