Description
Problem 1 (2 points): A typical machine learning task is supervised learning of a classification function (aka a concept): give example x the right class label l. Assume there is an unknown target concept c(x), whose domain is a set of unique examples X, called the instance space, and whose range is a set of unique labels L. The task is to learn that function. A learner does this by testing hypotheses. A hypothesis h(x) is also function whose domain is X and whose range is L. If the set of hypotheses a learner is able to consider is the same as the set of possible concepts, then the set of unique hypotheses (the hypothesis space H) is identical to the set of unique concepts (the concept space C). For this question, assume H = C. In supervised learning, exploration of the hypothesis space is guided by the use of a finite data set, D that contains examples from X with known labels from the target concept c(x). Since we can only measure success with respect to the data, we reframe the task of learning c(x) to that of finding a hypothesis consistent with the data: ∀x∈D, c(x)=h(x)
Definition: Two functions f1 and f2 are distinguishable, given D, if they differ in their labeling of at least one of the examples in D.
Definition: A set of hypotheses is distinguishable, given D, iff ALL pairs of hypotheses in the set are distinguishable given D. Call HD a largest set of distinguishable hypotheses, given D.
A) (1/2 point) Assume that X, L and D are all finite and given (i.e. they are all fixed). Is there one unique HD? Explain your reasoning.
B) (1/2 point) Let the size of the data and the label set be drawn from the counting numbers (i.e. |D|,|L|∈{1,2,3…}). Formulate the size of HD, as a function of |L| and |D|. Explain your reasoning.
For parts C and D assume the following. The label set L is {0,1}. The size of the data set |D| = 100. The size of the instance space |X| = 200. Assume a learner able to consider a maximal set of distinguishable hypotheses HD.
C) (1/2 point) Assume the learner is able to consider 10^9 (one billion) hypotheses per second. In the worst case, how long would it have to work to find a hypothesis h that is indistinguishable from the target function c, given D? Would this be a reasonable time to wait? Explain your reasoning. State your assumptions.
D) (1/2 point) Assume the learner HAS found a hypothesis h that is indistinguishable from the target concept c , given D. What is the probability that hypothesis h is also indistinguishable from the target concept c , given X? Explain your reasoning. State your assumptions.
EECS 349 (Machine Learning) Homework 1
Problem 2 (1 point): Given the following: Instances X: cars described by following attributes x is a tuple:<country,manufacturer,color,decade,type country∈{Japan,USA,Korea,Germany} manufacturer∈{Honda,Chrysler,Toyota} color∈{blue,green,red,white} decade∈{1970,1980,1990,2000} type∈{Economy,Sport,SUV}
The concept to learn, expressed in English is “Japanese Economy Car”. The target concept function c(x) that maps from X to {0,1} is illustrated by the data D in the following table.
Origin Manufacturer Color Decade Type Classification Japan Honda Blue 1980 Economy 1 Japan Toyota Green 1970 Sports 0 Japan Toyota Blue 1990 Economy 1 USA Chrysler Red 1980 Economy 0 Japan Honda White 1980 Economy 1 A) (1/2 point) Calculate the decision tree that would be learned from the training examples in the “Japanese Economy Car” concept by running ID3 (see the Machine Learning textbook chapter 3). Show information gain for each attribute at each level of the tree. B) (1/2 point) Write out the logical function encoded in the decision tree for “Japanese Economy Car.” How well does this function categorize the data used to build the tree? How well do you feel this captures the concept of “Japanese Economy Car”? What about the approach or the data caused this result? Problem 3 (1 point): A) (1/2 point) Assume a binary labeling problem on some set of examples X. ID3 assumes every attribute of an example takes a finite set of values and assigns a different branch to each value an attribute can take. This obviously can’t work with attributes drawn from the set of real numbers. One easy modification is to pick a split point on the real values (i.e. if attribute a < 3, go left). Describe how you would pick a split point that makes sense. What are the strengths and weaknesses of your approach to picking a split point?
B) (1/2 point) Assume your examples are all 2-dimensional real-valued points on the unit square. Assume you can build a decision tree on real valued data by picking a split point on each dimension. Assume you can always pick the optimal split point. Which of the above concepts can be represented? One? Both? Neither? Explain your reasoning. 0,0
1,1
1,0
0,1
c(x) = 0
c(x) = 1
0,0
1,1
1,0
0,1
c(x) = 0
c(x) = 1
. 5
.5
EECS 349 (Machine Learning) Homework 1
Problem 4 (2 point): Some basic definitions for measuring error A) (1/2 point) Look up and define the following: True Positive, False Positive, True Negative, False Negative. Cite your source(s). B) (1/2 point) Look up and define the following: Precision, Recall. Cite your source(s). C) (1/2 point) Look up and define the F1 score (aka F-measure). Cite your source(s). D) (1/2 point) Look up what a confusion matrix is. Explain why it is useful in analysis of machine learning. Cite your sources (give links & references). Give an example of why it is useful when a classifier has to apply more than two classes. Problem 5 (4 points): Create a Decision Tree classifier that builds a tree using the ID3 algorithm described in the textbook and in class. You are going to code up a decision tree, yourself. Recall that decision tree induction is a machine learning approach to approximating a target concept function f, given a set of examples. An example in our training data is a tuple <x1, x2,…, xn, c(x1, x2,…, xn) consisting of values for the n inputs to the function c and the output of c, given those values. For this problem, you will construct a binary decision tree learner for examples with categorical attributes. PROVIDED FILES You have been provided with two example input files for the learner. IvyLeague.txt – a file containing examples of target concept “people who will be accepted to an Ivy League university” MajorityRule.txt – a file containing examples of target concept “over half of them are ‘true’” An input file is expected to be an ASCII file, where the first line is a tab-delimited list of j attribute names, followed by the word “CLASS”. Each subsequent line consists of a fixed number of tab-delimited values. Each value must be the string ‘true’ or the string ‘false’ and there must be one value for each attribute in the first line of the file, plus an additional Boolean value (at the end of each line) that specifies how the target concept function would classify the example defined by these attribute values. The task for a machine learner is to learn how to categorize examples, using only the values specified for the attributes, so that the machine’s categorization matches the categorization specified in the file. What follows is an example 3-line input file for a target concept ‘People accepted to an Ivy League School’ GoodGrades GoodLetters GoodSAT IsRich Scholarship ParentAlum SchoolActivities CLASS true true true true true true true true true true true false true true false false
YOUR PROGRAM Your program must be written in Python 2.7 and run in the test environment without alteration. We are not responsible for debugging code written in other languages or other versions of Python. We are not responsible for linking to any 3rd party input/output libraries, except for SciPy.
The core decision tree algorithm code must be written by you. You cannot use an existing packages/modules/library that has implemented a decision tree. The point is to write your own decision tree. Your source code must be well commented so that can be easily understood. Your folder must contain a file named “decisiontree.py” that can be called according to the following usage spec: Usage: python decisiontree.py EECS 349 (Machine Learning) Homework 1
{‘GoodGrades’: True, ‘GoodLetters’: True, ‘GoodSAT’: True, ‘IsRich’: True, ‘HasScholarship’: True, ‘ParentAlum’: True, ‘SchoolActivities’: True} Note: Use string comparisons to change the string ‘true’ to the python boolean True. The format above will probably make it easier to write up the code. What the Parameters Do inputFileName – the fully specified path to the input file. Note that windows pathnames may require double backslash ‘\’ trainingSetSize – an integer specifying the number of examples from the input file that will be used to train the system numberOfTrials – an integer specifying how many times a decision tree will be built from a randomly selected subset of the training examples. verbose – a string that must be either ‘1’ or ‘0’ If verbose is ‘1’ the output will include the training and test sets. Else the output will only contain a description of the tree structure and the results for the trials. What the Program Must Do 1) Read in the specified text file containing the examples. 2) Divide the examples into a training set and a testing set. The training set should contain EECS 349 (Machine Learning) Homework 1
For each trial your program should output • The number of the trial • The proportion of correct classifications of the test set returned by the decision tree • The proportion of correct classifications returned by applying prior probability (based on probabilities derived from the training set) to classify the test set • The structure of the decision tree built from the training set When VERBOSE = 1 you must provide the following information for each trial: • The set of examples in the training set • The set of examples in the testing set • The classification returned by the decision tree for each member of the testing set • The classification returned by applying prior probability to each member of the testing set. We will not require that a particular layout be used. That said, if we have ANY problem finding the information specified above in your output file, you WILL lose points. It is up to you to make your output format CLEAR.
EECS 349 (Machine Learning) Homework 1
What follows is an example output for a non-verbose run with two trials in a format that would be completely acceptable. TRIAL NUMBER: 0 ——————– DECISION TREE STRUCTURE: parent: root attribute: IsRich trueChild:GoodLetters falseChild:HasScholarship parent: IsRich attribute: GoodLetters trueChild:leaf falseChild:GoodGrades parent: GoodLetters – parent: GoodLetters attribute: GoodGrades trueChild:leaf falseChild:leaf parent: GoodGrades – parent: GoodGrades – parent: IsRich attribute: HasScholarship trueChild:GoodLetters falseChild:leaf parent: HasScholarship attribute: GoodLetters trueChild:GoodSAT falseChild:leaf parent: GoodLetters attribute: GoodSAT trueChild:leaf falseChild:leaf parent: GoodSAT – parent: GoodSAT – parent: GoodLetters – parent: HasScholarship – Percent of test cases correctly classified by a decision tree built with ID3 = 88% Percent of test cases correctly classified by using prior probabilities from the training set = 45% TRIAL NUMBER: 1 ——————– DECISION TREE STRUCTURE: parent: root attribute: IsRich trueChild:GoodSAT falseChild:HasScholarship parent: IsRich attribute: GoodSAT trueChild:leaf falseChild:GoodGrades parent: GoodSAT – parent: GoodSAT attribute: GoodGrades trueChild:GoodLetters falseChild:leaf parent: GoodGrades attribute: GoodLetters trueChild:leaf falseChild:SchoolActivities parent: GoodLetters – parent: GoodLetters attribute: SchoolActivities trueChild:leaf falseChild:leaf parent: SchoolActivities – parent: SchoolActivities – parent: GoodGrades – parent: IsRich attribute: HasScholarship trueChild:leaf falseChild:leaf parent: HasScholarship – parent: HasScholarship – Percent of test cases correctly classified by a decision tree built with ID3 = 76% Percent of test cases correctly classified by using prior probabilities from the training set = 43% example file used = IvyLeague.txt number of trials = 2 training set size for each trial = 20 testing set size for each trial = 42 mean performance of decision tree over all trials = 82% correct classification mean performance of using prior probability derived from the training set = 44% correct classification
