Transcript ppt

Declarative Programming
PROLOG (+ Bayesian Nets)
Second part of Cmput325
Fall 2004
R Greiner + B Price
1
Declarative Programming





Motivation
 Warm Fuzzies
 What is Logic? ... Logic Programming?
Mechanics of Prolog
 Terms, Substitution, Unification, Horn Clauses, Proof process
Example: List Processing
Theoretical Foundations
 Semantics
 Logic / Theorem Proving … Resolution
Other Issues
Search Strategies
 Declarative/Procedural, ...
 “Impure'' Operators” --- NOT, !

Utilities
? Constraint Programming
? Bayesian Belief Nets



2
2004 … 1990 … 1980
3
Story …

MD sees patient … perhaps MENINGITIS!



Performs standard tests
Calls Infection Disease (medical) expert
Dialogue:

Expert asks for info re: patient


Fever, Organism Morphology, Gram Stain, Spinal Fluid, …
Doctor's answers:




DIRECT : from direct measurement, Lab tests
Qualitative: Has HIGH fever
Vague: Portal of Entry was GastroIntestinal (w/certainty 0.6)
Unknown: don’t know identity of organism?
4
Story … con’t

MD can ask questions:


Why ask about portal of entry?
Expert answers:




If further questioned, … point to definitive study
Expert provides DIAGNOSIS



trying to show
infecting organism is ENTEROBACTERICAE
this information is crucial in that decision.
organism was one of {E.coli, Enterobacteria }
suggest TREATMENT: Give GENTAMICIN
Happily ever after...
5
The Catch …
Expert System
6
Expert System
An EXPERT SYSTEM is a computer program
that exhibits Expert Level performance in
solving complex problems.

Reasons with Facts about the World:
Combines
 General Facts/Rules (about Diseases, ...)
with
 Specific Facts (about Patient)
to Produce new Conclusion (diagnosis)
7
Medical Expert Systems

MYCIN



Glaucoma


Kidney
Ventricle Movement
ONCOCIN


Ventilator Management
ALVEN


Erratic Heartbeat
VM

Present lllness Program

Digitalis advisor

Internal Medicine
CASNET


Blood Infections
CADUCEUS


…
Cancer Treatment
Protocols
8
Other Domains












Medicine
Chemistry
Instruction
Job-Shop Management
Financial Planning
Computer Diagnosis, Configuration
VLSI Design
Molecular Genetics
Signal Analysis
Structural Mechanics
Mathematics
…
9
“Declarative Programming''
1
2
Give
Gentamycin?
Is 
true?
Knowledge Base
--- -- --- ---- --- - -- --- - --- ------ -- --- -Facts about the world
-- ---- --- ---- ----- - ----- -- ----- -- --- - -
Proof
Procedure
Yes … No
10
Advantages of Framework
store “truths”
ask for other truths

Simply

Information is

Modular




Easy to Build
Easy to Modify (Extend, Debug)
Capable of Explanation
Declarative

Re-use same info for different tasks
11
Computers Manipulate SYMBOLS

Numbers



3, 5, ...
Addition, Multiplication, ...
Propositions


“D1 is an inverter''
“Inverters flip bits''
...
Deduction, ...
12
Simple Deduction




Socrates is a man.
If Socrates is a man,
Then Socrates is mortal.
Socrates is mortal.
In general…



13
Example of Deduction
(Goal)
Socrates is Mortal
R1
(New
Goal)
Socrates is a Man
RULES
R1: If Socrates is a Man,
Then Socrates is Mortal
o
o
FACTS
o
o
F1: Socrates is a Man.
o
14
Example of Deduction, #2
R2
Plato is Mortal
Plato is a Cat
R1
Plato is a Man
R3
Plato purrs
RULES
R1: If Plato is a Man,
Then Plato is Mortal
R2: If Plato is a Cat
Then Plato is Mortal.
R3: If Plato purrs,
Then Plato is a Cat.
FACTS
o
o
F3: Plato purrs.
o
o
o
15
Example of Deduction, #3
Aristotle is a man
R9
Aristotle is a Human
RULES
R2: If Plato is a Cat
Then Plato is Mortal.
o
R9: If Aristotle is a human
and Aristotle is male,
Then Aristotle is a man
o
Aristotle is male
FACTS
o
o
F3: Aristotle is male.
o
F8: Aristotle is a human
o
16
Oversimplified Proof Process
If Goal i = FACT
1.


then DONE
Else …
YES
Goal i = “Then Part” of Rule R
2.

then Goal i+1  “If Part” of R

else DONE NO
17
Just Manipulating Symbols

Consider claim


This is Belgium.
Conclusion is wrong!

based on “proof”


Today is Tuesday.
If
Today is Tuesday
Then This is Belgium.



This is Belgium

