DOC PREVIEW
Berkeley COMPSCI 188 - Practice Midterm

This preview shows page 1-2 out of 6 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 188 - Practice Midterm

Documents in this Course
CSP

CSP

42 pages

Metrics

Metrics

4 pages

HMMs II

HMMs II

19 pages

NLP

NLP

23 pages

Midterm

Midterm

9 pages

Agents

Agents

8 pages

Lecture 4

Lecture 4

53 pages

CSPs

CSPs

16 pages

Midterm

Midterm

6 pages

MDPs

MDPs

20 pages

mdps

mdps

2 pages

Games II

Games II

18 pages

Load more
Download Practice Midterm
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Practice Midterm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Practice Midterm 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?