Lecture 08.1: Rule-Based Expert Systems

A computer program capable of performing at a human-expert level in a narrow problem domain area is called an Expert System. Rather than relying on traditional algorithmic logic, these systems use specific domain knowledge and rules to simulate human decision-making. Common examples include Rule-based expert systems, Fuzzy expert systems, and Frame-based expert systems.

Production System Model & Architecture

Introduced by Allen Newell and Herbert Simon at Carnegie-Mellon University in the early 1970s, the production system model forms the foundation of modern rule-based expert systems. It mirrors human cognitive problem-solving by separating long-term knowledge from short-term context.

Production Rule Structure

In a production system, domain knowledge is expressed as production rules consisting of an antecedent (condition) and a consequent (action):

$\text{IF } \langle\text{antecedent}\rangle \quad \text{THEN } \langle\text{consequent}\rangle$

• Example 1:

  IF the 'traffic light' is green
  THEN the action is go

• Example 2:

  IF the 'traffic light' is red
  THEN the action is stop

Five Core Components

1. Knowledge Base (Long-term Memory): Contains domain-specific production rules (IF-THEN) acquired from human experts.
2. Database (Short-term Memory): Contains current problem-specific facts used to match the antecedent (IF) part of production rules.
3. Inference Engine: The reasoning mechanism that matches database facts against knowledge base rules to infer new facts or conclusions.
4. Explanation Facilities: Enables users to ask why specific questions are asked or how conclusions were derived.
5. User Interface: The interaction channel between the non-expert user and the expert system.

The Five Categories of Rules

In an expert system, rules do not just represent simple conditional tests; they model different facets of human expertise and reasoning:

1. Relation

Expresses a static relationship or physical link between entities in the domain.

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

2. Recommendation

Advises a specific course of action based on environmental conditions.

IF the season is autumn
AND the sky is cloudy
AND the forecast is drizzle
THEN the advice is 'take an umbrella'

3. Directive

Gives a specific command or instruction to resolve a detected problem state.

IF the car is dead
AND the 'fuel tank' is empty
THEN the action is 'refuel the car'

4. Strategy

Outlines sequential, procedural steps to troubleshoot or analyze a problem.

IF the car is dead
THEN the action is 'check the fuel tank'; step1 is complete

IF step1 is complete
AND the 'fuel tank' is full
THEN the action is 'check the battery'; step2 is complete

5. Heuristic

Represents a rule-of-thumb, shortcut, or empirical observation used by human experts to solve problems quickly without full physical models.

IF the spill is liquid
AND the 'spill pH' < 6
AND the 'spill smell' is vinegar
THEN the 'spill material' is 'acetic acid'

Inference Techniques: Forward vs. Backward Chaining

To illustrate how the Inference Engine operates, consider the following benchmark system setup:

• Knowledge Base (Rules):
  • Rule 1: $Y \wedge D \rightarrow Z$
  • Rule 2: $X \wedge B \wedge E \rightarrow Y$
  • Rule 3: $A \rightarrow X$
  • Rule 4: $C \rightarrow L$
  • Rule 5: $L \wedge M \rightarrow N$
• Database (Initial Facts): $\{A, B, C, D, E\}$
• Goal: Infer $Z$

1. Forward Chaining (Data-Driven Reasoning)

Forward chaining starts with known data/facts in the database and proceeds forward by matching antecedents and firing rules to deduce new facts until no further rules can be fired or the goal is reached.

[!NOTE] Conflict Resolution Rule: When multiple rules match the database simultaneously, the inference engine executes the topmost rule in rule order. Each rule can be executed at most once.

Step-by-Step Execution Trace (Match-Fire Cycles)

1. Cycle 1:
   • Match: $\{A, B, C, D, E\}$ matches Rule 3 ($A \rightarrow X$) and Rule 4 ($C \rightarrow L$).
   • Fire: Rule 3 (topmost rule).
   • Database Updated: $\{A, B, C, D, E, X\}$.
2. Cycle 2:
   • Match: $\{A, B, C, D, E, X\}$ matches Rule 4 ($C \rightarrow L$) and Rule 2 ($X \wedge B \wedge E \rightarrow Y$).
   • Fire: Rule 4 (topmost rule).
   • Database Updated: $\{A, B, C, D, E, X, L\}$.
3. Cycle 3:
   • Match: $\{A, B, C, D, E, X, L\}$ matches Rule 2 ($X \wedge B \wedge E \rightarrow Y$).
   • Fire: Rule 2.
   • Database Updated: $\{A, B, C, D, E, X, L, Y\}$.
4. Cycle 4:
   • Match: $\{A, B, C, D, E, X, L, Y\}$ matches Rule 1 ($Y \wedge D \rightarrow Z$).
   • Fire: Rule 1.
   • Database Updated: $\{A, B, C, D, E, X, L, Y, Z\}$.
   • Result: Goal $Z$ is added to the database. Match-fire cycle terminates!

[!WARNING] Efficiency Limitation: Forward chaining is not efficient if the goal is to infer only one particular fact, because it derives all intermediate facts (such as $L$ via Rule 4) regardless of whether they contribute to the goal $Z$.

2. Backward Chaining (Goal-Driven Reasoning)

Backward chaining starts with a hypothetical solution or goal ($Z$) and searches the knowledge base backward to find supporting evidence and satisfy required sub-goals.

Step-by-Step Execution Trace (6-Pass Reasoning)

1. Pass 1 (Goal $Z$):
   • Search KB for rules deriving $Z \rightarrow$ Rule 1 ($Y \wedge D \rightarrow Z$).
   • Facts needed: $Y$ and $D$.
   • Check DB: $D$ is in DB; $Y$ is missing.
   • New Sub-goal: $Y$.
2. Pass 2 (Sub-goal $Y$):
   • Search KB for rules deriving $Y \rightarrow$ Rule 2 ($X \wedge B \wedge E \rightarrow Y$).
   • Facts needed: $X, B, E$.
   • Check DB: $B$ and $E$ are in DB; $X$ is missing.
   • New Sub-goal: $X$.
3. Pass 3 (Sub-goal $X$):
   • Search KB for rules deriving $X \rightarrow$ Rule 3 ($A \rightarrow X$).
   • Facts needed: $A$.
   • Check DB: $A$ is in DB!
4. Pass 4: Fire Rule 3 $\rightarrow$ Add $X$ to DB. Sub-goal $X$ proven.
5. Pass 5: Fire Rule 2 ($X \wedge B \wedge E \rightarrow Y$) $\rightarrow$ Add $Y$ to DB. Sub-goal $Y$ proven.
6. Pass 6: Fire Rule 1 ($Y \wedge D \rightarrow Z$) $\rightarrow$ Add $Z$ to DB. Goal $Z$ proven!

[!TIP] Goal-Directed Efficiency: Unlike forward chaining, backward chaining never evaluates Rule 4 ($C \rightarrow L$) or Rule 5 ($L \wedge M \rightarrow N$) because they do not lead to goal $Z$. This makes backward chaining optimal when verifying a specific hypothesis.