Rule Based Expert System

Definition

An expert system is a type of software that after a training session, it is able to make deductions or choices itself by reading a set of initial informations called facts.

On an expert system the competence of an human expert is coded in the knowledge base (for instance as a rule) updatable in base of the experience.

Rule based expert systems are software composed of rules in the form “IF condition THEN action”.

Given a set of facts expert systems, thanks to the rules which are composed, are able to deduct new facts.

Why do I have to choose a rule based expert system?

Rules allow us to represent some kinds of knowledge that are difficult to implement in a canonical procedural software.

A rule based software splits the knowledge from the code logic.

With this approach it turns out the advantage that if there is a changement on the knowledge this not implies a changement of the procedural program and thus gives more flessibility, it is possible to posticipate some decisions or reconsider them without rewrite the whole software.

A sofware rule based can be write in severals ways. Some languages such as OPS-5 have been studied for this purpose (http://free-compilers.sharnoff.org/TOOL/OPS5-1.html).

What is a rule?

A rule gives some guidelines of how to solve a problem. It is based on the IF-THEN construct.
In the IF part is specified a fact or an information instead in the THEN part is specified an action.

The IF part is called ANTECEDENT (CONDITION or PREMISE) instead the THEN PART is called CONSEQUENCE (CONCLUSION or ACTION).

Definition of production rule based system

A production rule based system is composed by three elements:

  1. Knowledge Base (also known as long term memory) in which are stored the production rules
  2. Working Memory (also known as short term memory) in which are stored data and deductions computed by the systems
  3. Inference Engine

Each production rule has the following schema:

IF THEN

The rules are not invoked by their name but they are activate in base of pattern-matching.

The knowledge

  • Facts: informations regarding a particular situation
  • Rules: they sets basic mechanism if : : : then : : :

Rules type

  • Relations (e.g. casual relations)
  • Recommendations, advices, hints
  • Directives
  • Strategy
  • Euristic

Relations

IF the fuel tank is empty
THEN the car is dead.

Recommendations

IF the season is autumn AND the sky is cloudy
THEN I recommend you to take the umbrella

Strategy

IF the car is dead
THEN the action is check the FUEL tank; step-1 completed.

IF step-1 completed AND the FUEL tank is FULL
THEN the action is check the battery; step-2 completed.

Heuristic

IF the liquid is dark AND it has a pH<6 AND it has a acidulous smell THEN the liquid is 'balsamic vinegar'.

Directives

IF the car is dead
AND the fuel tank is empty
THEN the action is ‘refuel the car’.

Inference mechanisms – What to do Next?

There are two control techniques (chaining the rules):

Forward chaining: is also known as data-driven reasoning. It starts from the data (facts) stored in the short term memory and tries to reach a conclusion applying the rules following a chain forward. It stops when no further rules can be fired.

Backward chaining: is also known as goal-driven reasoning.

FORWARD CHAINING ALGORITHM (or DATA-DRIVEN)

In the initial configuration, the working memory contains the initial knowledge of the problems, that is the known facts.

The production rules applicable are those in which the antecedent might matching with a rule on the working memory (F-Rules).

Each time a rule is fired new facts are deducted and inserted in the working memory.

The cycle stops with success when in the working memory is inserted the goal to demostrate (terminal condition)

while <GOAL NOT REACHED> do
    begin
        <MATCH: compute the set of matching rules>;

        <CONFLICT_RESOLUTION: select the rule to apply>;

        <FIRE: execute the action associated to the rule>;
    end;


Hereafter is shown the mechanism of inference:
Inference

Example with Forward Chaining

Rules:
R1: Y and D → Z
R2: X and B and E → Y
R3: A → X
R4: C → L
R5: L and M → N
Facts: A B C D E

Rules that might be applied: R3,R4
2. Choosing R3
3. Facts: A B C D E X
4. Applicable rules: R2,R4
5. Choosing R2
6. Facts: A B C D E X Y
7. Applicable Rules: R1,R4
8. Choosing R1
9. Facts: A B C D E X Y Z
10. Applicable Rules: R4
11. Choosing R4
12. Facts: A B C D E X Y Z L
13. stop

Example

Given an expert system with the following rules:

R1) IF raining THEN grass_is_wet
R2) IF raining THEN roof_is_wet
R3) IF sprinkler_on THEN grass_is_wet
R4) IF roof_is_wet THEN water_in_garage

Given the following facts:

F1) raining

We would know if there is water in the garage (water_in_garage is true).

In case of a conflict resolution, the system chooses the rulex with the lower index (R2 will be fired before of R5)

Forward chaining

The working memory has only one information: raining.

The algorithm searchs for a matching with a fact (there is only a fact now)

There are two possible matching rules: R1 and R2. The system selects R1 and inserts on the working memory the fact grass_is_wet. The rule R1 will no longer considered.

Given the facts (raining and grass_is_wet), the next fired rule is R2 and the system add on the working memory the fact roof_is_wet. The rule R2 will no longer considered.

Given the current facts and with the elimination of the rules R1 and R2, the only matched rule is R4 that allow to insert in the working memory the fact that water_in_garage that is the goal.

Links

Leave a Reply