CSE 546 Midterm Exam, Fall 2014(with Solution)

1 CSE 546 Midterm Exam, Fall 2014(with Solution) 1. Personal info: Name: UW NetID: Student ID:2. There should be 14 numbered pages in this exam (including this cover sheet).3. You can use any material you brought: any book, class notes, your print outs of classmaterials that are on the class website, including my annotated slides and relevantreadings. You cannot use materials brought by other If you need more room to work out your answer to a question, use the back of the pageand clearly mark on the front of the page if we are to look at what s on the Work efficiently. Some questions are easier, some more difficult. Be sure to give yourselftime to answer all of the easy ones, and avoid getting bogged down in the more difficultones before you have answered the easier You have 80 Good luck!QuestionTopicMax scoreScore1 Short Answer242 Decision Trees163 Logistic Regression204 Boosting165 Elastic Net24 Total10011 [24 points] Short Answer1.

2 [6 points] On the 2D dataset below, draw the decision boundaries learned by thefollowing algorithms (using the featuresx/y).Be sure to mark which regions arelabeled positive or negative, and assume that ties are broken arbitrarily.(a) Logistic regression ( = 0)(b) 1-NN(c) 3-NN2. [6 points] A random variable follows anexponentialdistribution with parameter ( >0) if it has the following density:p(t) = e t, t [0, )This distribution is often used to model waiting times between events. Imagine youare given dataT= (t1,..,tn) where eachtiis modeled as being drawn from anexponential distribution with parameter .(a) [3 points] Compute the log-probability of T given . (Turn products into sumswhen possible).2 FANSWER:lnp(T) = ln ip(ti)lnp(T) = iln( e ti)lnp(T) = iln tilnp(T) =nln iti(b) [3 points] Solve for : (nln iti) = 0n iti= 0 MLE=n iti3. [6 points]ABCYFFFFTFTTTTFTTTTF(a) [3 points] Using the dataset above, we want to build a decision tree which classifiesYasT/Fgiven the binary variablesA,B,C.]

3 Draw the tree that would be learnedby the greedy algorithm with zero training error. You do not need to show :(b) [3 points] Is this tree optimal ( does it get zero training error with minimaldepth)? Explain in less than two sentences. If it is not optimal, draw the optimaltree as :Although we get a better information gain by first splitting onA,Yis just a function ofB/C:Y=BxorC. Thus, we can build a tree of depth 2which classifies correctly, and is [6 points] In class we used decision trees and ensemble methods for classification, butwe can use them for regression as well ( learning a function from features to realvalues). Let s imagine that our data has 3 binary featuresA,B,C, which take values0/1, and we want to learn a function which counts the number of features which havevalue 1.(a) [2 points] Draw the decision tree which represents this function. How many leafnodes does it have?4 FANSWER:We can represent the function with a decision tree containing8 nodes.

4 (b) [2 points] Now represent this function as a sum of decision stumps ( (A)).How many terms do we need?FANSWER:f(x) =sgn(A) +sgn(B) +sgn(C)Using a sum of decision stumps, we can represent this function using3 terms.(c) [2 points] In the general case, imagine that we havedbinary features, and wewant to count the number of features with value 1. How many leaf nodes would adecision tree need to represent this function? If we used a sum of decision stumps,how many terms would be needed? No explanation is :Using a decision tree, we will need2dnodes. Using a sum ofdecision stumps, we will [16 points] Decision TreesWe will use the dataset below to learn a decision tree which predicts if people pass machinelearning (Yes or No), based on their previous GPA (High, Medium, or Low) and whether ornot they this problem, you can write your answers using log2, but it may be helpful to notethat log23 [4 points] What is the entropy H(Passed)?

5 FANSWER:H(Passed) = (26log226+46log246)H(Passed) = (13log213+23log223)H(Passed) =log23 23 [4 points] What is the entropy H(Passed|GPA)?FANSWER:H(Passed|GPA) = 13(12log212+12log212) 13(12log212+12log212) 13(1 log21)H(Passed|GPA) =13(1) +13(1) +13(0)H(Passed|GPA) =23 [4 points] What is the entropy H(Passed|Studied)?6 FANSWER:H(Passed|Studied) = 12(13log213+23log223) 12(1 log21)H(Passed|Studied) =12(log23 23H(Passed|Studied) =12log23 13 [4 points] Draw the full decision tree that would be learned for this dataset. You donot need to show any :We want to split first on the variable which maximizes the informationgainH(Passed) H(Passed|A). This is equivalent to minimizingH(Passed|A), so weshould split on Studied? [20 points] Logistic Regression for Sparse DataIn many real-world scenarios our data has millions of dimensions, but a given example hasonly hundreds of non-zero features. For example, in document analysis with word counts forfeatures, our dictionary may have millions of words, but a given document has only hundredsof unique words.)

