This study source was downloaded by 100000831648457 from CourseHero com on 03 07 2022 00 53 24 GMT 06 00 https www coursehero com file 65178393 midterm cs 6375 spring 2018 the exam is closed book 1 cheat sheet allowed answer the questions in th 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 knownQuestionPointsScoreDecision Trees10Neural Networks10Support Vector Machines SVMs 10Short Questions20Total 501 This study source was downloaded by 100000831648457 from CourseHero com on 03 07 2022 00 53 24 GMT 06 00 https 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 2018Final Page 2 of 9March 8 2018 This study source was downloaded by 100000831648457 from CourseHero com on 03 07 2022 00 53 24 GMT 06 00 https 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 2018Final Page 3 of 9March 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 bcbcbcbcbcbcbc012345012345 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 00 https 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 2018Final Page 4 of 9March 8 2018Consider the dataset given below X1 X2 X3and X4are the attributes or features and Y is theclass variable X1X2X3X4Y3001 1100 2011 5110 4101 6010 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 00 https 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 2018Final Page 5 of 9March 8 2018Question 2 Neural Networks 10 points Consider the Neural network given below 3412x1x2w1w2w3w4w5w8w6w7Assume 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 00 https 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 2018Final Page 6 of 9March 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 4o2 This study source was downloaded by 100000831648457 from CourseHero com on 03 07 2022 00 53 24 GMT 06 00 https 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 2018Final Page 7 of 9March 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 x1x2y00 101 110 111 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 03 07 2022 00 53 24 GMT 06 00 https 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 2018Final Page 8 of 9March 8 2018Question 4 Short Questions 20 points Consider a linear regression problem y w1x w2z w0 with a