A Polynomial Time Algorithm for Finding Bayesian Probabilities from Marginal Constraints

A method of calculating probability values from a system of marginal\nconstraints is presented. Previous systems for finding the probability of a\nsingle attribute have either made an independence assumption concerning the\nevidence or have required, in the worst case, time exponential in the number of\nattributes of the system. In this paper a closed form solution to the\nprobability of an attribute given the evidence is found. The closed form\nsolution, however does not enforce the (non-linear) constraint that all terms\nin the underlying distribution be positive. The equation requires O(r^3) steps\nto evaluate, where r is the number of independent marginal constraints\ndescribing the system at the time of evaluation. Furthermore, a marginal\nconstraint may be exchanged with a new constraint, and a new solution\ncalculated in O(r^2) steps. This method is appropriate for calculating\nprobabilities in a real time expert system\n

Paper

Similar papers

© 2026 NYSGPT2525 LLC