Inference Algorithms For Bayesian Networks And A Tool For Developing Agricultural Expert System Based On Bayesian Networks

Uncertain information processing is an important research area in Artificial intelligence. From viewpoint of expert system, all the processing approaches fall into two categories - rule-based and model-based ones. One of the model-based approaches, Bayesian networks, was developed in 1980's and has been paid increasing attention to since 1990's. Compared with the early rule-based approaches, it has more clear semantics and usually makes more reasonable conclusions, but involves much more calculation.Inference in general Bayesian networks is NP hard. So far tens of Inference algorithms have been developed to make Bayesian networks as practical as possible. All the algorithms fall into two categories- exact ones and approximate ones. Three early algorithms- Belief-Net-Ask, message-passing and variable elimination, lay the foundations of other inference algorithms. Belief-Net-Ask can calculate posterior distribution for a single node in a Bayesian network of tree form. Message-Passing can calculate posterior distributions for multiple nodes in a Bayesian network of tree form. Variable elimination can calculate posterior distribution for a single node in a multi-connected Bayesian network. The three algorithms are typical since they have their own characteristics. In this paper, mathematical description, comparison and characterization of the nature of the three algorithms are presented on the basis of introduction to basic concepts of Bayesian networks.The computational complexity of variable elimination is O(n?cw), where n is the number of nodes in a Bayesian network, d is the maximal indegree of nodes, c is the maximal number of assignments of nodes, and w is referred to as width of elimination order. In variable elimination, the elimination order has no influence on the correctness of inference results, but has great influence on the computation. There exist one or more optimal elimination orders, which makes w minimal, with respect to a given Bayesian network. In fact, w is still the major reason of high complexity in most inference algorithms. Therefore, two aspects are often considered when the efficiency should be improved: one is searching for an optimal or almost optimal w, the other is (exactly or approximately) simplifying the structures of Bayesian networks.Simplifying strategies are discussed in this paper. Omitting operation is defined on the basis of pruning-node method. Replacing operation is proposed in viewpoint of preprocessing. Three conditions, which can be used to simplify Bayesian network structure, are presented, and traversing operation is given in a further step. Proofs based on probability theory and Bayesian network's semantics are made for all these operations. The relations of these operations are discussed. Empirical tests show that they can reduce computations with respect to concrete queries in most cases.Another aspect of this paper is the discussion about the software component for developing agricultural expert systems based on Bayesian network. Along with it, some critical problems in analysis and design for agriculture expert systems are described and answered.Research about agricultural expert system started in 1970's. With the increasing development in expert system and the support of governments in all nations, expert system has been greatly used in agriculture to provide instructions in the procedure of prediction, decision, diagnosis and control and has become a very useful tool for the industrialization of agriculture. Agricultural expert system is a remarkable field in the research area of intelligent agricultural information technology. In our country, "Intelligent Agricultural Information Technologies Application and Demonstration Projects" has been listed into National 863 Hi-Tech R&D Program. IPDIAS (Integrated Platform for Developing Intelligent Agricultural System) is a significant research task in this project. In this paper, we introduce a software component in IPDIAS for developing agricultural expert systems based on Bayesian networks.Besides th...