Transcript Resources - CSE, IIT Bombay

CS621: Artificial Intelligence
Pushpak Bhattacharyya
CSE Dept.,
IIT Bombay
Lecture 34– Predicate Calculus and
Himalayan Club example
(lectures 32 and 33 were on HMM+Viterbi
combined AI and NLP)
Resolution - Refutation

man(x) → mortal(x)



Convert to clausal form
~man(shakespeare)
mortal(x)

Clauses in the knowledge base



~man(shakespeare)
man(shakespeare)
mortal(shakespeare)
mortal(x)

Resolution – Refutation contd

Negate the goal


~man(shakespeare)
Get a pair of resolvents
~ mortal( shakespeare)
~ man( shakespeare)  mortal( shakespeare)
~ man( shakespeare)
~ man( shakespeare)
Resolution Tree
Re solvent1
Re solvent 2
Re solute
Search in resolution

Heuristics for Resolution Search

Goal Supported Strategy


Always start with the negated goal
Set of support strategy

Always one of the resolvents is the most recently
produced resolute
Inferencing in Predicate Calculus

Forward chaining




Backward chaining




Given P, P  Q , to infer Q
P, match L.H.S of
Assert Q from R.H.S
Q, Match R.H.S of
assert P
Check if P exists
PQ
Resolution – Refutation



Negate goal
Convert all pieces of knowledge into clausal form (disjunction of
literals)
See if contradiction indicated by null clause
can be derived
1.
2.
3.
P
P  Q converted to ~ P  Q
~Q
Draw the resolution tree (actually an inverted
tree). Every node is a clausal form and
branches are intermediate inference steps.
~ PQ
~Q
~P
P
Terminology


Pair of clauses being resolved is called the
Resolvents. The resulting clause is called
the Resolute.
Choosing the correct pair of resolvents is a
matter of search.
Predicate Calculus

Introduction through an example (Zohar Manna,
1974):

Problem: A, B and C belong to the Himalayan club.
Every member in the club is either a mountain
climber or a skier or both. A likes whatever B
dislikes and dislikes whatever B likes. A likes rain
and snow. No mountain climber likes rain. Every
skier likes snow. Is there a member who is a
mountain climber and not a skier?

Given knowledge has:
 Facts

Rules
Predicate Calculus: Example
contd.

Let mc denote mountain climber and sk denotes skier.
Knowledge representation in the given problem is as follows:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.


member(A)
member(B)
member(C)
∀x[member(x) → (mc(x) ∨ sk(x))]
∀x[mc(x) → ~like(x,rain)]
∀x[sk(x) → like(x, snow)]
∀x[like(B, x) → ~like(A, x)]
∀x[~like(B, x) → like(A, x)]
like(A, rain)
like(A, snow)
Question: ∃x[member(x) ∧ mc(x) ∧ ~sk(x)]
We have to infer the 11th expression from the given 10.
Done through Resolution Refutation.
Club example: Inferencing
member(A)
member(B)
member(C)
x[member( x)  (mc( x)  sk ( x))]
1.
2.
3.
4.
–
–
5.
6.
7.
Can be written as
[member( x)  (mc( x)  sk ( x))]
~ member( x)  mc( x)  sk ( x)
x[ sk ( x)  lk ( x, snow)]
~ sk ( x)  lk ( x, snow)
–
x[mc( x) ~ lk ( x, rain )]
~ mc( x) ~ lk ( x, rain )
–
x[like( A, x) ~ lk ( B, x)]
–
~ like( A, x) ~ lk ( B, x)
x[~ lk ( A, x)  lk ( B, x)]
8.
lk ( A, x)  lk ( B, x)
–
9.
lk ( A, rain )
10.
lk ( A, snow)
11.
x[member( x)  mc( x) ~ sk ( x)]
–
Negate– x[~ member( x) ~ mc( x)  sk ( x)]

1.
2.
3.
Now standardize the variables apart which
results in the following
member(A)
member(B)
member(C)
4.
~ member( x1)  mc( x1)  sk ( x1)
5.
~ sk ( x 2)  lk ( x 2, snow)
6.
~ mc( x 3) ~ lk ( x 3, rain )
7.
~ like( A, x 4) ~ lk ( B, x 4)
8.
lk ( A, x 5)  lk ( B, x 5)
9.
lk ( A, rain )
10.
lk ( A, snow)
x[~ member( x 6) ~ mc( x 6)  sk ( x 6)]
11.
~ like( A, x 4) ~ lk ( B, x 4)
lk ( A, snow) 10
7
12 ~ lk ( B, snow)
~ sk ( x 2)  lk ( x 2, snow)
13 ~ sk ( B )
5
~ member( x1)  mc( x1)  sk ( x1) 4
14 ~ member( B)  mc( B)
member(B ) 2
11
x[~ member( x 6) ~ mc( x 6)  sk ( x 6)]
mc(B)
16 ~ member( B)  sk ( B)
17 ~ member( B )
15
~ sk ( B ) 13
member(B )
2
Assignment



