1 / 8 Perceptron & SVM

Mistake-Driven Nudge

A perceptron misclassifies a training example (x,y)(x, y) with y∈{−1,+1}y \in {-1, +1} (i.e., sign(w⋅x+b)≠y\text{sign}(w \cdot x+b) \neq y). Which update rule does the perceptron learning algorithm apply, and what convergence guarantee holds when the training data is linearly separable?

A

w←w+η⋅xw \leftarrow w + \eta \cdot x, ignoring the label yy; the algorithm is guaranteed to converge in a finite number of updates

B

w←w+η⋅y⋅xw \leftarrow w + \eta \cdot y \cdot x; the algorithm converges, but specifically to the maximum-margin separating hyperplane

C

w←w+η⋅y⋅xw \leftarrow w + \eta \cdot y \cdot x (and bb updated similarly); the algorithm is guaranteed to converge to a separating hyperplane in a finite number of updates

D

w←w−η⋅y⋅xw \leftarrow w - \eta \cdot y \cdot x; the algorithm is guaranteed to converge in a finite number of updates

E

w←w+η⋅y⋅xw \leftarrow w + \eta \cdot y \cdot x; convergence is only guaranteed if the features are first normalized to unit variance