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

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

als, which are central to GIT, are shown to be largely invariant with respect to

the great diversity of uncertainty theories.

Further generalization of uncertainty theories by extending classical sets to

fuzzy sets of various types, which is usually referred to as fuzziﬁcation, is the

subject of Chapter 8. In order to make the book self-contained, relevant con-

cepts of fuzzy set theory are introduced in Chapter 7. This important area of

GIT is still largely undeveloped. Only a few uncertainty theories have been

fuzziﬁed thus far, and all these developed fuzziﬁcations involve only the stan-

dard fuzzy sets.

The survey of GIT is concluded by examining four important principles of

uncertainty in Chapter 9.These are methodological principles justiﬁed on epis-

temological grounds.Their applications to a wide variety of practical problems,

which are discussed in this chapter, demonstrate the importance of GIT.

The closing chapter of the book (Chapter 10) is devoted to conclusions. GIT

is examined in this chapter in both retrospect and prospect. The overall con-

clusion from this examination is that GIT is still in an early stage of its devel-

opment, notwithstanding the many important results that are surveyed in this

book.

NOTES

1.1. The recent book by Pollack [2003] is recommended as supplementary reading to

this chapter. It is a well-written and thorough discussion of the important role of

uncertainty in both science and ordinary life. Also recommended is the book by

Smithson [1989], in which the many facets of changing attitudes toward uncer-

tainty in science and other areas of human affairs throughout the 20th century are

carefully examined.

1.2. The turning point leading to the acceptance of methods based on probability

theory in science was the publication of sound mathematical foundations of sta-

tistical mechanics by Willard Gibbs [1902].

1.3. Research on a broader conception of uncertainty-based information, liberated

from the conﬁnes of classical set theory and probability theory, began in the

early 1980s [Higashi and Klir, 1983a, b; Höhle, 1982; Yager, 1983]. The name

generalized information theory (GIT) was coined for this research program by

Klir [1991].

1.4. Information measured solely by the reduction of uncertainty is not explicitly con-

cerned with the semantic and pragmatic aspects of information viewed in the

broader sense [Cherry, 1957; Jumarie, 1986, 1990; Kornwachs and Jacoby, 1996].

However, these aspects are not ignored, but they are assumed to be addressed

prior to each particular application. For example, when dealing with a system of

some kind (in general, a set of interrelated variables), we are assumed to under-

stand the language (formalized or natural) in which the system is described (this

resolves the semantic aspect of information), and we are also assumed to know

the purpose for which the system has been constructed (this resolves the prag-

matic aspect).These assumptions certainly restrict the applicability of uncertainty-

1. INTRODUCTION

based information. However, an argument can be made [Dretske, 1981, 1983] that

the notion of uncertainty-based information is sufﬁciently rich as a basis for addi-

tional treatment, through which the broader concept of information, pertaining to

human communication and cognition, can adequately be formalized.

1.5. The concept of information has also been investigated in terms of the theory of

computability. In this approach, which is not covered in this book, the amount of

information represented by an object is measured by the length of its shortest

description in some standard language (e.g., by the shortest program for the stan-

dard Turing machine). Information of this type is usually referred to as descriptive

information or algorithmic information [Kolmogorov, 1965; Chaitin, 1987], and it

is connected with the concept of Kolmogorov complexity [Li and Vitányi, 1993].

1.6. Some additional approaches to information have appeared in the literature since

the early 1990s. For example, Devlin [1991] formulates and investigates informa-

tion in terms of logic, while Stonier [1990] views information as a physical prop-

erty deﬁned as the capacity to organize a system or to maintain it in an organized

state. Another physics-based approach to information is known in the literature

as Fisher information [Fisher, 1950; Frieden, 1998]. A more recent, measurement-

based approach was developed by Harmuth [1992]. Again, these various

approaches are not covered in this book.

1.7. A digest of most mathematical concepts that are relevant to the subject of this

book is in Section 1.4.A useful reference for strengthening the background in clas-

sical set theory, which is suitable for self-study is Set Theory and Related Topics by

S. Lipschutz (Schaum Series/McGraw-Hill, New York). Basic familiarity with cal-

culus and some aspects of mathematical analysis are also needed for understand-

ing this book. The book Mathematical Analysis by T.M. Apostol (Addison-Wesley,

Reading, MA) is recommended as a useful reference in this area.

EXERCISES

1.1. For which of the following pairs of sets is A = B?

(a) A = {0, 1, 2, 3}; B = {1, 3, 2, 0}

(b) A = {0, 1, 0, 2, 3}; B = {0, 1, 2, 3, 2}

