In this article we will discuss about the examples of expert system. The examples are: 1. MYCIN 2. Prospector 3. Dendral 4. Mass/Charge 5. XCON.
Example # 1. MYCIN:
Historically, the MYCIN system played a major role in stimulating research interest in rule-based expert systems.
MYCIN is an expert system for diagnosing and recommending treatment of bacterial infections of the blood (such as meningitis and bacteremia). It was developed at Stanford University in California, USA, in the 1970s, and has become a template for many similar rule based systems. It is intended to support clinicians in the early diagnosis and treatment of meningitis, which can be fatal if not treated in time.
However, the laboratory tests for these conditions take several days to be completed, so doctors (and therefore MYCIN) have to make decisions with incomplete information associated with medical knowledge. MYCIN incorporated a calculus of uncertainty called certainty factors which seemed (at that time) to fit well with how doctors assessed the impact of evidence on the diagnosis.
ADVERTISEMENTS:
This system was able to perform as well as some experts and considerably better than junior doctors. A consultation with MYCIN begins with requests for routine information such as age, medical history and so on, programming to more specific questions as required.
MYCIN’S expertise knowledge lies in the domain of bacterial infections. MYCIN’S pool of knowledge consists of approximately 500 antecedent-consequent rules, implemented in LISP which give MYCIN the ability to recognise about 100 causes of bacterial infections. Physicians usually begin antibiotic treatment for patients who have bacterial infections without knowing exactly which organism is the culprit.
There is no time to wait for definitive laboratory culture evidence, which accumulates too slowly. For the desperately sick, therapy must begin at once, not 2 days after.
This requirement leaves two choices:
ADVERTISEMENTS:
i. The physician can either prescribe a broad-spectrum drug which covers all possibilities, or
ii. He can prescribe a better, disease specific drug.
MYCIN helps the physician to prescribe disease-specific drugs. MYCIN informs itself about particular cases by requesting information from the physician about a patient’s symptoms, general condition, history, and laboratory-test results. At each point, the question MYCIN asks is determined by MYCIN’S current hypothesis and the answer to all previous questions. Thus, the questions start as though taken from a checklist, but the questions then vary as evidence builds.
Here is an excerpt from a sample session:
ADVERTISEMENTS:
1. What is the patient’s name?
Arun Sehgal
2. Male or Female?
Male
ADVERTISEMENTS:
3. Age?
55
4. Have you obtained positive cultures indicating general type?
Yes.
ADVERTISEMENTS:
5. What type of infection is it?
Primary bacteria.
6. When did symptoms first appear?
May 5, 2006
7. Let’s call the most recent positive culture C1. From what site was C1 taken?
From the blood.
8. When?
May 9, 2006
9. Let’s call the first significant organism from this culture U1. Do you know the identity of U1?
No.
10. Is U1 a rod or a coccus or something else?
Rod.
11. What in the gram stain of U1?
Gram-negative.
12. Have there been positive cultures from sites which are not associated with the infections about which you are seeking advice?
No.
13. Did U1 grow aerobically?
Yes.
When MYCIN is satisfied that it has a reasonably good grasp of the situation, MYCIN announces its diagnosis:
My recommendation will be based on the opinion that the identity of U1 may be:
1. Pseudomonas-aeruginosa
2. Klebsiella-pneumonise.
3. E.coli
4. Bacteroides-fragilis.
5. Enterobacter.
6. Proteus-nonmirabilis.
After asking a few more questions about the patient, MYCIN announces its recommendation:
1. On a scale of 0 to 4, where the higher number indicates greater severity, how would you rate the patient’s degree of sickness?
2. Does the patient have a clinically significant allergic reaction to any antimicrobial agent?
3. How much does the patient weigh?
4. My first recommendation is as follows: to cover for items 1, 2, 3, 5 and 6, give gentamycin using a dose of 119 mg (1.7 mg/kg) q8h IV [or IM] for 10 days. Modify dose in renal failure. Also, to cover for item 4, give clindamycin using a dose of 595 mg (8.5 mg/kg) q6th IV [or IM] for 14 days. If diarrhea or other gastrointestinal symptoms develop, check for pseudomembranous colitis.
It has the following organisational features:
i. Knowledge Representation:
In the form of production rules implemented in LISP. K.B. is of the form – If condition, and …. and condition hold then draw conclusion, and …. and conclusion encoded in the data structure of LISP programming.
ii. Reasoning:
Backward chaining, and forward reasoning uses certainty factors to reason with uncertain information. MYCIN uses backward chaining to discover what organisms where present. Then it uses forward chaining to reason from the organism to a treatment regime.
iii. Heuristics:
When the general category of infection has been established, MYCIN examines each candidate diagnosis in a depth-first manner. Heuristics are used to limit the search, including checking all premises of a possible rule to see if anyone of these is known to be false.
iv. Dialogue/Explanation:
The dialogue is computer controlled, with MYCIN driving the consultation through asking questions. Explanations are generated by tracing back through the rules which have been fired. Both “how? ” and “why? ” explanation are supported.
Example # 2. Prospector:
PROSPECTOR is an expert system which was designed for decision making problems in mineral exploration. It uses a structure called an inference network to represent the data base. PROSPECTOR was written in 1978 by Richard O. Duda (1979), then of SRI International.
Its rules look like:
If:
Magnetite or pyrite in disseminated or veinlet from is present.
Then:
(2, – 4) there is favourable mineralisation and texture for the prophylactic stage.
The rules contain two confidence estimates. The first indicates the extent to which the presence of the evidence described in the condition part of this rule suggests the validity of the rule’s conclusion. Number 2, in the rule shown above indicates that the presence of the evidence is mildly encouraging.
The second confidence estimate measures the extent to which the evidence is necessary to the validity of the conclusion or in other words, the extent to which the lack of the evidence indicates that the conclusion is not valid. Here number – 4, indicates the absence of the evidence is strongly discouraging for the conclusion.
Some of the important features and contributions of PROSPECTOR are the following:
1. The system represents fuzzy input on a range from -5 = certainly false to +5 = certainly true and produces conclusion with associated uncertainty factors.
2. The system’s expertise is based on hand-crafted knowledge of twelve major prospect-scale models and 23 smaller regional scale models.
The prospect- scale models describe major ore-deposits such as:
I. Massive Sulfide deposit, Kuroko Type.
II. Mississippi-Valley Lead-Zince.
III. Western States Sandstone Uranium.
3. The system does not only understand the rules in its knowledge base but can explain the steps used in reaching its conclusions.
4. The knowledge acquisition system KAS has been developed for easy editing and expansion of the inference network structure in which the knowledge base is stored. PROSPECTOR performs at the level of an expert hard-rock geologist and has already proven itself successful at prospecting. It predicted a molybdenum deposit near Mt. Tolman in Washington State, USA, which was subsequently confirmed by core drilling as having a value of $ 100 million in 1984.
It has the following organisational features:
i. Knowledge Representation:
Production rules and semantic network.
ii. Reasoning:
Predominantly forward chaining (data-driven), with some backward chaining. Bayesian reasoning is used to deal with uncertainty.
iii. Heuristics:
Depth-first search is focused using the probabilities of each hypothesis.
iv. Dialogue/Explanation:
The dialogue uses mixed control. The user volunteers information at the start of the consultation, and PROSPECTOR can request additional information when required. Explanations are generated by tracking back through the rules which have been fired.
Example # 3. Dendral:
Dendral is one of the great classic application programs. To see what it does, let us suppose that an organic chemist wants to know the chemical nature of some substance newly created in the test tube. The first step is to determine the number of atoms of various kinds in one molecule of the stuff. This step determines the chemical formula, such as C8H16O. The notation indicates that each molecule has eight atoms of carbon, 16 of hydrogen, and one of oxygen.
Once a sample’s chemical formula is known, the chemist may use the sample’s mass spectrogram to work out the way the atoms are arranged in the chemical’s structure, thus identifying the isomer of the chemical.
The spectrogram machine bombards a sample with high energy electrons, causing the molecules to break up into charged chunks of various sizes. Then, the machine sorts the chunks by passing them through a magnetic field which deflects the high-charge, low-weight ones more than it does the low-charge, high-weight ones. The deflected chunks are collected, forming a spectrogram.
Example # 4. Mass/Charge:
The purpose of DENDRAL is to work, like a knowledgeable chemist, from a chemical formula and spectrogram to a deduced structure, producing a chemical structure like this:
The DENDRAL program works out structures from chemical formulas and mass spectrograms using the generate-and-test method. The generator consists of a structure enumerator and a synthesiser, which produces a synthetic mass spectrogram by simulating the action of a real mass spectrometer on each enumerated structure.
The structure enumerator ensures that the overall generator is on complete and non-redundant because the structure enumerator uses complete and non-redundant structure-enumeration procedure. The overall generator is also informed, because the structure enumerator uses the chemical formula and knowledge about necessary and forbidden substructures.
The tester compares the real mass spectrogram with those produced by the generator. The possible structures are those whose synthetic spectrograms match the real one adequately. The structure judged correct is the one whose synthetic spectrogram most closely matches the real one.
DENDRAL by AI researcher Edward Feigenbaum and gentilist Joshua Lederberg is one of the earliest expert systems, developed at Stanford, CA, USA; during the late 1960s. Originally, called Heuristic Dendral is not a stand-alone expert system, more an expert’s assistant, since it relies on the input of the human expert to guide its decision making.
However, it has been successful enough in this capacity to discover results which have been published as original research. Dendrals performance rivalled then of human chemists expert at the task, and the program was used in industry and universities.
It has the following organisational features:
i. Knowledge Representation:
Production rules and algorithms for generating graph structures are constructed by META-DENDRAL, META-DENDRAL is a program which uses learning techniques to construct rules for an expert system automatically.
ii. Reasoning:
Forward chaining (data-driven).
iii. Heuristics:
DENDRAL uses a variation of depth first search called generate and test, where all hypotheses are generated and then tested against the available evidence. Heuristic knowledge from the users (chemists) is also used to constrain the search.
iv. Dialogue/Explanation:
The dialogue uses mixed control. The user can supply information and the system can request information as required.
Example # 5. XCON:
Historically, the XCON system played a major role in stimulating commercial interest in rule based expert systems. XCON’s domain is computer-system components. When a company buys a big computer (main frame) it buys a central processor, memory, terminals, disk drives, tape drives, various peripheral controllers and other paraphernalia. All these components (100-200 in number) must be arranged sensibly along input-output buses. Moreover all the electronic modules must be placed on the proper kind of cabinet in a suitable slot of suitable back plane.
John McDermott (1982, 1984) of Carnegi-Mellon University USA, wrote R1/ XCON In collaboration will Digital Equipment Corporation. XCON is the acronym for expert configure and is used to configure the VAX and PDP-11 series of computer systems sold by DEC, XCON is the name used by the Digital Equipment Corporation while the Carnegie-Mellon research team uses R1 which is McDermott’s name for the system. He is quoted as saying, “Three years ago I wanted to be a knowledge engineer, and today I am one”.
XCON was proposed to DEC management in December of 1978, and a prototype system was demonstrated in May,1979. The initial system contained about 300 production rules of the standard variety for configuring the 420 possible components of a VAX-11/780 system and detailing its backplane wiring. A completed system containing some 800 production rules was delivered to DEC for acceptance testing in October, 1979. By 1980, DEC personnel had become sufficiently familiar with the operation of XCON to assume full responsibility for its maintenance and development, and they have extended it to contain over 4,000 rules.
The XCON system was designed to replace human “technical editors”. Such editors had been responsible for two operations: checking for completeness of orders, and laying out the physical placement and wiring connections between component modules in the chassis.
These tasks are fairly tedious; and each of the components is specified by properties such as voltage, frequency, how many devices it supports, and how many ports it has. In addition to this information, the editors had information indicating which components can or must be associated with other components. This set of rules governing the relationship between components is called “constraint knowledge”.
An example of one of the rules from XCON is shown:
IF the current sub-task is assigning devices to unibus-modules, and there is an unassigned dual port disk drive, and the type of controller it requires is known, and there are two such controllers, neither of which has any devices assigned to it, and the number of devices which these controllers can support is known.
THEN assign the disk drive to each controller and note that each controller supports one device.
XCON passed an extensive series of performance tests which were also used to upgrade its performance. A set of ten configurations was submitted to the program and the results were evaluated by a team of twelve people consisting of technical editors, technicians, and engineers. Errors detected were corrected and the cycle repeated until fifty configurations had been produced. This initial testing detected only twelve errors of seven different types. By December, 1979, XCON was judged expert enough to be used for routine configuration of VAX-11/780 systems.
The capabilities of XCON have grown to include configuring the much more complicated PDP-11 family of computer. By 1986 XCON represented an investment of over 50 person-years of human effort. The current R1/XCON system is used to configure over 97 per cent of the orders received for VAX-11 systems.
The experience of building XCON yielded a number of lessons which builders of other expert systems have found instructive include:
a. Since its birth, XCON has grown at a relatively uniform rate as its capabilities expanded from a single line of VAX computers to the complete VAX line and the PDP-11 line. This effort has required about four person-years per year.
b. The developers of XCON found that they did not have to complete the system before putting it to use. This illustrates an important characteristics of expert systems-their incremental growth.
c. No matter how much knowledge was added to XCON, it still continued to make occasional mistakes. The developers have concluded that it will never be possible to guarantee 100% error free performance and are resigned to this fact.
d. The developers of XCON found that building an expert system is an unending process. An expert system’s clientele continue to demand refinement of existing capabilities and extension of the boundaries of the domain of its expertise.
Since 1980, XCON has analysed over 100,000 unique orders and is presently operating with greater than 99% accuracy. It has become an indispensable and effective business tool. The savings produced by XCON has convinced DEC management that artificial intelligence, particularly its application to expert systems, has a bright future.
The organizational features of XCON are:
i. Knowledge Representation:
Production rules (about 10,000). Contain no numeric measures of uncertainty as this is dealing with design aspect.
ii. Reasoning:
Forward chaining (data-driven). Since it is possible to specify rules exactly no uncertainty is present.
iii. Heuristics:
The main configuration task is split into- subtasks which are always examined in a predetermined order. Constraint satisfaction is used to inform the search for a solution to a subtask.
iv. Dialogue/Explanation:
The dialogue is less important than in the previous situations since the customer’s requirements can be specified at the beginning and the system contains all the information it needs regarding other constraints.
The benchmark expert systems have proven the feasibility of using knowledge-based systems for solving problems traditionally requiring human experts. In their wake has come a flood of new expert systems, many of which have been published and even more of which are under development as proprietary, “in- house” products for improving industrial productivity.
These examples of expert systems illustrate how the different techniques can be combined to produce a useful solution and how different problems require different solutions.