《电子商务 E-business》阅读文献：Requirements for total_uncertainty measures in D-S theory of evidence.pdf

Intemational Journal of General Systems Taylor Francis vol.37,No.6, December2008,733-747 Requirements for total uncertainty measures in Dempster-Shafi theory of evidence Joaquin Abellan*and Andres Masegosa Department of Computer Science and Artificial Intelligence, University of granada, Received 9 October 2007, final version received 6 March 2008) Recently, an alternative measure of total uncertainty in Dempster-Shafer theory of evidence(dst)has been proposed in place of the maximum ent on the pignistic probability of a basic probability assignment and it is proved that this z∞一 asure verifies a set of needed properties for such a type of measur measure is motivated by the problems that maximum(upper)entropy has. In this yas o we analyse the requirements, presented in the literature, for total uncertainty measures DST and the shortcomings found on them. We extend the set of requirements, which we consider as a set of requirements of properties, and we use the set of shortcomings found on them to define a set of requirements of the behaviour for total uncertainty measures in DST. We present the differences of the principal total uncertainty measures presented in DST taking into account their properties and behaviour. Also, an experimental comparative study of the performance of total uncertainty measures in DST on a special type of belief decision trees is presented. Keywords: imprecise probabilities; theory of evidence; uncertainty based in total uncertainty: conflict; non-specificity In the classical theory of probability, Shannons entropy(Shannon 1948)is the tool used for quantifying uncertainty. Its main virtue is that it verifies a set of desirable properties for probability distributions In situations where the probabilistic representation is inadequate, an imprecise probability theory can be used as seen in Walley(1991), such as Dempster Shafer's theory (DST)(Dempster 1967, Shafer 1976), interval-valued probabilities Campos et al. 1994), order-two capacities( Choquet 1953/54), upper-lower probabilities (Suppes 1974, Fine 1983)or general convex sets of probability distributions( Good 1962, Levi 1980, Walley 1991), also called credal sets. In order to quantify the uncertainty represented by these situations, Shannons entropy has been used as the starting point It can be justified in different ways, but the most common one is the axiomatic approach, i.e. by assuming a set of necessary basic properties that a measure must verify(Klir and Wierman 1998). In Dempster-Shafer's theory (dSt), Yager(1983)distinguishes between two types of uncertainty: conflict (or randomness or discord) and non-specificity. A total uncertainty measure is also justified in this theory by an axiomatic approach considering the one used in probability theory as a reference. We believe that some aspects of dST that do not Corresponding author. Email: jabellan, andrew I @decsaiugres ISSN 0308-1079 print/ISSN 1563-5104 online Taylor Francis 108003081070802082486

Requirements for total uncertainty measures in Dempster–Shafer theory of evidence Joaquı´n Abella´n* and Andre´s Masegosa Department of Computer Science and Artificial Intelligence, University of Granada, Granada, Spain ( Received 9 October 2007; final version received 6 March 2008 ) Recently, an alternative measure of total uncertainty in Dempster–Shafer theory of evidence (DST) has been proposed in place of the maximum entropy measure. It is based on the pignistic probability of a basic probability assignment and it is proved that this measure verifies a set of needed properties for such a type of measure. The proposed measure is motivated by the problems that maximum (upper) entropy has. In this paper, we analyse the requirements, presented in the literature, for total uncertainty measures in DST and the shortcomings found on them. We extend the set of requirements, which we consider as a set of requirements of properties, and we use the set of shortcomings found on them to define a set of requirements of the behaviour for total uncertainty measures in DST. We present the differences of the principal total uncertainty measures presented in DST taking into account their properties and behaviour. Also, an experimental comparative study of the performance of total uncertainty measures in DST on a special type of belief decision trees is presented. Keywords: imprecise probabilities; theory of evidence; uncertainty based information; total uncertainty; conflict; non-specificity 1. Introduction In the classical theory of probability, Shannon’s entropy (Shannon 1948) is the tool used for quantifying uncertainty. Its main virtue is that it verifies a set of desirable properties for probability distributions. In situations where the probabilistic representation is inadequate, an imprecise probability theory can be used as seen in Walley (1991), such as Dempster– Shafer’s theory (DST) (Dempster 1967, Shafer 1976), interval-valued probabilities (Campos et al. 1994), order-two capacities (Choquet 1953/54), upper-lower probabilities (Suppes 1974, Fine 1983) or general convex sets of probability distributions (Good 1962, Levi 1980, Walley 1991), also called credal sets. In order to quantify the uncertainty represented by these situations, Shannon’s entropy has been used as the starting point. It can be justified in different ways, but the most common one is the axiomatic approach, i.e. by assuming a set of necessary basic properties that a measure must verify (Klir and Wierman 1998). In Dempster–Shafer’s theory (DST), Yager (1983) distinguishes between two types of uncertainty: conflict (or randomness or discord) and non-specificity. A total uncertainty measure is also justified in this theory by an axiomatic approach considering the one used in probability theory as a reference. We believe that some aspects of DST that do not ISSN 0308-1079 print/ISSN 1563-5104 online q 2008 Taylor & Francis DOI: 10.1080/03081070802082486 http://www.informaworld.com *Corresponding author. Email: {jabellan,andrew}@decsai.ugr.es International Journal of General Systems Vol. 37, No. 6, December 2008, 733–747 Downloaded by [New York University] at 12:09 08 November 2011

