Transcript SYSTEM - CE Sharif

Backward-Chaining
Rule-Based Systems
Elnaz Nouri
December 2007
1
Chapter 7 overview:


Introduction
Medical consultation systems




Automobile Diagnostic System


Example 1:Meningitis Diagnosis Expert System
Example 2:Meningitis Prescription Expert System
Example 3:Alternative Prescription Expert System
Example 4:Automobile Diagnostic via a Blackboard
Summary
2
Introduction


The principle objective of backward chaining
is to prove some goal or hypothesis
The process begins by collecting GOAL RULES



Goal Rules contain the goal proven in their
THEN part
The premise of the goal rules may be supported
by other rules, so they are set as Sub-Goals
The inference engine searches through the
system’s rules in a recursive fashion.
3



Backward Chaining inference engine will reach
some premise that is not supported by any of the
system’s rules (a Primitive)  Ask User
The answer is placed in the current memory
The process continue until all goals and
sub-goals are searched  memory contains
all information provided by user and
inferred by rules.
4
Medical Consultation Systems



Like MYCIN , performs diagnosis for
infectious blood diseases
Unlike MYCIN , doesn’t identify
organ but rather the nature of the
infection
3 different expert systems:
Diagnosis, Prescription, Prescription
Changes
5
Design Suggestion

Divide Complex problems into
smaller tasks and design system for
each task.
6
Example 1:
Megningitis Diagnosis Expert System

The system has only one goal :
Prove or disprove “Infection is meningitis”

One Goal rule : RULE 1
This can be proven if the user already
knows that the patient has meningitis or
the system can infer it.


RULE 2,3,4 : search the test results
RULE 5 : searches the area of patient
symptoms
7
Meningitis diagnosis rules
8
Medical Diagnosis Example Session


Begins with empty working memory
STEP 1:
Find rules with hypothesis in “THEN”
part


STEP 2:
see if first premise in RULE 1 is
listed in working memory


RULE 1
NO
STEP 3:
see if this premise exists in “THEN”
part of any rule

NO
9

STEP 4:
This premise is a primitive




STEP 5:
look at second premise in RULE 1
and see if it’s in working memory


Question : “Do you know if patient has
Meningitis ?”
Answer : NO
Working Memory: Patient known to have
Meningitis - FALSE
NO
STEP 6:
see if this premise exists in “THEN”
part of any rule

RULE 2
10

STEP 7: see if first premise in RULE 2 is listed in
working memory


STEP 8: see if this premise exists in “THEN” part of
any rule




NO
STEP 9:
RULE 3
Q: Were test run?
USER: YES
STEP 10: Q: Were cultures seen?
USER:YES
STEP 11: Q: The appearance of the culture is
coccus?
USER: WHY

System: This will aid in determining if cultures look like
Meningitis
11

STEP 11: Q: The appearance of the culture
is
coccus?
USER: WHY


STEP 12: USER : WHY 4.0


System: This will aid in determining if cultures
look like meningitis
RULE 4
STEP 13:


System: This will determining if “we suspect
meningitis from test results”
RULE 3
System: The appearance of the culture is
coccus?
USER: NO
12
Working Memory

Patient known to have meningitis-FALSE

Tests Run-TRUE
Cultures Seen-TRUE

Appearance of cultures is coccus-FALSE


The system was unsuccessful in establishing
meningitis from test results
13

STEP 14: look at second premise in RULE 2
and see if it’s in working memory


STEP 15: see if this premise exists in “THEN”
part of any rule


NO
RULE 5
STEP 16: All premises of RULE 5 are
unknown and primitives Questions


SYSTEM: Has the patient been suffering
persistent headaches?
USER: YES
14





SYSTEM: Has the patient been suffering
dizziness?
USER: YES
SYSTEM: Has the patient been lethargic?
USER: YES
STEP 17: RULE 5 fires RULE 2 fires RULE
1(Goal Rule) fires
SYSTEM: “After considering your info, I
believe the infection is Menningitis.”
15
Example Review








Simple Goal
Simple Questions
Depth First Search
Intelligent User
Safety Net
Ease of Expansion
Documenting of Rules
Inference Network
16
Inference network

Graphical representation of the
systems’ rules with the premises
and conclusions of the rules drawn
as nodes and their supporting
relationships drawn as links
17
18
Example 2: Meningitis Prescription
Expert System


Prescription task: formulate action
needed to correct the fault
Problem Solving Approach :
- The rules are shown in next slide.
- We have one goal to prove :
“Prescription is ? Prescription”
- 2 goal rules : RULES 1 ( higher priority )
and 2
- RULE 3 : patient’s age
19
Meningitis prescription rules
20
Medical Prescription Example Session
The fact that patient has meningitis is known
GOAL : Determine proper series of drugs


