Klir G.J. Uncertainity and Information. Foundations of Generalized Information Theory

Подождите немного. Документ загружается.

All the values are listed in Table 6.3b. Our new frame of discernment X is now

{c, d}. Since X π ⭋ and Bel(X) > 0, we repeat the process. The maximum of

Bel(A)/|A| is now reached at {c}. We put p

= 0.28, change Bel({d}) to 0.13, and

X to {d}.In the last pass through the loop we get p

= 0.13.We can conclude that

6.6.2. Computing the Aggregated Uncertainty in Possibility Theory

Due to the nested structure of possibilistic bodies of evidence, the computa-

tion of functional AU can be substantially simpliﬁed. It is thus useful to refor-

mulate Algorithm 6.1 in terms of possibility proﬁles for applications in

possibility theory. The following is the reformulated algorithm.

Algorithm 6.2. Calculating AU from a given possibility proﬁle.

Input. n Œ ⺞, r =·r

, r

,...,r

Ò.

Output. AU(Pos), ·p

|i Œ ⺞

Ò such that AU(Pos) =-S

i=1

log

, with p

≥ 0 for

i Œ ⺞

, S

i=1

= 1, and S

xŒA

£ Pos(A) for all ⭋ π A Ã X.

Step 1. Let j = 1 and r

n+1

= 0.

Step 2. Find maximal i Œ {j, j + 1,...,n} such that (r

- r

i+1

)/(i + 1 - j) is

maximal.

Step 3. For k Œ {j, j + 1,...,i}, put p

= (r

- r

i+1

)/(i + 1 - j).

AU Bel p p

iabcd

()

=- ¥ - -

{}

log

. log . . log . . log .

,,,

222

2 0 295 0 295 0 28 0 28 0 13 0 13

19⬟

232 6. MEASURES OF UNCERTAINTY AND INFORMATION

A Bel(A)

{a} 0.26 0.26

{b} 0.26 0.26

{c} 0.26 0.26

{a, b} 0.59 0.295

{a, c} 0.53 0.65

{a, d} 0.27 0.135

{b, c} 0.53 0.265

{b, d} 0.27 0.135

{c, d} 0.27 0.135

{a, b, c} 0.87 0.29

{a, b, d} 0.61 0.203

{a, c, d} 0.55 0.183

{b, c, d} 0.55 0.183

{a, b, c, d} 1 0.25

(a)

Bel A

()

A Bel(A)

{c} 0.28 0.28

{d} 0.02 0.02

{c, d} 0.41 0.205

(b)

Bel A

()

Table 6.3. Calculation of AU by Algorithm 6.1 in Example 6.10: (a) First Iteration;

(b) Second Iteration

Step 4. Put j = i + 1.

Step 5. If i < n, then go to Step 2.

Step 6. Calculate AU(Pos) =-S

i=1

log

As already mentioned, it is sufﬁcient to consider only all unions of focal

elements of a given belief function, in this case a necessity measure. Since all

focal elements of a necessity measure are nested, the union of a set of focal

elements is the largest focal element (in the sense of inclusion) in the set.

Therefore, we have to examine the values of Nec(A)/|A| only for A being a

focal element.

We show by induction on the number of passes through the loop of Steps

1–5 of Algorithm 6.1 that the following properties hold in a given pass:

(a) The “current” frame of discernment X is the set {x

, x

j+1

,...,x

}, where

the value of j is taken in the corresponding pass through the loop of

Steps 2–5 of Algorithm 6.2.

(b) All focal elements are of the form A

= {x

, x

j+1

,...,x

} for some i Œ {j,

j + 1,...,n}, where j has the same meaning as in (a).

) = r

- r

i+1

, where j is again as described in (a).

This implies that Algorithm 6.2 is a correct modiﬁcation of Algorithm 6.1 for

the case of possibility theory.

In the ﬁrst pass, j = 1, X = {x

, x

,...,x

}; (b) holds due to our ordering con-

