{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:21Z","timestamp":1761620961271,"version":"3.33.0"},"reference-count":23,"publisher":"Wiley","issue":"5","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5915,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1990,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Researchers in decision analysis and artificial intelligence (AI) have used Bayesian belief networks to build probabilistic expert systems. Using standard methods drawn from the theory of computational complexity, workers in the field have shown that the problem of probabilistic inference in belief networks is difficult and almost certainly intractable. We have developed a randomized approximation scheme, BN\u2010RAS, for doing probabilistic inference in belief networks. The algorithm can, in many circumstances, perform efficient approximate inference in large and richly interconnected models. Unlike previously described stochastic algorithms for probabilistic inference, the randomized approximation scheme (ras) computes a priori bounds on running time by analyzing the structure and contents of the belief network. In this article, we describe BN\u2010RAS precisely and analyze its performance mathematically.<\/jats:p>","DOI":"10.1002\/net.3230200510","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T09:21:36Z","timestamp":1178961696000},"page":"661-685","source":"Crossref","is-referenced-by-count":40,"title":["A randomized approximation algorithm for probabilistic inference on bayesian belief networks"],"prefix":"10.1002","volume":"20","author":[{"given":"R. Martin","family":"Chavez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory F.","family":"Cooper","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"A. Z.Broder How hard is it to marry at random? (On the approximation of the permanent).Proceedings of the Eighteenth ACM Symposium on Theory of Computing (1986)50\u201358.","DOI":"10.1145\/12130.12136"},{"first-page":"177","volume-title":"Proceedings of the First Workshop on Uncertainty in Artificial Intelligence","author":"Bundy A.","key":"e_1_2_1_3_2"},{"key":"e_1_2_1_4_2","unstructured":"R. M.Chavez Randomized algorithms for probabilistic expert systems. PhD thesis Knowledge Systems Laboratory Stanford University Stanford CA (to appear)."},{"first-page":"106","volume-title":"Proceedings of the Third Workshop on Uncertainty in Artificial Intelligence","author":"Chin H. L.","key":"e_1_2_1_5_2"},{"volume-title":"Uncertainty in Artificial Intelligence","year":"1989","author":"Chin H. L.","key":"e_1_2_1_6_2"},{"key":"e_1_2_1_7_2","unstructured":"G. F.Cooper The computational complexity of probabilistic inference using Bayesian belief networks.Artificial Intell.in press."},{"key":"e_1_2_1_8_2","unstructured":"G. F.Cooper Probabilistic inference using belief networks is NP\u2010hard. Technical Report KSL\u201087\u201027 Medical Computer Science Group Knowledge Systems Laboratory Stanford University Stanford CA May (1987)."},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_1_9_2"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-70396-5.50019-4"},{"volume-title":"Dynamic Programming and Markov Processes","year":"1960","author":"Howard R. A.","key":"e_1_2_1_11_2"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"M.JerrumandA.Sinclair Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved.Proceedings of the Twentieth ACM Symposium on Theory of Computing Chicago IL (1988)235\u2013244.","DOI":"10.1145\/62212.62234"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"R. M.KarpandM.Luby Monte\u2010Carlo algorithms for enumeration and reliability problems. Proceedings of the Twenty\u2010fourth IEEE Symposium on Foundations of Computer Science (1983).","DOI":"10.1109\/SFCS.1983.35"},{"issue":"2","key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1111\/j.2517-6161.1988.tb01721.x","article-title":"Local computations with probabilities on graphical structures and their application to expert systems","volume":"50","author":"Lauritzen S. L.","year":"1988","journal-title":"J. R. Stat. Soc. B"},{"key":"e_1_2_1_15_2","first-page":"39","volume-title":"Combinatorial Optimization: Annotated Bibliographies","author":"Papadimitriou C. H.","year":"1985"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90045-5"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90072-X"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90012-9"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90054-3"},{"volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","year":"1988","author":"Pearl J.","key":"e_1_2_1_20_2"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.4.589"},{"volume-title":"Proceedings of the Fifth Workshop on Uncertainty in Artificial Intelligence","author":"Shachter R. D.","key":"e_1_2_1_22_2"},{"key":"e_1_2_1_23_2","unstructured":"A. J.SinclairandM. R.Jerrum Approximate counting uniform generation and rapidly mixing Markov chains. Technical Report CSR\u2010241\u201087 Department of Computer Science University of Edinburgh Edinburgh Scotland UK (1987)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230200510","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230200510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:48:29Z","timestamp":1737006509000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230200510"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,8]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1990,8]]}},"alternative-id":["10.1002\/net.3230200510"],"URL":"https:\/\/doi.org\/10.1002\/net.3230200510","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[1990,8]]}}}