An expert is one who knows more and more about less and less.
-Nicholas Murray Butler (1862-1947)
In the 1970s there was terrific interest in the area of knowledge-based expert systems. An expert system or knowledge-based system is one that solves problems by applying knowledge that has been garnered from one or more experts in a field. Since these experts will not in general be programmers, they will very probably express their expertise in terms that cannot immediately be translated into a program. It is the goal of expert-system research to come up with a representation that is flexible enough to handle expert knowledge, but still capable of being manipulated by a computer program to come up with solutions.
A plausible candidate for this representation is as logical facts and rules, as in Prolog. However, there are three areas where Prolog provides poor support for a general knowledge-based system:
-
Reasoning with uncertainty. Prolog only deals with the black-and-white world of facts that are clearly true or false (and it doesn't even handle false very well). Often experts will express rules of thumb that are "likely" or "90% certain."
-
Explanation. Prolog gives solutions to queries but no indication of how those solutions were derived. A system that can explain its solutions to the user in understandable terms will be trusted more.
-
Flexible flow of control. Prolog works by backward-chaining from the goal. In some cases, we may need more varied control strategy. For example, in medical diagnosis, there is a prescribed order for acquiring certain information about the patient. A medical system must follow this order, even if it doesn't fit in with the backward-chaining strategy.
The early expert systems used a wide variety of techniques to attack these problems. Eventually, it became clear that certain techniques were being used frequently, and they were captured in expert-system shells: specialized programming environments that helped acquire knowledge from the expert and use it to solve problems and provide explanations. The idea was that these shells would provide a higher level of abstraction than just Lisp or Prolog and would make it easy to write new expert systems.
The MYCIN expert system was one of the earliest and remains one of the best known. It was written by Dr. Edward Shortliffe in 1974 as an experiment in medical diagnosis. MYCIN was designed to prescribe antibiotic therapy for bacterial blood infections, and when completed it was judged to perform this task as well as experts in the field. Its name comes from the common suffix in drugs it prescribes: erythromycin, clindamycin, and so on. The following is a slightly modified version of one of MYCIN's rules, along with an English paraphrase generated by the system:
(defrule 52
if (site culture is blood)
(gram organism is neg)
(morphology organism is rod)
(burn patient is serious)
then .4
(identity organism is pseudomonas))
Rule 52:
If
1) THE SITE OF THE CULTURE IS BLOOD
2) THE GRAM OF THE ORGANISM IS NEG
3) THE MORPHOLOGY OF THE ORGANISM IS ROD
4) THE BURN OF THE PATIENT IS SERIOUS
Then there is weakly suggestive evidence (0.4) that
1) THE IDENTITY OF THE ORGANISM IS PSEUDOMONASMYCIN lead to the development of the EMYCIN expert-system shell. EMYCIN stands for "essential MYCIN," although it is often mispresented as "empty MYCIN." Either way, the name refers to the shell for acquiring knowledge, reasoning with it, and explaining the results, without the specific medical knowledge.
EMYCIN is a backward-chaining rule interpreter that has much in common with Prolog. However, there are four important differences. First, and most importantly, EMYCIN deals with uncertainty. Instead of insisting that all predications be true or false, EMYCIN associates a certainty factor with each predication. Second, EMYCIN caches the results of its computations so that they need not be duplicated. Third, EMYCIN provides an easy way for the system to ask the user for information. Fourth, it provides explanations of its behavior. This can be summed up in the equation:
EMYCIN = Prolog + uncertainty + caching + questions + explanationsWe will first cover the ways EMYCIN is different from Prolog. After that we will return to the main core of EMYCIN, the backward-chaining rule interpreter. Finally, we will show how to add some medical knowledge to EMYCIN to reconstruct MYCIN. A glossary of the program is in figure 16.1.
 |
