Skip to main content
main-content

Über dieses Buch

At present one of the main obstacles to a broader application of expert systems is the lack of a theory to tell us which problem-solving methods areavailable for a given problem class. Such a theory could lead to significant progress in the following central aims of the expert system technique: - Evaluating the technical feasibility of expert system projects: This depends on whether there is a suitable problem-solving method, and if possible a corresponding tool, for the given problem class. - Simplifying knowledge acquisition and maintenance: The problem-solving methods provide direct assistance as interpretation models in knowledge acquisition. Also, they make possible the development of problem-specific expert system tools with graphical knowledge acquisition components, which can be used even by experts without programming experience. - Making use of expert systems as a knowledge medium: The structured knowledge in expert systems can be used not only for problem solving but also for knowledge communication and tutorial purposes. With such a theory in mind, this book provides a systematic introduction to expert systems. It describes the basic knowledge representations and the present situation with regard tothe identification, realization, and integration of problem-solving methods for the main problem classes of expert systems: classification (diagnostics), construction, and simulation.

Inhaltsverzeichnis

Frontmatter

Introduction

Frontmatter

1. Characterization and History of Expert Systems

Expert systems are programs for reconstructing the expertise and reasoning capabilities of qualified specialists within limited domains. The preliminary basic assumption is that experts construct their solutions from single pieces of knowledge which they select and apply in a suitable sequence. Hence expert systems require detailed information about the domain and the strategies for applying this information to problem solving. In order to construct an expert system, the knowledge must therefore be formalized, represented in the computer and manipulated according to some problem-solving method. However, since few people have both the detailed expert knowledge and programming skills, a division of labor is desirable. This could, for example, take the following form: An expert and a computer scientist agree on a common representation of the knowledge, the expert formulates his knowledge accordingly, and the computer scientist programs the appropriate problem-solving methods. By this means both can contribute their skills in the best possible way. It is perhaps even more important to create a clear interface between the specialist knowledge for the problem in hand and the general problem-solving methods. This makes an expert system much more amenable to modification than most conventional programs. This distinction between expert knowledge and the problem-solving method, possible in many domains, is a characteristic feature of the architecture of expert systems. The only difference between expert systems and knowledge-based systems is that the former derive their knowledge from experts (Fig. 1.1).

Frank Puppe

2. Programming Languages and Expert System Tools

The central problem (“bottleneck”) in the development of expert systems is finding a way of transferring a great deal of detailed knowledge to the program. The most important primary sources of knowledge are experts and textbooks. However, the knowledge in the minds of the experts is not easily accessible, because experts usually have little time or motivation to pass it on and mostly have great difficulties in doing so. In many fields of application there are no good textbooks, and even if they are available they usually require background knowledge and/or practical experience to be understood, so that textbook knowledge alone is seldom sufficient for the development of successful expert systems. The situation is made even worse by the fact that the knowledge often changes rapidly.

Frank Puppe

3. Use and Usability of Expert Systems

It is still difficult to estimate the extent to which expert systems have commercially permeated the data processing world. Feigenbaum et al. report an industrial acceptance with over 1500 expert systems in use world-wide byjthe end of 1987, with a rising trend and profit-to-cost ratios of 10 to 100 [Feigenbaum 88], whereas Coy and Bonsiepen, in a critical analysis of expert systems [Coy 89], write that at least in the FRG industry is cautious with investments, and civilian state support is the motor of the market:

“According to a report of the BMF

1

[…] on the situation of AI research, a sum of at least 300 million DM was provided for the civilian financial support of research on artificial intelligence and expert systems technology in the period from 1984 to 1989/90. This sum went into cooperative projects of industry, universities and other state research institutes. The amount of military support through the BMVg

2

, the IABG

3

and other industrial and state research and development departments is not given. Optimistic estimates give a maximum figure of 309 million DM for the market volume of this technology in the FRG from 1985 to 1988 […] not including the firms’ own contributions, which may be assumed to be of the same order of magnitude. Civilian support and the market are therefore in balance for the present, and the financial assistance is the motor of this market.” [Coy 89, p. 164].

Frank Puppe

Basic Techniques of Knowledge Representation

Frontmatter

4. Logic

The knowledge representation which has been most thoroughly investigated experimentally and is often used as a reference point for other representations is first-order predicate logic. However, since its practical use for expert systems is relatively slight, it is used here mainly as an introduction to the problems of knowledge representation systems and as a motivation for the development of other formalisms. Comprehensive introductions to predicate logic can be found, e.g., in [Bibel 87], [Charniak 85], [Genesereth 87], [Lloyd 87], [Melvin 91], [Nilsson 82].

