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

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

The solution is clearly b = 0; when this value is substituted for b into Eq. (9.3),

we obtain the uniform probability p

= 1/6 for all i Œ ⺞

Now consider a biased die for which it is known that E(x) = 4.5. Equation

(9.4) assumes a different form

When solving this equation (by a suitable numerical method), we obtain

b =-0.37105. Substitution of this value for b into Eq. (9.3) yields the maximum

entropy probability distribution:

Our only knowledge about the random variable x in the examples discussed

is the knowledge of its expected value E(x). It is expressed by Eq. (9.1) as a

constraint on the set of relevant probability distributions. If E(x) were not

known, we would be totally ignorant about x, and the maximum entropy prin-

ciple would yield the uniform probability distribution (the only distribution

for which the entropy reaches its absolute maximum).The entropy of the prob-

ability distribution given by Eq. (9.3) is usually smaller than the entropy of the

uniform distribution, but it is the largest entropy from among all the entropies

of the probability distributions that conform to the given expected value E(x).

A generalization of the principle of maximum entropy is the principle of

minimum cross-entropy. It can be formulated as follows: given a prior proba-

bility distribution function p¢ on a ﬁnite set X and some relevant new evidence,

determine a new probability distribution function p that minimizes the cross-

entropy S

given by Eq. (3.56) subject to constraints c

, c

,...,c

, which repre-

sent the new evidence, as well as to the standard constraints of probability

theory.

New evidence reduces uncertainty. Hence, uncertainty expressed by p is, in

general, smaller than uncertainty expressed by p¢. The principle of minimum

cross-entropy helps us to determine how much smaller it should be. It allows

145

26 66

005

210

26 66

008

304

26 66

011

441

26 66

017

639

26 66

024

927

26 66

035

----++=

35 25 15 05 05 15 0

35 25 15 05 05 15

..... . .

.... . .

eeeee e

bbbb b b

372 9. METHODOLOGICAL ISSUES

us to reduce the uncertainty of p¢ by the smallest amount necessary to satisfy

the new evidence.That is, the posterior probability distribution function p esti-

mated by the principle has the largest uncertainty among all other probabil-

ity distribution functions that conform to the evidence.

9.3.2. Principle of Maximum Nonspeciﬁcity

When the principle of maximum uncertainty is applied within the classical pos-

sibility theory, where the only recognized type of uncertainty is nonspeciﬁcity,

it is reasonable to describe this restricted application of the principle by a more

descriptive name—a principle of maximum nonspeciﬁcity. This specialized

principle is formulated as an optimization problem in which the objective func-

tional is based on the Hartley measure (basic or conditional, Hartley-based

information transmission, etc.). Constraints in this optimization problem

consist of the axioms of classical possibility theory and any information per-

taining to possibilities of the considered alternatives.

According to the principle of maximum nonspeciﬁcity in classical possibil-

ity theory, any of the considered alternatives that do not contradict given evi-

dence should be considered possible.An important problem area, in which this

principle is crucial, is the identiﬁcation of n-dimensional relations from the

knowledge of some of their projections. It turns out that the solution obtained

by the principle of maximum nonspeciﬁcity in each of these identiﬁcation

problems is the cylindric closure of the given projections. Indeed, the cylindric

closure is the largest and, hence, the most nonspeciﬁc n-dimensional relation

that is consistent with the given projections. The signiﬁcance of this solution

is that it always contains the true but unknown overall relation.

A particular method for computing cylindric closure is described and illus-

trated in Examples 2.3 and 2.4. A more efﬁcient method is to simply join all

the given projections by the operation of relational join (introduced in Section

1.4) and, if relevant, eliminate inconsistent outcomes.This method is illustrated

in the following example.

EXAMPLE 9.6. Consider a possibilistic system with three 2-valued variables,

, x

, that is discussed in Example 2.4. The aim is to identify the unknown

ternary relation among the variables (a subset of the set of overall states listed

in Figure 9.4a) solely from the knowledge of some of its projections. It is

assumed that we know two of the binary projections speciﬁed in Figure 9.4b

or all of them. As is shown in Example 2.4, the identiﬁcation is not unique in

any of these cases.When applying the principle of maximum nonspeciﬁcity, we

obtain in each case the least speciﬁc ternary relation, which is the cylindric

closure of the given projections. The aim of this example is to show that an

efﬁcient way of determining the cylindric closure is to apply the operation of

relational join.

Assume that projections R

and R

are given. Taking their relational join

, as illustrated in Figure 9.4c, we readily obtain their cylindric closure

(compare with the same result in Example 2.4). In a similar way, we obtain the

9.3. PRINCIPLE OF MAXIMUM UNCERTAINTY 373

