Transcript lection4-1-Rule-Based_Expert_Systems_and_the_MYCIN_Project

Diagnostic Systems (I):
Rule-Based Expert Systems
and the MYCIN Project
Rule-Based Expert Systems:
Suitable Domains
• Many Rules
• No Unifying Theorem
• Knowledge can be easily separated from the way
it is used
• Updating the knowledge base has to be easy
• The knowledge base can be the only [indirect]
communication channel among rules
• Clinical/psychological and other domains, rather
than mathematical/physical domains
MYCIN: The Problem
• Roberts & Visconti [1972]:
– Only 13% of patients are treated rationally
– 66% are being given irrational treatment
– 21% are being given questionable treatment
• Irrationality means, for example:
– Using a contra-indicated combination
– Using the wrong agent for a specific organism
– Not taking the required cultures
Stages in Diagnosis and Treatment
• Decide if there is a significant infection
• Identify the causing organism(s) by clinical
and laboratory evidence
• Decide what antibiotic agent the organisms
are sensitive to
• Prescribe the optimal drug combination for
the particular case
A MYCIN
Runtime
Example
The MYCIN Architecture
Consultation
program
Dynamic
patient data
Infectious
diseases expert
Explanation
program
Knowledge-acquisition
program
Physician
user
Static factual &
judgmental
knowledge
The Knowledge Base
• Inferential knowledge stored in decision rules
– If Premise then Action (Certainty Factor [CF])
– If A&B then C (0.6)
– The CF represents the inferential certainty
• Static knowledge:
– Natural language dictionary
– Lists (e.g., Sterile Sites)
– Tables (e.g., gram stain, morphology, aerobicity)
• Dynamic knowledge stored in the context tree
–
–
–
–
Patient specific
Hierarchical structures: Patient, cultures, organisms
<Object, Attribute, Value> triples: <Org1, Identity, Strep>
A CF used for factual certainty <Org1, Identity, Staph, 0.6>
Example of a Decision Rule
RULE-507
IF:
1. The infection which requires therapy is
meningitis
2. Organisms were not seen on the stain of the
culture
3. The type of the infection is bacterial
4. The patient does not have a head injury
defect
5. The age of the patient is between 15 and 55
years
Then:
The organisms that might be causing the
infection are diplococcus-pneumoniae and
neisseria-meningitidis
A Sample Context Tree
The Rule Interpreter
• Control structure: goal driven, backward chaining
• Attempt to establish values of clinical parameters at
the leaf nodes
• The interpreter retrieves a list of rules whose
conclusions bear on current goals, and tries to
evaluate these rules
• Questions are asked only when the rules fail to
deduce the necessary information
• If the user cannot supply the information, the rule is
ignored
The Goal Rule
RULE-092
IF:
1.
2.
There is an organism which requires therapy
Consideration has been given to the possible
existence of additional organisms requiring therapy,
even though they have not actually been recovered
from any current cultures
Then: Do the following:
1.
2.
Compile the list of possible therapies which, based
upon sensitivity data, may be effective against the
organisms requiring treatment
Determine the best therapy recommendations from the
compiled list
Else:
Indicate that the patient does not require therapy
A MYCIN Reasoning Tree
The Main MYCIN Algorithm
-Uses Monitor and FindOut to
recursively invoke each rule when
relevant
The Monitor Mechanism
The FindOut Mechanism
Certainty Factors
• Not a Bayesian probability measure, but rather a Certainty Factor
(CF) with its update functions
• A Conclude function uses
–
–
–
–
–
The CF of the rule used for making the inference
The minimal CF of the premises (using the Tally function)
The context node about which the conclusion is made
The clinical parameter whose value is added to the dynamic DB
The value of the clinical parameter
• Conclude derives a conclusion including the CF of the result
– E.g., “There is suggestive evidence (0.7) that the identity of the organism is
streptococcus”
– The CF is mapped into English
• The CF of a context is updated by other evidence (relevant rules)
• It is always true that -1 ≤ CF ≤ +1
• If CF = +1 then all other hypotheses are rejected
Question Answering
• General question answering module
– Used after a consultation regarding any aspect of it
– General questions about the knowledge base (e.g., “is
blood a sterile site?”)
– Uses a simple keyword pattern-matching approach
• Online reasoning status checker provided during
consultation
– A limited set of explanations for the reasoning line
– HOW: recapitulates all relevant successful rules used on
the path to the conclusion asked about
– WHY: backtracks to the reason that a question (a
particular bit of information) was asked
Example: The WHY Explanation Capability
In this series, how many of the cultures were positive for the e.coli
{typical system prompt}
(ORGANISM-1)?
—WHY
{request from user to determine motivation for question}
[i.e. WHY is it important to determine the number of cultures which
{system’s rephrasing of the WHY question, were
positive for the organism?]
and answer}
[1.0] This will help to determine whether there is significant disease
associated with this occurrence of the organism.
It has already been established that
[1.1] the culture was taken from a sterile source
[1.2] the number of cultures in the series is greater than 2
Therefore, if
[1.3] the number of cultures which were positive for ORGANISM-1
is greater than 2
Then there is suggestive evidence (.5) that there is significant disease
associated with this occurrence of the e.coli (ORGANISM-1).
[RULE049]
— WHY
{repeated WHY to determine relevance of previous explanation}
[i.e. WHY is it important to determine if there is significant disease associated with this occurrence of the organism?]
[2.0] This will help to determine a diagnosis for which the infection should be treated.
it has already been established that
[2.1] the infection is not one of: primary-bacteremia meningitis
[2.21 for some current culture of the patient it is true that the site of the culture is blood
Therefore, if
[2.3] there is significant disease associated with this occurrence of the organism
Then
it is definite (1.0) that the diagnosis for which the infection should be treated is secondary-bacteremia
[RULE103]
Knowledge Acquisition
• The knowledge base (KB) has to be modified and
expanded continuously
– The knowledge-acquisition (KA) bottleneck
• The TEIRESIAS module enabled interactive KA
from medical experts
– Included a rule model for different types of rules, which
creates expectations about the structure of the acquired
rule
– A new or old rule can be created or modified
interactively using meta-knowledge about rule models
– KA important also in the context of a reasoning error
Therapy Selection
• Originally a combination of Therapy Rules and a
LISP procedure
– A list of potential therapies is created
– The best combination of drugs is selected
• Resulted in a context tree of possible therapies under
the “current organism” node
• Replaced by a clearer version enabling explicit
explanations, as well as optimal therapy, using a
Plan, Generate, and Test strategy
– more appropriate, since the therapy-planning task is really
a configuration task
Improved Therapy Selection
• Plan by re-ranking the potential drugs, using local factors (e.g.,
organism sensitivity, drug toxicity, current therapy continuity)
• Propose a recommendation and Test it, using global factors (e.g.,
minimize total number of drugs)
– Proposals are managed using a canonical instruction set
– Testing uses rules to check for proper coverage, unique drug classes, and
patient-specific recommendations
– The first satisfactory proposal is chosen
• Prescribe final recommendation
– Uses algorithmic dosage calculation and patient-specific adjustment
Clinical Evaluation of MYCIN
[Yu et al., Comp. Prog. Biomed. 9, 1979]
•
•
Objective assessment of the basic (bacteremia)
system
Examined the main three decision-making steps:
1. Decide if there is a significant organism
2. Determine organism identity
3. Recommend therapy, including alternatives
The Evaluation Method
• 15 patients with positive blood cultures (at
least one organism)
• 5 Stanford infectious disease experts
• 5 experts from other hospitals
• All data recorded and given, if asked for, by
the computer or a human expert
• All decisions by the computer or the experts
recorded, including the majority opinion
Results of the Evaluation Study
•
Significant-organism decision:
– MYCIN decided identically in 97% of the 150 (15x10) decisions
– MYCIN decided identically in 1000% of the 15 majority decisions
•
Organism-identification decision:
– MYCIN identified 45 organisms in the 11 cases requiring therapy, thus 450 (45x10) organism
judgements
– Agreement in 80% of Stanford experts’ judgements, 72% of others
– Agreement by the majority of experts: 90%
•
Treatment decision: treatment was suggested to all 11 patients requiring it, thus 110
(11x10) decision instances to compare
–
–
–

•
•
Agreement with MYCIN’s recommendation was 76% for Stanford experts, 69% for the others
Agreement by a majority: 90% for Stanford experts, 73% for the others
In one case, agreement of 4/5 Stanford experts, disagreement of 4/5 others!
the KB represented well the Stanford prescription habits
Overall “acceptable” performance was rated in 93% (14/15) of cases
Several design problems, such as unblinded evaluation of the program’s and experts’
performance, were corrected in a later study
•
MYCIN was actually ranked best, relative to all other experts, in a blinded evaluation
Summary: Rule-Based Expert
Systems and the MYCIN Project
•
•
Task: Diagnosis and treatment of infectious diseases
Problem solving method: Heuristic Classification [Clancey, 1985]
– Data->Abstracted data=>Abstracted solutions->Solutions
•
•
Implementation: Backward-chaining production rules
Evaluation results: Surprisingly good for a research tool
– Different evaluation by Stanford and Other experts stems probably from different local
practices. This might be actually considered as a representational success. (Rules and tables
can be modified easily).
•
•
•
•
•
•
Many technical and conceptual problems prevented clinical use (small memory, slow
CPU, medical DB communication problems, stand-alone system, etc.), several of which
are now solvable
At the time of the first study, MYCIN rules included only bacteremia (meningitis and
endocarditis were added later), thus never tested in a real clinical environment with
general infections
Practically no temporal reasoning
Implicit control — hard to modify
Probabilistic model was not Bayesian and not intuitive
The knowledge-acquisition bottleneck remained significant