Computational Intelligence

Online Slides

September 10, 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 2, Lecture 1

Representation and Reasoning System

A Representation and Reasoning System (RRS) is made up of:

formal language: specifies the legal sentences
semantics: specifies the meaning of the symbols
reasoning theory or proof procedure: nondeterministic specification of how an answer can be produced.

Implementation of an RRS

An implementation of an RRS consists of

language parser: maps sentences of the language into data structures.
reasoning procedure: implementation of reasoning theory + search strategy.

Note: the semantics aren't reflected in the implementation!

Using an RRS

Begin with a task domain.
Distinguish those things you want to talk about (the ontology).
Choose symbols in the computer to denote objects and relations.
Tell the system knowledge about the domain.
Ask the system questions.

Role of Semantics in an RRS

Simplifying Assumptions of Initial RRS

An agent's knowledge can be usefully described in terms of individuals and relations among individuals.

An agent's knowledge base consists of definite and positive statements.

The environment is static.

There are only a finite number of individuals of interest in the domain. Each individual can be given a unique name.

=> Datalog

Syntax of Datalog

variable starts with upper-case letter.

constant starts with lower-case letter or is a sequence of digits (numeral).

predicate symbol starts with lower-case letter.

term is either a variable or a constant.

atomic symbol (atom) is of the form p or p(t₁,...,t_n) where p is a predicate symbol and t_i are terms.

Syntax of Datalog (cont)

definite clause is either an atomic symbol (a fact) or of the form:

where a and b_i are atomic symbols.

query is of the form ?b₁ & ··· & b_m.

knowledge base is a set of definite clauses.

Example Knowledge Base

in(alan,R) <-
     teaches(alan,cs322) &
     in(cs322,R).
grandfather(william,X) <-
      father(william,Y) &
     parent(Y,X).
slithy(toves) <-
      mimsy & borogroves &
     outgrabe(mome,Raths).

Chapter 2, Lecture 2

Semantics: General Idea

A semantics specifies the meaning of sentences in the language.

An interpretation specifies:

what objects (individuals) are in the world
the correspondence between symbols in the computer and objects & relations in world
- constants denote individuals
- predicate symbols denote relations

Formal Semantics

An interpretation is a triple I=<D,phi,pi>, where

D, the domain, is a nonempty set. Elements of D are individuals.
phi is a mapping that assigns to each constant an element of D. Constant c denotes individual phi(c).
pi is a mapping that assigns to each n-ary predicate symbol a relation: a function from Dⁿ into { TRUE, FALSE}.

Example Interpretation

Constants: phone, pencil, telephone.
Predicate Symbol: noisy (unary), left_of (binary).

Important points to note

The domain D can contain real objects. (e.g., a person, a room, a course). D can't necessarily be stored in a computer.
pi(p) specifies whether the relation denoted by the n-ary predicate symbol p is true or false for each n-tuple of individuals.
If predicate symbol p has no arguments, then pi(p) is either TRUE or FALSE.

Truth in an interpretation

A constant c denotes in I the individual phi(c) .

Ground (variable-free) atom p(t₁,...,t_n) is

true in interpretation I if pi(p)(t₁',...,t_n')= TRUE, where t_i denotes t_i' in interpretation I and
false in interpretation I if pi(p)(t₁',...,t_n')= FALSE.

Ground clause h <- b₁ & ... & b_m is false in interpretation I if h is false in I and each b_i is true in I, and is true in interpretation I otherwise.

Example Truths

In the interpretation given before:

noisy(phone)	true
noisy(telephone)	true
noisy(pencil)	false
left_of(phone,pencil)	true
left_of(phone,telephone)	false
noisy(pencil) <- left_of(phone,telephone)	true
noisy(pencil) <- left_of(phone,pencil)	false
noisy(phone) <- noisy(telephone) & noisy(pencil)	true

Models and logical consequences

A knowledge base, KB, is true in interpretation I if and only if every clause in KB is true in I.
A model of a set of clauses is an interpretation in which all the clauses are true.
If KB is a set of clauses and g is a conjunction of atoms, g is a logical consequence of KB, written KBg, if g is true in every model of KB.
That is, KBg if there is no interpretation in which KB is true and g is false.

Simple Example

KB={
p <- q.

q.

r <- s.
}

	pi(p)	pi(q)	pi(r)	pi(s)
I₁	TRUE	TRUE	TRUE	TRUE	is a model of KB
I₂	FALSE	FALSE	FALSE	FALSE	not a model of KB
I₃	TRUE	TRUE	FALSE	FALSE	is a model of KB
I₄	TRUE	TRUE	TRUE	FALSE	is a model of KB
I₅	TRUE	TRUE	FALSE	TRUE	not a model of KB

KB p, KB q, KB r, KB s

User's view of Semantics