Frank Puppe

5. Rules

A rule consists of a precondition (premise) and an action. The precondition describes a situation in which the action is to be performed. There are two types of action: Implications, with which the truth of a statement is derived (Rule (1) in Fig. 5.1) andInstructions for changing a state (Rule (2) in Fig. 5.1).

Frank Puppe

6. Objects/Frames

In simple rule systems the actual “knowledge” resides exclusively in the rules, whereas the data base is an unstructured, passive set of facts. This chapter deals with formalisms by means of which a set of facts can be better structured, economically stored and furnished with “basic knowledge” about their application. A first step in structuring is to collect together all propositions concerning a particular object in a data structure like the records in PASCAL, property lists in LISP or relations in a data base (see Fig. 6.1). The basic ideas of object-oriented (frame-based) knowledge representation are inheritance hierarchies, attached procedures and default values, which are explained briefly below.

Frank Puppe

7. Constraints

Constraints serve for the representation of relationships between variables and are particularly suitable for representing local boundary conditions which the problem solution must fulfill in any case regardless of the particular solution. For example, one can regard the wish of a teacher to have one day in the week free as a constraint in setting up the timetable of lessons. Each new constraint brings about a further restriction of the solution space. The aim of constraint systems is to find a solution which takes all constraints into consideration, e.g., setting up a timetable which fulfills all boundary conditions.

Frank Puppe

8. Probabilistic Reasoning

In classical logic it is usually assumed that a proposition is either true or false, whereas in real life the truth value of a proposition may be known only with a certain probability or not at all. Since such uncertainties are often encountered in the field of expert systems, the knowledge representation and especially the problem-solving strategy must be extended accordingly. The two basic approaches are probabilistic reasoning and non-monotonic reasoning, which is discussed in the next chapter. The basis of probabilistic reasoning [Genesereth 87] is the attachment of a probability to each proposition to express the uncertainty. The uncertainties may be derived from representative statistics or estimated by experts.1

Frank Puppe

9. Non-Monotonic Reasoning

A deduction in classical logic is valid for all time, but in non-monotonic reasoning new information may mean that conclusions may have to be withdrawn (See Fig. 9.1).

Frank Puppe

10. Temporal Reasoning

The representation of time-dependent information has been practically neglected so far in expert systems, because the knowledge representation and the derivation strategies can become considerably more complicated. On the other hand there are many fields of application where temporal information is important. In diagnostics, for example, the change of a symptom with time often conveys more than the actual value, and in planning temporal boundary conditions must be fulfilled. At present the most promising approach to temporal reasoning in expert systems is to limit the representation to the most important temporal aspects of the domain.

Frank Puppe

Problem Classes and Problem-Solving Methods

Frontmatter

11. Previous Approaches to Problem Classification

Despite the great theoretical and practical importance which must be attached to a division of application domains into problem classes, this subject has been rather neglected in the past. In many introductory books, such as [Jackson 86]

1

problem classes and problem-specific methods of solution are not treated. Even in the latest volume of the “Handbook of Artificial Intelligence” (1989), only basic techniques are described in the chapter on expert systems, and on the subject of problem classes it is stated:

“We lack a robust taxonomy of problem types (among the most complete so far is Chandrasekaran 1986)

2

so the individual examples still provide a better characterization of the types of problem than general descriptions.” [Buchanan 89, p. 183f].

Frank Puppe

12. Principles of Problem-Solving Methods

In this chapter we give a survey of the problem-solving methods described in detail in the following chapters and their basic principles. The search for problem-specific problem-solving methods and their operationalization in shells which experts can use independently corresponds to the approach of McDermott (Sect. 11.6 and 11.7). Compared to the few “data points” of McDermott, however, considerably more problem-solving methods will be described.

Frank Puppe

Classification

Frontmatter

13. Survey of the Problem-Solving Type Classification

The term classification (diagnostics) is given to the solution procedure for problems with the following properties: 1.The domain consists of two finite, disjunctive sets-one containing observations and the other problem solutions-and of typically uncertain, complex knowledge about the relationships between these two sets.2.A problem is defined by a given subset of observations, which may be incomplete.3.The result of the classification is the selection of one or more solutions to the problem.4.If the quality of the solution can be improved by considering additional observations, one of the tasks of classification is to determine which additional observations are to be requested.

Frank Puppe

14. Simple Classification

By simple classification we mean the evaluation of certain knowledge and certain data. The two main types are decision trees and decision tables.

Frank Puppe

15. Heuristic Classification

