Chapter 7


Inference engine performs 2 major tasks:
          1) examines existing facts and rules and adds new facts when possible
          2) decides the order in which inferences are made.

    We shall look at  Inference and Control


    Infer means " to derive as a conclusion from facts or premises".
    There are 2 common rules for deriving new facts from rules and known facts.These are
    Modus Ponens and Modus Tollens    


      An inference engine should be able to handle incomplete information. The degree of certainity is represented as a number of attached to a fact (certainty factor).
     There are three inferencing methods. These are Forward,Backward and Mixed Chaining.


   Forward Chaining(Example 1)
Problem: Does situation Z exists or not ?
      The first rule that fires is A->D because A is already in the database. Next we infer D. Existence of C and D causes second rule to fire and as a consequence F is inferred and placed in the database. This in turn, causes the third rule F?B->Z to fire, placing Z in the database.
      This technique is called forward chaining.
 A very simple Forward chaining Algorithm
        Given m facts F1,F2,....,Fm? N RULES
             for i ?- 1 to n do
                if one or more current facts match the antecedent of Ri then
             1 ) add the new fact(s) define by the consequent
             2 ) flag the rule that has been fired
             3 ) increase m
       until no new facts have been produced.

     Forward Chaining (Example 2)



 Backward Chaining (Example 1)       Backward Chaining(Example 2)

      In such a situation backward chaining might be more cost-effective.With this inference method the system starts with what it wants to prove, e.g.,that situation Z exists, and only executes rules that are relavent to establishing it.Figure  following shows how bacward chaining would work using the rules from the forward chaining example.
      In step 1 the system is told to establish (if it can) that situation Z exists,It first checks the data base for Z,and when that fails, searches for rules that conclude Z,i.e., have Z on the right side of the arrow.It finds the rule F?B->Z, and decides that it must establish F and B in order to conclude Z.

      In step 2 the system tries to establish F, first checking the data base and then finding a rule that concludes F. From this rule, C?D->F, the system decides it must establish C and D to conclude F.

      In steps 3 through 5 the system finds C in the data base but decides it must establish A before it can conclude D. It then finds A in the data base.

      In steps 6 through 8 the system executes the third rule to establish D, then executes the second rule to establish the original goal, Z.The infenece chain created here is identical to the one created by forward chaining. The difference in two approaches hinges on the method in which data and rules are searched.


  Mixed  Chaining (Example)
  R1. IF F and H then K           }   Suppose R1-R3 are
  R2. IF E and A then K           }   backward chaining
  R3. IF E and B then H           }

  R4. IF A and G then B          }  R4-R8
  R5. IF B and D then H          }  are forward chaining
  R6. IF G and D then E          }
  R7. IF A and B then D          }
  R8. IF A and C then G          }

  1) Mixed Chaining with priority to backward chaining
      only resort to forward chaining when unable to backward chaining
        Assume working memory has {A,C} ?goal to determine K.

    B    B                         B

 2) Mixed Chaining with priority to forward chaining
     some rule -set and goal and facts
   Result: 9 steps v.s +steps

   There are two problems addressed by the inference engine:

    1 ) It must have a way to decide where to start.Rules and facts reside in a static knowledge base. There must be a way for the reasining process to begin.
    2 ) The inference engine must resolve conflicts that occur when alternative links of reasining emerge,The system may reach a point where there are more than a few rules ready to fire. The inference engine must choose which rule to examine next.


       - most complicated than others
       - because it requires that each fact in the fact set is supplemented with a time tag , (or
      - a unique number indicating the "time" the fact was derived.
      Ex :
           Consider the following fact set
            t1 : x=a,
            t2 : x=b,
            t3 : y=c,
            t4 : z=d

      x occurs twice at time t1 has taken value a and at time t2 obtained the value b.

back home for

This page is maintained by: 
Mehmet R.TOLUN tolun@ceng.metu.edu.tr 
Last updated at: