Assignment 2: Inference With Knowledge Using Partial-Order Properties
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Spring 2016
The reading for this assignment is Knowledge Representation in The Elements of Artificial Intelligence with Python.
Due Wednesday, April 13 through Catalyst CollectIt at 11:59 PM.
 
Partnership Option: Although each student should turn in his or her own solutions for Part I (the written exercises), you may work in a partnership for the programming section of the assignment. If you work alone, you are responsible for Part II but not Part III. If you work in a partnership, you should do both Part II and Part III.
Part I. Written Answers (20 points).
  1. Exercise 3 on page 154.
  2. Exercise 4 on page 155.

Part II. ISA Hierarchy Manipulation: Redundancy Handling (80 points if working alone; 40 points if working in a partnerhip). The Python code for a program called Linneus that manages a small knowledge base is available here. Add the features described flow to the Linneus program. Hint 1: Draw graphs of the partial orders corresponding to example and analyze how the graph must change in response to each turn of the conversation. Hint 2: All of the indirect transitivity-related redundancy analysis can actually be handled with one general-case method. Then the textual answers from Linneus can be varied depending on the results of that analysis.
  1. direct redundancy detection (30 points). Have Linneus detect potential "direct'' redundancy in the database. Here the redundancy occurs when the newest user statement is implied by existing facts via transitivity or by the reflexive property of ISA. 
    > A sockeye is a salmon.
I understand.
> A salmon is a fish.
I understand.
> A sockeye is a fish.
You don't have to tell me that.
> OK
I don't understand.
> A spade is a spade.
You don't have to tell me that.
> A sockeye is a salmon.
You told me that earlier.
  2. simple indirect redundancy detection (20 points). Have Linneus detect and remove simple indirect redundancy. Here the newest statement makes an earlier statement redundant because the older statement could now be derived using transitivity. This is a simple case involving only three relevant propositions. 
    > A hawk is a bird.
I understand.
> A hawk is a raptor.  
I understand.
> A raptor is a bird.
Your earlier statement that a hawk is a bird is now redundant.
  3. intermediate indirect redundancy detection (20 points). Have Linneus detect and remove indirect redundancy in which a single earlier statement becomes implied by a chain of three or more statements including the newest one. 
    > A hawk is a raptor
I understand.
> A hawk is an animal
I understand.
> A bird is an animal
I understand.
> A raptor is a bird
Your earlier statement that a hawk is an animal is now redundant.
  4. complex indirect redundancy detection (10 points). Have Linneus detect and remove multiple indirect redundancies in which any number of earlier statements become implied by chains of two or more statements including the newest one. 
    > A chinook is an organism.
I understand.
> A sockeye is a salmon.
I understand.
> A fish is an animal.
I understand.
> A sockeye is an organism.
I understand.
> A chinook is an animal.
I understand.
> A chinook is a salmon.
I understand.
> A sockeye is an animal.
I understand.
> A fish is an organism.
I understand.
> A salmon is a fish.
The following statements you made earlier are now all redundant:
a chinook is an organism;
a sockeye is an organism;
a chinook is an animal;
a sockeye is an animal.
Part III. Qualified Statements and Plausible Arguments (40 points; do this only if you are in a partnership)
Implement a new variation of Linneus.py in a new file PlausibleArguments.py with the functionality described below.
  1. Allow entry of both "unqualified" and "qualified" statements, and handle questions about them. Unqualified statements are those already handled by Linneus such as "A dog is a mammal." And in addition, we will consider statements of the form "Jones is a reliable source." to be unqualified. For this assignment, A qualified statement is one that begins with the form Somebody Says, such as "Johnson says". Here are some examples. 
    > Jones says that an animal is an organism.
I understand.
> Jones says that Smith is a reliable source.
I understand.
> A dog is an animal.
I understand.
> Is a dog a pet?
I have no reason to believe so.
> Is a dog an organism?
It's quite possible that a dog is an organism.
> Is a dog an animal?
Yes.
> Is a an animal an organism?
Jones says that it is.
  2. Add the capability to handle two styles of Why questions. In the first style, the input is a full sentence. In the second style, the question consists only of the word "Why" and a question mark. The following example assumes the previous example was just run. 
    > Jones is an unreliable source.
