Forward and Backward Chaining in AI

Introduction to the Expert System

An expert system is a subject wherein Artificial Intelligence generates the behavior and judgment of a person or a group of specialists. It obtains vital information from its knowledge base and interprets it by the user's problem. The knowledge base's data is primarily contributed by humans who are specialists in a specific subject. Non-experts, on the other hand, use applications to gather knowledge. It is used in medical diagnostics, budgeting, coding, entertainment, and other fields.

An expert system, when broken down, is AI software that utilizes information stored in a knowledge base to address problems. This usually necessitates the use of a human expert, so it aims to keep the expertise of humans in its knowledge base. As a result, expert systems are computer software designed to solve complex problems in a specific domain at a higher level of human intellect and expertise.

Expert systems have five components:

• Knowledge Base: In an expert system, the knowledge base reflects information and rules. It includes information on particular domains as well as rules for solving issues and forming procedures about the domain.

• Inference Engine: The inference engine's most fundamental purpose is to obtain pertinent information from the knowledge base, analyze it, and discover a solution to the user's problem. Inference engines are also capable of explaining and troubleshooting.

• Knowledge acquisition and learning module: The purpose of this component is to make it possible for expert systems to gather more information from different resources and record it in the knowledge base.

• User Interface: This component is required for a non-expert person to communicate with the expert system and discover answers.

• Explanation module: This section, as the name implies, assists in giving the user a summary of the reached conclusion.

Inference Engine

The first stage in understanding the fundamentals of Forward Chaining and Backward Chaining in AI is to comprehend the Inference Engine, which employs these two methods of thinking.

It is an integral part wherein logical rules are implemented to the knowledge base to obtain new information or make a choice, as described in the preceding part. The inference engine employs backward and forward chaining methods as strategies for suggesting answers or deriving knowledge in the expert system.

A. Horn Clause and Definite Clause

Sentence forms like the definite and horn clauses allow knowledge bases to use more specialized and effective reasoning algorithms. Forward and backward chaining methods are used by logical inference engines, which require a knowledge base in the form of a first-order definite clause.

Definite clause: A definite clause, also known as a strict horn clause, is a clause that is a disjunction of literals with precisely one affirmative literal. An example of a Definite clause could be "A cat eats the fish."

Horn clause: A horn clause is a sentence that is a disjunction of literals that includes no more than one affirmative literal. As a result, all of the definite clauses are horn clauses.

B. Forward Chaining

i. What is forward chaining?

When utilizing an inference engine, forward chaining is indeed referred to as forward deduction or forward reasoning. Forward chaining is a type of reasoning in which atomic clauses in a knowledge base are used to retrieve more data in the forward path using inference principles (Modus Ponens).

Before deriving new information, the inference engine evaluates current data, derivations, and conditions in this sort of chaining. The manipulation of information in the knowledge base results in the achievement of an objective (goal).

Forward chaining may be employed for application planning, monitoring, management, and interpretation.

ii. Properties of forward chaining

• It follows a down-up strategy, going from bottom to top.
• It is the process of reaching a decision based on known facts or information, beginning with the initial state and progressing to the target state.
• The forward-chaining method is also known as data-driven because we achieve our objective by employing available data.
• The forward-chaining method is widely used in expert systems such as CLIPS, business rule systems, and manufacturing rule systems.

Before delving further into the chaining illustration, let us first understand the preprocessing that must be performed on the provided sentences to implement forward chaining, and that preprocessing is as follows:

1. Change the clauses to First Order Predicate Logic.
2. Distinguish truths from generated clauses.
3. Make note of what we need to establish at the end.

iii. Examples of forward chaining

Some Fact:

1. It is a crime for Indians to give weapons to enemies of India.
2. Country XYZ is an enemy of India
3. XYZ has some Nuclear warheads
4. All Nuclear warheads were sold to XYZ by Rajiv
5. Rajiv is Indian
6. A nuclear warhead is a weapon

Goal:

Rajiv is criminal

iv. Facts Conversion into FOL

Facts Conversion into First-Order Logic

Step 1: It is a crime for Indians to give weapons to enemies of India.

FOL: Indian( P ) ^ Weapon( Q ) ^ Enemy( R ) ^ Sells( P, Q, R ) → Criminal( P )

Step 2: Country XYZ is an enemy of India

FOL: Enemy( XYZ, India )

Step 3: XYZ has some Nuclear warheads

FOL: Owns( XYZ, x ) Nuclear warheads( x )

Step 4: All Nuclear warheads were sold to XYZ by Rajiv

FOL: Nuclear warheads( x ) ^ Owns( XYZ, x ) → Sell( Rajiv, x, XYZ )

Step 5: Rajiv is Indian

FOL: Indian( Rajiv )

Step 6: A nuclear warhead is a weapon

FOL: Nuclear warhead( x ) → Weapon ( x )

v. Forward chaining proof

Iteration 1:

1. Begin with the knowledge base and well-known facts: The facts that cannot be inferred from any other (represented in the LHS of the clauses)

   

2. To join the connections, add inferences one at a time.

   • As Rule (1) does not fulfill the, it is unlikely to be incorporated.
   • Rules (2) and (3) FOL have already been incorporated.
   • Rule (4) corresponds to the conclusion, so we will include it.

   

   • Rule(5) lacks RHS, therefore nothing would be incorporated.
   • Rule (6) has a weapon in RHS that is taken from Nuclear Warhead(x), which has already been a component, so we will include a weapon in the following state.

   

This wraps our first iteration

Iteration 2:

As we can see from the first iteration, Rule(1) meets all of the LHS requirements. So now that we have all four FOL in LHS, we can put Criminal(x) from RHS into the following stage.

We concluded that Rajiv is a criminal.