J. Abellan and A. Masegosa appear in classical probability theory, such as monotonicity, should be taken into account when studying the axiomatic approach Maeda and Ichihashi(1993) proposed a total uncertainty measure on DST adding up le generalised Hartley measure and upper entropy. They proved that this total uncertainty measure verifies all the necessary basic properties except for the required range. This property could, however, be discussed since there are more types of uncertainty in DST than in the probability theory DST is considered as a particular theory of credal sets. By applying the uncertainty invariance principle, a total uncertainty measure on general credal sets will be a generalisation of a total uncertainty measure on DST. With this aim, various studies of the quantification of uncertainty on credal sets have been published(Abellan and Moral Ez∞ 2003a, 2005b: Abellan et al. 2006) In Abellan and Moral (2003a), it is proved that the maximum of Shannons entropy (upper entropy) verifies on general credal sets all the basics properties that it verifies on DST. In Abellan and Moral (2005a) and Klir and Smith(2001), the use of maximum entropy on credal sets as a good measure of total uncertainty is justified. The problem lies in separating these functions into others, which really do measure the conflict and nor specificity parts by using a credal set to represent the information In DSt, we have two total uncertainty measures that verify a set of basic required properties: Maeda and Ichihashi's total uncertainty measure and upper entropy. More recently, however, Jousselme et al.(2006) presented a new total uncertainty measure in DST based on the pignistic distribution. The authors proved that this measure verifies the necessary properties and it resolves other shortcomings of upper entropy. We therefore have three total uncertainty measures in DST verifying all the required properties, and we will study these measures in this paper. In this paper, we justify an extension of the set of required properties for a total uncertainty measure on DST and we refer to this set as the requirements of properties. We present a comparative study of the properties verified for each total uncertainty measure, and in doing so, we will see that Jousselme et al's total uncertainty measure has some undesirable defects We will also analyse the shortcomings reported for the upper entropy by certain authors (Jousselme et al. 2006). In order to do so, we will revise the set of requirements of behaviour that a total uncertainty measure in DST must verify and study these requirements on the most significant total uncertainty measures defined in DST. By nsidering the new results on upper entropy, we will see that the upper entropy behaves Corm isms being not totally justified. e important aspect of total uncertainty measures in DST is their applicability, and this involves a not too complicated calculation In Appendix a of this paper, we present an application of these measures, having conducted an experimental study of these total uncertainty measures on a special type of belief decision trees(Abellan and Moral 2003b, 2005a), i.e. decision trees where the dsT is used to represent the information expressed by a database on a query variable. In this procedure, the way to quantify the information plays an important role in the success obtained. In our experimentation, we will use the differer total uncertainty measures analysed in this paper as tools to quantify the information In Section 2, we will introduce some necessary basic concepts and notation. Section 3 presents the extended set of basic properties verified by each total uncertainty measure. In Section 4, we analyse the shortcomings that total uncertainty measures present. Startin with this set of shortcomings, we will define a set of requirements of behaviour for this type of measure. Section 5 discusses our conclusions

