Schlechta K. Nonmonotonic Logics: Basic Concepts, Results, and Techniques

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

~ t'~

r- ~ / F

~J\ y\

228

CHAPTER 6. STRUCTURED REASONING

Note, that if X E E, then all calculated values for X are "constants", or even

trivial. So, assume in the sequel X ~ E.

We recollect:

Fact 6.68 a) < A ] B I C > -~

P(a,c ] b) : P(a I b),P(c [ b)

for all a E HA,

b E IIB, c E IIC,

P(alb)

= E{[P(alb, c),P(cib)]:cEFie},

c) <

A,B ]l C,D > ---, P(a,c I b,d) = P(a ] b) * P(c i d)

['or all a E rid etc.,

d) E{P(x

[ y) : z E IIX} : 1,

e) < X I Y I Z > --+ P(x,y,z) : e(~'Y)**'(v'z] for all x 6 FIX etc.

P(y)

The proofs are all elementary. []

For notational simplicity, we will a!so write x E X for x E UX etc.

We now discuss the details of the distributed computation via message passing.

We picture a local computer associated with each node, and messages flowing

along arrows between the computers. We show two things: First, the compu-

tation is in a reasonable sense distributed (one might, of course, do the whole

computation at each location, but this clearly is not intended), i.e. the local

computations are much simpler than a global computation is. (This will be triv-

ial by inspection - in the general case.) Second, that the "right" messages are

passed. To be more precise, the messages are passed along a well-founded order,

and the information used for the computation of the message originates only from

eartier (by this order) poinb. This ensures that finally, depending on the distance

from the base elements, the correct messages are passed. Finally, we have to show

that the messages suffice for computing the problem

(P(x I e)

for all z E X E F).

Let U -~ X --+ Y be in r. We have messages

PCxy

from parent to child, and

CPc~x

from child to parent, both originating from X. We show:

P(z

] e) can be calculated from (constants and the correct)

{PCvx : V E

Gx} u {CPxz : Z e Cx}.

PCxv

can be calculated from (constants and the correct)

{PCvx : V E

a~} u {CP~z : Z

cx -

{v)).

CPcrx

can be calculated from (donstants and the correct)

{PCvx : V E

ax - {u}) u

{CPxz : z ~ cx}.

~{ere

PCxy :: {P(x r e~y) : x ~ X},

CPux

:= {P(e%

t x):x E X) U {P(x t U,@x N

e~): r E

X,u E U}.

6.2. NETWORKS OF INFERENCE- J. PEARL'S BOOK

229

Single connectedness and the conditions Z 5r I/, V ~r U ensure the well-order of

the information processing (E will be the set of the base elements in the induc-

tion).

Fact 6.69 a)

P(x

]e)

~ ,1 p(g leG) , p(gC t~ )

Proof Both elementary, using Fact 6.66, a) and Fact 6.68, e). []

Fact 6.70 a) Let G} (UO... o

U~o }, G} = (u~ ~

....

.... a~,}, a} {u? u~}.

ThenP(xle~c)

P, { P(x l u~.. 2 u o

o ul u I

p(u o) , .. ,P(uoo) ,

"lZn2, 1 "''~no~ 1 "'" nl) *

P(ul [ eb~x) * ... * P(u{~ l eba, x): 76 9 IIG~ 9 Ha) }.

b) If U E G}c, then

P(x I 12, e}x ~ e~) = P(x I e~)

(if u is compatible with e). If

U ~ G~o then without loss of generality U = U ~ and

P(x ] u, @x n e~c ) =

{P(*lq ~= 120 u~ 121 ~l),p(~0), ,p(~o0) ,

...... nO

7%1

n2, ~

.....

P(121 1

~b;~)

*.-.* P(~L 1%1~): 7 9

n(al. -

{U}),V 9 r~

If U 9 G~c, then without loss of generality U:= U~, and

P(x I u, @x ~ e~) =

{ P(X I u2 " " ' 122n2,7~10 ....... .Uno,t/{0 ?.Zlnl) * P(?AO) * *P(~/'~

~(~1 1 ~b~) *...* P(12L 1%~): 12~ 9 na~,~ --r 9 n(a~ - {u} }

c) Thus,

P(x l e~)

can be computed from

{PCvx : V ~ G~x}, P(z ] u,@x Near )

can be computed from

{PCvx : V 9 G~x -

{U}}.

(Note that the u~ are fixed, and in e.)

Proof a) By (essentially) Lemma 6.62,b) any ei beyond