States x

0 0 0

0 0 1

0 1 1

1 0 0

States x

0 0 0

0 0 1

0 1 1

1 0 0

1 0 1

States x

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

0 0

0 1

1 0

0 0

0 1

1 1

0 0

0 1

1 0

(a)

(b)

0 0 0

11 1

0 0 0

11 1

R x

(c)

(d)

)

States

0 0 0 0

— 0 0 0 1

0 0 1 0

0 1 1 0

— 1 0 0 0

1 0 0 1

— 1 0 1 0

States

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

0 0 0

11 1

R x

0 0 0 0

1 1 1

R x

(e) ( f )

Figure 9.4. Computation of cylindric closures (Example 9.6).

374

cylindric closures for the other pairs of projections, as shown in Figure 9.4d

and 9.4e. Observe, however, that we need to use the inverse of one of the pro-

jections in these cases to be able to apply the relational join.The order in which

the join is performed is not signiﬁcant. When the relational join is applied to

all three binary projections, as shown in Figure 9.4f, the outcomes are quadru-

ples, in which one variable appears twice (variable x

in our case).Any quadru-

ple in which the two appearances of this variable have distinct values must be

excluded (they are shaded in the ﬁgure); such a quadruple indicates that the

triple obtained by the join R

is inconsistent with projection R

The idea of cylindric closure as the least speciﬁc identiﬁcation of an n-

dimensional relation from some of its projections is applicable to convex

subsets of n-dimensional Euclidean space as well. The main difference is that

there is a continuum of distinct projections in the latter case.

9.3.3. Principle of Maximum Uncertainty in GIT

In all uncertainty theories, except the two classical ones, two types of uncer-

tainty coexist, which are measured by the appropriately generalized Hartley

and Shannon functionals. To apply the principle of maximum uncertainty, we

can use one of these types of uncertainty or both of them. In addition, we can

also use the well-established aggregate of both types of uncertainty.This means

that we can formulate the principle of maximum uncertainty in terms of four

distinct optimization problems, which are distinguished from one another by

the following objective functionals:

(a) Generalized Hartley measure GH: Eq. (6.38).

(b) Generalized Shannon measure GS: Eq. (6.64).

: Eq. (6.61).

(d) Disaggregated measure of total uncertainty TU =·GH, GSÒ: Eq. (6.65).

(e) Alternative disaggregated measure of total uncertainty

TU =·S

- S,

SÒ: Eq. (6.75).

Which of the ﬁve optimization problems to choose depends a great deal on

the context of each application. However, a few general remarks regarding the

four options readily can be made. First, options (d) and (e) are clearly the most

expressive ones, but their relationship is not properly understood yet. The

utility of option (c) is somewhat questionable since functional S

is known to

be highly insensitive to changes in evidence. Of the two remaining options, (a)

seems to be conceptually more fundamental than (b); it is a generalization of

the principle of maximum nonspeciﬁcity discussed in Section 9.3.2. Moreover,

option (a) is computationally attractive due to the linearity of the generalized

Hartley measure.

None of the ﬁve optimization problems has been properly developed so far

in any of the nonstandard theories of uncertainty. The rest of this section is

thus devoted to illustrating the optimization problems by simple examples.

9.3. PRINCIPLE OF MAXIMUM UNCERTAINTY 375

EXAMPLE 9.7. To illustrate the principle of maximum nonspeciﬁcity in evi-

dence theory, let us consider a ﬁnite universal set X and three of its nonempty

subsets that are of interest to us: A, B, and A « B. Assume that the only evi-

dence on hand is expressed in terms of two numbers, a and b, that represent

the total beliefs focusing on A and B, respectively, (a, b Œ [0, 1]). Our aim is

to estimate the degree of support for A « B based on this evidence.

As a possible interpretation of this problem, let X be a set of diseases con-

sidered in an expert system designed for medical diagnosis in a special area

of medicine, and let A and B be sets of diseases that are supported for a par-

ticular patient by some diagnostic tests to degrees a and b, respectively. Using

this evidence, it is reasonable to estimate the degree of support for diseases in

A « B by using the principle of maximum nonspeciﬁcity. This principle is a

safeguard that does not allow us to produce an answer (diagnosis) that is more

speciﬁc than warranted by the evidence.

The use of the principle of maximum nonspeciﬁcity in our example leads

to the following optimization problem: Determine values m(X), m(A), m(B),

and m(A « B) for which the functional

reaches its maximum subject to the constraints

where a, b Œ [0, 1] are given numbers.

The constraints are represented in this case by three linear algebraic equa-

tions of four unknowns and, in addition, by the requirement that the unknowns

