VC Example2 solutions Question 1 Consider the case where the examples to a learning task are given as pairs of not necessarily Boolean numbers x1 x2 labeled as positive or negative Part A It is known that all positive examples and none of the negative examples satisfy x1 a AND 0 x2 b Here are a few training examples for the case in which a 3 b 1 x1 3 3 3 0 3 5 x2 1 0 5 0 0 5 2 6 label positive positive positive negative negative negative A1 Select the most appropriate learning algorithm for this task among the following choices 1 ID3 2 A perceptron implemented with a sigmoid unit with the following functions as input 1 1 2 x1 3 x 2 3 A neural network with the following functions as input 1 1 2 x1 3 x2 with one hidden layer and with as many hidden layer nodes as needed 4 A neural network with the following functions as input 1 1 2 x1 3 x2 with two hidden layers and with as many hidden layer nodes as needed 5 Naive Bayesian 6 Nearest Neighbor Answer 1 2 3 4 5 6 The most appropriate answer is 3 A2 Your answers to this part should not depend on your answer to A1 Assume that a learning algorithm capable of producing a hypothesis consistent with all training examples is available In each of the following cases compute how many randomly chosen training examples are needed to guarantee with confidence of at least 90 that at least 95 of randomly selected test examples are answered correctly Specify the formula you use for the computation and what is the value of each of the variables in the formula 1 the value of a is one of the following 1 1 5 2 2 5 3 3 5 The value of b is one of the following 1 1 5 2 2 5 3 3 5 Answer The number of training examples should be at least 118 The formula used m 1 ln r The variables in the formula have the values r 36 0 05 0 1 2 a b are real numbers Answer The number of training examples should be at least 1630 The formula used m 1 4 log2 2 8d log2 13 The variables in the formula have the values d 1 0 05 0 1
View Full Document