A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints
J. Miller, R. Goodman
Abstract:
A method of calculating probability values from a system of marginal constraints is presented. Previous systems for finding the probability of a single attribute have either made an independence assumption concerning the evidence or have required, in the worst case, time exponential in the number of attributes of the system. In this paper a closed form solution to the probability of an attribute given the evidence is found. The closed form solution, however does not enforce the (nonlinear) constraint that all terms in the underlying distribution be positive. The equation requires O(r^3) steps to evaluate, where r is the number of independent marginal constraints describing the system at the time of evaluation. Furthermore, a marginal constraint may be exchanged with a new constraint, and a new solution calculated in O(r^2) steps. This method is appropriate for calculating probabilities in a real time expert system
Keywords:
Pages: 186193
PS Link:
PDF Link: /papers/90/p186miller.pdf
BibTex:
@INPROCEEDINGS{Miller90,
AUTHOR = "J. Miller
and R. Goodman",
TITLE = "A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints",
BOOKTITLE = "Proceedings of the Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI90)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "1990",
PAGES = "186193"
}

