International Journal of Emerging Technology and Advanced Engineering Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 10, October 2012)
STUDY OF DIFFERENCE BETWEEN FORWARD AND BACKWARD REASONING Tilotma Sharma1, Navneet Tiwari2 and Deepali Kelkar3 1
M.Tech (IT), Mahakal Institute of Technology, Ujjain M.Tech (IT) 2 MCA Department, Mahakal Institute of Technology and Science, Ujjain 3 HOD CS/IT, Mahakal Institute of Technology and Management. Ujjain When found it can conclude, or infer, the THEN clause, resulting in the addition of new information to its dataset. In other words, it starts with some facts and applies rules to find all possible conclusions. Therefore, it is also known as Data Driven Approach [1].
Abstract - In artificial intelligence, an expert system is a computer system that emulates the decision making ability of a human expert. Expert systems are designed to solve complex problems by reasoning about knowledge, like an expert, and not by following the procedure of the developer as is the case in conventional programming. An expert system has a unique structure. It is divided into two parts, one fixed, independent of the expert system: the inference engine, and one variable: the knowledge base. To run an expert system, the engine reasons about the knowledge base like a human.
Flowchart of Forward Chaining:
Keywords - Artificial Intelligence, Expert system, inference engine, knowledge base, reasoning method
I.
INTRODUCTION
The inference engine is a computer program designed to produce reasoning on rules. In order to produce reasoning, it should be based on logic. With logic, the engine is able to generate new information from the knowledge contained in the rule base and data to be processed. The engine has two ways to run: batch or conversational. In batch, the expert system has all the necessary data to process from the beginning. For the user, the program works as a classical program: he provides data and receives results immediately. Reasoning is invisible. The conversational method becomes necessary when the developer knows he cannot ask the user for all the necessary data at the start, the problem being too complex. The software must "invent" the way to solve the problem, request the missing data from the user, gradually approaching the goal as quickly as possible. The result gives the impression of a dialogue led by an expert. To guide a dialogue, the engine may have several levels of sophistication: "forward chaining" and "backward chaining". II.
Fig 1: Flowchart of Forward Chaining
The standard definition of a forward-chaining system is that the system operates by repeating the following sequence of operations [2] (shown in Fig1): 1. Examine the rules to find one who’s If part is satisfied by the current contents of Working Memory. 2. Fire the rule by adding to Working Memory the facts that are specified in the rules Then part. (The Then part may perform other actions as well, but that can be ignored for now.) This control cycle continues until no rules have satisfied If parts.
FORWARD CHAINING
An inference engine using forward chaining searches the inference rules until it finds one where the IF clause is known to be true.
271
International Journal of Emerging Technology and Advanced Engineering Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 10, October 2012) III.
ii. If the condition is known to be unsatisfied, continue with the loop at Step 2. iii. If it was not possible to determine whether the condition was satisfied, continue with the loop at Step 2. b. If all the conditions in the selected rule are satisfied, add to Working Memory the facts specified in the Then part of the rule, pop the goal off the stack, and return from this invocation of the system. The system terminates with success when the goal stack is empty. It terminates with failure if the system runs out of rules to try in Step 2.
B ACKWARD CHAINING
An inference engine using backward chaining would search the inference rules until it finds one which has a THEN clause that matches a desired goal. If the IF clause of that inference rule is not known to be true, then it is added to the list of goals (in order for goal to be confirmed it must also provide data that confirms this new rule) [4]. In other words, this approach starts with the desired conclusion and works backward to find supporting facts. Therefore, it is also known as Goal-Driven Approach. Flowchart of Backward Chaining:
IV.
COMPARISON B ETWEEN FORWARD AND B ACKWARD CHAINING 1)
2)
3)
4)
Fig 2: Flowchart of Backward Chaining
5)
Backward-chaining systems try to satisfy the goals in the goal stack. They do this by finding rules that can conclude the information needed by the goal, and trying to make the If parts of those rules satisfied [6]. In more detail, the standard backward-chaining control cycle is (shown in Fig2): 1. Check the conclusions of the rules to find all rules that can satisfy the top goal on the stack. 2. Process these rules one at a time: a. Evaluate the conditions in the rules If part one at a time: i. If the condition is currently unknown (that is, if there is not enough information currently known to determine whether the condition is satisfied) push a goal to make that condition known, and recursively invoke the system.
6)
7)
272
The exploration of knowledge has different mechanisms in forward and backward chaining. Backward chaining is more focused and tries to avoid exploring unnecessary paths of reasoning. Forward chaining, on the other hand is like an exhaustive search [3]. Backward chaining systems are good for diagnostic and classification tasks, but they are not good for planning, design, process monitoring, and quite a few other tasks. Forward chaining systems can handle all these tasks. Forward chaining system, includes writing rules to manage sub goals. Whereas, backward chaining systems automatically manage sub goals [7]. Lots of output Hypothesis + Lots of data up front => Use Forward Chaining Fewer output Hypothesis + Must query for data=> Use Backward Chaining Backward chaining engines query for new facts, whereas forward chaining relies on the application asserting facts to the rule engine. In backward chaining, the search is goal directed, so rules can be applied that are necessary to achieve the goal. But in forward chaining the whole process is not directed towards goal, so when to stop the rules in not known [5]. If the facts that has to be established lead to a large number of conclusion, but the number of ways to reach that particular conclusion is small, then there is more information out rather than information in, then backward chaining should be used. On the other hand, if the number of ways to reach a particular conclusion is large, but the number of conclusions likely to be reach using the facts is small, then forward chaining is preferred.
International Journal of Emerging Technology and Advanced Engineering Website: www.ijetae.com (ISSN 2250-2459, Volume 2, Issue 10, October 2012) V.
CONCLUSION
REFERENCES [1 ] RC Chakraborty, Expert Systems, Artificial Intelligence, June 01, 2010. [2 ] George Luger, William Stubblefield, Artificial Intelligence, Structures and Strategies for Complex Problem Solving, Third Edition Addison-Wesley, 1998 [3 ] Knut Hinkelmann, Forward Chaining Vs Backward Chaining, University of Applied Sciences Northwestern Switzerland, School of Business, 2004 [4 ] Donna Kay, A Comparison of Forward and Backward Chaining Algorithms For use in a Technical Support Expert System Used for Diagnosing Computer Virus Issues, April 9th, 2009 Computer Science Department California State University, Chico. [5 ] John A. Bullinaria, IAI: Production Systems, 2005. [6 ] Alan Holland, Rule Based Systems, University College Cork, Mar 2010. [7 ] Alison Cawsey, Forward and Backward Chaining, Department of Computing and Electrical engineering, Heriot-Watt University, Edinburgh, UK.
Unfortunately, the only way to know how a rule will behave is to profile it and understand the business case. Many people make the mistake of thinking a rule engine will magically solve their problems. Writing high performance rules is not easy or intuitive. The best way to build efficient applications using rule engines is to take the time to learn how each approach works and use both techniques. Although it increases the learning curve, the choice between forward and backward chaining isn't something that can be summed up in 2-3 sentences. It's crucial to consider the intent of the rule, size of the dataset and performance requirements. Table1 Comparative Study
Attribute
Backward Chaining Goal-driven
Forward Chaining Data-driven New data
Processing
Possible conclusion Efficient
Aims for
Necessary data
Approach
Conservative/Cauti ous Number of possible final answers is reasonable or a set of known alternatives is available. Diagnostic, prescription and debugging application
Also known as Starts from
Practical if
Appropriate for
Reasoning Type of Search Who determine search Flow
Top-down reasoning Depth-first search Consequents determine search Consequent antecedent
to
Somewhat wasteful Any Conclusion(s) Opportunistic Combinatorial explosion creates an infinite number of possible right answers. Planning, monitoring, control and interpretation application Bottom-up reasoning Breadth-first search Antecedents determine search Antecedent to consequent
273
