Development of a Belief Merging framework for dlvhex

Abstract

In many fields it is common to work with several data sources.<br />This enables us to enlarge the total size of the knowledge base, leading to an information gain. If the sources are overlapping but not equivalent, this will allow the user to combine the advantages and use the most useful parts of each of the bases. Belief revision deals with the incorporation of new information into an existing belief base. During this process, the new entry has absolute priority, which means that it will be true in the revised base for sure. In contrast to that, belief merging deals with the aggregation of several sources. Unfortunately, naive union can lead to an inconsistent set of beliefs. Therefore the goal is to find a new base that is consistent and as similar to the existing ones as possible, according to some distance function. A practical application is the merging of medical data about a patient that were collected by different health institutes. But knowledge fusion is not only useful in medical settings. A very common task is ontology integration in the Semantic Web or the incorporation of employee or customer databases in case of company fusions. Other examples include the union of multidimensional index structures and the combination of classifiers that were trained upon disjoint sets of samples. In this thesis our case study will be judgment aggregation, which is a topic from the field of social choice theory, where the judgments of several individuals need to merged into a group decision. The open-source software dlvhex is a reasoner for an extension of logic programs under the answer-set semantics, called hex programs. Basically it provides two extensions, namely higher-order atoms and external atoms. Higher-order atoms enable the programmer to use variables instead of symbols as predicates. External atoms allow a bidirectional communication between logic programs and external sources of computation like relational databases, XML files and RDF ontologies. For this purpose, dlvhex can be extended with user-defined plugins provided as shared object libraries. In this thesis, the possibility of writing plugins will be exploited to implement a framework for belief merging tasks. The input is a set of hex programs that deliver sets of answer sets which represent the belief sources to be merged. Internally these programs can evaluate external atoms to access arbitrary data sources. In the merging task description the user defines how to combine these sources. For this purpose he or she can use merging operators that are applied on belief bases or recursively on the result of previous operator applications. This leads to a tree-like structure, where the leaf nodes are belief bases and the inner nodes are merging operators. This is very similar to the way we evaluate arithmetic expressions. The final result of a merging task is the result of the topmost operator. In the literature there were already defined operators for belief revision and update tasks. This idea can easily be generalized, such that not only a single formula is incorporated into an existing knowledge base, but complete belief bases are fused. However, to keep the framework flexible the user can not only select among a fixed set of operators, but can also implement custom ones that can be dynamically added to the framework. This makes the framework useful for any kind of merging task as long as suitable operators are provided. The actual benefit of the framework is that it takes the burden of repeating routine tasks from the user. The information flow through the different merging operators is managed automatically, so that the user can concentrate on the most interesting and relevant part, namely the development and optimization of the merging procedures. Further the framework allows to restructure the merging plan (i.e., the selection of operators and order of their applications) in a user-friendly merging language. This way it is possible to experiment with several settings and compare the results without manually reimplementing the flow of information after each modification.