Overheads about Rule-based systems

Rules:

1. antecedent assertions
2. consequent assertions

(assumption that each rule has one consequent)

*Should* be able to make conclusion
(AND (consequent1) (consequent2))

Data (Working Memory) are assertions (facts).

Forward: starts with collection of assertions and tries all rules over and over, adding new assertions,
(book: until no rule can produce a new assertion)

(exhaustive or single acceptable)

E.g., R1 (XCON) John McDermott - CMU
In contrast, a system does backward chaining if it starts with a hypothesis and tries to verify the hypothesis using data already known

E.g., Mycin Shortliffe - Stanford

       recognize-act vs. hypothesize-test

Knowledge Representation:

Assertion and Rule Streams

Function:

(remember-assertion)
*assertions*

( *'s denote global variables)

Winston - page 381

Rules are basically a list of assertions where the last assertion is the consequent if the beginning ones are valid. Rules are given names ...so

page 381 functions

• rule-name
• rule-ifs
• rule-then

1. Remember MATCH
   Pattern variables make it possible to match a database of assertions for varying cases.

   Use a binding stream where each element is an association list of pattern variable bindings.

2. Match the first antecedent in the first rule against each assertion
   E.g. Winston page 382
3. Match the second antecedent in the first rule against each assertion *with* an association list from the initial binding.
   Some may lead to one or more assoc. lists in this second binding
   Some may fail and lead to nothing
4. Repeat for each antecedent.
   "The binding stream stretches and shrinks like a rubber band as it moves from filter to filter. For each way of matching the rule to the assertion database, an association list emerges in the binding stream that leaves the final filter."

   Instantiation - replacing variables with variable values

   Two instantiations
   (sugar is a horse)
   (brassy is a horse)

   When rules are "fired" (all antecedents of a given rule have appropriate bindings), the variables will be instantiated and then these instantiations will be included in the *assertions* for future use.

   At this point, the bindings are forgotten as a new rule is used and bindings must be individual to each specific rule.

5. Repeat for each rule until no new instantiations

   The code

try-assertion page 383 (matches a pattern to a single assertion)

(one if antecedent; one assertion)

match-pattern-to-assertions (matches a pattern (e.g., an antecedent) to all the assertions (facts in *assertions*) - and converts back to a stream) (can be given an initial (1) association list (binding))

(one if antecedent; all assertions)

filter-binding-stream (uses stream- transform to apply match-pattern-to-assertions once for each association list in the binding stream)

(takes stream so can match to all bindings so far (not one at a time)) (discuss bindings vs instantiate)

apply-filters (uses filter-binding-stream once for each pattern in a list of patterns

(all if antecendents)

Instantiation:

instantiate-variables (uses extract-value and find-binding defined in Ch.24)

Finally - use-rule
(uses apply-filters to apply filter-binding-stream to each of the rule's antecedents, then the instantiated consequences are added to the assertions stream using remember-assertion)

Really Finally - forward-chain
(uses use-rule on all rules until no new assertions)

animals is in PAIL
(usr/ai/pail/forward-rules/rules)
See code for rules and interface

Explanation - how and why

Other methods?

Task specific or task independent?
Domain specific or domain independent?
Shells