3a, Rule-based systems

Uses of rule-based systems

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

Rules: structure

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.

Rules: procedures

Forward chaining

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.

Backward chaining

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.

Matching

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.

3b, Implementing rules in LISP

Structures

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.

Procedures

Forward chaining

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.

Matching and binding

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.

Backward chaining

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.

Assignment # 2, due Feb. 3, 2005

Phil/Psych 446

Computational Epistemology Laboratory.

Paul Thagard