Computing marginal probabilities in causal multiway trees given incomplete information

摘要

Causal networks are structures within which recently established techniques can be used to compute marginal probabilities. For these techniques to work, all the causal information implied by a particular network must be available. If some of the causal information is missing, Maximum Entropy could be used to provide these values in a minimally prejudiced manner. Unfortunately, the general problem of maximising Entropy is NP-complete. However, the authors have already shown that a Maximum Entropy approach to probabilistic reasoning is not intractable for causal information which can be represented by a binary tree. This paper extends that result by proving that, given a multiway tree of causal information (e.g. as required by Pearl's technique), the probability of the marginals can be found in linear space and time using Maximum Entropy. Further, it is shown that a simple algorithm can be used to estimate missing information in a causal multiway tree and hence enable existing methods to be used in a situation when they otherwise could not have been. If this work can be extended to more general causal networks it would enhance existing techniques.