More Results on the Complexity of Knowledge Base Refinement: Belief Networks
Abstract
The refinement of knowledge bases is an important activity in the expert system lifecycle. Belief networks have been proposed and studied as an alternative to rules in expert system knowledge bases. The problems of synthesis and refinement of belief networks arising from the development of a large belief-network-based knowledge-based system, are presented and formally analyzed. We prove that, for very simple Dempster-Shafer networks (trees), defining parameter values (synthesis) is NP-Complete. Additional results that are given without proof include the computational intractability of refining expert- estimated values (refinement), even when we settle for approximate values or demand agreement on only a certain percentage of cases. The potential impact of these results on the practice of expert system construction is discussed.
Cite
Text
Valtorta. "More Results on the Complexity of Knowledge Base Refinement: Belief Networks." International Conference on Machine Learning, 1990. doi:10.1016/B978-1-55860-141-3.50053-5Markdown
[Valtorta. "More Results on the Complexity of Knowledge Base Refinement: Belief Networks." International Conference on Machine Learning, 1990.](https://mlanthology.org/icml/1990/valtorta1990icml-more/) doi:10.1016/B978-1-55860-141-3.50053-5BibTeX
@inproceedings{valtorta1990icml-more,
title = {{More Results on the Complexity of Knowledge Base Refinement: Belief Networks}},
author = {Valtorta, Marco},
booktitle = {International Conference on Machine Learning},
year = {1990},
pages = {419-426},
doi = {10.1016/B978-1-55860-141-3.50053-5},
url = {https://mlanthology.org/icml/1990/valtorta1990icml-more/}
}