EXPERT SYSTEMS Most expert systems use the method of HEURISTIC ASSOCIATION. The general ARCHITECTURE of expert systems looks something like this: --------------------- | | | Inference Engine | | (Control) | | | --------------------- / \ / \ / \ / \ / \ / \ -------------------- ------------------ | | | | | Knowledge Base |------------| Database | | (Heuristic | | (General Data, | | Associations) | | Static Facts) | | | | | -------------------- ------------------ The CONTENT of associations is specific to the TASK being performed, e.g., the associations in a medical diagnostic expert system would map symptons into diseaes. The associations are usually represented in the LANGUAGE of rules, e.g, IF ... THEN ... Expert systems are often called "rule-based systems", because they are built on a production system architecture (see below) and they use rules to represent knowledge. (But we'll see non-rule-based expert systems too.) The control of processing can be Forward Chaining (from antecedents to consequents), or Backward Chaining (from consequents to antecedents) %---------------------------------------------------------------------------- Examples: - Finding molecular structure: DENDRAL - Locating oil and mineral sites: PROPECTOR - Medical diagnosis: MYCIN, INTERNIST/CADUCEUS - Tax consultant - Computer system component selection (R1/XCON) - Analyzing pulmonary problems (PUFF) - Optimal autoclave layout (CLAVIER) - ... Expert system tasks and problem categories (adapted from Waterman 1986): - INTERPRETATION (UNDERSTANDING): Forming high level conclusions or descriptions from collections of raw data. - PREDICTION: Projecting probable consequences of given situations. - DIAGNOSIS: Determining the cause of malfunctions in complex situations based on observable symptoms. - DESIGN: Determining a configuration of system componenents that meets certain performance goals while satisfying a set of constraints. - PLANNING: Devising a sequence of actions that will achieve a set of goals given certain starting conditions. - MONITORING: Comparing the observed behavior of a system to its expected behavior. - DEBUGGING and REPAIR: Prescribing and implementing remedies for malfunctions. - INSTRUCTION: Detecting and correcting deficiencies in students' understanding of a subject domain. - CONTROL: Governing the behavior of a complex environment. %---------------------------------------------------------------------------- PRODUCTION SYSTEMS (Post, 1943: computational model; Newell and Simon 1972) A production system is a set of test-action or situation-action pairs, also known as production rules or if-then rules (hence the name "rule-based system"). A production system is Turing equivalent; one can built a universal Turing machine with one, and hence do everything computable. Two types of justifications for production systems: 1. Psychological modelling 2. Knowledge engineering A production system has 3 parts: 1. A set of production rules ("rule base", "knowledge base", "production memory"). 2. A data base that can be examined and written ("data base", "world model", "context", "STM (short term memory)", "working memory"). The short term memory sometimes has a size limit (to model human like memory which has a size of about 5 +/- 2 items). 3. A mechanism to evaluate rules and select an action to perform ("interpreter", "control mechanism"). PRODUCTION WORKING Algorithm: MEMORY MEMORY WHILE match(tk,fi) p1: (t1 --> a1) f1 for some test tk and some fact fi p2: (t2 --> a2) f2 DO: ... ... 1. Find all matching p's (the pk: (tk --> ak) fi CONFLICT SET) ... \-----MATCH--/... 2. Decide which one to "fire" ... ... (CONFLICT RESOLUTION) pn: (tn --> an) fm 3. Execute its action (add or delete a fact in memory) Ideal production system: 1. All tests are evaluated simultaneously w.r.t. current data base. 2. There is a mechanism to resolve ties. 3. Right hand side actions are simple: they can only add or delete data base elements. They can't include procedures to fire other rules. Productions can perform the following actions: 1. Write a new item into short term memory at the front, dislodging the last item from the back. 2. Note items in short term memory by moving them to the front. 3. Mark an item in short term memory, to avoid it being matched again and again to the same production rules. 4. Send a message requesting information, or receive a message and place the information at the front of short term memory. Production systems that do not model short term memory explicitly (i.e., don't maintain a queue for short term memory) basically perform the following actions: 1. Place an item into short term memory. 2. Look for (or match) an item in short term memory. 4. Productions "communicate" only via the data base. Real production systems: 1. In each cycle, tests are evaluated sequentially. 2. Actions activate or build other production rules (so rules communicate outside the data base). Characteristics necessary for successful application of this technique: 1. Problem should lend itself to a modular solution. 2. Solution should not be hierarchical (because all productions are "equal"). 3. Solution should be based more on declarative than procedural knowledge. (These are not hard and fast rules because, since production systems are Turing equivalent, they can be used for any computational problem. However, the presence of these characteristics makes them a more "natural" choice.) Advantages of production systems: 1. Psychological plausibility. 2. Homogeneous knowledge representation (ideally). All knowledge is represented using the same kind of rules in the same kind of format. 3. Modular (ideally). In theory, each rule is independent. 4. Allows incremental growth (so good for learning). You can (ideally) add a production without worrying about what else the system knows because of modularity. (You can even semi-automate the learnign process, e.g., TEIRESIAS helps an expert add and revise rules for use by MYCIN.) 5. Allows well-defined and almost unrestricted communication between pieces of knowledge. 6. Natural way to represent many kinds of knowledge. Disadvantages of production systems: 1. Inefficient. 2. Opaqueness, unexpected interactions. Very hard to figure out the effects of adding a rule; very hard to figure out what depends on what and how. 3. Difficult to design. 4. Difficult to debug. 5. Is knowledge really rule-based? Major issues: Theoretical: How to represent knowledge in a rule based manner. Engineering: How to get experts to voice their internal rules. Design: Control: how to select which production to fire. Methods for selecting which production to fire (control mechanism): 1. Serial evaluation -- first matched. This is equivalent to parallel evaluation with a static ranking on rules. 2. Production with most specific (stringent) test is allowed to fire. 3. Most recently used production is allowed to fire. 4. Production most useful in the past is allowed to fire. 5. Dynamic ranking by some external process (not a "pure" production system). 6. Other methods. %----------------------------------------------------------------------------