Choose a task domain: intended interpretation.
Associate constants with individuals you want to name.
For each relation you want to represent, associate a predicate symbol in the language.
Tell the system clauses that are true in the intended interpretation: axiomatizing the domain.
Ask questions about the intended interpretation.
If KB g, then g must be true in the intended interpretation.

Computer's view of semantics

The computer doesn't have access to the intended interpretation.
All it knows is the knowledge base.
The computer can determine if a formula is a logical consequence of KB.
If KB g then g must be true in the intended interpretation.
If KBg then there is a model of KB in which g is false. This could be the intended interpretation.

Chapter 2, Lecture 3

Variables

Variables are universally quantified in the scope of a clause.
A variable assignment is a function from variables into the domain.
Given an interpretation and a variable assignment,
each term denotes an individual and
each clause is either true or false.
A clause containing variables is true in an interpretation if it is true for all variable assignments.

Queries and Answers

A query is a way to ask if a body is a logical consequence of the knowledge base:

?b₁ & ··· & b_m.

An answer is either

an instance of the query that is a logical consequence of the knowledge base KB, or
no if no instance is a logical consequence of KB.

Example Queries

KB={
in(alan,r123).

part_of(r123,cs_building).

in(X,Y) <- part_of(Z,Y) & in(X,Z).
}

Query Answer

?part_of(r123,B). part_of(r123,cs_building)

?part_of(r023,cs_building). no

?in(alan,r023). no

?in(alan,B). in(alan,r123)

in(alan,cs_building)

Logical Consequence

Atom g is a logical consequence of KB if and only if:

g is a fact in KB, or
there is a rule
g <- b₁ & ... & b_k
in KB such that each b_i is a logical consequence of KB.

Debugging false conclusions

To debug answer g that is false in the intended interpretation:

If g is a fact in KB, this fact is wrong.
Otherwise, suppose g was proved using the rule:
g <- b₁ & ... & b_k
where each b_i is a logical consequence of KB.
- If each b_i is true in the intended interpretation, this clause is false in the intended interpretation.
- If some b_i is false in the intended interpretation, debug b_i.

Electrical Environment

Axiomatizing the Electrical Environment

%~light(L) is true if L is a light

light(l₁). light(l₂).

%~down(S) is true if switch S is down

down(s₁). up(s₂). up(s₃).

%~ok(D) is true if D is not broken

ok(l₁). ok(l₂). ok(cb₁). ok(cb₂).

?light(l₁).	=>	yes
?light(l₆).	=>	no
?up(X).	=>	up(s₂), up(s₃)

connected_to(X,Y) is true if component X is connected to Y

connected_to(w_0,w_1) <- up(s_2).
connected_to(w_0,w_2) <- down(s_2).
connected_to(w_1,w_3) <- up(s_1).
connected_to(w_2,w_3) <- down(s_1).
connected_to(w_4,w_3) <- up(s_3).
connected_to(p_1,w_3).

?connected_to(w₀,W).	=>	W=w₁
?connected_to(w₁,W).	=>	no
?connected_to(Y,w₃).	=>	Y=w₂, Y=w₄, Y=p₁
?connected_to(X,W).	=>	X=w₀, W=w₁, ...

% lit(L) is true if the light L is lit

lit(L) <- light(L) & ok(L) & live(L).

% live(C) is true if there is power coming into C

live(Y) <-
connected_to(Y,Z) &
live(Z).
live(outside).

This is a recursive definition of live.

Recursion and Mathematical Induction

above(X,Y) <- on(X,Y).
above(X,Y) <- on(X,Z) & above(Z,Y).

This can be seen as:

Recursive definition of above: prove above in terms of a base case (on) or a simpler instance of itself; or
Way to prove above by mathematical induction: the base case is when there are no blocks between X and Y, and if you can prove above when there are n blocks between them, you can prove it when there are n+1 blocks.

Limitations

Suppose you had a database using the relation:

enrolled(S,C)

which is true when student S is enrolled in course C.

You can't define the relation:

empty_course(C)

which is true when course C has no students enrolled in it.

This is because empty_course(C) doesn't logically follow from a set of enrolled relations. There are always models where someone is enrolled in a course!

Chapter 2, Lecture 4

Proofs

A proof is a mechanically derivable demonstration that a formula logically follows from a knowledge base.
Given a proof procedure, KB g means g can be derived from knowledge base KB.
Recall KB g means g is true in all models of KB.
A proof procedure is sound if KB g implies KB g.
A proof procedure is complete if KB g implies KB g.

Bottom-up Ground Proof Procedure

One rule of derivation, a generalized form of modus ponens:

If "h <- b₁ & ... & b_m" is a clause in the knowledge base, and each b_i has been derived, then h can be derived.

You are forward chaining on this clause.

