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

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

Observe that Eq. (9.23) may be rewritten as

Since S

AŒP(X)

Bel(A), Nec(⭋), and Nec(X) are constants, minimizing D

Bel

equivalent to maximizing the expression

(9.24)

over all necessity functions Nec that satisfy Eq. (9.21).

EXAMPLE 9.18. Considering again the belief function deﬁned in Table 9.11,

let Nec

denote a necessity function that satisﬁes Eq. (9.21) and maximizes the

expression (9.24). To satisfy Eq. (9.21) in this case means that Nec

({a}) = 0.3,

Nec

({a, b, c}) = 0.8, and Nec

(X) = 1. Due to the nested structure of focal

subsets in possibility theory, Nec

({b, c}) = 0 and either Nec

({a, b}) = 0.3 and

Nec

({a, c}) Œ [0.3, 0.4] or Nec

({a, b}) Œ [0.3, 0.4] and Nec

({a, c}) = 0.3. The

maximum of expression (9.24) is clearly obtained for either Nec

({a, c}) = 0.4

and Nec

({a, b}) = 0.3 or Nec

({a, b}) = 0.4 and Nec

({a, c}) = 0.3. There are thus

two minima of D

Bel

in this case; the second one is shown in Table 9.11.

9.5.4. Transformations Between l-Measures and Possibility Measures

A common property of l-measures and possibility measures is that they are

fully represented by their values on singletons. It is thus reasonable to con-

sider uncertainty–invariant transformations between l-measures and possi-

bility measures by connecting the associated values on singletons via scales of

some type.

Considering a universal set X with n elements, let

denote an ordered possibility proﬁle on X with r

≥ r

i+1

for all i Œ ⺞

n-1

, and let

denote the associated proﬁle of a l-measure on X with l < 0 (i.e., the

l-measure represents an upper probability function) and

≥

i+1

for all

i Œ ⺞

n-1

. Then, components of r and

m can be connected by scales of some

type.

As an illustration of these transformations, let us examine transformations

from

m to r under log-interval scales and under the requirement

(9.25)

GS GH

()

r .

mm =· Œ Ò

i ⺞

r =· Œ Òri

⺞

Nec A

AX X

()

-∆

{}

P ,

D Nec Bel A Nec A

Bel

AXAX

()

ÂÂ

402 9. METHODOLOGICAL ISSUES

In this framework,

(9.26)

for all i Œ ⺞

. These equations are derived in a way similar to Eq. (9.12) for

transformations from probabilities to possibilities. Equation (9.25) assumes

the form

(9.27)

where GS(

m) and

for all i Œ ⺞

are given and the scaling parameter a is to

be determined. Once the value of a is determined, components of r are cal-

culated by Eq. (9.26).

EXAMPLE 9.19. Let

m =·0.576, 0.35, 0.32, 0.1Ò. Then, l =-0.625 and the l-

measure, which represents an upper probability function, is fully determined

by the l-rule. For this l-measure, we obtain S

(

m) = 1.890, GH(

m) = 0.329, and

GS(

m) = 1.561 (Exercise 9.19). Equation (9.27) has the form

The solution is a = 0.333. Substituting this value into Eq. (9.26), we readily

obtain

Clearly, S

(r) = 2, GH(r) = 1.560 (the small difference from GS(

m) at the third

decimal place is due to rounding errors), and GS(r) = 0.440.

The associated pairs of l-measures and possibility measures, whose proﬁles

are connected via log-interval scales and satisfy Eq. (9.25), may be viewed as

complementary representations of uncertainty. While the l-measure in each

pair represents uncertainty primarily in terms of GS, the associated possibil-

ity measure represents it primarily in terms of GH.

The inverse transformations, from possibility measures to l-measures, are

more difﬁcult, primarily due to the difﬁculty of formulating Eq. (9.25). They

require further research.

9.5.5. Approximations of Graded Possibilities by Crisp Possibilities

