Copyright (c) 1996, Edward Brent The following is a text summary of the first lecture for the expert systems topic for the Summer, 1996 course in Decision Making TITLE EXPERT SYSTEMS Lectures Presented at the University of Missouri - Columbia, Summer Session, July, 1996 by Edward Brent Professor of Sociology Adjunct Professor, Computer Engineering & Computer Science socbrent@showme.missouri.edu http://www.missouri.edu/socbrent Begin BEGIN ES LECTURES LECTURE SCHEDULE I. What are Expert Systems and When Should They be Used? II. Representation and Reasoning Strategies III. Shells, Knowledge Acquisition, and Interface Issues IV. Developing Expert Systems V. Expert Systems in a Social Context VI. In-Class Test, Take-Home Project Due, Course Evaluations I. WHAT ARE EXPERT SYSTEMS AND WHEN SHOULD THEY BE USED? WHAT ARE EXPERT SYSTEMS AND WHEN SHOULD THEY BE USED? What Are Expert Systems? The Architecture of Expert Systems Characteristics of Expert Systems Expert Systems and Other Forms of Knowledge When Should Expert Systems Be Used? WHAT ARE EXPERT SYSTEMS? WHAT ARE EXPERT SYSTEMS? Definitions of Expert Systems A Typology of Expert Systems Applications Classic Examples of Expert Systems Contemporary Examples of Expert Systems DEFINITIONS OF EXPERT SYSTEMS DEFINITIONS OF EXPERT SYSTEMS - Programs that do what human experts can do - Programs that do what non-experts cannot do - A vanishing field - A subfield of artificial intelligence - Knowledge-based systems - A definition of expert systems ------------------------------ * The term, "expert system" Return PROGRAMS THAT DO WHAT HUMAN EXPERTS CAN DO EXPERT SYSTEMS ARE PROGRAMS THAT DO WHAT HUMAN EXPERTS DO A common definition of expert systems is...computer programs which perform sophisticated tasks once thought possible only for human experts in a specific substantive domain. PROGRAMS THAT DO WHAT NON-EXPERTS CANNOT DO EXPERT SYSTEMS ARE PROGRAMS THAT DO WHAT NON-EXPERTS CANNOT DO A corollary to the assertion that expert systems do what experts can do is that they also DO WHAT NONEXPERTS CANNOT DO. By this, we mean expert systems provide users with information and advice which users need, which users probably cannot produce on their own, and on which users are dependent. In this respect, expert systems may be contrasted to another common type of program, decision support programs. Those programs generally provide users with information and perform tasks which the users COULD DO THEMSELVES but which users typically WOULD RATHER NOT DO. For example, a program to retrieve sales information and plot a graphic summary for monthly sales performs relatively tedious and detailed tasks which human users would rather not do, but could do themselves if they had to. A VANISHING FIELD ARTIFICIAL INTELLIGENCE IS A VANISHING FIELD Artificial intelligence is a vanishing field because every time we can get a computer program to do something we once thought only humans could do, we no longer think of that activity as something requiring intelligence. - Roger Schank A SUBFIELD OF ARTIFICIAL INTELLIGENCE EXPERT SYSTEMS ARE A SUBFIELD OF ARTIFICIAL INTELLIGENCE Computer Science Artificial Intelligence . . . Natural Robotics Expert Machine Speech Language Systems Vision Recognition . . . Understanding Expert systems are but one specialty within the field of "artificial intelligence". Artificial intelligence is a subfield within computer science. KNOWLEDGE-BASED SYSTEMS KNOWLEDGE-BASED SYSTEMS OR "KBSs" If performance were the sole criterion for labeling a program an expert system, many decision support systems, statistical, and spreadsheet progrmas could be called expert systems. Instead, the term "expert system" is usually reserved for computer programs that achieve expert-level performance in a specific substantive domain using artificial intelligence programming techniques such as symbolic representation, inference, and heuristic search (Buchanan, 1985). These systems are often called knowledge-based systems because their power to solve problems rests primarily in their knowledge base in some specific domain. It is that specific knowledge and their capacity to reason about it that permits expert systems to provide useful advice about real world problems. These knowledge-based systems are to be distinguished from earlier artificial intelligence programs which relied primarily on general problem-solving approaches. A DEFINITION OF EXPERT SYSTEMS A DEFINITION OF EXPERT SYSTEMS Expert systems are computer programs that use artificial intelligence strategies such as symbolic representation, inference, and heuristic search (Buchanan, 1985) to perform sophisticated tasks once thought possible only for human experts. Expert systems differ from earlier artificial intelligence programs based on general problem-solving strategies such as the General Problem Solver (Newell and Simon, 1963). In contrast, expert systems are "knowledge-based" systems that rely on domain-specific knowledge (Feigenbaum, 1977). A TYPOLOGY OF EXPERT SYSTEMS APPLICATIONS A TYPOLOGY OF EXPERT SYSTEMS APPLICATIONS Hayes-Roth, Waterman, and Lenat (1983:14) offer the following typology of expert systems applications. INTERPRETATION - Inferring situation descriptions from sensor data PREDICTION - Inferring likely consequences of given situations DIAGNOSIS - Inferring malfunctions from observables DESIGN - Configuring objects under constraints PLANNING - Designing actions MONITORING - Comparing observations to plan vulnerabilities DEBUGGING - Prescribing remedies for malfunctions REPAIR - Executing a plan to administer a prescribed remedy INSTRUCTION - Diagnosing, debugging, and repairing student behavior CONTROL - Interpreting, predicting, repairing, and monitoring system behaviors CLASSIC EXAMPLES OF EXPERT SYSTEMS CLASSIC EXAMPLES OF EXPERT SYSTEMS MYCIN - Diagnosing and treating infectious blood diseases CADUCEUS (originally called INTERNIST) - medical diagnoses in the field of internal medicine AI-RHEUM - diagnosis and treatment of rheumatological disorders PROSPECTOR - Identifying mineral deposits MACSYMA - symbolic algebraic computation EMYCIN - "Empty" MYCIN (an early rule-based expert system shell) R1 - configuring DEC VAX computer systems HEARSAY-II - speech recognition for connected discourse DIPMETER ADVISOR - diagnoses soil core samples obtained from drills ELECTROPHORESIS INTERPRETER - first expert system on a chip, interprets results from an electrophoresis meter ??? - decides whether to extend credit for American Express card purchases ??? - programs to manage stock portfolios (blamed by many for the 1987 Stock Market Crash) CONTEMPORARY EXAMPLES OF EXPERT SYSTEMS CONTEMPORARY EXAMPLES OF EXPERT SYSTEMS EX-SAMPLE - determining sample size (statistical computation, critique) PEER REVIEW EMULATOR - designing research proposals (semantic knowledge, forms) STATISTICAL NAVIGATOR - identifying appropriate statistics (decision making) WHICHGRAPH - identifying appropriate graphs DESIGNER RESEARCH - designing experiments (design) HYPER-SOC - teaching introductory sociology (simulations, modeling students) MAKING IT - embedded expert system creates intelligent actors behind virtual reality and digitized video interface ARCHITECTURE OF EXPERT SYSTEMS THE ARCHITECTURE OF EXPERT SYSTEMS Expert systems typically contain the following four components: Knowledge-Acquisition User Interface Interface Knowledge Base Inference Engine This architecture differs considerably from traditional computer programs, resulting in several characteristics of expert systems. Return KNOWLEDGE-ACQUISITION KNOWLEDGE-ACQUISITION INTERFACE The knowledge-acquisition interface controls how the expert and knowledge engineer interact with the program to incorporate knowledge into the knowledge base. It includes features to assist experts in expressing their knowledge in a form suitable for reasoning by the computer. This process of expressing knowledge in the knowledge base is called knowledge acquisition. Knowledge acquisition turns out to be quite difficult in many cases--so difficult that some authors refer to the knowledge acquisition bottleneck to indicate that it is this aspect of expert system development which often requires the most time and effort. Debugging faulty knowlege bases is facilitated by traces (lists of rules in the order they were fired), probes (commands to find and edit specific rules, facts, and so on), and bookkeeping functions and indexes (which keep track of various features of the knowledge base such as variables and rules). Some rule-based expert system shells for personal computers monitor data entry, checking the syntactic validity of rules. Expert systems are typically validated by testing their preditions for several cases against those of human experts. Case facilities--permitting a file of such cases to be stored and automatically evaluated after the program is revised--can greatly speed the vaidation process. Many features that are useful for the user interface, such as on-screen help and explanations, are also of benefit to the developer of expert systems and are also part of knowledge-acquisition interfaces. Expert systems in the literature demonstrate a wide range of modes of knowledge acquisition (Buchanan, 1985). Expert system shells on microcomputers typically require the user to either enter rules explicitly or enter several examples of cases with appropriate conclusions, from which the program will infer a rule. USER INTERFACE USER INTERFACE The user interface is the part of the program that interacts with the user. It prompts the user for information required to solve a problem, displays conclusions, and explains its reasoning. Features of the user interface often include Doesn't ask "dumb" questions Explains its reasoning on request Provides documentation and references Defines technical terms Permits sensitivity analyses, simulations, and what-if analyses Detailed report of recommendations Justifies recommendations Online help Graphical displays of information Trace or step through reasoning The user interface can be judged by how well it reproduces the kind of interaction one might expect between a human expert and someone consulting that expert. KNOWLEDGE BASE THE KNOWLEDGE BASE The knowledge base consists of specific knowledge about some substantive domain. A knowledge base differs from a data base in that the knowledge base includes both explicit knowledge and implicit knowledge. Much of the knowledge in the knowledge base is not stated explicitly, but inferred by the inference engine from explicit statements in the knowledge base. This makes knowledge bases have more efficient data storage than data bases and gives them the power to exhaustively represent all the knowledge implied by explicit statements of knowledge. There are several important ways in which knowledge is represented in a knowledge base. For more information, see knowledge representation strategies. Knowledge bases can contain many different types of knowledge and the process of acquiring knowledge for the knowledge base (this is often called knowledge acquisition) often needs to be quite different depending on the type of knowledge sought. TYPES OF KNOWLEDGE There are many different kinds of knowledge considered in expert systems. Many of these form dimensions of contrasting knowledge explicit knowledge implicit knowledge domain knowledge common sense or world knowledge heuristics algorithms procedural knowledge declarative or semantic knowledge public knowledge private knowledge shallow knowledge deep knowledge metaknowledge INFERENCE ENGINE INFERENCE ENGINE The inference engine uses general rules of inference to reason from the knowledge base and draw conclusions which are not explicitly stated but can be inferred from the knowledge base. Inference engines are capable of symbolic reasoning, not just mathematical reasoning. Hence, they expand the scope of fruitful applications of computer programs. The specific forms of inference permitted by different inference engines varies, depending on several factors, including the knowledge representation strategies employed by the expert system. CHARACTERISTICS OF EXPERT SYSTEMS CHARACTERISTICS OF EXPERT SYSTEMS Because the strength of expert systems is specific knowledge... - expert systems must be specialized, just like human experts Because the domain knowledge is separated from program code... - domain knowledge separated from program code can be more understandable - general purpose expert systems shells are possible - expert systems reduce the need for programming skill Because expert systems use a general inference engine... - the same inference engine could be used on different knowledge bases - different inference engines could be applied to same knowledge base Because expert systems rely heavily on symbolic reasoning... - they expand the scope of fruitful applications of computer programs Because expert systems are computer programs... - expert systems are inherently cumulative To the extent expert systems rely on heuristics... - expert systems are not guaranteed to be correct and sometimes fail Return EXPERT SYSTEMS MUST BE SPECIALIZED, JUST LIKE HUMAN EXPERTS EXPERT SYSTEMS SPECIALIZED, JUST LIKE HUMAN EXPERTS Because the power of expert systems derives from the specific knowledge base in a specific content domain, expert systems, like human experts, are only "expert" in specific areas. This means we are not likely to see a broad general purpose expert system which is expert in everything. Something which seems relatively simple, like common sense is far more difficult to model with expert systems than highly specialized knowledge of respected professionals. This also means that one of the common problems in expert systems is their performance on the boundaries of their competence. Ideally, we would like expert systems to display graceful degradation when applied to problems beyond their expertise. That is, we would like them to recognize their limits and inform the user when they don't believe they can help them. Some expert systems, like some human experts, are not very good at admitting they have limits. DOMAIN KNOWLEDGE SEPARATED FROM PROGRAM CODE CAN BE MORE UNDERSTANDABLE DOMAIN KNOWLEDGE SEPARATED FROM COMPUTER CODE IS MORE UNDERSTANDABLE Because the knowledge base containing domain-specific knowledge is separated from the general reasoning principles embodied in the inference engine, expert systems make it possible to represent knowledge about the domain in a manner that is similar to that used by human experts. Thus, instead of having to convert expert knowledge into computer code, the domain expert only needs to express it as a series of English-like statements such as rules, which are much closer to the way the expert actually thinks about the knowledge. This makes it much easier than converting the knowledge into computer code, and the expert can concentrate on improving the knowledge base and representing knowledge accurately rather than being distracted by complex and difficult computer programming tasks. reduces need for programming skill permits knowledge to be represented in manner more easily understood by humans GENERAL PURPOSE EXPERT SYSTEMS SHELLS ARE POSSIBLE GENERAL PURPOSE EXPERT SYSTEMS SHELLS ARE POSSIBLE Since the knowledge base is separated from the rest of the program, it is possible to build a program having the other three components which non-programmers can then use to complete an expert system. Such programs are called "expert system shells". Knowledge-Acquisition User Interface Interface Knowledge Base --left empty, to be completed by the user Inference Engine EXPERT SYSTEMS REDUCE THE NEED FOR PROGRAMMING SKILL EXPERT SYSTEMS REDUCE THE NEED FOR PROGRAMMING SKILL Expert systems separate the program code from the knowledge base, and permit the knowledge base to be expressed in a syntax easily understood by non-programmers. This permits non-programmers or people with little programming skill to work with an expert system shell to build their own expert system. THE SAME INFERENCE ENGINE COULD BE USED ON DIFFERENT KNOWLEDGE BASES For example, the inference engine developed for MYCIN was converted into EMYCIN (for "empty" MYCIN) to make a general expert system which could be applied to a number of problems. EXPAND THE SCOPE OF FRUITFUL APPLICATIONS OF COMPUTER PROGRAMS EXPERT SYSTEMS EXPAND THE SCOPE OF FRUITFUL APPLICATIONS OF COMPUTER PROGRAMS Because expert systems rely on symbolic reasoning as well as computational (numeric) reasoning), they have expanded the scope of computing to include tasks which can only be solved using nonnumeric, symbolic reasoning. Thus, it is possible to apply expert systems programs to problems where formal algorithmic solutions based on numeric analysis are not available. This greatly expands the useful scope of computing and offers particular promise for disciplines and applications where numeric, formal, algorithmic solutions are not readily available. For example, expert systems can be applied to - diagnosing diseases - configuring computers - predicting behavior in social settings - other problems not amenable to formal numeric solution EXPERT SYSTEMS ARE INHERENTLY CUMULATIVE EXPERT SYSTEMS ARE INHERENTLY CUMULATIVE Knowledge bases developed in expert systems are cumulative. - A knowledge base developed by one expert can be modified or improved upon by another. - Over time, the same expert can modify and improve the knowledge base in the face of new information. - Unlike written documents which must be rewritten extensively, knowledge bases, much like data bases, can be updated incrementally through minor changes. - Those changes and their implications then immediately become available throughout the program. EXPERT SYSTEMS AND OTHER FORMS OF KNOWLEDGE EXPERT SYSTEMS AND OTHER FORMS OF KNOWLEDGE Another way to understand the strengths and limitations of expert systems is by comparing them to more familiar forms of knowledge. There are several important ways in which expert systems differ from human experts, manuals, numeric algorithms and other forms of knowledge. Books or manuals Human experts Traditional numeric algorithms Traditional programs Data bases (versus knowledge bases) First generation artificial intelligence programs Machine learning strategies NOTE: It is difficult to compare expert systems to other types of programs cleanly since new features are often added and there is no accepted standard for expert systems like spreadsheets or word processors EXPERT SYSTEMS COMPARED TO BOOKS OR MANUALS EXPERT SYSTEMS COMPARED TO BOOKS OR MANUALS Just as manuals present the user with considerable information, so do expert systems. Unlike manuals, however, expert systems can tailor their advice to fit the problem of a particular user. With a book, readers may never be quite sure whether or not they have overlooked something important or misunderstood the advice. SIMILARITIES: both present user with much information DISSIMILARITIES: expert systems can tailor advice to the particular user with book readers may overlook important issues or misunderstand advice EXPERT SYSTEMS COMPARED TO HUMAN EXPERTS EXPERT SYSTEMS COMPARED TO HUMAN EXPERTS Like human experts, expert systems are able to ask users a series of questions, and then, based on those answers, recommend specific actions to be taken, personalized to fit the needs of that person. However, unlike human experts, expert systems are not likely to overlook something, to have a bad day, or to get angry, hostile, or bored. SIMILARITIES: both ask users questions both recommend actions based on answers both give personalized advice DISSIMILARITIES: expert systems always have even performance never have bad days, get angry, hostile, or bored expert systems can be duplicated and distributed widely expert systems don't mind being called in the middle of the night expert systems don't retire, quit, or die EXPERT SYSTEMS COMPARED TO TRADITIONAL NUMERIC ALGORITHMS EXPERT SYSTEMS COMPARED TO TRADITIONAL NUMERIC ALGORITHMS Expert systems resemble traditional numeric algorithms in that they can systematically address a specific problem and provide a written report to the user. However, unlike numerical algorithms, expert systems do not force every problem into a strict mathematical mold. Expert systems can be applied to a much broader range of problems than numeric algorithms, including qulaitative problems that are clearly inappropriate for mathematical solutions. However, because they may use heuristic and unproven strategies, expert systems may produce solutions that have less assurance that they are correct than more formal mathematical algorithms. SIMILARITIES both systematically address a specific problem both provide written report DISSIMILARITIES expert systems do not force problems into strict mathematical mold expert systems can be applied to much broader range of problems expert systems produce solutions which may be incorrect WHEN SHOULD EXPERT SYSTEMS BE USED? WHEN SHOULD EXPERT SYSTEMS BE USED? Gonzalez and Dankel (1993) offer the following questions to assist in determining whether a knowledge-based approach is the best approach for a particular problem. Is human problem-solving knowledge being replicated in the solution of the problem? Is the problem-solving knowledge heuristic in nature or is it predominantly algorithmic? Does the knowledge or expertise periodically change or does it remain constant? If expertise is involved, is the expertise fairly well understood and accepted? Are the input data always complete and correct? (Could users answer the questions?) Can the problem be solved better through other means? Does it pass the telephone test? To these, I would add the following considerations: Is the problem too complex to be solved? Is an expert willing, able, and available for the project? BEGIN ES LECTURES LECTURE SCHEDULE I. What are Expert Systems and When Should They be Used? II. Representation and Reasoning Strategies III. Shells, Knowledge Acquisition, and Interface Issues IV. Developing Expert Systems V. Expert Systems in a Social Context VI. In-Class Test, Take-Home Project Due, Course Evaluations II. REPRESENTATION AND REASONING STRATEGIES REPRESENTATION AND REASONING STRATEGIES The Representation Problem Procedural Rules Frames Semantic Networks Reasoning Under Uncertainty THE REPRESENTATION PROBLEM THE REPRESENTATION PROBLEM Before expert systems can reason symbolically about knowledge, it is necessary to represent knowledge within the computer in such a way that 1. Information can be stored and retrieved efficiently. 2. The knowledge is faithful to the phenomenon. 3. The computer can "understand" the phenomenon -- that is, the computer can manipulate the information in substantively meaningful ways. This is often called the representation problem and constitutes one of the central problems in artificial intelligence research (Barr and Feigenbaum, 1981, chpt. 3). Examples EXAMPLES ILLUSTRATING THE REPRESENTATION PROBLEM EXAMPLES ILLUSTRATING THE REPRESENTATION PROBLEM A TEXT representation of knowledge, for example, may faithfully represent the phenomenon, but to the computer it is not knowledge, but merely text--sequences of characters having no substantive significance. The comptuer has no "understanding" of that knowledge and cannot manipulate it in meaningful ways. MATHEMATICAL MODELS, on the other hand, can usually be understood and manipulated by the computer, but sometimes oversimplify and are then unfaithful to the phenomena they are trying to model. Expert systems typically address the representation problem by using symbolic representations of knowledge about which the program can reason logically. We shall show that there are several such symbolic representations, each capable of different kinds of logical reasoning and each appropriate for different varieties of substantive knowledge. PROCEDURAL RULES PROCEDURAL RULES Rule-based systems represent knowledge as a series of production rules-- statements of the form "If x Then y" (Waterman and Hayes-Roth, 1978) containing certain antecedent conditions which, when fulfilled, "trigger" or "fire" the rule asserting the consequent to be true. Consequences deduced in this manner by rules are added to the knowledge base as new facts. Complexity of Rules Graphical Representations of Rules Varieties of Knowledge That Can Be Represented by Rules Rule-Based Reasoning COMPLEXITY OF RULES COMPLEXITY OF RULES Each rule has one or more antecedent conditions (those in the IF clause) and one or more subsequent conditions (those in the THEN clause). Rules can vary in complexity, having a single antecedent condition or many antecedent conditions linked by Boolean operators such as "and," "or," "less than," "greater than", and so on. There may also be one or several consequents. By making the antecedents of some rules the consequents of others, these independent rules can be linked in a network of interrelated rules to form an integrated knowledge base. Together, these rules may represent complex systems of knowledge. Many rule-based programs contain hundreds of rules. Rules permit complex problems to be broken down into simpler components which, when solved, contribute to the solution of the larger problem. One rule-based expert system, XCON, uses literally thousands of rules to configure VAX computers. GRAPHICAL REPRESENTATIONS OF RULES GRAPHICAL REPRESENTATIONS OF RULES A rule, such as "IF D THEN E" can be represented graphically as a directed path connecting the antecedent to the consequent as shown below: By making the antecedents of some rules the consequences of others, these independent rules can be linked in a network of interrelated rules to form an integrated knowledge system such as that diagrammed below. The rules to the left are represented by the graph on the right. VARIETIES OF KNOWLEDGE THAT CAN BE REPRESENTED BY RULES VARIETIES OF KNOWLEDGE THAT CAN BE REPRESENTED BY RULES "IF...THEN" procedural rules can be constructed to represent a wide variety of knowledge types, including all of the following (Brent, 1986): mathematical or statistical formulae causal relationships logical classifications logical statements principles informal rules of thumb TYPES OF REASONING IN RULE-BASED SYSTEMS TYPES OF REASONING IN RULE-BASED SYSTEMS Rule-based systems typically support some kinds of logical reasoning, but not others. For example, most rule-based systems can reason using propositional logic, but do not permit the more powerful predicate logic. Artificial intelligence languages such as PROLOG, on the other hand, are based on predicate logic. Propositional Logic Predicate Logic In addition to logical reasoning strategies, rule-based systems also typically employ strategies to schedule the sequence in which rules are considered. These are forward or backward chaining strategies. Forward and Backward Chaining Finally, some rule-based systems employ pattern matching algorithms to handle more complex forms of reasoning than can be expressed by other methods. Pattern Matching permit modus ponens but do not permit modus tollens reasoning. PROPOSITIONAL LOGIC TYPES OF REASONING IN RULE-BASED SYSTEMS Propositional logic is one of the oldest and simplest forms of logic permitting us to represent knowledge as a series of simple statements that are assigned truth values and to evaluate the truth or falsity of complex statements formed by connecting simple statements with propositional connectives ("and", "or", "not", "if-then", "equals"). A simple proposition is a statement that is either true or false. For example, each of the following are propositions that are true or false. It is raining E=mc2 Complex propositions are combinations of simple propositions connected by propositional connectives. Here are some examples of complex propositions. I've fallen AND I can't get up to be OR not to be Modus Ponens and Modus Tollens Reasoning Limitations of Propositional Logic permit modus ponens but do not permit modus tollens reasoning. MODUS PONENS AND MODUS TOLLENS REASONING MODUS PONENS AND MODUS POLLENS REASONING Two common forms of reasoning in propositional logic are modus ponens and modus tollens reasoning. Modus ponens reasoning If A then B takes the general form: A is true Example Therefore B is true Expert systems use reasoning of this sort to derive new "facts," which then become part of the knowledge base in either a forward-chaining or backward-chaining system. However, many expert systems shells do not support modus tollens reasoning. Modus tollens reasoning If A then B takes the general form: Not B Example Therefore Not A This rule of logic, modus tollens, is not implemented in many expert systems. Hence, these expert systems would not be able to conclude that A is not true under such circumstances without "tricking" the system to make these inferences. LIMITATIONS OF PROPOSITIONAL LOGIC Limitations of Propositional Logic Propositional logic has a number of significant limitations that reduce its effectiveness as a means of representing and reasoning within expert systems. Thus, expert systems based on propositional logic may not be as sophisticated as they seem, giving the illusion of greater intelligence than they actually have. Some of the most important of these limitations are the following. Indivisible Propositions Incapable of Dealing with Quantifiers The Combinatorial Explosion INDIVISIBLE PROPOSITIONS INDIVISIBLE PROPOSITIONS Propositional logic assigns truth values to entire propositions. Propositional logic is not capable of analyzing the components of that proposition. We can illustrate the limits of propositional logic with a simple rule from one of Goffman's insights into team behavior. Earlier we pointed out some of the assertions Goffman made regarding team member obligations to one another in the presence of an audience to help cover when someone commits a "false note" and to avoid disagreements in public. Even these relatively simple assertions quickly show some of the limits of propositional logic. In order to express these relationships employing propositional logic we must do something like the following. If (A) George and John avoid publicly critizing each other and (B) George and John postpone taking a public stand until they know the team position Then (C) George and John successfully avoid public disagreement If (D) George and John hide prior consultation from others Then (E) George and John's public agreement appears to be based on independent decisions If (C) George and John successfully avoid public disagreement and (E) George and John's public agreement appears to be based on independent decisions Then (F) George and John collaborate to maintain a definition of the situation If (F) George and John collaborate to maintain a definition of the situation then (G) George and John are on the same team Note that these rules correspond to the rules diagrammed earlier in Figure One. Note too that an expert system permitting modus ponens reasoning could use rules like these to determine whether two actors were on the same team (i.e., to conclude G from ot Note that these rules correspond to the rules diagrammed earlier in Figure One. Note too that an expert system permitting modus ponens reasoning could use rules like these to determine whether two actors were on the same team (i.e., to conclude G from other evidence), but unless the expert system also permits modus tollens reasoning, it could not use the same rules to infer that because two actors are on the same team, they will exhibit these behaviors. In addition, these rules expressed in propositional logic are not as sophisticated as they seem. The rules are more clearly represented as seven specific propositions connected by the "and," and "if-then" connectives as illustrated below for the first rule: If (A)_George_and_John_avoid_publicly_critizing_each_other and (B)_George_and_John_postpone_taking_a_public_stand_until_they_know_the_team_position Then (C)_George_and_John_successfully_avoid_public_disagreement Propositional logic always takes the form If A then B where A and B are single, nondivisible propositions and reasoning can only be on the level of assessing the truth or validity of the entire proposition. All this program "knows" is whether the proposi Propositional logic always takes the form If A then B where A and B are single, nondivisible propositions and reasoning can only be on the level of assessing the truth or validity of the entire proposition. All this program "knows" is whether the proposition on the left is true or false. It doesn't "understand" the link implied between "George" and some action. Nor does it understand the components of any of the other propositions. It recognizes no relationship between any assertion about George and any other assertions about George. It can apply modus pollens reasoning to conclude the consequent propositions are true if the antecedent propositions are true, but it cannot employ modus tollens reasoning to infer that if the consequent propositions are false then at least one of the antecedent conditions must also be false. INCAPABLE OF DEALING WITH QUANTIFIERS INCAPABLE OF DEALING WITH QUANTIFIERS Another major limitation of propositional logic is that it is incapable of dealing with quantifiers such as "all" or "some." This is why we were forced to word the rule above so concretely. In propositional logic we would need a separate rule such as that above for each person or combination of persons on the same team. We are unable to assert a general rule to cover the multiple instantiations of this general principle. This makes programs using propositional logic particularly susceptible to becoming overwhelmingly complex as the number of poten- tial combinations that must be considered increases geometrically. This problem is called the "combinatorial explosion" and is a serious problem all formal models must face. Rule-based expert systems make the representation of procedural knowledge far easier than coding in traditional languages because expert system programs can search through all rules in the knowledge base and determine which rules should fire. In contrast, traditional procedural programs written in Pascal or BASIC would have to explicitly guide the program along various decision paths. A complex decision tree with many options can be slow and tedious to program using traditional languages. Expert systems make it much easier to express the knowledge. THE COMBINATORIAL EXPLOSION The Combinatorial Explosion However, if there are many antecedent conditions required, for example, to classify a phenomenon into its appropriate sociological category, this may lead to a combinatorial explosion of possible combinations of conditions. For example, five antecedent conditions, each having two possible categories produces 25 or 32 possible combinations. If there are three possible categories it balloons to 35 or 243 possible combinations. If uncertain- ties are expressed as values on a scale from 0 to 10, then there are 115 or 161,051 possible combinations. These are not unrealistic examples. In the Statistical Navigator program (Brent, et al., 1993a) to advise researchers on the appropriate form of statistical analysis for their research problem some of the statistics had over 20 different criteria, each scaled from 0 to 10 for 6.73 x 1020 possible combinations. If we had used a separate rule for each possible combination we would still be writing rules. There are ways to avoid this combinatorial problem, even within propositional logic, by including rules that group conditions into broader categories. But the easiest way to avoid this problem is to employ predicate logic. PREDICATE LOGIC PREDICATE LOGIC Many expert system shells and artificial intelligence programming languages such as PROLOG (Clocksin and Mellish, 1984 ) employ a more sophisticated form of logic, predicate logic. Predicate logic is an alternative form of logic having far greater capabilities than the propositional logic described above. Predicate logic reasons at the level of "predicates" or relationships among objects and their qualities or attributes. Predicate logic is capable of expressing relationships among multiple objects rather than just a single object. Such relationships are expressed as predicates, and the objects and their attributes in the relationships are expressed as arguments or terms of the predicate. Any particular predicate can be true or false and its truth value varies for different terms. Thus, predicate logic can represent variables and a predicate can be true for one set of terms and false for others. An Example of Predicate Logic Characteristics of Predicate Logic Reasoning with Predicate Logic Sample Applications of Predicate Logic AN EXAMPLE OF PREDICATE LOGIC AN EXAMPLE OF PREDICATE LOGIC: GOFFMAN'S ASSERTIONS ABOUT TEAMS As an example, predicate logic might be used to represent Goffman's assertions about teams as a series of predicates (known facts) and rules linking predicates, as follows. FACTS avoid_criticism(George, John) postpone_public_stand(George, John) hide_prior_consultation(George, John) hide_prior_consultation(John, Susan) NOT avoid_criticism(John, Susan) RULES If avoid_criticism(X, Y) and postpone_public_stand(X, Y) Then avoid_public_disagreement(X, Y) If hide_prior_consultation(X, Y) Then public_agreement_appears_independent(X, Y) If avoid_public_disagreement(X, Y) and public_agreement_appears_independent(X, Y) Then collaborate_to_maintain_definition(X, Y) If collaborate_to_maintain_definition(X, Y) then on_same_team(X, Y) CHARACTERISTICS OF PREDICATE LOGIC PREDICATE LOGIC AVOIDS MOST OF THE LIMITATIONS OF PROPOSITIONAL LOGIC These rules are expressed as general principles for any two actors, X and Y and are not limited to specific actors as was the earlier expression of these rules in propositional logic. Thus, these rules can be used for many different specific instantiations of the variables and statements may be true for some instantiations and false for others. Note that predicate logic is capable of reasoning about predicates or components of a proposition, unlike propositional logic. Predicate logic can express rules such as If then and is capable of reasoning about the different components of those propositions. Predicate logic can evaluate an expression for different instantiations of variables and can recognize that it may be true for some values and false for others. Because predicate logic can use general rules to represent a wide range of specific relations, it is less susceptible to a combinatorial explosion in representing knowledge and better able than is propositional logic to "explain" its reasoning by appeal to general principles. Thus, predicate logic is capable of providing what philosophers of science call "covering law" explanations of its reasoning (Hempel, 1965). REASONING WITH PREDICATE LOGIC Methods of reasoning for predicate logic The principal forms of reasoning in predicate logic are unification and resolution. Unification Resolution UNIFICATION UNIFICATION Unification is essentially a process of pattern matching in which the program can determine the truth or falsity of any particular assertion by examining the knowledge base to assess the truth or falsity of each of its component predicates. A component predicate is true if it matches a true assertion in the knowledge base. Unification can be used in this knowledge base to answer questions such as the following. QUESTION ANSWER Which people avoid public criticism of each other? George and John Which people hide prior consultation? George and John, John and Susan Which people postpone public stands? George and John RESOLUTION RESOLUTION Predicate logic also uses a form of reasoning called resolution. Resolution can be used to infer new facts not explicitly represented in the knowledge base in the following manner: If (A or B) is true and (not B or C) is true Then (A or C) is true Whenever the program can find two clauses containing the same component, both clauses are known to be true, and the shared component is in positive form in one clause and negative form in the other, then the program can conclude that all the other components of the two clauses are true. Both modus tollens and modus pollens reasoning are special cases of resolution. Resolution is a very powerful form of reasoning and has been used in theorem proving tasks. When combined with unification, resolution can be used to make a wide range of logical inferences such as the following inferences for our example knowledge base. QUESTION ANSWER Are George and John on the same team? Yes Are John and Susan on the same team? No Are George and Susan on the same team? No SAMPLE APPLICATIONS OF PREDICATE LOGIC SAMPLE APPLICATIONS OF PREDICATE LOGIC Predicate logic can be used to represent and reason about a wide range of social science concepts. Kuipers (1975) and Aikens (1983) discuss how attitudes, values, and beliefs can be represented in the computer. Brent (1986) showed how rule-based and logic-based expert systems can be used to represent norms, levels of aggregation, contextual effects, emergent properties, and classification and identification. Predicate logic was used by Brent, et al. (1989) in an earlier version of a program to reason about Erving Goffman, and by Masuch and LaPotin (1989) in their model of organizational choice. FORWARD AND BACKWARD CHAINING FORWARD AND BACKWARD CHAINING Two procedures are commonly used to schedule the reasoning such systems: forward chaining and backward chaining. FORWARD CHAINING In forward chaining, the system begins with a series of state- ments, then reasons forward to deduce implications of those, until it has reached all the conclusions it can reach with the available information and rendered its advice to the user. BACKWARD CHAINING In backward chaining, the system begins with a choice or conclusion it wants to assess, then traces the rules backward to determine what information it needs to make that choice. For each antecedent the program examines rules to deduce it, and the backward process continues until it reaches variables having no rules to infer them. The program then asks the user for the values it cannot deduce. Once those values are provided, it uses them to go forward in the chain of reasoning to determine its conclusion. Continue FORWARD AND BACKWARD CHAINING (CONTINUED) FORWARD AND BACKWARD CHAINING (CONTINUED) Backward chaining programs ask the user only for the values they must have to determine their conclusions and ignore all other information they don't need. For example, for the rules below, a backward chaining system would begin with the final goal (G) and look for antecedents it needed to determine that goal (F). F then becomes the intermediate goal. If there are any rules leading to that antecedent, then it looks for antecedents to those rules (C and E). C and E then become intermediate goals and the process repeats until an antecedent is found that has no rules leading to it (A, B, and D). Then the user is asked the value of antecedents one at a time. If any of the antecedents for a rule do not meet the conditions to fire the rule, then the program quits asking for other information related to that rule. For example, if A is false in this example, a backward chaining program will then not bother to ask about B since it already knows it cannot fire the rule. Forward and Backward Chaining Illustration Selecting Forward or Backward Chaining FORWARD AND BACKWARD CHAINING ILLUSTRATION FORWARD AND BACKWARD CHAINING ILLUSTRATED Select which form of chaining you wish to examine using the radio buttons. As you input the value of each variable, the program selects the next variable to ask you. As each variable's value is determined, it is checked off in the diagram. Forward Chaining Backward Chaining A A B B C C D D E E F F G G Reset SELECTING FORWARD OR BACKWARD CHAINING Selecting forward or backward chaining Forward chaining programs typically must ask the user for all information every time. In the example rules displayed in the graphical diagram earlier a forward chaining system would always ask for the value of A, B, and D regardless of the responses of the user. Thus, forward chaining systems are often used where there are only a few inputs and many possible conclusions. Backward chaining systems are more efficient when there are many possible inputs, only a few of which may be needed to determine the conclusions. PATTERN MATCHING PATTERN MATCHING FRAMES FRAMES Frames, first proposed by Minsky (1975) are a knowledge representation strategy in which each frame represents a single bundle of related information. An Example Frame Frame-Based Reasoning Applications of Frames Frames vs Other Knowledge Representation Strategies AN EXAMPLE FRAME AN EXAMPLE FRAME Goffman's assertions about teams can be represented using frames as in the figure below. In this figure, the "George" frame, describing the person George, contains several slots (gender, competence, and so on). Some slots are filled in with specific information (e.g., George's age is "21"). Other slots are blank (e.g., George's personal goals are unknown at this time and are left blank). Other slots are filled in with default information which is presumed to be true in the absence of explicit information to the contrary (e.g., the obligations of team members are presumed to include avoiding the appearance of collusion and so on unless otherwise indicated). Still other slots are filled in with pointers to other frames and inherit properties of those other frames unless specified otherwise (e.g., George's gender points to the "Male" frame where general characteristics of males can be described in more detail), permitting many frames to be linked to one another to represent complex knowledge. FIGURE: An Example of Frame-Based Reasoning AN EXAMPLE OF FRAME-BASED REASONING FRAME-BASED REASONING FRAME-BASED REASONING There are three common forms of reasoning used by frames: default knowledge, inheritance, and the use of procedural rules embedded in frames. Default Knowledge Inheritance Using Procedural Rules in Frames DEFAULT KNOWLEDGE DEFAULT KNOWLEDGE A surprisingly powerful form of knowledge is "default knowledge." This is knowledge which is assumed to be true about a frame unless specified otherwise. For example, a person frame in a medical expert system may include default knowledge such as the following: Each person is assumed to have two arms, two eyes, two kidneys, two lungs, and so on. Only for persons who lack two of a specific organ or body part is it necessary to specify any additional information. The reason default knowledge is so powerful is because it permits frames to represent a great deal of information very efficiently. For example, a frame representing a specific piece of equipment in a warehouse could, by default, assume the equipment is assembled and in proper working order. When default knowledge corresponds to the most common state in the population of items represented, it is most effective. INHERITANCE INHERITANCE One of the most powerful forms of reasoning in frames is inheritance. Specialized frames can "inherit" properties of more general frames. For example, in our example frame-based representation of Goffman's work, the "George" frame can inherit properties of the "Actor" frame without having to specify those properties again. This permits great economies of representation since many specialized frames can inherit the properties of a few more general frames by default without requiring those properties to be respecified in each instance. Only when the default properties are not inherited is there a need for an explicit statement in the knowledge base. For example, we might want to point out if George was an unusually incompetent actor in social settings, leading him to act in an inappropriate manner. USING PROCEDURAL RULES IN FRAMES USING PROCEDURAL RULES IN FRAMES Frames can be used to represent both declarative knowledge (e.g., facts such as who, what, where, when, etc.) and procedural knowledge. Procedural knowledge is often represented by production rules where procedures are attached to specific slots or entire frames (see Aikens, 1983). A common method is to use demons--procedural rules executed only if certain conditions are found to be true. Demons include rules for determining the value of a frame if it is unknown and needed and rules to be fired if the value in a slot changes. The latter strategy is used here and is illustrated in Figure Three where, for example, the Competence slot for the "George" frame could have a procedural attachment which, when social competence is unknown, attempts to infer it from the person's age, experience, and other attributes. APPLICATIONS OF FRAMES APPLICATIONS OF FRAMES Frames have been used to represent knowledge in programs for natural language understanding where they have proven to have great economy of representation. Frames have been employed in sociology to represent the qualitative reasoning by theorists such as Goffman (Brent, et al., 1989). The complexity of reasoning with frames, involving multiple levels of abstraction and complex semantic relationships offers a sophisticated form of computational reasoning and appears to address many of the concerns raised by Blumer's (1955) critique of variable analysis in sociology. FRAMES VS OTHER KNOWLEDGE REPRESENTATION STRATEGIES FRAMES VS OTHER REPRESENTATION STRATEGIES Frames vs Semantic Networks Like semantic networks, frames can express a rich variety of links between concepts including relations such as is_a, has_a, subset_of, and soon. Unlike semantic networks, frames combine these links into bundles of related information and provide a wide variety of ways to reason about that knowledge. Any semantic network can be represented by frames and frames can be represented by a semantic network. However, one representation may be more efficient than another for a specific purpose. Frames vs Data Base Management Systems Frames have many similarities to data base management systems, particularly relational databases, and procedures for forming normalized relational databases can be used to help design a frame-based representation of knowledge that represents knowledge efficiently in the computer and helps to avoid many of the problems of a combinatorial explosion (Brent, 1985). Frames have been used to represent knowledge in programs for natural language understanding where they have proven to have great economy of representation. Frames have been employed in sociology to represent the qualitative reasoning by theorists such as Goffman (Brent, et al., 1989). The complexity of reasoning with frames, involving multiple levels of abstraction and complex semantic relationships offers a sophisticated form of computational reasoning and appears to address many of the concerns raised by Blumer's (1955) critique of variable analysis in sociology. SEMANTIC NETWORKS SEMANTIC NETWORKS Another commonly-used strategy for representing and reasoning about knowledge with expert systems is the semantic network. Semantic networks were originally developed to represent knowledge in sentences (Quillian, 1968) but have since been generalized to include associative networks of a wide range of types, including physical and causal relationships among variables (Gonzalez and Dankel, 1993). Carley's (1988) maps used to permit her expert systems programs to help human coders code text data are essentially semantic networks. A semantic network defines a concept through a directed graph expressing its linkages with other concepts and properties. Semantic networks permit items to be linked with labeled relationships. These relationships commonly include generic relationships such as is_a, has_properties, subset_of, and so on. Semantic networks can express complex interrelationships among concepts and can be very effective at representing complex semantic distinctions in sociological theories such as those characteristic of Goffman's work. For example, our hypothetical example of teamwork might be partially represented in a semantic network as shown in Figure Two. FIGURE: A Semantic Network View of Teams Reasoning with Semantic Networks Advantages and Disadvantages of Semantic Networks A SEMANTIC NETWORK VIEW OF TEAMS REASONING WITH SEMANTIC NETWORKS Reasoning with Semantic Networks Semantic networks are particularly good at representing knowledge in the form of hierarchies. They can also represent complex causal relationships. Their explicit links and visual diagrams can make knowledge quite clear. Much of the reasoning with semantic networks is in the form of deducing indirect links between concepts based on direct links explicitly stated. Those inferences depend on whether the links are transitive (e.g., x->y and y>z implies x>z), commutative (e.g., x->y implies y-> x), and so on. For example, in the semantic network representing Goffman's assertions regarding teamwork above, we can answer questions such as the following: QUESTION ANSWER Which people are on the same team? George and John Who is on the same team as George? John Semantic networks are often combined with rules to be able to perform a wide range of reasoning such as answering the question, "Would George ignore John's mistake?" ADVANTAGES AND DISADVANTAGES OF SEMANTIC NETWORKS ADVANTAGES AND DISADVANTAGES OF SEMANTIC NETWORKS The wide range of possible kinds of links and the ways they might combine to form indirect linkages, plus the large number of concepts usually included in a semantic network make this form of representation susceptible to a combinatorial explosion. Semantic networks have difficulty associating procedural knowledge with the facts represented by the network and, since they lack any means of bundling related facts into associated clusters, usually result in a proliferation of many different concepts and linkages, producing a complex representation that may require extensive search operations to reach conclusions. REASONING UNDER UNCERTAINTY REASONING UNDER UNCERTAINTY Because of the many variables that affect social life, a deterministic reasoning strategy could in many cases, not do justice to the complexity of social life. Instead, much sociological knowledge can only be expressed using uncertainties. Expert systems handle reasoning under uncertainty in a variety of ways. Bayesian approaches can be used when there is substantial historical empirical data available to provide reasonable estimates of the probabilities. When data are less plentiful expert systems often rely on strategies such as fuzzy logic (Zadeh, 1965, 1986; Negoita, 1985). Some expert systems simply treat uncertainties as independent or dependent probabilities (Benfer, et al., 1991:58-59). Some systems permit users to attach uncertainties to specific evidence they provide, while others attach uncertainty only to the inferences drawn. Bayesian Analysis Fuzzy Logic Example Reasoning Under Uncertainty for Different Shells EXAMPLE REASONING UNDER UNCERTAINTY FOR DIFFERENT SHELLS EXAMPLE REASONING UNDER UNCERTAINTY FOR DIFFERENT SHELLS As an example, consider two of the three ways the expert system shell, EXSYS, can reason under uncertainty. One method EXSYS uses is the averaging method. Imagine if we had two separate rules each of which can conclude that two people are on the same team. If one rule assigns this conclusion a probability of 80/100 and a second rule assigns the same conclusion a probability of 30/100, then the averaging method would assign this conclusion the average of the two or 55/100. Another method for handling uncertainties available from EXSYS is to multiply the probabilities to compute the final value for this conclusion. In this example, our final probability would be (80/100) * (30/100) = 24/100. Notice that these methods produce very different results: one is 55/100, the other is 24/100. Many rules making the same conclusion at a relatively high level (say 80/100) using the multiplicative method would produce the interest- ing result that the more rules are fired at this high level the lower the overall probability of the conclusion, while for the averaging method, the probability would remain 80/100 regardless of the number of rules. As Benfer points out (Benfer, et. al., 1991:58-59), care must be taken in selecting a procedure for handling uncertainty and the researcher should make sure they understand the properties of the technique. Some of the more complex procedures can require more effort to develop than the rest of the knowledge base (Schwartz, 1990). Though complicated, procedures for handling uncertainty can be crucial for making an expert system suitable for many kinds of sociological problems. TITLE EXPERT SYSTEMS Lectures Presented at the University of Missouri - Columbia, Summer Session, July, 1996 by Edward Brent Professor of Sociology Adjunct Professor, Computer Engineering & Computer Science socbrent@showme.missouri.edu http://www.missouri.edu/socbrent Begin BEGIN ES LECTURES LECTURE SCHEDULE I. What are Expert Systems and When Should They be Used? II. Representation and Reasoning Strategies III. Shells, Knowledge Acquisition, and Interface Issues IV. Developing Expert Systems V. Expert Systems in a Social Context VI. In-Class Test, Take-Home Project Due, Course Evaluations III. SHELLS, KNOWLEDGE ACQUISITION, AND INTERFACE ISSUES EXPERT SYSTEM SHELLS KNOWLEDGE ACQUISITION AND INTERFACE ISSUES Commercial Expert System Shells Knowledge Acquisition The User Interface COMMERCIAL EXPERT SYSTEM SHELLS EXPERT SYSTEM SHELLS Level 5 Object EXSYS VP-Expert KnowledgePro 1st-Class Fusion ForeThought Nexpert RuleMaster Expert System Shells Available on Campus EXPERT SYSTEM SHELLS AVAILABLE ON CAMPUS EXPERT SYSTEM SHELLS ON CAMPUS The University of Missouri at Columbia has site licenses for the following expert system shells Level 5 Object - IBM Windows, and Macintosh EXSYS - IBM DOS, Windows, and Macintosh Favorable terms are also available for the expert system hypermedia program developed by Idea Works, Inc., Forethought. KNOWLEDGE ACQUISITION KNOWLEDGE ACQUISITION The Knowledge-Acquisition Interface The Knowledge Acquisition Bottleneck Knowledge Acquisition from Experts Machine Learning and Data-Oriented Knowledge Acquisition KNOWLEDGE-ACQUISITION INTERFACE KNOWLEDGE-ACQUISITION INTERFACE The knowledge-acquisition interface controls how the expert and knowledge engineer interact with the program to incorporate knowledge into the knowledge base. It includes features to assist experts in expressing their knowledge in a form suitable for reasoning by the computer. This process of expressing knowledge in the knowledge base is called knowledge acquisition. Knowledge acquisition turns out to be quite difficult in many cases--so difficult that some authors refer to the knowledge acquisition bottleneck to indicate that it is this aspect of expert system development which often requires the most time and effort. Knowledge-Acquisition Interface Features KNOWLEDGE-ACQUISITION INTERFACE FEATURES KNOWLEDGE ACQUISITION INTERFACE FEATURES There are many interface features, some common, some not so common, that can help the human expert and knowledge expert enter and validate a knowledge base. These include EDITING FEATURES BUILT-IN EDITORS (note EXSYS's built-in editor) CAPABLE OF READING TEXT FILES RULE-ENTRY VS CASE-ENTRY--Some ES's derive rules from cases DEBUGGING FEATURES SYNTAX CHECKING (usually requires built-in editor for interactive checking, otherwise batch) TRACES--lists of rules in the order in which they fired WHY?--explain why the system is asking for a specific item HOW?--explain how a fact was determined PROBES--commands to find and edit specific rules, facts, and so on DATA RETRIEVAL--ability to retrieve and edit knowledge easily in knowledge base OVERVIEW, VISUAL DIAGRAM--diagrammatic overview of knowledge base (e.g., NEXPERT) CASE MANAGEMENT FACILITIES FOR VALIDATION--permitting a file of cases to be stored and automatically evaluated after the program is revised--can greatly speed the vaidation process. HYPERTEXT HELP ISSUES EASE OF USE OF EDITOR MANAGING LARGE KNOWLEDGE BASES CHUNKING KNOWLEDGE KNOWLEDGE ACQUISITION BOTTLENECK KNOWLEDGE ACQUISITION BOTTLENECK The knowledge acquisition process in which expert knowledge is codified into the knowledge base is time-consuming and difficult and constitutes one of the primary bottlenecks in expert systems development. Experts have a difficult time capturing their knowledge for an expert program. First attempts to incorporate the reasoning of an expert in a program are often disappointing, and several attempts are usually required before the program captures nuances of meaning and subtleties of reasoning not initially apparent to the expert. Knowledge-acquisition interfaces of expert systems shells typically have several features to assist in this acquisition process. KNOWLEDGE ACQUISITION FROM EXPERTS KNOWLEDGE ACQUISITION FROM EXPERTS SEMANTIC KNOWLEDGE--TAXONOMY OF CONCEPTS (Concepts grouped hierarchically) COMPUTER PROGRAMS WITH STRUCTURED QUERIES--Often inflexible REPEATED INTERVIEWS WITH EXPERT USE OF PROTOTYPES AND CASES TO STIMULATE THOUGHTS INPUT FORMS OBSERVATION TITLE EXPERT SYSTEMS Lectures Presented at the University of Missouri - Columbia, Summer Session, July, 1996 by Edward Brent Professor of Sociology Adjunct Professor, Computer Engineering & Computer Science socbrent@showme.missouri.edu http://www.missouri.edu/socbrent Begin BEGIN ES LECTURES LECTURE SCHEDULE I. What are Expert Systems and When Should They be Used? II. Representation and Reasoning Strategies III. Shells, Knowledge Acquisition, and Interface Issues IV. Developing Expert Systems V. Expert Systems in a Social Context VI. In-Class Test, Take-Home Project Due, Course Evaluations IV. DEVELOPING EXPERT SYSTEMS DEVELOPING EXPERT SYSTEMS The Development Team Identifying Users and Program Objectives Selecting a Platform/Shell/Language The Development Process Practical Issues in Knowledge Acquisition Validating Expert Systems Insights and Heuristics THE DEVELOPMENT TEAM THE DEVELOPMENT TEAM Most expert systems are developed by a team of people, with the number of members varying with the complexity and scope of the project. Of course, a single individual can develop a very simple system. But usually at least two people are involved. There are two essential roles that must filled by the development: knowledge engineer and substantive expert. The Knowledge Engineer The Substantive Expert THE KNOWLEDGE ENGINEER THE KNOWLEDGE ENGINEER CRITERIA FOR SELECTING THE KNOWLEDGE ENGINEER Competent Organized Patient PROBLEM KNOWLEDGE ENGINEERS Technician with little social skill Sociable with low technical skill Disorganized Unwilling to challeng expert to produce clarity Unable to listen carefully to expert Undiplomatic when discussing flaws in system or expert's knowledge Unable to quickly understand diverse substantive areas THE SUBSTANTIVE EXPERT THE SUBSTANTIVE EXPERT CRITERIA FOR SELECTING THE EXPERT Competent Available Articulate Self-Confident Open-Minded VARIETIES OF EXPERTS No expert Multiple experts Book knowledge only The knowledge engineer is also the expert PROBLEM EXPERTS The unavailable expert The reluctant expert The cynical expert The arrogant expert The rambling expert The uncommunicative expert The too-cooperative expert The would-be-knowledge-engineer expert IDENTIFYING USERS AND PROGRAM OBJECTIVES IDENTIFYING THE USERS AND PROGRAM OBJECTIVES What level of knowledge are they likely to have? How diverse are they likely to be? What levels of knowledge do you want the program to provide? What kind of interface strategy is likely to work for the users? EXAMPLES: How would an expert system need to be different for physicians, college freshmen, third graders, non-English-speaking users? SELECTING A PLATFORM/SHELL/LANGUAGE SELECTING A PLATFORM/SHELL/LANGUAGE SELECTING A PLATFORM Greater power versus wider availability (e.g., multimedia standards) SHELLS VS LANGUAGES (CANNED SHELL VS NEW PROGRAM DEVELOPMENT) Shells do much more of the work for the developer and let them focus on the knowledge. Languages offer much more flexibility and power. SELECTING AMONG SHELLS Knowledge representation and reasoning paradigm Flexibility Special requriements (real-time, delivery environment, inferface to other programs and data) User interface needs (graphics, hypertext) Features (explanation, trace, testing aids, case management, knowledge retrieval and display) Performance Requirements (hardward and software requirements) License restrictions and costs Vendor support THE DEVELOPMENT PROCESS THE DEVELOPMENT PROCESS The systems development process often used for traditional software such as management information systems often employs a process described as the "System Development Life Cycle" or "Waterfall" Model. While this model identifies a number of important tasks in the development process, many developers of expert systems have found it to be inadequate for expert systems for a number of important reasons. Instead, many expert systems are developed using a process called "Rapid Prototyping and Incremental Development." The System Development Life Cycle Rapid Prototyping and Incremental Development THE SYSTEM DEVELOPMENT LIFE CYCLE THE SYSTEM DEVELOPMENT LIFE CYCLE PROBLEM ANALYSIS Is the problem solvable? Is it feasible with this approach? cost-benefit analysis REQUIREMENTS SPECIFICATION What are the desired features and goals of the proposed system? Who are the users? What constraints must be considered? What development and delivery environments will be used? DESIGN PRELIMINARY DESIGN - overall structure, data flow diagram, perhaps language DETAILED DESIGN - details of each module IMPLEMENTATION Writing and debugging code, integrating modules, creating interfaces TESTING Comparing system to its specifications and assessing validity MAINTENANCE Corrections, modifications, enhancements Problems with the Systems Development Life Cycle Approach PROBLEMS WITH THE SYSTEMS DEVELOPMENT LIFE CYCLE APPROACH PROBLEMS WITH THE SYSTEMS DEVELOPMENT LIFE CYCLE APPROACH Problems with this approach for software in general There is no way for the customer to get the feel of the system before it is done. The system is of little or no use until the entire process has been completed. Problems with this approach for knowledge-based systems It doesn't recognize the significant effort required for knowledge acquisition The amount and nature of knowledge required is often poorly understood at the beginning of the development process and may even undergo a dramatic paradigm shift in which the entire project has to be reconceptualized RAPID PROTOTYPING AND INCREMENTAL DEVELOPMENT RAPID PROTOTYPING AND INCREMENTAL DEVELOPMENT PRACTICAL ISSUES IN KNOWLEDGE ACQUISITION PRACTICAL ISSUES IN KNOWLEDGE ACQUISITION Knowledge Elicitation Strategies The Repertory Grid - e.g., see Statistical Navigator or other decision-making programs Knowledge Documentation Strategies VALIDATING EXPERT SYSTEMS VALIDATING EXPERT SYSTEMS Expert systems are complex systems that can be judged by many different standards. For experts, the primary question is does the expert system produce valid results. Pro- grammers would judge the system by how well it meets its objectives and specifications, whether it is syntactically correct, and whether it is efficient and well-executed. In addition, users might ask whether the program is understandable, usable, Validity (Expert Standards) worthwhile. If the expert system is to be used in an organization, then we must ask how well it fits into the operations of Verification (Programming Standards) the organization and whether it will be adopted for actual use. If the expert system is a commercially available system, User Acceptance (User Standards) the question is whether people will buy it in sufficient numbers to recover development costs and produce an acceptable profit. Commercial Viability (Market Standards) These audiences have different standards and must be considered separately. Organizational Fit (Organizational Standards) What do we mean by Validating? Criteria for Assessing Validity What is Validated? Basis for Testing WHAT DO WE MEAN BY VALIDATING? MULTIPLE OVERLAPPING AUDIENCES AND STANDARDS VALIDITY (Expert Performance Standard) Does the program do what it claims? VERIFICATION (meets objectives, specifications, syntactically correct, well-executed) USER ACCEPTANCE (acceptability, usability) COMMERCIAL VIABILITY ORGANIZATIONAL FIT STANDARDS FOR VALIDITY STANDARDS FOR USER ACCEPTANCE USER ACCEPTANCE Do users find the program easy to use, worthwhile? Laboratory tests Beta tests (field tests) VALIDITY (EXPERT STANDARDS) VALIDITY (EXPERT STANDARDS) FORMATIVE AND SUMMATIVE EVALUATION CRITERIA FOR ASSESSING VALIDITY ("GOLD STANDARD") Expert who developed system Other expert Panel of recognized experts Objective standards such as pathological exams after death EXAMPLES: AI-RHEUM, HOME-SAFE-HOME WHAT IS VALIDATED? Final Conclusions Intermediate Conclusions Entire Reasoning Process Sensitivity Analysis Program Run by Experts vs Run by Actual Users BASIS FOR TESTING Hypothetical example responses Hypothetical complete cases Hypothetical complete cases selected to reflect variation Real cases selected to test varieties Representative sample of cases from a population VERIFICATION (PROGRAMMING STANDARDS) VERIFICATION (PROGRAMMING STANDARDS) STANDARDS FOR VERIFICATION COMPLIANCE WITH SPECIFICATION Knowlede representation and reasoning strategies Interfaces to other data bases and programs User interface Performance standards (speed, accuracy, etc.) Maintainability Security CODE QUALITY redundant rules conflicting rules subsumed rules circular rules unnecessary antecedent conditions dead-end rules missing rules unreachable rules VERIFICATION TOOLS AND FEATURES EXSYS's ability to test all rules in the knowledge base INSIGHTS AND HEURISTICS INSIGHTS AND HEURISTICS Modularize, Modularize, Modularize The 80:20 Rule Learn From the Interface Learn From Documentation Involve Users Early On Paradigm Shift V. EXPERT SYSTEMS IN A SOCIAL CONTEXT EXPERT SYSTEMS IN A SOCIAL CONTEXT Linking Expert Systems Ethical and Legal Issues for Expert Systems The Business of Expert Systems Deskilling vs Enabling Controversy What level of knowledge is required for expert systems to be useful? LINKING EXPERT SYSTEMS LINKING EXPERT SYSTEMS Why Link? Blackboard Systems: Linking Multiple Expert Systems Linking Expert Systems to Sources of Data Linking Expert Systems to Other Programs Integrated Expert Systems Embedded Expert Systems WHY LINK? WHY LINK? Links are connections between an expert system program and other programs or data. REASONS YOU MIGHT WANT TO LINK AN EXPERT SYSTEM TO OTHER PROGRAMS OR DATA Use data from an existing database as inputs to the expert system Perform a computational or graphical task with another program that cannot be performed with the expert system shell Use conclusions from the expert system to assign values to a database in an information system Use another program to create an interface not possible with the expert system shell TYPES OF PROGRAMS YOU MIGHT WANT TO LINIK AN EXPERT SYSTEM TO graphics programs process control programs databases spreadsheets MIS system EXAMPLES running external programs from within an expert system shell passing data out and into expert systems retrieving data from databases or spreadsheets graphics display, manipulation BLACKBOARD SYSTEMS BLACKBOARD SYSTEMS One of the biggest problems with expert systems (and computer programs in general) is they have expertise in only a narrow substantive domain. Outside that domain, programs are not helpful, and worse yet, lack the common sense to know when they are outside their domain of expertise. Thus, as expert systems develop in a discipline such as sociology, we will find isolated narrow areas of knowledge with large regions separating those systems where little or no knowledge is available. Worse yet, incompatibilities in programming languages and data structures can make it difficult for programs to communicate with one another and share knowledge. In the field of expert systems a promising strategy for addressing these issues has been developed. This strategy is based on an analogy to a blackboard. A blackboard system (Newell, 1962) implements a method of reasoning called "opportunistic reasoning." In this method, the reasoning at each point in time is contingent upon what has already been discovered. Separate expert systems reason individually on parts of a problem in which they have expertise, then periodically post their current knowledge to a shared data system (the "blackboard"). At the same time each system posts its own conclusions, it also examines what knowledge has been posted to the blackboard by other systems. A classic example of this approach was its use in the Hearsay project, a speech-understand- ing program developed at Carnegie-Mellon University (Erman, et al., 1980) and sponsored by the Defense Applied Research Projects Agency (DARPA). That system used thirteen different knowledge sources to handle different components of the speech recognition system from interpreting sound waves to recognizing syntax) Blackboard systems thus provide a mechanism for linking expert systems to provide a broader range of knowledge and advice than can be found from individual systems. In our own work we have used a blackboard system to link eight different programs, each providing advice about some aspect of research methods, into a comprehensive program --the Methodologist's ToolchestO (Brent and Thompson, 1995). Blackboard systems offer a basis for building integrated knowledge systems combining programs written by different authors. The systems are only loosely coupled, permitting different reasoning and representation strategies to be used in each component so long as they can communicate with the blackboard. Blackboard systems can help overcome the narrowness of expert systems, and offer a basis for building a more integrated system of knowledge-based systems. Feigenbaum (1992) argues blackboards and strategies for linking expert systems are one of the most important next steps in the development of computer-based knowledge systems. This, or some other integrative strategy, will be essential for developing a computational sociology in which diverse simulations and models from different researchers could be linked in broader systems. These various components could be used as interchangeable building blocks of social theory. Then models of individual social actors by one researcher could be linked to models of emergent group properties by another researcher and models of technological constraints on organizational performance by still another researcher. While promising, blackboards have limits. They presume knowledge can be separated into largely divisible, independent "chunks." In some cases this may not be true. They are likely to be seriously constrained for some time to come by differences in programming languages, shells, and operating systems. This strategy of linking diverse programs also is reminiscent of earlier efforts to unify science, which have been largely abandoned today. So we would be wise to temper our expectations for what can be accomplished with such unifying strategies. LINKING EXPERT SYSTEMS TO SOURCES OF DATA LINKING EXPERT SYSTEMS TO SOURCES OF DATA TYPES OF DATA COMMONLY REQUIRED Spreadsheets Databases Analog data EXAMPLE SYSTEMS THAT DO THIS The American Express system for extending credit Expert systems for process control that monitor and regulate a process based on analog data from instruments (e.g., plasma coating) LINKING EXPERT SYSTEMS TO OTHER PROGRAMS LINKING EXPERT SYSTEMS TO OTHER PROGRAMS TYPES OF PROGRAMS TO WHICH LINKS MAY BE REQUIRED Spreadsheets Statistical programs Multimedia interface programs EXAMPLE PROJECTS LINKING EXPERT SYSTEMS TO OTHER PROGRAMS "Making It" uses expert system to emulate behavior of intelligent simulated actors and links that to a multimedia frontend using virtual reality and digitized video INTEGRATED SYSTEMS INTEGRATED EXPERT SYSTEMS An early effort to link expert systems to other programs was the development of INTEGRATED EXPERT SYSTEMS in which the expert system was only one component in an integrated system. Other components were spreadsheets, database managers, and word processors. An example of this approach is GURU. Like other integrated applications, this approach does not seem to have taken hold with expert systems because such integrated systems typically have some components which are weaker than the competing products. Instead, people seem more inclined to purchase suites of packages each of which is good in their own area, and they are only weakly linked. Then they substitute their own preferred word processor, spreadsheet, database, and so on. EMBEDDED EXPERT SYSTEMS EMBEDDED EXPERT SYSTEMS An EMBEDDED EXPERT SYSTEM is an expert system which runs as a component of some other system. It may be entirely invisible to the user. Embeddable libraries Expert system on a chip EMBEDDABLE LIBRARIES An example of this approach is M.4 --embeddable expert systems libraries written in C EXPERT SYSTEM ON A CHIP hardware incorporating embedded expert systems e.g., electrophoresis interpreter--first expert system on a chip ETHICAL AND LEGAL ISSUES FOR EXPERT SYSTEMS ETHICAL AND LEGAL ISSUES FOR EXPERT SYSTEMS LEGAL ISSUES LIABILITY THE THEORY OF STRICT LIABILITY - manufacturer liable for defective product if in business of selling the product--generally applicable to tangible products sold to consumers at large THE THEORY OF NEGLIGENCE - plaintiff must prove negligence in provision of services THE PUBLICATION THEORY - treats expert systems like books where manufacturers and authors are usually not held liable for information provided so long as not defamatory or fraudulent ARE PROGRAMS PRODUCTS OR SERVICES? - if hired to develop software, treated as a service. When sold to the masses may treat as a product. SOFTWARE PROTECTION COPYRIGHT PROTECTION - Not necessary to register. . . copyright last sfor lifetime of the author plus 50 years. . . protects the work from being reproduced, but does not protect the ideas contained within the work--only protects the expression of those ideas. May need to copyright screens or interfaces separately. PATENT PROTECTION - protect the idea itself. . . must be reduced to practice. . lasts only 17 years. . . expensive, time-consuming process to apply for a patent. . . once granted, its details are in the public domain. TRADE SECRET PROTECTION - protects a secret. . . owner must take reasonable precautions to keep it a secret. . . nondisclosure agreeements INTERNATIONAL PROTECTION - problematic in many countries WHO OWNS THE SOFTWARE - work for hire owned by hiring company. . . work by a sub- contracting company providing services owned by contractor unless specified in the contract THE BUSINESS OF EXPERT SYSTEMS COMPETENCE LEVELS FOR EXPERT SYSTEMS Continue EXPERT SYSTEMS AND COMPETENCE IN THE POPULATION