Computational Intelligence

Online Slides

October 29, 2002

These are slides from Computational Intelligence, A Logical Approach, Oxford University Press, 1998. Copyright ©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1999-2002. You may prefer the pdf interface for which these slides were designed (you can read pdf files using the free acrobat reader).

Chapter 7, Lecture 1


Equality


Equality doesn't mean similarity

chair1 != chair2
chair_on_right = chair2
chair_on_right is not similar to chair2, it is chair2.


Why is equality important?


Allowing Equality Assertions


Axiomatizing Equality

X=X.
X=Y <- Y=X.
X=Z <- X=Y & Y=Z.

For each n-ary function symbol f there is a rule of the form

f(X_1,...,X_n)=f(Y_1,..., Y_n) <-
     X_1=Y_1 & ··· & X_n=Y_n.

For each n-ary predicate symbol p, there is a rule of the form

p(X_1,...,X_n) <-
     p(Y_1,..., Y_n) & X_1=Y_1 & ··· & X_n=Y_n.


Special-Purpose Equality Reasoning

paramodulation: if you have t1=t2, then you can replace any occurrence of t1 by t2.

Treat equality as a rewrite rule, substituting equals for equals.

You select a canonical representation for each individual and rewrite all other representations into that representation.

Example: treat the sequence of digits as the canonical representation of the number.

Example: use the student number as the canonical representation for students.


Unique Names Assumption

The convention that different ground terms denote different individuals is the unique names assumption.

For every pair of distinct ground terms t1 and t2, assume t1 != t2, where " != " means "not equal to."

Example: For each pair of courses, you don't want to have to state, math302 != psyc303, ...

Example: Sometimes the unique names assumption is inappropriate, for example 3+7 != 2×5 is wrong.


Axiomatizing Inequality for the UNA


Top-down procedure and the UNA


Implementing the UNA


Inequality Example

notin(X,[]).
notin(X,[H|T]) <- X != H & notin(X,T).
good_course(C) <- course(C) & passes_analysis(C).
course(cs312).
course(cs444).
course(cs322).
passes_analysis(C) <- something_complicated(C).
? notin(C,[cs312,cs322,cs422,cs310,cs402])
      & good_course(C).



Chapter 7, Lecture 2


Complete Knowledge Assumption (CKA)


CKA: propositional case


CKA: Ground Database

Example: Consider the relation defined by:

student(mary).
student(john).
student(ying).

The CKA specifies these three are the only students:

student(X) <-> X=mary or X=john or X=ying.

To conclude ¬student(alan), you have to be able to prove
alan != mary & alan != john & alan != ying
This needs the unique names assumption.

Clark Normal Form

The Clark normal form of the clause:

p(t_1,...,t_k) <- B

is the clause

p(V_1,...,V_k) <-
      exist W_1...exist W_m V_1=t_1 & ... & V_k =t_k & B,

where V1,...,Vk are k different variables that did not appear in the original clause.

W1,...,Wm are the original variables in the clause.


Clark normal form: example


Clark's Completion of a Predicate

Put all of the clauses for p into Clark normal form, with the same set of introduced variables:

p(V_1,...,V_k) <- B_1
     ...
p(V_1,...,V_k) <- B_n

This is the same as: ~~ p(V1,...,Vk) <- B1 or ... or Bn.

Clark's completion of p is the equivalence

p(V_1,...,V_k) <-> B_1 or ... or B_n,

That is, p(V1,...,Vk) is true if and only if one Bi is true.

Clark's Completion Example

Given the mem function:

mem(X,[X|T]).
mem(X,[H|T]) <- mem(X,T).

the completion is

mem(X,Y) <-> (exist T Y=[X|T]) or
     (exist H exist T Y=[H|T] & mem(X,T))


Clark's Completion of a KB


Using negation as failure

Previously we couldn't define empty_course(C) from a database of enrolled(S,C).

This can be defined using negation as failure:

empty_course(C) <-
      course(C) &
      ~ has_Enrollment(C).
has_Enrollment(C) <-
     enrolled(S,C).


Bottom-up NAF proof procedure

C:={};
repeat
either select "h <- b1 & ... & bm" in KB such that
bi in C for all i, and h not in C;
C:=C union {h}
or select h such that
for every rule "h <- b1 & ... & bm" in KB
either for some bi, ~ bi in C
or some bi= ~ g and g in C
C:=C union { ~ h}
until no more selections are possible


Negation as failure example

p <- q & ~ r.
p <- s.
q <- ~ s.
r <- ~ t.
t.
s <- w.


Top-Down NAF Procedure


Free Variables in Negation as Failure

Example:

p(X) <- ~ q(X) & r(X).
q(a).
q(b).
r(a).
r(c).

There is only one answer to the query ?p(X), namely X=c.

For calls to negation as failure with free variables, you need to delay negation as failure goals that contain free variables until the variables become bound.


Floundering Goals

If the variables never become bound, a negated goal flounders.

In this case you can't conclude anything about the goal.

Example: Consider the clauses:

p(X) <- ~ q(X)
q(X) <- ~ r(X)
r(a)

and the query

?p(X).



Chapter 7, Lecture 3


Integrity Constraints


Horn clauses


Negative Conclusions


Disjunctive Conclusions


Questions and Answers in Horn KBs


Conflict Example

Example: If {c,d,e,f,g,h} are the assumables
KB={
false <- a & b.
a <- c.
b <- d.
b <- e.
}


Using Conflicts for Diagnosis


Electrical Environment


lit(L) <=light(L)&ok(L)&live(L).
live(W) <=connected_to(W,W_1)&live(W_1).
live(outside)<=true.
light(l_1)<=true.
light(l_2)<=true.
connected_to(l_1,w_0)<=true.
connected_to(w_0,w_1) <=up(s_2)&ok(s_2).
connected_to(w_1,w_3) <=up(s_1)&ok(s_1).
connected_to(w_3,w_5) <=ok(cb_1).
connected_to(w_5,outside)<=true.



Diagnoses


Meta-interpreter to find conflicts

dprove(G,D0,D1) is true if list D0 is an ending of list D1 such that assuming the elements of D1 lets you derive G.

dprove(true,D,D).
dprove((A&B),D_1,D_3) <-
     dprove(A,D_1,D_2) & dprove(B,D_2,D_3).
dprove(G,D,[G|D]) <- assumable(G).
dprove(H,D_1,D_2) <-
     (H<=B) & dprove(B,D_1,D_2).
conflict(C) <- dprove(false,[],C).


Example

false <=a.
a <=b &c.
b <=d.
b <=e.
c <=f.
c <=g.
e <=h &w.
e <=g.
w <=f.
assumable  d,f,g,h.


Bottom-up Conflict Finding


Bottom-up Conflict Finding Code

C:={<a,{a}>:a is assumable };
repeat
select clause "h <- b1 & ... & bm" in T such that
<bi,Ai> in C for all i and
there is no <h,A'> in C or <false,A'> in C
such that A' subset A where A=A1 union ... union Am;
C:=C union {<h,A>}
Remove any elements of C that can now be pruned;
until no more selections are possible


Integrity Constraints in Databases


©David Poole, Alan Mackworth, Randy Goebel and Oxford University Press, 1998-2002