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

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

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

(a)

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.25

0.5

0.75

0.2

0.4

0.6

0.8

(b)

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.25

0.5

0.75

0.2

0.4

0.6

0.8

(c)

Figure 6.11. For all m

, m

Œ [0, 1]: (a) S

, m

); (b) GH(m

, m

); (c) GS(m

, m

To facilitate the following derivations, let

denote the family of all focal sets of a given body of evidence in

Dempster–Shafer theory. Furthermore, let

denote the partition of 傼

kŒ⺞

that is produced by Algorithm 6.1. Clearly,

r £ q and

For convenience, assume that block B

is produced by the kth iteration of the

algorithm, and let Pro(B

) denote the probability of B

. Clearly,

(6.66)

According to Algorithm 6.1,

where Bel denote the belief measure associated with the given body of evi-

dence. This equation can be rewritten as

Due to Eq. (6.66), the ﬁrst term on the right-hand side of this equation is the

Shannon entropy of E and the second term is the generalized Hartley measure

of E. We can thus rewrite this equation as

Using now Eq. (6.64), we obtain

(6.67)

This equation indicates that the generalized Shannon entropy is expressed by

the Shannon entropy of E and the difference between the nonspeciﬁcity of E

and the nonspeciﬁcity of the given body of evidence ·F, mÒ.

GS Bel S Pro B k GH Pro B k GH m A i

kr kr iq

()

⺞⺞⺞.

S Bel S Pro B k GH Pro B k

kr kr

()

⺞⺞.

S Bel Pro B Pro B Pro B B

()

() ()

()

ŒŒ

ÂÂ

log log .

⺞⺞

S Bel Pro B Pro B B

kkk

()

() ()

[]

log ,

⺞

Pro B

()

⺞

EP=Œ

()

{}

BB X k

kk r

, ⺞

FP=Œ

()

{}

AA X i

ii q

, ⺞

6.9. GENERALIZED SHANNON ENTROPY 243

In the rest of this section, some properties of the generalized Shannon

entropy are derived for two special types of bodies of evidence, those in which

focal elements are either disjoint or nested.

Theorem 6.12. Consider a given body of evidence ·F, mÒ in which F is a family

of pairwise sets. Then,

where Bel denotes the belief measure based on m.

Proof. For convenience, let m

= m(A

) and a

=|A

|. Assume (without any loss

of generality) that

Then, m

≥ m

. Now comparing m

with (m

+ m

)/(a

+ a

), we

obtain

It is obvious that the same result is obtained when m

is compared with

for any I 債 {2, 3, . . . , q}. Hence, Algorithm 6.1 assigns probabilities m

all elements in A

in the ﬁrst iteration (observe that Bel(A

) = m(A

) for all

i Œ⺞

when focal elements are disjoint). By repeating the same argument for

, we can readily show that Algorithm 6.1 assigns probabilities m

to all

elements of A

in the second iteration, and so forth. Hence,

Now,

S Bel a

mm ma

m m GH Bel

()

=- +

()

ÂÂ

log

log log

log .

mmaa

ŒŒ

ÂÂ

ma ma

aa a

12 21

11 2

()

≥ .

≥≥≥

...

GS Bel m A m A

()

() ()

log ,

244 6. MEASURES OF UNCERTAINTY AND INFORMATION

䊏

Now let us consider some properties of the generalized Shannon entropy

for nested bodies of evidence. Let X = {x

|i Œ⺞

} and assume that the elements

of X are ordered in such a way that the family

contains all focal sets.According to this special notation (introduced in Section

5.2.1), F 債 A. For convenience, let m

= m(A

) for all i Œ ⺞

Given a particular nested body of evidence ·F, mÒ,

While GH(m) in this equation is expressed by the simple formula

(6.68)

the expression of S

(m) is not obvious at all. To investigate some properties of

GS for nested bodies of evidence, let the following three cases be distin-

guished:

(a) m

≥ m

i+1

for all i Œ⺞

n-1

;

(b) m

£ m

i+1

for all i Œ ⺞

n-1

;

Following the algorithm for computing S

, we obtain the formula

(6.69)

for any function m that conforms to Case (a). By applying the method of

Lagrange multipliers (Appendix E), we can readily ﬁnd out that the maximum,

GS*

(n), of this functional for each n Œ⺞ is obtained for

where the value of a is determined by solving the equation

211

()

a ln

mi i

()

12a ln

,⺞

GS m m m i

aii

()

log

GH m m i

()

log ,

GS m S m GH m

()

A ==

{}

Axx xi

iin12

, ,..., ⺞

GS Bel S Bel GH Bel

()

log .

6.9. GENERALIZED SHANNON ENTROPY 245

Let . Then,

and, hence,

Substituting this expression for m

in Eq. (6.69), we obtain

(6.70)

The maximum, GS*

(n), of this functional for some n Œ ⺞, subject to the

inequalities that are assumed in Case (b), is obtained for m

= 1/n for all

i Œ⺞

. Hence,

(6.71)

For large n, n! in this equation can be approximated by the Stirling formula

Then,

and

Hence, GS*

(n) = log

e ª 1.442695.That is, GS*

is bounded, contrary to GS*

(n).

Moreover GS*

(n) < GS*

(n) for all n Œ ⺞. Plots of GS*

(n) and GS*

(n) for

n Œ ⺞

1000

are shown in Figure 6.12.

Case (c) is more complicated for a general analytic treatment since it covers

a greater variety of bodies of evidence with respect to the computation of GS.

This follows from the algorithm for computing S

. For each given body of evi-

dence, the algorithm partitions the universal set in some way, and distributes

the value of the lower probability in each block of the partition uniformly. For

lim

lim .

Æ• Æ•

()

112

nne

()

112

nne

!.ª

()

GS n

()

= log

GS n s

()

= log .

()

1log

a =-

()

log ln

112s

()

246 6. MEASURES OF UNCERTAINTY AND INFORMATION

nested bodies of evidence, the partitions preserve the induced order of ele-

ments of X. There are 2

n-1

-order preserving partitions. The most reﬁned par-

tition and the least reﬁned one are represented by Cases (a) and (b),

respectively. All the remaining 2

n-1

- 2 partitions are represented by Case (c).

A conjecture, based on a complete analysis for n = 3 and extensive simulation

experiments for n > 3, is that the maxima of GS for all these partitions are for

all n Œ ⺞ smaller than the maximum GS*

(n) for Case (a). According to this

plausible conjecture, whose proof is an open problem, the difference between

the maximum nonspeciﬁcity, GH*(n), and the maximum conﬂict, GS*

(n),

grows rapidly with n.This is illustrated by the plots of GH*(n) and GS*(n) for

n Œ⺞

1000

in Figure 6.13.

6.9. GENERALIZED SHANNON ENTROPY 247

200 400 600 800 1000

1.25

1.5

1.75

2.25

2.5

2.75

Figure 6.12. Plots of GS

*(n) and GS

*(n).

200 400 600 800 1000

Figure 6.13. Illustration of the growing difference [GH*(n) - GS*(n)] with increasing n.

In addition to deﬁning the general Shannon entropy by Eq. (6.64), it seems

also reasonable to express it by the interval [S(D), S

(D)], where S(D) and

(D) are, respectively, the minimum and maximum values of the Shannon

entropy within a given convex set D of probability distributions. Then, an

alternative total uncertainty, TU¢, is deﬁned as the pair

(6.72)

While this measure is quite expressive, as it captures all possible values of the

Shannon entropy within each given set D, its properties and utility have yet

to be investigated (see Note 6.10).

6.10. ALTERNATIVE VIEW OF DISAGGREGATED

TOTAL UNCERTAINTY

The disaggregated measure of total uncertainty introduced in Section 6.8 is

based on accepting the generalized Hartley functional as a measure of non-

speciﬁcity and using its numerical complement with respect to the aggregated

measure S

as a generalization of the Shannon entropy. This approach to dis-

aggregating S

is reasonable since the generalized Hartley functional is well

justiﬁed (on both intuitive and mathematical grounds) as a measure of

nonspeciﬁcity in at least all the uncertainty theories that are subsumed under

DST. No functional with a similar justiﬁcation has been found to generalize

the Shannon entropy, as is discussed in Section 6.5.

Although the full justiﬁcation of the generalized Hartley functional does

not extend to all theories of uncertainty, due to the lack of subadditivity (as

shown in Example 6.7), this does not hinder its role in the disaggregated

measure. The two components in the disaggregated measure are deﬁned in

such a way that whenever one of them violates any of the required properties,

the other one compensates for these violations.

Recall that measure, S

, which is well justiﬁed in all uncertainty theories,

aggregates two types of uncertainty: nonspeciﬁcity and conﬂict. In classical

uncertainty theories, these types of uncertainty are measured by the Hartley

functional and the Shannon functional, respectively. In the various general-

izations of the classical theories, appropriate counterparts of these classical

measures of nonspeciﬁcity and conﬂict are needed. This suggests looking for

justiﬁable generalizations of the Hartley and Shannon functionals in the

various nonclassical uncertainty theories. However, all attempts to generalize

these functionals independently of each other have failed. This eventually led

to the idea of disaggregating the aggregated measure S

.According to this idea,

the generalization of the classical functionals should be constrained by the

requirement that their sum always be equal to S

. One way of satisfying this

requirement is to choose one of the components of the disaggregated measure

TU GH S S¢=

[]

,, .

248 6. MEASURES OF UNCERTAINTY AND INFORMATION

and deﬁned the other one as its numerical complement with respect to S

Clearly, there are two ways to pursue this approach to the disaggregation of

: the chosen component is either a measure of nonspeciﬁcity or a measure of

conﬂict.

The disaggregated total uncertainty introduced in Section 6.8 is based on

choosing the generalized Hartley functional as a measure of nonspeciﬁcity.The

aim of this section is to explore the other possibility: to choose a particular

measure of conﬂict, and to deﬁne the measure of nonspeciﬁcity as its numer-

ical complement with respect to S

. Since, in this context, the chosen measure

of conﬂict does not have to satisfy all the required properties, all the proposed

generalizations of the Shannon entropy, which are discussed in Section 6.5, are

in principle applicable. However, a measure that seems to capture best the

generalized Shannon entropy is the functional S deﬁned for any arbitrary

closed and convex set D of probability distributions by the formula

(6.73)

This measure has been neglected due to its massive violations of the

subadditivity requirement. However, this deﬁciency does not matter when S

is used as one component of the disaggregated measure of total uncertainty.

Functional S is intuitively a good choice for a generalized Shannon entropy,

since it measures (by the Shannon entropy itself) the essential (irreducible)

amount of conﬂict embedded in any given credal set D. When it is accepted

as a measure of conﬂict, then the measure of nonspeciﬁcity, N, is deﬁned for

any given credal set D by the formula

(6.74)

This means that, according to this view of disaggregating S

, the measure of

nonspeciﬁcity is not a generalized Hartley measure anymore.

Functionals S and N have been proved to possess the following properties

(Note 6.10):

1. The range of both S and N is [0, log

|X|] provided that the units of mea-

surement are bits. The lower and upper bounds are reached under the

following conditions:

•

S(D) = 0 iff for some x Œ X.

•

S(D) = log

|X| iff D contains only the uniform probability distribution

on X.

•

N(D) = 0 iff |D|=1.

•

N(D) = log

|X| iff for some x Œ X and D contains the

uniform probability distribution on X.

sup

(){}

sup

(){}

NSSDDD

()

Spxpx

()

() ()

{}

min log .

6.10. ALTERNATIVE VIEW OF DISAGGREGATED TOTAL UNCERTAINTY 249

2. S is monotone decreasing and N is monotone increasing with respect to

subsethood relation between credal sets if D 債 D¢, then S(D) ≥ S(D¢)

and N(D) £ N(D¢).

3. Both S

and N are additive.

4. Both S and N are continuous.

Taking into account all these properties, it makes sense to deﬁne for any

given credal set D an alternative measure of disaggregated total uncertainty,

TU, by the formula

(6.75)

In Figure 6.14, plots of the functionals involved in

TU (i.e., S

, N = S

- S, and

S) are shown for the class of simple bodies of evidence introduced in Example

6.14.These are counterparts of the plots shown in Figure 6.11 of the functionals

involved in TU. In this case,

where a = max(m

, m

, 0.5) and b = max(1 - m

,1 - m

, 0.5),

where c = min(m

, m

) and d = min(1 - m

,1 - m

), and N(m) = S

(m) - S(m);

S denotes the Shannon entropy.

The practical utility of the alternative measure

TU of disaggregated total

uncertainty is contingent on an efﬁcient algorithm for computing S. While it

has been established that, due to the concavity of the Shannon entropy, S(D)

is always obtained at some extreme point of D, the computational complex-

ity of searching through the extreme points is still very high. Since the upper

count of the number of extreme point is |X|!, some ways of avoiding an exhaus-

tive search is essential. Some results in this direction have been obtained

already (Note 6.10).

EXAMPLE 6.17. Consider the credal set D deﬁned in Example 6.7. Clearly,

S(D) is obtained for the extreme point p

, as can be seen from the plot of

S(lp

+ (1 - l)p

) in Figure 6.8, where p

=·0.4, 0.4, 0.2, 0Ò and p

=·0.6, 0.2,

0, 0.2Ò. We have S(D) = S(p

) = 1.371. Since S

(D) = 1.693 in this case (see

Example 6.13), we have,

TU = 0 21 1 371.,. .

Sc c m m

Sd d m m

()

+£

()

+≥

{

when

Sa a m m

Sb b m m

()

+£

()

+≥

{

when

TU S S SDDDD

()

() ()

250 6. MEASURES OF UNCERTAINTY AND INFORMATION

6.10. ALTERNATIVE VIEW OF DISAGGREGATED TOTAL UNCERTAINTY 251

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

0.2

0.4

0.6

0.8

Figure 6.14. Counterparts of plots in Figure 6.11 for

TU deﬁned by Eq. (6.75).