×

zbMATH — the first resource for mathematics

Recursive conditioning. (English) Zbl 0969.68150
Summary: We introduce an any-space algorithm for exact inference in Bayesian networks, called recursive conditioning. On one extreme, recursive conditioning takes \(O(n)\) space and \(O(n\exp(w\log n))\) time – where \(n\) is the size of a Bayesian network and \(w\) is the width of a given elimination order – therefore, establishing a new complexity result for linear-space inference in Bayesian networks. On the other extreme, recursive conditioning takes \(O(n\exp(w))\) space and \(O(n\exp(w))\) time, therefore, matching the complexity of state-of-the-art algorithms based on clustering and elimination. In between linear and exponential space, recursive conditioning can utilize memory at increments of \(X\)-bytes, where \(X\) is the number of bytes needed to store a floating point number in a cache. Moreover, the algorithm is equipped with a formula for computing its average running time under any amount of space, hence, providing a valuable tool for time-space tradeoffs in demanding applications. Recursive conditioning is therefore the first algorithm for exact inference in Bayesian networks to offer a smooth tradeoff between time and space, and to explicate a smooth, quantitative relationship between these two important resources.

MSC:
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., Vol. 25, 6, 1305-1317, (1996) · Zbl 0864.68074
[2] Boutilier, C.; Friedman, N.; Goldszmidt, M.; Koller, D., Context-specific independence in Bayesian networks, (), 115-123
[3] Cooper, G.F., Bayesian belief-network inference using recursive decomposition, (1990), Technical Report KSL-90-05, Knowledge Systems Laboratory Stanford, CA
[4] A. Darwiche, Decomposable negation normal form, J. ACM, to appear · Zbl 1127.03321
[5] Darwiche, A., Conditioning algorithms for exact and approximate inference in causal networks, (), 99-107
[6] Darwiche, A., Compiling knowledge into decomposable negation normal form, (), 284-289
[7] Darwiche, A., Dtrees: A new graphical model for structure-based reasoning, (1999), Technical Report D-107, Computer Science Department, UCLA Los Angeles, CA
[8] Darwiche, A., Utilizing device behavior in structure-based diagnosis, (), 1096-1101
[9] Dechter, R., Constraint networks, (), 276-285
[10] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artificial intelligence, Vol. 38, 353-366, (1989) · Zbl 0665.68084
[11] Dechter, R., Bucket elimination: A unifying framework for probabilistic inference, (), 211-219 · Zbl 0910.68209
[12] Dechter, R., Topological parameters for time-space tradeoff, (), 211-219
[13] Díez, F.J., Local conditioning in Bayesian networks, Artificial intelligence, Vol. 87, 1, 1-20, (1996)
[14] Djidjev, H.N.; Gilbert, J.R., Separators in graphs with negative and multiple vertex weights, Algorithmica, Vol. 23, 57-71, (1999) · Zbl 0913.68155
[15] George, A., Nested dissection of a regular finite element mesh, SIAM J. numer. anal., Vol. 10, 2, 345-363, (1973) · Zbl 0259.65087
[16] Horvitz, E.J.; Suermondt, H.J.; Cooper, G.F., Bounded conditioning: flexible inference for decisions under scarce resources, (), 182-193
[17] Huang, C.; Darwiche, A., Inference in belief networks: A procedural guide, Internat. J. approx. reason., Vol. 15, 3, 225-263, (1996) · Zbl 0941.68767
[18] Jensen, F.V.; Lauritzen, S.L.; Olesen, K.G., Bayesian updating in recursive graphical models by local computation, Computational statistics quarterly, Vol. 4, 269-282, (1990) · Zbl 0715.68076
[19] Lauritzen, S.L.; Spiegelhalter, D.J., Local computations with probabilities on graphical structures and their application to expert systems, J. roy. statist. soc. ser. B, Vol. 50, 2, 157-224, (1988) · Zbl 0684.68106
[20] Li, Z.; D’Ambrosio, B.D., Efficient inference in Bayes networks as a combinatorial optimization problem, Internat. J. approx. reason., Vol. 11, 55-81, (1994) · Zbl 0808.68098
[21] Lipton, R.; Rose, D.; Tarjan, R.A., Generalized nested dissection, SIAM J. numer. anal., Vol. 16, 2, 346-358, (1979) · Zbl 0435.65021
[22] Lipton, R.; Tarjan, R.A., A separator theorem for planar graphs, SIAM J. appl. math., Vol. 36, 2, 177-189, (1979) · Zbl 0432.05022
[23] Maier, D., The theory of relational databases, (1983), Computer Science Press Rockville, MD · Zbl 0519.68082
[24] Miller, G.L.; Reif, J.H., Parallel tree contraction and its application, (), 478-489
[25] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA
[26] Peot, M.A.; Shachter, R.D., Fusion and propagation with multiple observations in belief networks, Artificial intelligence, Vol. 48, 3, 299-318, (1991) · Zbl 0738.68074
[27] Rosenthal, A., Computing the reliability of complex networks, SIAM J. appl. math., Vol. 32, 2, 384-393, (1977) · Zbl 0379.90048
[28] Shachter, R.; Andersen, S.K.; Szolovits, P., Global conditioning for probabilistic inference in belief networks, (), 514-522
[29] Shachter, R.; D’Ambrosio, B.D.; del Favero, B., Symbolic probabilistic inference in belief networks, (), 126-131
[30] Shenoy, P.P., A valuation-based language for expert systems, Internat. J. approx. reason., Vol. 5, 3, 383-411, (1989)
[31] Tarjan, R.E., Decomposition by clique separators, Discrete math., Vol. 55, 221-232, (1985) · Zbl 0572.05039
[32] Zhang, N.L.; Poole, D., Exploiting causal independence in Bayesian network inference, J. artificial intelligence res., Vol. 5, 301-328, (1996) · Zbl 0900.68384
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.