(This rule also covers the case when m=0.)

Bottom-up proof procedure

KBg if g in C at the end of this procedure:

C:={};

repeat

select clause "h <- b₁ & ... & b_m" in KB such that

b_i in C for all i, and

h not in C;

C:=C union {h}

until no more clauses can be selected.

Nondeterministic Choice

Don't-care nondeterminism If one selection doesn't lead to a solution, there is no point trying other alternatives. select
Don't-know nondeterminism If one choice doesn't lead to a solution, other choices may. choose

Example

a <- b & c.
a <- e & f.
b <- f & k.
c <- e.
d <- k.
e.
f <- j & e.
f <- c.
j <- c.

Soundness of bottom-up proof procedure

If KBg then KBg.

Suppose there is a g such that KBg and KBg.

Let h be the first atom added to C that's not true in every model of KB. Suppose h isn't true in model I of KB.
There must be a clause in KB of form

h <- b₁ & ... & b_m

Each b_i is true in I. h is false in I. So this clause is false in I. Therefore I isn't a model of KB.

Contradiction: thus no such g exists.

Fixed Point

The C generated at the end of the bottom-up algorithm is called a fixed point.

Let I be the interpretation in which every element of the fixed point is true and every other atom is false.

I is a model of KB.
Proof: suppose h <- b₁ & ... & b_m in KB is false in I. Then h is false and each b_i is true in I. Thus h can be added to C. Contradiction to C being the fixed point.

I is called a Minimal Model.

Completeness

If KBg then KBg.

Suppose KBg. Then g is true in all models of KB.

Thus g is true in the minimal model.

Thus g is generated by the bottom up algorithm.

Thus KBg.

Chapter 2, Lecture 5

Top-down Ground Proof Procedure

Idea: search backward from a query to determine if it is a logical consequence of KB.

An answer clause is of the form:

yes <- a_1 & a_2 & ... & a_m

The SLD Resolution of this answer clause on atom a_i with the clause:

a_i <- b_1 & ... & b_ p

is the answer clause

yes <- a_1 & ··· & a_i-1 & b_1 & ··· & b_p & a_i+1 & ··· & a_m.

Derivations

An answer is an answer clause with m=0. That is, it is the answer clause yes <- .
A derivation of query "?q₁ & ... & q_k" from KB is a sequence of answer clauses gamma₀, gamma₁, ..., gamma_n such that
- gamma₀ is the answer clause yes <- q₁ & ... & q_k,
- gamma_i is obtained by resolving gamma_i-1 with a clause in KB, and
- gamma_n is an answer.

Top-down definite clause interpreter

To solve the query ?q₁ & ... & q_k:

ac:= "yes <- q₁ & ... & q_k"

repeat

select a conjunct a_i from the body of ac;

choose clause C from KB with a_i as head;

replace a_i in the body of ac by the body of C

until ac is an answer.

Example: successful derivation

a <- b & c. a <- e & f. b <- f & k.

c <- e. d <- k. e.

f <- j & e. f <- c. j <- c.

Query: ?a

gamma₀: yes <- a gamma₄: yes <- e

gamma₁: yes <- e & f gamma₅: yes <-

gamma₂: yes <- f

gamma₃: yes <- c

Example: failing derivation

a <- b & c. a <- e & f. b <- f & k.

c <- e. d <- k. e.

f <- j & e. f <- c. j <- c.

Query: ?a

gamma₀: yes <- a gamma₄: yes <- e & k & c

gamma₁: yes <- b & c gamma₅: yes <- k & c

gamma₂: yes <- f & k & c

gamma₃: yes <- c & k & c

Chapter 2, Lecture 6

Reasoning with Variables

An instance of an atom or a clause is obtained by uniformly substituting terms for variables.
A substitution is a finite set of the form {V₁/t₁,...,V_n/t_n}, where each V_i is a distinct variable and each t_i is a term.
The application of a substitution sigma={V₁/t₁,...,V_n/t_n} to an atom or clause e, written esigma, is the instance of e with every occurrence of V_i replaced by t_i.

Application Examples

The following are substitutions:

sigma₁={X/A,Y/b,Z/C,D/e}
sigma₂={A/X,Y/b,C/Z,D/e}
sigma₃={A/V,X/V,Y/b,C/W,Z/W,D/e}

The following shows some applications:

p(A,b,C,D) sigma₁ = p(A,b,C,e)
p(X,Y,Z,e) sigma₁ = p(A,b,C,e)
p(A,b,C,D) sigma₂ = p(X,b,Z,e)
p(X,Y,Z,e) sigma₂ = p(X,b,Z,e)
p(A,b,C,D) sigma₃ = p(V,b,W,e)
p(X,Y,Z,e) sigma₃ = p(V,b,W,e)

Unifiers

