0.Cover

Rules-14

Rule-based Systems

rule-based systems are built around rules like the following:
Rule R_n if condition 1
condition 2
...
then action 1
action 2
...
block diagram of a rule-based system:
A working memory is a representation in which
- lexically, there are assertions and application-specific symbols. There are also patterns that contain application-specific symbols mixed with pattern symbols.
- Structurally, the assertions are lists of application-specific symbols
- Semantically, the assertions denote facts in some world.
With constructors that
- add an assertion to working memory
with readers that
- produce a list of the matching assertions in working memory, given a pattern.

A rule base is a representation in which
- there is a working memory
- lexically, there are rules.
- Structurally, the rules consists of patterns. Some of these patterns constitute the rule's if patterns; the others constitute the rule's then pattern.
- Semantically, rules denote constraints that enable procedures to seek new assertions or to validate a hypothesis.
With constructors that
- construct a rule, given an ordered list of if patterns and a then pattern
with readers that
- produce a list of a given rule's if patterns
- produce a list of a given rule's then patterns.

Example (Theatre)

Rule	IF	THEN
T1	Distance > 5 miles	Means is "drive"
T2	Distance > 1 mile and time < 15 min.	Means is "drive"
T3	Distance > 1 mile and time > 15 min.	Means is "walk"
T4	Means is "drive" and location is "downtown"	Action is "take a cab"
T5	Means is "drive" and location not "downtown"	Action is "drive your car"
T6	Means is "walk" and weather is "bad"	Action is "take a coat and walk"
T7	Means is "walk" and weather is "good"	Action is "walk"

Assertions: (in Working Memory)

A1: The theatre is located 6 miles away

A2: The weather is bad

A3: The theatre's location is downtown

A4: The film starts in 10 minutes.

Premises of the rules are examined to see whether or not they are true given the information on hand (recognized-act cycle)

Cycle	Rules	Rule selected	Add to Working Memory
0			A1, A2, A3, A4
1	T1,T2	T1	means is "drive"
2	T1,T2,T4	T2
3	T1,T2,T4	T4	action is "take a cab"
4	T1,T2,T4		stop

Conflict Resolution Strategies

Specificity Ordering
- use a rule whose IF part is more specialized.
Rule Ordering
- arrange the rules in one long priority list
Data Ordering
- arrange all possible aspect of the situation in one long list.
Size Ordering
- use a rule whose IF part is longest
Recency Ordering
- consider the most recently used rule to have the highest priority, or the least recent one.
Context limiting
- Reduce the likelihood of conflict by separating the rules into groups.

Example:

Rule	IF	THEN
I1	the animal has hair	it is a mammal
I2	the animal gives milk	it is a mammal
I3	the animal has feather	it is a bird
I4	the animal flies and it lays eggs	it is a bird
I5	the animal is a mammal it eats meat	it is a carnivore
I6	the animal is a mammal it has pointed teeth it has claws its eyes point forward	it is a carnivore
I7	animal is a mammal it has hoofs	it is an ungulate
I8	animal is a mammal it chew cud	it is an ungulate it is even-toed
I9	animal is a carnivore it has a tawny color it has dark spots	it is a cheetah
I10	animal is a carnivore it has a tawny color it has black strip	it is a tiger
I11	animal is an ungulate it has long legs it has long neck it has a tawny color it has dark spots	it is a giraffe
I12	animal is an ungulate it has a white color it has black strip	it is a zebra
I13	animal is a bird it does not fly it has long legs it has a long neck it is black and white	it is an ostrich
I14	animal is a bird it does not fly it swims it is black and white	it is a penguin
I15	animal is a bird it is a good flyer	it is an albatross

In a zoo, an unknown animal with the following observation:

has a tawny color
has dark spots
animal chews it cud
animal gives milk
animal has long legs
animal has long neck

Cycle	Rules selected	Add to Working Memory
1	I2	animal is mammal
2	I8	animal is ungulate
3	I11	animal is giraffe

Backward-Chaining Deduction

a rule-based system can hypothesized a conclusion (or goal) and use the antecedent-consequent rules to work backward toward the hypothesis-supporting facts.

Example (Theatre)

goal is to find an action.

Cycle	Rule Selected	Actions
0		Goal is action
1	T4	Mean=? Location=?
2	T1	Distance > 5?
3	Ask Question	Distance=2
4		Rule 1 failed
5	T2	Distance > 1 Time < 15?
6	Ask Question	Time=10
7		Rule T2 succeeded mean is "drive"
8	T3	Rule T3 failed
9	T4	Location=?
10	Ask Question	Location=Downtown
11		Rule T4 succeeded
12	T5,T6,T7	T5,T6,T7 failed
13		consultation done
14		action is "take a cab"

