Unformatted text preview:

Midterm: CS 6375Spring 2018The exam is closed book (1 cheat sheet allowed). Answer the questions in the spaces provided on thequestion sheets.If you run out of room for an answer, use an additional sheet (available from the instructor)and staple it to your exam.• NAME• UTD-ID if knownQuestion Points ScoreDecision Trees 10Neural Networks 10Support Vector Machines (SVMs)10Short Questions 20Total: 501This study source was downloaded by 100000831648457 from CourseHero.com on 03-07-2022 00:53:24 GMT -06:00https://www.coursehero.com/file/65178393/midterm-cs-6375-spring-2018-the-exam-is-closed-book-1-cheat-sheet-allowed-answer-the-questions-in-th/Spring 2018 Final, Page 2 of 9 March 8, 2018This study source was downloaded by 100000831648457 from CourseHero.com on 03-07-2022 00:53:24 GMT -06:00https://www.coursehero.com/file/65178393/midterm-cs-6375-spring-2018-the-exam-is-closed-book-1-cheat-sheet-allowed-answer-the-questions-in-th/Spring 2018 Final, Page 3 of 9 March 8, 2018Question 1: Decision Trees(10 points)Consider a large dataset D having n examples in which the positive (denoted by +) and negative exam-ples (denoted by ◦) follow the pattern given below. (Notice that the data is clearly linearly separable).× × ××× ××bcbcbcbcbcbcbc0123450 1 2 3 4 5(a) (5 points)Which among the following is the “best upper bound” (namely the smallest one that isa valid upper bound) on the number of leaves in an optimal decision tree for D (n is the numberof examples in D)? By optimal, I mean a decision tree having the smallest number of nodes.Cir-cle the answer and explain why it is the best upper bound. No credit without a correct explanation.1. O(n)2. O(log n)3. O(log log n)4. O((log n)2)Solution:O(n) is the correct answer.Since all splits are either horizontal or vertical, each ofthem will classify at most one point correctly.This study source was downloaded by 100000831648457 from CourseHero.com on 03-07-2022 00:53:24 GMT -06:00https://www.coursehero.com/file/65178393/midterm-cs-6375-spring-2018-the-exam-is-closed-book-1-cheat-sheet-allowed-answer-the-questions-in-th/Spring 2018 Final, Page 4 of 9 March 8, 2018Consider the dataset given below.X1, X2, X3and X4are the attributes (or features) and Y is theclass variable.X1X2X3X4Y3 0 0 1 +1 1 0 0 −2 0 1 1 −5 1 1 0 +4 1 0 1 +6 0 1 0 −(b) (2 points)Which attribute (among X1, X2, X3and X4) has the highest information gain?Solution:X1has the highest information gain (it has a different value for each example).(c) (3 points)In the above dataset, is the attribute having the highest information gain useful (namelywill it help improve generalization)? Answer YES/NO and then• Explain why the attribute is useful if your answer is “YES.”• If your answer is “NO”, explain how will you change the information gain criteria so that suchuseless attributes are not selected.Solution:Answer is NO. The attribute does not generalize well.Use the GainRatio criteriawe discussed in class (we divide the gain by the entropy of the attribute).This study source was downloaded by 100000831648457 from CourseHero.com on 03-07-2022 00:53:24 GMT -06:00https://www.coursehero.com/file/65178393/midterm-cs-6375-spring-2018-the-exam-is-closed-book-1-cheat-sheet-allowed-answer-the-questions-in-th/Spring 2018 Final, Page 5 of 9 March 8, 2018Question 2: Neural Networks (10 points)Consider the Neural network given below.3 41 2x1x2w1w2w3w4w5w8w6w7Assume that all internal nodes and output nodes compute the sigmoid σ(t) function.In this ques-tion,we will derive an explicit expression that shows how back propagation (applied to minimize theleast squares error function) changes the values of w1, w2, w3, w4, w5, w6, w7and w8when the algo-rithm is given the example (x1, x2, y1, y2) with y1and y2being outputs at 3 and 4 respectively (thereare no bias terms).Assume that the learning rate is η.Let o1and o2be the output of the hidden units 1and 2 respectively.Let o3and o4be the output of the output units 3 and 4 respectively.Hint: Derivative:ddtσ(t) = σ(t)(1 − σ(t)).(a) (2 points)Forward propagation.Write equations for o1, o2, o3and o4.Solution:o1= σ(w1x1+ w3x2)o2= σ(w2x1+ w4x2)o3= σ(w5o1+ w7o2)o4= σ(w6o1+ w8o2)(b) (4 points)Backward propagation.Write equations for δ1, δ2, δ3and δ4where δ1, δ2, δ3and δ4arethe values propagated backwards by the units denoted by 1, 2, 3 and 4 respectively in the neuralnetwork.Solution:δ1= o1(1 − o1)(δ3w5+ δ4w6)δ2= o2(1 − o2)(δ3w7+ δ4w8)δ3= o3(1 − o3)(y1− o3)δ4= o4(1 − o4)(y2− o4)This study source was downloaded by 100000831648457 from CourseHero.com on 03-07-2022 00:53:24 GMT -06:00https://www.coursehero.com/file/65178393/midterm-cs-6375-spring-2018-the-exam-is-closed-book-1-cheat-sheet-allowed-answer-the-questions-in-th/Spring 2018 Final, Page 6 of 9 March 8, 2018(c) (4 points)Give an explicit expression for the new (updated) weights w1, w2, w3, w4, w5, w6, w7and w8after backward propagation.Solution:w1= w1+ ηδ1x1w2= w2+ ηδ2x1w3= w3+ ηδ1x2w4= w4+ ηδ2x2w5= w5+ ηδ3o1w6= w6+ ηδ4o1w7= w7+ ηδ3o2w8= w8+ ηδ4o2This study source was downloaded by 100000831648457 from CourseHero.com on 03-07-2022 00:53:24 GMT -06:00https://www.coursehero.com/file/65178393/midterm-cs-6375-spring-2018-the-exam-is-closed-book-1-cheat-sheet-allowed-answer-the-questions-in-th/Spring 2018 Final, Page 7 of 9 March 8, 2018Question 3: Support Vector Machines (SVMs)(10 points)Consider the following 2-D dataset (x1and x2are the attributes and y is the class variable).Dataset:x1x2y0 0 +10 1 +11 0 +11 1 −1(a) (5 points)Precisely write the expression for the dualproblem (assuming Linear SVMs).Letα1, α2, α3, α4be the lagrangian multipliers associated with the four data points.Solution:Maximize: α1+ α2+ α3+ α4−12−2α2α4− 2α3α4+ 2α24+ α22+ α23subject to:α1, α2, α3, α4≥ 0, α1+ α2+ α3− α4= 0(b) (5 points)Identify the support vectors and compute the value of α1, α2, α3and α4. (Hint:Youdon’t have to solve the dual optimization problem to compute α1, α2, α3and α4.)Solution:The last three points are the support vectors.This means that α1= 0 and α4=α2+ α3. Substituting these two constraints in the quadratic optimization problem, we get:Maximize: 2α2+ 2α3−12(α22+ α23)Taking derivatives with respect to α2and α3and setting them to zero,we get:α2= 2 andα3= 2. Therefore, α4= α2+ α3= 2 + 2 = 4.This study source was downloaded by 100000831648457 from CourseHero.com on


View Full Document

UTD CS 6375 - Midterm: CS 6375

Download Midterm: CS 6375
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 Midterm: CS 6375 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 Midterm: CS 6375 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?