Assignment 5 - Forward and Double Inferencer Due

Your assignment consists of two parts, programming and rule writing.

BEGIN INTIMIDATION

This assignment is HARD, please read this entire page first. That way the double inferencer will require little extra programming. Write pseudocode first. No, really.

Students often think that this is a good assignment to skip. They are right except that:

END INTIMIDATION

This is about ten times harder than Eliza. It is also much more fun. Unlike Eliza, you could say that the inferencer actually reasons. It is up for debate.

  1. Write (I mean that you have to write a program) a forward inferencer - a program that will keep making inferences from a set of initial states and actions.

    Example:
    Marko gave assignments to Larry 
    > Larry has assignments, Larry wanted assignments 
    > Larry can give assignments to someone 
    > etc
    
    1. Write the basic program - you need the pattern matcher (the same one used for Eliza) and a queue (it might be easier with two queues, one for old statements and one for new).
    2. Allow the user to specify a depth, that is how many levels of inference before the program stops. In the example above the depth is 2. ("Marko gave assignments to Larry") is not an inference, it was in the queue at the start of the program.
    3. Detect cycles and don't make cyclical inferences.
    4. Detect statements that only have variables (Someone gave something to somebody), and do not inference anything from them.
    5. Make sure that the output of your program consists of a statement, a statement that it was derived from, and the rule name. NOT the rule itself. Give each rule a name. See Sample output below.

      Now save a working version of your program and work on the rules. You can use your table if you want. Rules are important, they are where the "smarts" are. I don't care if you have a great program with stupid rules. On the other hand a stupid program with smart rules will go a long way.

      After you are done with the rules, make the modifications below.

    6. Modify your program and rules so that you can assert more than one statement if the rule fires. For example, do (Marko gave assignments to Larry > Larry has assignments, Larry wanted assignments) with one rule. This is simple.
    7. (optional:Extra Credit, see below) Modify your inferencer so that each statement carries a time tag: past, present, future. The rules should give the correct tags to the statements that are added to the queue. You have to decide which rules change the tags, and which preserve them.
    8. Make your program produce forward inference chains from one statement to another.
    9. Modify the rule data structure so that it indicates which direction in time does the inference go. This is necessary for the double inferencer. You need to make only forward inferences from statement1 and only backward inferences from statement2. I mean forward in time and backward in time. Rules can be :forward, :backward, and :both.
    10. Write a double inferencer. This means that inference needs to go simultaneously in both directions until a link is found.
    11. Write an inferencer that can link three statements in a chain. That's not too hard. Experiment with it. Give me one sample run, and a paragraph that tells what you learned from this experience.

    I hate giving students sample outputs because that stifles creativity, but this assignment is  hard enough, and you deserve some help.

    Example:

    Inference chain from (GIVE ACTOR JOHN OBJECT BOOK FROM JOHN TO MARY)

    to (HAS-POSSESSION ACTOR MARY OBJECT BOOK)

    Output:

    ? (inferencer-double example1-statement1  ;;calling the program with
                         example1-statement2) ;; the names of the two statements

    Checking:
    Queue1...
    checking the first queue and deriving all statements from it

    (GIVE ACTOR JOHN OBJECT BOOK FROM JOHN TO MARY)
    Derived via GIVE-RESULT-POSS rule...
    (HAS-POSSESSION ACTOR MARY OBJECT BOOK)

    Checking:
    Queue2...
    checking the second queue: no statements derived - there is only one rule in my program
    (HAS-POSSESSION ACTOR MARY OBJECT BOOK)

    Link found...

    Inferencer found a link. Now it is going to print all the statements in it in order

    (GIVE ACTOR JOHN OBJECT BOOK FROM JOHN TO MARY)

    GIVE-RESULT-POSS

    (HAS-POSSESSION ACTOR MARY OBJECT BOOK)

    ...........link here............

    (HAS-POSSESSION ACTOR MARY OBJECT BOOK)

    END Example

    This is a chain of only three links hopefully yours will be longer.

    Hints for the double inferencer:

  2. Translate your table into rules and statements that the computer understands
    1. X gives book to Y becomes (GIVE X Y BOOK), and so on
    2. Write rules to implement the relationships in the table. If you do not like your table, you can make new relationships.
    3. You can do the steps a and b in one go.
    4. Write some statements to test your rules. For example, if you have a rule that says if (on radio) then (listen radio). put a statement (radio on) in the queue. Note: you will have to type less if you give your statements names like you did with rules.
    5. Write three pairs of statements to show that your double inferencer works. Make sure that the chains that result from them are at least four long.
    6. Write one triple of statements to test the triple inferencer.

Extra Credit

You have to finish the main assignment before working on the Extra Credit

Time is big a problem.

  1. Modify your inferencer so that each statement carries a time tag: past, present, future. The rules should give the correct tags to the statements that are added to the queue. You have to decide which rules change the tags, and which preserve them.

  2. Really Past, Present, and Future are not enough. After all, if I have the book in the past, Somebody gave it to me  in the past, but it was an earlier past.

    Improve the handling of time. You could for example assign negative integers for past and positive for future. Or invent your own scheme. Make sure that you actually show some inference that your program can make that was not possible before. Otherwise, what's the point of extending the inferencer?

  3. If this is still too easy, handle duration as well.

Extra Credit is a bit more serious this time.

Hand in:

  1. What the submission guidelines say you should (please read them).
  2. Your program
  3. Your rules
  4. Sample run of single inferencer to depth 5.
  5. Three sample runs of double inferencer.
  6. One sample run of the triple inferencer.
  7. If you did Extra credit, give me a sample run and a description.
  8. A summary sheet:

    Please label everything correctly. If you think this assignment is hard, imagine grading them. It is your responsibility to make it clear to me that you handed in everything. Don't start the night before it is due. There are other assignments after this one.

Comments:

I am sure that this is, again, unclear. Post your questions on the newsgroup. (Rule of thumb: If you found an interpretation of this assignment that requires less than four hours of work, it is wrong.)

Have Fun,

ayman