Quantum Computing Forum

Backward chaining is an inference method used in artificial intelligence (AI), particularly in logic programming and expert systems. It is a goal-driven approach that starts with a goal and works backwards to determine what data or rules need to be satisfied to achieve that goal. This method contrasts with forward chaining, which is data-driven and starts from known facts to infer new facts.

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.

Example:
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.

And the known facts are:

• Fact 1: The patient has a fever.
  Fact 2: The patient has a cough.

Goal: Determine the treatment for the patient.

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.

Treatment for Flu: Since the patient has the flu, according to Rule 3, the treatment is rest and fluids.

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.

Final Conclusion: The patient is diagnosed with the flu and the recommended treatment is rest and fluids.

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.

Logic Programming:

• Languages like Prolog use backward chaining to answer queries by proving the goals based on the given facts and rules.

Game AI:

• Used in strategic decision-making, where the AI needs to evaluate potential moves by working backwards from a desired game state.

Advantages and Disadvantages:
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.

Disadvantages:

• 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.

Conclusion

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.