Evidential Reasoning in Semantic Networks: A Formal Theory

Abstract

This paper presents an evidential approach to kn o wledge representation and inference wherein the prin ciple of maximum entropy is applied to deal with uncertainty and incompleteness. It focuses on a restricted rep resentation language - similar in expressive power to se mantic network formalisms. and develops a formal th eo ry of evidential inheritance wtthin this language. The th eo ry applies to a limited, but we think interesting, class o f inh eritance problems including those that involve exceptions and multiple inheritance hierarchies. The lan guage and the accompanying evidential inference structure provide a natural treatment of defaults and conllicting information. The evidence combination rule propos ed in this paper is incremental, commutative and C~ ssoc iative and hence, shares most of the attractive fea tures o f the Dempster-Shafer evidence combination rul e. Furthermore. it is demonstrably better than the Dempster-Shafer rule in the context of the problems a ddr ess ed in this paper. The resulting theory can be implem ented as a highly parall el (connectionist) network made up o f active elements that can solve inheritance pro bl ems in time proportional to the depth of the conceptual hierarchy.