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

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

APPENDIX D

PROPER RANGE

OF GENERALIZED

SHANNON ENTROPY

442

The purpose of this Appendix is to prove that S

(Bel) - GH(Bel) ≥ 0 for any

given belief function (or any of its equivalent representations). To facilitate

the proof, which is adopted from Smith [2000], some relevant features of

Algorithm 6.1 are examined ﬁrst.

Applying Algorithm 6.1 to a given belief function Bel deﬁned on P(X)

results in the following sequence of sets A

債 X and associated probabilities

, each obtained in the ith pass through Steps 1–5 (or the ith iteration) of the

algorithm (i Œ ⺞

, assuming that the algorithm terminates after n passes):

•

is equal to A 債 X such that

is maximal. If there are more such sets than one, then the one with the

largest cardinality is chosen. Each element of set A

is assigned the

probability

•

is equal to A 債 X such that

Bel A A Bel A

()

Bel A

()

Bel A

()

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

is maximal. If there are more such sets than one, then the one with the

largest cardinality |A - A

| is chosen. Each element of set A

- A

assigned the probability

•

is equal to A 債 X such that

is maximal. If there are more such sets than one, then the one with the largest

cardinality |A - (A

» A

)| is chosen. Each element of set A

- (A

» A

) is

assigned the probability

•

In general, for any i Œ ⺞

, A

is equal to A 債 A

such that

(D.1)

is maximal. If there are more such sets than one, then the one with the largest

cardinality |A - (傼

i-1

j=1

)| is chosen. Each element of set A

- (傼

i-1

j=1

) is

assigned the probability

(D.2)

In the following, let m denote the basic probability assignment function

associated with the considered belief function Bel. Observe that in each iter-

ation of the algorithm, values of m for some focal elements are converted to

probabilities. In pass 1, these are focal elements B such that B 債 A

; in pass

2, they are focal elements B such that B 債 A

» A

, but B Õ

A. In general, in

the ith iteration they are focal elements in the family

(D.3)

BXBABA=Õ Õ Õ

{}

and .

Bel A Bel A

()

Bel A A Bel A

()

Bel A A A Bel A A

AAA

321 21

321

»»

()

-»

()

-»

()

Bel A A A Bel A A

AA A

»»

()

-»

()

-»

()

21 21

Bel A A Bel A

21 1

()

APPENDIX D. PROPER RANGE OF GENERALIZED SHANNON ENTROPY 443

444 APPENDIX D. PROPER RANGE OF GENERALIZED SHANNON ENTROPY

The regularities of Algorithm 6.1, expressed by Eqs. (D.1)–(D.3), make it

possible to decompose S

and GH into n components, S

and GH

, one for each

iteration of the algorithm, such that

(D.4)

(D.5)

The proof that S

(Bel) - GH(Bel) ≥ 0 then can be accomplished by proving

that S

(Bel) ≥ GH

(Bel) for all i Œ ⺞

. To pursue the proof, it is convenient to

prove the following Lemma ﬁrst.

Lemma D.1. In each iteration of Algorithm 6.1,

(D.6)

Proof. Assume that inequality (D.6) does not hold for some i Œ ⺞

. Then,

(D.7)

Due to the maximization of the assigned probabilities in each iteration of the

algorithm, p

> p

for all j < i. Hence,

(D.8)

for all j Œ ⺞

under the assumption (D.7).

According to Eq. (D.2), |A

- 傼

i-1

j=1

| elements of X are assigned the prob-

ability p

in the ith iteration of the algorithm. Hence, the inequality

(D.9)

must hold since all the probabilities generated by the algorithm must add to

1. However,

AAp

-£

GH Bel GH Bel

()

S Bel S Bel

()

APPENDIX D. PROPER RANGE OF GENERALIZED SHANNON ENTROPY 445

which contradicts inequality (D.9). 䊏

Theorem D.1. For any belief function Bel and the associated basic probabil-

ity assignment function m, S

(m) - GH(m) ≥ 0.

Proof. Assume that Algorithm 6.1 terminates after n iterations. Let

(D.10)

where F

is deﬁned by Eq. (D.3). Then,

(D.11)

and, since for all B Œ F

(D.12)

Now deﬁne

(D.13)

which represents the contribution to S