(d) A = {0}; B = {∆}

1.2. Which of the following deﬁnitions are acceptable as deﬁnitions of clas-

sical (crisp) sets?

(a) A = {a | a is a real number}

(b) B = {b | b is a real number much greater than 1}

(d) D = {d | d is a section in this book}

(e) E = {e | e is a set}

(f) F = { f | f is a pretty girl}

EXERCISES 23

1.3. Which of the following statements are correct provided that X = {∆,0,

1, 2, {0, 1}}?

(a) {0, 1} ŒX

(b) {0, 1} Ã X

(d) {{0, 1}} Ã X

(e) {0, 1, 2} ŒX

(f) {∆} ŒX

1.4. Let A = ⺞

, B = {b | b is a natural number divisible by 3, b £ 30},

C = {c | c is an odd natural number, a £ 50}. Determine the following sets:

(a) A - B; A - C; C - A, C - B

(b) A « B; A « C; B « C

(d) (A « B) » C;(A » B) « C; B » (A « C)

1.5. Determine the partition lattices of sets A = {1, 2, 3} and B = {1, 2, 3, 4}.

1.6. How many possible relations can be deﬁned on the following Cartesian

products of ﬁnite sets?

(a) X

¥ X

¥ ...¥ X

(b) A ¥ B

¥ C

(d) A

¥ P

(B) ¥ C

1.7. For each of the following relations, determine whether or not it is reﬂex-

ive, symmetric, antisymmetric, or transitive:

(a) R Õ P(X) ¥ P(X); ·A, BÒŒR iff A Õ B for all A, B ŒP(X).

(b) R Õ C ¥ C, where C denotes the set of courses in a graduate

program: ·a,bÒŒR iff course a is a prerequisite of course b.

Õ ⺞ ¥ ⺞: ·a,bÒŒR

iff the remainders obtained by diving a and

b by n are the same, where n is some speciﬁc natural number greater

than 1.

(d) R Õ W ¥ W, where W denotes the set of all English words:

·a,bÒŒR iff a is a synonym of b.

(e) R Õ F ¥ F, where F denotes the set of all ﬁve-letter English words:

·a,bÒŒR iff a differs from b in at most one position.

(f) R Õ A ¥ A: ·a,bÒŒR iff f(a) = f(b), where f is a function of the form

(g) R Õ T ¥ T, where T denotes all persons included in a family tree:

·a,bÒŒR iff a is an ancestor of b.

fA A:.Æ

24 1. INTRODUCTION

(h) R = {·0,0Ò, ·0,1Ò, ·1,0Ò, ·1,1Ò, ·1,2Ò, ·2,2Ò, ·0,2Ò, ·3,3Ò}

(i) R = {·0,0Ò, ·0,3Ò, ·1,1Ò, ·2,2Ò, ·1,0Ò, ·0,1Ò, ·3,1Ò, ·3,3Ò, ·3,0Ò}

1.8. Let X = ⺞

. Determine which of the following relations on X

are equiv-

alence relations, compatibility relations, or partial orderings:

(a) R

= {·x, yÒ|x < y}

(b) R

= {·x, yÒ|x £ y}

= {·x, yÒ|x = y}

(d) R

= {·x, yÒ|2x = y}

(e) R

= {·x, yÒ|x = y - 1}

(f) R

= {·x, yÒ|x < y or x > y}

(g) R

= {·1, 2Ò, ·2, 3Ò, ·3, 2Ò, ·4, 3Ò}

1.9. For the binary relations in Exercise 1.8, determine the following com-

positions and joins:

(a) R

and R

(b) R

-1

and R

-1

and R

(d) R

-1

and R

-1

1.10. For each of the following functions, determine the supremum and

inﬁmum, as well as the maximum and minimum (if they exist):

(a) f(x) = 1 - x, where x Œ [0, 1)

(b) f(x) = sinx, where x Œ [0, 2p]

(d) f(x) = sinx/x, where x Œ⺢

(f) f(x) = max[0, 2x - x

], where x Œ [0, 1]

1.11. For each of the following binary relations on ⺢

, determine its 1-

dimensional projections, its cylindric extensions, and the cylindric closure

of these projections:

(a) R = {·x, yÒ|x

+ y

£ 1}

(b) R = {·x, yÒ|0 £ y £ 2x - x

}

(d) R = {·x, yÒ|x

+ 2y

£ 1}

EXERCISES 25

CLASSICAL POSSIBILITY-

BASED UNCERTAINTY

THEORY

When you have eliminated the impossible, whatever remains must have been the

case, however improbable it may seem to be.

