B egin Set icon

B egin Set

НазваниеB egin Set
Дата конвертации26.09.2012
Размер22.26 Kb.

Estimating Component Availability by Dempster-Shafer Belief Networks

Lan Guo

LDCSEE, West Virginia University, Morgantown, WV 26506-6109


  1. Introduction

Dempster-Shafer (D-S) Belief Network is a complete formalism of evidential reasoning for computing and propagating evidential (confirming or disconfirming) support throughout the network. The D-S evidential representation and inference scheme is a more general and robust theory than the Bayesian theory [1]. In this paper, we propose a novel methodology to induce the D-S belief networks. Our method is validated by an empirical example of component availability estimation.

  1. D-S Belief Network Induction

We use prediction logic based on a contingency table of probabilities [3] to induce the belief network. The drawback of the induction algorithm proposed by Liu et al. [2] is its dramatic dependence on the sample size. Additionally, their algorithm violates the assumption of the binomial distribution that the sample size must be constant. In [2], the sample sizes used for deriving modus ponens and modus tollens are random, only the total size of the contingency table is constant. Therefore, using binomial distribution for implication induction is improper and leads to erroneous results. We used a modified -Optimality method [3] to derive the proposition between two events as shown in Figure 1.



Set a significance level min and a minimal Umin

For nodep, p  [0, nmax – 1] and nodeq, q  [p + 1, nmax] (Note: nmax is the total number of nodes)

For all empirical case samples N

N11 N12

N21 N22
Compute a contingency table

Mpq =

For each relation type k find the solution to

Max Up

Subject to Max Up > Umin


ij = 1 or 0 (if Nij corresponds to an error cell, ij = 1; otherwise, ij = 0)

(b) > (b’) if (b) = 1 and (b’) = 0

If the solution exists, then return a type k relation

Figure 1. The Implication Induction Algorithm

For a single error cell, if Nij is the number of error occurrences, we have: Up = Uij =

p = ij = 1-

For multiple error cells,

Up = *Uij

(ij = 1 for error cells; otherwise, ij = 0)

p = ij

In our algorithm, the logical equivalent relations are derived only once and carry different weight. We use a quintuple to represent each implication rule:

IЇ, I=ant, Ncon, WI, WI’>

Where WI and WIare weight functions mapping the antecedent-consequent nodes, i.e., Nant and Ncon, for the relation type R:

WI: Nant x Ncon  [0, 1]

WI’: Ncon x Nant  [0, 1]

  1. Reasoning Based on the D-S Belief Network

In the D-S belief networks, the set of all possible outcomes of a node is called the frame of discernment, , which must be exhaustive and disjoint. The D-S theory allows a basic probability assignment to the subsets of a conclusion, which satisfies: m: 2  [0, 1], m() = 0, and. When evidence about a certain node arrives, the beliefs of this node can be updated by Dempster’s rule of combination [1]. For  = {a, a},

Bel(a) = m’(a) =

Bel(a) = m’(a) =

Due to the node connectivity, the updated belief can be propagated throughout the network by the algorithm stated in [2].

  1. ^ Empirical Validation

In this experiment, the data set was generated from the Bayesian network used for estimating component availability [4] in a large distributed network. There are 1,100 model components called network access devices (NAD) in the whole network. There are six basic types of failures that occur everyday: power failures, reset button failures, address failures, bus failures, configuration failures, and other failures. Repeated failures are grouped as software error, configuration error, and operational error. Component availability is linked to the corresponding failure nodes.

Based on the node probability tables associated with the Bayesian network, we generated two sets of data samples: one for constructing the D-S network with 1000 data points, and the other for validating the inference scheme with 100 data points. There are only two states for each node in the network. For the failure type nodes, the two states are low failure occurrences (represented by 1) and high failure occurrences (represented by 0) with the corresponding failure number ranges. For availability node, the two states are available (represented by 1) and unavailable (represented by 0).

Next, we applied the implication induction algorithm, described in Section 2, to induce the implication relationships between pairs of nodes based on the data simulated. This step builds the D-S belief network automatically from the data.

For the testing sample, we randomly selected an unobserved node and used its value as the new evidence and propagated the updated belief values to the other nodes reachable from the observed one.

