Kolloquium/Ringvorlesung des Graduiertenkolleg Wissensrepräsentation

The theory of preferential consequence relations has been investigated extensively in the classical context, where copies of classical valuations serve as the terms of the preference relation. The first purpose is to extend the theory to preferential consequence relations in certain three/four-valued contexts, well-known as the paraconsistent logics J3 and FOUR. We give characterizations of several families of preferential consequence relations in these two contexts. Our second and main purpose is to investigate a qualified version of preferential consequence, which we call preferential-discriminative consequence. This is defined to hold between a set T of formulae and formula a iff T |~ a but NOT T |~ neg a, where |~ is the plain relation. We provide characterizations of several families of such preferential-discriminative consequence relations for all of the classical, three, and four-valued contexts.

Präferenzen sind im beruflichen und privaten Leben allgegenwärtig und spielen für viele persönliche Entscheidungen eine zentrale Rolle. Dies gilt in gleichem Maße für Anwendungen des elektronischen und mobilen Handels über das Internet, wobei die Personalisierung von Suchmaschinen und Dienstleistungen einen wesentlichen Faktor darstellt. Zu seinem Leidwesen wird aber wohl jeder Internetbenutzer schon öfters erfahren haben, dass heutige Suchmaschinen und E-Dienstleistungen mit Präferenzen nicht richtig umgehen können, was sich u.a. in leeren Antwortmengen oder der Überflutung mit irrelevanten Suchergebnissen äußert.

Unter dem Motto It?s a Preference World befasst sich der Lehrstuhl bereits seit längerem intensiv mit dieser Problematik. Der Vortrag stellt wesentliche Resultate dieser Präferenzforschung vor: Das Präferenz-Modell und Aspekte eines Preference Engineering, Designprinzipien für Präferenz-Abfragesprachen und Preference SQL, sowie Aspekte der Präferenz-Abfrageoptimierung bei loser und enger Kopplung mit SQL-Datenbanksystemen. Der richtige Umgang mit Präferenzen ermöglicht zudem bessere kooperative Datenbanksysteme: Der Prototyp der multimodalen elektronischen Verkäuferin COSIMA zeigt neue Perspektiven zu innovativen Anwendungen im Bereich der präferenzgesteuerten Mensch-Maschine-Interaktion.

Expected utility is the dominant decision-theoretic foundation for fields such as finance and game theory. Likewise, in the context of AI, expected utility is the foundation for single- and multi-agent graphical models such as Influence Diagrams, Game Networks and Multi-Agent Influence Diagrams. Despite the intuitive appeal of the underlying preference axioms, and the convenience of its linear framework, expected utility has been challenged since its inception by a number of paradoxes and empirical violations. In this talk I will survey the dominant paradoxes, and introduce a tractable generalization of expected utility which overcomes them. I will then discuss the applicability of this generalized framework to game theory and AI.

Answer Set Programming (ASP) is a problem solving paradigm, originally founded on the stable model semantics of logic programs - a nonmonotonic logic. Many combinatorial problems and many classical AI problems can be elegantly formulated in ASP and solved by well-engineered reasoning engines, such as SMODELS and DLV. Still, there exist interesting problems (such as scheduling problems) whose solution with the standard methods requires too many resources - especially memory. The reason is that the state-of-the-art answer set solvers first compute the ground instantiation of the program, that may be significantly larger than the input program.

In this seminar we report preliminary results on a hybrid technique, by which part of the program needs not be grounded and is handled by a constraint solver, instead. We report encouraging experimental results showing that the hybrid technique may significantly increase the size of the problem instances that can be actually solved.

Current systems for reasoning with large knowledge bases having ontologies of thousands of concept types and millions of facts and axioms have encountered serious difficulties: they are brittle, difficult to extend to new subjects, and take a long time for complex reasoning. Restricting the logic to a smaller, more tractable subset can often improve the speed, but it does not make the system less brittle or more extensible. Furthermore, it makes certain kinds of questions impossible to ask. This talk presents some new computational methods that greatly improve the efficiency of searching for relevant information. They enable analogy finding, which takes N-cubed time with the older algorithms, to be performed in (N log N) time, where N is the number of assertions in the knowledge base. Analogies can be used to support less brittle, more extensible case-based reasoning, and they can also be used to align independently developed ontologies. The same methods that improve the speed of analogy finding can be used to improve other methods of reasoning, including induction, deduction, and abduction.

Words are just the "tip of the iceberg" of a wider semantic structure representing the language. Deriving automatically such a structure from corpora is then a key issue in Computational Linguistics. Domain Models allows us to represent lexical ambiguity a nd variability by inducing soft clusters of terms from corpora. We exploit Domain Models to define a generalized similarity function among texts, name ly the Domain Kernel, that can be profitably used in a Support Vector Machine classifi cation framework. The Domain Kernel allows us to define semi-supervised learning sche ma, in which both labeled and unlabeled data are provided for training. Experiments performed in different tasks (i.e. Word Sense Disambiguation, Text Categor ization, Term Categorization. Cross Language Text Categorization) and in different lan guages show that our learning methodology achieves the state-of-the-art performance wh ile reducing substantially the amount of labeled training data.

Asynchronous cellular automata (ACAs) provide a model for concurrent systems whose components communicate with one another. They have been introduced originally by Zielonka in the framework of Mazurkiewicz traces and were generalized by Droste et al. to run on pomsets without autoconcurrency. ACAs could be shown to be expressively equivalent to existential monadic second-order (EMSO) logic relative to traces and CROW-pomsets, which are subject to an axiom that considers concurrent read and exclusive owner write. As ACAs can process an event only depending on its past, their expressive power is generally incomparable with that of first-order logic.

Another approach of recognizing sets of partial orders and graphs is that of graph acceptors as introduced by Thomas. They are known to be exactly as expressive as EMSO logic for arbitrary classes of graphs that have bounded degree. While graph acceptors have access to the future of an event, however, they lack an operational behavior.

We propose asynchronous cellular automata with types (ACATs), which combine the models of asynchronous cellular automata and graph acceptors and allow a uniform embedding of many existing models of concurrency. In particular, an ACAT has (limited) access to the future to articulate communication requests. ACATs turn out to have the same expressive power as EMSO logic relative to any class of pomsets and dags without autoconcurrency.