AI Final Review Questions

The following questions are provided as an aid to preparing for the final exam. The scope of the final exam will vary from year to year, so this list may include some questions on material that we did not cover. If you are in doubt about whether or not you should know something the safest and best strategy to use is to go ahead and learn it. Just think of how much you will end up knowing. You can also check with the TA or instructor.

The exam is cumulative, covering the material from the entire course. Roughly 1/4 of the exam will be drawn from the first half of the course, and the other 3/4 will be drawn from the second half.

Topics covered in the midterm exam

Be sure to review the topics covered in the midterm exam, e.g., Prolog, search and games.

Miscellaneous

Answer the following true/false questions:

Logic

Describe the main differences between propositional logic and first order logic.

Give two propositional logic sentences that are equivalent to P Þ Q.

Modeling in logic

Translate the following statements into a FOPC sentence, choosing appropriate predicates and functions: (a) ``Good food is not cheap and cheap food is not good.''; (b) ``If a computer can beat Kasparov in chess, then a computer can beat anyone''. Rewrite your FOPC sentence as a set of sentences in conjunctive normal form and in implicative normal form.

Evaluating sentences

For each of the following sentences, say whether it is valid, unsatisfiable or either. Verify your assessment using either truth tables or by applying tautologies.

• smoke => smoke
• smoke => fire
• (smoke => fire) => (~smoke => ~fire)
• smoke V fire V ~fire
• (smoke ^ heat) => fire <=> ((smoke => fire) V (heat => fire))
• (smoke => fire) => ((smoke ^ heat) => fire)

Connectives

Consider the four standard binary connectives used in logic: and, or, implies, iff. (a) How many possible binary connectives can we define? (b) give an example of two others which might be useful.

Evaluating sentences

Classify the following sentences as valid, satisfiable or unsatisfiable:

1. " x P(x) Þ $ x P(x)
2. $ x $ y ~Q(x,y) | P(x) Þ Q(x, y)
3. " x P(x)

Unification

For each of the following pairs of predicates, determine if they unify. If so, show the resulting substitution.