For each of the unobserved nodes, we compared the belief value predicted and the value in the testing sample, and output the difference by the evaluation metrics computed (see below). We continued step 4 and 5 until all nodes were observed.

The absolute difference between the actual value in the testing sample and the computed belief value is defined as:

X = | Belemp(X) – Belest(X)|

The evaluation metrics are the mean error and the standard error of estimate defined as:


Where nmax is the number of nodes in the network, NS is the number of simulated testing samples. In this case, nmax =10 and NS = 100.

The implication method performance of the constructed D-S network was compared with the performance when no inference propagation was performed (where the frequency of event occurrences are used as beliefs) in Figure 2.

Figure 2. The mean estimate error in two different modes of observation

  1. Conclusions

This paper presented a novel, efficient, and dynamic means to automatically construct D-S belief networks. The method is free of subjective biases, which is an important advantage over the Bayesian belief networks. In contrast to the implication induction algorithm by Liu et al. [2], which gives erroneous results, our induction algorithm is a sound prediction method. The validity of the D-S belief network inducted and the implication inference algorithms is demonstrated in the experiment. The prediction error is greatly reduced by the implication method over the D-S network compared to the performance without inference propagation. The predicted component availability of 67.8% is much closer to the observations from the 100 testing samples (74.0%). For the same data set, traditional probability solution offers 89.3% availability and the Bayesian network prediction is 89.4% [4].

This study is the first attempt to utilize the D-S belief network for software reliability engineering. We believe it is a promising methodology. This general method could also be applied in other areas. Our future work includes employing the entropy notion for optimal inference for greater prediction accuracy over the whole network.


  1. Shafer G. A Mathematical Theory of Evidence, Princeton University Press, 1976.

  2. Liu J. and Desmarais M. C. A Method of Learning Implication Networks from Empirical Data: Algorithm and Monte-Carlo Simulation-Based Validation, IEEE Transactions on Knowledge and Data Engineering, Vol. 9, No. 6, Nov./Dec. 1997.

  3. Hildebrand D. K. Laing J. D. and Rosenthal H. Prediction Analysis of Cross Classifications, New York: John Wiley & Sons, 1977.

  4. Yu Y. and Stoker E. A Comparison of Probability and Bayesian Belief Networks Methods to Estimate Component Availability in Large, Distributed Networks, ISSRE 2001 Student Paper, 2001.


B egin Set iconДокументы
1. /C60_schematics/Diagram Set C60.pdf
B egin Set iconДокументы
1. /!The Elder Scrolls 4 Construction Set!.doc
B egin Set iconGeneral notes on functional sтyles of language
А functional style is thus to bе regarded as the product of а certain concrete task set bу the sender of the message. Functional...
B egin Set iconВнеклассное мероприятие Thanksgiving Day Сарайкина В. И. Thanksgiving Day Вступительное слово: 1-ый ведущий: Good afternoon, ladies and gentlemen!
Учитель: The first game is carrot pitching. Each player takes a carrot and throws it into a basket from a set distance. The winning...
B egin Set iconЗадача по расчету характеристик set транзистора состоит в том, чтобы вычислить средний ток через транзистор для фиксированных значений напряжения на нем и его затворе при заданной температуре.
Почтовый адрес: 117296, Ломоносовский просп. 16, Телефон/факс: (095) 133-2435, е-mail: info@lit msu ru
B egin Set iconДокументы
1. /Led Zeppelin/Led Zeppelin/1969 - Led Zeppelin I/01-Good Times Bad Times.rtf

B egin Set iconДокументы
1. /Annihilator/1989 - Alice In Hell/01 - Crystal Ann.txt
2. /Annihilator/1989...

B egin Set iconДокументы
1. /doors/Texts/Jim Morrison/1978 - An American Prayer - part 1/01 - Awake Ghost Song.txt
B egin Set iconДокументы
1. /Texts/1993 - I'm Falling (single)/Believe In Me.txt
2. /Texts/1993...

B egin Set iconДокументы
1. /urok7/konspekt.doc
2. /urok7/practika.doc
Разместите кнопку на своём сайте:

База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации