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

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

If the functional GH satisﬁes the axiomatic requirements of subadditivity,

additivity, symmetry, branching, and normalization (i.e., the axiomatic require-

ments (GH1)–(GH6)), then for any m Œ M,

where F denotes the set of focal elements associated with m.

Proof. To facilitate the proof, let us introduce a convenient notation. Let (

C, . . .) denote a basic probability assignment function such that m(A) =

a, m(B) = b, m(C) = g ...,where A, B, C,...are the focal elements of m.

When we are concerned only with the cardinalities of the focal elements, the

basic probability assignment function can be written in the form (

. . .) where a, b, c,...are positive integers that stand for the cardinalities of

the focal elements; occasionally, when a = 1, we write (a) instead of (

a). For

the sake of simplicity, let us refer to the value m(A) of a basic assignment m

as the weight of A.

(i) First, we prove that GH(

a) = log

a. For convenience, let W(a) = GH(

(that is, W is a nonnegative real-valued function on ⺞). From additivity (GH2),

we have

(B.1)

When a = b = 1, W(1) = W(1) + W(l) and, consequently, W(1) = 0. To show

that W(a) £ W(a = 1), let us take set A of a(a + 1) elements, which is a

subset of a Cartesian product X ¥ Y. By symmetry (GH3), GH(A) does not

depend on how the elements of A are arranged. Let us consider two possible

arrangements. In the ﬁrst arrangement, A is viewed as a rectangle a ¥ (a + 1);

here ¥ denotes a Cartesian product of sets with cardinalities a and a + 1.

Then

(B.2)

by additivity. In the second arrangement, we view A as a subset of a square

(a + 1) ¥ (a + 1) such that at least one diagonal of the square is fully covered.

In this case, the projections onto both X and Y have the same cardinality

a + 1. Hence, by subadditivity (GH1), we have

(B.3)

It follows immediately from Eqs. (B.1) and (B.2) that

Wa Wa

()

£+

()

GH A W a W a

()

£+

()

11.

GH A W a W a

()

Wab Wa Wb

()

GH m m A A

()

log ,

432 APPENDIX B. UNIQUENESS OF THE GENERALIZED HARTLEY MEASURE IN THE DST

APPENDIX B. UNIQUENESS OF THE GENERALIZED HARTLEY MEASURE IN THE DST 433

Function W is thus monotonic nondecreasing. Since it is also additive in the

sense of Eq. (B.1) and normalized by Axiom (GH6), it is equivalent to the

Hartley information H. Hence, by Theorem 2.1

(B.4)

(ii) We prove that GH(

1, . . .) = 0. First, we show that the equality

holds only for two focal elements, that is, we show that GH(

1) = 0. Con-

sider a set A of a

elements for some sufﬁciently large, temporarily ﬁxed a. Let

B = A ¥ (

1). Then GH(A) = 2log

a and

(B.5)

by Eq. (B.4) and additivity. Set B can be considered as consisting of two

squares a ¥ a with weights a and b. Let us now place both of these squares

into a larger square (a + 1) ¥ (a + 1) in such a way that at least one of the diag-

onals of the larger square is totally covered by elements of the smaller squares

and, at the same time, the a ¥ a squares do not completely overlap. Clearly,

both projections of this arrangement of set B have the same cardinality a + 1.

Hence,

by subadditivity. Substituting for GH(B) from Eq. (B.5) and applying Eq.

(B.4), we obtain

or, alternatively,

This inequality must be satisﬁed for all a Œ ⺞. When a goes to inﬁnity, the left-

hand side of the inequality remains constant, whereas its right-hand side

converges to zero. Hence,

By repeating the same argument for (

1, . . .) with n focal elements, we

readily obtain

and, again, by allowing a to go to inﬁnity, we obtain

GH n a a

111 2 1

, , , . . . log log ,

()

£+

()

[][]

11 0,.

()

GH a a

11 2 1

, log log .

()

£+

()

[]

GH a a

11 2 2 1

, log log

()

+£ +

()

GH B GH a GH a

()

£+

()

GH B a GH

()

211

log ,

Wa GH a a

()

log .

(B.6)

Applying this result and the additivity of GH, we also have for an arbitrary

basic assignment m the following:

(B.7)

This means that we can replicate all focal elements of m the same number of

times, splitting their weights in a ﬁxed proportion a, b, g,...,and the value of

GH does not change.

(iii) Next, we prove that GH(m

) = GH(m

), where m

= (

b+g

b) and m

= (

b). Since the actual weights are not essential in this proof, we omit

them for the sake of simplicity; if desirable, they can be easily reconstructed.

The proof is accomplished by showing that GH(m

) £ GH(m

) and, at the same

time, GH(m

) £ GH(m

). To demonstrate the ﬁrst inequality, let us view the

focal elements m

and m

as collections of intervals of lengths a, b, and a, b,

b, respectively. Furthermore, let us place both intervals of m

side by side, the

ﬁrst and second interval of m

side by side, and the third interval of m

above

the second interval of m

. According to this arrangement, the two projections

of m

consist of m

and a pair of singletons with appropriate weights, say (

1). It then follows from the subadditivity that

The last term in this inequality is 0 by Eq. (B.6) and, consequently, GH(m

) £

GH(m

To prove the opposite inequality, let m

= (

1) so that m

·m

assigns the

same weights to the b’s as does m

.We select a sufﬁciently large integer n, tem-

porarily ﬁxed. Let s and s¢ denote squares n ¥ n and (n + 1) ¥ (n + 1), respec-

tively. We can view m

·m

·s as a collection of four parallelepipeds, two with

edges a, n, n, and the other two with edges b, n, n. Similarly, m

·s¢ can be

viewed as a collection of three parallelepipeds, one with edges a, n + 1, n + 1,

and two with edges b, n + 1, n + 1. We now place two blocks with edges a, n,

n of m

·m

·s inside one block with edges a, n + 1, n + I of m

so that they cover

the main diagonal. Furthermore, we place two blocks with edges b, n, n of

·m

·s inside the separate blocks with edges b, n + 1, n + 2 of m

·s¢ so

that they again cover the diagonals. Using additivity and Eq. (B.4), the

construction results in the equation

Using subadditivity and the projections of the construction, we obtain

GH m m s GH m GH n

GH m n

13 1 2

11 2

◊◊

()

, log

log .

GH m GH m GH

()

GH m GH m GH GH m◊

()()

()

111 111, , ,... , , ,... .

111 0, , ,... .

()

434 APPENDIX B. UNIQUENESS OF THE GENERALIZED HARTLEY MEASURE IN THE DST

Hence,

and

For n going to inﬁnity, the right-hand side of this inequality converges to 0

and, consequently,

The proof can easily be extended to the case of a general basic probability

assignment function in which any given cardinality may repeat more than

twice and the number of different cardinalities is arbitrary.

(iv) Repeatedly applying the branching property, we obtain

According to property (iii), we can combine the singletons so that the proof

of the theorem reduces to the determination of GH(

1-a

1) for arbitrary a

and a. Moreover,

and, by the branching axiom,

Hence,

Similarly,

GH a GH a GH a

113231434

3131

()

, , ....

GH a GH a

11212

()

GH a a GH a

12 12 12 12

21,,.

()

GH a GH a a

11212

()

GH a b c GH a GH b

, , ,... , , ,... , , ,... ....

()

11 11

GH m GH m

()

≥

()

GH m GH m

()

≥

GH m GH m n n

2122

()

≥-+

()

[]

log log .

GH m n GH m n

12 22

()

+£

()

+log log

GH m m s GH m GH n GH n

13 2

11◊◊

()

APPENDIX B. UNIQUENESS OF THE GENERALIZED HARTLEY MEASURE IN THE DST 435

Using Eq. (B.4) we obtain for each t = 1/n the equation

This formula can easily be shown to hold for any rational t. Since an arbitrary

real number can be approximated by a monotonic sequence of rational

numbers, property (iii) implies that the formula holds also for any t Œ [0, 1].

This concludes the proof. 䊏

GH a t a

, log .

()

436 APPENDIX B. UNIQUENESS OF THE GENERALIZED HARTLEY MEASURE IN THE DST

APPENDIX C

CORRECTNESS OF

ALGORITHM 6.1

437

The correctness of the algorithm is stated in Theorem C.1. The proof employs

the following two lemmas.

Lemma C.1. Let x > 0 and c - x > 0. Denote

Then L(x) is strictly increasing in x when (c - x) > x.

Proof. L¢(x) = log

(c - x) - log

x so that L¢(x) > 0 whenever (c - x) > x. 䊏

Lemma C.2. [Dempster, 1967b] Let X be a frame of discernment, Bel a gen-

eralized belief function* on X, and m the corresponding generalized basic

probability assignment; then a tuple ·p

|x Œ XÒ satisﬁes the constraints

and

Bel A p A X

()

£"Õ

01££ "Œ

()

pxX

p Bel X

Lx cx cx x x

()

=- -

()

[]

log log .

Uncertainty and Information: Foundations of Generalized Information Theory, by George J. Klir

* A generalized belief function, Bel, is a function that satisﬁes all requirements of a belief measure

except the requirement that Bel(X) = 1. Similarly, values of a generalized basic probability assign-

ment are not required to add to one. Bel in Algorithm 6.1 is clearly a generalized belief function

after the ﬁrst iteration of the algorithm.

if and only if there exist nonnegative real numbers a

for all nonempty sets

A 債 X and for all x Œ A such that

Using the results of Lemma C.1 and Lemma C.2, we can now address the

principal issue of this appendix, the correctness of Algorithm 6.1. This issue is

the subject of the following theorem.

Theorem C.1. Algorithm 6.1 stops after a ﬁnite number of steps and the

output is the correct value of function AU(Bel) since ·p

|x ŒXÒ maximizes the

Shannon entropy within the constraints induced by Bel.

Proof. The frame of discernment X is a ﬁnite set and the set A chosen in Step

1 of the algorithm is nonempty (note also that the set A is determined

uniquely). Therefore, the “new” X has a smaller number of elements than the

“old” X and so the algorithm terminates after ﬁnitely many passes through

the loop of Steps 1–5.

To prove the correctness of the algorithm, we proceed in two stages. In the

ﬁrst stage, we show that any distribution ·p

|x Œ XÒ that maximizes the

Shannon entropy within the constraints induced by Bel has to satisfy the equal-

ity p

= Bel(A)/|A| for all x Œ A. In the second stage we show that, for any

partial distribution ·p

|x Œ X - AÒ that satisﬁes the constraints induced by the

“new” generalized belief function deﬁned in Step 3 of the algorithm, the com-

plete distribution ·q

|x Œ XÒ, deﬁned by

(C.1)

satisﬁes the constraints induced by the original (generalized) belief function,

and vice versa.That is, for any distribution ·q

|x Œ XÒ satisfying the constraints

induced by Bel and such that q

= Bel(A)/|A| for all x Œ A, it holds that

·q

|x Œ X - AÒ satisﬁes the constraints induced by the “new” generalized belief

function deﬁned in Step 3 of the algorithm. The theorem then follows by

induction.

First, assume that ·p

|x Œ XÒ is such that

and

Bel B p

()

AU Bel p p

p Bel X

()

log ,

q BelAA xA q p xXA

xxx

()

Œ=Œ-for and for ,

pmA

xx A

()

a .

438 APPENDIX C. CORRECTNESS OF ALGORITHM 6.1

for all B Ã X, and there is y Œ A such that p

π Bel(A)/|A|, where A is the set

chosen in Step 1 of the algorithm. That is, Bel(A)/|A|≥Bel(B)/|B| for all B 債

X, and if Bel(A)/|A|=Bel(B)/|B|, then |A|>|B|. Furthermore, we can assume

that p

> Bel(A)/|A|. This is justiﬁed by the following argument: If p

Bel(A)/|A|, then due to Bel(A) £S

xŒA

there exists y¢ŒA such that p

y¢

Bel(A)/|A|, and we can take y¢ instead of y.

For a ﬁnite sequence {x

}

i=0

, where x

Œ X and m is a positive integer, let F

denote the set of all focal elements associated with Bel and let

for i = 1,...,m, where a

are the nonnegative real numbers whose existence

is guaranteed by Lemma C.2 (we ﬁx one such set of those numbers). Let

There are now two possibilities. Either there is z Œ D such that in the

sequence {x

}

i=0

from the deﬁnition of D, where x

= z, it holds that p

< p

m-1

This, however, leads to a contradiction with the maximality of ·p

|x ŒXÒ since

by Lemma C.1, where q

= p

for x Œ (X - {z, x

m-1

}), q

= p

+ e, and

; here

where C is the focal element of Bel from the deﬁnition of D containing both

z and x

m-1

and such that The distribution ·q

|x Œ XÒ satisﬁes the con-

straints induced by Bel due to the Lemma C.2. Or, the second possibility is

that for all x Œ D and all focal elements C 債 X of Bel such that x Œ C, when-

ever it holds that p

≥ p

for all z Œ (C - {x}). It follows from Lemma

C.2 that Bel(D) =S

xŒD

. However, this fact contradicts the choice of A,

since

We have shown that any ·p

|x Œ XÒ maximizing the Shannon entropy

within the constraints induced by Bel, has to satisfy p

= Bel(A)/|A| for all

x Œ A.

Let Bel¢ denote the generalized belief function on X - A deﬁned in Step 3

of the algorithm; that is, Bel¢ (B) = Bel(B » A) - Bel(A). It is really a gener-

Bel D

Bel A

xD x

()

=≥>

()

> 0,

eaŒ+

()

{}()

,min , ,

mm--

-<-

ŒŒ

ÂÂ

xX x x xX x x

pp qqlog log

DxX m

xyx x i mx x

imzxpp

mii

iz x

=Œ$

{}

{

== = Œ

()

="Œ

()

≥

}

non- negative integers and x such that

for all and for all

, , , ,..., ,

, ,..., ,

F xCXCxC

()

=» Õ Œ Œ >

{}

F ,,

0 and a

APPENDIX C. CORRECTNESS OF ALGORITHM 6.1 439

alized belief function.The reader can verify that its corresponding generalized

basic probability assignment can be expressed by

for all nonempty sets B 債 X - A, and m¢(Ø) = 0. Assume, then, that ·p

|x Œ

X - AÒ is such that p

Œ [0, 1],

and

for all B Ã X - A. Let ·q

|x Œ XÒ denote the complete distribution deﬁned by

Eq. (C.1). Clearly, q

Œ [0, 1]. Since

we have

From Bel(A)/|A|≥Bel(B)/|B| for all B 債 X, it follows that S

xŒB

≥ Bel(C) for

all C 債 A. Assume that B 債 X and B « (X - A) π Ø. We know that

From Eq. (5.40), we get

Since Bel(A)/|A|≥Bel(A « B)/|A « B|, we get

Bel A

Bel B

xA BxB X AxB

()

≥

()

Œ«Œ« -

()

ÂÂÂ

Bel A B Bel A Bel B Bel A B»

()

≥

()

-«

()

p Bel B X A Bel A B Bel A

xB XA

≥¢«-

()()

=»

()

Œ« -

()

Bel X p Bel A

Bel A

xXA

xAxXA

()

Œ-

ŒŒ-

ÂÂ

Bel X A Bel X Bel A¢-

()

pBelB

≥¢

()

pBelXA

xXA

=¢-

()

Œ-

()

Õ«-

()()

mB mC

CXC XA B

440 APPENDIX C. CORRECTNESS OF ALGORITHM 6.1

Conversely, assume ·q

|x Œ XÒ is such that q

Œ [0, 1], q

= Bel(A)/|A| for all

x Œ A, S

xŒX

= Bel(X), and S

xŒB

≥ Bel(B) for all B Ã X. Clearly, we have

Let C 債 X - A. We know that S

xŒA»C

≥ Bel(A » C), but it follows from this

fact that

This means that we reduced the size of our problem, and therefore the

theorem follows by induction. 䊏

Several remarks regarding Algorithm 6.1 can be made:

(a) Note that we have also proved that the distribution maximizing the

entropy within the constraints induced by a given belief function is

unique. It is possible to prove this fact directly by using the concavity

of the Shannon entropy.

(b) The condition that A has the maximal cardinality among sets B with

equal value of Bel(B)/|B| in Step 1 is not necessary for the correctness

of the algorithm, but it speeds it up. The same is true for the condition

Bel(X) > 0 in Step 5. Moreover, we could exclude the elements of X

outside the union of all focal elements of Bel (usually called core within

evidence theory) altogether.

that it is not necessary to work with the whole power set P(X); it is

enough to consider C = {A 債 X $ {F

,..., F

} 債 P(X) such that

m(F

) > 0 and }.

q Bel A C Bel A Bel C

≥»

()

=¢

()

Bel X A Bel X Bel A q

xXA

¢-

()

Œ-

APPENDIX C. CORRECTNESS OF ALGORITHM 6.1 441