Computing marginal probabilities in causal inverted binary trees given incomplete information

摘要

Causal networks require complete causal information if they are to be evaluated using propagation. Complete information is not always available as, for example, in the context of supporting decisions. In these cases one approach is to take that information which is available and use minimally prejudiced techniques to estimate that which is missing. Traditional techniques can then be used to evaluate the network.Maximum Entropy can be used to find minimally prejudiced estimates of missing information but doing so has, until recently, been considered to be computationally unfeasible. However, the authors have already shown that a method exists for solving this problem in linear time for two valued causal trees.This paper extends that work by providing a method for finding minimally prejudiced estimates of missing information in two valued causal inverted binary trees. In doing so, the traditional theory for Maximum Entropy has to be extended to handle non linear constraints arising from independence. In addition a new algebraic method is presented which isolates an unknown Lagrange multiplier by using the ratio of a pair of state probabilities. This is much simpler than the traditional method which requires summations over many states.Finally, it is shown that any missing conditional information can be found in linear time by using a fixed point iterative algorithm derived from the above algebra.