View source for Incidence calculus

A mechanism for automatic reasoning about uncertain knowledge. Most automatic reasoning mechanisms represent knowledge using logical formulas and manipulate these formulas with rules of inference (cf. [[Permissible law (inference)|Permissible law (inference)]]). When the knowledge is uncertain, an uncertainty value is associated with each formula and a propagation rule is associated to each rule of inference. Probabilities are often used as uncertainty values. The propagation rule calculates the new uncertainty for the conclusion of the rule of inference from the old uncertainty values of its premises. More generally, it may only be possible to place upper and lower bounds on the uncertainty values of formulas, so that the propagation rule generates upper and lower bounds for the conclusion from those on the premises.

One problem with using probabilities as uncertainty values is that the [[Probability|probability]] of a compound formula cannot be calculated solely from the probabilities of its sub-formulas. Consider, for instance, a formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100701.png" /> with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100702.png" />. Note that its negation, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100703.png" />, will also have probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100704.png" />. Now one would like <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100705.png" /> to also have probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100706.png" />, but <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100707.png" /> to have probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100708.png" />. But both these compound formulas are conjunctions of two sub-formulas each with probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i1100709.png" />. One consequence of this is that either the uncertainty propagation rule has to appeal to information additional to probabilities or it will calculate bounds that are much too loose. For instance, without additional information the probability of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007010.png" /> can be anything between <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007011.png" /> and the minimum of the probabilities of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007012.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007013.png" />.

Incidence calculus solves this problem by appealing to the foundations of [[Probability theory|probability theory]]. Instead of associating probabilities directly with formulas, sets of possible worlds (called  "outcomes"  in probability and  "points"  in statistics) are associated with formulas. Probabilities are then associated with possible worlds and the probabilities of formulas are calculated by summing the probabilities of their associated possible worlds. The set of possible worlds associated with a formula is called its incidence. To see how this solves the problem, suppose there are two possible worlds <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007014.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007015.png" /> with equal probability. The incidence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007016.png" /> might be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007017.png" />. Then, by definition, the incidence of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007018.png" /> will be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007019.png" />, that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007020.png" /> will be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007021.png" /> and that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007022.png" /> will be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110070/i11007023.png" />, as required to give the desired probabilities. An algorithm called the legal assignment finder is provided in incidence calculus to propagate incidence bounds between propositional formulas and their sub-formulas and hence infer new probability bounds from old.

Introductions to incidence calculus can be found in [[#References|[a1]]], [[#References|[a2]]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  A. Bundy,   "Incidence calculus: a mechanism for probabilistic reasoning"  ''J. Automated Reasoning'' , '''1''' :  3  (1985)  pp. 263–284  (Earlier version in: Proceedings of FGCS–84 and in: Proceedings of the Workshop on Uncertainty and Probability. Also available from Edinburgh as DAI Research Paper No 216)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  A. Bundy,   "Incidence calculus" , ''Encycl. Artificial Intelligence''  (1992)  pp. 663–668  (Also available from Edinburgh as DAI Research Paper No. 497)</TD></TR></table>