CS 188: Practice MidtermSpring 2006March 4, 20061 True/FalseT/F A rational agent may choose to play a game of chance with negative expected payoff.T/F If a tree search algorithm is complete, the corresponding g raph search algorithm will be, too.T/F For all random variables X, Y and Z and distributions over them,P (Y |X)P (Z|X)P (X)P (Y, Z)= P (X|Y, Z)T/F The p erceptron algorithm always converges for inseparable dataT/F If a CSP is known to have a tree-structured graph, then forward checking and arc consistency areequivalent operations.2 SearchConsider the following search problem:S G10ABC52152Node hS 4A 3B 2C 100G 0Which path will each search algorithm return, assuming all successor functions work out in such a way thatnodes are explored in alphabetical order whenever possible?(a) Breadth-first search(b) Depth-first search(c) Uniform-cost search(d) A* search(e) Greedy search(f) Name a node that uniform-cost search will e xpand, but A* will not.Describe a reasonably g e neral case in which ea ch of the following will occur, or state that the scenariois impossible. Correct answers should not take mo re than o ne or two sentences.(g) Depth-first search never terminates, despite a finite goal(h) Breadth-first search never terminates, despite a finite goal(i) Uniform cost se arch and breadth-first search expand the same nodes and return the same goal3 CSPsYou must arrange three statues in an exhibit hall: an ice carving of a swan (i), a gold lion (g), and a marbleabstract piece (m). There are three tables, 1, 2, and 3, arranged in a row, with 1 closest to the door and3 farthest into the exhibit hall. It is a hot day and so the ice carving cannot be neares t the door. Yourmanager also informs you that it will look bad to have to animal sculptures on adjacent tables. Reality tellsyou that each table must have a different sculpture.If we formulate this problem as a binary CSP with variables X1, X2, and X3, each with domain {i, g, m}:(a) What are the unary constraint(s) (list them explicitly)(b) What are the binary constra int(s) (list them explicitly)Assume we enforce the unary c onstraint(s) in pre-processing for the remaining parts:(c) Which variable will be assigned first by the MRV heuristic?(d) If we assign X3= i, show the domains of the remaining variables after forward checking.(e) If no variables are assigned, show the initial domains after running arc consistency.(f) If it’s a cool day, and we drop the requirement that the ice swan cannot be nearest the door, what arethe initial domains after running arc consistency?4 Proba bilityYou are hired by a casino to help detect cheaters who manage to sneak loaded dice into a game whichinvolves rolling a die 4 times in a row. With CS188 under your belt, you’ve decided to use a Naive Bayesmodel in order to detect cheaters. Assume that the prior probability of a player cheating is P (cheat) = 0.1.Non-cheaters all use fair dice, and cheaters all use a single type of lo aded die.(a) The casino has kept a record of the rolls of the last three known cheaters : they were [1, 2, 6, 6],[6, 3, 5, 4],and [6, 6, 6, 6]. Using this data, estimate the distribution of the loaded die.(b) What is the poster ior probability that a gambler is cheating given a roll sequence of [6, 2, 6, 6] accordingto your estimate of the distribution from (a)?(c) If the utility of falsely accusing a non-cheater is -10, what is the minimum utility for catching a cheaterwhich will make accusing the gambler in (b) the rational action?5 ClassificationImagine we have featur e s f1, f2, f3, f4and three classes, {x, y, z}. Assume we are training a multi-classperceptron and a given point in the training, it ha s the following weight vectors:wx= h0, 0, 0, 0iwy= h0, 2, 0, 0iwz= h2, 0, 1, 0i(a) If we next encounter the instance h1, 0, 0, 1i with true label x, write the resulting weights after process-ing this new instance:(b) If we next encounter the instance h0, 1, 1, 1i with true lab e l y, write the resulting weights after pro-cessing this new instance:Consider a domain with three Boolean attributes, {X, Y, Z} and the ta rget function f(x, y, z) = x xor z.Let H be the space of decision tree s over these attributes.(c) Is f realizable? If so, draw a decisio n tree which proves it; if not, argue why it is not.Consider the following data set:X Y Z f1 0 1 11 1 0 00 0 0 00 1 1 11 0 1 10 0 1 00 1 1 11 1 1 0(d) Draw the decision tree which would be learned from this data using the recursive splitting algorithmpresented in class. Assume that splits are chosen using information gain, and gain ties are broken to prefersplits by alphabetical
View Full Document