vention regarding possibility proﬁles. Since r

= 1, we have

So (c) is true.

Let us now assume that (a)–(c) were true in some ﬁxed pass. We want to

show that (a)–(c) hold in the next pass. Let l denote the value of i maximiz-

ing Nec(A

)/|A

|=Nec(A

)/(i + 1 - j). Now X becomes X - A

= {x

l+1

, x

l+2

,...,

}. Therefore (a) holds, since j = l + 1 and Nec(A

) becomes

for i Œ {j, j + 1,...,n}. This implies that (b) and (c) hold.

Nec A Nec A A Nec A

Pos

A Pos

ilil

li l

()

=»

()

=- -

()

[]

()

[]

{}

=+ =+

max max

Nec A Pos

()

{}

max

6.6. AGGREGATE UNCERTAINTY IN DEMPSTER–SHAFER THEORY 233

EXAMPLE 6.11. Consider X = {1,2,...,8} and the possibility proﬁle

The relevant values of (r

- r

i+1

)/(i + 1 - j) are listed in Table 6.4.

We can see there that in the ﬁrst pass the maximum is reached at i = 3, and

= p

–

. In the second pass, the maximum is reached at both i = 7 and

i = 8. We take the bigger one and put p

= p

= 0.1. We ﬁnish by

computing

6.7. AGGREGATE UNCERTAINTY FOR CONVEX SETS OF

PROBABILITY DISTRIBUTIONS

Once the aggregated measure of uncertainty AU has been established in DST,

it is fairly easy to generalize it for convex sets of probability distributions. Let

this generalized version of AU be denoted by S

to emphasize its deﬁnition in

terms of the maximum Shannon entropy. Clearly, S

is a functional deﬁned on

the family of convex sets of probability distribution functions. Given a convex

set D of probability distribution functions p, S

is deﬁned by the formula

(6.61)

Spxpx

()

() ()

max log .

AU Pos p p

()

=- = +

log log log

295

p = 1 09 085 05 05 035 03 01,.,. ,.,.,. ,.,..

234 6. MEASURES OF UNCERTAINTY AND INFORMATION

Table 6.4. Illustration of the Use of Algorithm 6.2 in

Example 6.11

Pass 1 2

i/j 14

1 0.1

2 0.075

3 0.16

4 0.125 0

5 0.13 0.075

6 0.116

0.06

7 0.1286 0.1

8 0.125 0.1

It is essential to show that S

satisﬁes the following requirements, which are

appropriate generalizations of their counterparts for AU:

1) Probability Consistency. When D contains only one probability dis-

tribution, S

assumes the form of the Shannon entropy.

2) Set Consistency. When D consists of the set of all possible probabil-

ity distributions on A 債 X, then

3) Range. The range of S

is [0, log

|X|] provided that uncertainty is mea-

sured in bits.

4) Subadditivity. If D is an arbitrary convex set of probability distribu-

tions on X ¥ Y and D

and D

are the associated sets of marginal

probability distributions on X and Y, respectively, then

5) Additivity. If D is the set of joint probability distributions on X ¥ Y

that is associated with independent marginal sets of probability distri-

butions, D

and D

, which means that D is the convex hull of the set

It is obvious that the functional S

deﬁned by Eq. (6.61) satisﬁes require-

ments (S

1)–(S

3). The remaining two properties, subadditivity and additivity,

are addressed by the following two theorems.

Theorem 6.10. Functional S

deﬁned by Eq. (6.61) satisﬁes the requirement

4), that is, it is subadditive.

Proof. Given a convex set of joint probability distributions on X ¥ Y, let p

denote the joint probability distribution in D for which the maximum in Eq.

(6.61) is obtained and let p

and p

denote the marginal probability distribu-

tions of p

. Then, by Gibbs’ inequality (Eq. 3.28),

䊏

Spxypxy

px y p x p y

px y p x px y p y

xXyY

xXyYyY

, log

˙˙

, log

˙˙

, log

()