Animal Example

hypothesize that animal is cheetah
From rule I9 animal is a carnivore and
animal has tawny color and
animal has dark spots
verify animal is a carnivore
2 rules, I5, I6.
Try i5: animal is a mammal and
it eats meat
verify animal is a mammal
2 rules, I1, I2.
Try I1: animal has hair
Does animal have hair?
Assume Yes.
Then animal is mammal.
Does animal eat meat?
No evidence to conclude. Abandon I5.
Try I6 animal is a mammal and
it has pointed teeth and
it has claws and
its eyes point forward
animal is a mammal û established.
animal has pointed teeth û Yes.
animal has claws? û Yes.
animal has eyes point forward? û Yes
conclude animal is a carnivore.
animal has tawny hair? û Yes
animal has dark spot? û Yes
conclude animal is cheetah.

AND-OR Graph Representation of Backward Chaining

Grouping of Rules

As rule base grow in size, inefficient in searching
Group the rules into groups
e.g.

If current goal is concerning mammals, there is no need to search rules about birds, etc.

Combination of Forward & Backward System

Forward chaining:
- generate new facts from known facts
- starting from the leaves of the AND-OR graph and deduce towards the goal.
Backward chaining:
- verify goal by generating subgoals and verify them.
- starting from the goal and deduce towards the leaves.
A combination forward & backward system:
- starting from the goal (root of tree) and the leaves (facts)
- backward system grow from goal towards leaves.
- forward system grow from leaves towards root.
- Hoping to meet in the middle (a bi-directional search)

Example (Animal Example)

forward deduction : generate new facts.
From has hair & gives milk 0 mammal
backward deduction : verify goal
verify is-carnivore 0 verify is-mammal & eat-meat
can group rules into
- forward rules: used by forward chaining system
- backward rules: used by backward chaining system.
Some rules are more suitable for forward systems and others backward systems.
e.g. CAT(x) 0 ANIMAL(x)
DOG(x) 0 ANIMAL(x)
are more suitable for forward system, while
~ANIMAL(x) 0 ~CAT(x)
~ANIMAL(x) 0 ~DOG(x)
are more suitable for backward system.

Including control knowledge

Meta Rules
- rules about how rules should be applied
  e.g. IF goal is verify a tiger THEN
  try rules about mammals ... etc
Heuristic Function
- embedding some of the control knowledge into evaluation functions used by the control strategy.
Rule Modification
- include the control information into the rules instead of using meta rules
- more straightforward but less efficient.

Answer Questions about Deduction

WHY do you ask this question?
- From the current triggered rule
- example (Theatre)
  at cycle 3, the system ask question:
  > What is the distance from home to theatre?
  >> WHY?
  >By rule 1, to establish mean=drive, we need to know the distance ...
HOW do you get your conclusion.
> Action is "take a cab"
>> How?
- the answer can be obtained from the AND-OR graph
> since distance > 1 mile and time < 15 min, by rule 2, the mean to theatre is "drive". Location of theatre is at downtown. By rule 4, the action is take a cab.
- what rules are successfully fired?
  repeat the condition satisfied.

AND-OR graph of the theatre example:

For the animal example:

How?

Animal is Cheetah?

Forward Vs Backward Systems

Forward Chaining System

Advantages:

works well when the problem naturally begins by gathering information and then seeing what can be inferred from it.

E.g. Patient has a high temperature and a sore throat ...
can provide a considerable amount of information from only a small amount of data.
DATA NEW INFORMATION
Raining 0 Grass is wet 0 Can't mow grass
0 Game cancelled 0 Goto Theatre
Forward-chaining is an excellent approach for certain types of problem solving task, such as planning, monitoring, control and interpretation.

Disadvantages:

have no means of recognizing that some evidence might be more important than others

[The system will ask all possible questions, even though it may only need to ask a few to arrive conclusion]
The system may also ask unrelated questions.
E.g. Q: Do you have a high temperature?
Q: Have you visited England lately?

Backward Chaining Systems

Advantage:

works well when the problem naturally begins by forming a hypothesis and then seeing if it can be proven:
e.g. "I believe the patient has strep throat"
Backward chaining remain focused on a given goal. This produces a series of questions on related topics, a situation which is comfortable for the user.
It searches only that part of the knowledge base that is relevant to the current problem.
Excellent approach for certain types of problem solving task, such as diagnosis, prescription and debugging.

Disadvantages:

it will continue to follow a given line of reasoning even if it should drop it and switch to a different one.

Choosing between forward and backward system

How does the expert solve it?
- First collect data and then see what can be inferred from it 0 forward chaining.
- Hypothesize a solution and then see if it can be proven 0 backward chaining.
Consider the search space
Past/others' experience
prototype the system early to evaluate the choice.