Knowledge representation

Knowledge representation

67.1 Purpose

This chapter describes typical expert system applications and briefly describes knowledge representation techniques.

67.2 Strengths, weaknesses, and limitations

The strengths and weaknesses associated with each knowledge representation technique will be discussed in context.

67.3 Inputs and related ideas

Chapter 6 discusses basic object-oriented principles. Chapter 7 discusses expert systems. Chapter 34 discusses expert system problem solving analysis techniques. Chapter 43 discusses data structures.

67.4 Concepts

This chapter discusses typical expert system applications and briefly describes knowledge representation techniques.

67.4.1 Types of expert systems

Interpretation systems are used primarily to explain data by providing appropriate symbolic meanings and describing the situation and/or state that accounts for the data. Applications include surveillance, image analysis, speech understanding, chemical structure analysis, and signal interpretation. For example, PROSPECTOR is a geological expert system, and HEARSAY II is concerned with understanding speech.

Prediction systems are used to infer likely consequences from a given situation. Applications include weather forecasting, demographic predictions, traffic predictions, crop estimates, and military forecasting. For example, SPERIL was developed at Purdue University to analyze structures for possible earthquake damage.

Diagnosis systems are used to relate observed behavioral irregularities with underlying causes. These systems combine knowledge of system design with knowledge of potential design, implementation, or component flaws to diagnose malfunctions or recommend further investigation. Applications are found in medicine and in electronic, mechanical, and software design. For example, DART was developed jointly by Stanford University and IBM to determine computer faults, and MYCIN was developed at Stanford University to diagnosis blood infections.

Design systems construct descriptions of objects in various relationships with each other and verify that the resulting configurations conform to known constraints. These systems often incorporate goal-seeking behavior and attempt to minimize an objective function and accomplish the goal. Applications include circuit design, building design, and budgeting. For example, SYN was developed at MIT to perform electronic circuit analysis.

Monitoring systems compare observations of system behavior to features that seem crucial to successful outcomes. Applications include fiscal management, regulatory enforcement, disease monitoring, and air traffic control. For example, IMS was developed by Carnegie Mellon University to perform automated factory monitoring and CALLISTO was developed by Digital Equipment Corporation to perform project management activities.

Planning systems employ models of agent behavior to infer the results and outcomes of the agent’s activities. Applications include automated programming, robotics, routing, data communication, and military planning. For example, PECOS was developed at Stanford to model oil exploration and ISIS-II was developed by Carnegie Mellon University for job shop scheduling.

Debugging systems are used to prescribe remedies for malfunctions and/or failures. Applications include computer programming, software development, text editing, question and answer systems, natural language processing, and computer-aided instruction.

Repair systems develop and execute plans to administer a remedy for some diagnosed problem. Applications include communications networks and computer maintenance. Repair systems are relatively new, and successful implementations are just beginning to emerge.

Instruction systems are used to diagnose and debug system behaviors and to provide the decision-maker with trouble-shooting support. Applications include student instruction and animal behavior explanation systems. For example, GUIDON was developed by Stanford University to provide medical instruction and WUMPUS was developed by MIT to provide athletic coaching instruction.

A control system adaptively governs the overall behavior of a system, repeatedly interpreting the current situation, predicting the future, diagnosing the causes of anticipated problems and/or symptoms, and formulating a plan to monitor execution to ensure success. Air traffic control, business management, battle management, and mission control are possible application areas.

67.4.2 Knowledge representation techniques

The purpose of knowledge representation is to organize the required information into a form that the expert system can readily access for decision making, planning, recognizing objects and situations, analyzing scenes, drawing conclusions, and other cognitive functions.

67.4.2.1 First-order predicate logic

First-order predicate logic is commonly used in mathematics to prove theorems. The idea is to use qualifiers and logical operators to describe objects, properties, situations, and relationships. The process is natural, precise, flexible, and modular, providing simplicity of notation and well-understood formal semantics. On the other hand, this technique lacks organizational principles, has weak manipulation procedures, and does not represent procedural or heuristic knowledge well.

67.4.2.2 Frames and slots

A frame is a complex data structure representing a stereotyped situation, such as an object, an activity, or a person. Slots are frame-like structures for representing stereotyped sequences of events or values. For example, in a frame that describes a bank account, the slots can be used to represent the account number, the account type, and the account balance. Generally, a frame is composed of a concept, one or more slots, one or more values, and one or more attached procedures (Figure 67.1).

