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

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

The Cartesian product of the projections includes the original set as a subset,

and both of them are cubes. Hence, the area of the surface is a Cartesian

product, which is twice the left-hand side of the preceding inequality. Hence,

this area is greater than or equal to the area of the surface of the set A, which

is twice the right-hand side. Therefore, the inequality holds.

n-Dimensional Case In addition to n = 2, 3, it is easy to prove the additiv-

ity for any arbitrary n under the assumption that A is a set with equal edges.

To show the proof, let a

= a for all i Œ⺞

. Then, we have

and consequently,

Hence, the additivity holds. For a fully general proof of additivity of the

Hartley-like measure, see Note 2.3.

2.3.3. Examples

The purpose of this section is to illustrate by speciﬁc examples some subtle

issues involved in computing the various forms of the Hartley-like measure

(basic, conditional, normalized) as well as information based on the Hartley-

like measure. For the sake of simplicity, the examples are restricted to n = 2

and it is assumed that the universal set is the Cartesian product of X ¥ Y, where

X = Y = [0, 100] in some units of length, which are assumed to be the same in

all examples. This means that m(X) = m(Y) = 100 and m(X ¥ Y) = 100

. Due to

the additivity of HL, we have

EXAMPLE 2.6. Assume that, according to given evidence, the only possible

alternatives (points in X ¥ Y) are located in a square, S, whose side is equal

HL X Y¥

()

=+-

()

log

log . .

222

101 100 100

101 13 32

111

()

[]

()

≥+

()

[]

≥+

()

===

’’’

mm m mAA A A a

ttt

ikik

()

≥

cos

52 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

to 8. Due to the additivity of HL, we can readily calculate the nonspeciﬁcity

of this evidence, the associated conditional nonspeciﬁcities, and the informa-

tion transmission:

Next, we can calculate the amount of information contained in the given

evidence:

It may also be desirable to calculate the normalized counterparts of the

nonspeciﬁcity and information, which are independent of the chosen units:

The last result means that the given evidence contains 52% of the total amount

of information needed to identify the true alternative. Clearly, NHL(S) +

(S) = 1.

EXAMPLE 2.7. In this example, the only possible alternatives are known to

be located in a circle, C, with a radius r = 4. Clearly, m(C) = p · 4

= 50.27. The

two projections of C, C

and C

, are in this case invariant with respect to rota-

tions and, clearly, m(C

) = m(C

) = 8. Hence, the calculations of the same quan-

tities as in Example 2.6 is straightforward:

HL C

HL C H C

HL C C HL C HL C

T C C HLC HLC HLC

XY Y

YX X

HL X Y X Y

()

=+-

()

log . . ,

log . ,

9 5027 8 607

9317

0027

725

046

054

I C HL X Y HL C

NHL C HL C HL X Y

NI C I C HL X Y

HL HL

()

=¥

()

NHL S HL S HL X Y

NI S I S HL X Y

HL HL

()

048

052

I S HL X Y HL S

()

=¥

()

= 698..

HL S

HL S HL S

HL S S H S H S

TSS HLS HLS HS

XY Y

YX X

HL X Y X Y

()

=+-

()

log

log . ,

222

988

81 6 34

9317

317

