Artificial Intelligence: Problem Set 5

Assigned: Mar. 28
Due: April 11

Problem 1

Consider the following game: On each turn, you pay an ante of $1, and you roll a die. If it comes up heads, you get back $10 and the game is over (you do not also get back your ante in addition). If the coin comes up tails, you may take another turn. You can quit the game at any time.

Problem 2

Suppose that we are trying to learn a relation R(a,b,c,d) over four integer-valued parameters a,b,c,d. We conjecture that R is either an inequality of one of the forms "X > Y", "X > = Y" or "X = Y", or R is the conjunction of two such inequalities. No more than two inequalities will be considered. Thus, some of the elements of the version space include
d > = b.
a = c & d > c.
b > d & c > = a.
and so on. We will also include in our version space the universal relation, satisfied by all quadruples, and the empty relation, satisfied by no quadruples.

Describe what will happen if the candidate elimination algorithm is applied to this problem and the following examples are encountered, in succession. That is, you should show the successive values of the sets S and G as each new example is encountered.

R(3,1,4,2) is satisfied.
R(2,2,1,3) is not satisfied.
R(1,3,4,4) is satisfied.