AI Notes
Learn inference engine. Forward, backward chaining. Expert systems 2024.
What is an Inference Engine?
The inference engine is the central reasoning component of an expert system—it determines how knowledge is applied to solve problems. Given a knowledge base of rules and a working memory of current facts, the inference engine decides which rules to fire, in what order, and how to derive new conclusions. It is the "brain" that transforms static knowledge into dynamic problem-solving.
Think of the knowledge base as a library and the inference engine as the librarian who knows how to find relevant books (rules), combine information, and produce answers. Without the inference engine, rules are just inert text; the engine brings them to life through systematic reasoning.
Core Reasoning Strategies
Forward Chaining (Data-Driven)
Forward chaining starts with known facts and applies rules to derive new facts until the goal is reached or no more rules apply. It works "forward" from data to conclusions.
| 2. MATCH | Find all rules whose conditions are satisfied |
| 3. CONFLICT RESOLUTION | Select one rule from the matched set |
| 4. EXECUTE | Fire the selected rule, add conclusion to working memory |
| 5. If goal reached | STOP; else → go to step 2 |
Forward Chaining Trace Example
Knowledge Base
R1: IF animal=has_feathers THEN animal=bird
R2: IF animal=bird AND animal=cannot_fly THEN animal=penguin
R3: IF animal=bird AND animal=can_fly AND size=small THEN animal=sparrow
R4: IF animal=penguin THEN habitat=antarctic
R5: IF animal=bird AND color=red THEN animal=cardinal
Working Memory: {has_feathers=yes, cannot_fly=yes, color=black_white}
Cycle 1
Match: R1 (has_feathers → bird)
Fire R1: Add bird=yes to working memory
WM: {has_feathers, cannot_fly, color=black_white, bird=yes}
Cycle 2
Match: R2 (bird AND cannot_fly → penguin)
Fire R2: Add penguin=yes
WM: {..., bird=yes, penguin=yes}
Cycle 3
Match: R4 (penguin → habitat=antarctic)
Fire R4: Add habitat=antarctic
WM: {..., penguin=yes, habitat=antarctic}
Cycle 4: No new rules match → HALT
Conclusion: The animal is a penguin from Antarctica.
Backward Chaining (Goal-Driven)
Backward chaining starts with a hypothesis (goal) and works backward to find supporting evidence. It's like a detective testing theories.
| a. If condition is in working memory | satisfied |
| b. If condition is unknown | set as new sub-goal (recurse) |
| c. If no rule can prove condition | ask the user |
| 4. If all conditions satisfied | goal proved; else → goal fails |
Backward Chaining Trace Example
| Goal | Is the animal a penguin? |
| Step 1 | Find rules concluding "penguin" |
| R2 | IF bird AND cannot_fly THEN penguin |
| Step 2 | Prove sub-goal "bird" |
| R1 | IF has_feathers THEN bird |
| Check has_feathers | In WM? Yes! → bird proved ✓ |
| Step 3 | Prove sub-goal "cannot_fly" |
| No rule concludes cannot_fly | ASK USER |
| User says: "Yes, cannot fly" | cannot_fly proved ✓ |
| Step 4: All conditions of R2 met | penguin PROVED ✓ |
Conflict Resolution Strategies
When multiple rules match simultaneously (conflict set), the engine must choose one:
| 1. SPECIFICITY | Prefer rules with more conditions |
| R1 | IF fever THEN maybe_sick |
| R2 | IF fever AND rash AND joint_pain THEN dengue |
| 2. RECENCY | Prefer rules matching recently added facts |
| 3. PRIORITY | Rules assigned explicit priority values |
| R1 (priority=5) | IF ... THEN ... |
| R2 (priority=8) | IF ... THEN ... |
| 4. REFRACTION | Don't fire the same rule on the same data twice |
| 5. FIRST-MATCH | Fire the first rule that matches |
The Rete Algorithm
The Rete (Latin for "net") algorithm efficiently matches rules against working memory. Instead of rechecking all rules every cycle, it builds a network that propagates changes incrementally.
Structure
Alpha network: Tests individual conditions
Node: "temperature > 100?"
Node: "has_cough = true?"
Beta network: Joins conditions across rules
Combines: temp>100 AND has_cough → partial match
Terminal nodes: Complete rule matches → conflict set
Efficiency
Naive matching: O(rules × facts^conditions) per cycle
Rete matching: O(changes × affected_rules) per cycle
For stable working memory with small changes,
Rete is dramatically faster (used in all production systems)
Inference with Uncertainty
Real-world reasoning involves uncertain knowledge. The inference engine must propagate confidence through rule chains:
Certainty Factors (MYCIN approach)
| Rule | IF symptom_A (CF=0.8) AND symptom_B (CF=0.6) |
| Combined premise CF | min(0.8, 0.6) = 0.6 |
| Conclusion CF | 0.6 × 0.9 = 0.54 |
| Interpretation | 54% confidence in disease_X |
| Example: CF₁=0.6, CF₂=0.7 | 0.6 + 0.7×0.4 = 0.88 |
Forward vs. Backward Chaining Comparison
| Aspect | Forward Chaining | Backward Chaining |
|---|---|---|
| Direction | Data → Conclusions | Goal → Evidence |
| Best when | Many inputs, few goals | Specific hypothesis to test |
| Strategy | Breadth exploration | Focused verification |
| User interaction | Minimal (data-driven) | Asks targeted questions |
| Example systems | CLIPS, OPS5, Drools | MYCIN, Prolog |
| Analogy | "What can I conclude?" | "Is this true?" |
Implementation Architecture
class InferenceEngine:
def __init__(self, knowledge_base):
self.rules = knowledge_base.rules
self.working_memory = set()
def forward_chain(self, initial_facts, goal=None):
self.working_memory = set(initial_facts)
fired_rules = set()
while True:
# Match phase
conflict_set = []
for rule in self.rules:
if rule not in fired_rules:
if all(cond in self.working_memory
for cond in rule.conditions):
conflict_set.append(rule)
if not conflict_set:
break # No rules to fire
# Resolve conflicts (specificity)
selected = max(conflict_set,
key=lambda r: len(r.conditions))
# Execute
self.working_memory.add(selected.conclusion)
fired_rules.add(selected)
if goal and goal in self.working_memory:
return True # Goal achieved
return goal in self.working_memory if goal else TrueReal-World Inference Engines
CLIPS (C Language Integrated Production System)
- Developed by NASA
- Forward chaining with Rete algorithm
- Used in aerospace, manufacturing
Drools (Java)
- Modern business rules engine
- Forward and backward chaining
- Used in banking, insurance, healthcare
Prolog (Programming language)
- Built-in backward chaining
- Unification-based matching
- Used in NLP, expert systems, databases
Interview Questions
Q: When would you use forward chaining vs. backward chaining? A: Forward chaining when you have lots of data and want to see what conclusions emerge (monitoring systems, data interpretation). Backward chaining when you have a specific question to answer (diagnostic systems, verification). Many systems use both: forward chain to derive initial facts, backward chain to prove specific hypotheses.
Q: What is the Rete algorithm's key optimization? A: Rete avoids redundant computation by saving partial match state between cycles. When working memory changes by one fact, only rules potentially affected by that change are re-evaluated. For systems with thousands of rules and stable working memory, this gives orders-of-magnitude speedup.
Q: How does an inference engine handle contradictions? A: Through truth maintenance systems (TMS). When a fact is retracted, the TMS identifies all conclusions that depended on it and retracts them too. Non-monotonic reasoning allows the system to revise beliefs when new evidence contradicts old conclusions.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Inference Engine - Reasoning Core.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, expert, systems, inference, engine
Related Artificial Intelligence Topics