appear in classical probability theory, such as monotonicity, should be taken into account when studying the axiomatic approach. Maeda and Ichihashi (1993) proposed a total uncertainty measure on DST adding up the generalised Hartley measure and upper entropy. They proved that this total uncertainty measure verifies all the necessary basic properties except for the required range. This property could, however, be discussed since there are more types of uncertainty in DST than in the probability theory. DST is considered as a particular theory of credal sets. By applying the uncertainty invariance principle, a total uncertainty measure on general credal sets will be a generalisation of a total uncertainty measure on DST. With this aim, various studies of the quantification of uncertainty on credal sets have been published (Abella´n and Moral 2003a, 2005b; Abella´n et al. 2006). In Abella´n and Moral (2003a), it is proved that the maximum of Shannon’s entropy (upper entropy) verifies on general credal sets all the basics properties that it verifies on DST. In Abella´n and Moral (2005a) and Klir and Smith (2001), the use of maximum entropy on credal sets as a good measure of total uncertainty is justified. The problem lies in separating these functions into others, which really do measure the conflict and nonspecificity parts by using a credal set to represent the information. In DST, we have two total uncertainty measures that verify a set of basic required properties: Maeda and Ichihashi’s total uncertainty measure and upper entropy. More recently, however, Jousselme et al. (2006) presented a new total uncertainty measure in DST based on the pignistic distribution. The authors proved that this measure verifies the necessary properties and it resolves other shortcomings of upper entropy. We therefore have three total uncertainty measures in DST verifying all the required properties, and we will study these measures in this paper. In this paper, we justify an extension of the set of required properties for a total uncertainty measure on DST and we refer to this set as the requirements of properties. We present a comparative study of the properties verified for each total uncertainty measure, and in doing so, we will see that Jousselme et al.’s total uncertainty measure has some undesirable defects. We will also analyse the shortcomings reported for the upper entropy by certain authors (Jousselme et al. 2006). In order to do so, we will revise the set of requirements of behaviour that a total uncertainty measure in DST must verify and study these requirements on the most significant total uncertainty measures defined in DST. By considering the new results on upper entropy, we will see that the upper entropy behaves correctly, with the criticisms being not totally justified. One important aspect of total uncertainty measures in DST is their applicability, and this involves a not too complicated calculation. In Appendix A of this paper, we present an application of these measures, having conducted an experimental study of these total uncertainty measures on a special type of belief decision trees (Abella´n and Moral 2003b, 2005a), i.e. decision trees where the DST is used to represent the information expressed by a database on a query variable. In this procedure, the way to quantify the information plays an important role in the success obtained. In our experimentation, we will use the different total uncertainty measures analysed in this paper as tools to quantify the information. In Section 2, we will introduce some necessary basic concepts and notation. Section 3 presents the extended set of basic properties verified by each total uncertainty measure. In Section 4, we analyse the shortcomings that total uncertainty measures present. Starting with this set of shortcomings, we will define a set of requirements of behaviour for this type of measure. Section 5 discusses our conclusions. 734 J. Abella´n and A. Masegosa Downloaded by [New York University] at 12:09 08 November 2011

