text: # 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
  
  • Sometimes two terms denote the same individual.
  • Example: Clark Kent & superman. 4×4 & 11+5.
  The projector we used last Friday & this projector.
  • Ground term t1 equals ground term t2, written t1=t2, is true in interpretation I if t1 and t2 denote the same individual in interpretation I.
  
  ## 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?
  
  • In a doctor's office, the doctor wants to know if a patient is the same patient that she saw last week (or is his twin sister).
  • In a criminal investigation, the police want to determine if someone is the same person as the person who committed some crime.
  • When buying a replacement switch, an electrician may want to know if it was built in the same factory as the switches that were unreliable. (And if it is a different switch to the one that was replaced the previous time).
  
  ## Allowing Equality Assertions
  
  • Without equality assertions, the only thing that is equal to a ground term is itself.
  
  This can be captured as though you had the assertion X=X. Explicit equality never needs to be used.
  
  • If you allow equality assertions, you need to derive what follows from them. Either:
  • axiomatize equality like any other predicate
  • build special-purpose inference machinery for equality
  
  ## 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
  
  • c != c' for any distinct constants c and c'.
  • f(X1,...,Xn) != g(Y1,...,Ym) for any distinct function symbols f and g.
  • f(X1,...,Xn) != f(Y1,...,Yn) <- Xi != Yi, for any function symbol f. There are n instances of this schema for every n-ary function symbol f (one for each i such that 1 <= i <= n).
  • f(X1,...,Xn) != c for any function symbol f and constant c.
  • t != X for any term t in which X appears (where t is not the term X).
  
  ## Top-down procedure and the UNA
  
  • Inequality isn't just another predicate. There are infinitely many answers to X != f(Y).
  • If you have a subgoal t1 != t2, for terms t1 and t2 there are three cases:
  • t1 and t2 don't unify. In this case, t1 != t2 succeeds.
  • t1 and t2 are identical including having the same variables in the same positions. Here t1 != t2 fails.
  • Otherwise, there are instances of t1 != t2 that succeed and instances of t1 != t2 that fail.
  
  ## Implementing the UNA
  
  • Recall: in SLD resolution you can select any subgoal in the body of an answer clause to solve next.
  • Idea: only select inequality when it will either succeed or fail, otherwise select another subgoal. Thus you are delaying inequality goals.
  • If only inequality subgoals remain, and none fail, the query succeeds.
  
  ## 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)
  
  • Sometimes you want to assume that a database of facts is complete. Any fact not listed is false.
  • Example: Assuming a database of enrolled(S,C) relations is complete, you can define empty_course(C).
  • The definite clause RRS is monotonic: adding clauses doesn't invalidate a previous conclusion.
  • With the complete knowledge assumption, the system is nonmonotonic: a conclusion can be invalidated by adding more clauses.
  
  ## CKA: propositional case
  
  • Suppose the rules for atom a are
   a <- b1. ... a <- bn.
  or equivalently: a <- b1 or ... or bn
  • Under the CKA, if a is true, one of the bi must be true:
  
  a -> b_1 or ... or b_n.
  
  • Under the CKA, the clauses for a mean Clark's completion:
  
  a <-> b_1 or ... or b_n
  
  ## 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
  
  • The Clark normal form of:
  
  room(C,room208) <-
  cs_course(C) & enrollment(C,E) & E<120.
  
  is
  
  room(X,Y) <- exist C exist E X=C & Y=room208 &
  cs_course(C) & enrollment(C,E) & E<120.
  
  ## 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
  
  • Clark's completion of a knowledge base consists of the completion of every predicate symbol, along with the axioms for equality and inequality.
  • If you have a predicate p defined by no clauses in the knowledge base, the completion is p <-> false. That is, ¬p.
  • You can interpret negations in the bodies of clauses. `~` p means that p is false under the Complete Knowledge Assumption. This is called negation as failure.
  
  ## 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
  
  • If the proof for a fails, you can conclude `~` a.
  • Failure and success can be defined recursively:
  • Suppose you have rules for atom a:
   a <- b1 ... a <- bn
  If each body bi fails, a fails.
  If one body, bi succeeds, a succeeds.
  • A body fails if one of the conjuncts in the body fails.
  A body succeeds if all of the conjuncts succeed.
  • If a fails, `~` a succeeds. If a succeeds `~` a fails.
  
  ## 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
  
  • In the electrical domain, what if we predict that a light should be on, but observe that it isn't?
  What can we conclude?
  • We will expand the definite clause language to include integrity constraints which are rules that imply false, where false is an atom that is false in all interpretations.
  • This will allow us to make conclusions from a contradiction.
  • A definite clause knowledge base is always consistent. This won't be true with the rules that imply false.
  
  ## Horn clauses
  
  • An integrity constraint is a clause of the form
  
  false <- a_1 & ... & a_k
  
  where the ai are atoms and false is a special atom that is false in all interpretations.
  • A Horn clause is either a definite clause or an integrity constraint.
  
  ## Negative Conclusions
  
  • Negations can follow from a Horn clause KB.
  • The negation of alpha, written ¬alpha is a formula that
  • is true in interpretation I if alpha is false in I, and
  • is false in interpretation I if alpha is true in I.
  • Example:
  KB={ false <- a & b. a <- c. b <- c.
  } KB ¬c.
  
  ## Disjunctive Conclusions
  
  • Disjunctions can follow from a Horn clause KB.
  • The disjunction of alpha and beta, written alpha or beta, is
  • true in interpretation I if alpha is true in I or beta is true in I (or both are true in I).
  • false in interpretation I if alpha and beta are both false in I.
  • Example:
  KB={ false <- a & b. a <- c. b <- d.
  } KB ¬c or ¬d.
  
  ## Questions and Answers in Horn KBs
  
  • An assumable is an atom whose negation you are prepared to accept as part of a (disjunctive) answer.
  • A conflict of KB is a set of assumables that, given KB imply false.
  • A minimal conflict is a conflict such that no strict subset is also a conflict.
  
  ## Conflict Example
  
  Example: If {c,d,e,f,g,h} are the assumables
  KB={
   false <- a & b. a <- c. b <- d. b <- e.
  }
  • {c,d} is a conflict
  • {c,e} is a conflict
  • {c,d,e,h} is a conflict
  
  ## Using Conflicts for Diagnosis
  
  • Assume that the user is able to observe whether a light is lit or dark and whether a power outlet is dead or live.
  • A light can't be both lit and dark. An outlet can't be both live and dead:
  
  false <=dark(L) &lit(L).
  
  • Make ok assumable: assumable(ok(X)).
  • Suppose switches s1, s2, and s3 are all up:
  up(s1). up(s2). up(s3).
  
  ## 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.
  
  • If the user has observed l1 and l2 are both dark:
  dark(l1).~dark(l2).
  • There are two minimal conflicts:
  
  {ok(cb_1),ok(s_1),ok(s_2),ok(l_1)}  and
  {ok(cb_1),ok(s_3),ok(l_2)}.
  
  • You can derive:
  
  ¬ok(cb_1) or ¬ok(s_1) or ¬ok(s_2) or ¬ok(l_1)
  ¬ok(cb_1) or ¬ok(s_3) or ¬ok(l_2).
  
  • Either cb1 is broken or there is one of six double faults.
  
  ## Diagnoses
  
  • A consistency-based diagnosis is a set of assumables that has at least one element in each conflict.
  • A minimal diagnosis is a diagnosis such that no subset is also a diagnosis.
  • Intuitively, one of the minimal diagnoses must hold. A diagnosis holds if all of its elements are false.
  • Example: For the proceeding example there are seven minimal diagnoses: {ok(cb1)}, {ok(s1),ok(s3)}, {ok(s1),ok(l2)}, {ok(s2),ok(s3)},...
  
  ## 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
  
  • Conclusions are pairs <a,A>, where a is an atom and A is a set of assumables that imply a.
  • Initially, conclusion set C={<a,{a}>:a is assumable}.
  • If there is a rule h <- b1 & ... & bm such that
  for each bi there is some Ai such that <bi,Ai> in C, then <h,A1 union ... union Am> can be added to C.
  • If <a,A1> and <a,A2> are in C, where A1 strict subset A2, then <a,A2> can be removed from C.
  • If <false,A1> and <a,A2> are in C, where A1 subset A2, then <a,A2> can be removed from C.
  
  ## Bottom-up Conflict Finding Code
  
   C:={:a is assumable }; repeat select clause "h <- b1 & ... & bm" in T such that in C for all i and there is no in C or in C such that A' subset A where A=A1 union ... union Am; C:=C union {} Remove any elements of C that can now be pruned; until no more selections are possible
  
  ## Integrity Constraints in Databases
  
  • Database designers can use integrity constraints to specify constraints that should never be violated.
  • Example: A student can't have two different grades for the same course.
  
  false <-