Transcript Notes-7-rules

Rule Based Systems
Introduction to Production
System Architecture
1
Rules and ‘Productions’
• ‘Production’ - a rule for changing grammar
• Englishs regular verbs
– regular_verb + (past) --> verb + ‘ed’
• Pig-latin productions
– consontant string  string + consonant + ‘ay’
– vowel + string  string + ay
• Is this enough? What do we have to add?
• Can you reverse it?
2
Work through this production
system to decode the result
• zl
up
ph
lw  llo
qr
vw
re
• uqzv  ??
3
Rules
• Form
– IF antecedent THEN conclusion
– IF condition THEN action
– IF antecedent THEN goal
• Interpreters
– Backward chaining
» Trigger on conclusion/goal
– Forward chaining
» Trigger on antecedent/condition
4
Rules and Logic
• Rules are really statement in logic
– About what we believe to be true
– About what should occur
• Translation 1 - situations
– IF may_rain THEN should_take_umbrella
 s. Situation s  May_rain s  Take_umbrella s
“For all s, if s is a situation & s is a may_rain situation,
then s is a take_umbrella situation.
5
Rules and Logic
• Translation 2 - implied objects
– IF may_rain THEN should_take_umbrella
 wp. Weather w  Person p  May_rain w  Out_in p w
Take_umbrella p
“For all w and p, if w is a weather and w is may_rain
weather and p is a person and p is out in w, then p
(should) take an umbrella.”
• Translations: be careful of the words
– The words are just symbols
» They have no meaning except help human know what the
symbols are for
» Just like variable names - could all be x,y,z...
•  wp. W w  P p  M w  O p w T p
6
Forward and Backward
Chaining
• Rules
– r1: IF may_rain THEN should_take_umbrella
– r2: IF cloudy THEN may_rain
• Questions
– “Should I take an umbrella?”
– “What should I do if it is cloudy?”
• How did you answer the questions?
– Which part of the rule did you look for? (‘match’)
7
Backward Chaining
• Rules
– R1: IF may_rain THEN should_take_umbrella
– R2: IF cloudy THEN may_rain
• “Should I take an umbrella?”
– “Do the rules indicate I should take an umbrella?
» Is there a rule about “taking umbrellas”?
• R1: goal: should_take_umbrella
» How can I prove that goal?
• What has to be true for r1 to hold?
– may_rain is the antecedent of r1
» Can I prove that it may_rain?
• R2: goal: may_rain
» How can I prove that goal2
• What has to be true for r2 to hold
– cloudy is the antecedent of r2
» How can I prove ‘cloudy’?
8
Backward Chaining
Goal_2  Goal_3
rules
Goal_3  Goal_4
Direction of reasoning
Goal_1  Goal_2
Goal_4  Goal_5
Question
9
Backward Chaining
• Rules
–
–
–
–
R1: IF may_rain THEN should_take_umbrella
R2: IF cloudy THEN may_rain
R3: IF may_be_intense_sun THEN should_take_umbrella
R4: IF summer AND in_tropics THEN
may_be_intense_sun
• “Should I take an umbrella?”
– “Do the rules indicate I should take an umbrella?
» Is there are rule about “taking umbrellas”?
• R1: goal: should_take_umbrella
» What is antecedent for r1?
• R1:antecedent may_rain
» Can I prove that it may_rain?
• R2: goal: may_rain
» How can I prove may_rain
• R2:antecedent: cloudy
» BUT NOT CLOUDY!
10
Backward Chaining: Backtracking
• Rules
–
–
–
–
R1: IF may_rain THEN should_take_umbrella
R2: IF cloudy THEN may_rain
R3: IF may_be_intense_sun THEN should_take_umbrella
R4: IF summer AND in_tropics THEN
may_be_intense_sun
• “Should I take an umbrella?”
» Are there any other rules about umbrellas?
• R3: goal: should_take_umbrella
» What is antecedent of R3?
• R3:antecedent: summer AND in tropics
11
Goal_1  Goal_2
Goal_8  Goal 7
Goal_2  Goal_3
Goal_7  Goal_6
fail
Goal_3  Goal_4
rules
Goal_6  Goal_4
Goal_4  Goal_5
Question
12
Direction of reasoning
Backwards Chaining with Backtracking
Backwards Chaining Systems
• MYCIN
– ‘The original expert system’
» Diagnosis of acute infections (Meningitis, blood infections)
• Still a good example of how it works
» Also used
• uncertain reasoning
• Explanation
– ‘How’ did you prove that?
– ‘Why’ are you asking me that?
» Never used ‘for real’
• PROLOG
– One of the two standard AI languages
» A simple backwards chaining engine with backtracking
13
Backwards Chaining Engines
usually written ‘backwards’
• Goal  Antecedent
– Umbrella  may_rain
– may_rain  cloudy
• Prolog ‘Edinburgh’ notation
– umbrella :- may_rain.
– may_rain :- cloudy.
NB upper and lower case very important in Prolog
• In KnowledgeWorks
– (defrule r1 :backward <body>)
» Or special functions ‘any’, ‘test’, and ‘not’
• Awkward - don’t try it first time.
14
Forward Chaining
• Rules
– R1: IF may_rain THEN should_take_umbrella
– R2: IF cloudy THEN may_rain
• “What should I do if it is cloudy?”
– “What do the rules indicate I should do if it is cloudy?”
» Is there a rule that applies when it is cloudy?
• R2: antecedent: cloudy
» What do I conclude from that antecedent, ‘cloudy’
• R2: conclusion: may_rain
» Is there a rule that applies when it may_rain?
• R1: antecedent: may_rain
» What do I conclude from that antecedent: ‘may_rain’
• R1: conclusion: should_take_umbrella
15
Forward chaining
‘Production Systems’
– Vocabulary used differently on west and east coast of US
for many years
» On east coast, ‘production systems’ means forward
chaining
» On west coast, ‘production systems’ just means rule based
systems
– Usually, and in this course, ‘Production System’ means
‘forward chaining’
• Classic system is OPS5
• Basic strategy of KnowledgeWorks
16
Forward Chaining
Fact_1
Fact_1  Fact_2
rules
Fact_3  Fact_4
Direction of reasoning
Fact_2  Fact_3
Fact_4  Fact_5
Action=Fact_5
17
Consider
R1: IF sky=cloudy THEN expect=rain
R2: IF expect=?X THEN weather=?X
R3: IF sky=cloudy AND temperature=freezing
THEN expect=snow
R4: IF weather=rain THEN termperature=above_freezing
What happens if ‘sky=cloudy’?
What happens if ‘sky=cloudy and
‘temperature=freezing’?
Conflict Resolution
18
Production system interpreter
• Objectives:
– Fire rules as the facts come in to the knowledge base
– Never fire a rule unless its conditions are satisfied
– Fire every rule whose conditions are satisfied
• Are these objectives consistent.
– Forward chaining rules sometimes called ‘demons’
» From a system called “Pandemonium”
– How can they be made consistent?
19
Production System Strategy
• All rules tested at each cycle
• Only one rule fires at a time
20
Production System Cycle
1
2
3
4
5
6
Test all rules
Put all rules satisfied into the ‘conflict set’
Choose one rule from the conflict set
Fire the rule
Update the dynamic database
Repeat until goal reached or no more rules
satisfied
21
Conflict Resolution
R1: IF sky=cloudy THEN expect=rain
R2: IF expect=?X THEN weather=?X
R3: IF sky=cloudy AND temperature=freezing
THEN expect=snow
R4: IF weather=rain THEN termperature=above_freezing
What happens if ‘sky=cloudy’?
What happens if ‘sky=cloudy and
‘temperature=freezing’?
22
Possible Conflict Resolution
Strategies
•
•
•
•
•
Specificity
Priority
Lexical Ordering
Source file ordering
Explicit rules for conflict resolution
– a rule based system within a rule based system
23
Basic Production System
Architecture
Dynamic Memory
execute
tickle
Rule Execution
Rule Store
Select
(resolve conflicts)
check satisfaction
Conflict Set
24
Modules (Contexts) & Agendas
• How to modularise RBSs
• Agenda = Sequence of modules (Stack)
• Module = Named Set of rules
– (Rule MODULE::rule_name
IF ...THEN...)
• Contexts popped off stack when finished.
25
Agenda/Modules Example
• focus
search stuck
• defrule search::r1
IF
hero is at ?Place-1 &
?Place-1 gives_access_to ?Place-2
THEN
move hero to ?Place-2
• defrule stuck::r1
IF
context stuck &
hero is at ?Place
not ?Place = goal
THEN
ask-user “What do I do now?”
26
Expert Systems
Configuring systems
• defrule
IF
AND
THEN
• defrule
IF
AND
AND
THEN
AND
BACKPLANE_STRUCTURE::R1
the_processor IS in place
the_devices_to_mount INCLUDE
?Device
mount ?Device
BACKPLANE_STRUCTURE::R1
mount ?Device
?Slot_1 IS_A backplane_slot
NOT lower_number_available_than
?Slot_1 ?Slot_2
?Slot_1 is_occupied_by ?Device
?Device is_mounted.
27
The Structure of Heuristics
• Trigger
• Constraints
• Antecedents
• Actions
• Conclusions
• Control
28
Formalising Heuristics
• Triggers
– quick & sensitive
• Constraints
– quick & specific
• Antecedents
– complete and sufficient
• Actions
• Conclusions
• Control
29
Formalising Heuristics
• Triggers
• Constraints
• Antecedents
• Actions
– Things effecting the outside world
• Conclusions
– New facts for the dynamic data base
• Control
– changes to agenda
30