The Perceptron Learning Algorithm In this problem, you will create your own target function f and data set D to see how the Perceptron Learning Algorithm works. Take d=2 so you can visualize the problem, and assume X=[-1,1] x[-1,1] with uniform probability of picking each χελ. In each run, choose a random line in the plane as your target function f (do this by taking two random, uniformly distributed points in [-1,1] x [-1,1] and taking the line passing through them), where one side of the line maps to +1 and the other maps to-1. Choose the inputs x, of the data set as random points (uniformly in X'), and evaluate the target function on each x, to get the corresponding output y Now, in each run, use the Perceptron Learning Algorithm to find g. Start the PLA with the weight vector w being all zeros (consider sign(0) = 0, so all points are ini- tially misclassified), and at each iteration have the algorithm choose a point randomly from the set of misclassified points. We are interested in two quantities: the number of iterations that PLA takes to converge to g, and the disagreement between f and g which is P[f(x) + g(x)] (the probability that and g will disagree on their clas sification of a random point). You can either calculate this probability exactly, or approximate it by generating a sufficiently large, separate set of points to estimate it. In order to get a reliable estimate for these two quantities, you should repeat the experiment for 1000 runs (each run as specified above) and take the average over these is. 4. Take N 10. How many iterations does it take on average for the PLA to converge for N 10 training points? Pick the value closest to your results (again, 'closest' means: [your answer - given option is closest to 0). [a] 1 [b] 15 [c] 300 [d] 5000 [e] 10000 5. Which of the following is closest to P|f(x) + g(x)] for N = 10? [a] 0.001 [b] 0.01 [e] 0.1 [d] 0.5 [e] 0.8 6. Now, try N = 100. How many iterations does it take on average for the PLA to converge for N = 100 training points? Pick the value closest to your results. [a] 50 [b] 100 [c] 500 [d] 1000 [e] 5000 7. Which of the following is closest to P[f(x) = g(x)] for N = 100? [a] 0.001 [b] 0.01 [c] 0.1 [d] 0.5 [e] 0.8