can be neglected,

= s .- * 9 n2) = (bySb)

soP(z f~x ~) P(z

l evl x .e%x,~.. u 2

{P(x I e.U1X gUalX ,1.1,~,, 2 0 0 1 ,.ul

s ... s "?]"n2'Ul "''Uno'?'tl " nl) *

s ~ u ~ .- IIa~ f IIa}

1 I~vlx %1x,~1 ,,=). ~0 9 9 } =

Uno ~ 121 nl ) ~

9 . . 'U.n2 ~ ......

Pfu_ ~* *P(u )*P(~. e. ~* P(u e.

i X n|

: ~0 ~ Ha},~ c Ha} } =

U 1 X Un 1

9 7~n2 ~ ' nO ~ 'U'I ' " " nl ) * '"

P(,4 1 ~b:x)

*...* P(,4~ 1%x): 7~ e rta},~ 9 nc} }

(The last but one equation holds because of < X ] U~... Un ]

eb~x... @~x >,

and the independence of all U~-.)

For the proof of b), note that U has the same role as some U/2. c) is obvious from

the Definition. []

We turn towards calculating P(e)~ x).

Let C} = (r~

C} = {E ~ . rg~), C} = {h~...~/~).

230

CHAPTER 6. STRUCTURED REASONING

Lemma 6.71 Let F(z,Z):=

P(eC l z) 9 P(z ix, e}z Cl e~) * P(e~xz

f~ ezG). Then

a) P(~ I ~) = H { ~{F(~, z): z e Z}: Z e C~ } 9 ~ { F(~,Z): Z e C~ } (~ is

fixed in the second factor by e).

b) If Y E C}, then

P(eCx N e~xy I x) = P(eCx t x).

If Y E C), then P(e~ n

e~xr I x) = II { E{F(z,Z): z E

Z}: Z E C} - {Y} } *

r1 { F(~,Z): Z e C} }.

If Y r C}, then

P(e~

M e~(y [ x) = II { E{F(z,Z): z E Z}: Z E C} } *

n { F(~,Z): Z e C} - {Y} }.

c) F(z,Z) can be computed from

CPxz.

Thus,

P(e~: I x)

can be computed

from

{CPxz

: Z E C~:U C}} and P(e~ M e)z I x) can be computed from

{cPx~ :

z e (c}

- {Y})}

Proof a) By Facts 6.66, b) and 6.68, a)

IfY = y/l, then

P(e~xz,X) = E {P(e~xz,x,y): y E Y},

and

P(ey, exy n P(e~z I x) = r'{P(eC'edxYn~'x'Y):YeY}

If Y = <2, then

p(edxy,X) = P(e c,edxY f]

e~,x,y), so

P(edXy I z) =

c d G

P(~)

___' ,Y y' , __

Now, P(e~, e d, M e,~, x, y) = (by Fact 6.68, e) e(~g Y)*'(~ n~ ~ ~)

p(y)

P( ec I Y) * P(Y [ x, e~xy N el) 9 P(z,eexz a e~) =

P(~ I y) * P(y I =, ~ n #) 9 p(x)

9

P(edxy N e~) = P(z) 9 F(y, Y).

For b), note that Y has the same role as some y/0. c) is again obvious. []

To summarize, by Facts 6.69, 6.70, and Lemma 6.71,

P(x

I e) can be computed from

{PCvx: V E G~x}

(for

P(x

e)~)) and

{CPxz:

z E c.~ u cl.} (for P(~ I

x)),

PCxy

can be computed from