1. P(x, y, z) P(A, f(x), f(x))
2. P(y, g(x), h(x)) P(f(u,v), u, h(v)
3. P(f(x),x) P(y,f(y))
4. Loves(Lover(x), Monica) Loves(Bill, Monica)
5. Rel(Loves, x, x) Rel(Loves, Lover(y), y)
6. P(x, f(A,B), y) P(u, f(u, v), u)

Modeling in logic

s(X,L) --- Person X speaks language L. 
c(X,Y) --- Persons X and Y can communicate. 
i(W,X,Y) --- Person W can serve as an interpreter between persons X and Y. 
j,p,e,f --- Constants: Joe, Pierre, English, and French respectively.

• i. Joe speaks English.
• ii Pierre speaks French.
• iii. If X and Y both speak L, then X and Y can communicate.
• iv. If W can communicate both with X and with Y, then W can serve as an interpreter between X and Y.
• v. For any two languages L and M, there is someone who speaks both L and M.
• vi. There is someone who can interpret between Joe and Pierre.

Show that (vi) can be proven from (i)---(v) using backward-chaining resolution. You must show the Skolemized form of each statement, and every resolution that is used in the final proof. You need not show the intermediate stages of Skolemization, or show resolutions that are not used in the final proof.

Resolution theorem proving

Use resolution to prove $ v P(A,v)&Q(A) given the following sentences. Express your proof as a resolution graph, and show substitutions.

• " x Q(x) | S(x)
• " y ~S(y) | T(B)
• " z,w ~T(z) | P(w,z)

Game theory

Prisoner's dilemma

Nash equilibrium

Newcomb's Paradox

Knowledge representation

Planning

Situation calculus

The Prince of Pizza has a magic wand that will turn a frog into a pizza. However, it only works if he is holding the wand, the wand is touching the frog, and he says "Presto." Write a situation calculus description of the Presto action. Use an effect axiom and a frame axiom. Do not use a successor-state axiom.

Representing Actions

1. Write one or more effect axioms in the Situation Calculus that define the action "toggle." Use just one action called Toggle if possible; if not, use more and explain why more are needed.
2. Write a frame axiom that says any object x at any location y remains at that location after toggling any light switch. Use the predicate location/2 in your answer.
3. Write one or more STRIPS-type operators that represent the action "toggle." Use just one operator called Toggle if possible; if not, use more and explain why more are needed.

Wolf, goat, and cabbage

A man has to take a wolf, a goat, and some cabbage from Moscow to Petersburg across a river. His rowboat has enough room for the man plus either the wolf or the goat or the cabbage. If he takes the cabbage with him, the wolf will eat the goat. If he takes the wolf, the goat will eat the cabbage. Only when the man is present are the goat and the cabbage safe from their enemies. Initially, the man, cabbage, goat, and wolf are on the Moscow side of the river. All the same, the man carries wolf, goat, and cabbage across the river.

1. Design a domain description for this problem using the STRIPS representation as discussed in lectures and the homework. You can use variables in the preconditions and effects of operators.
   • Write down the objects used by your domain description
   • Write down the predicates used by your domain description
   • Write down the operator definition (name, preconditions, add list, and del list, conditions) used by your domain description
2. Write down the expression for the initial state
3. Write down the goal expression for the problem above

Partial order planning

Progression and regression

Jess

Jess one

Assume we have unordered Jess facts like the following to represent a person's various income sources:

     (income joeSmith salary 50000)
     (income joeSmith consulting 5000)
     (income joeSmith interest 50)
     (income joeSmith investments -1000)

     (totalincome joesmith 54050)

Jess two

Write a set of Jess expressions (e.g., defrules and deffacts) to model the following sentences. What additional facts would your sentences assert.

     all birds have wings.
     Assume a bird can fly unless you know it can't.
     sparrows are bird.
     penguins are birds.
     Hoppy is a sparrow.
     Tux is a penguin.
     Penguins can not fly.

Jess three

...to be supplied...

Learning

Decision Trees

1. Compute the information gain of using the attribute leg-cover for predicting gender!
2. What is the information gain of using the attribute beard to predict gender?
3. Based on yours answers to (1) and (2) which attribute should be used as the root of a decision tree?
4. What is the "intuitive idea" that underlies ID3's information gain heuristic --- what attributes does it prefer?
5. How can the information gain heuristic that was originally designed for symbolic attributes be generalized to cope with continuous attributes?

Overfitting

Decision trees

You've been hired as the IT person for the newest trendy bar in Canton. Your boss wants to predict how much business they will do so he can ensure she has enough staff and food for the day. She hasn't gathered much data yet, but she still wants you to build a decision model.

(a) Which attribute would be the first one selected when using the ID3 algorithm?

(b) Calculate the information gain for each of the three attributes (DOW, Rainy, Temperature). You need not simplify the formulae.

(c) Construct a decision tree using the ID3 algorithm.

(d) Tomorrow is Wednesday and the outlook is that it will be hot and rainy. What do you tell your boss about how many customers to expect?

(e) The weather prediction for Saturday is that it will be sunny with either a hot or moderate temperature. Your boss is anxious to plan for the weekend and wants your system to work even when the weather predications are uncertain. How could you modify a decision tree to make reasonable predictions even when all of the attributes are not known?

Evaluating learning systems

Explain briefly (2 or 3 sentences) the use of a training set and a test set in evaluating learning programs.

Supervised and Unsupervised learning

Explain the difference between supervised and unsupervised learning.

Ockham’s razor

Ockham’s razor favors some generalizations over others. What is Ockham’s razor and how can it be operationalized? Use decision tree induction as an example to illustrate.

Decision trees

                              Color
                                |
                       -------------------
                   Blue|     Red|   Green|
                       |        |        |
                     Width      No    Height
                  -----------        ---------
              Thin|      Fat|   Short|    Tall|
                  |         |        |        |
                  No       Yes       No      Yes

        New Data:
        Example Color Height Width
        A       Red   Short  Thin
        B       Blue  Tall   Fat
        C       Green Short  Fat
        D       Green Tall   Thin
        E       Blue  Short  Thin

Self organizing systems