Q1. (10 points) Answer the following with a yes or no along with proper justification. a. Is the decision boundary of voted perceptron linear? b. Is the decision boundary of averaged perceptron linear?

Question 1 – A: No, there are nonlinear bounds for the voted perceptron. Consider the following scenario: You are attempting to distinguish between positive and negative samples, and you have two weight vectors (0,1) and (-1,0). Both weight vectors have a survival time of 1, meaning that they each withstand the same amount of training iterations. Only occurrences in the left quadrant will be marked as positive. That makes it nonlinear. Question 1 - B: Yes, since we simply average the two vectors of weights. (1(0,1) + 1(-1, 0))/2 = (-1/2,1/2) Thus, the linear decision boundary is defined by this single weights vector.