Figure 67.2 shows a set of frames that represent information about bank accounts. A bank representative opens the account file for a customer by soliciting, entering, and verifying all the required information. The associated expert system then automatically triggers an attached procedure that asks the representative to select a transaction type (for example, add a new customer, update customer information, delete a customer, and so on). The expert system then responds by triggering the appropriate procedure.

Frame and slots were developed at about the same time object-oriented techniques (Chapter 6) were developed. A frame is similar to an object. A slot holds properties or attributes, a value is an actual instance of a particular property, and an attached procedure is similar to a method.

Using frames and slots facilitates certain predetermined information processing activities (such as add, delete, or update an account) and organizes the knowledge for easy retrieval, reference, and maintenance. Not all real-world situations can be resolved by predetermined logic, however, and new situations (e.g., adding a new feature such as a debit card) are not easily accommodated without major changes to the frames and slots structure.

Figure 67.1  Frames and slots.

Figure 67.2  A set of frames that represent information about bank accounts.

67.4.2.3 Property lists

The property lists approach uses objects and lists of their properties (or attributes) to describe the state of the world. This method is borrowed from the object-oriented approach (Chapter 6). All appropriate properties for an object are grouped into a list, and lists are easily structured in LISP, a popular expert system programming language. However, property lists are not very effective for inference-oriented operations (Chapter 34).

67.4.2.4 Semantic nets

The semantic net technique describes the state of the world through a collection of nodes that represent objects, object properties, concepts, events, and arcs of links (Figure 67.3); see Chapter 43 for a discussion of the graph data structure. For example, Figure 67.4 shows the bank accounts from Section 67.4.2.2 as a semantic net.

Figure 67.3  A semantic net.

Figure 67.4  A semantic net of bank account information.

Like an object-oriented class structure, the objects at the bottom of the top-down hierarchy inherit properties from higher-levels but also possess unique properties. For example, an individual checking account inherits such properties as an account number and an account type, but such properties as overdraft protection, minimum balance, and linkages to other accounts can change from account to account.

With a semantic net, important associations and relationships can be described explicitly, and the inheritance hierarchy is easy to understand and revise. Consequently, it is easier to add new situations to a semantic net than to a set of slots and frames. Also, the relevant facts can be found within the hierarchy, so it is not necessary to search through a large database to find specific information. Establishing an inheritance hierarchy is a difficult task, however, and determining the unique (non-inherited) properties for each low-level node calls for (subjective and/or objective) judgment.

67.4.2.5 Direct representation

Direct representation (or analogical representation) is based on analogy. Using direct representation, certain properties of a new situation can be described by reference to a known situation, and the known situation’s recommended course of action can be borrowed by an expert system faced with a new but similar situation. For example, to a weather forecasting expert system, the atmospheric conditions (except for the air temperature) that produce a rainstorm and a snowstorm are similar, so once a rainstorm is fully described, many of the parameters associated with a snowstorm are already known.

Direct representation facilitates searching because the important constraints are already known. Also, the known situation provides a base of established information that might prove relevant to the new situation. Direct representation is not suitable for all expert system tasks, however. For example, it is inappropriate when the problem calls for generalizing several specific cases into a generic meta-problem.

67.4.2.6 Procedure/subroutine

In the procedure/subroutine approach, knowledge about the world is contained in procedures, small programs that know how to do specific things (such as proceed in a well-defined situation). This technique is particularly well suited to tasks that require searching a problem domain. In computer program design, this technique views each intelligent routine as an agent that works independently to accomplish a specific task and then passes the results back to the main program (which resolves the meta-problem).

The procedure/subroutine approach is good for representing heuristic knowledge, modeling complex meta-problems, and performing extended logical inferences and reasoning. Procedures and subroutines are difficult to verify or change, however, and the information needed to control the subroutines can limit or even exclude significant alternatives or information.

67.4.2.7 Procedural/production system

In this technique, knowledge is represented by a collection of loosely coupled procedures, which may be organized into sets. For example, imagine a planning or brainstorming session in which numerous participants (multiple independent knowledge sources) nominate ideas that are recorded on a blackboard. Subsequently, the elements of a procedural/production system analyze the contents of the blackboard, locate similarities, distinguish differences, and merge similar ideas to form aggregate categories. Note that the control mechanism is part of an expert system.

