Belief merging

Add links
From Wikipedia, the free encyclopedia

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.

Approaches[edit]

Combination[edit]

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.

Arbitration[edit]

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]

Merging[edit]

The merging approach was presented by Konieczny and Perez.[8] There are several differences between combination operators and merging operators:[9]

  • Combination is syntax-dependent, whereas merging is based on the principle of irrelevance of syntax: an operation on two equivalent databases should return two equivalent databases.
  • Combination operators ignore the information about the source of the knowledge bases, so they cannot take into account the number of experts supporting each proposition. In particular, they cannot make decisions based on a majority vote among experts.

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:

  • IC0: f(P,c) models c. [this means that the merging output satisfies the constraint]
  • IC1: If c is consistent, then f(P,c) is consistent.
  • IC2: If the logical conjunction of p1,...,pn,c is consistent, then f(P,c) equals this logical conjunction.
  • IC3: if P1 is equivalent to P2 and c1 is equivalent to c2, then f(P1,c1) is equivalent to f(P2,c2). [this means that the merging is syntax-independent]
  • IC4: if p1 models c and p2 models c, then the logical conjunction of f(p1,p2,c) and p1 is consistent iff the logical conjunction of f(p1,p2,c) and p2 is consistent.
  • IC5: The conjunction of f(P1,c) and f(P2,c) models f(P1+P2,c).
  • IC6: If the conjunction of f(P1,c) and f(P2,c) is consistent, then f(P1+P2,c) models it.
  • IC7: The conjunction of f(P,c1) and c2 models f(P, conjunction of c1 and c2).
  • IC8: If the conjunction of f(P,c1) and c2 is consistent, then f(P, conjunction of c1 and c2) models it.

They present several operators that satisfy all these properties, e.g.:

  • Minimizing the sum of distances between the interpretations of the pi and the interpretation of the outcome (where "distance" can be measured by Hamming distance or another metric). If the formulas pi correspond to agens, then this corresponds to the utilitarian rule.
  • Minimizing the largest distance between the interpretations of the pi and the interpretation of the outcome. This corredponds similarly to the egalitarian rule, refined by the leximin order.

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 and social choice[edit]

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:

  • The utilitarian rule (minimizing the sum of distances) will choose x1,x2,x3,x4; this is unfair to the minority expert, who is not represented at all.
  • The egalitarian rule (minimizing the maximum distances) will choose x1,x2,y1,y2; this is unfair to the majority experts, who are represented by only 2 out of 4 propositions, even though they are 3/4 of the population.
  • A new suggested rule, based on Proportional approval voting, would choose x1,x2,x3,y1, which satisfies "justified representation" for both the minority and the majority.

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 

Other related fields[edit]

The formal methods developed for belief merging have been applied in other areas of social epistemology, such as:

  • Group consensus;[22]
  • Judgement aggregation - a closely-related process, in which several experts express their own judgement (as a logical formula), and society has to aggregate them in a consistent way.[23]

See also[edit]

  • Belief revision - a closely-related process, in which an individual changes an existing knowledge base after receiving a new and conflicting piece of information.
  • Belief aggregation - a similar term but refers to a different process, in which the beliefs are expressed as probability distributions over events, and the goal is to aggregate them into a single distribution.
  • Sensor fusion - aggregating data from different sensors.