—Sherlock Holmes

2.1. POSSIBILITY AND NECESSITY FUNCTIONS

One of the two classical theories of uncertainty, which is the subject of this

chapter,is based on the notion of possibility and the associated notion of neces-

sity. The other classical theory, which is the subject of Chapter 3, is based on

the notion of probability. Of the two classical theories, the one based on pos-

sibility is simpler, more fundamental, and older. To describe this rather simple

theory, let X denote a ﬁnite set of mutually exclusive alternatives that are of

concern to us (diagnoses, predictions, etc.). This means that in any given situ-

ation only one of the alternatives is true. To identify the true alternative, we

need to obtain relevant information (e.g., by conducting relevant diagnostic

tests). The most elementary and, at the same time, the most fundamental kind

of information is a demonstration (based, for example, on outcomes of the

conducted diagnostic tests) that some of the alternatives in X are not possi-

ble. After excluding these alternatives from X, we obtain a subset E of X. This

subset contains only alternatives that, according to the obtained information,

are possible. We can say that alternatives in E are supported by the evidence.

Let the characteristic function of the set of all possible alternatives, E,be

called in this context a basic possibility function and be denoted by r

. Then,

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

(2.1)

Using common sense, a possibility function, Pos

, deﬁned on the power set,

P(X), is then given by the formula

(2.2)

for all A ŒP(X). It is indeed correct to say that it is possible that the true alter-

native is in A when A contains at least one possible alternative (an alterna-

tive that is also contained in E). It follows immediately that

(2.3)

for any pair of sets A, B ŒP(X).

Given the possibility function Pos

on the power set of X, it is useful to

deﬁne another function, Nec

, to describe for each A ŒP(X) the necessity that

the true alternative is in A. Clearly, the true alternative is necessarily in A if

and only if it is not possible that it is in A

, the complement of A. Hence,

(2.4)

for all A ŒP(X).

2.2. HARTLEY MEASURE OF UNCERTAINTY FOR FINITE SETS

The question of how to measure the amount of uncertainty associated with

a ﬁnite set E of possible alternatives was addressed by Hartley [1928]. He

showed that the only meaningful way to measure this amount is to use a func-

tional of the form.

or, alternatively,

where |E| denotes the cardinality of set E; b and c are positive constants, and

it is required that b π 1. Each choice of values b and c determines the unit in

which the uncertainty is measured. Requiring, for example, that

which is the most common choice, uncertainty would be measured in bits.One

bit of uncertainty is equivalent to uncertainty regarding the truth or falsity of

log ,21=

log ,

crx

log

()

Nec A Pos A

()

Pos A B Pos A Pos B

EEE

()

() ()

{}

max ,

Pos A r x

()

max ,

()

