Inconsistency in multi-context systems : analysis and efficient evaluation

Abstract

Multi-Kontext-Systeme sind ein Formalismus zur Repräsentation von Systemen, die aus mehreren wissensbasierten Systemen (Kontexten) bestehen.<br />Wissensaustausch zwischen Kontexten wird in Form von Regeln (Bridge Rules) modelliert; diese Regeln fügen Formeln zur Wissensbasis eines Kontexts hinzu, wenn bestimmte Aussagen von anderen Wissensbasen akzeptiert werden (oder nicht akzeptiert werden). Als Beispiel betrachten wir ein Spitalsinformationssystem, welches Patienten- und Labordatenbanken sowie ein Expertensystem für Behandlungsvorschläge vernetzt. In einem derartigen wissensverarbeitenden System kommt es durch unerwartete Interaktionen zwischen Kontexten und Regeln leicht zu einer Inkonsistenz des Gesamtsystems. Beispielsweise kann ein PatientInnendaten-Import dem Inhalt der Labordatenbank widersprechen, oder eine PatientInnenallergie kann sämtliche Behandlungsmöglichkeiten ausschließen. Globale Inkonsistenz eines Systems hat zur Folge, dass keine sinnvollen Informationsabfragen an das System mehr möglich sind. Bestehende Verfahren zur Inkonsistenzbehandlung ignorieren oder entfernen Inkonsistenz oder sie betrachten Inkonsistenz als spezifischen Wahrheitswert im System.<br />In dieser Arbeit erörtern wir einen neuen Ansatz, der Inkonsistenzen analysiert, automatisches Schlussfolgern über dieser Analyse zulässt, und letztendlich die Möglichkeit bietet, au- tomatische oder benutzergestützte Systemreparaturen durchzuführen. Vor dem Hintergrund der praktische Anwendbarkeit unserer Verfahren betrachten und bewerten wir stets deren Effizienz. Wir untersuchen unsere Ansätze auf theoretischer Ebene mithilfe von formalen Methoden der Informatik, im Speziellen aus dem Gebiet der Logikorientierten Programmierung. Wir realisieren unsere Verfahren in Software Prototypen, führen empirische Untersuchungen durch um die Effizienz dieser Prototypen zu messen, und untersuchen mögliche Optimierungen.<br />Auf theoretischer Ebene ist das Hauptergebnis dieser Arbeit die Einführung von zwei neuen formalen Begriffen für die Analyse von Inkonsistenzen in Multi-Kontext-Systemen: Diagnose und Inkonsistenzerklärung. Diese Begriffe charakterisieren Inkonsistenz über Mengen von Bridge Rules, welche die Inkonsistenz verursachen. Diagnosen zeigen mögliche Reparaturen des Systems auf, während Inkonsistenzerklärungen unabhängige Inkonsistenzen in einem System voneinander abgrenzen. Wir zeigen formale Eigenschaften dieser neu eingeführten Begriffe und stellen ein Verfahren vor, das es ermöglicht, sogar bei unvollständiger Information über ein System dessen Inkonsistenz zu analysieren. Weiters beschreiben wir die neue Sprache IMPL zur Spezifikation von Strategien für Inkonsistenzmanagement von Multi-Kontext-Systemen. Diese Sprache erlaubt zu spezifizieren, welche Inkonsistenzen auf Basis einer Inkonsistenzanalyse automatisch repariert werden sollen (beispielsweise durch Ignorieren eines geringfügig abweichenden Geburtsdatums) und welche Inkonsistenzen einem menschlichen Benutzer (beispielsweise einem Arzt) vorgelegt werden müssen, um über deren Reparatur zu entscheiden.<br />Ein wichtiges empirisches Ergebnis dieser Arbeit ist die Realisierung der Inkonsistenzanalysebegriffe im MCS-IE Software Prototypen, der Diagnosen und Inkonsistenzerklärungen auf der Basis von HEX-Programmen - ein Formalismus der logische Programmierung mit externen Berechnungen erweitert - berechnet. Um die Skalierbarkeit von MCS-IE und HEX zu ver- bessern, erstellen wir ein neuartiges Berechnungsframework für HEX-Programme. Wir führen dieses Framework formal ein, beweisen dessen Korrektheit, und beschreiben eine empirische Untersuchung, die zeigt, dass unser neuen Berechnungsframework Effizienzvorteile gegenüber dem vorher existierenden Verfahren aufweist. Die Inkonsistenz-Management-Methoden, welche wir in dieser Arbeit vorstellen, ermöglichen es, den Betrieb von verteilten wissensbasierten Systemen robuster zu machen. Unser ver- bessertes Verfahren zur Evaluierung von HEX-Programmen erweitert die Anwendbarkeit von HEX in der Praxis und wirft neue wissenschaftliche Fragestellungen im Bereich der effizienten Auswertung von logischen Programmen auf.<br />

Multi-Context Systems are a formalism for representing systems that consist of multiple knowledge-based systems (contexts). Knowledge exchange between contexts is represented in the form of bridge rules, which are rules that add formulas to knowledge bases if certain beliefs are accepted (or not accepted) at certain contexts. As an example, we consider a hospital information system that links patient and laboratory databases with a decision support system for suggesting therapies. Inconsistency of such a system can easily arise due to unexpected interactions caused by bridge rules and contexts, for example a wrong birth date could make the lab database inconsistent, and a patient allergy might eliminate all treatment options for a patient, making the global system inconsistent. As a consequence, the system can no longer provide meaningful answers to requests. Existing approaches for dealing with inconsistency mostly ignore or remove inconsistency or they regard inconsistency as a special truth value in the system.<br />In this thesis, we aim at a new approach that allows for analyzing inconsistency and reasoning about it, and eventually allows for repairing inconsistency with or without support from a human operator. To facilitate practical applicability, we put a particular emphasis on efficiency. We use formal methods of computer science, in particular from logic programming, to investigate these problems on a theoretical level. We realize formal results in a software prototype, conduct empirical experiments to validate efficiency, and investigate potential optimizations. As a main theoretical result we obtain two novel formal notions for analyzing inconsistency in multi-context systems: diagnoses and inconsistency explanation. These notions characterize inconsistency in terms of sets of bridge rules that cause inconsistency. Diagnoses provide possible repairs of the system, while inconsistency explanations separate independent reasons for inconsistency in one system. We establish formal relationships between these notions, and show how they can be approximated if parts of the system are hidden from our observations. Furthermore we describe a novel policy language for managing inconsistency in multi-context systems (IMPL) which allows for analyzing inconsistencies and for specifying in a declarative way which inconsistencies shall be repaired automatically (e.g., by ignoring a slightly differing birth date) and which shall be presented to a human user (e.g., a doctor, in case of the allergy mentioned above) for deciding how to deal with them.<br />A main empirical result of this thesis is the realization of our inconsistency analysis notions in the MCS-IE prototype software, which uses HEX programs - a formalism that extends logic programming with external computations - as underlying formalism. To improve scalability of MCS-IE and of HEX , we introduce a novel flexible evaluation framework for HEX programs, formally show its correctness, and describe an empirical study on the performance benefits compared to the previous state-of-the-art in HEX evaluation.<br />Using our inconsistency management methods it is possible to make operation of distributed knowledge-based systems more robust. Our improved HEX evaluation formalism widens applicability of HEX for practical reasoning tasks and prompts additional research on the subject of efficient evaluation of logic programs.