Practice Test 3

Task 1 Write the pseudocode for the perceptron algorithm. Include the formulas for updating the weight vector and the classification rule.

Task 2 What is the difference, in terms of margin, between the linear separator found by the perceptron algorithm and that found by SVM?

Task 3 Define the optimization criterion for SVM such that it is robust to noise and to some outlying data (meaning that the data is linearly separable, excepting a few points).

Task 4 Suppose $\mathbf{w},b$ are the parameters of a line where $\mathbf{w}$ is the unit normal to the line. Let $y_i\in\{-1,1\}$ and $\mathbf{x} \in R^2$. Plot the areas defined by $y_i(\mathbf{w}\mathbf{x}+b)-1 \leq 0$ and the area defined by $y_i(\mathbf{w}\mathbf{x}+b)-1 > 0$ and mark them as “A” and “B” respectively.

Task 5 Explain the difference between expected risk and empirical risk. In what setting would you prefer expected risk over empirical risk? Rigorously define both quantities.