We thank anonymous referees for several insightful comments that led to a substantial improvement of the paper. This research was supported by the National Science Foundation under Faculty Early Career Development (CAREER) Program, grant IRI-9624629, and by the Air Force Office of Scientific Research grants F49620-97-1-0225 and F49620-00-1-0112. An earlier version of this paper has received the 2000 School of Information Sciences Robert R. Korfhage Award, University of Pittsburgh. Malcolm Pradhan and Max Henrion of the Institute for Decision Systems Research shared with us the CPCS network with a kind permission from the developers of the INTERNIST system at the University of Pittsburgh. We thank David Heckerman for the PATHFINDER network and Abigail Gerner for the ANDES network used in our tests. All experimental data have been obtained using SMILE, a Bayesian inference engine developed at the Decision Systems Laboratory and available at http://www2.sis.pitt.edu/genie.