() ()

£-

() ()

◊

()

[]

() ()

ŒŒ

ŒŒŒŒ

ÂÂ

ÂÂÂÂ

ppx px py py

() ()

()

ŒŒ

ÂÂ

log

˙˙

log

˙˙

DD D D

DD D

XY X Y X XY Y

px y p x p y x X y Y p P

SS S

ƒ=

()

◊

()

ŒŒ Œ Œ

{}

()

,,,,,

.then

SS S

DD D

()

SAD

()

= log .

6.7. AGGREGATE UNCERTAINTY FOR CONVEX SETS OF PROBABILITY DISTRIBUTIONS 235

Theorem 6.11. Functional S

deﬁned by Eq. (6.61) satisﬁes the requirement

5), that is, it is additive.

Proof. From Theorem 6.10

It is thus sufﬁcient to show that

under the assumption of independence. Let p

and p

denote the marginal

probability distributions on X and Y for which the maxima in Eq. (6.61) are

obtained. Then

䊏

EXAMPLE 6.12. Consider the following convex sets of marginal probability

distributions on X = {x

, x

} and Y = {y

, y

The maximum entropy within D

is obtained for l

= 1 (i.e., for p

) = 0.4

and p

) = 0.6). The maximum entropy within D

is obtained for l

= 1 (i.e.,

for p

) = 0.2 and p

) = 0.8). Hence,

Assuming the independence of the marginal probabilities, the set D of the

associated joint probabilities on Z = X ¥ Y is the convex hull of the set

where z

i,j

=·x

, y

Ò for all i, j = 1, 2. The maximum entropy within D

ƒ D

obtained for l

= l

= 1 and, hence,

XY X Y

ƒ=

()

{

()

02 02 01 01

02 02 09 01

08 02 01 01

08 02 09 0

.. ..,

.. ..

l 1101lll

YXY

()

[]

}

,,,

()

04 06 0971

02 08 0722

1 693

., . . ,

XX XX XX

YY XY YY

px px

py py

()

=- Œ

[]

{}

()

=- Œ

[]

{}

02 02 08 02 0 1

01 01 09 01 0 1

.., .. ,,

.., .. ,.

lll

S S px px py py

px py px py

XY X X

XY Xy

xXyY

()

() ()

()

◊

() ()

◊

()

[]

()

ŒŒ

ÂÂ

log

˙˙

log

˙˙

log

˙˙

SS S

DD D

()

≥

()

SS S

DD D

()

236 6. MEASURES OF UNCERTAINTY AND INFORMATION

Functional S

is deﬁned in this section for convex sets of probability distri-

butions. However, it can be as well deﬁned for the lower and upper probabil-

ity functions or the Möbius representations obtained uniquely from convex

sets of probability distributions. We can thus write not only S

(D), but also

(),S

), or S

(m).

Algorithm 6.1 (introduced in Section 6.6.1) is formulated and proved

correct for belief functions. It is not necessarily applicable to lower probabil-

ities that are more general or incomparable with belief functions. A lower

probability for which the algorithm does not work is examined in the follow-

ing example.

EXAMPLE 6.13. Consider the following convex set D of probability distri-

butions on Z = {z

, z

} deﬁned in Example 6.7. The lower probability

function,

, associated with this set, which is derived by Eq. (4.11), is shown

in Table 6.2. Recall that

is not 2-monotone in this example.

Applying Algorithm 6.1 results in probability distribution

for which S(0.4, 0.4, 0.1, 0.1) = 1.722. However, this probability distribution is

not a member of the given set of probability distributions. The plot of the

Shannon entropy for l Œ [0, 1] is shown in Figure 6.8. Its maximum is = 1.69288.

It is obtained for p =·0.48, 0.32, 0.12, 0.08Ò. Algorithm 6.1 thus does not

produce the correct value of S

( ) in this example.

pz pz pz pz

11 12 21 22

04 01

()

=., .,

SS S

DD D

()

= 1 693..

