1. Let X = {-1,0, 1} {0}. Let y = {-1, +1} Let h be the right-most nonzero function that maps each string x EX to the value of its right-most nonzero coordinate. Thus h(x) = Xmax{i:\x;l=1} In the previous quiz we showed that a separating hyperplane w E RP exists. Now we show that the perceptron algorithm makes at least an exponential number of mistakes in p before it finds a separating hyperplane. 4. Prove that if we feed all points of X to the perceptron algorithm repeatedly in any order, then the algorithm makes at least 2P-1 mistakes before finding a separating hyperplane. Hint: inspect the largest coordinate of w. How much does it increase at each mistake? 1. Let X = {-1,0, 1} {0}. Let y = {-1, +1} Let h be the right-most nonzero function that maps each string x EX to the value of its right-most nonzero coordinate. Thus h(x) = Xmax{i:\x;l=1} In the previous quiz we showed that a separating hyperplane w E RP exists. Now we show that the perceptron algorithm makes at least an exponential number of mistakes in p before it finds a separating hyperplane. 4. Prove that if we feed all points of X to the perceptron algorithm repeatedly in any order, then the algorithm makes at least 2P-1 mistakes before finding a separating hyperplane. Hint: inspect the largest coordinate of w. How much does it increase at each mistake