Local optimization for multi-context systems with constraint pushing

Abstract

Multi-Context Systeme (MCS) sind Formalismen, die es einzelnen Wissensbasen (den Kontexten) erlauben, mittels sogenannten Bridge Regeln verbunden zu werden. In dieser Arbeit konzentrieren wir uns auf heterogene nicht-monotone MCS von Brewka und Eiter, und entwickeln einen neuartigen verteilten Algorithmus zur Berechnung der Equilibria dieser MCS. Wir untersuchen bisherige Ansätze für verteilte MCS-Auswertung, die als Teil des DMCS Systems implementiert wurden. Darüber hinaus verwenden wir sogenannte Assoziationsregeln und Assoziationsregel-Extraktion aus dem Bereich des Data Mining. Keine der verfügbaren Techniken beantwortet die Frage der lokalen Optimierung innerhalb einer verteilten Evaluation, die die Motivation unserer Arbeit ist. Unser Ansatz des Constraint Pushings (genannt DMCS-SLIM) beruht auf der Kopplung von Optimierungsverfahren zur verteilten MCS Auswertung mit lokaler Assoziationsregeln-Extraktion. Wir beweisen Korrektheit und Vollständigkeit von DMCS-SLIM. Darüber hinaus präsentieren wir eine prototypische Implementierung, die wir zur empirischen Auswertung heranziehen. Wir führten ausgiebige Experimente durch und testeten unser System mit mehreren Laufzeit-Parametern, und verglichen unseren Ansatz mit bereits bestehenden. Wir beobachteten, dass unser Ansatz das Potenzial besitzt, die aktuellen Ansätze zu übertreffen.<br />

Multi-Context Systems (MCS) are formalisms that enable the inter-linkage of single knowledge bases called contexts, via bridge rules. In this thesis, we focus on Brewka and Eiter-style heterogeneous nonmonotonic MCS and develop a novel distributed algorithm for computing the equilibria of such MCS. We examine previous approaches for distributed MCS evaluation that have been implemented as part of the DMCS system. Moreover, the notion of association rules and the process of association rule extraction from the data mining field are recalled. None of the available techniques addressed the issue of local optimization within a distributed evaluation, which is the motivation behind our work. Our approach for local constraint pushing (DMCS-SLIM), relies on the coupling of some optimization techniques for distributed MCS evaluation with local association rules extraction. We prove DMCS-SLIM to be sound and complete. Furthermore, we present a prototypical implementation, which is used for empirical evaluation. We performed exhaustive set of experiments against several runtime parameters of our system as well as comparisons with existing approaches. We observed that our approach has potential to surpass the current approaches.