6.7. AGGREGATE UNCERTAINTY FOR CONVEX SETS OF PROBABILITY DISTRIBUTIONS 237

0.2 0.4 0.6 0.8 1

1.4

1.5

1.6

1.7

Figure 6.8. Values of the Shannon entropy for l Œ [0, 1] in Example 6.13.

6.8. DISAGGREGATED TOTAL UNCERTAINTY

Functional S

deﬁned by Eq. (6.60) is certainly well justiﬁed on mathematical

grounds as an aggregate measure of uncertainty in the theory based on arbi-

trary convex sets of probability distributions and, consequently, to the various

special theories of uncertainty as well. However, it has a severe practical short-

coming: it is highly insensitive to changes in evidence. To illustrate this unde-

sirable feature of S

, let us examine the following example.

EXAMPLE 6.14. Consider the following class of simple bodies of evidence

in DST: X = {x

, x

}, m({x

}) = m

, m({x

}) = m

, m(X) = 1 - m

- m

, where m

Œ [0, 1] and m

+ m

£ 1 (Figure 6.9a). Clearly, Bel({x

}) = m

, Bel({x

}) =

, and Bel(X) = 1. Then, S

(Bel) = 1 (or AU(Bel) = 1 when using the special

notation in DST) for all m

Œ [0, 0.5] and m

Œ [0, 0.5]. Moreover, when m

0.5, S

(Bel) = S(m

,1 - m

), where S denotes the Shannon entropy. Hence,

(Bel) is independent of m

. Similarly, when m

> 0.5, S

(Bel) = S(m

,1 - m

)

and, hence, S

(Bel) is independent of m

. These values of S

(Bel) are shown in

Figure 6.9b. The functional S

in this example can also be expressed by the

formula

(6.62)

for all m

, m

Œ [0, 1] such that m

+ m

£ 1, where S denotes the Shannon

entropy.

This example surely illustrates that the insensitivity of the functional S

changes in evidence is very severe. This feature makes the functional ill-suited

for measuring uncertainty on conceptual and pragmatic grounds. However,

S Bel S m m m m

()

{}

{}()

max , , . , max , , .

12 12

05 1 05