Prove the inferencing in the Himalayan club
example with different starting points,
producing different resolution trees.
Think of a Prolog implementation of the
problem
Prolog Reference (Prolog by Chockshin &
Melish)
Problem-2
From predicate calculus
A “department” environment
1.
2.
3.
4.
5.
6.
7.
8.
Dr. X is the HoD of CSE
Y and Z work in CSE
Dr. P is the HoD of ME
Q and R work in ME
Y is married to Q
By Institute policy staffs of the same
department cannot marry
All married staff of CSE are insured by LIC
HoD is the boss of all staff in the
department
Diagrammatic representation
CSE
ME
Dr. P
Dr. X
Y
Z
Q
married
R
Questions on “department”



Who works in CSE?
Is there a married person in ME?
Is there somebody insured by LIC?
Text Knowledge
Representation
A Semantic Graph
bought
past tense
time
agent
object
student
computer
the: definite
modifier
a: indefinite
June
in: modifier
new
The student bought a new computer in June.
UNL representation
Representation of Knowledge
Ram is reading the newspaper
UNL: a United Nations project
Dave, Parikh and Bhattacharyya, Journal of Machine Translation, 2002






Started in 1996
10 year program
15 research groups across continents
First goal: generators
Next goal: analysers (needs solving various ambiguity
problems)
Current active language groups






UNL_French (GETA-CLIPS, IMAG)
UNL_Hindi (IIT Bombay with additional work on
UNL_English)
UNL_Italian (Univ. of Pisa)
UNL_Portugese (Univ of Sao Paolo, Brazil)
UNL_Russian (Institute of Linguistics, Moscow)
UNL_Spanish (UPM, Madrid)
Knowledge Representation
UNL Graph - relations
read
agt
Ram
obj
newspaper
Knowledge Representation
UNL Graph - UWs
read(icl>interpret)
agt
Ram(iof>person)
obj
newspaper(icl>print_media)
Knowledge Representation
UNL graph - attributes
read(icl>interpret)
agt
@entry
@present
@progress
obj
@def
Ram(iof>person)
newspaper(icl>print_media)
Ram is reading the newspaper
Another Example
The boy who works here went to school
agt
go(icl>move)
@ entry @ past
plt
boy(icl>person
)
agt
plc
work(icl>do
)
@ entry
here
:01
school(icl>institution)
What do these examples
show?



Logic systematizes the reasoning process
Helps identify what is
mechanical/routine/automatable
Brings to light the steps that only human
intelligence can perform


These are especially of foundational and structural
nature (e.g., deciding what propositions to
start with)
Algorithmizing reasoning is not trivial
About the SA/GA assignments
Key points

1. SA and GA are randomized search algorithms;
(a) why does one do randomized search?
(b) To QUICKLY find a solution even if the the solution is not
FULLY accurate
2. For example, TSP is NP hard; so any algorithm that purports
to give the correct tour ALWAYS is going to take exponential
amount of time.
3. But it may be alright to get the solution certain percentage of
time. Then one can use SA/GA.
4. For sorting , consider getting the sorted sequences for any
set of of numbers of any sequence length, say 200,000
numbers.
Key points cntd

5. It may be OK to get an ALMOST sorted sequence QUICKLY;
so see if SA and GA can be used
6. SO what is coming out strongly is TIME vs. ACCURACY
TRADE-OFF
7. ***THE ABOVE HAS TO COME OUT IN YOUR ASSIGNMENT
8. What about 8 puzzle? Optimal path is not needed.
Key points cntd

9. But you HAVE TO demonstrate randomness. That means
Ther are times when the goal state will not be reached;
10. The above will be the case when randomness is
INTRODUCED in the system by making the tempearure HIGH.
11. Thus a key point of the assignment is the EFFECT OF HIGH
TEMPERATURE on the system.
12. Another point about the next state: make sure you pick it up
RANDOMLY and not deterministically.
13. Think about the connection between BFS and random
search. The former will guarantee finding the goal state, the
latter not. But there may be gain in time complexity.