CSC4444 Homework 4 Due Monday Nov. 12 20018 I [50%] Consider the following examples of a concept defined over attributes "Shape", "Color" and "Size" Here the possible values for "Shape circle, triangle, square, those for "Color" red, blue and for "Size"sl, medium, large. Construct a decision tree to classify the examples. Show the information gain calculation at each intemal node, and draw the final decision tree. Exp Shape Color Size el circle e2 ci e3 crcle red large e4 e square red e6 square e7 e8 square blue large e9 riangle red Class blue large rele red medium square blue small square blue medium + uare edSmall small 0 riangle red arge ell triangle blue medium+ 2(50%) 2.1 Consider a learning task in which each instance is a Boolean vector of length n. Namely, the exanmples/instances are represented by n Boolean attributes. What is the size of the Instance Space X? Explain your answer 2.2 Assume the hypothesis space H for learning is the collection of ALL Boolean functions with Boolean variables. How many semantically distinct bypotheses do we have in H Explain your answer. In particular, when 3, what is the size of H? 2.3 Write down ALL hypothses in Hcon (assuming we have n 2 Boolean variables x and x2) where Hco is the collection of Boolean Conjunctive Concepts namely, each hypothesis in h is a Conjunction (logical "and") of Boolean literals. Assume we have two data sets R and S. Here R has totally 200 examples, with 120 positive examples and 80 negative examples. And set S has totally 100 examples with 30 positive examples and 70 negative examples. Calculate the entropy for each set. Which set has the larger Information Entropy? Explain your answer you might want to draw the curve for the Information Entropy to illustrate your point. 2.4 2.5 What is Overfitting in machine learning? What are the possible causes for overfitting? 2.6 Briefly describe one method that tackles the issue of overfitting in Decision Tree learning. 2.7 Draw a decision tree T for the Boolean function xAx2vx3ATA CSC4444 Homework 4 Due Monday Nov. 12 20018 I [50%] Consider the following examples of a concept defined over attributes "Shape", "Color" and "Size" Here the possible values for "Shape circle, triangle, square, those for "Color" red, blue and for "Size"sl, medium, large. Construct a decision tree to classify the examples. Show the information gain calculation at each intemal node, and draw the final decision tree. Exp Shape Color Size el circle e2 ci e3 crcle red large e4 e square red e6 square e7 e8 square blue large e9 riangle red Class blue large rele red medium square blue small square blue medium + uare edSmall small 0 riangle red arge ell triangle blue medium+ 2(50%) 2.1 Consider a learning task in which each instance is a Boolean vector of length n. Namely, the exanmples/instances are represented by n Boolean attributes. What is the size of the Instance Space X? Explain your answer 2.2 Assume the hypothesis space H for learning is the collection of ALL Boolean functions with Boolean variables. How many semantically distinct bypotheses do we have in H Explain your answer. In particular, when 3, what is the size of H? 2.3 Write down ALL hypothses in Hcon (assuming we have n 2 Boolean variables x and x2) where Hco is the collection of Boolean Conjunctive Concepts namely, each hypothesis in h is a Conjunction (logical "and") of Boolean literals. Assume we have two data sets R and S. Here R has totally 200 examples, with 120 positive examples and 80 negative examples. And set S has totally 100 examples with 30 positive examples and 70 negative examples. Calculate the entropy for each set. Which set has the larger Information Entropy? Explain your answer you might want to draw the curve for the Information Entropy to illustrate your point. 2.4 2.5 What is Overfitting in machine learning? What are the possible causes for overfitting? 2.6 Briefly describe one method that tackles the issue of overfitting in Decision Tree learning. 2.7 Draw a decision tree T for the Boolean function xAx2vx3ATA