Using this technique, information can be easily added, removed, and updated, and it is relatively easy to keep track of changes. Additionally, the procedural/production system technique is consistent with compiler design. Because of the complexity of the logic, program execution is inefficient, however, and the process is constrained by the predetermined control flow imposed by the program.

67.5 Key terms

Control system —

A type of expert system that adaptively governs the overall behavior of a system, repeatedly interpreting the current situation, predicting the future, diagnosing the causes of anticipated problems and/or symptoms, and formulating a plan to monitor execution to ensure success.

Debugging system —

A type of expert system used to prescribe remedies for malfunctions and/or failures.

Design system —

A type of expert system that constructs descriptions of objects in various relationships and verifies that the resulting configurations conform to known constraints.

Diagnosis system —

A type of expert system used to relate observed behavioral irregularities with underlying causes.

Direct representation (analogical representation) —

A technique that allows an expert system to analyze the properties of a new situation and use the course of action for an old situation to deal with it.

Expert system (knowledge-based system) —

A computer program that emulates the thought process of a human expert.

First-order predicate logic —

The type of logic used in mathematics to prove theorems.

Frame —

A complex data structure composed of a concept, one or more slots, one or more values, and one or more attached procedures; a frame represents a stereotyped situation.

Goal —

An objective.

Heuristics —

General rules derived from experience, common sense, inferences, and intelligent trial and error.

Inference —

The act or process of deriving logical conclusions from premises known or assumed to be true.

Instruction system —

A type of expert system used to diagnose and debug system behaviors and to provide the decision-maker with trouble-shooting support.

Interpretation system —

A type of expert system used to explain data by providing appropriate symbolic meanings and describing the situation and/or state that accounts for the data.

Knowledge —

The sum or range of what has been perceived, discovered, or learned; specific information about something.

Language parser —

A routine that executes correctly interpreted commands to accomplish the tasks determined by the program.

Lexical analyzer —

A component of a compiler that deals with the interpretation and understanding of the commands and related syntax.

Monitoring system —

A type of expert system that compares observations of system behavior to features that seem crucial to successful outcomes.

Prediction system —

A type of expert system used to infer likely consequences from a given situation.

Procedural/production system —

A technique that analyzes information from multiple independent knowledge sources, identifies similarities, distinguishes differences, and merges similar ideas and concepts to form aggregate categories.

Procedure/subroutine approach —

An approach to knowledge representation in which knowledge about the world is contained in procedures, small programs that know how to do specific things.

Property lists approach —

An approach to knowledge representation that uses objects and lists of their properties (or attributes) to describe the state of the world.

Reasoning —

The act of using inference to lead to a conclusion based on existing knowledge and/or data.

Repair system —

A type of expert system used to develop and execute plans to administer a remedy for some diagnosed problem.

Rule —

A formal specification or description of a unit of knowledge.

Semantic net technique —

An approach to knowledge representation that describes the state of the world as a collection of nodes that represent objects, object properties, concepts, events, and arcs of links in a graph.

Slot —

A frame-like structure for representing stereotyped sequences of events.

Stereotype —

A description that embodies a set image or type; a template.

67.6 Software

Not applicable. However, the chapter did reference LISP, a popular expert system programming language.

67.7 References

1.  Awad, E. M., Building Expert Systems: Principles, Procedures, and Applications, West, St. Paul, MN, 1996.

2.  Durkin, J. and Durkin, J., Expert Systems: Design and Development, Macmillan, New York, 1994.

3.  Giarratano, J. C. and Riley, G. D., Expert Systems: Principles and Programming, 2nd ed., PWS, Boston, MA, 1994.

4.  Harmon, P. and King, D., Expert Systems: Artificial Intelligence in Business, John Wiley & Sons Inc., New York, 1985.

5.  Hayes-Roth, F., Waterman, D., and Lenat, D., Building Expert Systems, Addison-Wesley, Reading, MA, 1983.

6.  Holsapple, C. W. and Whinston, A. B., Business Expert Systems, Richard D. Irwin, Homewood, IL, 1987.

7.  Silverman, B. G., Expert Systems for Business, Addison-Wesley, Reading, MA, 1991.

8.  Waterman, D., A Guide to Expert Systems, Addison-Wesley, Reading, MA, 1986.

9.  Zahedi, F., Intelligent Systems for Business: Expert Systems with Neural Networks, Wadsworth, Belmont, CA, 1993.