For overview, see lecture notes for Phil/Psych 256.

Rule-based systems are useful for implementing:

- deductive reasoning, e.g. proving theorems
- problem solving and planning
- explanation, e.g. medical diagnosis and scientific reasoning
- linguistic knowledge

A rule consists of

- IF part, consisting of a set of antecedents (also called conditions)
- THEN part, consisting of a set of consequents (also called actions)

Antecedents and consequents are assertions, e.g. "x is a student".

R1. IF x is enrolled-at-university THEN x is a student.

R2. IF x is a student, THEN x is short-of-money.

Working memory: set of assertions currently active.

Modus ponens is the logical rule that has the form: if P then Q, P, therefore Q.

Forward chaining is basically repetition of modus ponens:

Pat is enrolled-at-university, so (R1) Pat is a student, so (R2) Pat is short-of-money.

Instead of starting with what you know, as in forward chaining, you can start with what you want to know and work backward.

E.g. Is Pat short of money? We could answer this question using rule R2, if we could answer the question whether Pat is a student, which we could answer using rule R1 if we knew whether Pat is enrolled at university.

This is very useful for generating explanations (abductive reasoning).

Human problem solving is often bidirectional, using both forward and backward chaining, e.g. proving a theorem in geometry by paying attention both to the axioms and definitions (forward) and working backward from the theorem you need to prove.

In forward chaining, match the working memory
against the antecedents of a rule. If the rule's antecedents match,
then the rule is *triggered.*

In a deduction system, all the triggered rules
are *fired*, i.e. have their consequents added to the working
memory.

In a reaction system, however, there is a limit to what can be done, so only some of the triggered rules might be fired, following conflict resolution. E.g. suppose you have the rules IF shot-at THEN run, and IF shot-at THEN dive. You can't both run and dive at the same time.

In backward chaining working memory consists of a set of assertions to be established, and is matched against the consequents of rules to see which rules might be relevant to answering a question.

Assertions are naturally represented as lists, e.g. (Wayne plays hockey), or, in more logical format (plays Wayne hockey) or (plays (Wayne hockey)). Note that assertions can contain variables, e.g. (plays ?x ?y).

There are many different ways in which a rule might be implemented as a list, for example as: (rule-name (antecedent1 antecedent2 ...) (consequent1 consequent2 ...)).

I've found it convenient to use property lists, attaching to a symbol giving the rule name such properties as:

- antecedents
- consequents
- strength, i.e. usefulness
- confidence, i.e. probability

Working memory can be a symbol *working-memory*
whose value is a list of the active assertions.

A simple forward chaining rule-based system can operate by doing the following steps for each available rule:

- Match the antecedents of the rule against working memory.
- If all the antecedents of the rule are matched, then construct new assertions by adapting the consequents of the rule using the bindings established by the match of the antecedents.
- Add the new assertions to the working memory.

Continue until there are no more rules that can add anything to working memory.

This is really tricky. Suppose we are matching the assertion (plays Wayne hockey) against the rule (IF (plays ?x ?y) THEN (likes ?x ?y)). Then we need to bind ?x to Wayne and ?y to hockey, and construct the new assertion from the consequent that gets the variable binding straight in order to produce the new assertion in working memory, (likes Wayne hockey).

Rete matching is the standard way of performing this procedure.

The assertions in working memory are not statements that are accepted, but assertions you want to deduce or explain.

For each available rule:

- Match the
*consequents*of the rule against working memory. - If all the consequents of the rule are matched, then construct new assertions by adapting the antecedents of the rule using the bindings established by the match of the consequents.
- Add the new assertions to the working memory.

Continue until there are no more assertions that can be added or until desired result has been achieved, i.e. the question has been answered or the problem solved.

Computational Epistemology Laboratory.

This page updated Jan. 17, 2005