یک روش ساده گرافیکی برای درک استنتاج احتمالاتی در شبکه های بیزی
|کد مقاله||سال انتشار||مقاله انگلیسی||ترجمه فارسی||تعداد کلمات|
|28774||2009||18 صفحه PDF||سفارش دهید||11203 کلمه|
Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Information Sciences, Volume 179, Issue 6, 1 March 2009, Pages 699–716
We present a simple graphical method for understanding exact probabilistic inference in discrete Bayesian networks (BNs). A conditional probability table (conditional) is depicted as a directed acyclic graph involving one or more black vertices and zero or more white vertices. The probability information propagated in a network can then be graphically illustrated by introducing the black variable elimination (BVE) algorithm. We prove the correctness of BVE and establish its polynomial time complexity. Our method possesses two salient characteristics. This purely graphical approach can be used as a pedagogical tool to introduce BN inference to beginners. This is important as it is commonly stated that newcomers have difficulty learning BN inference due to intricate mathematical equations and notation. Secondly, BVE provides a more precise description of BN inference than the state-of-the-art discrete BN inference technique, called LAZY-AR. LAZY-AR propagates potentials, which are not well-defined probability distributions. Our approach only involves conditionals, a special case of potential.
Bayesian networks (BNs) , , , , , , , , ,  and  are an established framework for uncertainty management in artificial intelligence. For instance, they have been applied in building intelligent agents, such as Office Assistant, and adaptive user interfaces by Microsoft ,  and , process control by NASA  and  and Lockheed , software diagnosis by Hewlett–Packard  and  and Nokia , and medical diagnosis such as the heart disease program  at the Massachusetts Institute of Technology and the Pathfinder Project for lymph-node diseases  at the Stanford University. A BN consists of a directed acyclic graph (DAG) and a corresponding set of conditionals (conditional probability tables) . The probabilistic conditional independencies (CIs)  and  encoded in the DAG indicate the product of the conditionals is a joint probability distribution . Thus, BNs provide a clear semantic modelling tool facilitating the acquisition of probabilistic knowledge. On the other hand, it is widely acknowledged , , , ,  and  that understanding inference algorithms in BNs is an arduous task. Jensen  explicitly states that probabilistic reasoning literature is not meant for readers looking for a way into the field. Understanding a probabilistic inference algorithm is not trivial . Although practical applications require multiply connected BNs , newcomers are usually introduced to inference algorithms conducted on singly connected BNs (SCBNs), a special case of BNs. Kim and Pearl  proposed one such algorithm, called propagation in singly connected BNs (PIS) . Even for inference in SCBNs, Russell and Norvig  state that some of the mathematics and notation are unavoidably intricate. Furthermore, Neapolitan  writes that inference in a tree BN, a special case of SCBN, is not very transparent. We advocate that the use of potentials ,  and  is the biggest hindrance to the comprehension of probabilistic inference in BNs. Potentials do not have clear physical interpretation  as they are not well-defined probability distributions . Yet, potentials play an integral part in the numerous inference algorithms developed for multiply connected BNs , , , , , , , , ,  and . Even worse, inference in SCBNs , ,  and  is more complicated in the sense that two types of potentials are needed, namely, λλ-potentials are propagated upwards in the SCBN, while ρρ-potentials are propagated downwards. Thus, it is not surprising that beginners experience difficulty grasping probabilistic inference. In this paper, we propose a simple graphical approach for understanding exact probabilistic inference in discrete BNs. A conditional is represented as a graphional , which is a DAG involving one or more black vertices and zero or more white vertices. More specifically, given a conditional Pr(X|Y)Pr(X|Y), the corresponding graphional Gr(X|Y)Gr(X|Y) has a directed edge from each variable in YY to each variable in XX. Those variables in XX are represented by black vertices, while variables in YY are depicted using white vertices. BN inference is described using the join tree propagation (JTP) framework , ,  and . In JTP, messages are systematically passed in a join tree (JT)  and  constructed from the DAG of the BN. We present an algorithm, called black variable elimination (BVE), to graphically illustrate the conditionals being passed from a JT node to a neighbour. We establish the polynomial time complexity of BVE. In addition, we prove the correctness of BVE by showing that the conditionals depicted by our approach are exactly the same as the messages passed by LAZY-AR ,  and , the state-of-the-art algorithm for exact inference in discrete BNs. There are two favourable features of our approach. Our purely graphical method can be used as a pedagogical tool to introduce SCBN inference. We propose the SCBN2JT algorithm to build a special JT from a SCBN. We show that the messages passed in our constructed JT using the BVE algorithm are exactly the same as those passed in the given SCBN using the PIS algorithm. The difference being BVE is purely graphical, whereas PIS requires intricate mathematical equations and two types of potentials. Our method also provides a more detailed perspective on inference in multiply connected BNs for experienced practitioners. LAZY-AR propagates potentials in a JT. On the contrary, our approach graphically describes this same probability information in terms of conditionals. There should be an improvement in clarity, since conditionals are a special case of potentials. This paper is organized as follows. Section 2 contains definitions. A graphical approach to probabilistic inference is given in Section 3. Section 4 provides the theoretical foundation of our approach. We show how our approach can be used to introduce SCBN inference in Section 5. Section 6 shows how our method can clarify inference in multiply connected BNs. Conclusions are provided in Section 7.
نتیجه گیری انگلیسی
It is widely acknowledged that comprehension of exact probabilistic inference in discrete BNs is regarded as a complicated task. In this paper, we propose a simple graphical inference method for understanding probabilistic inference in BNs. The probability information propagated in a network can be graphically depicted by introducing the black variable elimination (BVE) algorithm. We have implemented the BVE algorithm and have included screen-shots depicting inference in SCBNs and multiply connected BNs with and without evidence. We argue that there is some improvement in clarity. Our graphical inference approach then can be used as a pedagogical tool for introducing SCBN inference algorithm to newcomers. As established in Lemma 2, the potentials passed by PIS in SCBN are exactly those conditionals passed by BVE in the JT we construct from the SCBN. Example 19 shows that, for inference without evidence in a SCBN, the PIS potentials in Fig. 15 exactly correspond to the BVE conditionals in Fig. 12. Example 20 demonstrates that, for inference with evidence in a SCBN, the PIS potentials in Fig. 16 precisely coincide with the BVE conditionals in Fig. 13. The PIS algorithm involves intricate mathematical equations and notation  and propagates two kinds of potentials. Our approach is purely graphical and propagates conditionals, a special case of potential. Castillo et al.  explicitly state that conditionals are easily interpretable in contrast with general potentials, since conditionals are well-defined probability distributions. The second main advantage of our approach is that it provides a more refined perspective on inference in multiply connected BNs for experienced practitioners. Theorem 2 shows that the conditionals passed by BVE exactly coincide with the potentials propagated by LAZY-AR, the state-of-the-art method for exact inference in discrete BNs ,  and . Example 22 illustrates that the LAZY-AR potentials in Fig. 6 are exactly those BVE conditionals in Fig. 8. It is important to realize that the LAZY-AR potential ϕ(f,g)ϕ(f,g) in Fig. 6 is actually the conditional Pr(g|f)Pr(g|f) in Fig. 8. Example 23 makes the same point for inference involving evidence. The realization of structure by BVE is justified. While the AR Eqs. (1) and (2) were developed for inference in a well-defined BN, Lemma 4 and Lemma 5 show that the AR equations also hold during JTP. By utilizing the two independencies holding in Lemma 3, the distributions propagated in a JT are conditionals as Lemma 4 and Lemma 5 indicate. Therefore, the probability information being passed in a JT should be described in terms of conditionals rather than as potentials as LAZY-AR does in Algorithm 1.