{PCvx

: V E a~,} (for

P(x

e~()) and

{CPxz :

Z E (C} U C} - {Y}} (for P(e:~ M e)z ] x)),

CPux

can be computed from

{CPxz

: Z E C} U C}} (for P(e:~ t x)) and

{PC.x: v e el- - {u}} (for P(~ 1 ~, e% n

<~)).

We repeat the following important facts:

1) The calculations have no "history", previous wrong results do not matter.

2) The calculation of some message to be passed to some area does not depend

on any information from that area: The calculation of the messages from X to

a parent U does not depend on

ebx,

and the messages from X to some child Y

does not depend on eJ~y.

3) It is easily seen, that after some time of calculations and message-passing the

correct data will arrive at all nodes X, depending on the distance from all E/E E.

The treatment of general DAGs (i.e. not necessarily singly connected) in Pearl

amounts to tricks of transforming such DAGs to polytrees, and the reader is

referred to [Pea88] for the discussion.

6.2. NETWORKS OF INFERENCE - J. PEARL'S BOOK

231

The "Best Explanation" In conclusion, we shortly treat Chapter 5 of

[Pea88]:

Let 12 be the set of all nodes in A, and e be as above. The problem discussed in

the Chapter 5 of [Pea88] is to compute the most probable "explanation" of e, i.e.

P(w* I e)

:= max

{P(w I

e): w E rip} (note that Y includes E). The cMculation

has many similarities with the one in Chapter 4 of [Pea88], and we note only the

first few (decisive new) steps.

Fix X E ]~, and assume X • E. Then

P(w [ e) = P(w~, w~,x I e) - P(~~

_- p(~) 9

Note that for Wt E F,

E/ E E, W/= Ei

and

wl • el

implies

P(w

] e) = 0. As

we are interested in the maximal

P(w I e),

we can assume that e and w coincide

wherever possible. Consequently,

P(w~v, w~, z, e) = P(w~, w~v, z).

As < W~ I

x lw,5 >,

P(w a,

Wx c, x) = p(,~,~).p(~,~c) =

P(w~, I-x) 9 P(w a, z).

Thus,

P(~)

P(w*le)

= P-~t .max{P(w~c

Iz)*P(w~,z):

w e,wx a,z E El))}.

Note that for any real-valued function h, and any finite A, B,

maz{h(a, b) : a E

A,b E B} = maz{maz{h(a,b): b E

B}: a E A} and for any sets of non-negative

reals A,B

maz{a * b: a E A, b E B) = (raazA) * (mazB).

Consequently,

ma• {P(*4 1 x) 9 P(w~,.):

wx,wx,~ ~ ~ E HV) =

and

P(w* I e) = ~; ~x{.,a~{P(,~

I *): ~ e nW~} *

ma~{P(w~,~):

~x ~ E

nW~?}: 9 e X)

The

P(w~v I ~)

