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)). 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 of a compound formula cannot be calculated solely from the probabilities of its sub-formulas. Consider, for instance, a formula $P$ with probability $0.5$. Note that its negation, $\neg P$, will also have probability $0.5$. Now one would like $P\land P$ to also have probability $0.5$, but $P\land\neg P$ to have probability $0$. But both these compound formulas are conjunctions of two sub-formulas each with probability $0.5$. 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 $P\land Q$ can be anything between $0$ and the minimum of the probabilities of $P$ and $Q$.

Incidence calculus solves this problem by appealing to the foundations of 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 $a$ and $b$ with equal probability. The incidence of $P$ might be $\{a\}$. Then, by definition, the incidence of $\neg P$ will be $\{b\}$, that of $P\land P$ will be $\{a\}$ and that of $P\land\neg P$ will be $\{$, 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 [a1], [a2].

References

[a1]	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)
[a2]	A. Bundy, "Incidence calculus" , Encycl. Artificial Intelligence (1992) pp. 663–668 (Also available from Edinburgh as DAI Research Paper No. 497)