I understand.    
> Why is it possible that a dog is an organism?
Because a dog is definitely an animal,
and Jones says that an animal is an organism.
However, Jones is an unreliable source,
and therefore we cannot be certain about this chain of reasoning.
Extra Credit Options
Those working alone may opt to do cycle-detection and elimination in the graph of statements for 10 points of extra credit.
Those working a partnership may opt to extend their PlausibleArguments.py program in several ways for 10 points of extra credit.
  1. Cycle Detection and Elimination. Because the ISA relation is a partial order, it must obey the antisymmetry property, which states that if x R y and y R x, then x = y. Because of transitivity, this means than in any cycle, such as a R b, b R c, and c R a, it must be the case that a = b = c. When the user inputs statements that form such a cycle, your program should detect that a cycle would be formed by the latest statement, if processed normally. It should report that to the user and then perform the following changes to the database: Determine which node is the starting point in the cycle (for example x when x R y and y R x are input in that order). Make all the other nodes in the cycle become "aliases" of the starting node, and merge them into the starting node. That means any edge involving one of these nodes has one of its endpoints replaced by the starting node. The program should be able to use the aliases in further interactions. An example is given below. 
    > A creature is a being.
I understand.    
> A being is a living-thing.
I understand.    
> A living-thing is a creature.
I infer that creature, being, and living-things are all names
for the same thing, and I'll call it creature.
> A bug is a creature.
I understand.
> Is a bug a being?
Yes.
> Why is a bug a being?
Because a bug is a creature, and being is another name for creature.
> A living-thing is an organism.
I understand.
> Is a bug an organism?
Yes.
> Why is a bug an organism?
Because a bug is a creature, and a creature is an organism.
  2. For 10 points in a partnership, do at least one of the three extensions suggested plus one of the two fictional "applications". Extension suggestions for PlausibleArguments.py:
    1. a. Allow for more degrees of reliability/unreliability of sources. e.g., "Jones is somewhat reliable."
    2. b. Allow for more qualification in statements: e.g., "Jones says that an animal is probably an organism."
    3. c. Allow more complex argument building. 
      It's possible that a dog is an organism.
Why?
Because we have two chains of plausible reasoning to support it:
First, Smith says a dog is a pet, and Smith also says a pet is an animal, and then
Jones says that an animal is probably an organism;
second, I was told on good authority that a dog is a mammal and a mammal is an animal,
and then Bates says an animal is a living-thing and that a living-thing is an organism.
    Give an example of a session for a fictional application. The following two scenarios are intended to stimulate your imagination. You may choose to use either one, or to make up an application completely your own. The example should effectively show off the features of your enhanced program.
    • A. cancer investigation in which several scientists make claims about what kinds of viruses are what, and finally an argument is given that a melanoma-virus belongs to a certain class of viruses. It doesn't have to be viruses, but could be categories of "illnesses" on an alien planet.
    • B. crime investigation where different detectives make claims about what kind of crime it was or what type of criminal it was ... various types of psycopaths, perhaps. The computer then answers questions about plausible classifications for the type of crime committed or the type of perpetrator. This doesn't have to be about human-committed crimes; it might be about robot-committed crimes or accidents.
What to Turn In

Each student should Turn in a file PartI.txt. At the beginning of that file, state whether you are working alone or in a partnership of two. If you are in a partnership, the name of your partner should be given there, too.
If you are working alone, turn in your file PartII.py. If you are in a partnership, and your last name comes alphabetically before that of your partner, turn in your PartII.py file and your file PlausibleArguments.py for Part III. Your PartI.txt file should contain your name and the answers to the questions in Part I. Your PartII.py file should begin with a multiline string that gives, on the first line, your name, and on the next four lines, the status of your solutions to the Part II and Part III requirements, and then an indication of which extra-credit options you did, if any. Here is an example. 

'''PartII.py
John Doe, CSE 415, Spring 2016, University of Washington
Instructor:  S. Tanimoto.
Assignment 2 Part II.  ISA Hierarchy Manipulation

I have worked alone (no partner).

Status of the implementation of new features:

All forms of redundancy detection and processing are working.
Extra credit (Cycle detection and processing) implemented and working.


'''

The rest of your file PartII.py should contain a version of the Linneus program that provides the implementation of the features according to your status comments.

Updates and Corrections

If necessary, substantial updates and corrections will be posted here and mentioned in class or on GoPost.