238 6. MEASURES OF UNCERTAINTY AND INFORMATION

)1,()(

mmSmS -=

)1,()(

mmSmS -=

0.5

mm --

(a)

(b)

1)(

=mS

Figure 6.9. Illustration of the severe insensitivity of the aggregate uncertainty measure

(Example 6.14).

recognizing that S

is an aggregate of the two types of uncertainty—nonspeci-

ﬁcity and conﬂict—it must be that

(6.63)

where is a lower probability function, which can be derived from any of the

other representations of the same uncertainty (the associated convex set of

probability distributions, Möbius representation, or upper probability func-

tion) or may be converted to any of these representations as needed. In Eq.

(6.63) GH is the well-justiﬁed functional for measuring nonspeciﬁcity (deﬁned

at the most general level by Eq. (6.38) and referred to as the generalized

Hartley measure) and GS is an unknown functional for measuring conﬂict

(referred to as the generalized Shannon entropy).

Since functionals S

and GH in Eq. (6.63) are well justiﬁed and GS is an

unknown functional, it is suggestive to deﬁne GS from the equation as

(6.64)

Here, GS is deﬁned indirectly, in terms of two well-justiﬁed functionals, thus

overcoming the unsuccessful attempts to deﬁne it directly (as discussed in

Section 6.5).

Functional S

, which is well justiﬁed but practically useless due to its insen-

sitivity, can now be disaggregated into two components, GH and GS, which

measure two types of uncertainty that coexist in all uncertainty theories except

the classical ones. A disaggregated total uncertainty, TU, is thus deﬁned as the

pair

(6.65)

where GH and GS are deﬁned by Eqs. (6.38) and (6.64), respectively. Since

the sum of the two components of TU is S

, TU is as well justiﬁed as S

. One

advantage of the disaggregated total uncertainty, TU, in comparison with its

aggregated counterpart S

, is that it expresses amounts of both types of uncer-

tainty (nonspeciﬁcity and conﬂict) explicitly, and consequently, it is highly sen-

sitive to changes in evidence.

Another advantage of TU is that its components, GH and GS, need not

satisfy all the mathematical requirements for measures of uncertainty. It

only matters that their aggregate measure, S

, satisﬁes them. The lack of

subadditivity of GH for arbitrary convex sets of probability distributions,

established in Example 6.7, is thus of no consequence when GH is employed

as one component in TU.

EXAMPLE 6.15. To appreciate the difference between S

and TU, let us

consider the following three bodies of evidence on X and let |X|=n for

convenience:

TU GH GS= ,,

GS S GHmm m

()

SGHGSmmm

()

6.8. DISAGGREGATED TOTAL UNCERTAINTY 239

(a) In the case of total ignorance (when m(X) = 1), S

(m) = log

n and TU(m)

=·log

n,0Ò.

(b) When evidence is expressed by the uniform probability distribution

on X (i.e., m({x}) = 1/n for all x Œ X), then again S

(m) = log

n, but

TU(m) =·0, log

nÒ.

and m(X) = 1 - na, then again S

(m) = log

n, while TU(m) =·(1 -

na)log

n, nalog

nÒ.

EXAMPLE 6.16. To illustrate the disaggregated total uncertainty TU =·GH,

GSÒ, let us consider again the class of simple bodies of evidence introduced in

Example 6.14. Plots of the dependences of S

, GH, and GS on m

and m

are

shown in the ﬁrst column of Figure 6.10. We can see that both components of

TU (GH and GS) are sensitive to changes of evidence. Plots of S

, GH, and GS

for the extreme cases when either m

= 0 or m

= 0 (nested or possibilistic

bodies of evidence) are shown in the second column of Figure 6.10. It is easy

to determine that the maximum of GS is 0.585, and it is attained in these cases

for m

= 2/3 and m

= 0 (or m

= 0 and m

= 2/3).

The plots in Figure 6.10 are based on the lower probability function, when

+ m

£ 1. Similar plots can be made for the upper probability function, when

+ m

≥ 1. In Figure 6.11, values of S

, m

), GH(m

, m

), GS(m

, m

) are

shown for all values of m

, m

Œ [0, 1]. Clearly,

where S denotes the Shannon entropy, and

To fully justify the disaggregated total uncertainty TU deﬁned by Eq.(6.65),

it remains to prove that its second component, the generalized Shannon

entropy GS deﬁned by Eq. (6.64) is always nonnegative. That is, we need to

prove that the inequality

holds for any lower probability function (or any of its equivalent represen-

tations). This proof is presented for belief functions in Appendix D. A proof

for lower probability functions outside DST is still needed.

SGHmm

()

≥ 0

GH m m

mm mm

GS m m S m m GH m m

12 12

12 12 12

,, ,,

()

-- +£

+- +≥

{

()

when

Sm m

Smm

mm m m

Smm

mm mm

12 1 2

12 12

105 1

11 05

11105 1

max , , . ,

max , , .

max , , . ,

()

{}(

{})

+£

{}(

---

{})

+≥

when

240 6. MEASURES OF UNCERTAINTY AND INFORMATION

6.9. GENERALIZED SHANNON ENTROPY

The generalized Shannon entropy deﬁned by Eq. (6.64) emerged fairly

recently and has not been sufﬁciently investigated as yet. Nevertheless, some

of its properties in Dempster–Shafer theory are derived in this section on the

basis of Algorithm 6.1.

6.9. GENERALIZED SHANNON ENTROPY 241

Figure 6.10. Uncertainties for the two-element bodies of evidence deﬁned in Example 6.14.

First column: S

, GH, and GS for all m

and m

such that m

+ m

£ 1; second column: S

, GH,

and GS for either m

= 0 or m

= 0.