Heuristic classification is suitable for classification problems in which it is known from experience which observations— or combinations of observations — indicate intermediate or final solutions, and with what degree of certainty. Thus the basic object types are observations, solutions and rules of the form “observation indicates solution” (O → S, with certainty x). That solution is selected which has the highest total score on the basis of the observations (Fig. 15.1).

Frank Puppe

16. Heuristic Classification: Additional Mechanisms

In the previous chapter we discussed how to deal with the central requirements of heuristic classification, namely the treatment of uncertain knowledge, step-wise abstraction and dialog control. In this chapter the mechanisms for the remaining requirements of Sect. 13.3 are described: the treatment of uncertain, subjective, potentially false, incomplete and parametrizable knowledge, of multiple solutions and combined recommendations for several solutions. The basic structure developed in Chap. 15 will be assumed.

Frank Puppe

17. Set-Covering Classification

Set-covering classification is suitable for classification problems in which the solutions (causes) evoke particular symptoms (effects) — possibly via intermediate states — with a relatively high reliability. In the simplest form the knowledge representation consists of observations, solutions and rules of the form: solution causes observation (S → O). The probability of a given solution or group of solutions is greater, the more observations are explained, i.e., covered, according to its rules and the smaller the number of non-observed features which can be derived from it. The basic structure is illustrated in When set-covering classification is used for fault-finding it is called classification with fault models. Two examples of fault models from the technical and medical fields, respectively, are shown in Figs. 17.2 and 17.3. Set-covering is not only suitable for fault-finding, however, but for all domains in which the solutions may be described by characteristic sets of problem features.

Frank Puppe

18. Functional Classification

Functional classification is suitable for fault-finding in systems whose normal and defective structures can be described by materials and components with states, and whose normal and abnormal behavior can be derived from the description of the behavior of the components. A functional model describes how the input materials are converted into the output materials in a system. Examples are the gasoline engine, which converts air and gasoline into motive power and exhaust gases (Fig. 18.1), the blood circulation for supplying oxygen to the body (Fig. 18.2) and a circuit for addition and multiplication, which has numbers as input and output (Fig. 18.3).

Frank Puppe

19. Statistical Classification

Statistical classification is suitable for classification problems for which a large, representative collection of successfully solved cases exists. The basic idea is similar to that of heuristic classification, except that the relationships between observations and solutions are not estimated by experts but extracted from case data bases with statistical methods. This has the great advantage that the knowledge is less subjective. The limitations of statistical classification result from the fact that a number of conditions must be fulfilled before it can be used. Actually it is possible to use the same approach even if the conditions are not fulfilled, but we would then be dealing with a heuristic method, since the objectivity is lost.

Frank Puppe

20. Case-Comparing Classification

Case-comparing classification is suitable for classification problems for which there is a large collection of genuine or imagined cases with the correct solutions and additional knowledge, above all for the relative weighting of observations. A new case is solved by first finding the case in the data base whose features (observations) best agree with those of the new case. If the similarity is sufficient, the solution is used for the new case (see Fig. 20.1). In order to evaluate how well the cases agree a measure of similarity is required. For a given measure of similarity the quality of the solutions improves with each new case in the data base. Since this simplifies the knowledge acquisition, case-comparing classification is theoretically very attractive. However, hardly any practical experience has been gained so far, because the method has not been used for very long in expert systems, and suitable case collections are rare, despite the fact that they have to fulfill less stringent requirements than for statistical classification.

Frank Puppe

Construction

Frontmatter

21. Review of the Problem-Solving Type Construction