(()

= 0.

2.3. HARTLEY-LIKE MEASURE OF UNCERTAINTY FOR INFINITE SETS 53

EXAMPLE 2.8. According to given evidence, the only possible alternatives

are located in an equilateral triangle, E, with sides of length a (in some

appropriate units of lengths). Assume, without any loss of generality, that one

vertex of the triangle is located at the origin of the coordinated system, as

shown in Figure 2.4a. When the triangle is rotated around the origin, the

projections of E change and, hence, the logarithmic function in Eq. (2.38)

changes as well. To calculate HL(E), we need to determine the minimum of

this function.

As shown in Figure 2.4a, the position of the triangle can be expressed by

the angle a. Due to the symmetry of E, it is sufﬁcient to consider values

a Œ [0, 30°]. Within this range, the dependence of the projections, E

and E

on a is expressed by the equations

Moreover, which is the area of the triangle. The logarithmic

function in Eq. (2.38) is then a function of a, f(a), expressed by the formula

A natural way to determine extremes of f(a) is to solve the equation f ¢(a) =

0 for a, where f ¢(a) denotes the derivative of f with respect to a. That is,

This equation reduces to the simple equation

which is independent of a. The solution is a = 15°. However, by plotting the

function f(a) for some value of a (or by determining that its second deriva-

tive is negative), we can easily ﬁnd that the function attains its maximum at a

= 15°. Due to the periodicity of the rotation with the cycle of 30°, maxima of

f(a) are also obtained at a = (15 ± 30k)°, for any nonnegative integer k. Three

cycles (k = 0, 1, 2) are shown are Figure 2.4b for a = 4. We can see that the

minimum value of f(a) is attained at a = (0 ± 30k)°, which are values at which

the function is not differentiable. When a = 4, the minimum value of f(a) is

3.944 (Figure 2.4b), which is also the value of HL(E). For an arbitrary a,

Moreover, we have

HL E f a a a

()

=++ +

[]

013234

log .

-+ ∞-

()

=sin sin ,aa30 0

()

-+ ∞-

()

++ ∞-

()

sin sin

ln cos cos

21 30 3 4

faaaaaa

()

=+ + ∞-

()

[]

log cos cos .

13034

m Ea

()

=∞-

()

cos ,

cos .30

54 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

2.3. HARTLEY-LIKE MEASURE OF UNCERTAINTY FOR INFINITE SETS 55

Ex(a)

(a)

20 40 60 80

3.945

3.95

3.955

3.96

3.965

3.97

(b)

(a)

Figure 2.4. Calculation of HL(E ) in Example 2.8.

For a = 4, HL(E

) = 2.322 and HL(E

) = 2.158. Then,

NOTES

2.1. Possibility and necessity functions introduced in Section 2.1 are closely connected

with operators of possibility and necessity in classical modal logic [Chellas, 1980;

Hughes and Creswell, 1996]. To show this connection let Pos

(A) deﬁned by Eq.

(2.2) be interpreted for each A Œ P(X) as the truth value of the proposition “Given

evidence E, it is possible that the true alternative is in set A.” Then, according to

modal logic,

which is the counterpart of Eq. (2.3). Moreover, the following is a tautology in

modal logic: “Any proposition p is necessary iff its complement, p¯, is not possible.”

Its counterpart is Eq. (2.4).

2.2. Possibilistic measure of uncertainty was derived by Hartley [1928]. Its signiﬁcance

is discussed by Kolmogorov [1965]. Axiomatic treatment of the Hartley measure

and the proof of its uniqueness presented in Section 2.2 are due to Rényi [1970b].

The uniqueness of the Hartley measure was also proved under different axioms

(somewhat less intuitive) and in more complicated ways by the Hungarian

mathematician Erdös in 1946 and by the Russian mathematician Fadeev in 1957.

References to these historical publications are given in [Rényi, 1970b], including

a reference to his own original publication of the proof in 1959.

2.3. The Hartley-like measure, HL, was proposed in a paper by Klir and Yuan [1995b].

The proposed measure was proved in the paper to satisfy all essential require-

ments with one exception: the additivity for sets with unequal edges when n > 3

remained an open problem. It was posed in SIAM Review [38(2), 1996, p. 315] in

the following form:

Let A = [0,a

] ¥ ···¥ [0,a

] be a block of R

, and let A

be the block obtained

by rigid rotation t of A around the origin. For i = 1,2,...,n, let b

denote

the length of the projection of A

on the ith coordinate axis. Show that

Pos A or B Pos A Pos B

EEE

iff or

() () ()

HL E E HL E HL E

TEE HLE HLE HE

I E HL X Y HL E

NHL E HL E HL X Y

XY Y

YX X

HL X Y X Y

()

=¥

()

1 786

1 622

0 536

9 376

,.,

.. ,

296

0 704NI E I E HL X Y

HL HL

()

HL E a HL E a

()

[]

()

[]

log log .

1132and

56 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

The problem has come from an attempt to ﬁnd a measure for nonspeciﬁcity

of convex sets, which is a generalization of the Hartley measure for inﬁnite

sets. The requirement of additivity leads to the above mentioned inequality.

The problem was solved by Ramer and the solution was presented ﬁrst in a very

concise form in the SIAM Review [39(3), 1997, p.516–51]. Its more elaborate version

is covered in Ramer and Padet [2001]. A possibility of extending the applicability

of the Hartley-like measure to nonconvex sets and some other related issues are

also discussed in this paper.

EXERCISES

2.1. Repeat the calculations in Examples 2.1c and 2.2c under the assumption

that the possible states at the time t are: (i) {s

}; (ii) {s

}; (iii) {s

, s

}, (iv)

, s

2.2. Repeat Examples 2.1 and 2.2 for a system with three states, s

, s

whose state-transition relation R is deﬁned by the following matrix:

ab ab

== = =

’’ ’ ’

()

≥+

()

11 1 1

11 .

EXERCISES 57

110

101

010

= M

In addition, calculate the nonspeciﬁcity in predicting the state at time

t + k (k = 2, 3, 4).

2.3. Assume that the systems employed in the previous Exercises are used

for retrodiction (determining past states or sequences of states) rather

than prediction. Repeat, under this assumption, some of the calculations

done in the previous Exercises.

2.4. Repeat Example 2.3 for some other sets of projections deﬁned by you.

Some projections may be 3-dimensional.

2.5. Consider a system with three variables, x

, x

. The variables, whose

values are in the set {0, 1}, are constrained by a ternary relation R, which

is not known. It is only known that each of the three binary projections

is the full Cartesian product {0, 1}

. Determine the cylindric closure of

those projections and all its subsets that are consistent and complete with

respect to the projections. Then, calculate the amount of nonspeciﬁcity

in identifying the overall relation and the amount of information pro-

vided by the projections.

2.6. Consider a system with three variables, x

, x

, whose values are in the

set {0, 1}.The variables are constrained by the following ternary relation:

58 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

001

010

100

111

Calculate conditional nonspeciﬁcities and information transmissions, as

well as their normalized versions, for all pairs of variables and for all

two-block partitions of {x

, x

2.7. Assume that the following messages were received with some missing

information. Determine the nonspeciﬁcity and informativeness of each

of the messages.

(a) A number with 10 decimal digits was received, but k of the digits

were not readable (k Œ ⺞

(b) A coded message with six letters of the English alphabet was

received, but k of the letters were not readable (k Œ ⺞

2.8. Consider three variables that are related by the equation v = v

+ v

Values of v

and v

are integers from 0 to 100, values of v are integers

from 0 to 200. Given a particular value v, what is the nonspeciﬁcity in

determining the corresponding values of v

and v

, and what is the infor-

mativeness of v about v

and v

2.9. Consider the equation d = a + bc, where a, b, c are input variables whose

values are integers in the set {0, 1,...,9},andd is an output variable

with values in the set {0, 1,...,90}. Assume now that the values of the

input variables are not fully speciﬁc. We know only that a Œ {3, 4},

b Œ {1, 2, 3}, and c Œ {7, 8}. What are the input and output nonspeciﬁci-

ties in this case? What are the amounts of information contained in the

input and in the output?

2.10. Assume that 1000 attractive design alternatives are conceived by an

engineering designer. After applying requirements r

, r

(in that

order), the number of alternatives is reduced to 200, 100, 64, 12, 1 (in the

respective order). What are the prescriptive nonspeciﬁcities at the indi-

vidual stages of the design process, and what is the amount of prescrip-

tive information contained in each of the requirements?

2.11. To test a particular digital electronic chip with n inputs and m outputs

for correctness means to determine the actual logic function the chip

implements at each output solely by manipulating the input variables

and observing the output variables. Initially, there are possible logic

functions at each output and, hence, the diagnostic nonspeciﬁcity is 2

bits. To resolve this nonspeciﬁcity and determine that the implemented

function is the correct one, 2

tests must be conducted. If n is large, this

is not realistic. However, when less than 100% of the required tests have

been carried out, some diagnostic nonspeciﬁcity remains (unless a defect

in the chip was discovered by one of the tests). As an example, let n =

30 and m = 10, and assume that only 90% of the required tests have been

carried out and they are all positive. Calculate the information obtained

by the tests and the remaining diagnostic nonspeciﬁcity.

2.12. Consider the 2-dimensional Euclidean space ⺢

, and let the domain of

interest (the universal set) X ¥ Y be the square [0, 1000]

. This speciﬁ-

cation is expressed in some chosen units of length. Our aim is to deter-

mine the location of an object, which we know must be somewhere in

the square [0, 1000]

. From one information source, we know that the

object cannot be outside the square area A shown in Figure 2.5. From

another source, we know that it cannot be outside the circular area B

also shown in the ﬁgure. Calculate, assuming that a = 2 (in the chosen

units of length), the following:

(a) Basic and conditional nonspeciﬁcities of A, B, and A 艚 B;

(b) Normalized versions of these nonspeciﬁcities;

together and their normalized versions.

2.13. Assume that the chosen unit of length in Exercise 2.12 is a meter.Repeat

the calculations by expressing the same length in centimeters.

2.14. Repeat Example 2.8 for the following areas in ⺢

(a) A hexagon with sides equal to 1;

(b) An ellipse with semiaxes a = 2 and b = 1;

2.15. Consider the 3-dimensional Euclidean space ⺢

within which the domain

of interest, X ¥ Y ¥ Z, is the cube [0, 100]

. For the following convex

subsets of possible points in this domain, calculate the various basic and

conditional amounts of nonspeciﬁcity, and the associated information, as

well as values of relevant information transmissions:

(a) A unit cube;

(b) A sphere with radius r = 2;

(d) A regular tetrahedron with sides s = 2.

EXERCISES 59

2.16. In each of the following algebraic expressions, x and y are input vari-

ables whose values are in the interval [0, 10], and z is an output variable

whose range is determined by each of the expressions:

(a) z = x + y

(b) z = xy/(x + y)

(d) z = (x + y)

Assuming that the values of x and y are known only imprecisely,

x Œ [,x

] and y Œ [,y

], determine for each expression the input and

output nonspeciﬁcity and the input informativeness about the output.

Consider, for example, x Œ[1, 2] and y Œ [5, 7], or x Œ [0.1, 1] and

y Œ[0, 1].

2.17. Consider the set A

of all points on a straight-line segment in the 2-

dimensional Euclidean space whose length is l(l ≥ 0). Calculate the non-

speciﬁcity of A

60 2. CLASSICAL POSSIBILITY-BASED UNCERTAINTY THEORY

1000

X Y

A B

Figure 2.5. Illustration to Exercise 2.12.

CLASSICAL PROBABILITY-

BASED UNCERTAINTY

THEORY

Probability is degree of certainty and differs from absolute certainty as the part

differs from the whole.

—Jacques Bernoulli

3.1. PROBABILITY FUNCTIONS

Probability-based uncertainty theory, which is the subject of this chapter,

is one of the two classical theories of uncertainty. It is based on the notion

of probability, which, in turn, is based on the notion of classical (additive)

measure.The study of probability has a long history whose outcome is a theory

that is now well developed at each of the four fundamental levels (formaliza-

tion, calculus, measurement, and methodology). The literature on probability

theory, including textbooks at various levels, is abundant. Since probability

theory is also covered in most academic programs, it is reasonable to as-

sume that the reader is familiar with its fundamentals. Therefore, only a few

basic concepts from probability theory are brieﬂy reviewed in this section.

These are concepts that are needed for examining in greater depth the various

issues regarding the measurement of probabilistic uncertainty (Sections 3.2

and 3.3).

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