Production Systems

'Production systems' is one of the oldest techniques of knowledge representation. A production system includes a knowledge base, represented by production rules, a working memory to hold the matching patterns of data that causes the rules to fire and an interpreter, also called the inference engine, that decides which rule to fire, when more than one of them are concurrently firable. On firing of a rule, either its new consequences are added to the working memory or old and unnecessary consequences of previously fired rules are dropped out from the working memory. The addition to and deletion from working memory depends on the consequent (then) part of the fired rule. Addition of new elements to the working memory is required to maintain firing of the subsequent rules. The deletion of data elements from the working memory, on the other hand, prevents a rule from firing with the same set of data. This chapter provides a detailed account of production systems, its architecture and relevance to state-space formulation for problem solving.

3.1 Introduction

Knowledge in an Expert System can be represented in various ways. Some of the well- known techniques for representation of knowledge include

Production Systems, Logical Calculus and Structured Models. This chapter is devoted to the Production System-based approach of knowledge representation. Logical Calculus-based methods for knowledge representation are covered in chapter 5, 6 and 7 while the structured models for reasoning with knowledge are presented in chapter 8. The reasoning methodologies presented in chapter 3, 5 and 6 are called monotonic [8] as the conclusions arrived at in any stage of reasoning do not contradict their predecessor premises derived at earlier. However, reasoning people often apply common sense, which in many circumstances results in conclusions that contradict the current or long chained premises. Such a type of reasoning is generally called non-monotonic [8]. A detailed account of the non-monotonic logics will be covered later in chapter 7. The reasoning methodologies covered in chapter 38 do not presume any temporal and spatial variations of their problem states. The issues of spatio-temporal models for reasoning will be taken up later in chapter 11.

This chapter is an opening chapter on knowledge representation. We, therefore, discuss some elementary aspects, relevant to this chapter. Before presenting the technique for knowledge representation by Production Systems, we define the term "Knowledge", which is widely used throughout the text.

Formally, a piece of knowledge is a function that maps a domain of clauses onto a range of clauses. The function may take algebraic or relational form depending on the type of applications. As an example consider the production rule PRi , which maps a mother-child relationship between (m, c) to a Love relationship between the same pair.

where the clause Mother (m, c) describes that "m" is a mother of child "c"; the clause Loves (m, c) denotes that "m" loves "c" and the arrow denotes the if-then condition. In brief, the rule implicates: if "m" is a mother of child "c " then "m" loves "c".

The production system is the simplest and one of the oldest techniques for knowledge representation. A production system consists of three items: i) a set of production rules (PR), which together forms the knowledge base, ii) One (or more) dynamic database(s), called the working memory and iii) a control structure / interpreter, which interprets the database using the set of PRs [4], [7]. The production system, which has wide applications in automata theory, formal grammars and the design of programming languages, however, entered into knowledge engineering (1978) by Buchanan and Feigenbarm [2] only a few years back.

Before presenting the architecture of a production system, applied to intelligent problem solving, let us first introduce the functionaries of its modules.

3.2 Production Rules

The structure of a production rule PR1 can be formally stated as follows:

PR1: P1 (X) A P2 (Y) A .. Pn (X, Z) — Qi (Y) V Q2 (Z) V.. Qm (Y, X)

where Pi and Qj are predicates; x, y, z are variables; "A", "V" , and " —" denote the logical AND, OR and if-then operators respectively. The left-hand side of a PR is called the antecedent / conditional part and the right-hand side is called the consequent / conclusion part. Analogously, the left-side symbol Pi is called the antecedent predicate, while the right-side symbol Qj is called the consequent predicates.

It should be pointed out that the antecedent and consequent need not be always predicates. They may equally be represented by object-attribute-value triplets. For example, (person-age-value) may be one such triplet. To represent the rules in this fashion, we consider an example, presented in PR2.

PR2 : if (person age above-21) & (person wife nil) & (person sex male) then (person eligible for marriage) .

It should further be noted that though object-attribute-value in PRs are often represented using variables, still the presence of constants in the triplet-form cannot be excluded. PR3, given below, is one such typical example.

PR3: if (Ram age 25) & (Ram wife nil) & (Ram sex male) then (Ram eligible for marriage).

In the last example person's name and age are explicit in the PR.

3.3 The Working Memory

The working memory (WM) generally holds data either in the form of clauses or object-attribute-value (OAV) triplet form. The variables in the antecedent predicates / OAV relationship of the antecedent part of PRs are matched against the data items of the WM. In case all the variable instantiation of the antecedent parts of a rule are consistent, then the rule is fired and the new consequents are added to the WM. In some production systems, the right-hand-side of the rule indicates which data are to be added to or deleted from the WM. Normally, new consequents are added to the WM and some old data of WM, which are no longer needed, are deleted from the WM to minimize the search time required for matching the antecedent parts of a rule with the data in WM. OPS5 is a production language that offers the addition / deletion features highlighted above.

3.4 The Control Unit / Interpreter

The control unit / interpreter for a production system passes through three steps, which together is called the recognize-act cycle [4].

Recognize-Act Cycle

1. Match the variables of the antecedents of a rule, kept in a knowledge base, with the data recorded in the WM.

2. If more than one rule, which could fire, is available then decide which rule to fire by designing a set of strategies for resolving the conflict regarding firing of the rules.

3. After firing of a rule, add new data items to WM or delete old (and unnecessary) data, as suggested by the fired rule from the WM and go to step (1).

Generally, a start-up element is kept at the working memory at the beginning of a computation to get the recognize-act cycle going. The computation process is terminated if no rule fires or the fired rule contains an explicit command to halt.

The conflict resolution process helps the system by identifying which rule to fire. It is, however, possible to construct a rule-set where only one rule is firable at any instant of time. Such systems are called deterministic. Since most of the real world problems contain a non-deterministic set of rules, it becomes difficult for many systems to present the rule-set in a deterministic manner.

Good performance of a control unit / interpreter depends on two properties, namely, i) sensitivity and ii) stability [4]. A production system or more specifically a control unit is called sensitive, if the system can respond quickly to the change in environment, reflected by the new contents of the WM. Stability, on the other hand, means showing continuity in the line of reasoning.

3.5 Conflict Resolution Strategies

The Conflict Resolution strategies vary from system to system. However, among the various strategies, the following three are most common. In many systems a combination of two or all of the following strategies [4] are used for resolving conflict in a control unit.

1. Refractoriness

This strategy requires that the same rule should not be fired more than once when instantiated with the same set of data. The obvious way of implementing this is to discard the instantiations from the WM, which have been used up once. Another version of their strategy deletes instantiations, which were used up during the last recognition-act cycle. This actually helps the system overcome the problems of moving on loops.

2. Recency

This strategy requires that the most recent elements of the WM be used up for instantiating one of the rules. The idea is to follow the leading edge of computation, rather than doubling back to take another look at the old data. Doubling back, of course, is necessary when the reasoning in the current line of action fails.

3. Specificity

This strategy requires that the rule with more number of antecedent clauses be fired than rules handling fewer antecedent clauses. As an example, consider the following two rules, denoted as PR1 and PR2.

Suppose the WM contains the data Bird (parrot) and Not emu (parrot). Then both the rules are firable. However, the second rule should be fired using the specificity strategy.

3.6 An Alternative Approach for Conflict Resolution

The MYCIN experiments [3] of Stanford University proposed another approach for resolving conflicts via metarules. Metarules too are rules, whose task is to control the direction of reasoning and not to participate in the reasoning process itself. Metarules can be either domain-specific or domainfree. A domain-specific metarule is applicable for identifying the rule to fire only in a specific domains, while domain-free metarules are of very general kinds and can be used for controlling the firing of rules in a generalized knowledge base. To illustrate this concept, we take examples from MYCIN [3].

Example 3.1: Domain-specific metarule

Metarule: IF 1) the infection is pelvic abscess and

2) there are rules which mention in their premise entero-bactoriae, and

3) there are rules which mention in their premise gram- positive rods.

THEN there exists suggestive evidence (0.4) that the former should be applied before the latter.

Example 3.2: Domain-free rule

Metarule: IF 1) there are rules which do not mention the current goal in their premise, and

2) there are rules while mention the current goal in their premise

THEN it is definite (1.0) that the former should be applied before the latter.

Fig. 3.1: Architecture of a typical production

system.

The architecture of a production system [5] is now presented, vide fig. 3.1. The conflict resolution with two rules PRi and PRj has been demonstrated in this architecture. The other descriptions in fig. 3.1 being self-explanatory are left to the readers for interpretation.

To demonstrate the working principle of a production system, let us illustrate it using the well- known water-jug problem. The following statement can best describe the problem.

3.7 An Illustrative Production System

We now consider the well known water jug problem, presented below, as a case study of production systems.

Example 3.3: Given 2 water jugs, 4 liters and 3 liters. Neither has any measuring marks on it. There is a pump that can be used to fill the jugs. How can you get exactly 2 liters of water into 4-liter jugs?

Let us assume that u and v denote the content of 4L and 3L jugs respectively. The content of the two jugs will be represented by (u, v). Suppose, the start-up element in the WM is (0,0). The set of PRs for the problem [8] are listed below.

List of PRs for the water-jug problem

PR 1. (u, v : u <4) ^ (4, v) PR 2. (u, v : v <3) ^ (u, 3)

PR 3. (u, v : u >0) ^ (u - D, v ), where D is a fraction of the previous content of u.

PR 4. (u, v : v >0) ^ (u, v - D), where D is a fraction of the previous content of v.

PR 5. (u, v : u >0) ^ (0, v) PR 6. (u, v : v >0) ^ (u, 0)

PR 7. (u, v : u + v > 4 A v >0) ^ (4, v - ( 4 - u)) PR 8. (u, v : u + v > 3 A u >0) ^ (u - (3 - v), 3) PR 9. (u, v : u + v <4 A v >0) ^ (u + v, 0)

To keep track of the reasoning process, we draw a state-space for the problem. Note that the leaves generated after firing of the rules should be stored in WM. We first consider all possibilities of the solution (i.e., without resolving the conflict). Later we would fire only one rule even though more than one are firable. The state-space without conflict resolution is given in fig. 3.2.

0 0

Post a comment