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 knowledge and rules to simulate human decision-making.

The Architecture of a Rule-Based Expert System

The production system model, introduced in the 1970s, forms the core of modern rule-based expert systems. It separates the "rules" of the world from the specific "facts" of the current problem.

1. Knowledge Base: Contains domain-specific knowledge formatted as a set of IF-THEN production rules (Long-term memory).
2. Database: Contains facts that are utilized to match the IF part of the production rules (Short-term memory).
3. Inference Engine: The brain of the system. It connects the rules from the knowledge base with the facts in the database to derive solutions.
4. Explanation Facilities: Allows the user to ask the system why a particular conclusion was reached or why a specific fact is needed.
5. User Interface: The communication medium between the system and the user.

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. Here are the five primary categories:

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 understand how the Inference Engine reasons, let us use a consistent Knowledge Base and Database:

• 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: Prove $Z$

1. Forward Chaining (Data-Driven Reasoning)

Forward chaining starts with the known facts in the database and works forward, firing rules whose conditions are met to deduce new facts.

Step-by-Step Execution Trace

1. Cycle 1:
   • Match: The database $\{A, B, C, D, E\}$ satisfies the antecedents of Rule 3 (needs $A$) and Rule 4 (needs $C$).
   • Conflict Resolution: Suppose we fire the topmost matching rule, Rule 3.
   • Action: The database is updated: we add the fact $X$.
   • New DB: $\{A, B, C, D, E, X\}$.
2. Cycle 2:
   • Match: The new database satisfies the antecedent of Rule 2 (needs $X \wedge B \wedge E$, which are all present) and Rule 4 (needs $C$).
   • Action: We fire Rule 2.
   • New DB: $\{A, B, C, D, E, X, Y\}$.
3. Cycle 3:
   • Match: The database satisfies Rule 1 (needs $Y \wedge D$) and Rule 4 (needs $C$).
   • Action: We fire Rule 1, adding $Z$ to the database.
   • New DB: $\{A, B, C, D, E, X, Y, Z\}$.
4. Cycle 4:
   • The goal $Z$ is now in the database. Reasoning terminates successfully!

• Best Used When: You have all or many facts known, and you want to discover everything that follows from them (e.g., system monitoring, real-time alerts).

2. Backward Chaining (Goal-Driven Reasoning)

Backward chaining starts with the goal we want to prove ($Z$) and recursively works backward to find rules that can establish it.

Step-by-Step Execution Trace

1. Pass 1 (Goal $Z$):
   • We search the Knowledge Base for rules that conclude $Z$. Rule 1 ($Y \wedge D \rightarrow Z$) is selected.
   • To prove $Z$, we must prove $Y$ and $D$.
   • We check the database: $D$ is present. $Y$ is missing.
   • $Y$ becomes our new Sub-goal.
2. Pass 2 (Sub-goal $Y$):
   • We search for rules that conclude $Y$. Rule 2 ($X \wedge B \wedge E \rightarrow Y$) is selected.
   • To prove $Y$, we must prove $X$, $B$, and $E$.
   • We check the database: $B$ and $E$ are present. $X$ is missing.
   • $X$ becomes our new Sub-goal.
3. Pass 3 (Sub-goal $X$):
   • We search for rules that conclude $X$. Rule 3 ($A \rightarrow X$) is selected.
   • To prove $X$, we must prove $A$.
   • We check the database: $A$ is present!
   • Rule 3 fires. $X$ is added to the database. Sub-goal $X$ is successfully proven.
4. Pass 4 (Sub-goal $Y$ resolution):
   • Now that sub-goal $X$ is proven, and $B, E$ are already in the DB, the antecedents for Rule 2 are complete.
   • Rule 2 fires. $Y$ is added to the database. Sub-goal $Y$ is successfully proven.
5. Pass 5 (Goal $Z$ resolution):
   • Now that sub-goal $Y$ is proven, and $D$ is in the DB, the antecedents for Rule 1 are complete.
   • Rule 1 fires. $Z$ is added to the database.
   • Goal $Z$ is successfully proven!

• Best Used When: You have a specific hypothesis in mind and want to verify it without wasting time deriving irrelevant facts (e.g., medical diagnostics, checking eligibility).