An Algorithm for Computing Probabilistic Propositions
This work addresses a specific computational bottleneck in probabilistic reasoning for AI researchers, but it appears incremental as it builds on existing belief network algorithms.
The paper tackles the problem of computing probabilistic propositions in belief networks by presenting a method that uses a single external routine for probability calculations, enabling general probabilistic propositions over nodes. The result shows that while worst-case time complexity is exponential in query size, it is polynomial for many common query types.
A method for computing probabilistic propositions is presented. It assumes the availability of a single external routine for computing the probability of one instantiated variable, given a conjunction of other instantiated variables. In particular, the method allows belief network algorithms to calculate general probabilistic propositions over nodes in the network. Although in the worst case the time complexity of the method is exponential in the size of a query, it is polynomial in the size of a number of common types of queries.