CSCE 883: Test 3


Show your work for every question but make clear which one is the final answer by drawing a box around it. Remember to copy the question number to your answer booklet. In all questions it is critical that you show your work.

  1. [15 points] Use sequential covering with the learn-one-rule to learn a set of rules that can predict the isBird concept from the examples below. Assume an entropy threshold of 0.
    Example # hasBeak laysEggs hasFeathers isBird
    1 T T T T
    2 T T F T
    3 T F F F
    4 T T T T
    5 T F T F
  2. [10 points] Given the set of predicates: Father(x,y), ChildOf(x,y), Niece(x,y), what are the possible specializations (as defined by FOIL) of the rule:

    Niece(x,y) ← ChildOf(x,z)
  3. [15 points] Use inverse resolution to determine what else one would need to know in order to deduce that

    Screams(x) ∧ Runs(Bob) ∧ Giggles(x)

    given that,

    Tickles(x,y) ∧ Screams(x) ∧ Runs(y).
  4. [15 points] Given the domain knowledge:
    and the positive example (for the CanScore target concept)
    you were able to use the domain knowledge to deduce that CanScore is true. What is the weakest pre-image of that deduction?
  5. [10 points] You decide to learn the concept "is in simplest form" over the domain of algebraic equations. That is, given an algebraic equation your program has to decide whether or not the equation is in its simplest possible form. How would you use EBL to solve this problem?
  6. [10 points] You implement the KBANN algorithm with a domain theory that has one incorrect statement in it. What happens when you run the algorithm on a set of examples that contradict the domain theory. The examples are all correct.
  7. [10 points] FOCL is an extension of FOIL. Can the added functionality in FOCL guide the hypothesis-space search in a completely wrong direction? Explain.
  8. [15 points] You have a robot that lives in a 3 by 3 grid world and can move N,S,E,W by one space. Each time the robot moves he loses 2 tokes but can pick up tokens from the the space it reaches. The tokens can be picked up only once. The initial world looks like:
    2 3 10
    5 6 1
    R 2 1
    where R is the robot and the numbers reflect the number of tokens initially in each space. The goal is to end up with as many tokens as possible in the least amount of time. Explain how you would solve this problem with Q-learning and display the first 5 steps of the Q table.

Jose M. Vidal