On the complexity of belief network synthesis and refinement

AbstractBelief networks are important objects for research study and for actual use, as the experience of the MUNIN project demonstrates. There is evidence that humans are quite good at guessing network structure but poor at settling values for the numerical parameters. Determining these parameters by standard statistical techniques often requires too many sample points (test cases) for larger systems, so knowledge engineers have sought direct algorithms to define or adjust the parameters by appeal to selected test cases. It is shown for both Dempster-Shafer networks and Bayesian networks that for very simple networks (trees), defining parameter values (synthesis) or refining expert-estimated values (refinement) can be computationally intractable. These unpleasant results hold even when we settle for approximate values or demand agreement on only a certain percentage of cases