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.