| Figure 16.1: Glossary for the EMYCIN Program |
(ed: this could be a markdown table)
EMYCIN deals with uncertainty by replacing the two boolean values, true and false, with a range of values called certainty factors. These are numbers from -1 (false) to +1 (true), with 0 representing a complete unknown. In Lisp:
(defconstant true +1.0)
(defconstant false -1.0)
(defconstant unknown 0.0)To define the logic of certainty factors, we need to define the logical operations, such as and, or, and not. The first operation to consider is the combination of two distinct pieces of evidence expressed as certainty factors.
Suppose we are trying to determine the chances of a patient having disease Χ.
Assume we have a population of prior patients that have been given two lab tests.
One test says that 60% of the patients have the disease and the other says that 40% have it.
How should we combine these two pieces of evidence into one?
Unfortunately, there is no way to answer that question correctly without knowing more about the dependence of the two sources on each other.
Suppose the first test says that 60% of the patients (who all happen to be male) have the disease, and the second says that 40% (who all happen to be female) have it.
Then we should conclude that 100% have it, because the two tests cover the entire population.
On the other hand, if the first test is positive only for patients that are 70 years old or older, and the second is positive only for patients that are 80 or older, then the second is just a subset of the first.
This adds no new information, so the correct answer is 60% in this case.
In section 16.9 we will consider ways to take this kind of reasoning into account. For now, we will present the combination method actually used in EMYCIN. It is defined by the formula:
combine (A, B) =
According to this formula, combine(.60,.40) = .76, which is a compromise between the extremes of .60 and 1.00. It is the same as the probability p(A or B), assuming that A and B are independent.
However, it should be clear that certainty factors are not the same thing as probabilities. Certainty factors attempt to deal with disbelief as well as belief, but they do not deal with dependence and independence. The EMYCIN combination function has a number of desirable properties:
-
It always computes a number between -1 and +1.
-
Combining unknown (zero) with anything leaves it unchanged.
-
Combining true with anything (except false) gives true.
-
Combining true and false is an error.
-
Combining two opposites gives unknown.
-
Combining two positives (except true) gives a larger positive.
-
Combining a positive and a negative gives something in between.
So far we have seen how to combine two separate pieces of evidence for the same hypothesis. In other words, if we have the two rules:
A => C
B => C
and we know A with certainty factor (cf) .6 and B with cf .4, then we can conclude C with cf .76. But consider a rule with a conjunction in the premise:
A and B => C
Combining A and B in this case is quite different from combining them when they are in separate rules. EMYCIN chooses to combine conjunctions by taking the minimum of each conjunct's certainty factor. If certainty factors were probabilities, this would be equivalent to assuming dependence between conjuncts in a rule. (If the conjuncts were independent, then the product of the probabilities would be the correct answer.) So EMYCIN is making the quite reasonable (but sometimes incorrect) assumption that conditions that are tied together in a single rule will be dependent on one another, while conditions in separate rules are independent.
The final complication is that rules themselves may be uncertain. That is, MYCIN accommodates rules that look like:
A and B => .9C
to say that A and B imply C with .9 certainty. EMYCIN simply multiplies the rule's cf by the combined cf of the premise. So if A has cf .6 and B has cf .4, then the premise as a whole has cf .4 (the minimum of A and B), which is multiplied by .9 to get .36. The .36 is then combined with any existing cf for C. If C is previously unknown, then combining .36 with 0 will give .36. If C had a prior cf of .76, then the new cf would be .36 + .76 - (.36 x .76) = .8464.
Here are the EMYCIN certainty factor combination functions in Lisp:
(defun cf-or (a b)
"Combine the certainty factors for the formula (A or B).
This is used when two rules support the same conclusion."
(cond ((and (> a 0) (> b 0))
(+ a b (* -1 a b)))
((and (< a 0) (< b 0))
(+ a b (* a b)))
(t (/ (+ a b)
(- 1 (min (abs a) (abs b)))))))
(defun cf-and (a b)
"Combine the certainty factors for the formula (A and B)."
(min a b))Certainty factors can be seen as a generalization of truth values.
EMYCIN is a backward-chaining rule system that combines certainty factors according to the functions laid out above.
But if we only used the certainty factors true and false, then EMYCIN would behave exactly like Prolog, returning only answers that are definitely true.
It is only when we provide fractional certainty factors that the additional EMYCIN mechanism makes a difference.
Truth values actually serve two purposes in Prolog. They determine the final answer, yes, but they also determine when to cut off search: if any one of the premises of a rule is false, then there is no sense looking at the other premises. If in EMYCIN we only cut off the search when one of the premises was absolutely false, then we might have to search through a lot of rules, only to yield answers with very low certainty factors. Instead, EMYCIN arbitrarily cuts off the search and considers a premise false when it has a certainty factor below .2. The following functions support this arbitrary cutoff point:
(defconstant cf-cut-off 0.2
"Below this certainty we cut off search.")
(defun true-p (cf)
"Is this certainty factor considered true?"
(and (cf-p cf) (> cf cf-cut-off)))
(defun false-p (cf)
"Is this certainty factor considered false?"
(and (cf-p cf) (< cf (- cf-cut-off 1.0))))
(defun cf-p (x)
"Is X a valid numeric certainty factor?"
(and (numberp x) (<= false x true)))Exercise 16.1 [m] Suppose you read the headline "Elvis Alive in Kalamazoo" in a tabloid newspaper to which you attribute a certainty factor of .01. If you combine certainties using EMYCIN's combination rule, how many more copies of the newspaper would you need to see before you were .95 certain Elvis is alive?
The second thing that makes EMYCIN different from Prolog is that EMYCIN caches all the facts it derives in a data base. When Prolog is asked to prove the same goal twice, it performs the same computation twice, no matter how laborious. EMYCIN performs the computation the first time and just fetches it the second time.
We can implement a simple data base by providing three functions: put-db to add an association between a key and a value, get-db to retrieve a value, and clear-db to empty the data base and start over:
(let ((db (make-hash-table :test #'equal)))
(defun get-db (key) (gethash key db))
(defun put-db (key val) (setf (gethash key db) val))
(defun clear-db () (clrhash db)))This data base is general enough to hold any association between key and value.
However, most of the information we will want to store is more specific.
EMYCIN is designed to deal with objects (or instances) and attributes (or parameters) of those objects.
For example, each patient has a name parameter.
Presumably, the value of this parameter will be known exactly.
On the other hand, each microscopic organism has an identity parameter that is normally not known at the start of the consultation.
Applying the rules will lead to several possible values for this parameter, each with its own certainty factor.
In general, then, the data base will have keys of the form (parameter instance) with values of the form ((val1cf1) (val2cf2)...).
In the following code, get-vals returns the list of value/cf pairs for a given parameter and instance, get-cf returns the certainty factor for a parameter/instance/value triplet, and update-cf changes the certainty factor by combining the old one with a new one.
Note that the first time update-cf is called on a given parameter/instance/value triplet, get-cf will return unknown (zero).
Combining that with the given cf yields cf itself.
Also note that the data base has to be an equal hash table, because the keys may include freshly consed lists.
(defun get-vals (parm inst)
"Return a list of (val cf) pairs for this (parm inst)."
(get-db (list parm inst)))
(defun get-cf (parm inst val)
"Look up the certainty factor or return unknown."
(or (second (assoc val (get-vals parm inst)))
unknown))
(defun update-cf (parm inst val cf)
"Change the certainty factor for (parm inst is val),
by combining the given cf with the old."
(let ((new-cf (cf-or cf (get-cf parm inst val))))
(put-db (list parm inst)
(cons (list val new-cf)
(remove val (get-db (list parm inst))
:key #'first)))))The data base holds all information related to an instance of a problem. For example, in the medical domain, the data base would hold all information about the current patient. When we want to consider a new patient, the data base is cleared.
There are three other sources of information that cannot be stored in this data base, because they have to be maintained from one problem to the next.
First, the rule base holds all the rules defined by the expert.
Second, there is a structure to define each parameter; these are indexed under the name of each parameter.
Third, we shall see that the flow of control is managed in part by a list of contexts to consider.
These are structures that will be passed to the MYCIN function.
The third way that EMYCIN differs from Prolog is in providing an automatic means of asking the user questions when answers cannot be derived from the rules. This is not a fundamental difference; after all, it is not too hard to write Prolog rules that print a query and read a reply. EMYCIN lets the knowledge-base designer write a simple declaration instead of a rule, and will even assume a default declaration if none is provided. The system also makes sure that the same question is never asked twice.
The following function ask-vals prints a query that asks for the parameter of an instance, and reads from the user the value or a list of values with associated certainty factors.
The function first looks at the data base to make sure the question has not been asked before.
It then checks each value and certainty factor to see if each is of the correct type, and it also allows the user to ask certain questions.
A ? reply will show what type answer is expected.
Rule will show the current rule that the system is working on.
Why also shows the current rule, but it explains in more detail what the system knows and is trying to find out.
Finally, help prints the following summary:
(defconstant help-string
"~&Type one of the following:
? - to see possible answers for this parameter
rule - to show the current rule
why - to see why this question is asked
help - to see this list
xxx - (for some specific xxx) if there is a definite answer
(xxx .5 yyy .4) - If there are several answers with
different certainty factors.")Here is ask-vals.
Note that the why and rule options assume that the current rule has been stored in the data base.
The functions print-why, parm-type, and check-reply will be defined shortly.
(defun ask-vals (parm inst)
"Ask the user for the value(s) of inst's parm parameter,
unless this has already been asked. Keep asking until the
user types UNKNOWN (return nil) or a valid reply (return t)."
(unless (get-db `(asked ,parm ,inst))
(put-db `(asked ,parm ,inst) t)
(loop
(let ((ans (prompt-and-read-vals parm inst)))
(case ans
(help (format t help-string))
(why (print-why (get-db 'current-rule) parm))
(rule (princ (get-db 'current-rule)))
((unk unknown) (RETURN nil))
(? (format t "~&A ~a must be of type ~a"
parm (parm-type parm)) nil)
(t (if (check-reply ans parm inst)
(RETURN t)
(format t "~&Illegal reply. ~
Type ? to see legal ones."))))))))The following is prompt-and-read-vals, the function that actually asks the query and reads the reply.
It basically calls format to print a prompt and read to get the reply, but there are a few subtleties.
First, it calls finish-output.
Some Lisp implementations buffer output on a line-by-line basis.
Since the prompt may not end in a newline, finish-output makes sure the output is printed before the reply is read.
So far, all the code that refers to a parm is really referring to the name of a parameter-a symbol.
The actual parameters themselves will be implemented as structures.
We use get-parm to look up the structure associated with a symbol, and the selector functions parm-prompt to pick out the prompt for each parameter and parm-reader to pick out the reader function.
Normally this will be the function read, but read-line is appropriate for reading string-valued parameters.
The macro defparm (shown here) provides a way to define prompts and readers for parameters.
(defun prompt-and-read-vals (parm inst)
"Print the prompt for this parameter (or make one up) and
read the reply."
(fresh-line)
(format t (parm-prompt (get-parm parm)) (inst-name inst) parm)
(princ " ")
(finish-output)
(funcall (parm-reader (get-parm parm))))
(defun inst-name (inst)
"The name of this instance."
;; The stored name is either like (("Jan Doe" 1.0)) or nil
(or (first (first (get-vals 'name inst)))
inst))The function check-reply uses parse-reply to convert the user's reply into a canonical form, and then checks that each value is of the right type, and that each certainty factor is valid.
If so, the data base is updated to reflect the new certainty factors.
(defun check-reply (reply parm inst)
"If reply is valid for this parm, update the DB.
Reply should be a val or (val1 cf1 val2 cf2 ...).
Each val must be of the right type for this parm."
(let ((answers (parse-reply reply)))
(when (every #'(lambda (pair)
(and (typep (first pair) (parm-type parm))
(cf-p (second pair))))
answers)
;; Add replies to the data base
(dolist (pair answers)
(update-cf parm inst (first pair) (second pair)))
answers)))
(defun parse-reply (reply)
"Convert the reply into a list of (value cf) pairs."
(cond ((null reply) nil)
((atom reply) `((,reply ,true)))
(t (cons (list (first reply) (second reply))
(parse-reply (rest2 reply))))))Parameters are implemented as structures with six slots: the name (a symbol), the context the parameter is for, the prompt used to ask for the parameter's value, a Boolean that tells if we should ask the user before or after using rules, a type restriction describing the legal values, and finally, the function used to read the value of the parameter.
Parameters are stored on the property list of their names under the parm property, so getting the parm-type of a name requires first getting the parm structure, and then selecting the type restriction field.
By default, a parameter is given type t, meaning that any value is valid for that type.
We also define the type yes/no, which comes in handy for Boolean parameters.
We want the default prompt to be "What is the PARM of the INST?" But most user-defined prompts will want to print the inst, and not the parm.
To make it easy to write user-defined prompts, prompt-and-read-vals makes the instance be the first argument to the format string, with the parm second.
Therefore, in the default prompt we need to use the format directive "~*" to skip the instance argument, and "~2:*" to back up two arguments to get back to the instance.
(These directives are common in cerror calls, where one list of arguments is passed to two format strings.)
defparm is a macro that calls new-parm, the constructor function defined in the parm structure, and stores the resulting structure under the parm property of the parameter's name.
(defstruct (parm (:constructor
new-parm (name &optional context type-restriction
prompt ask-first reader)))
name (context nil) (prompt "~&What is the ~*~a of ~2:*~a?")
(ask-first nil) (type-restriction t) (reader 'read))
(defmacro defparm (parm &rest args)
"Define a parameter."
`(setf (get ',parm 'parm) (apply #'new-parm ',parm ',args)))
(defun parm-type (parm-name)
"What type is expected for a value of this parameter?"
(parm-type-restriction (get-parm parm-name)))
(defun get-parm (parm-name)
"Look up the parameter structure with this name."
;; If there is none, make one
(or (get parm-name 'parm)
(setf (get parm-name 'parm) (new-parm parm-name))))
(deftype yes/no () '(member yes no))Earlier we gave an equation relating EMYCIN to Prolog. That equation was not quite correct, because EMYCIN lacks one of Prolog's most important features: the logic variable. Instead, EMYCIN uses contexts. So the complete equation is:
EMYCIN = Prolog + uncertainty + caching + questions + explanations + contexts - variables
A context is defined by the designers of MYCIN as a situation within which the program reasons. But it makes more sense to think of a context simply as a data type. So the list of contexts supplied to the program will determine what types of objects can be reasoned about. The program keeps track of the most recent instance of each type, and the rules can refer to those instances only, using the name of the type. In our version of MYCIN, there are three types or contexts: patients, cultures, and organisms. Here is an example of a rule that references all three contexts:
(defrule 52
if (site culture is blood)
(gram organism is neg)
(morphology organism is rod)
(burn patient is serious)
then .4
(identity organism is pseudomonas))Ignoring certainty factors for the moment, this MYCIN rule is equivalent to a Prolog rule of the form:
(<- (identity ?o ?pseudomonas)
(and (culture` ?c) `(site ?c blood)
(organism ?o) (gram ?o neg) (morphology ?o rod)
(patient ?p) (burn ?p serious)))The context mechanism provides sufficient flexibility to handle many of the cases that would otherwise be handled by variables. One important thing that cannot be done is to refer to more than one instance of the same context. Only the most recent instance can be referred to. Contexts are implemented as structures with the following definition:
(defstruct context
"A context is a sub-domain, a type."
name (number 0) initial-data goals)
(defmacro defcontext (name &optional initial-data goals)
"Define a context."
`(make-context :name ',name :initial-data ',initial-data
:goals ',goals))The name field is something like patient or organism. Instances of contexts are numbered; the number field holds the number of the most recent instance.
Each context also has two lists of parameters.
The initial-data parameters are asked for when each instance is created.
Initial data parameters are normally known by the user.
For example, a doctor will normally know the patient's name, age, and sex, and as a matter of training expects to be asked these questions first, even if they don't factor into every case.
The goal parameters, on the other hand, are usually unknown to the user.
They are determined through the backward-chaining process.
The following function creates a new instance of a context, writes a message, and stores the instance in two places in the data base: under the key current-instance, and also under the name of the context.
The contexts form a tree.
In our example, the patient context is the root of the tree, and the current patient is stored in the data base under the key patient. The next level of the tree is for cultures taken from the patient; the current culture is stored under the culture key.
Finally, there is a level for organisms found in each culture.
The current organism is stored under both the organism and current-instance keys.
The context tree is shown in figure 16.2.
 |
| Figure 16.2: A Context Tree |
(defun new-instance (context)
"Create a new instance of this context."
(let ((instance (format nil "~a-~d"
(context-name context)
(incf (context-number context)))))
(format t "~&------ ~a ------~&" instance)
(put-db (context-name context) instance)
(put-db 'current-instance instance)))Now that we have seen how EMYCIN is different from Prolog, we are ready to tackle the way in which it is the same: the backward-chaining rule interpreter. Like Prolog, EMYCIN is given a goal and applies rules that are appropriate to the goal. Applying a rule means treating each premise of the rule as a goal and recursively applying rules that are appropriate to each premise.
There are still some remaining differences.
In Prolog, a goal can be any expression, and appropriate rules are those whose heads unify with the goal.
If any appropriate rule succeeds, then the goal is known to be true.
In EMYCIN, a rule might give a goal a certainty of .99, but we still have to consider all the other rules that are appropriate to the goal, because they might bring the certainty down below the cutoff threshold.
Thus, EMYCIN always gathers all evidence relating to a parameter/instance pair first, and only evaluates the goal after all the evidence is in.
For example, if the goal was (temp patient > 98.6), EMYCIN would first evaluate all rules with conclusions about the current patient's temperature, and only then compare the temperature to 98.6.
Another way of looking at it is that Prolog has the luxury of searching depth-first, because the semantics of Prolog rules is such that if any rule says a goal is true, then it is true. EMYCIN must search breadth-first, because a goal with certainty of .99 might turn out to be false when more evidence is considered.
We are now ready to sketch out the design of the EMYCIN rule interpreter: To find-out a parameter of an instance: If the value is already stored in the data base, use the known value.
Otherwise, the two choices are using the rules or asking the user.
Do these in the order specified for this parameter, and if the first one succeeds, don't bother with the second.
Note that ask-vals (defined above) will not ask the same question twice.
To use-rules, find all the rules that concern the given parameter and evaluate them with use-rule.
After each rule has been tried, if any of them evaluate to true, then succeed.
To use-rule a rule, first check if any of the premises can be rejected outright.
If we did not have this check, then the system could start asking the user questions that were obviously irrelevant.
So we waste some of the program's time (checking each premise twice) to save the more valuable user time.
(The function eval-condition takes an optional argument specifying if we should recursively ask questions in trying to accept or reject a condition.)
If no premise can be rejected, then evaluate each premise in turn with evaluate-condition, keeping track of the accumulated certainty factor with cf-and (which is currently just min), and cutting off evaluation when the certainty factor drops below threshold.
If the premises evaluate true, then add the conclusions to the data base.
The calling sequence looks like this.
Note that the recursive call to find-out is what enables chaining to occur:
find-out ; To find out a parameter for an instance:
get-db ; See if it is cached in the data base
ask-vals ; See if the user knows the answer
use-rules ; See if there is a rule for it:
reject-premise ; See if the rule is outright false
satisfy-premises ; Or see if each condition is true:
eval-condition ; Evaluate each condition
find-out ; By finding the parameter's valuesBefore showing the interpreter, here is the structure definition for rules, along with the functions to maintain a data base of rules:
(defstruct (rule (:print-function print-rule))
number premises conclusions cf)
(let ((rules (make-hash-table)))
(defun put-rule (rule)
"Put the rule in a table, indexed under each
parm in the conclusion."
(dolist (concl (rule-conclusions rule))
(push rule (gethash (first concl) rules)))
rule)
(defun get-rules (parm)
"A list of rules that help determine this parameter."
(gethash parm rules))
(defun clear-rules () (clrhash rules)))Here, then, is the interpreter, find-out.
It can find out the value(s) of a parameter three ways.
First, it looks to see if the value is already stored in the data base.
Next, it tries asking the user or using the rules.
The order in which these two options are tried depends on the parm-ask-first property of the parameter.
Either way, if an answer is determined, it is stored in the data base.
(defun find-out (parm &optional (inst (get-db 'current-instance)))
"Find the value(s) of this parameter for this instance,
unless the values are already known.
Some parameters we ask first; others we use rules first."
(or (get-db `(known ,parm ,inst))
(put-db `(known ,parm ,inst)
(if (parm-ask-first (get-parm parm))
(or (ask-vals parm inst) (use-rules parm))
(or (use-rules parm) (ask-vals parm inst))))))
(defun use-rules (parm)
"Try every rule associated with this parameter.
Return true if one of the rules returns true."
(some #'true-p (mapcar #'use-rule (get-rules parm))))
(defun use-rule (rule)
"Apply a rule to the current situation."
;; Keep track of the rule for the explanation system:
(put-db 'current-rule rule)
;; If any premise is known false, give up.
;; If every premise can be proved true, then
;; draw conclusions (weighted with the certainty factor).
(unless (some #'reject-premise (rule-premises rule))
(let ((cf (satisfy-premises (rule-premises rule) true)))
(when (true-p cf)
(dolist (conclusion (rule-conclusions rule))
(conclude conclusion (* cf (rule-cf rule))))
cf))))
(defun satisfy-premises (premises cf-so-far)
"A list of premises is satisfied if they are all true.
A combined cf is returned."
;; cf-so-far is an accumulator of certainty factors
(cond ((null premises) cf-so-far)
((not (true-p cf-so-far)) false)
(t (satisfy-premises
(rest premises)
(cf-and cf-so-far
(eval-condition (first premises)))))))The function eval-condition evaluates a single condition, returning its certainty factor.
If find-out-p is true, it first calls find-out, which may either query the user or apply appropriate rules.
If find-out-p is false, it evaluates the condition using the current state of the data base.
It does this by looking at each stored value for the parameter/instance pair and evaluating the operator on it.
For example, if the condition is (temp patient > 98.6)) and the values for temp for the current patient are ((98 .3) (99 .6) (100 .1)), then eval-condition will test each of the values 98, 99, and 100 against 98.6 using the > operator.
This test will succeed twice, so the resulting certainty factor is .6 + .1 = .7.
The function reject-premise is designed as a quick test to eliminate a rule.
As such, it calls eval-condition with find-out-p nil, so it will reject a premise only if it is clearly false without seeking additional information.
If a rule's premises are true, then the conclusions are added to the data base by conclude.
Note that is is the only operator allowed in conclusions, is is just an alias for equal.
(defun eval-condition (condition &optional (find-out-p t))
"See if this condition is true, optionally using FIND-OUT
to determine unknown parameters."
(multiple-value-bind (parm inst op val)
(parse-condition condition)
(when find-out-p
(find-out parm inst))
;; Add up all the (val cf) pairs that satisfy the test
(loop for pair in (get-vals parm inst)
when (funcall op (first pair) val)
sum (second pair))))
(defun reject-premise (premise)
"A premise is rejected if it is known false, without
needing to call find-out recursively."
(false-p (eval-condition premise nil)))
(defun conclude (conclusion cf)
"Add a conclusion (with specified certainty factor) to DB."
(multiple-value-bind (parm inst op val)
(parse-condition conclusion)
(update-cf parm inst val cf)))
(defun is (a b) (equal a b))All conditions are of the form: (parameter instance operator value).
For example: (morphology organism is rod).
The function parse-condition turns a list of this form into four values.
The trick is that it uses the data base to return the current instance of the context, rather than the context name itself:
(defun parse-condition (condition)
"A condition is of the form (parm inst op val).
So for (age patient is 21), we would return 4 values:
(age patient-1 is 21), where patient-1 is the current patient."
(values (first condition)
(get-db (second condition))
(third condition)
(fourth condition)))At this point a call like (find-out 'identity 'organism-1) would do the right thing only if we had somehow entered the proper information on the current patient, culture, and organism.
The function get-context-data makes sure that each context is treated in order.
First an instance is created, then find-out is used to determine both the initial data parameters and the goals.
The findings for each goal are printed, and the program asks if there is another instance of this context.
Finally, we also need a top-level function, emycin, which just clears the data base before calling get-context-data.
(defun emycin (contexts)
"An Expert System Shell. Accumulate data for instances of each
context, and solve for goals. Then report the findings."
(clear-db)
(get-context-data contexts))
(defun get-context-data (contexts)
"For each context, create an instance and try to find out
required data. Then go on to other contexts, depth first,
and finally ask if there are other instances of this context."
(unless (null contexts)
(let* ((context (first contexts))
(inst (new-instance context)))
(put-db 'current-rule 'initial)
(mapc #'find-out (context-initial-data context))
(put-db 'current-rule 'goal)
(mapc #'find-out (context-goals context))
(report-findings context inst)
(get-context-data (rest contexts))
(when (y-or-n-p "Is there another ~a?"
(context-name context))
(get-context-data contexts)))))At this point all the serious computational work is done: we have defined a backward-chaining rule mechanism that deals with uncertainty, caching, questions, and contexts. But there is still quite a bit of work to do in terms of input/output interaction. A programming language needs only to interface with programmers, so it is acceptable to make the programmer do all the work. But an expert-system shell is supposed to alleviate (if not abolish) the need for programmers. Expert-system shells really have two classes of users: the experts use the shell when they are developing the system, and the end users or clients use the resulting expert system when it is completed. Sometimes the expert can enter knowledge directly into the shell, but more often it is assumed the expert will have the help of a knowledge engineer-someone who is trained in the use of the shell and in eliciting knowledge, but who need not be either an expert in the domain or an expert programmer.
In our version of EMYCIN, we provide only the simplest tools for making the expert's job easier.
The macros defcontext and defparm, defined above, are a little easier than calling make-context and make-parm explicitly, but not much.
The macro defrule defines a rule and checks for some obvious errors:
(defmacro defrule (number &body body)
"Define a rule with conditions, a certainty factor, and
conclusions. Example: (defrule R001 if ... then .9 ...)"
(assert (eq (first body) 'if))
(let* ((then-part (member 'then body))
(premises (ldiff (rest body) then-part))
(conclusions (rest2 then-part))
(cf (second then-part)))
;; Do some error checking:
(check-conditions number premises 'premise)
(check-conditions number conclusions 'conclusion)
(when (not (cf-p cf))
(warn "Rule ~a: Illegal certainty factor: ~a" number cf))
;; Now build the rule:
`(put-rule
(make-rule :number ',number :cf ,cf :premises ',premises
:conclusions ',conclusions))))The function check-conditions makes sure that each rule has at least one premise and conclusion, that each condition is of the right form, and that the value of the condition is of the right type for the parameter.
It also checks that conclusions use only the operator is:
(defun check-conditions (rule-num conditions kind)
"Warn if any conditions are invalid."
(when (null conditions)
(warn "Rule ~a: Missing ~a" rule-num kind))
(dolist (condition conditions)
(when (not (consp condition))
(warn "Rule ~a: Illegal ~a: ~a" rule-num kind condition))
(multiple-value-bind (parm inst op val)
(parse-condition condition)
(declare (ignore inst))
(when (and (eq kind 'conclusion) (not (eq op 'is)))
(warn "Rule ~a: Illegal operator (~a) in conclusion: ~a"
rule-num op condition))
(when (not (typep val (parm-type parm)))
(warn "Rule ~a: Illegal value (~a) in ~a: ~a"
rule-num val kind condition)))))The real EMYCIN had an interactive environment that prompted the expert for each context, parameter, and rule. Randall Davis (1977, 1979, Davis and Lenat 1982) describes the TEIRESIAS program, which helped experts enter and debug rules.
Once the knowledge is in, we need some way to get it out.
The client wants to run the system on his or her own problem and see two things: a solution to the problem, and an explanation of why the solution is reasonable.
EMYCIN provides primitive facilities for both of these.
The function report-findings prints information on all the goal parameters for a given instance:
(defun report-findings (context inst)
"Print findings on each goal for this instance."
(when (context-goals context)
(format t "~&Findings for ~a:" (inst-name inst))
(dolist (goal (context-goals context))
(let ((values (get-vals goal inst)))
;; If there are any values for this goal,
;; print them sorted by certainty factor.
(if values
(format t "~& ~a:~{~{ ~a (~,3f) ~}~}" goal
(sort (copy-list values) #'> :key #'second))
(format t "~& ~a: unknown" goal))))))The only explanation facility our version of EMYCIN offers is a way to see the current rule.
If the user types rule in response to a query, a pseudo-English translation of the current rule is printed.
Here is a sample rule and its translation:
(defrule 52
if (site culture is blood)
(gram organism is neg)
(morphology organism is rod)
(burn patient is serious)
then .4
(identity organism is pseudomonas))
Rule 52:
If
1) THE SITE OF THE CULTURE IS BLOOD
2) THE GRAM OF THE ORGANISM IS NEG
3) THE MORPHOLOGY OF THE ORGANISM IS ROD
4) THE BURN OF THE PATIENT IS SERIOUS
Then there is weakly suggestive evidence (0.4) that
1) THE IDENTITY OF THE ORGANISM IS PSEUDOMONASThe function print-rule generates this translation:
(defun print-rule (rule &optional (stream t) depth)
(declare (ignore depth))
(format stream "~&Rule ~a:~& If" (rule-number rule))
(print-conditions (rule-premises rule) stream)
(format stream "~& Then ~a (~a) that"
(cf->english (rule-cf rule)) (rule-cf rule))
(print-conditions (rule-conclusions rule) stream))
(defun print-conditions (conditions &optional
(stream t) (num 1))
"Print a list of numbered conditions."
(dolist (condition conditions)
(print-condition condition stream num)))
(defun print-condition (condition stream number)
"Print a single condition in pseudo-English."
(format stream "~& ~d)~{ ~a~}" number
(let ((parm (first condition))
(inst (second condition))
(op (third condition))
(val (fourth condition)))
(case val
(YES `(the ,inst ,op ,parm))
(NO `(the ,inst ,op not ,parm))
(T `(the ,parm of the ,inst ,op ,val))))))
(defun cf->english (cf)
"Convert a certainy factor to an English phrase."
(cond ((= cf 1.0) "there is certain evidence")
((> cf .8) "there is strongly suggestive evidence")
((> cf .5) "there is suggestive evidence")
((> cf 0.0) "there is weakly suggestive evidence")
((= cf 0.0) "there is NO evidence either way")
((< cf 0.0) (concatenate 'string (cf->english (- cf))
" AGAINST the conclusion"))))If the user types why in response to a query, a more detailed account of the same rule is printed.
First, the premises that are already known are displayed, followed by the remainder of the rule.
The parameter being asked for will always be the first premise in the remainder of the rule.
The current-rule is stored in the data base by use-rule whenever a rule is applied, but it is also set by get-context-data to the atom initial or goal when the system is prompting for parameters.
print-why checks for this case as well.
Note the use of the partition-if function from page 256.
(defun print-why (rule parm)
"Tell why this rule is being used. Print what is known,
what we are trying to find out, and what we can conclude."
(format t "~&[Why is the value of ~a being asked for?]" parm)
(if (member rule '(initial goal))
(format t "~&~a is one of the ~a parameters."
parm rule)
(multiple-value-bind (knowns unknowns)
(partition-if #'(lambda (premise)
(true-p (eval-condition premise nil)))
(rule-premises rule))
(when knowns
(format t "~&It is known that:")
(print-conditions knowns)
(format t "~&Therefore,"))
(let ((new-rule (copy-rule rule)))
(setf (rule-premises new-rule) unknowns)
(print new-rule)))))That completes the definition of emycin.
We are now ready to apply the shell to a specific domain, yielding the beginnings of an expert system.
This section applies emycin to MYCIN's original domain: infectious blood disease.
In our version of MYCIN, there are three contexts: first we consider a patient, then any cultures that have been grown from samples taken from the patient, and finally any infectious organisms in the cultures.
The goal is to determine the identity of each organism.
The real MYCIN was more complex, taking into account any drugs or operations the patient may previously have had.
It also went on to decide the real question: what therapy to prescribe.
However, much of this was done by special-purpose procedures to compute optimal dosages and the like, so it is not included here.
The original MYCIN also made a distinction between current versus prior cultures, organisms, and drugs.
All together, it had ten contexts to consider, while our version only has three:
(defun mycin ()
"Determine what organism is infecting a patient."
(emycin
(list (defcontext patient (name sex age) ())
(defcontext culture (site days-old) ())
(defcontext organism () (identity)))))These contexts declare that we will first ask each patient's name, sex, and age, and each culture's site and the number of days ago it was isolated. Organisms have no initial questions, but they do have a goal: to determine the identity of the organism.
The next step is to declare parameters for the contexts. Each parameter is given a type, and most are given prompts to improve the naturalness of the dialogue:
;;; Parameters for patient:
(defparm name patient t "Patient's name: " t read-line)
(defparm sex patient (member male female) "Sex:" t)
(defparm age patient number "Age:" t)
(defparm burn patient (member no mild serious)
"Is ~a a burn patient? If so, mild or serious?" t)
(defparm compromised-host patient yes/no
"Is ~a a compromised host?")
;;; Parameters for culture:
(defparm site culture (member blood)
"From what site was the specimen for ~a taken?" t)
(defparm days-old culture number
"How many days ago was this culture (~a) obtained?" t)
;;; Parameters for organism:
(defparm identity organism
(member pseudomonas klebsiella enterobacteriaceae
staphylococcus bacteroides streptococcus)
"Enter the identity (genus) of ~a:" t)
(defparm gram organism (member acid-fast pos neg)
"The gram stain of ~a:" t)
(defparm morphology organism (member rod coccus)
"Is ~a a rod or coccus (etc.):")
(defparm aerobicity organism (member aerobic anaerobic))
(defparm growth-conformation organism
(member chains pairs clumps))Now we need some rules to help determine the identity of the organisms. The following rules are taken from Shortliffe 1976. The rule numbers refer to the pages on which they are listed. The real MYCIN had about 400 rules, dealing with a much wider variety of premises and conclusions.
(clear-rules)
(defrule 52
if (site culture is blood)
(gram organism is neg)
(morphology organism is rod)
(burn patient is serious)
then .4
(identity organism is pseudomonas))
(defrule 71
if (gram organism is pos)
(morphology organism is coccus)
(growth-conformation organism is clumps)
then .7
(identity organism is staphylococcus))
(defrule 73
if (site culture is blood)
(gram organism is neg)
(morphology organism is rod)
(aerobicity organism is anaerobic)
then .9
(identity organism is bacteroides))
(defrule 75
if (gram organism is neg)
(morphology organism is rod)
(compromised-host patient is yes)
then .6
(identity organism is pseudomonas))
(defrule 107
if (gram organism is neg)
(morphology organism is rod)
(aerobicity organism is aerobic)
then .8
(identity organism is enterobacteriaceae))
(defrule 165
if (gram organism is pos)
(morphology organism is coccus)
(growth-conformation organism is chains)
then .7
(identity organism is streptococcus))Here is an example of the program in use:
> (mycin)
------ PATIENT-1 ------
Patient's name: Sylvia Fischer
Sex: female
Age: 27
------ CULTURE-1 ------
From what site was the specimen for CULTURE-1 taken? blood
How many days ago was this culture (CULTURE-1) obtained? 3
------ ORGANISM-1 ------
Enter the identity (genus) of ORGANISM-1: unknown
The gram stain of ORGANISM-1: ?
A GRAM must be of type (MEMBER ACID-FAST POS NEG)
The gram stain of ORGANISM-1: negThe user typed ? to see the list of valid responses.
The dialog continues:
Is ORGANISM-1 a rod or coccus (etc.): rod
What is the AEROBICITY of ORGANISM-1? Why
[Why is the value of AEROBICITY being asked for?]
It is known that:
1) THE GRAM OF THE ORGANISM IS NEG
2) THE MORPHOLOGY OF THE ORGANISM IS ROD
Therefore,
Rule 107:
If
1) THE AEROBICITY OF THE ORGANISM IS AEROBIC
Then there is suggestive evidence (0.8) that
1) THE IDENTITY OF THE ORGANISM IS ENTEROBACTERIACEAEThe user wants to know why the system is asking about the organism's aerobicity. The reply shows the current rule, what is already known about the rule, and the fact that if the organism is aerobic, then we can conclude something about its identity. In this hypothetical case, the organism is in fact aerobic:
What is the AEROBICITY of ORGANISM-1? aerobic
Is Sylvia Fischer a compromised host? yes
Is Sylvia Fischer a burn patient? If so, mild or serious? why
[Why is the value of BURN being asked for?]
It is known that:
1) THE SITE OF THE CULTURE IS BLOOD
2) THE GRAM OF THE ORGANISM IS NEG
3) THE MORPHOLOGY OF THE ORGANISM IS ROD
Therefore,
Rule 52:
If
1) THE BURN OF THE PATIENT IS SERIOUS
Then there is weakly suggestive evidence (0.4) that
1) THE IDENTITY OF THE ORGANISM IS PSEUDOMONAS
Is Sylvia Fischer a burn patient? If so, mild or serious? serious
Findings for ORGANISM-1:
IDENTITY: ENTEROBACTERIACEAE (0.800) PSEUDOMONAS (0.760)The system used rule 107 to conclude the identity might be enterobacteriaceae. The certainty is .8, the certainty for the rule itself, because all the conditions were known to be true with certainty. Rules 52 and 75 both support the hypothesis of pseudomonas. The certainty factors of the two rules, .6 and .4, are combined by the formula .6 + .4 - (.6 x .4) = .76. After printing the findings for the first organism, the system asks if another organism was obtained from this culture:
Is there another ORGANISM? (Y or N) Y
------ ORGANISM-2 ------
Enter the identity (genus) of ORGANISM-2: unknown
The gram stain of ORGANISM-2: (neg .8 pos .2)
Is ORGANISM-2 a rod or coccus (etc.): rod
What is the AEROBICITY of ORGANISM-2? anaerobicFor the second organism, the lab test was inconclusive, so the user entered a qualified answer indicating that it is probably gram-negative, but perhaps gram-positive. This organism was also a rod but was anaerobic. Note that the system does not repeat questions that it already knows the answers to. In considering rules 75 and 52 it already knows that the culture came from the blood, and that the patient is a compromised host and a serious burn patient. In the end, rule 73 contributes to the bacteroides conclusion, and rules 75 and 52 again combine to suggest pseudomonas, although with a lower certainty factor, because the neg finding had a lower certainty factor:
Findings for ORGANISM-2:
IDENTITY: BACTEROIDES (0.720) PSEUDOMONAS (0.646)Finally, the program gives the user the opportunity to extend the context tree with new organisms, cultures, or patients:
Is there another ORGANISM? (Y or N) N
Is there another CULTURE? (Y or N) N
Is there another PATIENT? (Y or N) NThe set of rules listed above do not demonstrate two important features of the system: the ability to backward-chain, and the ability to use operators other than is in premises.
If we add the following three rules and repeat the case shown above, then evaluating rule 75 will back-chain to rule 1, 2, and finally 3 trying to determine if the patient is a compromised host. Note that the question asked will be "What is Sylvia Fischer's white blood cell count?" and not "Is the white blood cell count of Sylvia Fischer < 2.5?" The latter question would suffice for the premise at hand, but it would not be as useful for other rules that might refer to the WBC.
(defparm wbc patient number
"What is ~a's white blood cell count?")
(defrule 1
if (immunosuppressed patient is yes)
then 1.0 (compromised-host patient is yes))
(defrule 2
if (leukopenia patient is yes)
then 1.0 (immunosuppressed patient is yes))
(defrule 3
if (wbc patient < 2.5)
then .9 (leukopenia patient is yes))Certainty factors are a compromise. The good news is that a system based on rules with certainty factors requires the expert to come up with only a small set of numbers (one for each rule) and will allow fast computation of answers. The bad news is that the answer computed may lead to irrational decisions.
Certainty factors have been justified by their performance (MYCIN performed as well or better than expert doctors) and by intuitive appeal (they satisfy the criteria listed on page 534). However, they are subject to paradoxes where they compute bizarre results (as in Exercise 16.1, page 536). If the rules that make up the knowledge base are designed in a modular fashion, then problems usually do not arise, but it is certainly worrisome that the answers may be untrustworthy.
Before MYCIN, most reasoning with uncertainty was done using probability theory. The laws of probability-in particular, Bayes's law-provide a well-founded mathematical formalism that is not subject to the inconsistencies of certainty factors. Indeed, probability theory can be shown to be the only formalism that leads to rational behavior, in the sense that if you have to make a series of bets on some uncertain events, combining information with probability theory will give you the highest expected value for your bets. Despite this, probability theory was largely set aside in the mid-1970s. The argument made by Shortliffe and Buchanan (1975) was that probability theory required too many conditional probabilities, and that people were not good at estimating these. They argued that certainty factors were intuitively easier to deal with. Other researchers of the time shared this view. Shafer, with later refinements by Dempster, created a theory of belief functions that, like certainty factors, represented a combination of the belief for and against an event. Instead of representing an event by a single probability or certainty, Dempster-Shafer theory maintains two numbers, which are analogous to the lower and upper bound on the probability. Instead of a single number like .5, Dempster-Shafer theory would have an interval like [.4,.6] to represent a range of probabilities. A complete lack of knowledge would be represented by the range [0,1]. A great deal of effort in the late 1970s and early 1980s was invested in these and other nonprobabilistic theories. Another example is Zadeh's fuzzy set theory, which is also based on intervals.
There is ample evidence that people have difficulty with problems involving probability. In a very entertaining and thought-provoking series of articles, Tversky and Kahneman (1974, 1983, 1986) show how people make irrational choices when faced with problems that are quite simple from a mathematical viewpoint. They liken these errors in choice to errors in visual perception caused by optical illusions. Even trained doctors and statisticians are subject to these errors.
As an example, consider the following scenario. Adrian and Dominique are to be married. Adrian goes for a routine blood test and is told that the results are positive for a rare genetic disorder, one that strikes only 1 in 10,000 people. The doctor says that the test is 99% accurate-it gives a false positive reading in only 1 in 100 cases. Adrian is despondent, being convinced that the probability of actually having the disease is 99%. Fortunately, Dominique happens to be a Bayesian, and quickly reassures Adrian that the chance is more like 1%. The reasoning is as follows: Take 10,001 people at random. Of these, only 1 is expected to have the disease. That person could certainly expect to test positive for the disease. But if the other 10,000 people all took the blood test, then 1% of them, or 100 people would also test positive. Thus, the chance of actually having the disease given that one tests positive is 1/101. Doctors are trained in this kind of analysis, but unfortunately many of them continue to reason more like Adrian than Dominique.
In the late 1980s, the tide started to turn back to subjective Bayesian probability theory. Cheeseman (1985) showed that, while Dempster-Shafer theory looks like it can, in fact it cannot help you make better decisions than probability theory. Heckerman (1986) re-examined MYCIN's certainty factors, showing how they could be interpreted as probabilities. Judea Pearl's 1988 book is an eloquent defense of probability theory. He shows that there are efficient algorithms for combining and propagating probabilities, as long as the network of interdependencies does not contain loops. It seems likely that uncertain reasoning in the 1990s will be based increasingly on Bayesian probability theory.
The MYCIN project is well documented in Buchanan and Shortliffe 1984. An earlier book, Shortliffe 1976, is interesting mainly for historical purposes. Good introductions to expert systems in general include Weiss and Kulikowski 1984, Waterman 1986, Luger and Stubblefield 1989, and Jackson 1990.
Dempster-Shafer evidence theory is presented enthusiastically in Gordon and Shortliffe 1984 and in a critical light in Pearl 1989/1978. Fuzzy set theory is presented in Zadeh 1979 and Dubois and Prade 1988.
Pearl (1988) captures most of the important points that lead to the renaissance of probability theory. Shafer and Pearl 1990 is a balanced collection of papers on all kinds of uncertain reasoning.
Exercise 16.2 [s] Suppose the rule writer wanted to be able to use symbolic certainty factors instead of numbers. What would you need to change to support rules like this:
(defrule 100 if ... then true ...)
(defrule 101 if ... then probably ...)Exercise 16.3 [m] Change prompt-and-read-vals so that it gives a better prompt for parameters of type yes/no.
Exercise 16.4 [m] Currently, the rule writer can introduce a new parameter without defining it first. That is handy for rapid testing, but it means that the user of the system won't be able to see a nice English prompt, nor ask for the type of the parameter. In addition, if the rule writer simply misspells a parameter, it will be treated as a new one. Make a simple change to fix these problems.
Exercise 16.5 [d] Write rules in a domain you are an expert in, or find and interview an expert in some domain, and write down rules coaxed from the expert. Evaluate your resulting system. Was it easier to develop your system with EMYCIN than it would have been without it?
Exercise 16.6 [s] It is said that an early version of MYCIN asked if the patient was pregnant, even though the patient was male. Write a rule that would fix this problem.
Exercise 16.7 [m] To a yes/no question, what is the difference between yes and (no-1)? What does this suggest?
Exercise 16.8 [m] What happens if the user types why to the prompt about the patient's name?
What happens if the expert wants to have more than one context with a name parameter?
If there is a problem, fix it.
The remaining exercises discuss extensions that were in the original EMYCIN, but were not implemented in our version. Implementing all the extensions will result in a system that is very close to the full power of EMYCIN. These extensions are discussed in chapter 3 of Buchanan and Shortliffe 1984.
Exercise 16.9 [h] Add a spelling corrector to ask-vals.
If the user enters an invalid reply, and the parameter type is a member expression, check if the reply is "close" in spelling to one of the valid values, and if so, use that value.
That way, the user can type just entero instead of enterobacteriaceae.
You may experiment with the definition of "close," but you should certainly allow for prefixes and at least one instance of a changed, missing, inserted, or transposed letter.
Exercise 16.10 [m] Indent the output for each new branch in the context tree. In other words, have the prompts and findings printed like this:
------ PATIENT-1 ------
Patient's name: Sylvia Fischer
Sex: female
Age: 27
------ CULTURE-1 ------
From what site was the specimen for CULTURE-1 taken? blood
How many days ago was this culture (CULTURE-1) obtained? 3
------ ORGANISM-1 ------
Enter the identity (genus) of ORGANISM-1: unknown
The gram stain of ORGANISM-1: neg
...
Findings for ORGANISM-1:
IDENTITY: ENTEROBACTERIACEAE (0.800) PSEUDOMONAS (0.760)
Is there another ORGANISM? (Y or N) N
Is there another CULTURE? (Y or N) N
Is there another PATIENT? (Y or N) NExercise 16.11 [h] We said that our emycin looks at all possible rules for each parameter, because there is no telling how a later rule may affect the certainty factor.
Actually, that is not quite true.
If there is a rule that leads to a conclusion with certainty 1, then no other rules need be considered.
This was called a unity path.
Modify the program to look for unity paths first.
Exercise 16.12 [m] Depending on whether a parameter is in initial-data or not, all the relevant rules are run either before or after asking the user for the value of the parameter.
But there are some cases when not all initial data parameters should be asked for.
As an example, suppose that identity and gram were initial data parameters of organism.
If the user gave a positive answer for identity, then it would be wasteful to ask for the gram parameter, since it could be determined directly from rules.
After receiving complaints about this problem, a system of antecedent rules was developed.
These rules were always run first, before asking questions.
Implement antecedent rules.
Exercise 16.13 [h] It is useful to be able to write default rules that fill in a value after all other rules have failed to determine one. A default rule looks like this:
(defrule n if (parm inst unknown) then (parm inst is default))It may also have other conjuncts in the premise.
Beside details like writing the unknown operator, the difficult part is in making sure that these rules get run at the right time (after other rules have had a chance to fill in the parameter), and that infinite loops are avoided.
Exercise 16.14 [h] The context tree proved to be a limitation.
Eventually, the need arose for a rule that said, "If any of the organisms in a culture has property X, then the culture has property Y." Implement a means of checking for some or every instance of a context.
Exercise 16.15 [m] As the rule base grew, it became increasingly hard to remember the justification for previous rules. Implement a mechanism that keeps track of the author and date of creation of each rule, and allows the author to add documentation explaining the rationale for the rule.
Exercise 16.16 [m] It is difficult to come up with the perfect prompt for each parameter.
One solution is not to insist that one prompt fits all users, but rather to allow the expert to supply three different prompts: a normal prompt, a verbose prompt (or reprompt) for when the user replies with a ?, and a terse prompt for the experienced user.
Modify defparm to accommodate this concept, add a command for the user to ask for the terse prompts, and change ask-vals to use the proper prompt.
The remaining exercises cover three additional replies the user can make: how, stop, and change.
Exercise 16.17 [d] In addition to why replies, EMYCIN also allowed for how questions.
The user can ask how the value of a particular parameter/instance pair was determined, and the system will reply with a list of rules and the evidence they supplied for or against each value.
Implement this mechanism.
It will require storing additional information in the data base.
Exercise 16.18 [m] There was also a stop command that immediately halted the session.
Implement it.
Exercise 16.19 [d] The original EMYCIN also had a change command to allow the user to change the answer to certain questions without starting all over.
Each question was assigned a number, which was printed before the prompt.
The command change, followed by a list of numbers, causes the system to look up the questions associated with each number and delete the answer to these questions.
The system also throws away the entire context tree and all derived parameter values.
At that point the entire consultation is restarted, using only the data obtained from the unchanged questions.
Although it may seem wasteful to start over from the beginning, it will not be wasteful of the user's time, since correct answers will not be asked again.
Identify what needs to be altered to implement change and make the alterations.
Exercise 16.20 [h] Change the definition of cf-and and cf-or to use fuzzy set theory instead of certainty factors.
Do the same for Dempster-Shafer theory.
Answer 16.1 Because EMYCIN assumes independence, each reading of the same headline would increase the certainty factor. The following computation shows that 298 more copies would be needed to reach .95 certainty. A more sophisticated reasoner would realize that multiple copies of a newspaper are completely dependent on one another, and would not change the certainty with each new copy.
> (loop for cf = .01 then (cf-or .01 cf)
until (> cf .95)
count t)
298Answer 16.2 The defrule expands to (make-rule :number '101 :cf true ...); that is, the certainty factor is unquoted, so it is already legal to use true as a certainty factor!
To support probably and other hedges, just define new constants.
Answer 16.4 Just make the default parameter type be nil (by changing t to nil in parm-type).
Then any rule that uses an undefined parameter will automatically generate a warning.
Answer 16.6
(defrule 4
if (sex patient is male)
then -1 (pregnant patient is yes))Answer 16.7 Logically, there should be no difference, but to EMYCIN there is a big difference.
EMYCIN would not complain if you answered (yes 1 no 1).
This suggests that the system should have some way of dealing with mutually exclusive answers.
One way would be to accept only yes responses for Boolean parameters, but have the input routine translate no to (yes -1) and (no cf) to (yes 1-cf).
Another possibility would be to have update-cf check to see if any certainty factor on a mutually exclusive value is 1, and if so, change the other values to -1.
Answer 16.18 Add the clause (stop (throw 'stop nil)) to the case statement in ask-vals and wrap a (catch 'stop ...) around the code in emycin.