be nonnegative real numbers. The ﬁrst two equations represent our evidence,

the third equation and the inequalities represent general constraints of evi-

dence theory. The equations are consistent and independent. Hence, they

involve one degree of freedom. Selecting, for example, m(A « B) as the free

variable, we readily obtain

(9.5)

Since all the unknowns must be nonnegative, the ﬁrst two equations set the

upper bound of m(A « B), whereas the third equation speciﬁes its lower

bound; the bounds are

mA a mA B

mB b mA B

mX a b mA B

()

=- «

()

=- «

()

=--+ «

()

mA mA B a

mB mA B b

mX mA mB mA B

()

+«

()

+«

()

+«

()

() () ()

()

≥

0,,, ,

GH m m X X m A A m B B

mA B A B

()

log log log

log

222

376 9. METHODOLOGICAL ISSUES

(9.6)

Using Eqs. (9.5), the objective function now can be expressed solely in terms

of the free variable m(A « B). After a simple rearrangement of terms, we

obtain

Clearly, only the ﬁrst term in this expression can inﬂuence its value, so that we

can rewrite the expression as

(9.7)

where

and

are constant coefﬁcients. The solution to the optimization problem depends

only on the value of K

. Since A, B, and A « B are assumed to be nonempty

subsets of X, K

> 0. If K

< 1, then log

< 0 and we must minimize m(A «

B) to obtain the maximum of GH(m); hence, m(A « B) = max{0, a + b - 1}

due to Eq. (9.6). If K

> 1, then log

> 0, and we must maximize m(A « B);

hence, m(A « B) = min{a, b} as given by Eq. (9.6).When K = 1, log

= 0, and

GH(m) is independent of m(A « B);this implies that the solution is not unique

or, more precisely, that any value of m(A « B) in the range of Eq. (9.6) is a

solution to the optimization problem. The complete solution thus can be

expressed by the following equations:

The three types of solutions are illustrated visually in Figure 9.5 and given for

speciﬁc numerical values in Table 9.5.

EXAMPLE 9.8. The aim of this example is to illustrate an application of the

principle of maximum nonspeciﬁcity within the uncertainty theory based on

l-measures. Assume that marginal l-measures,

and

, are given, where

X = Y = {0, 1}, and we want to determine the unknown joint l-measure,

m,by

mA B

ab K

ab ab K

ab K

()

{}

{}{}

[]

{}

max ,

max , , min ,

min , .

01 1

when

KabXaAbB

2222

1=--

()

++log log log ,

XA B

◊«

◊

GH m m A B K K

()

=«

()

+log ,

21 2

GH m m A B X A B A B

ab X a A b B

()

=«

()

--+«

[]

+--

()

log log log log

log log log .

2222

222

max , min , .01ab mA B ab+-

{}

£«

()

{}

9.3. PRINCIPLE OF MAXIMUM UNCERTAINTY 377

using the principle of maximum nonspeciﬁcity. A simple notation to be used

in this example is introduced in Figure 9.6: values x

, x

, y

are given; values

a, b, c, d are to be determined. Observe that the given values must satisfy the

equations:

378 9. METHODOLOGICAL ISSUES

GH(m)

max GH(m)

< 1

m(A « B)

min{a, b}

max{0, a + b – 1}

GH(m)

0 1

max GH(m)

> 1

m(A « B)

min{a, b}

max{0, a + b – 1}

0 1

max GH(m)

= 1

m(A « B)

min{a, b}

max{0, a + b – 1}

Figure 9.5. Illustration of the three possible outcomes in Example 9.7.

The relationship between the joint and marginal measures is expressed by the

following equations:

To determine the solution set of nonnegative values for a, b, c, d, we need one

free variable. For example, choosing c as the free variable, we readily obtain

the following dependencies of the remaining variables on c:

a b ab x

c d cd x

a c cd y

b d bd y

++ =

9.3. PRINCIPLE OF MAXIMUM UNCERTAINTY 379

0 a b

1 c d

Y 0 1

(x)

(x, y)

Figure 9.6. Notation employed in Example 9.8.

Table 9.5. Examples of the Three Types of Possible Solutions Discussed in

Example 9.7

(a) Three Particular Examples

Example |X||A||B||A « B| ab GH[m(A « B)]

(i) 10 5 5 2 0.7 0.5 -0.322m(A « B) + 2.122

(ii) 10 5 4 2 0.8 0.6 1.497

(iii) 20 10 12 7 0.4 0.5 0.222m(A « B) + 3.553

(b) Solutions for Three Particular Examples Obtained by the Principle of

Maximum Nonspeciﬁcity

Example Type m(A « B) m(A) m(B) m(X)

(i) K

< 1 0.2 0.5 0.3 0.0