In construction problems the solution cannot be selected as in classification, but must be put together from solution elements. In a wide sense of the word every problem may be regarded as a construction problem, classification being a simple special case. It is therefore not realistic to expect a more or less complete division into problem-solving classes with strong problem-solving methods. As for classification we will attempt a systematization according to three classification principles, although the knowledge type plays a less dominant role in this case: 1.Problem type: configuration, assignment, planning.2.Knowledge type: heuristic, case-comparing, model-based.3.Problem-solving method: (search strategies, skeletal construction, propose-and-revise, least commitment.

Frank Puppe

22. Skeletal Construction

Skeletal construction is suitable for simple planning and configuration problems in which the search space may be represented in a hierarchical, non-recursive AND/OR graph, and selection knowledge for the hierarchical expansion of the graph is available. The “AND” nodes in the graph are called “skeletal plans” and the “OR” nodes “construction steps” (Fig. 22.1).

Frank Puppe

23. Propose and Revise

The propose-and-revise strategy is suitable for deriving values for a set of parameters. It makes possible an efficient, sequential determination of the parameter values, even when the search space is locally or globally under- or over-determined or when cyclic relationships exist. Its flexibility results from the fact that the parameter values first proposed can be corrected at any time with “revision knowledge” if this turns out to be necessary. It is suitable for cyclic parameter relationships because loops can be broken by taking a cyclic parameter as a starting parameter and estimating its value. If a contradiction occurs in the subsequent calculations on account of the cyclic relations, the parameter value is raised or lowered (Fig. 23.1).

Frank Puppe

24. Propose and Exchange

The propose-and-exchange strategy is suitable for the heuristic solution of complex assignment problems for which exact optimizing algorithms are not applicable. The basic idea is that of the propose-and-revise strategy (Chap. 23). The task of assignment is not to determine object properties as in configuration (e.g., the thickness of a cable in elevator configuration) but to assign given sets of objects to one another according to certain boundary conditions (see Fig. 24.1).

Frank Puppe

25. Least-Commitment Strategy

Like the propose-and-revise strategy, the least-commitment strategy is suitable for deriving the values of a set of parameters, but it avoids a rapid, temporary, heuristic determination of parameter values. In particular, there are no loops to be broken as is Fig. 23.1. The knowledge about the relationships between the parameters is represented in the form of undirected constraints instead of directed rules. The least-commitment strategy is therefore useful only when reasonably efficient constraint programming is possible. The most important constraint propagating techniques [see Chap. 7] are: Propagation of fixed values. It is generally assumed that (n − 1) of the n variables of a constraint are known.Propagation of sets of values (example see Sect. 25.1). This is useful above all for small, symbolic parameter value ranges.Propagation with case distinction. Case distinctions are meaningful only for limited, symbolic parameter value ranges.Symbolic Propagation. This requires powerful algebraic techniques for transforming symbolic expressions and is therefore used only rarely and in simplified form in expert systems.

Frank Puppe

26. Model-Based Planning

Heuristic planning is restricted to the critical aspects of the planning process and requires empirical knowledge about which aspects are the critical ones and how to represent them, but no such reductions are performed in model-based planning. Instead, the objects of the field of application are described with sufficient accuracy, so that the operators may be completely characterized by their effects on the objects. A feature of mo del-based planning is the inherent possibility of a simulation of the finished plan by showing how the execution of the operators transforms the starting situation step by step into the target situation. This possibility is lacking in heuristic planning, because the effects of the operators on the situations are usually not known with sufficient detail.

Frank Puppe

27. Case-Comparing Construction

In case-comparing construction a case library is searched in an attempt to find a case which is as similar as possible to the task at hand, so that its solution can be adopted. Unlike the problem type classification, the solutions of two different problems seldom agree in construction, so that the old case must be modified according to the special requirements of the new one. For this purpose an additional knowledge representation is required. Case-comparing construction should not therefore be regarded as an independent problem-solving method, but rather as an extension of the construction method whose knowledge representation it uses. Therefore in this chapter only the special case-comparing features are described. Case-comparing construction has two phases: the selection of the old case and the adoption or modification of its solution.

Frank Puppe

28. Partial Integration of Construction Methods

The construction methods discussed above are each based on a different central idea: Skeletal construction: top-down refinement along an AND/OR hierarchy.Propose and revise, propose and exchange: direct, heuristic determination of parameter values or assignments with the possibility of knowledge-based correction, respectively.Least commitment: the use of constraint generation to avoid premature fixing of parameter values, and subsequent evaluation by constraint propagation,Case-comparing construction: adoption of as many construction decisions as possible from a similar case.Model-based construction: construction on the basis of a model which is manipulated explicitly with operators.

Frank Puppe

Simulation

Frontmatter

29. Review of the Problem-Solving Type Simulation

In classification and construction, solutions are selected or assembled, respectively. Simulation, however, serves “only” for predicting the effects of certain assumptions on the system. A prerequisite is a model of the system containing parameters and relationships between them. The simulation consists in deriving the values of certain (output) parameters from given values of other (input) parameters.

Frank Puppe

30. Single-Phase Simulation

Although single-phase simulation is relatively simple on account of the lack of an explicit temporal representation, it is sufficient for many applications, since temporal relationships are often implicit. In Fig. 30.1, for example, it is obvious without an explicit time representation that the arrows on the materials represent a strict before/after relationship.

Frank Puppe

31. Numerical Multiple-Phase Simulation

In multiple-phase simulation the components may change their behavior during the simulation, the changes being governed by the input data or by a random number generator representing failure frequency. The different behaviors are represented by different simulation phases. In numerical simulation the phase transitions and the behavior of the components can be calculated exactly, whereas qualitative simulation does not use exact data. Numerical multi-phase simulation is a well-established, widely used aid in science and technology. We describe here only a simple basic structure, which must be extended according to the complexity of the domain.

Frank Puppe

32. Qualitative Multiple-Phase Simulation

Qualitative multiple-phase simulation is a simplified form of numerical multiple-phase simulation. Unlike the latter it requires no global clock and cannot supply exact utilization statistics, but gives a state transition diagram as its result. A state is characterized by a set of simultaneous parameter values. The value range of the parameters is qualitative and is chosen so that each value has a special significance for the simulation, which is why they are often called “landmark values”. Any change of a value leads to a new state. Since value changes are no longer given by the advancing of a clock and numerical formulas, another concept must be introduced. It is based on the fact that in addition to the qualitative value of each parameter the trend, with the value range “increasing”, “constant” or “decreasing”, is also represented. A change of state occurs by replacing the value of a parameter with the trend “increasing” or “decreasing” by the next highest or lowest value, respectively. However, since there is no clock the time required for a change of state cannot be determined. On the other hand, state transition diagrams are relatively compact, and cyclic sequences of states can be recognized easily, which would be much more difficult with numerical multiple-phase simulation. Figure 32.1 shows the result of a qualitative multiple-phase simulation for a thermostat-controlled central heating system with a cyclic sequence of states (episodes 1 to 4).

Frank Puppe

Integration of Problem-Solving Methods

Frontmatter

33. Basic Ideas for the Integration of Problem-Solving Methods

The dilemma of expert system tools is to find the right compromise between time-saving in the development of an expert system and the associated restriction of its applicability. The history of expert systems shows a trend to specialization, which constitutes an essential difference with respect to universal programming environments. On the other hand, with specialized tools it is usually possible to solve only selected parts of the whole problem field in an optimum way, while other problem-solving methods and tools are required for other parts. The price for the simplicity resulting from the use of specialized tools is usually the difficulty of coupling different partial solutions. There is therefore considerable pressure from users of expert system for the development of support for the coupling process.

Frank Puppe

34. Integration of Classification Methods

An integration of classification methods promises good synergetic effects, since classification is the best-understood problem-solving method, and the knowledge forms of the different methods (simple, heuristic, statistical, case-comparing, set-covering and functional classification, see Chaps. 14–20), although they overlap somewhat, are not mutually convertible: Statistical and heuristic knowledge resemble one another in the representation of probabilistic assessments. They differ, however, firstly in the variety of knowledge representation they provide, since heuristic classification systems offer mechanisms such as multiple hierarchies, rules with symptom combinations and exceptions, etc., which have no equivalents in statistical knowledge representation systems, and secondly in the precision of the probabilistic assessments, which are calculated from data bases or estimated by experts, respectively. The importance of the difference between calculated and estimated symptom/diagnosis probabilities was shown by experiments with a successful program by de Dombal, based on Bayes’ Theorem: the success rate of the program dropped drastically when the statistical probabilities were replaced by experts’ estimates [de Dombal 72].Heuristic and set-covering classification are both based on empirical knowledge about faulty behavior of the system being investigated. They differ, however, in the direction of derivation (symptom → diagnosis and diagnosis → symptom, respectively) and also in the fact that the experts ’ estimates play an important role in heuristic systems, while set-covering systems rather check whether diagnoses are consistent with the observed symptoms.Set-covering and functional classification resemble one another in the way they match observed and predicted symptoms. They differ, however, in the conceptual function of symptoms and diagnoses. In set-covering classification the diagnoses and symptoms, represented as states, are fixed concepts in their own right, as in all other types of knowledge, whereas in functional classification they are derived from the functional model: diagnoses are components with an altered input/output behavior, and symptoms are abnormal parameter values of the materials.Case-comparing classification differs basically from all other knowledge types, since it is based not so much on an abstraction of case knowledge but rather on a direct comparison of a new case with those stored in a data base.Simple classification can be regarded as a compiled form of the other problem-solving methods, in which the uncertainties or causal relationships are no longer explicitly represented.

Frank Puppe

35. Aspects of the Overall Integration

Starting from the integration of the classification methods discussed in the last chapter, we consider below the additional integration of the construction and simulation methods indicated in namely skeletal construction, the propose-and-revise strategy for configuration, a simple form of the least-commitment strategy, case-comparing construction and single-phase simulation. The common feature of these methods is that they all fit in with the simple basic conception described in Sect. 12.2, in which all objects of the domain are named explicitly. In our opinion the integration of more powerful construction is problematical on account of the increasing complexity, so that the coupling of independent shells may be preferable.

Frank Puppe

Backmatter

Weitere Informationen