Substitution sigma is a unifier of e₁ and e₂ if e₁sigma=e₂sigma.
Substitution sigma is a most general unifier (mgu) of e₁ and e₂ if
- sigma is a unifier of e₁ and e₂; and
- if substitution sigma' also unifies e₁ and e₂, then esigma' is an instance of e sigma for all atoms e.
If two atoms have a unifier, they have a most general unifier.

Unification Example

p(A,b,C,D) and p(X,Y,Z,e) have as unifiers:

sigma₁={X/A,Y/b,Z/C,D/e}
sigma₂={A/X,Y/b,C/Z,D/e}
sigma₃={A/V,X/V,Y/b,C/W,Z/W,D/e}
sigma₄={A/a,X/a,Y/b,C/c,Z/c,D/e}
sigma₅={X/A,Y/b,Z/A,C/A,D/e}
sigma₆={X/A,Y/b,Z/C,D/e,W/a}

The first three are most general unifiers.

The following substitutions are not unifiers:

sigma₇={Y/b,D/e}
sigma₈={X/a,Y/b,Z/c,D/e}

Bottom-up procedure

You can carry out the bottom-up procedure on the ground instances of the clauses.
Soundness is a direct corollary of the ground soundness.
For completeness, we build a canonical minimal model. We need a denotation for constants:
Herbrand interpretation: The domain is the set of constants (we invent one if the KB or query doesn't contain one). Each constant denotes itself.

Definite Resolution with Variables

A generalized answer clause is of the form

yes(t_1,...,t_k) <- a_1 & a_2 & ... & a_m,

where t₁,...,t_k are terms and a₁,...,a_m are atoms.

The SLD resolution of this generalized answer clause on a_i with the clause

a <- b_1 & ... & b_p,

where a_i and a have most general unifier theta, is

(yes(t_1,...,t_k) <-
a_1 & ... & a_i-1 & b_1 & ... & b_p & a_i+1 & ... & a_m)theta.

To solve query ?B with variables V₁,...,V_k:

Set ac to generalized answer clause yes(V₁,...,V_k) <- B;

While ac is not an answer do

Suppose ac is yes(t₁,...,t_k) <- a₁ & a₂ & ... & a_m

Select atom a_i in the body of ac;

Choose clause a <- b₁ & ... & b_p in KB;

Rename all variables in a <- b₁ & ... & b_p;

Let theta be the most general unifier of a_i and a.

Fail if they don't unify;

Set ac to (yes(t₁,...,t_k) <- a₁ & ... & a_i-1 &

b₁ & ... & b_p & a_i+1 & ... & a_m)theta

end while.

Example

live(Y) <- connected_to(Y,Z) & live(Z).live(outside).
connected_to(w_6,w_5).connected_to(w_5,outside).
?live(A).
     yes(A) <- live(A).
     yes(A) <- connected_to(A,Z_1) & live(Z_1).
     yes(w_6) <- live(w_5).
     yes(w_6) <- connected_to(w_5,Z_2) & live(Z_2).
     yes(w_6) <- live(outside).
     yes(w_6) <- .

Function Symbols

Often we want to refer to individuals in terms of components.

Examples: 4:55 p.m. English sentences. A classlist.

We extend the notion of term. So that a term can be f(t₁,...,t_n) where f is a function symbol and the t_i are terms.

In an interpretation and with a variable assignment, term f(t₁,...,t_n) denotes an individual in the domain.

With one function symbol and one constant we can refer to infinitely many individuals.

Lists

A list is an ordered sequence of elements. Let's use the constant nil to denote the empty list, and the function cons(H,T) to denote the list with first element H and rest-of-list T. These are not built-in.

The list containing david, alan and randy is

cons(david,cons(alan,cons(randy,nil)))

append(X,Y,Z) is true if list Z contains the elements of X followed by the elements of Y

append(nil,Z,Z).
append(cons(A,X),Y,cons(A,Z)) <- append(X,Y,Z).

Query	Answer
?part_of(r123,B).	part_of(r123,cs_building)
?part_of(r023,cs_building).	no
?in(alan,r023).	no
?in(alan,B).	in(alan,r123)
	in(alan,cs_building)

%~light(L) is true if L is a light
light(l₁).	light(l₂).
%~down(S) is true if switch S is down
down(s₁).	up(s₂).	up(s₃).
%~ok(D) is true if D is not broken
ok(l₁).	ok(l₂).	ok(cb₁).	ok(cb₂).

a <- b & c.	a <- e & f.	b <- f & k.
c <- e.	d <- k.	e.
f <- j & e.	f <- c.	j <- c.

gamma₀:	yes <- a	gamma₄:	yes <- e
gamma₁:	yes <- e & f	gamma₅:	yes <-
gamma₂:	yes <- f
gamma₃:	yes <- c