(m) by probabilities generated in itera-

tion i of the algorithm. That is,

(D.14)

SSm

()

SA Ap p

=- -

log ,

mB B mB A

()

ÂÂ

log log .

債

GH GH m

()

GH m B B

()

log ,

AApApAAp AAp

AAA

AAAA

jij

- = + - +◊◊◊+ -

>+-

(

+◊◊◊

)

()()

=+»-

()

+◊

11 2 1 2

121

1211

by Eq. D.8

◊◊ ◊

(

())

Now observe that

(D.15)

Applying this equation and Eq. (D.2) to Eq. (D.13), we obtain

(D.16)

The proof is now completed by showing that S

≥ GH

for all i Œ⺞

䊏

SmBp

mB A

mB B

()

≥-

()

≥

() ( )()

log

log .

log

by Lemma

by Eq. D.12

SA A

mB p

=- -

()

log

log .

Bel A Bel A m B

()

446 APPENDIX D. PROPER RANGE OF GENERALIZED SHANNON ENTROPY

APPENDIX E

MAXIMUM OF GS

SECTION 6.9

447

It is stated in Section 6.9 that the maximum, GS

(n), of the functional

(E.1)

where m

Œ [0, 1] for all i Œ ⺞

and

(E.2)

is obtained when

(E.3)

for all i Œ ⺞

; the value of a is determined by solving the equation

(E.4)

In order to derive this maximum, it is convenient to use the method of

Lagrange multipliers. Using the constraint Eq. (E.2) of values of m

, we form

the Lagrange function

Lmmi m

ii i

()

ÂÂ

log ,

211

()

a ln

()

12ln

GS n m m i

aii

()

log ,

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

where a is a Lagrange multiplier. Now, setting the partial derivatives of L with

respect to the individual variables m

to zero, we obtain

for all i Œ ⺞

. Solving these equations for m

, we obtain

(E.5)

for all m

Œ ⺞

. Adding all these equations results in

due to Eq. (E.2). This equation can be rewritten as

(E.6)

Introducing, for convenience

and solving Eq. (E.6) for a, we readily obtain

(E.7)

Substituting this expression for a into Eq. (E.5), we obtain

Finally, substituting this expression for each m

into Eq. (E.1), we obtain

GA n i s s

ss i

log

log .

()

()( )

()

[]

()

1log

a =-

()

log ln .

112s

()

12 1

()

a ln

112

()

a ln

()

12a ln

∂

()

log ln

12 0a

448 APPENDIX E. MAXIMUM OF GS

IN SECTION 6.1

APPENDIX F

GLOSSARY OF KEY

CONCEPTS

449

Additive (classical) measure. A set function m: C Æ ⺢

deﬁned on a nonempty

family C of subsets of a given set X for which m(Ø) = 0 and m(A » B) =

m(A) + m(B) for all A, B, A » B Œ C such that A « B = Ø.

Aggregate uncertainty. For a given convex set D of probability distributions,

aggregate uncertainty (subsuming nonspeciﬁcity and conﬂict) is deﬁned by

the maximal value of the Shannon entropy within D.

Alternating Choquet capacity of order k. A subadditive measure m on ·X, C Ò

that satisﬁes the inequality

for all families of k sets in C.

Basic possibility function. A possibility measure restricted to singletons.

Basic probability assignment. For any given nonempty and ﬁnite set X,a

function m: P(X) Æ [0, 1] such that m(Ø) = 0, , and m(A) ≥ 0

for all A 債 X.

Belief measure. Choquet capacity of inﬁnite order.

Bit. A unit of uncertainty: one bit of uncertainty is equivalent to uncertainty

regarding the truth or falsity of one elementary proposition.

Characteristic function. Function c

:X Æ {0, 1} by which a subset A of a given

universal set X is deﬁned. For each x ŒX,

if is a member of

if is not a member of .

AXÕ

()

= 1

mmAA

π∆

£-

()

⺞

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

Choquet capacity of order k. A superadditive measure m on ·X, CÒ that

satisﬁes the inequalities

for all families of k sets in C.

Choquet integral. Given a nonnegative, ﬁnite, and measurable function f on

set X and a monotone measure on a family C of subsets of X that contains