Hence proved!

vi. Advantages

• It may be employed to reach several inferences.
• It serves as a solid foundation for drawing inferences.
• It is more adaptable than backward chaining since the data generated from it is not limited.

vii. Disadvantages

• Forward chaining can be a time-consuming procedure. Eliminating and synchronizing available info may take a long period.
• The interpretation of facts or findings for this form of chaining is not as obvious as it is for backward chaining. The former employs a goal-driven approach that yields quick results.

C. Backward chaining

i. What is backward chaining?

Backward Chaining, also known as backward reasoning, is an inference engine reasoning method that begins with an imagined objective. It employs backtracking to discover the most optimum method for dispute resolution or to achieve the target state, in which the search begins from the outcome and travels back to comprehend the circumstances from which it came.

Inference engines use this reasoning method to discover the circumstances and rules that led to a logical outcome or conclusion.

ii. Properties of backward chaining

The following are the main traits that distinguish backward chaining from forward chaining:

• It is referred to as a top-down strategy.
• Backward chaining is founded on the law of modus ponens reasoning.
• Backward chaining divides the objective into sub-goals to demonstrate the truth of the facts.
• A goal-driven strategy is used because a list of objectives determines which rules are chosen and used.
• The backward-chaining method is used in game theory, automatic theorem-proving techniques, inference engines, prove assistants and other artificial intelligence uses.
• For evidence, the backward-chaining technique mostly employed a depth-first search strategy.

Before going any further with the chaining example, let's first comprehend the algorithm that needs to be applied to the given phrases to apply backward chaining:

1. First, the system checks the information base to see if the objective has been stated.
2. If not, it scans the knowledge base for rules until it finds one with the objective in its THEN portion in the shape of premises.
3. Once the hypotheses are specified and recognized, the system checks to see if they are in the knowledge base; if not, a new objective is set. This new objective is known as a sub-goal to be proven.
4. The system repeats the above stages until it discovers the premise that's not given by any regulation. It is referred to as a primitive premise.
5. Finally, when the system locates the primitive, it prompts the user for additional data, which is employed to establish both the sub-goal and the initial goal.

iii. Examples of backward chaining

Some Facts:

1. Ravi enjoys a wide variety of foods.
2. Banana are food.
3. Pizza is food.
4. A food is anything that anyone consumes and isn't harmed by.
5. Sam eats Idli and is still alive.
6. Bill eats everything Sam eats.

Goal:

Ravi Like Idli

Conversion into FOL:

The first sentence can be expressed as follows: ∀x Food ( x ) -> Likes ( Ravi, x )

The second sentence can be expressed as follows:: Food ( Banana )

The third sentence can be expressed as follows:: Food ( Pizza )

The fourth sentence can be expressed as follows:: ∀x ∀y Eats(x, y) ^ ¬ Harmed(y) -> Food(x)

The fifth sentence can be expressed as follows:: Eats ( Idli, Sam ) -> ¬ Harmed ( Sam )

The sixth sentence can be expressed as follows:: ∀x Eats ( x, Sam ) -> Eats ( x, Bill )

iv. Backward-Chaining proof

Iteration 1:

Separation of Facts:

• Food ( Banana )
• Food ( Pizza )
• Eats ( Idli, Sam ) -> ¬ Harmed ( Sam )

Iteration 2:

1. We must regard the statement we must establish to be true, i.e. Likes ( Ravi, Idli ) is now true.

2. We can deduce from the first rule that Food ( Idli ) is true.

3. We can deduce from the fourth rule that Eats ( Idli, Ravi ) -> ¬ Harmed ( Ravi ) is true.

We demonstrated that the assertion we wished to prove is legitimate because we ended up with all of the statements being true.

Hence Proved!

v. Advantages

Backward Chaining, like Forward Chaining, has several advantages, a few of which are listed below:

• The problem typically begins by developing a hypothesis and afterward determining whether or not it can be proven.
• Because it is concentrated on a specific objective, it only employs parts of the knowledge base that are pertinent to the hypothesis.
• It is appropriate for issues requiring an expert system for diagnosis, prescribing, and troubleshooting.
• Backward chaining is a faster procedure because it only analyses and verifies the necessary rules.

vi. Disadvantages

Backward Chaining is an immensely helpful reasoning method that conducts task analysis swiftly and effectively assists the system in reaching the target state. However, this method has a few disadvantages, including:

• It may pursue a specific line of reasoning and inquiry even if it demonstrates to be impractical in the end.
• Backward chaining can be difficult to execute at times.

Differences Between Forward and Backward Chaining

The following is the distinction between forward and backward chaining:

• As the name implies, forward chaining begins with known facts and moves forward by implementing logical rules to extract more information, and it keeps going until it reaches the objective, whereas backward chaining begins with the goal and moves backward by implementing logical deduction rules to evaluate the information that satisfies the objective.
• Backward chaining is a goal-driven inference method, whereas forward chaining is a data-driven inference technique.
• Forward chaining is referred to as the down-up method, whereas backward chaining is referred to as the top-down approach.
• Backward chaining employs a depth-first search strategy, whereas forward chaining employs a breadth-first search strategy.
• Both forward and reverse chaining use the Modus ponens reasoning rule.
• Forward chaining is useful for tasks like planning, design process tracking, diagnostic, and categorization, whereas backward chaining is useful for tasks like categorization and diagnosis.
• Forward chaining can be compared to a comprehensive search, whereas backward chaining attempts to prevent unnecessary thinking paths.
• Forward-chaining may include multiple ASK questions from the information source, whereas backward chaining may include fewer ASK questions.
• Forward chaining is slow because it tests all of the rules, whereas backward chaining is quick because it only examines the rules that are needed.