Belief merging, also called belief fusion or propositional belief merging, is a process in which an individual agent aggregates possibly conflicting pieces of information, expressed in logical formulae, into a consistent knowledge-base. Applications include combining conflicting sensor information received by the same agent (see sensor fusion) and combining multiple databases to build an expert system. [1] [2] [3] [4] It also has applications in multi-agent systems.
In the combination approach, we take the union of the knowledge bases (a finite set of logical formulas). If the union is consistent, we are done. Otherwise, we select some maximal consistent subset of it. Baral, Kraus, Minker and Subrahmanian [5] [2] present algorithms for combining knowledge-bases consisting of first-order theories, and to resolve inconsistencies among them.Subrahamanian [3] presents a uniform theoretical framework, based on annotated logics, for combining multiple knowledge bases which may have inconsistencies, uncertainties, and nonmonotonic modes of negation.
In the arbitration approach, the assumption is that all sources of information (both old and new) are equally reliable, so the resulting base should contain as much as possible of both sources. [6] [7]
The merging approach was presented by Konieczny and Perez. [8] There are several differences between combination operators and merging operators: [9]
Konieczny and Perez [10] [11] [12] extended their framework to merging under a set of exogenously imposed constraints that have to be satisfied by the combined database. Their framework is now the standard framework for belief merging. [13] In their framework, a merging operator is a function f that takes as input a vector of n consistent (satisfiable) propositional formulas, P=(p1,...,pn), representing e.g. claims made by n different experts, and another formula c, representing constraints. It should satisfy the following postulates:
They present several operators that satisfy all these properties, e.g.:
Konieczny, Lang and Marquis [14] present the DA2 framework, which generalizes the merging framework. They prove that, in this framework, query entailment from merged bases is only at the first level of the polynomial hierarchy.
Belief merging is somewhat related to social choice, in which opinions of different citizens have to be combined into a single "social" opinion. Meyer, Ghose and Chopra [15] relate belief-merging to social choice, elections and preference aggregation.
Chpora, Ghose and Meyer [16] relate belief-merging to strategyproofness. They show that the Arrow's impossibility theorem and Gibbard–Satterthwaite theorem do not hold in their belief-merging framework.
Everaere, Konieczny and Marquis [17] study belief-merging operators in settings in which the different information sources are strategic, and may try to change their stated beliefs in order to influence the outcome. They study strategyproof merging operators.
Haret and Wallner [18] show that most aggregation procedures are manipulable, and study the computational complexity of finding a manipulation.
Haret, Pfandler and Woltran [19] consider some classic social choice axioms in the context of belief merging.
Haret, Lackner, Pfandler and Wallner [20] study belief-merging operators that satisfy fairness properties, similar to justified representation. To illustrate, suppose three experts support propositions x1,x2,x3,x4 and oppose propositions y1,y2,y3,y4, whereas a fourth expert opposes propositions x1,x2,x3,x4 and supports propositions y1,y2,y3,y4. Then:
Multiwinner voting can be seen as a special case of belief-merging with constraints, where the constraints encode the size of the committee. [21]: Sub.6.7
The formal methods developed for belief merging have been applied in other areas of social epistemology, such as:
{{
cite journal}}
: Cite journal requires |journal=
(
help)
This article needs additional or more specific
categories. (November 2023) |
Belief merging, also called belief fusion or propositional belief merging, is a process in which an individual agent aggregates possibly conflicting pieces of information, expressed in logical formulae, into a consistent knowledge-base. Applications include combining conflicting sensor information received by the same agent (see sensor fusion) and combining multiple databases to build an expert system. [1] [2] [3] [4] It also has applications in multi-agent systems.
In the combination approach, we take the union of the knowledge bases (a finite set of logical formulas). If the union is consistent, we are done. Otherwise, we select some maximal consistent subset of it. Baral, Kraus, Minker and Subrahmanian [5] [2] present algorithms for combining knowledge-bases consisting of first-order theories, and to resolve inconsistencies among them.Subrahamanian [3] presents a uniform theoretical framework, based on annotated logics, for combining multiple knowledge bases which may have inconsistencies, uncertainties, and nonmonotonic modes of negation.
In the arbitration approach, the assumption is that all sources of information (both old and new) are equally reliable, so the resulting base should contain as much as possible of both sources. [6] [7]
The merging approach was presented by Konieczny and Perez. [8] There are several differences between combination operators and merging operators: [9]
Konieczny and Perez [10] [11] [12] extended their framework to merging under a set of exogenously imposed constraints that have to be satisfied by the combined database. Their framework is now the standard framework for belief merging. [13] In their framework, a merging operator is a function f that takes as input a vector of n consistent (satisfiable) propositional formulas, P=(p1,...,pn), representing e.g. claims made by n different experts, and another formula c, representing constraints. It should satisfy the following postulates:
They present several operators that satisfy all these properties, e.g.:
Konieczny, Lang and Marquis [14] present the DA2 framework, which generalizes the merging framework. They prove that, in this framework, query entailment from merged bases is only at the first level of the polynomial hierarchy.
Belief merging is somewhat related to social choice, in which opinions of different citizens have to be combined into a single "social" opinion. Meyer, Ghose and Chopra [15] relate belief-merging to social choice, elections and preference aggregation.
Chpora, Ghose and Meyer [16] relate belief-merging to strategyproofness. They show that the Arrow's impossibility theorem and Gibbard–Satterthwaite theorem do not hold in their belief-merging framework.
Everaere, Konieczny and Marquis [17] study belief-merging operators in settings in which the different information sources are strategic, and may try to change their stated beliefs in order to influence the outcome. They study strategyproof merging operators.
Haret and Wallner [18] show that most aggregation procedures are manipulable, and study the computational complexity of finding a manipulation.
Haret, Pfandler and Woltran [19] consider some classic social choice axioms in the context of belief merging.
Haret, Lackner, Pfandler and Wallner [20] study belief-merging operators that satisfy fairness properties, similar to justified representation. To illustrate, suppose three experts support propositions x1,x2,x3,x4 and oppose propositions y1,y2,y3,y4, whereas a fourth expert opposes propositions x1,x2,x3,x4 and supports propositions y1,y2,y3,y4. Then:
Multiwinner voting can be seen as a special case of belief-merging with constraints, where the constraints encode the size of the committee. [21]: Sub.6.7
The formal methods developed for belief merging have been applied in other areas of social epistemology, such as:
{{
cite journal}}
: Cite journal requires |journal=
(
help)
This article needs additional or more specific
categories. (November 2023) |