References[edit]

  1. ^ Elmagarmid, Ahmed K.; Rusinkiewicz, Marek; Sheth, Amit (1999). Management of Heterogeneous and Autonomous Database Systems. Morgan Kaufmann. ISBN 978-1-55860-216-8.
  2. ^ a b Baral, Chitta; Kraus, Sarit; Minker, Jack; Subrahmanian, V. S. (1992-02-01). "COMBINING KNOWLEDGE BASES CONSISTING OF FIRST‐ORDER THEORIES". Computational Intelligence. 8 (1): 45–71. doi:10.1111/j.1467-8640.1992.tb00337.x. ISSN 0824-7935. S2CID 964506.
  3. ^ a b Subrahmanian, V. S. (1994-06-01). "Amalgamating knowledge bases". ACM Transactions on Database Systems. 19 (2): 291–331. doi:10.1145/176567.176571. ISSN 0362-5915. S2CID 15968948.
  4. ^ "Modern database systems". Guide books. Retrieved 2023-11-13.
  5. ^ Baral, C.; Kraus, S.; Minker, J. (1991-06-01). "Combining Multiple Knowledge Bases". IEEE Transactions on Knowledge and Data Engineering. 3 (2): 208–220. doi:10.1109/69.88001. ISSN 1041-4347.
  6. ^ Revesz, Peter Z. (1993-08-01). "On the semantics of theory change: Arbitration between old and new information". Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '93. New York, NY, USA: Association for Computing Machinery. pp. 71–82. doi:10.1145/153850.153857. ISBN 978-0-89791-593-9. S2CID 2627403.
  7. ^ Liberatore, P.; Schaerf, M. (1998). "Arbitration (or how to merge knowledge bases)". IEEE Transactions on Knowledge and Data Engineering. 10 (1): 76–90. doi:10.1109/69.667090. ISSN 1041-4347. S2CID 5672503.
  8. ^ Konieczny, Sébastien; Pino Pérez, Ramón (2011-04-01). "Logic Based Merging". Journal of Philosophical Logic. 40 (2): 239–270. doi:10.1007/s10992-011-9175-5. ISSN 1573-0433. S2CID 1458423.
  9. ^ Konieczny, Sébastien (2000-04-11). "On the difference between merging knowledge bases and combining them". Proceedings of the Seventh International Conference on Principles of Knowledge Representation and Reasoning. KR'00. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc.: 135–144.
  10. ^ Konieczny, Sébastien; Pérez, Ramón Pino (1999). "Merging with Integrity Constraints". In Hunter, Anthony; Parsons, Simon (eds.). Symbolic and Quantitative Approaches to Reasoning and Uncertainty. Lecture Notes in Computer Science. Vol. 1638. Berlin, Heidelberg: Springer. pp. 233–244. doi:10.1007/3-540-48747-6_22. ISBN 978-3-540-48747-0.
  11. ^ Konieczny, S. (2002-10-01). "Merging Information Under Constraints: A Logical Framework". Journal of Logic and Computation. 12 (5): 773–808. doi:10.1093/logcom/12.5.773.
  12. ^ Konieczny, Sébastien; Pino Pérez, Ramón (2005-02-01). "Propositional belief base merging or how to merge beliefs/goals coming from several sources and some links with social choice theory". European Journal of Operational Research. Decision Analysis and Artificial Intelligence. 160 (3): 785–802. doi:10.1016/j.ejor.2003.06.039. ISSN 0377-2217.
  13. ^ Pigozzi, Gabriella (2015-07-08). "Belief Merging and Judgment Aggregation". {{cite journal}}: Cite journal requires |journal= (help)
  14. ^ Konieczny, S; Lang, J; Marquis, P (2004-08-01). "DA2 merging operators". Artificial Intelligence. Nonmonotonic Reasoning. 157 (1): 49–79. doi:10.1016/j.artint.2004.04.008. ISSN 0004-3702.
  15. ^ Meyer, Thomas; Ghose, Aditya; Chopra, Samir (2001). "Social Choice, Merging, and Elections". In Benferhat, Salem; Besnard, Philippe (eds.). Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Lecture Notes in Computer Science. Vol. 2143. Berlin, Heidelberg: Springer. pp. 466–477. doi:10.1007/3-540-44652-4_41. ISBN 978-3-540-44652-1.
  16. ^ Chopra, Samir; Ghose, Aditya; Meyer, Thomas (2006-03-01). "Social choice theory, belief merging, and strategy-proofness". Information Fusion. Logic-based Approaches to Information Fusion. 7 (1): 61–79. doi:10.1016/j.inffus.2005.05.003. ISSN 1566-2535.
  17. ^ Everaere, P.; Konieczny, S.; Marquis, P. (2007-02-06). "The Strategy-Proofness Landscape of Merging". Journal of Artificial Intelligence Research. 28: 49–105. arXiv:1110.2766. doi:10.1613/jair.2034. ISSN 1076-9757. S2CID 2559616.
  18. ^ Haret, Adrian; Wallner, Johannes P. (2019). "Manipulating Skeptical and Credulous Consequences when Merging Beliefs". In Calimeri, Francesco; Leone, Nicola; Manna, Marco (eds.). Logics in Artificial Intelligence. Lecture Notes in Computer Science. Vol. 11468. Cham: Springer International Publishing. pp. 133–150. doi:10.1007/978-3-030-19570-0_9. ISBN 978-3-030-19570-0. S2CID 146807947.
  19. ^ Haret, Adrian; Pfandler, Andreas; Woltran, Stefan (2016-08-29). "Beyond IC postulates: classification criteria for merging operators". Proceedings of the Twenty-second European Conference on Artificial Intelligence. ECAI'16. NLD: IOS Press: 372–380. doi:10.3233/978-1-61499-672-9-372. ISBN 978-1-61499-671-2.
  20. ^ Haret, Adrian; Lackner, Martin; Pfandler, Andreas; Wallner, Johannes P. (2020-04-03). "Proportional Belief Merging". Proceedings of the AAAI Conference on Artificial Intelligence. 34 (3): 2822–2829. doi:10.1609/aaai.v34i03.5671. ISSN 2374-3468.
  21. ^ Lackner, Martin; Skowron, Piotr (2023). Multi-Winner Voting with Approval Preferences. Springer Nature. ISBN 978-3-031-09016-5.
  22. ^ Gauwin, Olivier; Konieczny, Sébastien; Marquis, Pierre (2005). "Conciliation and Consensus in Iterated Belief Merging". In Godo, Lluís (ed.). Symbolic and Quantitative Approaches to Reasoning with Uncertainty. Lecture Notes in Computer Science. Vol. 3571. Berlin, Heidelberg: Springer. pp. 514–526. doi:10.1007/11518655_44. ISBN 978-3-540-31888-0.
  23. ^ Pigozzi, Gabriella (2006-09-01). "Belief merging and the discursive dilemma: an argument-based account to paradoxes of judgment aggregation". Synthese. 152 (2): 285–298. doi:10.1007/s11229-006-9063-7. ISSN 1573-0964. S2CID 18001376.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Belief_merging&oldid=1193261631"