Interesting applications of the principle of uncertainty invariance are approx-

imations of graded possibilities by crisp possibilities.These approximations are

r =· Ò1 0 847 0 822 0 558,. ,. ,. .

1 561

035

0 576

032

0 576

aaa

()

log ,

9.5. PRINCIPLE OF UNCERTAINTY INVARIANCE 403

especially useful when graded possibilities are interpreted in terms of fuzzy

sets.Approximating fuzzy sets that result from approximate reasoning by crisp

sets is often desirable, since the latter are easier to comprehend. A crisp

approximation of a fuzzy set also can be utilized as an intermediary step in its

defuzziﬁcation.

Recall that each basic function r of graded possibilities on X is associated

with a family of basic functions of crisp possibilities, {

r | a Œ (0, 1]}, where

for all x ŒX. In general, any function in this family may be taken as a crisp

approximation of r. However, according to the principle of uncertainty invari-

ance, we should take the one for which the amount of nonspeciﬁcity is the

same as for r. When X is ﬁnite, this requirement is expressed by the equation

(9.28)

where |

r| denotes the number of possible alternatives according to function

r. When X is inﬁnite, the requirement is expressed by the alternative

equation

(9.29)

where UL is deﬁned by Eq. (6.26).

EXAMPLE 9.20. To illustrate the application of Eq. (9.28), consider function

r deﬁned in Figure 6.1, whose nonspeciﬁcity is 2.99 (according to the calcula-

tion in Example 6.1). Hence, Eq. (9.28) has the form

and we need to solve it for

r. Values of log

r| for all values a that are dis-

tinguished in this example are shown in Table 9.12. We can see that none of

the values is exactly equal to 2.99 (due to discreteness of function r) and there

are two of them that are equally close to 2.99 (for a = 0.6 and 0.7) which are

indicated in Table 9.12 in boldface.

EXAMPLE 9.21. To illustrate the application of Eq. (9.29), ﬁrst consider the

case of X = ⺢. Let

299

. log=

UL r d UL r

()

log log ,

ard r

()

≥

when

otherwise

404 9. METHODOLOGICAL ISSUES

be a given possibility proﬁle whose graph is shown in Figure 9.11. Then,

and

UL r d d

aaa

()

ÚÚ

1 546

log

aar =-

[]

,4 2

()

[

)

[

)

()

[]

()

112

22 24

when

otherwise

9.5. PRINCIPLE OF UNCERTAINTY INVARIANCE 405

0.5 1 1.5 2 2.5 3 3.5 4

0.2

0.4

0.6

0.8

Figure 9.11. Possibility proﬁle in Example 9.22.

Table 9.12. Illustration to Example 9.21

a |

r| log

0.1 15 3.91

0.3 12 3.59

0.4 11 3.46

0.6 9 3.17

0.7 7 2.81

0.9 5 2.32

1.0 3 1.58

Hence, Eq. (9.29) has the form

and its solution is a = 0.481. The crisp approximation of r is thus the closed

interval

EXAMPLE 9.22. This example illustrates the application of Eq. (9.29) when

r is deﬁned on ⺢

. Let

be a given 2-dimensional possibility proﬁle whose graph is shown in Figure

9.12a. Clearly

r deﬁnes points in a circle whose radius depends on a. Projec-

tions of r are functions

Their graphs, which are identical, are shown in Figure 9.12b. From r

(as well

as r

), we can readily conclude that for each a Œ (0, 1] the radius of the circle

representing points of

r is . We can also infer that

Using all these facts, we have

and

Hence, Eq. (9.29) assumes the form

1 796 1 4

. log ,=+

UL r d

()

1 796..

UL r

()

log

==-

12-

()

rx x

ry y

()

{}

()

{}

max ,

max , .

01 2

rxy x y, max ,

()

=-+

(){}

01 2