6 In this question we will makel2regularized SGD efficient when our inputdata is sparse. Recall that inl2regularized logistic regression, we want to maximize thefollowing objective (in this problem we have excludedw0for simplicity):F(w) =1NN j=1l(x(j),y(j),w) 2d i=1w2iwherel(x(j),y(j),w) is the logistic objective functionl(x(j),y(j),w) =y(j)(d i=1wix(j)i) ln(1 + exp(d i=1wix(j)i))and the remaining sum is our regularization we do stochastic gradient descent on point (x(j),y(j)), we are approximating theobjective function asF(w) l(x(j),y(j),w) 2d i=1w2iDefinition of sparsity:Assume that our input data hasdfeatures, (j) Rd. Inthis problem, we will consider the scenario wherex(j)is sparse. Formally, letsbe averagenumber of nonzero elements in each example. We say the data is sparse whens << d. In thefollowing questions,your answer should take the sparsity of x(j)into considerationwhen :When we use a sparse data structure, we can iterate over thenon-zero elements inO(s) time, whereas a dense data structure requiresO(d) [2 points] Let us first consider the case when = 0.

7 Write down the SGD update ruleforwiwhen = 0, using step size , given the example (x(j),y(j)).FANSWER:The update rule can be written asw(t+1)i w(t)i+ x(j)i(y(j) 11 + exp( kwkx(j)k))2. [4 points] If we use a dense data structure, what is the average time complexity toupdatewiwhen = 0? What if we use a sparse data structure? Justify your answerin one or two :The time complexity to calculate kwkx(j)kisO(d)when the datastructure is dense, andO(s)when the data structure is sparse. Note that even if weupdatewifor alli, we only need to calculate kwkx(j)konce, and then update thewisuch thatx(j)i6= 0. So the answer isO(d)for the dense case, andO(s)for the [2 points] Now let us consider the general case when >0. Write down the SGDupdate rule forwiwhen >0, using step size , given the example (x(j),y(j)).FANSWER:w(t+1)i w(t)i w(t)i+ x(j)i(y(j) 11 + exp( kwkx(j)k))4.

8 [2 points] If we use a dense data structure, what is the average time complexity toupdatewiwhen >0?FANSWER:The time complexity isO(d)5. [4 points] Letw(t)ibe the weight vector aftert-th update. Now imagine that we per-formkSGD updates onwusing examples (x(t+1),y(t+1)), ,(x(t+k),y(t+k)), wherex(j)i= 0 for every example in the sequence. ( thei-th feature is zero for all of theexamples in the sequence). Express the new weight,w(t+k)iin terms ofw(t)i,k, , and .FANSWER:Whenx(j)i= 0,w(t+1)i=w(t)i w(t)i=w(t)i(1 )so the answer isw(t+k)i=w(t)i(1 )k6. [6 points] Using your answer in the previous part, come up with an efficient algorithmfor regularized SGD when we use a sparse data structure. What is the average timecomplexity per example? (Hint: when do you need to updatewi?)9 Algorithm 1:Sparse SGD Algorithm for Logistic Regression with RegularizationInitializeci 0 fori {1,2, ,d}forj {1,2, n}do p 11+exp( kwkx(j)k)forisuch thatx(j)i6= 0dok j ci; auxiliary variableciholds the index of last time we seex(j)i6= 0wi wi(1 )k; apply all the regularization updateswi wi+ x(j)i(y(j) p);regularization is done in previous stepci j;remember last time we seex(j)i6= 0endendFANSWER:The idea is to only updatewiwhenx(j)i6= 0.

9 Before we do the update,we apply all the regularization updates we skipped before, using the answer from previousquestion. You can checkout Algorithm 1 for details. Using this trick, each update takesO(s)time. (Note: we can use the same trick applies for SGD withl1regularization)104 [16 points] BoostingRecall that Adaboost learns a classifierHusing a weighted sum of weak learnershtas followsH(x) =sgn(T t=1 tht(x))In this question we will use decision trees as our weak learners, which classify a point as{1, 1}based on a sequence of threshold splits on its features (herex,y).In the questions below, be sure to mark which regions are marked posi-tive/negative, and assume that ties are broken :The solutions below are one of several possible answers. You got full creditas long as you were consistent and found a boundary with the lowest training error forh1, [2 points] Assume that our weak learners are decision trees of depth 1 ( decisionstumps), which minimize the weighted training error.

10 Using the dataset below, drawthe decision boundary learned [3 points] On the dataset below, circle the point(s) with the highest weights on thesecond iteration, and draw the decision boundary learned :The points with the highest weight will be those that were classifiedincorrectly [3 points] On the dataset below, draw the decision boundary ofH=sgn( 1h1+ 2h2).(Hint, you do not need to explicitly compute the s).FANSWER:Althoughh1andh2misclassify the same number of points, the pointswhichh2gets wrong have been downweighted. Thus, we have 1> 2, so 2> 1, andh2will dominate overh1whenever there is a conflict. In other words,Hhas the sameboundary [2 points] Now assume that our weak learners are decision trees of maximium depth2, which minimize the weighted training error. Using the dataset below, draw thedecision boundary learned [3 points] On the dataset below, circle the point(s) with the highest weights on thesecond iteration, and draw the decision boundary learned :Again, the points with the highest weight will be those that were clas-sified incorrectly [3 points] On the dataset below, draw the decision boundary ofH=sgn( 1h1+ 2h2).