play the role of the P(4 t z) in Chapter 4 of [Pea88J, the

P(w~,

that of the

P(z { e~)

in the further development in Chapter 5 of [Pea88].

Bibliography

[AGM85] C.Alchourron, P.Ggrdenfors, D.Makinson, "On the Logic of Theory

Change: Partial Meet Contraction and Revision Functions", Journal of

Symbolic Logic 50 (1985), p.510-530

JAM82] C.Alchourron, D.Makinson, "On the Logic of Theory Change: Con-

traction functions and their associated revision functions", Theoria 48

(1982), p.14-37

[Ada75] E.W.Adams, "The Logic of Conditionals", Dordrecht, 1975

[BB94] S.Ben-David, R.Ben-Etiahu, "A modal logic for subjective default rea-

soning", Proceedings LICS-94, 1994

[BH92] F.Baader, B.Hollunder, "Embedding defaults into terminological knowl-

edge representation formalisms", in Proceedings of the 3rd International

Conference on Knowledge Representation and Reasoning, Cambridge,

Mass., USA, 1992

[BHR90] K.H.Blgosius, U.Hedtstfick, C.-R.Rollinger (eds.), "Sorts and Types in

Artificial Intelligence", Springer, Berlin, 1990

[BMS91 1] G.Brewka, D.Makinson, K.Schlechta, "JTMS and Logic Program-

ming", "Proceedings International Workshop on Non-Monotonic Rea-

soning and Logic Programming", Washington, dull 1991

[BMS91-2] G.Brewka, D.Makinson, K.Schlechta, "Cumulative Inference Rela-

tions for JTMS and Logic Programming", in: "Nonmonotonic and In-

ductive Logic", J.Dix, K.P.Jantke, P.Schmitt eds., Springer Verlag 1991,

p.i-i2

[BS85]

G.Bossu, P.Siegel, :'Saturation, Nonmonotonic Reasoning and the

Closed-World Assumption", Artificial Intelligence 25 (1985) 13-63

[BS93] F.Baader, K.Schlechta, "A semantics for open normal defaults via a

modified preferential approach", Research Report RR-93-13, Deutsches

Forschungszentrum ffir Kfinstliche Intelligenz, Stuhlsatzenhausweg 3,

D-66123 Saarbrficken, Germany, 1993

234

BIBLIOGRAPHY

[Bar77]

[Bau74]

[Bel90]

[Bes89]

[Bir91]

[Bou90a]

[Boug0b]

[Bou92]

[Bre87]

[Bre91a]

[Bre91b]

[CK77]

[DUS90]

[Da~88]

[De187]

[Del88]

J.Barwise, "An introduction to first-order ?~ogic", in "Handbook of

Mathematical Logic", J.Barwise ed., North Holland, Amsterdam, t977,

p.5-46

H.Bauer, "Wahrscheinlichkeitstheorie", de'Gruyter, Berlin, 1974

&Bell, "The Logic of Nonmonotonicity', Artificial Intelligence 41

(1989/90), p.365-374

P.Besnard, "An Introduction to Default Logic", Springer, Berlin, 1989

L.Birnbaum, "Rigor mortis", Artificial Intelligence 47 (1991), p.57-77

C.Boutilier, "Conditional Logics of Normality as Modal Systems",

AAAI 1990, Boston, p.594

C.Boutilier, "Viewing Conditional Logics of Normality as Extensions of

the Modal System $4", Toronto University , KRR-TR-90-4, June 1990

C.Boutilier, "Conditional Logics for Default Reasoning and Belief Re-

vision", Dept. of Comp. Sc., Univ. Brit. Columbia TR 92-1, Vancouver,

Canada, Jan. 92,

G.Brewka, "Nonmonotonic Logics: An Introductory Overview", Ar-

beitspapiere der GMD, Gesellschaft f(ir Mathematik und Datenverar-

beitung, D-5205 Sankt Angustin, Germany, 1987

G.Brewka, "Cumulative Default Logic: In Defense of Nonmonotonic

Inference Rules", Artificial Intelligence 50 (1991), p.183-205

G.Brewka, "Nonmonotonic Reasoning: Logical Foundations of Com-

monsense", Cambridge University Press, 1991

C.C.Chang, H.a.Keisler, "Model Theory", North Holland, Amsterdam,

1977

J.Dix, R.Hghnle, P.H.Schmitt, "0ber die Negation im logischen Pro-

grammieren und ihre Beziehung zu ni'chtmonotonen Logiken: Tell 1",

Universitgt Karlsruhe, Institut f{ir L0gik, Komplexitgt und Deduktion-

ssysteme, D-7500 Karlsruhe, Germany, Interner Bericht 13/90, 1990

M.Dalal, "Investigations Into a Theory of Knowledge Base Revisions:

Preliminary Report", Proc. 7th Nat. Conf. AI, Minneapolis, p.475-479,

1988

J.P.Delgrande, "A First-Order Conditional Logic for Prototypical Prop-

erties", Artificial Intelligence 33 (1987), p.105-130

J.P.Delgrande, "An Approach to Default Reasoning Based on a First-

Order Conditional Logic: Revised Report", Artificial Intelligence a6

(1988), p.63-90

BIBLIOGRAPHY

235

[Doy79]

[Dre87]

[EG92]

[EG95]

[Elk90]

[Eng771

[Eth87a]

[Eth87b]

[FH95]

[F i9o]

[Fuvs3]

[Fre9a]

[GM88]

[GM91]

J.Doyle, "A Truth Maintenance System", Artificial Intelligence 12

(1979), p.231-272

O.Dressler,

"An

Extended Basic ATMS", Siemens, Munich, Germany,

Tech. Report INF2 ARM-3-87, also in: M.Reinfrank, J.de Kleer,

M.L.Ginsberg, E.Sandewall (eds.), "Non-Monotonic Reasoning", Pro-

ceedings 2nd Int. Workshop Grassau 1988, Springer, Berlin, 1989

T.Eiter, O.Gottlob, "On the complexity of propositional knowledge base

revision, updates and counterfactuals", Artificial Intelligence, 57:227-

270, 1992

T.Eiter, G.Gottlob, "The complexity of logic-based abduction", Journal

of the ACM, 42(1):3-42, January 1995

J.Elkan, "A rational reconstruction of nonmonotonic truth maintenance

systems", Artificial Intelligence 43 (1990), p.219-234.

R.Engelking, "General Topology", Warszawa, 1977

D.W.Etherington, "Relating Default Logic and Circumscription" Pro-

ceedings IJCAI 87, p.489-494

D.W.Etherington, "A Semantics for Default Logic" Proceedings IJCAI

87, p.495-498

N.Friedman, J.Halpern "Plausibility measures and default reasoning",

IBM Almaden Research Center, Technical Report, 1995

M.Freund, D.Lehmann, D.Makinson, "Canonical Extensions to the

Infinite Case of Finitary Nonmonotonic Inference Relations". In:

O.Brewka, H.Freitag (eds.), "Proceedings of the Workshop on Non-

monotonic Reasoning, GMD, 1989", Gesellschaft fflr Mathematik und

Datenverarbeitung, D-5205 Sankt Augustin, Germany, p.133-138

R.Fagin, J.D.Ullmann, M.Y.Vardi, "On the Semantics of Updates in

Databases", Proc. Second ACM SICACT-SIGMOD, 1983, p.352-365

M.Freund, "Supracompact Inference Operations", Studia Logica, 52

(1993), p.457-481

P.Ggrdenfors, D.Makinson, "Revisions of Knowledge Systems Using

Epistemic Entrenchment". In: M.Y.Vardi (ed.), "Theoretical Aspects

of Reasoning about Knowledge", Morgan Kaufmann, San Mateo, Cal.,

1988, p.83-95

P.Ggrdenfors, D.Makinson, "Nonmonotonic Inference Based on Expec-

tations", Artificial Intel!igence 65 (1994), p.197-245

236

BIBLIOGRAPHY

[GPP86]

[0v89]

[Gab85]

[Oar88]

loin8?]

[Gin891

[Goo55]

[Got92]

[Got95a]

[Got95b]

[HC84]

[ T88]

[HTT871

[HalS0]

[Ham701

M.Gelfond, H.Przymusinska, T.Przymusinski, "The extended closed

world assumption and its relationship to parallel circumscription",

Proc. ACM SIGACT-SIGMOD Symposium on Principles of Database

Systems, 1986, p.133-139

H.Geffner, T.Verma, "Inheritance = Chaining+Defeat", UCLA Techni-

cal Report CSD-890039, R-129-L, June 1989, also in: Proceed. Fourth

International Symposium on Methodologies for Intelligent Systems,

North Holland, 1989, p.411-418

D.M.Gabbay, "Theoretical foundations for non-monotonic reasoning in

expert systems". In: K.R.Apt (ed.), "Logics and Models of Concurrent

Systems", Springer, Berlin, 1985, p.439-457

P.Gfirdenfors, "Knowledge in Flux", MIT Press, Cambridge, Mass.,

USA, 1988

M.L.Ginsberg, "Readings in Nonmonotonic Reasoning", Morgan Kauf-

mann, San Mateo, 1987

M.Ginsberg, "A circumscriptive theorem prover", Artificial Intelligence

39 (1989), p.209-230

N.Goodman, "Fact, Fiction, and ForeCast":, Harvard Univ. Press, 1955

O.(]ottlob, "Complexity results for nonmonotonic logics", Journal of

Logic and Computation, 2(3):397-425, 1992

G.Gottlob, :'Translating Default Logic into Standard Autoepistemic

Logic", Journal of the ACM, 42(4):711-740, July 1995

G.Gottlob, "The Complexity of Default Reasoning under the Stationary

Fixed Point Semantics", Information and Computation, 121(1):81-92,

1995

G.E.Hughes, M.J.Cresswell, "A Companion to Modal Logic", Methuen,

London, 1984

J.F.Horty, R.H.Thomason, "Mixing Strict and Defensible Inheritance",

Proceedings AAAI 88, Morgan Kaufmann, San Marco, 1988, p.427-432

J.F.Horty, R.H.Thomason, D.S.Touretzky,. "A Sceptical Theory of In-

heritance in Nonmonotonic Semantic Networks", Dept. Comp. Sci.,

Carnegie Mellon Univ., CMU-CS-87-I75, October 1987 also in: Pro-

ceedings AAAI-87 (1987), p.358-363, or: Artificial Intelligence 42

>31 >348

P.Halmos, "Measure Theory", New York, 1950

C.L.Hamblin, "Fallacies", Methuen, London, 1970

BIBLIOGRAPHY

237

[Han69]

B.Hansson, "An analysis of some deontic logics", Nous 3, 373-398.

Reprinted in R.Hilpinen ed. "Deontic Logic: Introductory and System-

atic Readings". Reidel, Dordrecht, 1971, 121-147

[Imi87] T.Imielinski, "Results on Translating Defaults to Circumscription", Ar-

tificial Intelligence 32 (1987), p.13t-146

[Jec78] T.Jech, "Set Theory", Academic Press, New York, 1978

[KK89] T.Krishnaprasad, M.Kifer, "An Evidence-based Framework for a The-

ory of Inheritance", Proceed. IJCAI 89, p.1093-1098

[KKW89a] T.Krishnaprasad, M.Kifer, D.Warren, "On the Circumscriptive Se-

mantics of Inheritance Networks", Proceed. Fourth International Sym-

posium on Methodologies for Intelligent Systems, North Holland, 1989,

p.448-456

[KKW89b] T.Krishnaprasad, M.Kifer, D.Warren, "On the Declarative Semantics

of Inheritance Networks", Proceed. IJCAI 89, p.1098-1103

[KLM90]

S.Kraus, D.Lehmann, M.Magidor, "Nonmonotonic reasoning, prefer-

ential models and cumulative logics", Artificial Intelligence, 44 (1-2),

p.167-207, July 1990

[KM73] J-L. Krivine, K.McAloon, "Forcing and Generalized Quantifiers", An-

nals of Mathematical Logic 5 (1973), 199-255

[KM90]

H.Katsuno, A.O.Mendelzon, "On the Difference Between Updating a

Knowledge Base and Revising It", Univ. of Toronto Tech. Rept., KRR-

TR-90-6

[Kau84] M.Kaufmann, "Filter logics on w", Journal of Symbolic Logic, 49 (1),

1984, p.241-256

[KeiT0] H.J.Keisler, "Logic with the quantifier "there exist uncountably

many"", Annals of Mathematical Logic 1 (1970), 1-93

[Kei77]

H.J.Keisler, "Fundamentals of model theory", in "Handbook of Mathe-

matical Logic", J.Barwise ed., North Holland, Amsterdam, 1977, p.47-

104

[Ke175] J.L.Kelley, "General Topology", Springer, Berlin, 1975 (original edition

Princeton 1955)

[Ke178] J.S.Kelly, Arrow Impossibility Theorems, Academic Press, New York,

1978

[Kle86] J.de Kleer, "An Assumption-based TMS", Artificial Intelligence 28

(1986), p.127-162