Transcript Rules and Rewriting: CLIPS

Rewriting Rules, CLIPS
Content of this lecture:
1. Interpretation of rules
2. Example: CLIPS Sorting
3. Non-determinism
4. Control regimes: Selection
5. Conflict Resolution
Content of next lecture:
1. Serious CLIPS: Language
Understanding
2. Interpreter issue: Rete
Expert Systems 3
C
Language
Integrated
Production
System
(NASA, 1985)
1
Rules as Declarative Knowledge
Example of a declarative rule:
IF
X is a rabbit
THEN X is four-legged
Meaning independent of
program state.
Premisse: X is rabbit
Conclusion: X is four-legged
Procedural interpretation:
IF
the memory state has
X stored as a rabbit
THEN update the state to
make X four-legged
When will this happen??
Expert Systems 3
Rule gives Z-knowledge:
Rabbit
Non-Rabbit
Four-legged
Non-four-legged
We don’t know the situation
when X is not a rabbit
2
Conditional statement in programming
Form of conditional:
if
c
if
c
then S1
then S1
else S2
Executed at some point;
know exactly what happens!
Condition c at that moment
gives action S1,
non c gives action S2.
Form of production rule:
• Theoretical:
{c} S1
• Informal in Rule-based:
IF c
THEN S1
But not conditional statement!
• In CLIPS:
(defrule NAME
c
=>
S1
)
Truth of c allows application of
action S1
Expert Systems 3
3
What if more rules apply?
Life experiment with four volunteers
Describe the positions of these heroes
Expert Systems 3
4
Representation of facts: Relations
• Define table structure:
(deftemplate neighbor
(field left (type SYMBOL))
(field right (type SYMBOL))
)
• Provide facts:
(deffacts inputs
(neighbor (left Anneke)
(right Bert))
(neighbor (left Bert)
(right Carol))
(neighbor (left Carol)
(right Danny))
)
Object, Attribute, Value
Expert Systems 3
Table name
Column name
neighbor
left
right
Anneke
Bert
Carol
Danny
Bert
Carol
Table content: 3 facts
Facts are numbered
(time stamped)
5
Numerical inputs for the volunteers
(deftemplate holds
(field person (type SYMBOL))
(field number (type INTEGER))
)
(holds
(holds
(holds
(holds
(person
(person
(person
(person
Anneke) (number 17))
Bert) (number 6))
Carol) (number 7))
Danny) (number 27))
holds
person
Anneke
number
17
Expert Systems 3
Goal: put numbers in
ordered sequence
6
The sorting rule: swap
IF
neighbor X Y
X holds a
Y holds b
b>a
THEN X gets b
Y gets a
Procedural sorting knowledge:
parties exchange their
numbers when locally in
wrong order
Expert Systems 3
7
The sorting rule in CLIPS
Rule name
Value wildcard
Value wildcard
(defrule swap
(neighbor (left ?X) (right ?Y))
Tuple wildcard
?Xhas <- (holds (person ?X) (number ?a))
?Yhas <- (holds (person ?Y)
(number ?b&:(> ?b ?a)))
=>
(modify ?Xhas (number ?b))
Value condition
(modify ?Yhas (number ?a))
)
Matching instantiation:
Action part modifies
Facts w. common value of X, Y, a, b
two existing facts
Defines (binds) values for wildcards
Expert Systems 3
8
Non-determinism
• “Program determines behavior of Computer”
• Sorting rule allows different behaviors depending on
chosen instantiation:
Non-determinism
• Theorem 1: Each sequence of swaps is finite.
• Theorem 2: In any blocked situation, numbers are
descending.
• Conclusion:
Non-determinism is not necessarily a problem.
Expert Systems 3
9
The Recognize-Act Cycle
works as
Rule interpretation is a threeMatch
stroke engine:
1. Match:
Form Conflict Set by finding
Conflict set
Fact base
satisfied rule instances.
(CLIPS: Agenda)
2. Choose:
Select one instance from the
conflict set by applying a
Conflict Resolution strategy.
Choose
Apply
3. Apply:
“Happy”
Modify memory according to
rule
selected rule.
Conflict set is usually formed
explicitly.
Expert Systems 3
10
Beyond Sorting: Selection
Find the second largest number
1. Sort the numbers;
2. Find the person on position 2
(from neighbor relation);
3. Output the number of person
on position 2.
Sequential programming:
sort program ;
indexer program ;
output program.
Expert Systems 3
Production rule set:
Sorting
Rules
Indexing
Rules
Output
Rules
11
Rules for indexing
(deftemplate index
(field person (type SYMBOL))
(field place (type INTEGER))
)
Absence of tuple
cannot bind
wildcard
(defrule pickfirst
(neighbor (left ?X))
(not (neighbor (right ?X)))
=>
(assert (index (person ?X) (place 1)))
Add
object
)
(defrule picknext
(neighbor (left ?X) (right ?Y))
(index (person ?X) (place ?I))
=>
(assert (index (person ?Y) (place (+ ?I 1))))
Expert Systems 3
)
Clutter Logic in
Parenthesis Spaghetti
12
Rule for output
(defrule answer
(index (person ?X) (place 2))
(holds (person ?X) (number ?A))
=>
(printout t crlf
"The second greatest number is “
?A "." t crlf )
)
Summary of rules:
• Sorting: swap
• Indexing: pickfirst, picknext
• Output: answer
See program select.clp and play
with it in the CLIPS interpreter
Expert Systems 3
13
Control the firing of rules
Conflict Resolution can be
• Local control
Preference among rules is explicit in program
Strategy is problem dependent
Ex. Meta-Rules (not in CLIPS)
Salience, Goal variable
• Global control
Use built-in mechanism of interpreter
Bad adaptation to domain, but can select best one
Ex. Depth, Breadth, Specificity,
MEA, LEX
(Non-determinism of the second type:
not relevant for CLIPS.)
Expert Systems 3
14
Salience: Ordering on Rules
• Add in rule: (declare (salience 30))
• Range -100 … 100, default 0.
• Selection program (selectSalience.clp):
Sorting 30, indexing 20, output 10.
• Note: firing of rule may enable a rule of higher salience
Higher rule will be preferred in next cycle!
Sorting gets high priority permanently!!
• No resolution among instantiations of same rule
• Easily overcontrolled:
sorting and indexing can overlap
Expert Systems 3
15
Control with goal variable
• Simple variable has two names!
(deftemplate goal
(field phase (type SYMBOL)) )
• Add condition to rules:
(defrule answer
(goal (phase output))
(index (person ?X) (place 2))
• Explicit switch of goal (new rule!):
(defrule endindexing
?c <- (goal (phase indexing))
(index (place 2))
=>
(modify ?c (phase output)) )
• Ex.: selectGoal.clp.
• Fine control over subtasks
• Alternation possible
Expert Systems 3
Table name
Column name
goal
phase
sorting
Table storage:
multiple goals
simultaneously
16
Global control regimes
• Order in program
• Refraction: never repeat an instantiation.
(defrule pickfirst
(not (neighbor (right ?X))) =>
(assert (index (person ?X) (place 1)))
Need not condition on uncomputed place
• Recency: order by time tags of matching facts
• Specificity: prefer instantiations with more facts
bird => fly
bird, penguin => not fly
Suitable for coding exceptions or shift of goal.
Expert Systems 3
)
17
Depth and Breadth
• Depth strategy:
Prefer instantiations by new
facts
• Breadth strategy:
Prefer instantiations by old
fact
Start state
QED
Expert Systems 3
18
Complexity used to switch subtasks
Abbreviation!
(defrule swap
(goal sort)
(neighbor ?X ?Y)
?Xs <- (holds ?X ?a)
?Ys <- (holds ?Y ?b>?a)
=>
(modify ?Xs (number ?b))
(modify ?Ys (number ?a))
)
• Conditions of endsort less
complex than swap
• Goal is changed only when
no swap applies
• Explicit switch prevents later
uncontrolled swapping (cp.
with salience)
• Requires the global regime
complexity to be selected!
(defrule endsort
?c <- (goal sort)
=>
(modify ?c indexing)
)
Expert Systems 3
19
LEX (lexicographic)
• Each fact has time stamp
• To choose from conflict set:
1. Dump all instantiations not using the most recent
fact present in the CS;
2. From remaining facts, drop this most recent fact
Repeat until choice is made.
• LEX implies Recency and Complexity
• MEA variation: first order by time
stamp of fact in first condition of rule
Live experiment
Expert Systems 3
20
Summary and conclusions
• Production rules encode steps towards solution
• Non-determinism results from collection of rules
• Local control regimes resolve conflicts by adding metaknowledge to the program
• Eliciting and coding meta-knowledge is difficult
• Knowledge and meta-knowledge are not well-separated
in rule-based program (CLIPS)
• Global control regimes use properties of the interpreter
• Different global regimes cannot be combined
• Selection is not a typical Expert System task!
• Next class (4): Language understanding
Expert Systems 3
21