Conclusion is
ONLY AS TRUE
as PREMISES
If Premises true,
then Conclusion is.
Not fault of PROOF
process
GIGO…
18
19
Rules
R1: if (1) You have a Parking Permit &
This space is Permit-Parkable,
then You can park at this space.
(2)
R2: if (1) This space is a Parking Space &
Permit-Sign at this space &
(3) Current date is Acceptable,
then This space is Permit-Parkable.
(2)
R3: if (1) Current time is 7am-Midnight &
This space is Permit-Parkable,
then You can park at this space.
(2)
R4: if
(1)
R5: if
(1)
Current month is Dec-Mar,
then Current date is Acceptable.
Current month is in Apr-Nov &
(2) Current day of month is ≤ 15
then Current date is Acceptable.
20
Facts












This space is a Parking Space.
You live near this space.
You have a Parking Permit.
Current month is in Apr-Nov.
Current day is Tuesday.
Current day of month is ≤ 15.
Permit-Sign at this space.
You own a car.
Your car is >5 years old.
Current time is 3am.
You have $18.00.
...
21
Inference Graph
You can park at this space
R1
You have a Parking Permit
This space is Permit-Parkable
R2
… Parking Space
Current date is Acceptable
R5
Permit-Sign …
…Apr-Nov
… ≤ 15
22
Additional Rules
R1: if
(1)
R2: if
(1)
You have a Parking Permit &
(2) This space is Permit-Parkable,
then You can park at this space.
This space is a Parking Space &
(2) Permit-Sign at this space &
(3) Current date is Acceptable,
then This space is Permit-Parkable.
R7: if
(1)
R8: if
(1)
You live near this space &
(2) You own a car &
(3) You apply for a permit,
then You have a Parking Permit.
You can park at this space
then You can take a car.
R3: if (1) Current time is 7am-Midnight &
This space is Permit-Parkable,
then You can park at this space.
(2)
R4: if
(1)
R5: if
(1)
Current month is Dec-Mar,
then Current date is Acceptable.
Current month is in Apr-Nov &
(2) Current day of month is ≤ 15
then
Current date is Acceptable.
23
Inference Graph
You can take a car
R8
You can park at this space
R1
You have a Parking Permit
This space is Permit-Parkable
R2
R7
… Parking Space
… live near …
… apply for permit
Current date is Acceptable
R5
Permit-Sign …
…own a car
…Apr-Nov
… ≤ 15
24
Mycin: What is the suspected portal of entry of ORGANISM-1 into
this sterile site?
Doctor: WHY
Mycin: [ie, why is it important to determine the … site?]
[3.0] … to determine which organism(s) to cover …
It has already been established that
3.1] site of culture is blood
3.2] organism stain is gram positive
Therefore, if
3.3] portal of entry is g.i.
3.4] locus of infection is Pelvis or Abdomen,
Then
 strongly suggestive evidence (0.9) that therapy
should cover enterobacteriaceae.
[Rule 095]
...
25
Mycin: What is the suspected portal of entry of ORGANISM-1 into
this sterile site?
Doctor: WHY
Mycin: [ie, why is it important to determine the … site?]
[3.0] … to determine which organism(s) to cover …
If has already been established that
3.1] site of culture is blood
3.2] organism stain is gram positive
Therefore, if
3.3] portal of entry is g.i.
3.4] locus of infection is Pelvis or Abdomen,
Then
 strongly suggestive evidence (0.9) that therapy
should cover enterobacteriaceae.
[Rule 095]
...
26
Advantage of Rule Transparency



Explain reasoning
Support / Credability
Helpful when…


building/extending system
modifying system
27
Issues


Faster Computation
User Interaction




Focus of Attention
“Human Engineering”
Variables
Control of Search

Which (sub)goal? Which rule?
28
Variables
You can park at
RL
RA
RB
X = SpaceA
X = SpaceB
RA: if
…,
then Can park @ SpaceA.
o
o
o
(1)
X
RB: if
X = ParkingLot-L
…,
RL: if (1) …,
then Can park @ SpaceB. then Can park @ Lot-L.
o
o
o
o
o
o
(1)
29
Control of Search
FACTS
F1:
F2:
F3:
RULES
f( Abe, Bob )
f( Bob, Charles )
f( Charles, Dave )
R1:
R2:
a( x, y ) & a( y, z )  a( x, z )
f( x, y )  a ( x, y )
a(Abe, Dave)
R1
a(Abe, y1)
R1
a(Abe, y2)
R1
a(Abe, y3)
R2
a( y1, Dave)
f(Abe, Dave)
R2
a(y2, y1)
f(Abe, y1)
R2
a(y3, y2)
f(Abe, y2)
30
Research Issues

Better Decision Making



“Deeper Knowledge”



Coping with Uncertainty
Better Explanation
First Principles
“Meta”
Acquiring the Knowledge


… from expert
… from data
31