Ø and X, the Choquet integral of f with respect to m on a given set A ŒC,

(C)兰

fdm, is deﬁned by the formula

where

F = {x|f(x) ≥ a}, a Œ [0, •).

Compatibility relation. Binary relation on X

that is reﬂexive and symmetric.

Conﬂict. The type of information-based uncertainty that is measured by the

Shannon entropy and its various generalizations.

Convex fuzzy subset A of R

. Fuzzy set whose a-cuts are convex subset of R

in the classical sense for all a Œ(0, 1].

Convex subset A of R

. For any pair of points r =·r

|i Œ ⺞

Ò and s =·s

|i Œ

⺞

Ò in A and every real number l Œ [0, 1], the point t =·lr

+ (1 - l) s

|i Œ

⺞

Ò is also in A.

Cutworthy property. Any property of classical sets that is fuzziﬁed via the a-

cut representation by requiring that it holds in the classical sense in all a-

cuts of the fuzzy sets involved.

Defuzziﬁcation. A replacement of a given fuzzy interval by a single real

number that, in the context of a given application, best represents the fuzzy

interval.

Dempster–Shafer theory. Theory of uncertainty based on belief measures and

plausibility measures.

Disaggregated total uncertainty. For a given set D of probability distributions,

either the pair

or, alternatively, the pair

where GH, S

and S denote, respectively, the generalized Hartley measure,

the aggregate uncertainty, and the minimal value of the Shannon entropy

within D.

TU S S S=· - Ò,

TU GH S GH=· - Ò,

() ,Cfd AFd

mm a

ÚÚ

=«

()

mmAA

π∆

≥-

()

⺞

450 APPENDIX F. GLOSSARY OF KEY CONCEPTS

Equivalence relation. Binary relation on X

that is reﬂexive, symmetric, and

transitive.

Fuzziﬁcation. A process of imparting fuzzy structure to a deﬁnition (concept),

a theorem, or even a whole theory.

Fuzziness. The type of uncertainty that is not based on information deﬁciency,

but rather on the linguistic imprecision (vagueness) of natural language.

Fuzzy partition of set X. A ﬁnite family {A

ŒF(X), A

π Ø, i Œ ⺞

, n ≥ 1}

of fuzzy subsets A

of X such that for each x ŒX

Fuzzy complement. A function c: [0, 1] Æ [0, 1] that is monotonic decreasing

and satisﬁes c(0) = 1 and c(1) = 0; also it is usually continuous and such that

c(c(a)) = a for any a Œ [0, 1].

Fuzzy implication. Function J of the form [0, 1]

Æ [0, 1] that for any truth

values a, b of given fuzzy propositions p, q, respectively, deﬁnes the truth

value J(a, b), of the proposition “if p, then q.”

Fuzzy number. Normal fuzzy sets on ⺢ whose support is bounded and whose

a-cuts are closed intervals of real numbers for all a Œ (0, 1].

Fuzzy relation. Fuzzy subset of a Cartesian product of several crisp sets.

Fuzzy system. A system whose variables range over states that are fuzzy

numbers or fuzzy intervals (or some other relevant fuzzy sets).

Generalized Hartley measure. A functional GH deﬁned by the formula

where D is a given convex set of probability distributions on a ﬁnite set X

and m

is the Möbius representation associated with D.

Generalized Shannon entropy. For a given convex set D of probability dis-

tributions, the difference between the aggregate uncertainty and the

generalized Hartley measure or, alternatively, the minimal value of the

Shannon entropy within D.

Hartley-like measure of uncertainty. The functional deﬁned by Eq. (2.38) by

which the uncertainty associated with any bounded and convex subset of

⺢

is measured.

Hartley measure of uncertainty. The functional H(E) = log

|E|, where E is a

ﬁnite set of possible alternatives and uncertainty is measured in bits.

Information transmission. In every theory of uncertainty, the difference

between the sum of marginal uncertainties and the joint uncertainty.

Interval-valued probability distribution. For a given ﬁnite set X, a tuple

·[p

(x), p

(x)]|x ŒXÒ such that and .

xXŒ

()

≥ 1

xXŒ

()

£ 1

GH m A A

()

log ,

()

⺞

APPENDIX F. GLOSSARY OF KEY CONCEPTS 451