CIS509 |
 |  |
||
Lesson 2 The Development of Expert Systems Technology
1.6 THE DEVELOPMENT OF EXPERT SYSTEMS TECHNOLOGY
AI has many branches concerned with speech, vision, robotics, natural language understanding and learning, and expert systems. The roots of expert systems lie in many disciplines. In particular, one of the major roots of expert systems is the area of human information processing called cognitive science. Cognition is the study of how humans process information. In other words, cognition is the study of how people think, especially when solving problems.
The study of cognition is very important if we want to make computers emulate human experts. Often experts can’t explain how they solve problems – the solutions just come to them. If the expert can’t explain how a problem is solved, it’s not possible to encode the knowledge in an expert system based on explicit knowledge. In this case the only possibility is programs that learn by themselves to emulate the expert. These are programs based on induction and artificial neural systems, which will be discussed later.
Human Problem Solving and Productions
The development of expert systems technology draws on a wide background. Table 1.2 is a brief summary of some important developments that have converged in modern expert systems. Whenever possible, the starting dates of projects are given. Many projects extend over several years. These developments are covered in more detail in this chapter and others. The single best reference for all the early systems is the three-volume Handbook of Artificial Intelligence.
---------------------------------------------------------------------------------------------------
Year Event
1943 Post production rules; McCulloch and Pitts Neuron Model
1954 Markov Algorithm for controlling rule execution
1956 Dartmouth Conference; Logic Theorist; Heuristic Search; "AI" term
coined
Perceptron invented by Rosenblatt;
GPS (General Problem Solver) started
(Newell, Shaw, and Simon)
1958 LISP AI language (McCarthy)
1962 Rosenblatt’s Principles of Neurodynamics on perceptions
Resolution Method of automatic
theorem proving (Robinson) Fuzzy Logic
for reasoning about fuzzy
objects (Zadeh) Work begun on DENDRAL,
the first expert system
(Feigenbaum, Buchanan, et al.)
1968 Semantic nets, associative memory model (Quillian)
1969 MACSYMA math expert system (Martin and Moses)
1970 Work begins on PROLOG (Colmerauer, Roussell, et al.)
HEARSAY I for speech recognition
Human Problem Solving popularizes rules
(Newell and Simon)
MYCIN expert system for
medical diagnosis (Shortliffe, et al.) leading to
GUIDON, intelligent tutoring
(Clancey) TEIRESIAS, explanation facility
concept (Davis), and EMYCIN,
first shell (Van Melle, Shortliffe, and Buchanan)
HEARSAY II, blackboard model
of multiple cooperating experts
1975 Frames, knowledge representation (Minsky)
AM (Artificial Mathematician)
creative discovery of math concepts (Lenat
Dempster-Shafer Theory of
Evidence for reasoning under uncertainty Work
begun on PROSPECTOR expert
system for mineral exploration
(Duda, Hart, et al.)
1977 OPS expert system shell (Forgy), used in XCON/R 1
1978 Work started on XCON/Rl (McDermott, DEC) to configure DEC computer
systems
Meta-DENDRAL, metarules,
and rule induction (Buchanan)
Rete Algorithm for fast
pattern matching (Forgy) Commercialization of AI begins
Inference Corp. formed (releases
ART expert system tool in 1985)
1980 Symbolics, LMI founded to manufacture LISP machines
SMP math expert system;
Hopfield Neural Net;
Japanese Fifth Generation
Project to develop intelligent computers
1983 KEE expert system tool (IntelliCorp)
1985 CLIPS expert system tool (NASA)
---------------------------------------------------------------------------------------------------
Table 1.2 Some Important Events in the History of Expert Systems
In the late 1950s and early 1960s, a number of programs were written with the goal of general problem solving. The most famous of these was the General Problem Solver, created by Newell and Simon and described in a series of papers culminating in their monumental 920-page work on cognition, Human Problem Solving.
One of the most significant results demonstrated by Newell and Simon was that much of human problem solving or cognition could be expressed by IF... THEN – type production rules. For example, IF it looks like it’s going to rain THEN carry an umbrella, or IF your spouse is in a bad mood THEN don’t appear happy. A rule corresponds to a small, modular collection of knowledge called a chunk. Chunks are organized in a loose arrangement, with links to related chunks of knowledge. One theory is that all human memory is organized in chunks. An example of a rule representing a chunk of knowledge is
Long-term memory consists of many rules having the simple IF...THEN structure. In fact, a grand master chess expert may know 50,000 or more chunks of knowledge about chess patterns. In contrast to the long-term memory, the short-term memory is used for the temporary storage of knowledge during problem solving. Although long-term memory can hold hundreds of thousands or more chunks, the capacity of working memory is surprisingly small – four to seven chunks. As a simple example of this, try visualizing some numbers in your mind. Most people can see only four to seven numbers at one time. Most people can memorize many more than four to seven numbers. However, those numbers are kept in long-term memory.
One theory proposes that short-term memory represents the number of chunks that can be simultaneously active and considers human problem solving as a spreading of these activated chunks in the mind. Eventually, a chunk may be activated with such intensity that a conscious thought is generated and you say to yourself, "Hmm... something’s burning."
The other element necessary for human problem solving is a cognitive processor. The cognitive processor tries to find the rules that will be activated by the appropriate stimuli. But not just any rule will do. For example, you wouldn’t want to fill your gas tank every time you heard a siren. Only a rule that matched the stimuli would be activated. If multiple rules are activated at one time, the cognitive processor must perform a conflict resolution to decide which rule has the highest priority. That rule will be executed, for example, if both of the following rules are activated:
The Newell and Simon model of human problem solving in terms of long-term memory (rules), short-term memory (working memory), and a cognitive processor (inference engine) is the basis of modern rule-based expert systems.
Rules like these are a type of production system. Today rule-based production systems are a popular method of implementing expert systems. The individual rules that comprise a production system are the production rules. In designing an expert system an important factor is the amount of knowledge or granularity of the rules. Too little granularity makes it difficult to understand a rule without reference to other rules. Too much granularity makes the expert system difficult to modify, because several chunks of knowledge are intermingled in one rule.
Until the mid-sixties, a major quest of AI was to produce intelligent systems that relied little on domain knowledge and more on powerful methods of reasoning. Even the name General Problem Solver illustrates the concentration on machines that were not designed for one specific domain but were intended to solve many types of problems. Although the methods of reasoning used by general problem solvers were powerful, the machines were eternal beginners. When presented with a new domain, they had to discover everything from first principles and were not as good as human experts, who relied on domain knowledge for high performance.
An example of the power of knowledge is the game of chess. Although computers now rival humans, people play well despite the fact that computers can do calculations millions of times faster. Studies have shown that human expert chess players do not have super powers of reasoning but instead rely on knowledge of chess piece patterns built up over years of play. As mentioned previously, one estimate places an expert chess player’s knowledge at about 50,000 patterns. Humans are very good at recognizing patterns such as pieces on a chess-board. Instead of trying to reason ahead ten or twenty possible moves for every piece, as a computer might, the human analyzes the game in terms of patterns that reveal long-term threats while remaining alert for short-term surprise moves.
Although domain knowledge is powerful, it is generally limited to the domain. For example, a person who becomes an expert chess player does not automatically become an expert at solving math problems or even an expert at checkers. While some knowledge may carry over to another domain, such as the careful planning of moves, this is a skill rather than genuine expertise.
By the early 1970s, it had become apparent that domain knowledge was the key to building machine problem solvers that could function at the level of human experts. Although methods of reasoning are important, studies have shown that experts do not primarily rely on reasoning in problem solving. In fact, reasoning may play a minor role in an expert’s problem solving. Instead, experts rely on a vast knowledge of heuristics and the experience they have built up over the years. If an expert cannot solve a problem based on expertise, then he or she must reason from first principles and theory (or, more likely, ask another expert). The reasoning ability of an expert is generally no better than that of an average person in dealing with a totally unfamiliar situation. Early attempts at building powerful problem solvers based only on reasoning have shown that they are crippled if they must rely solely on reasoning.
The insight that domain knowledge was the key to building real-world problem solvers led to the success of expert systems. The successful expert systems today are thus knowledge-based expert systems rather than general problem solvers. In addition, the same technology that led to the development of expert systems has also led to the development of knowledge-based systems that do not necessarily contain human expertise.
While expertise is considered knowledge that is specialized and known only to a few, knowledge is generally found in books, periodicals, and other widely available resources. For example, the knowledge of how to solve a quadratic equation or perform integration and differentiation is widely available. Knowledge-based computer programs such as MACSYMA and SMP are available to automatically perform these and many other mathematical operations on either numeric or symbolic operands. Other knowledge-based programs may perform process control of manufacturing plants. Today the terms knowledge-based programming and expert systems are often used synonymously. In fact, expert systems is now considered an alternative programming model or paradigm to conventional algorithmic programming.
The Rise of Knowledge-based Systems
With the acceptance of the knowledge-based paradigm in the 1970s,a number of successful prototype expert systems were created. These systems could interpret mass spectrograms to identify chemical constituents (DENDRAL), diagnose illnesses (MYCIN), analyze geologic data for oil (DIPMETER) and minerals (PROSPECTOR), and configure computer systems (XCON/Rl).The news that PROSPECTOR had discovered a mineral deposit worth $100 million and that XCON/Rl was saving Digital Equipment Corporation (DEC) millions of dollars a year triggered a sensational interest in the new expert systems technology by 1980. The branch of AI that had started off in the 1950s as a study of human information processing had now grown to achieve commercial success by the development of practical programs for real-world use.
The MYCIN expert system was important for several reasons. First, it demonstrated that AI could be used for practical real-world problems. Second, MYCIN was the testbed of new concepts such as the explanation facility, the automatic acquisition of knowledge, and the intelligent tutoring that are found in a number of expert systems today. The third reason that MYCIN was important is that it demonstrated the feasibility of the expert system shell.
Previous expert systems such as DENDRAL were unique systems in which the knowledge base was intermingled with the software that applied the knowledge, the inference engine. MYCIN explicitly separated the knowledge base from the inference engine. This was extremely important to the development of expert system technology because it meant that the essential core of the expert system could be reused. That is, a new expert system could be built much more rapidly than a DENDRAL – type system by emptying out the old knowledge and putting in knowledge about the new domain. The part of MYCIN that dealt with inference and explanation, the shell, could then be refilled with knowledge about the new system. The shell produced by removing the medical knowledge of MYCIN was called EMYCIN (essential or empty MYCIN).
By the late 1970s, the three concepts basic to most expert systems today had converged, as shown in Figure 1.5. These concepts are rules, the shell, and knowledge.
By 1980 new companies had started to bring expert systems out of the university laboratory and produce commercial products. Powerful new software for expert system development was introduced, including the Automated Reasoning Tool (ART) by the Inference Corp., the Knowledge Engineering Tool (KEE) by IntelliCorp, and Rulemaster by Radian Corp. In addition, specialized new hardware was developed to run the software with greater speed than ever before. Companies such as Symbolics and LMI introduced computers referred to as LISP machines because they were designed for LISP, the underlying base language of the expert systems development software. In LISP machines the native assembly language, operating system, and all other fundamental code were created in LISP.
Figure 1.5 Convergence of Three Important Factors to Create the
Modern Rule-based Expert System
Unfortunately, this high technology also commanded a high price. Although a single-user LISP machine was much more powerful and productive than a general-purpose machine running LISP, the single-user machine and a single-user software license together cost $100,000. Establishing an AI lab with a half-dozen programmers could easily cost $500,000.
These objections were overcome in the mid-1980s by the introduction of powerful development software such as CLIPS by NASA. CLIPS is written in C for speed and portability, and also uses a powerful pattern matching called the Rete Algorithm. CLIPS is free to government users and government contractors. It is available at a nominal cost to other users from COSMIC, which distributes NASA-developed software; universities can obtain it at half price. CLIPS is royalty free and may be freely distributed by anyone who obtains a legitimate copy from COSMIC.
CLIPS can be installed on any C compiler that supports the standard Kernigan and Richie C language. It has been installed on the IBM-PC and compatibles, VAX, Hewlett-Packard, Sun, Cray, and many other makes of computers. Versions for Macintosh Windows and others are available from COSMIC.
1.7 EXPERT SYSTEMS APPLICATIONS AND DOMAINS
Conventional computer programs are used to solve many types of problems. These problems generally have algorithmic solutions that lend themselves well to conventional programs and programming languages such as FORTRAN, Pascal, Ada, and so on. In many application areas such as business and engineering, numeric calculations are of primary importance. By contrast, expert systems are primarily designed for symbolic reasoning.
While languages such as LISP and PROLOG are also used for symbolic manipulation, they are more general purpose than expert system shells. This does not mean that it is not possible to build expert systems in LISP and PROLOG. In fact, many expert systems have been built with PROLOG and LISP. PROLOG especially has a number of advantages for diagnostic systems because of its built-in backward chaining. However, it is more convenient and efficient to build large expert systems with shells and utility programs specifically designed for expert system building. Instead of "reinventing the wheel" every time a new expert system is to be built, it is more efficient to use specialized tools designed for expert system building rather than general purpose tools.
Applications of Expert Systems
Expert systems have been applied to virtually every field of knowledge. Some have been designed as research tools while others fulfill important business and industrial functions. One example of an expert system in routine business use is the XCON system of Digital Equipment Corp. (DEC). The XCON system (originally called Rl) was developed in conjunction with John McDermott of Carnegie-Mellon University. XCON is an expert configuring system for DEC computer systems.
The configuration of a computer system means that when a customer places an order, all the right parts – software, hardware, and documentation – are supplied. For large systems, the customer’s system is set up or configured at the factory and tested to insure that it meets the customer’s requirements. Unlike with the purchase of a TV set or a home computer, there are many options and interconnections possible with a large computer system. In putting together a large system, it’s not enough to ship the requested number of CPUs, disk drives, terminals, and so forth. The proper interconnections and cabling must also be supplied and the system checked to verify that it is working correctly.
The XCON system is probably one of the most successful expert systems in routine use and saves DEC millions of dollars a year, reduces the time to configure the orders, and improves the accuracy of orders. XCON can configure an average order in about two minutes, which is fifteen times faster than a human. Also, whereas the humans configured orders correctly 70 percent of the time, XCON has an accuracy of 98 percent. These are important concerns because configuring a complex computer system at the factory involves considerable effort. It is expensive to partially configure a system and then find out that the system cannot meet the customer’s requirements or that other components are needed and shipment will be delayed until the parts arrive.
Hundreds of expert systems have been built and reported on in computer
journals, books, and conferences. This probably represents only the tip
of the iceberg since many companies and military organizations will not
report their systems because of proprietary or secret knowledge contained
in the systems. Based on the systems described in the open literature,
certain broad classes of expert systems applications can be discerned,
as shown in Table 1.3.
Examples of some expert systems are shown in Tables 1.4 through 1.9, and in the historical bibliography at the end of this chapter.
----------------------------------------------------------------------------------------
Class
General Area
Configuration Assemble proper components
of a system in the proper way.
Diagnosis
Infer underlying problems based on observed evidence.
Instruction
Intelligent teaching so that a student can ask Why, How,
and What If - type questions just as if a human was teaching.
Interpretation Explain observed data.
Monitoring Compare
observed data to expected data to judge performance.
Planning
Devise actions to yield a desired outcome.
Prognosis
Predict the outcome of a given situation.
Remedy
Prescribe treatment for a problem.
Control
Regulate a process. May require interpretation, diagnosis,
monitoring, planning, prognosis, and remedies.
----------------------------------------------------------------------------------------
Table 1.3 Broad Classes of Expert Systems
----------------------------------------------------------------------------------------
Name Chemistry
CRYSALIS Interpret a protein’s
3-D structure
DENDRAL Interpret molecular
structure
TQMSTUNE Remedy Triple Quadruple Mass Spectrometer
(keep it tuned)
CLONER Design
new biological molecules
MOLGEN Design gene-cloning
experiments
SECS
Design complex organic molecules
SPEX
Plan molecular biology experiments
----------------------------------------------------------------------------------------
Table 1.4 Chemistry Expert Systems
----------------------------------------------------------------------------------------
Name Electronics
ACE
Diagnose telephone network faults
IN-ATE Diagnose oscilloscope
faults
NDS
Diagnose national communication net
EURISKO Design 3-D microelectronics
PALLADIO Design and test new VLSI circuits
REDESIGN Redesign digital circuits
CADHELP Instruct for computer-aided design
SOPHIE Instruct circuit fault diagnosis
----------------------------------------------------------------------------------------
Table 1.5 Electronics Expert Systems
----------------------------------------------------------------------------------------
Name
Medicine
PUFF
Diagnose lung disease
VM
Monitor intensive-care patients
ABEL
Diagnose acid-base/electrolytes
AI/COAG Diagnose blood
disease
AI/RHEUM Diagnose rheumatoid disease
CADUCEUS Diagnose internal medicine disease
ANNA
Monitor digitalis therapy
BLUE BOX Diagnose/remedy depression
MYCIN
Diagnose/remedy bacterial infections
ONCOCIN Remedy/manage chemotherapy patients
ATTENDING Instruct in anesthetic management
GUIDON Instruct in
bacterial infections
---------------------------------------------------------------------------------------
Table1.6 Medical Expert Systems
----------------------------------------------------------------------------------------------------------------------------------------------------
Name
Engineering
REACTOR
Diagnose/remedy reactor accidents
DELTA
Diagnose/remedy
STEAMER
GE locomotives Instruct operation – steam powerplant
----------------------------------------------------------------------------------------------------------------------------------------------------
Table 1.7 Engineering
Expert Systems
----------------------------------------------------------------------------------------------------------------------------------------------------
Name
Geology
DIPMETER
Interpret dipmeter logs
LITHO
Interpret oil well log data
MUD
Diagnose/remedy drilling problems
PROSPECTOR Interpret
geologic data for minerals
----------------------------------------------------------------------------------------------------------------------------------------------------
Table 1.8 Geology
Expert Systems
----------------------------------------------------------------------------------------------------------------------------------------------------
Name
Computer Systems
PTRANS
Give prognosis for managing DEC computers
BDS
Diagnose bad parts in switching net
XCON
Configure DEC computer systems
XSEL
Configure DEC computer sales orders
XSITE
Configure customer site for DEC computers
YES/MVS
Monitor/control IBM MVS operating system
TIMM
Diagnose DEC computers
----------------------------------------------------------------------------------------------------------------------------------------------------
Table 1.9 Computer
Expert Systems
Appropriate Domains for Expert Systems
Before starting to build an expert system, it is essential to decide if an expert system is the appropriate paradigm. For example, one concern is whether an expert system should be used instead of an alternative paradigm, such as conventional programming. The appropriate domain for an expert system depends on a number of factors:
• Can the problem be effectively solved by conventional programming? If the answer is yes, then an expert system is not the best choice. For example, consider the problem of diagnosing some equipment. If all the symptoms for all malfunctions are known in advance, then a simple table lookup or decision tree of the fault is adequate. Expert systems are best suited for situations in which there is no efficient algorithmic solution. Such cases are called ill-structured problems and reasoning may offer the only hope of a good solution.
As an example of an ill-structured problem, consider the case of a person who is thinking about travel and visits a travel agent. While most people have a destination and plans, there are exceptions. Table 1.10 lists some characteristics of an ill-structured problem as indicated by the person’s responses to the travel agent’s questions.
Although this is probably an extreme case, it does illustrate the basic concept of an ill-structured problem. As you can see, an ill-structured problem would not lend itself well to an algorithmic solution because there are so many possibilities. In this case, a default option should be exercised when all else fails. For example, the travel agent could say, "Ah ha! I have the perfect trip for you: a round-the-world cruise. Please fill out the following credit card application and everything will be taken care of."
----------------------------------------------------------------------------------------------------------------------------------------------------
Travel Agent’s Questions
Responses
Can I help you?
I'm not sure.
Where do you want to
go?
Somewhere.
Any particular destination?
Here and there.
How much can you afford?
I don't know.
Can you get some money?
I don’t know.
When do you want to go?
Sooner or later.
----------------------------------------------------------------------------------------------------------------------------------------------------
Table 1.10 An Example
of an Ill-structured Problem
In dealing with ill-structured problems, there is a danger in that the expert system design may accidentally mirror an algorithmic solution. That is, the development of the expert system may unknowingly discover an algorithmic solution. An indication that this has happened is if a solution that requires a rigid control structure is foun1 That is, the rules are forced to execute in a certain sequence by the knowledge engineer explicitly setting the priorities of many rules. Forcing a rigid control structure on the expert system cancels a major advantage of expert system technology, which is dealing with unexpected input that does not follow a predetermined pattern. That is, expert systems react opportunistically to their input, whatever it is. Conventional programs generally expect input to follow a certain sequence. An expert system with a lot of control often indicates a disguised algorithm and may be a good candidate for recoding as a conventional program.
• Is the domain well-bounded? It is important to have well-defined limits on what the expert system is expected to know and what its capabilities should be. For example, suppose you wanted to create an expert system to diagnose headaches. Certainly the medical knowledge of a physician would be put in the knowledge base. However, for a deeper understanding of headaches, you might also put in knowledge about neurochemistry, then its parent area of bio-chemistry, then chemistry, molecular biophysics, and so forth perhaps on down to subnuclear physics. Other domains such as biofeedback, psychology, psychiatry, physiology, exercise, yoga, and stress management may also contain pertinent knowledge about headaches. The point: when do you stop adding domains? The more domains, the more complex the expert system becomes.
In particular, the task of coordinating all the expertise becomes a major task. In the real world we know from experience how difficult it is to have coordinated teams of experts working on problems, especially when they come up with conflicting recommendations. If we knew how to program well the coordination of expertise, then we could try programming an expert system to have the knowledge of multiple experts. Attempts have been made to coordinate multiple expert systems in the HEARSAY II and HEARSAY III systems. However, such coordination is a complex task that should be viewed more as research rather than as producing a deliverable expert system product.
• Is there a need and a desire for an expert system? Although it’s great experience to build an expert system, it’s rather pointless if no one is willing to use it. If there are many human experts already, it’s difficult to justify an expert system based on the reason of scarce human expertise. Also, if the experts or users don’t want the system, it will not be accepted even if there is a need for it.
Management especially must be willing to support the system. This is even more critical for expert systems than for conventional programs because expert systems is a new technology. This means that there are few experienced people and more uncertainty about what can be accomplished. However, the area of expert systems deserves more support because it attempts to solve the problems that cannot be solved by conventional programming. The risks are greater, but so are the rewards.
• Is there at least one human expert who is willing to cooperate? There must be an expert who is willing, and preferably enthusiastic, about the project. Not all experts are willing to have their knowledge examined for faults and then put into a computer. Even if there are multiple experts willing to cooperate in the development, it might be wise to limit the number of experts involved. Different experts may have different ways of solving a problem, such as requesting different diagnostic tests. Sometimes they may even reach different conclusions. Trying to code multiple methods of problem solving in one knowledge base may create internal conflicts and incompatibilities.
• Can the expert explain the knowledge so that it is understandable by the knowledge engineer? Even if the expert is willing to cooperate, there may be difficulty in expressing the knowledge in explicit terms. As a simple example of this difficulty, can you explain in words how you move a finger? Although you could say it’s done by contracting a muscle in the finger, the next question is, how do you contract a finger muscle? The other difficulty in communication between expert and knowledge engineer is that the knowledge engineer doesn’t know the technical terms of the expert. This problem is particularly acute with medical terminology. It may take a year or longer for the knowledge engineer to even understand what the expert is talking about, let alone translate that knowledge into explicit computer code.
• Is the problem-solving knowledge mainly heuristic and uncertain? Expert systems are appropriate when the expert’s knowledge is largely heuristic and uncertain. That is, the knowledge may be based on experience, called experiential knowledge, and the expert may have to try various approaches in case one doesn’t work. In other words, the expert’s knowledge may be a trial-and-error approach, rather than one based on logic and algorithms. However, the expert can still solve the problem faster than someone who is not an expert. This is a good application for expert systems. If the problem can be solved simply by logic and algorithms, it is best handled by a conventional program.