Dao-Tran, M. (2014). Distributed nonmonotonic multi-context systems : algorithms and efficient evaluation [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2014.22501
Knowledge representation and reasoning; Multi-context systems; Distributed reasoning; Heterogeneity
en
Abstract:
Heterogene nichtmonotone Multi-Kontext Systeme (MCSs) sind eine Generalisierung einer Reihe von Arbeiten von John McCarthy über die Formalisierung von Kontexten in der Künstlichen Intelligenz, die bis in die 80er Jahre reichen. Sie sind ein Formalismus zur Repräsentierung von Systemen von mehreren (möglicherweise nichtmonotonen) wissensbasierten Systemen (Kontexte). Das Wissen zwischen Kontexten wird mittels Brückenregeln (bridge rules) ausgetauscht. Diese Form von Regeln erlaubt, Wissen eines Kontextes zu erweitern, je nachdem, ob gewisse Überzeugungen (nicht) bei gewissen Kontexten akzeptiert werden. Obwohl nahezu alle Formalisierungen von Systemen mit mehreren Kontexten grundsätzlich auf Verteilte Systeme abzielen, existieren keine echten verteilten Algorithmen zur Evaluierung ihrer Semantiken aufgrund mehrerer Hürden: (i) die semantische Abstraktion der Kontexte mit Hilfe von Überzeugungsmengen (belief sets) verhindert den Zugriff in den lokalen Evaluationsprozess von Kontexten; (ii) Informationsabgrenzung und Sicherheitsaspekte sperren den Zugriff auf die Kontext Theorien; (iii) die komplette Systemtopologie konnte einem partikularen Kontext unbekannt sein, was wiederum das aufgeteilte Evaluieren verhindert; und (iv) die Brückenregeln zweier Kontexte können aufeinander verweisen, was ein zyklisches System erzeugt, welches mit Vorsicht handzuhaben ist. Um diese Herausforderungen zu meistern, zielen wir auf das Entwerfen und Realisieren von echten verteilten Algorithmen zur Evaluierung von MCSs. Durch bewusste Annäherung an diese Probleme, haben wir mit einem einfachem Algorithmus angefangen, der sich hauptsächlich auf verteilte Aspekte konzentriert, das heisst, dem Übertragen von Nachrichten und dem Brechen von Zyklen. Danach untersuchten wir mögliche Optimierungen auf der Meta-Ebene, welche die globale Topologie des Systems aufbereiten, um den Informationsaustausch zu reduzieren. Einen Schritt vorausgehend, erforschen wir die stufenweise Auswertung von MCS, bei denen nicht alle Ergebnisse auf einmal zurückgegeben werden, sondern auf kontinuierliche Weise. Auf einem weiteren explorativen Zweig entwickelten wir einen Algorithmus zur Konfiguration dynamischer MCSs auf ursprüngliche MCS. Als theoretische Resultate dieser Dissertation entwickelten wir Konzepte, die die Evaluierung von MCSs unterstützen, wie etwa Import Nachbarschaft, Import Abschluss, Import Schnittstelle, partielle Überzeugungsmengen und Gleichgewichte, Schleifenformeln für MCSs, Zerlegung von MCSs, etc. Basierend auf diesen Konzepten, schlugen wir unterschiedliche Algorith- men zur Evaluierung von MCSs vor, nämlich DMCS, DMCSOPTsowie DMCS-STREAMING. Die ersten beiden korrespondieren zur einfachen und Topologie-optimierten Evaluierung. Der letzte Algorithmus stellt eine neue Strategie vor, in welcher sowohl DMCS als auch DMCSOPT eingesetzt werden kann zur Berechnung partieller Gleichgewichte auf kontinuierlicher Weise. Die empirischen Resultate der Dissertation umfassen die Realisierung aller vorgeschlagenen Algorithmen in prototypischen Implementierungen. Weiters haben wir eine sorgfältige experimentelle Evaluierung durchgeführt, um die implementierten Algorithmen auf unterschiedlichen Aspekten zu vergleichen. Bei der Analyse der experimentellen Resultaten haben wir eine kurze Richtlinie entwickelt, um den geeigneten Algorithmus und Laufmodus in einer bestimmten Situation zu wählen, welcher durch eine Parameterkonfiguration bestimmt wird. Neben den Hauptresultaten haben wir eine Anzahl interessanter zukünftiger Studien ausgearbeitet, die aus den Erfahrungen des Dissertationsprojekt gewonnen wurden, einschliesslich, aber nicht beschränkt auf Konfliktlernen für die Algorithmen, Anfragebeantwortung von MCSs, sowie Potentiale für verteilte heterogene Datenstromsschlussfolgerung.
de
Heterogeneous Nonmonotonic Multi-Context Systems (MCSs) are a generalization of a series of works on formalizing contexts in AI dating back in the 80s by John McCarthy. As such, they are a formalism for representing systems consisting of multiple (possibly nonmonotonic) knowledge-based systems (contexts). Knowledge between contexts is exchanged via bridge rules, a form of rules that allow to augment knowledge at a context depending on whether certain beliefs are accepted (not accepted) at certain contexts. Although virtually all formalizations of systems of multiple contexts are inherently targeted for distributedness, no truly distributed algorithms for evaluating their semantics exist, due to several obstacles: (i) the semantic abstraction of contexts to belief sets hinders interference with the local valuation processes in contexts; (ii) information hiding and security aspects disable access to the context theories themselves, merely interfaces to the belief sets are provided; (iii) the complete system topology might be unknown to a context, which hinders decomposed evaluation; and (iv) the bridge rules of two contexts may refer to each other, thus creating cyclic systems that must be handled with care. Coping with these challenges, we aim at designing and realizing truly distributed algorithms for evaluating MCSs. Deliberately approaching the issues, we started with a basic algorithm that mainly concentrates on the distributed aspects, i.e., dealing with transferring messages and breaking cycles. Then, we looked into possible optimizations at the meta level which preprocesses the global topology of the system to reduce information exchange. Taking one more step forward, we investigated gradually evaluating MCS where not all results are returned at once but in a streaming fashion. On an additional explorative branch, we designed an algorithm to configure dynamic MCSs into the original ones. As the theoretical results of this thesis, we came up with notions to support evaluation of MCSs, such as contextsimport neighborhood, import closure, import interface, partial belief states and equilibria, loop formulas for MCSs, decomposition of MCSs, etc. Based on these notions, different algorithms to evaluate MCSs were proposed, namely DMCS, DMCSOPT, and DMCS-STREAMING. The first two correspond to the basic and topology-optimized evaluation. The last one introduces a new strategy in which both DMCS and DMCSOPT can be deployed to compute partial equilibria in a streaming fashion. As the empirical results of the thesis, we have realized all proposed algorithms in a proto- type implementation. Furthermore, we did a thorough experimental evaluation to compare the implemented algorithms on different aspects. And by analyzing the experimental results, we give a brief guideline on choosing the appropriate algorithm and running mode in a particular situation, determined by the parameter setting. Beside the main results, a number of interesting future works were also revealed from experiences gained within the thesis project, including but not limited to conflicts learning for the algorithms, query answering in MCSs, and a potential for distributed heterogeneous stream reasoning.