{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T08:13:08Z","timestamp":1760170388466},"reference-count":44,"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":4819,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1993,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A belief network is a graphical representation of the underlying probabilistic relationships in a complex system. Belief networks have been employed as a representation of uncertain relationships in computer\u2010based diagnostic systems. These diagnostic systems provide assistance by assigning likelihoods to alternative explanatory hypotheses in response to a set of findings or observations. Approximation algorithms have been used to compute likelihoods of hypotheses in large networks. We analyze the performance of leading Monte Carlo approximation algorithms for computing posterior probabilities in belief networks. The analysis differs from earlier attempts to characterize the behavior of simulation algorithms in our explicit use of Bayesian statistics: We update a probability distribution over target probabilities of interest with information from randomized trials. For real \u03f5, \u03b4 &lt; 1 and for a probabilistic inference Pr[<jats:italic>x<\/jats:italic>|<jats:italic>e<\/jats:italic>], the output of an inference approximation algorithm in an (\u03f5, \u03b4)\u2010<jats:italic>estimate<\/jats:italic> of Pr[<jats:italic>x<\/jats:italic>|<jats:italic>e<\/jats:italic>] if with probability at least 1 \u2013 \u03b4 the output is within relative error \u03f5 of Pr[<jats:italic>x<\/jats:italic>|<jats:italic>e<\/jats:italic>]. We construct a stopping rule for the number of simulations required by <jats:italic>logic sampling, randomized approximation schemes<\/jats:italic>, and <jats:italic>likelihood weighting<\/jats:italic> to provide (\u03f5, \u03b4)\u2010estimates of Pr[<jats:italic>x<\/jats:italic>|<jats:italic>e<\/jats:italic>]. With Probability 1 \u2013 \u03b4, the stopping rule is <jats:italic>optimal<\/jats:italic> in the sense that the algorithm performs the minimum number of required simulations. We prove that our stopping rules are insensitive to the prior probability distribution on Pr[<jats:italic>x<\/jats:italic>|<jats:italic>e<\/jats:italic>]. \u00a9 <jats:italic>1993 by John Wiley &amp; Sons, Inc.<\/jats:italic><\/jats:p>","DOI":"10.1002\/net.3230230506","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T16:18:17Z","timestamp":1178986697000},"page":"499-516","source":"Crossref","is-referenced-by-count":15,"title":["A Bayesian analysis of simulation algorithms for inference in belief networks"],"prefix":"10.1002","volume":"23","author":[{"given":"Paul","family":"Dagum","sequence":"first","affiliation":[]},{"given":"Eric","family":"Horvitz","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"S.Andreassen M.Woldbye B.Flack andS.Andersen MUNIN\u2014A causal probabilistic network for interpretation of electromyographic findings.Proceedings of 10th International Joint Conference on Artificial Intelligence Milan Italy (1987)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"I.Beinlich H.Suermondt R.Chavez andG.Cooper The ALARM monitoring system: A case study with two probabilistic inference techniques for belief networks.Proceedings of the Second European Conference on Artificial Intelligence.Berlin. Springer\u2010Verlag (1989).","DOI":"10.1007\/978-3-642-93437-7_28"},{"key":"e_1_2_1_4_2","unstructured":"P.Billingsley Convergence of Probability Measures. New York (1968)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"J.Breese E.Horvitz M.Peot R.Gay andG.Quentin Automated decision\u2010analytic diagnosis of thermal performance in gas turbines.Proceedings of Turbine Expo 92.American Society of Mechanical Engineers (1992).","DOI":"10.1115\/92-GT-399"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"A.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"},{"key":"e_1_2_1_7_2","unstructured":"R.Chavez Architectures and approximation algorithms for probabilistic expert systems. PhD Thesis Department of Computer Science and Medicine Stanford University Stanford CA (1990)."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230200510"},{"key":"e_1_2_1_9_2","unstructured":"G.Cooper NESTOR: A Computer\u2010based medical diagnostic aid that integrates causal and probabilistic knowledge. PhD Thesis Computer Science Department Stanford University Stanford CA (1984). Report No. STAN\u2010CS\u201084\u201048. Also numbered HPP\u201084\u201048."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(90)90060-D"},{"key":"e_1_2_1_11_2","unstructured":"P.DagumandR.Chavez Approximating probabilistic inference in Bayesian belief networks. Technical Report KSL\u201091\u201046 Knowledge Systems Laboratory Stanford University Stanford CA (1991).Pattern Anal. Machine Intell. special issue on probabilistic reasoning to appear."},{"key":"e_1_2_1_12_2","unstructured":"P.DagumandE.Horvitz An analysis of Monte\u2010Carlo algorithms for probabilistic inference. Technical Report KSL\u201091\u201067 Knowledge Systems Laboratory Stanford University Stanford CA (1991)."},{"key":"e_1_2_1_13_2","unstructured":"P.DagumandM.Luby Approximating probabilistic inference in Bayesian belief networks in NP\u2010hard. Technical Report KSL\u201091\u201051 Knowledge Systems Laboratory Stanford University Stanford CA (1991).Artific. Intell. to appear as a research note."},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176345391"},{"key":"e_1_2_1_15_2","unstructured":"R.FungandK.Chang Weighting and integrating evidence for stochastic simulation in Bayesian networks.Proceedings of Fifth Workshop on Uncertainty in Artificial Intelligence Windsor ON.Association for Uncertainty in Artificial Intelligence Mountain View CA (1989)112\u2013117."},{"key":"e_1_2_1_16_2","unstructured":"A.GelmanandD. B.Rubin An overview and approach to inference from iterative simulation.Workshop on Bayesian Computation via Stochastic Simulation(1991)."},{"key":"e_1_2_1_17_2","volume-title":"Table of Integrals, Series and Products","author":"Gradshteyn I. S.","year":"1980"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8242-3"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"D.Heckerman E.Horvitz andB.Nathwani Toward normative expert systems: The Pathfinder project.Method Inform. Med.(1992).","DOI":"10.1055\/s-0038-1634867"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-70396-5.50019-4"},{"key":"e_1_2_1_21_2","first-page":"385","volume-title":"Influence Diagrams, Belief Networks, and Decision Analysis","author":"Henrion M.","year":"1990"},{"key":"e_1_2_1_22_2","first-page":"64","article-title":"Decision analysis and expert systems","volume":"12","author":"Henrion M.","year":"1992","journal-title":"AI Mag."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0888-613X(88)90120-X"},{"key":"e_1_2_1_24_2","unstructured":"E.Horvitz H.Suermondt andG.Cooper Bounded conditioning: Flexible inference for decisions under scarce resources.Proceedings of Fifth Workshop on Uncertainty in Artificial Intelligence Windsor ON.Association for Uncertainty in Artificial Intelligence Mountain View CA (1989)182\u2013193."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1970.7719"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90038-2"},{"issue":"19","key":"e_1_2_1_28_2","article-title":"Local computations with probabilities on graphical structures and their application to expert systems","volume":"50","author":"Lauritzen S.","year":"1988","journal-title":"J. Royal Stat. Sco. B"},{"key":"e_1_2_1_29_2","first-page":"816","article-title":"The INTERNIST\u20101\/Quick Medical Reference project\u2010status report","volume":"145","author":"Miller R.","year":"1986","journal-title":"West. J. Med."},{"key":"e_1_2_1_30_2","unstructured":"G.Nino\u2010MurciaandM.Shwe An expert system for diagnosis of sleep disorders.1991 Annual Meeting Abstracts Association of Professional Sleep Societies Toronto Canada (1991)165."},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90054-3"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90012-9"},{"key":"e_1_2_1_33_2","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"Pearl J.","year":"1988"},{"key":"e_1_2_1_34_2","volume-title":"Calculus with Analytic Geometry","author":"Purcell E. J.","year":"1972"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"A. E.RafteryandS.Lewis How many iterations in the gibbs sampler.Bayesian Statistics 4.Oxford University Press Oxford (1992)765\u2013776.","DOI":"10.21236\/ADA640705"},{"key":"e_1_2_1_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316511"},{"key":"e_1_2_1_37_2","unstructured":"G.Rutledge G.Thomsen I.Beinlich B.Farr B.Sheiner andL.Fagan Combining qualitative and quantitative computation in a ventilator therapy planner.Proceedings of the Thirteenth Annual Symposium on Computer Applications in Medical Care.The American Medical Informatics Association Washington DC (1989)315\u2013319."},{"key":"e_1_2_1_38_2","volume-title":"Non\u2010negative Matrices and Markov Chains","author":"Seneta E.","year":"1973"},{"key":"e_1_2_1_39_2","article-title":"Evidential reasoning using likelihood weighting","author":"Shachter R.","journal-title":"Artific. Intell."},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88738-2.50024-5"},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4809(91)90020-W"},{"key":"e_1_2_1_42_2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1055\/s-0038-1634846","article-title":"Probabilistic diagnosis using a reformulation of the INTERNIST\u20101\/QMR knowledge base\u2014I: The probabilistic model and inference algorithms","volume":"30","author":"Shwe M.","year":"1991","journal-title":"Methods Inform. Med."},{"key":"e_1_2_1_43_2","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1055\/s-0038-1634847","article-title":"Probabilistic diagnosis using a reformulation of the INTERNIST\u20101\/QMR knowledge base\u2010II: Evaluation of diagnostic performance","volume":"30","author":"Shwe M.","year":"1991","journal-title":"Methods Inform. Med."},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_45_2","first-page":"36","volume":"12","author":"von Neumann J.","year":"1951","journal-title":"Natl. Bur. Stand. Appl. Math. Ser."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230230506","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230230506","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T10:37:21Z","timestamp":1698230241000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230230506"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,8]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1993,8]]}},"alternative-id":["10.1002\/net.3230230506"],"URL":"https:\/\/doi.org\/10.1002\/net.3230230506","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,8]]}}}