CS 221 exam-2016 Stanford University

Document Content and Description Below

CS221 Exam Solutions CS221 November 29, 2016 Name: | {z } by writing my name I agree to abide by the honor code SUNet ID: Read all of the following information before starting the exam: • This test has 4 problems and is worth 150 points total. It is your responsibility to make sure that you have all of the pages. • Keep your answers precise and concise. Show all work, clearly and in order, or else points will be deducted, even if your final answer is correct. • Don’t spend too much time on one problem. Read through all the problems carefully and do the easy ones first. Try to understand the problems intuitively; it really helps to draw a picture. • You cannot use any external aids except one double-sided 81 2" x 11" page of notes. • Good luck! Problem Part Max Score Score 1 - 10 2 a 10 b 10 c 10 d 10 3 a 10 b 10 c 10 d 10 e 10 4 a 10 b 10 c 10 d 10 e 10 Total Score: + + = 11. Warmup (10 points) Let us warmup with five conceptual multiple choice questions, each worth two points. For each question, circle all the letters that apply. 1. Which of the following algorithms are guaranteed to compute the global optimum of their respective objectives (minimize cost, minimize loss, or maximize value) for the problems they are applicable to? Circle all that apply. a. k-means b. value iteration c. backtracking search d. dynamic programming e. iterated conditional modes Answer: b, c, d. K-means and iterated conditional modes are only guaranteed to converge to local optima, not global optima. 2. Which of the following are valid ways to reduce overfitting? Circle all that apply. a. Removing some feature templates. b. Performing early stopping when optimizing the training objective using SGD. c. Constraining the norm (length) of the weight vector to be at most 1. d. Setting some of the feature weights to be zero. e. Replacing a single more complex feature (e.g., x10) with a simpler one (e.g., x). Answer: a, b, c, d. Only the last one is not valid because we are only changing one feature, not reducing the number of features. If we had replaced the features x; x2; : : : ; x10 with x, that would reduce overfitting. 3. Which of the following algorithms can be used to find the minimum number of actions needed to reach an end state from the start state in an arbitrary search problem? Circle all that apply. a. depth-first search b. breadth-first search c. uniform cost search d. dynamic programming e. backtracking search Answer: b, c, e. To minimize the number of actions, we set all action costs to a positive constant (say 1). This is exactly the condition for which breadth-first search works. Since all costs are non-negative as well, uniform cost search works. Dynamic programming requires acyclicity, which we are not guaranteed. Backtracking search always works.

[Show More]

Last updated: 3 months ago

Preview 1 out of 24 pages

Buy Now

Instant download