1. Concept:
Backward chaining begins with a hypothesis or goal and attempts to prove it by recursively breaking it down into sub-goals and determining if there are rules or facts in the knowledge base that support these sub-goals. If a sub-goal matches a known fact or can be derived from other sub-goals, it is considered proven. This process continues until the original goal is proven or disproven.
2. Mechanism:
- Goal Selection: The process starts with selecting a goal that needs to be proved.
Rule Matching: The system searches for rules in the knowledge base where the consequent (then-part) matches the goal.
Sub-goal Creation: For each matching rule, the antecedents (if-parts) are treated as new sub-goals.
Recursive Proof: The system recursively attempts to prove these sub-goals, applying the same process to them.
Fact Checking: If a sub-goal matches a known fact, it is considered proven.
Backtracking: If a sub-goal cannot be proven, the system backtracks to try alternative rules or goals.
Consider a simple expert system for medical diagnosis. Suppose we have the following rules in the knowledge base:
- Rule 1: If the patient has a fever and a cough, then the patient has the flu.
Rule 2: If the patient has a fever and a rash, then the patient has measles.
Rule 3: If the patient has the flu, then treat with rest and fluids.
Rule 4: If the patient has measles, then treat with isolation and vitamin A.
- Fact 1: The patient has a fever.
Fact 2: The patient has a cough.
Step-by-Step Backward Chaining Process:
- Select Goal: The initial goal is to determine the treatment for the patient.
Match Rule: Look for rules that provide a treatment. Rules 3 and 4 are candidates.
Sub-goal Creation: For Rule 3, the sub-goal is to prove the patient has the flu. For Rule 4, the sub-goal is to prove the patient has measles.
Prove Sub-goal (Flu):
- Match Rule for Flu: Rule 1 states that the patient has the flu if they have a fever and a cough.
Create Sub-goals for Rule 1: Sub-goals are to prove the patient has a fever and the patient has a cough.
Check Facts: Both sub-goals match known facts (Fact 1 and Fact 2).
Conclusion: The sub-goals are proven, so the patient has the flu.
Alternative Path (Measles):
- Match Rule for Measles: Rule 2 states that the patient has measles if they have a fever and a rash.
Create Sub-goals for Rule 2: Sub-goals are to prove the patient has a fever and a rash.
Check Facts: The patient has a fever (Fact 1), but there is no fact supporting a rash.
Conclusion: The sub-goal for measles cannot be proven due to lack of evidence for a rash.
Applications of Backward Chaining:
Expert Systems:
- Used in medical diagnosis systems, troubleshooting systems, and other domains where decision-making is based on rules and knowledge bases.
- Languages like Prolog use backward chaining to answer queries by proving the goals based on the given facts and rules.
- Used in strategic decision-making, where the AI needs to evaluate potential moves by working backwards from a desired game state.
Advantages:
- Efficiency: Only explores relevant parts of the knowledge base, making it efficient for specific queries.
Focus on Goals: Directly focuses on proving or disproving specific goals, which is useful for diagnostic and decision-making tasks.
- Dependency on Knowledge Base: Effectiveness is heavily dependent on the completeness and accuracy of the rules and facts in the knowledge base.
Complexity with Large Systems: Can become complex and less efficient with very large or highly interconnected knowledge bases.
Backward chaining is a powerful inference technique in AI that starts with goals and works backward to find supporting evidence in the knowledge base. It is particularly useful in expert systems and logic programming where goal-driven reasoning is needed. By systematically breaking down goals into sub-goals and matching them against known facts and rules, backward chaining helps AI systems make informed decisions and derive logical conclusions.