CMSC 421 Homework 5OPTIONAL HomeworkDue Date: Tuesday, December 13 at the start of class1. [20 points] Decision tree learningThe following table gives a data set for deciding whether or not to go sailing, dependingon the weather conditions.Outlook Temp (F) EngineOK? Windy? Classsunny 75 yes true Sailsunny 80 no true Don’t Sailsunny 85 yes false Don’t Sailsunny 72 yes false Don’t Sailsunny 69 yes false Sailovercast 72 yes true Sailovercast 83 yes false Sailovercast 64 yes true Sailovercast 81 yes true Sailrain 71 no true Don’t Sailrain 65 no true Don’t Sailrain 75 yes false Don’t Sailrain 68 yes false Don’t Sailrain 70 yes false Don’t Sail(a) At the root node for a decision tree in this domain, what are the informationgains associated with the Outlook and EngineOK attributes?(b) Again at the root node, what are the gain ratios associated with the Outlookand EngineOK attributes?(c) Suppose you build a decision tree that splits on the Outlook attribute at the rootnode. How many children nodes are there are at the first level of the decisiontree? Which branches require a further split in order to create leaf nodes withinstances belonging to a single class? For each of these branches, is there anattribute you can split on to complete the decision tree building process at thenext level (i.e., so that at level 2, there are only leaf nodes)? Draw the resultingdecision tree, showing the decisions (class predictions) at the leaves.2. [20 points] Version SpacesConsider a domain describing restaurants and consider the version space defined bythe concepts that are a conjunction of the following three attributes: cuisine type,price and portion size. Suppose we have the generalization hierachies for each of theattributes shown in the figure.Examples of legal concepts in this domain include [chinese $ all-you-can-eat], [eu-ropean expensive small], and [any-type any-price any-size]. No disjunctive conceptsare allowed, other than the implicit disjunctions represented by the internal nodes inthe attribute hierarchies. (For example, the concept [[asian v african] $ large] isn’tallowed.)Homework 5: CMSC 421, Introduction to Artificial Intelligence: Fall 2005 2any-typeeuropeanafricanasianchinese japanese french italianany-priceexpensiveinexpensive$ $$ $$$ $$$$any-sizelargesmalltiny petite big all-you-can-eatethiopian(a) Consider the initial version space for learning in this domain. What is the Gset? How many elements are in the S set? Give one representative member ofthe initial S set.(b) Suppose the first example I1 is a positive example, with attribute values [chinese$ all-you-can-eat]. After processing this instance, what are the G and S sets?(c) Now suppose the learning algorithm receives example I2, a negative example,with attribute values [french $$$$ petite]. What are the G and S sets afterprocessing this example?(d) If learning ends at this point, how many possible concepts remain in the versionspace?(e) For this question, you should start with the version space that remains after I1and I2 are processed. For each of the following combinations of instance type andevents, give a single instance of the specified type that would cause the indicatedevent, if such an instance exists. If no such instance exists, explain why.i. A positive instance that causes the version space to collapse.ii. A negative instance that causes the version space to collapse.iii. A positive instance that reduces the size of the version space to a singleconcept.iv. A negative instance that reduces the size of the version space to a singleconcept.3. [20 points] Statistical Learning and Utilities R & N, 20.34. [20 points] Neural Networks R & N,
View Full Document
Unlocking...