{

when

when .

2.2. HARTLEY MEASURE OF UNCERTAINTY FOR FINITE SETS 27

one elementary proposition. Conveniently choosing b = 2 and c = 1 to satisfy

the preceding equation, we obtain a unique functional, H, deﬁned for any basic

possibility function, r

, by the formula

This functional is usually called a Hartley measure of uncertainty. It is easy to

see that uncertainty measured by this functional results from the lack of speci-

ﬁcity. Clearly, the larger the set of possible alternatives, the less speciﬁc are

predictions, diagnoses, and the like. Full speciﬁcity is obtained when only one

of the considered alternatives is possible. This type of uncertainty is thus well

characterized by the term nonspeciﬁcity.

2.2.1. Simple Derivation of the Hartley Measure

This simple derivation is due to Hartley [1928]. Assume, as before, that from

among a ﬁnite set X of considered alternatives, the only possible alternatives

are those in a nonempty subset E of X. That is, there is evidence that alterna-

tives that are not in set E are not possible.

Given now a particular set E of possible alternatives, sequences of its

elements can be formed by successive selections. If s selections are made, then

there are |E|

different potential sequences.The amount of uncertainty in iden-

tifying one of the sequences, H(|E|

), which is equivalent to the amount of

information needed to remove this uncertainty, should be proportional to s.

That is,

where K(|E|) is some function of |E|.

Consider now two nonempty subsets of X, E

and E

, such that |E

|π|E

Assume that after making s

selections from E

and s

selections from E

the number of sequences in both cases is the same. Then, the amounts of

information needed to remove uncertainty associated with the two sets of

sequences should be the same as well. That is, if

(2.5)

then

(2.6)

From Eqs. (2.5) and (2.6), we obtain

log

KE s KE s

11 22

◊= ◊.

= ,

HE KE s

()

◊ ,

Hr E

()

= log .

28 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

and

respectively. Hence,

This equation can be satisﬁed only by a function K of the form

where b, c are positive constants and b π 1. Each choice of values of the con-

stants b and c determines the unit in which uncertainty is measured. When

b = 2 and c = 1, which is the most common choice, uncertainty is measured

in bits, and we obtain

(2.7)

This can also be expressed in terms of the basic possibility function r

(2.8)

2.2.2. Uniqueness of the Hartley Measure

Hartley’s derivation of the measure of possibilistic uncertainty (or nonspeci-

ﬁcity) H, which is expressed by either Eq. (2.7) or Eq. (2.8), is certainly con-

vincing. However, it does not explicitly prove that H is the only meaningful

functional to measure possiblistic uncertainty in bits. To be meaningful, the

functional must satisfy some essential axiomatic requirements.The uniqueness

of this functional H was proven on axiomatic grounds by Rényi [1970b].

Since, according to our intuition, the possibilistic uncertainty depends only

on the number of possible alternatives (the number of elements in the set

E Õ X), Rényi conceptualized the measure of possibilistic uncertainty, H, as a

functional of the form:

Using this form, he characterized the functional by the following axioms:

Axiom (H1) Branching. H(n · m) = H(n) + H(m).

H :.⺞⺢Æ

Hr r x

()

log .

HE E

()

= log ,

KE c E

()

=◊log ,

log

= ,

2.2. HARTLEY MEASURE OF UNCERTAINTY FOR FINITE SETS 29

Axiom (H2) Monotonicity. H(n) £ H(n + 1).

Axiom (H3) Normalization. H(2) = 1.

Axiom (H1) involves a set with m · n elements, which can be partitioned

into n subsets each with m elements. A characterization of an element from

the full set requires the amount H(m · n) of information. However, we can

also proceed in two steps to characterize the element by taking advantage of

the partition of the set. First, we characterize the subset to which the element

belongs: the required information is H(n). Then, we characterize the element

within the subset: the required information is H(m). These two amounts of

information completely characterize an element of the full set and, hence,their

sum should equal H(m · n). This is exactly what the axiom requires.

Axiom (H2) expresses an essential and rather obvious requirement:

When the number of possible alternatives increases, the amount of informa-

tion needed to characterize one of them cannot decrease. Axiom (H3) is

needed to deﬁne the measurement unit. As it is stated by Rényi, the deﬁned

measurement unit is the bit.

Using the three axioms, Rényi established that H deﬁned by Eq. (2.7) is the

only functional that satisﬁes these axioms. This is the subject of the following

uniqueness theorem.

Theorem 2.1. The functional H(n) = log

n is the only functional that satisﬁes

Axioms (H1)–(H3).

Proof. Let n be an integer greater than 2. For each integer i, deﬁne the integer

q(i) such that

(2.9)

These inequalities can be written as

When we divide these inequalities by i and replace log

2 with 1, we get

Consequently,

(2.10)

Let H denote a functional that satisﬁes Axioms (H1)–(H3).Then, by Axiom

(H2),

lim log .

Æ•

()

£<

()

log .

qi i n qi

()

£<

()

log log log .

22 2

212

1qi

() ()

£< .

30 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

(2.11)

for a < b. Combining Eq. (2.11) and Eq. (2.9), we obtain

(2.12)

By Axiom (H1), we obtain

If we apply this to all three terms of Eq. (2.12), we get

By Axiom (H3), H(2) = 1, so these inequalities become

Dividing through by i yields

and consequently,

(2.13)

Comparing Eq. (2.10) with Eq. (2.13), we conclude that H(n) = log

n for

n > 2. Since log

2 = 1 and log

1 = 0, function H trivially satisﬁes all the axioms

for n = 1, 2 as well. 䊏

2.2.3. Basic Properties of the Hartley Measure

First, it is easy to see that the Hartley measure deﬁned by Eq. (2.7) satisﬁes

the inequalities

for any E ŒP(X). The lower bound is obtained when only one of the consid-

ered alternatives is possible, as exempliﬁed by deterministic systems. The

upper bound is obtained when all considered alternatives are possible. This

expresses the state of total ignorance.

In some applications, it is preferable to use a normalized Hartley measure,

NH, which is deﬁned by the formula

()

£HE Xlog

lim .

Æ•

()

qi i H n qi

()

£◊

()

+1.

qi H i H n qi H

()

◊

()

£◊

()

◊

()

212.

Ha kHa

()

=◊

()

HHnH

() ()

()

Ha Hb

()

2.2. HARTLEY MEASURE OF UNCERTAINTY FOR FINITE SETS 31