(ii) K

= 1 [0.4, 0.6] [0.2, 0.4] [0.0, 0.2] [0.0, 0.2]

(iii) K

> 1 0.4 0.0 0.1 0.5

Since it is required that a, b, c, d ≥ 0, we obtain the following range of accept-

able values of c:

(9.8)

Each value of c within this range deﬁnes a particular joint l-measure,

, that

is consistent with the given marginals. One way of determining the least spe-

ciﬁc of these measures is to search through the range of c by small increments

and calculate for each value of c the measure

, its Möbius representation,

and the value of the generalized Hartley measure. The measure with the

maximum value of the Hartley measure is then chosen. In a similar way, joint

l-measures that maximize functionals S

or GS can be determined.

To illustrate the procedure for some numerical values, let x

= 0.6, x

= 0.1,

= 0.4, and y

= 0.2. Then, clearly, l = 5, c Œ [0, 0.1], and

The maximum of the generalized Hartley measure is 0.573 and it is obtained

for c = 0.069.The least speciﬁc l-measure (the one for c = 0.069) and its Möbius

representation are shown in Table 9.6. Also shown in the table are measures

that maximize functionals S

(obtained for c = 0.039) and GS (obtained for

c = 0.036). All these measures represent lower probabilities (since l is posi-

tive). The corresponding upper probabilities can readily be calculated via the

duality relation.

The problem of identifying an unknown n-dimensional relation from

some of its projections by using the principle of maximum nonspeciﬁcity is

illustrated in Example 9.6 for relations formalized in classical possibility

theory. Two common methods for dealing with the problem are: (1) con-

structing the intersection of cylindric extensions of the given projections;

and (2) combining the given projection by the operation of relational join

0 067 1 333

..,

max , min , .0

cxy

££

{}

xccy

()

(from the third equation),

(from the second equation),

(from the first equation).

380 9. METHODOLOGICAL ISSUES

and, if relevant, excluding inconsistencies. Both methods can be easily gener-

alized to the theory of graded possibilities, as is illustrated in the following

example.

EXAMPLE 9.9. Consider a system with three variables,x

, x

, that is similar

to the one in Example 9.6.The set of all considered overall states of the system,

speciﬁed in Table 9.7a, is the same as in Example 9.6. Again, we want to iden-

tify the unknown ternary relation from its projections by using the principle

of maximum nonspeciﬁcity. The difference in this example is that the projec-

tions are fuzzy relations, which are deﬁned by their membership functions in

Table 9.7b. Since these projections provide us with partial information about

the overall relation, we can interpret them as basic possibility functions. As in

Example 9.6, the least speciﬁc overall relation that is consistent with the given

projections is the cylindric closure of the projections.The construction of cylin-

dric closures for fuzzy relations is discussed in Section 7.6.1. Applying this

construction to the projections in this example, we ﬁrst construct cylindric

extensions of the projections, ER

, ER

(as shown in Table 9.7c). Then,

we determine the cylindric closure by taking the standard intersection (based

on the minimum operator) of the cylindric extensions (shown in Table 9.7d).

Recall that the standard operation of intersection of fuzzy sets is the only cut-

worthy one. This means that each a-cut of the cylindric closure of some fuzzy

projections is a cylindric closure in the classical sense. An alternative, more

efﬁcient way of constructing cylindric closures of fuzzy projections is to use

the relational join introduced in Section 7.5.2 (Eq. (7.34)).

9.3. PRINCIPLE OF MAXIMUM UNCERTAINTY 381

Table 9.6. Resulting l-measures in Example 9.8

X ¥ Y max GH max S

max GS

00 01 01 11

m(A) m(A)

A:00000.000 0.000 0.000 0.000 0.000 0.000

10000.246 0.246 0.302 0.302 0.309 0.309

01001.159 1.159 0.119 0.119 0.115 0.115

00100.069 0.069 0.039 0.039 0.036 0.036

00010.023 0.023 0.051 0.051 0.054 0.054

11000.600 0.195 0.600 0.179 0.600 0.177

10100.400 0.085 0.400 0.059 0.400 0.056

10010.298 0.028 0.430 0.077 0.446 0.084

01100.282 0.055 0.181 0.023 0.171 0.021

01010.200 0.018 0.200 0.030 0.200 0.031

00110.100 0.008 0.100 0.010 0.100 0.010

11100.876 0.067 0.756 0.035 0.744 0.032

11010.692 0.023 0.804 0.046 0.817 0.048

10110.469 0.010 0.553 0.015 0.563 0.015

01110.338 0.006 0.278 0.006 0.272 0.006

11111.000 0.008 1.000 0.009 1.000 0.009