International Journal of General Systems 2. Previous concepts 2.1 Dempster-Shafer theory of evidence Let X be a finite set considered as a set of possible situations, X= n, o(X) the power set of X and x any element in X. The Dempster-Shafer theory is based on the concept of basic probability assignment. a basic probability assignment (b.p. a ), also called a mass assignment, is a mapping m: p(X)= ch that m(0)=0 A set A where m(A)>0 is called a focal element of Let x, y be finite sets. Considering the product space of the possible situation XxY and m a b P a on X X Y, the marginal b P.a. on X, mr and similarly on Y, my is defined in the following way mx(A)=> m(R),VACX where R is the set projection of R on X. There are two functions associated with each basic probability assignment belief function, Bel, and a plausibility function, Pl: Bel(A)=RcAM(B), Pl(A) CA0Rzgn(B). These can be seen as the lower and upper probability of A, respectivel We may note that belief and plausibility functions are inter-related for all A E p(X) Pl(A)=l- Bel(A), where A denotes the complement of A. Furthermore, Bel(A)sPI(A) 2.2 Uncertainty in DST The classical measure of entropy(Shannon 1948)on probability theory is defined by the following continuous function: S(P)=-CIExP(x)log 2(p(r), where p=(p(r))ex is a probability distribution on X, p(r) is the probability of value x and log2 is normally used to quantify the value in bits. The value- S(p) quantifies the only type of uncertainty presented on probability theory and it verifies a large set of desirable properties(Shannon 1948, Klir and Wierman 1998) In DSt, Yager(1983)distinguishes between two types of uncertainty: the first associated with cases where the information focuses on sets with empty intersections, and the second is associated with cases where the information focuses on sets with greater- than-one cardinality. These are called conflict (or randomness or discord)and non- ificity, respectively The following function, introduced by Dubois and Prade(1984), has its origin in classical Hartley measure(Hartley 1928)on classical set theory and in the extended Hartley m associated with a b p a. It is expressed as follows: 1(m)= 2AcXm(A)log(lAD I(m) attains its minimum, zero, when m is a probability distribution. The maximum, log(IXD), is obtained for a b p a, m, with m(X)=l and m(A)=O, VA CX. Many measures were introduced to quantify the conflict degree that a b p a.represents (Klir and Wierman 1998). One of the most representative confict functions was introduced by Yager(1983): E(m)= (A)log Pl(a). This function, however, does not verify all the required properties on dst

2. Previous concepts 2.1 Dempster –Shafer theory of evidence Let X be a finite set considered as a set of possible situations, jXj ¼ n; ‘ðXÞ the power set of X and x any element in X. The Dempster–Shafer theory is based on the concept of basic probability assignment. A basic probability assignment (b.p.a.), also called a mass assignment, is a mapping m : ‘ðXÞ ! 0; 1 ; such that m(Y) ¼ 0 and P A#XmðAÞ ¼ 1. A set A where m(A) . 0 is called a focal element of m. Let X, Y be finite sets. Considering the product space of the possible situation X £ Y and m a b.p.a. on X £ Y, the marginal b.p.a. on X, mx and similarly on Y, mY is defined in the following way: mXðAÞ ¼ X RjA¼RX mðRÞ; ;A # X; where Rx is the set projection of R on X. There are two functions associated with each basic probability assignment: a belief function, Bel, and a plausibility function, Pl : BelðAÞ ¼ P P B#AmðBÞ; PlðAÞ ¼ A>B–YmðBÞ: These can be seen as the lower and upper probability of A, respectively. We may note that belief and plausibility functions are inter-related for all A [ ‘ðXÞ, by PlðAÞ ¼ 1 2 BelðAc Þ; where A c denotes the complement of A. Furthermore, Bel(A) # Pl(A). 2.2 Uncertainty in DST The classical measure of entropy (Shannon 1948) on probability theory is defined by the following continuous function: SðpÞ ¼ 2P x[XpðxÞ log 2ðpðxÞÞ; where p ¼ ðpðxÞÞx[X is a probability distribution on X, p(x) is the probability of value x and log2 is normally used to quantify the value in bits1 . The value2 S( p) quantifies the only type of uncertainty presented on probability theory and it verifies a large set of desirable properties (Shannon 1948, Klir and Wierman 1998). In DST, Yager (1983) distinguishes between two types of uncertainty: the first is associated with cases where the information focuses on sets with empty intersections, and the second is associated with cases where the information focuses on sets with greaterthan-one cardinality. These are called conflict (or randomness or discord) and nonspecificity, respectively. The following function, introduced by Dubois and Prade (1984), has its origin in classical Hartley measure (Hartley 1928) on classical set theory and in the extended Hartley measure on possibility theory (Higashi and Klir 1983). It represents a measure of non-specificity associated with a b.p.a. It is expressed as follows: IðmÞ ¼ P A#XmðAÞ log ðjAjÞ: I(m) attains its minimum, zero, when m is a probability distribution. The maximum, log(jXj), is obtained for a b.p.a., m, with m(X) ¼ 1 and mðAÞ ¼ 0; ;A , X. Many measures were introduced to quantify the conflict degree that a b.p.a. represents (Klir and Wierman 1998). One of the most representative conflict functions was introduced by Yager (1983): EðmÞ ¼ 2 X A#X mðAÞ log PlðAÞ: This function, however, does not verify all the required properties on DST. International Journal of General Systems 735 Downloaded by [New York University] at 12:09 08 November 2011

J. Abellan and A. Masegosa Harmanec and Klir(1996)proposed the measure S"(m)which is equal to the maximum of the entropy (upper entropy) of the probability distributions verifying Bel(A)s AP(r)s Pl(A), VA CX. This set of probability distributions is the credal set associated with a b p a. m, and will be denoted as K Maeda and Ichihashi (1993)proposed a total uncertainty measure using the measures which quantifies the conflict and non-specificity contained in a b p a. on X following way MI(m)=I(m)+S(m) where 1(m)is used as a non-specificity function and S"(m)is used as a measure of conflict. 二Ez∞N一 This measure was analysed in Abellan and Moral (1999) Harmanec and Klir(1996)proposed S as a total uncertainty measure in DST, i.e.as a neasure that quantifies conflict and non-specificity, but they do not separate this into parts that quantify these two types of uncertainty on DST. More recently, abellan et al.(2006 proposed upper entropy as an aggregate measure on more general theories than dst, coherently separating conflict and non-specificity. These parts can also be obtained in DSt in a similar way. In DSt, we can consider where S(m) represents maximum entropy and S(m) represents minimum entropy on the credal Km associated to a b p a. m, with S(m) coherently quantifying the conflict part and (S-S)(m)its non-specificity part Quite recently, Jousselme et al.(2006)presented a measure to quantify ambiguity (discord or conflict and non-specificity)in DST, i.e. a total uncertainty measure on dst. This measure is based on the pignistic distribution on DST: let m be a b p a. on a finite set X, then the pignistic probability distribution BetPm, on all the subsets A in X is defined by A∩B BetPm(A)=>m(B For a singleton set A=[x], we have BetPm([))=CreB[m(B)/Bl]. Therefore, the ambiguity measure for a b p a. m on a finite set X is defined as M(m)=->BetPm(x)log(BetPm(x) 3. Basic properties of total uncertainty measures in DST In Klir and wierman(1998), we can find five requirements for a total uncertainty measure (TU in DST, i.e. for a measure which captures both conflict and non-specificity. Using the above notation, these requirements can be expressed in the following way Pl) Probabilistic consistency all the focal elements of a b P a. m are singletons hen a total uncertainty measure must be equal to the Shannon entropy

Harmanec and Klir (1996) proposed the measure S* (m) which is equal to the maximum of the entropy (upper entropy) of the probability distributions verifying P BelðAÞ # x[ApðxÞ # PlðAÞ; ;A # X: This set of probability distributions is the credal set associated with a b.p.a. m, and will be denoted as Km. Maeda and Ichihashi (1993) proposed a total uncertainty measure using the above measures which quantifies the conflict and non-specificity contained in a b.p.a. on X in the following way: MIðmÞ ¼ IðmÞ þ S*ðmÞ; where I(m) is used as a non-specificity function and S* (m) is used as a measure of conflict. This measure was analysed in Abella´n and Moral (1999). Harmanec and Klir (1996) proposed S* as a total uncertainty measure in DST, i.e. as a measure that quantifies conflict and non-specificity, but they do not separate this into parts that quantify these two types of uncertainty on DST. More recently, Abella´n et al. (2006) proposed upper entropy as an aggregate measure on more general theories than DST, coherently separating conflict and non-specificity. These parts can also be obtained in DST in a similar way. In DST, we can consider S*ðmÞ ¼ S*ðmÞþðS* 2 S*ÞðmÞ; where S* (m) represents maximum entropy and S*ðmÞ represents minimum entropy on the credal Km associated to a b.p.a. m, with S*ðmÞ coherently quantifying the conflict part and ðS* 2 S*ÞðmÞ its non-specificity part. Quite recently, Jousselme et al. (2006) presented a measure to quantify ambiguity (discord or conflict and non-specificity) in DST, i.e. a total uncertainty measure on DST. This measure is based on the pignistic distribution on DST: let m be a b.p.a. on a finite set X, then the pignistic probability distribution BetPm, on all the subsets A in X is defined by BetPmðAÞ ¼ X B#X mðBÞ jA > Bj jBj : For a singleton set A ¼ {x}, we have BetPmð{x}Þ ¼ P x[B ½mðBÞ=jBj. Therefore, the ambiguity measure for a b.p.a. m on a finite set X is defined as AMðmÞ ¼ 2 X x[X BetPmðxÞ log ðBetPmðxÞÞ: 3. Basic properties of total uncertainty measures in DST In Klir and Wierman (1998), we can find five requirements for a total uncertainty measure (TU) in DST, i.e. for a measure which captures both conflict and non-specificity. Using the above notation, these requirements can be expressed in the following way: (P1) Probabilistic consistency: when all the focal elements of a b.p.a. m are singletons, then a total uncertainty measure must be equal to the Shannon entropy: TUðmÞ ¼ X x[X mðxÞ log mðxÞ: 736 J. Abella´n and A. Masegosa Downloaded by [New York University] at 12:09 08 November 2011