STEP 1: Find rules with hypothesis in “THEN” part


RULE 1 and RULE 2
STEP 2: chose RULE 1 because of higher priority
and see if first premise in RULE 1 is listed in working
memory


YES
STEP 3: see if the second premise of RULE 1
exists in working memory

NO
21

STEP 4:
see if this premise exists in “THEN”
part of any rule


STEP 5:
see if this premise of RULE 3 is
listed in working memory


RULE 3
NO
STEP 6:
see if this premise exists in “THEN”
part of any rule

NO
22

STEP 7:
This premise is a primitive



Question : “What is the patient’s age?”
Answer : 8
STEP 8: Rule 3 fires (patient is a child)
 Rule 1 also fires
SYSTEM : “My first recommendation is this :
Ampicillin --- Dose : 3.8 g
Gentamicin --- Dose : 131 mg ”
23

STEP 9:
USER: HOW
SYSTEM : To drive goal ”Prescription is ?
Prescription” I considered:
-RULE1(1.1 is known to be true)
-To drive 1.2 I considered RULE3
-To drive 3.1 I asked you. your answer was 8.
-RULE 3 was concluded.
-RULE 1 was concluded.
24
Example Review




Variable goal
Rule priorities
Accommodating user
Numeric Relationships
25
Example 3: Alternative Prescription
Expert System

Non-Monotonic Reasoning : facts that
are logically dependent on other facts that
have been retracted can be retracted.

Database Access:
- Using existing knowledge
- Using general knowledge
26
Prescription change rules
27
Prescription change functions









Display current drugs
Determine deleted drugs
Determine substituted drugs
Determine if drug is effective
Determine if drug is safe
Compare ages
Try another drug
Remember facts
Recycle
28
Alternative Prescription Example Session


Drug recommendation AMPICILIN-TRUE
Drug recommendation GENTAMICIN-TRUE




GOAL: allow user choose alternative drug
SYSTEM: do you want to consider another
prescription?
USER: YES
SYSTEM: which one do you want to delete?
USER: ampicilin
SYSTEM: what drug do you want to add?
USER: stremptomycin
29


SYSTEM: The requested drug comes from
class AMINOGLYCOSIDES and would not
be effective. you could try another drug.
USER: PENICILIN
SYSTEM: The requested drug comes from
class PENNICILLINS and would be an
effective replacement for AMPICILLIN
which also comes from PENNICILLINS.
30
Example Review




Ease of modification
General knowledge
Monotonic Reasoning
Non-Monotonic Reasoning
31
Automobile Diagnosis System


Design Suggestion: For problems that
require expertise from more than one
individual, develop separate expert
systems that capture the expertise of
each individual.
Blackboard: The mean for infromation
exchange when the ES is designed to
incorporate separate expert modules.
32
Example 4: Automobile Diagnostics
Expert System


Object Attribute Value: allows you
to display to user a menu of
possible values.
Problem Solving Approach :
- Determine problem area
- Determine specific fault
- Determine cost
33
34
Automobile Diagnostics Example Session

SYSTEM:

USER: won’t start
SYSTEM: please tell me whether the starter

USER: does turn
SYSTEM: the engine turns VERY SLOWLY,
please tell me whether the engine
WILL START,WON’T START?
DOES TURN,DOESN’T TURN?
NORMALLY BUT WON’T START?
USER:
normally but won’t start
35

SYSTEM:

SYSTEM:

USER: does move
SYSTEM: The car will START OCCASIONALLY,
I believe the problem might be
with the FUEL SYSTEM. I will check with my
expert in this area.
The fuel gage DOESN’T
MOVE,DOES MOVE?
NEVER STARTS?
USER:
star occasionally
36

SYSTEM:
After working on your problem it is
my belief that your car has problem with the
FUEL SYSTEM.
The specific problem is DIRTY CARBURETOR.
My recommendation is REBUILD THE
CARBURETOR.
The cost for such repair is 100 dollars.
37
Example Review







Separate Systems
Meta Rules
Display of intermediate findings
Blackboard
O-A-V facts
Initializing knowledge
Intelligent Safety Net
38
Summary on Backward Chaining
Expert Systems



BC attempts to prove a goal by
recursively moving back through the rules
in search of supporting evidence
To ease the development and
maintenance of these systems, design
them in modular form
Care should be given to provide clear final
displays and keeping user informed
39




The user should allow user to provide
known information and avoid unnecessary
search by the system
Some intelligent findings should be
provided even if the system is not totally
successful
Database information should be used
Cooperating expert systems modules
communicate over a structure known as
Blackboard
40