BBESS - The Basic Inference Algorithm.

 

The algorithm is described in levels, with the steps of each level described in greater detail at the next lower level.  Look here for a much more detailed description of the algorithm.

 

Top Level SetUp

w Read rules and prompts from a file

     v Store as global variables, e.g., *rules*; *prompts*

w Set any other global values, as necessary

 

User Interface Level  {This runs in a continuous loop}

w Set fact base to nil

     v Assume we know nothing about the plant in question

          X Note: This is not a feature of all expert systems.  We accept this with our

                   system for the sake of simplicity of design.

w Ask for user input

w Process user input

    v If input is a valid query

          X Send query to Inference Engine

          X Receive answer from Inference Engine

          X Display answer to user

    v Otherwise

          X If input indicates termination, exit the program

          X Otherwise, signal invalid input and try again

 

Inference Engine: Top Level

w Receive a query

    v This may originate with the user

    v Or it may be generated at a lower level by the inference engine itself

          X Note: At the very beginning the process starts with a query sent from the user

                   interface

w Attempt to answer that query

w Send answer back to point of origination

 

Attempt to answer a query

w Look in fact base for answer

w If query (attribute) is observable, prompt user {Tryprompting}

          X Note: Simplicity of design is gained if the prompting function is called,

                   giving the responsibility of determining observability to next level.

w Carry out inferencing process

 

Look in fact base for answer

w Since query is in the form of an attribute check attribute part of all AV-pairs in fact

   base for a match.

          X Note: This can be done easily with the member function.

      v If a match is found, return the value part of the AV-pair.

      v Otherwise, signal failure

          X Note: Usually this is done by returning nil.

 

Background to Try Prompting

w Here is a typical prompt

    (stem "Is the stem of the plant WOODY or GREEN?" (woody green))

w Notice that it is a triple

      v first: attribute

      v second: prompt string, wherein the valid responses are all upper case

      v third: set of valid responses

w Although member is not a direct help as it was for the fact base, it turns out that when

    we use a special feature of member it can be used in this context.

      v Type in the Lisp forms below:

        (defun matches-first (elt list) (eq elt (first list)))

        (setf x ‘a)

        (setf y ‘(a b c))

        (setf z ‘((e f g)(a b c)(r s t)))

        (matches-first x y)

        (member x z :test #’matches-first)

      v Notice that member is a very general function. 

          X It allows the user to specify the membership test.

          X Thus, it not only tests a list to see if a certain element is a member.  It also

              tests for presence in the list of an element meeting certain criteria specified by

              the function named by :test.

      v With this in mind, try your hand at writing code to look for a prompt matching a

          given query (attribute).

         

Try Prompting

w Check the set of prompts to find a prompt for the given query

w If there is none, return nil.

w If there is such a promt:

      v Print prompt string

      v Receive user response

      v If response is valid

          X Create a new fact

              Y query (attribute) + response (value) = fact (AV-pair)

          X Place it into the fact base

          X Return the value part (response)

w Note: Lisp allows you to combine these actions

      v Assignment: Try your hand at writing the function putinfb

          X It takes two arguments, an attribute and a value

          X It combines these into a list and places that list into the fact base

              Y If the fact base is a global variable, e.g., *fb*

                   T cons the fact onto *fb*

                   T setf *fb* to the result of the cons

          X It returns the value

              Y Remember: To return a value, no return statement is needed; Lisp

                   automatically returns the last Lisp form evaluated

              Y Question: How do you cause the return of a value already bound to a

                   variable?

         

Try Inferencing

w Find all rules whose conclusion contains the query as an attribute of the AV-pair

    v Example: If the query is type, then the rule: ((stem green)(type herb)) contains

          type in its conclusion, since its conclusion is (type herb).

w Test the rules one by one

    v Check the premises of the rule

          X If the premises are all true, draw the conclusion

          X If a premise is not true, discard the rule; try the next one

w If no rule can be found whose antecedent is true; signal failure

    v Treat this as a special case

          X Normally, we signal failure by returning nil.

          X But this is the end of the line, and the user is waiting for an answer

          X Note: Lisp treats a string as an atom

              Y Therefore, if we return a message, such as “Sorry, rule base is incomplete”

                    it will be forwarded to the user, if the round of inferencing originated with

                   the user.

              Y What if it did not?

                   T Assignment: Determine the effect of returning such a message to the

                       inference engine itself.

 

Check the premises {a recursive function}

w If there are no premises, return true ( t ) because all premises were true

w Otherwise

    v Call checkprem to check first premise

          X If answer is nil (indicating premise is false), return nil.

          X Otherwise return answer given by recursive call to itself

 

Check one premise

w Issue a query to the inference engine

          X Note: This is a case of indirect recursion

    v I.e., send the attribute part of the AV-pair (which is the premise) as the query

w When an answer returns, check it against the value part of the AV-pair

    v If there is a match, the premise is true: return t

    v Otherwise, the premise is false: return nil