Top

previous chapter Syntactic Pattern Analysis

next chapter Pattern Recognition and Cluster Analysis

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

9. Rule-Based Systems

Author: Mariusz Flasiński

Publisher: Springer International Publishing

Published in: Introduction to Artificial Intelligence

» Get access to the full version

Abstract

The main idea of reasoning in rule-based systems is, in fact, the same as in the case of logic-based reasoning introduced in Chap. 6. Both models are based on deductive reasoning.

Please log in to get access to this content

To get access to this content you need the following product:

Computer Science Explorer

Purchase now

The reader is recommended to recall the discussion in Sect. 6.1.

Basic notions concerning deductive reasoning are contained in Appendix F.2.

The issue of rule matching is discussed in detail in the next section.

It is called a set of conflicting rules because the system has to choose one reasoning path, i.e., it has to choose one of several matched rules, which compete. (They are in conflict.).

In fact, we can combine both strategies into the so-called mixed strategy of reasoning in rule-based systems. We do not discuss this in the monograph.

The reader should recall notions of progressive/regressive deduction. They are defined in Appendix F.2.

In our example we do not consider the issue of a conflict situation. This issue is discussed in the next section.

Let us remember that an agnatic grandfather is the father of somebody’s father.

If the reader is confused, then she/he is advised to draw a part of a genealogy tree for the third rule.

In an analogous way we have started the reasoning process in a FOL-based system in order to verify a hypothesis in Chap. 6. The way of reasoning is the difference between the two methods. In Chap. 6 we have used the resolution method, which is based on theorem proving by contradiction (in Latin: reductio ad absurdum). In the case of a rule-based system we use Backward Chaining, which is based on regressive deduction.

The reader who does not know the notion of a stack (in the computer science sense) should read Footnote 17 about pushdown automata in Sect. 8.2.

This is the main difference between BC and FC strategies. In the case of the FC strategy the system matches a condition of a rule to facts.

In Figs. 9.4 and 9.5 in the column BINDINGS we define bindings after performing successive substitutions.

The engine adds elementary conditions in any order, since a conjunction is commutative.

One can easily notice that the inference engine, firstly, tries to match the facts to the hypothesis on the top of the stack. Only if no fact matches the hypothesis, the engine tries to match rules. Let us notice that the fact \(F^{k}\) can be treated as a rule of the form: IF TRUE THEN \(F^{k}\).

Let us notice that after the substitution \(P^{4}\): A \(\leftarrow \) Raul, the following binding of variables and the constant holds: A = K = Raul, cf. Fig. 9.4c.

Let us remember that B = H according to the substitution \(P^{5}\). Thus, now the following binding of variables and the constant holds: B = H = Ian, cf. Fig. 9.4d.

In principle, this hypothesis should be removed later. However, we verify this obvious fact now.

Of course, taking into account the following bindings determined during the inference process: F = Karl, K = Raul, H = Ian, G = Earl.

In fact, it means that we are not able to recognize the initial hypothesis as valid on the basis of the facts and rules stored in the system.

Apart from the methods listed, we also use the principle of blocking a rule recently applied in case its corresponding facts do not change. We have used this rule in the previous section for the FC strategy.

For example, an AI system designed under the supervision of the author and Dr. Ulf Behrens for a particle physics experiment at the Deutsches Elektronen Synchrotron in Hamburg contained more than 1,300 rules and approximately 12,000 facts (see Behrens U., Flasiński M., et al.: Recent developments of the ZEUS expert system. IEEE Trans. Nuclear Science 43 (1996), pp. 65–68).

The rule-matching phase consumes about 90 \(\%\) of time of a single cycle.

Charles L. Forgy—a researcher in the area of rule-based systems, a Ph.D. student of Allen Newell. He designed OPS5, which was the first language used for constructing rule-based systems applied in practice.

In Latin rete means net.

Rules play a role, which is analogous to the productions of generative grammars.

Title

Rule-Based Systems

Book

Introduction to Artificial Intelligence

Print ISBN: 978-3-319-40020-4

Electronic ISBN: 978-3-319-40022-8

https://doi.org/10.1007/978-3-319-40022-8

DOI

https://doi.org/10.1007/978-3-319-40022-8_9

Author:

Mariusz Flasiński

Publisher

Springer International Publishing

Sequence number

Chapter number

Chapter 9