Belief merging

Last updated

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.

Contents

Approaches

Combination

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

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

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 and social choice

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:

See also

Related Research Articles

In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make (a AND NOT b) = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

<span class="mw-page-title-main">Regress argument (epistemology)</span> Problem in epistemology that any proposition can be endlessly questioned

In epistemology, the regress argument is the argument that any proposition requires a justification. However, any justification itself requires support. This means that any proposition whatsoever can be endlessly (infinitely) questioned, resulting in infinite regress. It is a problem in epistemology and in any general situation where a statement has to be justified.

Reification is the process by which an abstract idea about a computer program is turned into an explicit data model or other object created in a programming language. A computable/addressable object—a resource—is created in a system as a proxy for a non computable/addressable object. By means of reification, something that was previously implicit, unexpressed, and possibly inexpressible is explicitly formulated and made available to conceptual manipulation. Informally, reification is often referred to as "making something a first-class citizen" within the scope of a particular system. Some aspect of a system can be reified at language design time, which is related to reflection in programming languages. It can be applied as a stepwise refinement at system design time. Reification is one of the most frequently used techniques of conceptual analysis and knowledge representation.

In geometry, an incidence relation is a heterogeneous relation that captures the idea being expressed when phrases such as "a point lies on a line" or "a line is contained in a plane" are used. The most basic incidence relation is that between a point, P, and a line, l, sometimes denoted P I l. If P I l the pair (P, l) is called a flag. There are many expressions used in common language to describe incidence (for example, a line passes through a point, a point lies in a plane, etc.) but the term "incidence" is preferred because it does not have the additional connotations that these other terms have, and it can be used in a symmetric manner. Statements such as "line l1 intersects line l2" are also statements about incidence relations, but in this case, it is because this is a shorthand way of saying that "there exists a point P that is incident with both line l1 and line l2". When one type of object can be thought of as a set of the other type of object (viz., a plane is a set of points) then an incidence relation may be viewed as containment.

Truthmaker theory is "the branch of metaphysics that explores the relationships between what is true and what exists". The basic intuition behind truthmaker theory is that truth depends on being. For example, a perceptual experience of a green tree may be said to be true because there actually is a green tree. But if there were no tree there, it would be false. So the experience by itself does not ensure its truth or falsehood, it depends on something else. Expressed more generally, truthmaker theory is the thesis that "the truth of truthbearers depends on the existence of truthmakers". A perceptual experience is the truthbearer in the example above. Various representational entities, like beliefs, thoughts or assertions can act as truthbearers. Truthmaker theorists are divided about what type of entity plays the role of truthmaker; popular candidates include states of affairs and tropes.

In mathematical logic, a superintuitionistic logic is a propositional logic extending intuitionistic logic. Classical logic is the strongest consistent superintuitionistic logic; thus, consistent superintuitionistic logics are called intermediate logics.

Belief revision is the process of changing beliefs to take into account a new piece of information. The logical formalization of belief revision is researched in philosophy, in databases, and in artificial intelligence for the design of rational agents.

The closed-world assumption (CWA), in a formal system of logic used for knowledge representation, is the presumption that a statement that is true is also known to be true. Therefore, conversely, what is not currently known to be true, is false. The same name also refers to a logical formalization of this assumption by Raymond Reiter. The opposite of the closed-world assumption is the open-world assumption (OWA), stating that lack of knowledge does not imply falsity. Decisions on CWA vs. OWA determine the understanding of the actual semantics of a conceptual expression with the same notations of concepts. A successful formalization of natural language semantics usually cannot avoid an explicit revelation of whether the implicit logical backgrounds are based on CWA or OWA.

Symbolic Link (SYLK) is a Microsoft file format typically used to exchange data between applications, specifically spreadsheets. SYLK files conventionally have a .slk suffix. Composed of only displayable ANSI characters, it can be easily created and processed by other applications, such as databases.

A "production system" is a computer program typically used to provide some form of artificial intelligence, which consists primarily of a set of rules about behavior, but it also includes the mechanism necessary to follow those rules as the system responds to states of the world. Those rules, termed productions, are a basic representation found useful in automated planning, expert systems and action selection.

In computer science and recursion theory the McCarthy Formalism (1963) of computer scientist John McCarthy clarifies the notion of recursive functions by use of the IF-THEN-ELSE construction common to computer science, together with four of the operators of primitive recursive functions: zero, successor, equality of numbers and composition. The conditional operator replaces both primitive recursion and the mu-operator.

Imperative logic is the field of logic concerned with imperatives. In contrast to declaratives, it is not clear whether imperatives denote propositions or more generally what role truth and falsity play in their semantics. Thus, there is almost no consensus on any aspect of imperative logic.

In artificial intelligence, action description language (ADL) is an automated planning and scheduling system in particular for robots. It is considered an advancement of STRIPS. Edwin Pednault proposed this language in 1987. It is an example of an action language.

The PROPT MATLAB Optimal Control Software is a new generation platform for solving applied optimal control and parameters estimation problems.

<span class="mw-page-title-main">Relationships among probability distributions</span> Topic in probability theory and statistics

In probability theory and statistics, there are several relationships among probability distributions. These relations can be categorized in the following groups:

Concepts are an extension to the templates feature provided by the C++ programming language. Concepts are named Boolean predicates on template parameters, evaluated at compile time. A concept may be associated with a template, in which case it serves as a constraint: it limits the set of arguments that are accepted as template parameters.

LOOP is a simple register language that precisely captures the primitive recursive functions. The language is derived from the counter-machine model. Like the counter machines the LOOP language comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer. A few arithmetic instructions operate on the registers. The only control flow instruction is 'LOOP x DO...END'. It causes the instructions within its scope to be repeated x times.

<span class="mw-page-title-main">Probabilistic soft logic</span>

Probabilistic Soft Logic (PSL) is a statistical relational learning (SRL) framework for modeling probabilistic and relational domains. It is applicable to a variety of machine learning problems, such as collective classification, entity resolution, link prediction, and ontology alignment. PSL combines two tools: first-order logic, with its ability to succinctly represent complex phenomena, and probabilistic graphical models, which capture the uncertainty and incompleteness inherent in real-world knowledge. More specifically, PSL uses "soft" logic as its logical component and Markov random fields as its statistical model. PSL provides sophisticated inference techniques for finding the most likely answer (i.e. the maximum a posteriori (MAP) state). The "softening" of the logical formulas makes inference a polynomial time operation rather than an NP-hard operation.

Dynamic epistemic logic (DEL) is a logical framework dealing with knowledge and information change. Typically, DEL focuses on situations involving multiple agents and studies how their knowledge changes when events occur. These events can change factual properties of the actual world : for example a red card is painted in blue. They can also bring about changes of knowledge without changing factual properties of the world : for example a card is revealed publicly to be red. Originally, DEL focused on epistemic events. We only present in this entry some of the basic ideas of the original DEL framework; more details about DEL in general can be found in the references.

References

  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. 1 2 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. 1 2 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. hdl:20.500.12657/60149. 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 (PDF). 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.