0 481 4 2 0 481 0 694 2 613., . .,. .-

[]

1 546 5 3

. log ,=-

()

406 9. METHODOLOGICAL ISSUES

9.5. PRINCIPLE OF UNCERTAINTY INVARIANCE 407

0.5

–1

–0.5

0.5

0.25

0.5

0.75

–1

–0.5

0.5

(

–1 –0.5 0 0.5 1

0.2

0.4

0.6

0.8

(b)

Figure 9.12. Illustration to Example 9.22.

and its solution is a = 0.585. Crisp approximation of r is thus obtained for a =

0.585. This is the set of all points in the circle whose radius is

and whose center is in the origin of the coordinate

system.

NOTES

9.1. Thus far, the principle of minimum uncertainty has been employed predominantly

within the domain of probability theory, where the function to be minimized is the

Shannon entropy (usually some of its conditional forms) or another function based

on it (information transmission, directed divergence, etc.). The great utility of this

principle in dealing with a broad spectrum of problems is perhaps best demon-

strated by the work of Christensen [1980–81, 1985, 1986]. Another important user

of the principle of minimum entropy is Watanabe [1981, 1985], who has repeatedly

argued that entropy minimization is a fundamental methodological tool in the

problem area of pattern recognition. Outside probability theory, the principle of

minimum uncertainty has been explored in reconstructability analysis of possi-

bilistic systems [Cavallo and Klir, 1982b; Klir, 1985, 1990b; Klir et al., 1986, Klir

and Way, 1985; Mariano, 1997]; the function that is minimized in these explorations

is the U-uncertainty or an appropriate function based on it [Higashi and Klir,

1983b]. The use of the principle of minimum uncertainty for resolving local incon-

sistencies in systems was investigated for probabilistic and possibilistic systems by

Mariano [1985, 1987].

9.2. The principle of maximum entropy was founded,presumably, by Jaynes in the early

1950s [Rosenkrantz, 1983]. Perhaps the greatest skill in using this principle in a

broad spectrum of applications has been demonstrated by Christensen [1980–81,

1985, 1986], Jaynes [1979, 2003], Kapur [1989, 1994, 1994/1996], and Tribus [1969].

The literature concerned with this principle is extensive. The following are a few

relevant books of special signiﬁcance: Batten [1983], Buck and Macaulay [1991],

Kapur and Kesavan [1987, 1992], Karmeshu [2003], Levine and Tribus [1979],Theil

[1967], Theil and Fiebig [1984], Webber [1979], Wilson [1970]. A rich literature

resource regarding research on the principle of maximum entropy, both basic

and applied, are edited volumes Annual Workshops on Maximum Entropy and

Bayesian Methods that have been published since the 1980s by several publishers,

among them Kluwer, Cambridge University Press, and Reidel.

9.3. The principle of maximum entropy has been justiﬁed by at least three distinct

arguments:

1. The maximum entropy probability distribution is the only unbiased distribu-

tion, that is, the distribution that takes into account all available information

but no additional (unsupported) information (bias). This follows directly from

the facts that

a. All available information (but nothing else) is required to form the con-

straints of the optimization problem, and

b. The chosen probability distribution is required to be the one that represents

the maximum uncertainty (entropy) within the constrained set of probabil-

ity distributions. Indeed, any reduction of uncertainty is an equal gain of

1 0 585 2

0 456

()

408 9. METHODOLOGICAL ISSUES

information. Hence, a reduction of uncertainty from its maximum value,

which would occur when any distribution other than the one with maximum

entropy were chosen would mean that some information from outside the

available evidence was unwittingly added.

This argument of justifying the maximum entropy principle is covered in the

literature quite extensively. Perhaps its best and most thorough presentation

is given in a paper by Jaynes [1979], which also contains an excellent histo-

rical survey of related developments in probability theory, and in a book by

Christensen [1980–81, Vol. 1].

2. It was shown by Jaynes [1968], strictly on combinatorial grounds, that the

maximum probability distribution is the most likely distribution in any given

situation.

3. It was demonstrated by Shore and Johnson [1980] that the principle of

maximum entropy can be deductively derived from the following consistency

axioms for inductive (or ampliative) reasoning:

Axiom (ME1) Uniqueness. The result should be unique.

Axiom (ME2) Invariance. The choice of coordinate system (permutation of vari-

ables) should not matter.

Axiom (ME3) System Independence. It should not matter whether one accounts

for independent systems separately in terms of marginal probabilities or together

in terms of joint probabilities.

Axiom (ME4) Subset Independence. It should not matter whether one treats an

independent subset of system states in terms of separate conditional probabilities

or together in terms of joint probabilities.

The rationale for choosing these axioms is expressed by Shore and Johnson

[1980] as follows: Any acceptable method of inference must be such that different

ways of using it to take the same information into account lead to consistent

results. Using the axioms, they derive the following proposition: Given some infor-

mation in terms of constraints regarding the probabilities to be estimated, there

is only one probability distribution satisfying the constraints that can be chosen

by a method that satisﬁes the consistency axioms; this unique distribution can be

attained by maximizing the Shannon entropy (or any other function that has

exactly the same maxima as the entropy) subject to the given constraints. Alter-

native derivations of the principle of maximum entropy were demonstrated by

Smith [1974], Avgers [1983], and Paris and Vencovská [1990].

The principle of minimum cross-entropy can be justiﬁed by similar arguments.

In fact, Shore and Johnson [1981] derived both principles and showed that the

principle of maximum entropy is a special case of the principle of minimum cross-

entropy. The latter principle is further examined by Williams [1980], who shows

that it generalizes the well-known Bayesian rule of conditionalization. A broader

range of applications of the principle of minimum cross-entropy was developed

by Rubinstein and Kroese [2004].

In general, the principles of maximum entropy and minimum cross-entropy as

well as the various principles of uncertainty that extend beyond probability theory

are tools for dealing with a broad class of problems referred to as inverse prob-

lems or ill-posed problems [McLaughlin, 1984; Tarantola, 1987]. A common char-

acteristic of these problems is that they are underdetermined and, consequently,

NOTES 409

do not have unique solutions. The various maximum uncertainty principles allow

us to obtain unique solutions to underdetermined problems by injecting uncer-

tainty of some type to each solution to reﬂect the lack of information in the for-

mulation of the problem.

As argued by Bordley [1983], the assumption that “the behavior of nature can

be described in such a way as to be consistent” (so-called consistency premise) is

essential for science to be possible. This assumption, when formulated in a partic-

ular context in terms of appropriate consistency axioms, leads to an optimization

principle. According to Bordley, the various optimization principles, which are

exempliﬁed by the principles of maximum entropy and minimum cross-entropy,

are central to science.

9.4. The principle of maximum nonspeciﬁcity was ﬁrst conceived by Dubois and Prade

[1987b], who also demonstrated its signiﬁcance in approximate reasoning based

on possibility theory [Dubois and Prade, 1991]. Applications of the principle were

developed in the area of image processing by Wierman [1994] and in the area of

fuzzy control by Padet [1996].

9.5. The principle of uncertainty invariance was introduced in the context of proba-

bility–possibility transformations by Klir [1989b, 1990a]. These transformations

were mathematically investigated by Geer and Klir [1992] and Harmanec and

Klir [1997] for the discrete case, and by Wonneberger [1994] for the continuous

case of n dimensions. It follows from the work of Geer and Klir [1992] that the

existence of transformations based on the principle of uncertainty invariance

expressed by Eq. (9.11) is not guaranteed under interval scales, but it is guaran-

teed under log-interval scales. Probability–possibility transformations were also

investigated experimentally (by a series of simulation experiments) and compared

with other probability–possibility transformations in terms of several criteria [Klir

and Parviz, 1992]. Approximations of belief measures by necessity measures by

preserving S

were studied by Harmanec and Klir [1997].

9.6. The material presented in Section 9.5.3 is based on a paper by Harmanec and Klir

[1997]. Many details presented in the paper are omitted in Section 9.5.3, in par-

ticular proofs of theorems and an efﬁcient algorithm to facilitate relevant

computations.

9.7. One methodological area that exempliﬁes the utility of the principles of uncer-

tainty discussed in this chapter is known in the literature as reconstructability

analysis (RA). The purpose of RA is to deal in information–theoretic terms with

two broad classes of problems that are associated with the relationship between

overall systems and their various subsystems: identiﬁcation problems and recon-

struction problems. In identiﬁcation problems, a set of subsystems is given and the

aim is to make meaningful inference about the associated overall system from

information in the subsystems and, possibly, some additional background infor-

mation. This may involve the use of the principle of minimum uncertainty to

resolve local inconsistencies among the given subsystems, the use of the principle

of maximum uncertainty to identify one particular overall system that is formal-

ized within the same theory as the subsystems, or the use of the principle of req-

uisite generalization by identifying the family of all overall systems that are

consistent with the given information, and moving thus to a more general theory

that is capable of representing this family. In reconstruction problems, an overall

system is given and the aim is to investigate, in a systematic way, which sets of sub-

410

9. METHODOLOGICAL ISSUES

systems at each complexity level preserve most of the information contained in

the overall systems. This requires determining how accurately the overall system

can be reconstructed from each considered sets of subsystems.

Reconstruction problems and identiﬁcation problems of RA were ﬁrst recog-

nized in terms of n-dimensional relations (i.e., within the classical possibility

theory) by Ashby [1964] and Madden and Ashby [1972], respectively. They were

further investigated within probability theory by Klir [1976, 1985, 1986a,b, 1990b],

Broekstra [1976 –77], Cavallo and Klir [1979, 1981, 1982a], Jones [1982, 1985, 1986],

and Conant [1988], and within the theory of graded possibilities by Cavallo and

Klir [1982b], Higashi et al. [1984], and Klir et al. [1986].

The few references on RA given in the previous paragraph cover only some of

the early, historically signiﬁcant contributions to RA. The literature on RA is now

too extensive to be covered here more completely. However, RA is a broad and

important application area of GIT and, therefore, it is appropriate to refer at least

to key sources of further information on RA:

•

Overview articles of RA: [Klir and Way, 1985; Pittarelli, 1990; Zwick, 2004].

•

Special Issues on RA:

—International Journal of General Systems, 7(1), 1981, pp. 1–107;

—International Journal of General Systems, 29(3), 2000, pp. 357–495;

—Kybernetes, 33(5–6), 2004, pp. 873–1062.

•

Bibliographies of RA: International Journal of General Systems, 7(1), 1981;

24(1–2), 1996.

EXERCISES

9.1. Consider the relation deﬁned in Table 2.2 and assume that variables x

are input variables and variable x

is an output variable. Using the

principle of minimum uncertainty, determine which of the three input

variables can be excluded to lose the least amount of information.

9.2. Consider the probabilistic systems in Table 3.3 and assume in each case

that x and y are input variables and z is an output variable. Using the

principle of minimum uncertainty, determine which of the two input

variables is preferable to exclude in each case.

9.3. Consider the joint possibility proﬁle in Figure 5.5a and assume that X

and Y are states of an input variable and an output variable, respectively.

Using the principle of minimum uncertainty, determine the best quanti-

zation of the input variable with:

(a) Four quantized states;

(b) Three quantized states.

9.4. Let a ﬁnite set of states contains n states, where n ≥ 2. How many mean-

ingful quantizations exist for each n = 2,3,...,10,provided that:

(a) The states are totally ordered;

(b) The states are not ordered.

EXERCISES 411