Perceptron

Definition

Start with $w_0=0$. For the points in turn: if $y_t⟨w,x_t⟩\le 0$ (a mistake, ties included), update $w\leftarrow w+y_t{x}_t$. Cycle through the data until a full sweep makes no update. This is SGD with step size 1 on the linear loss $\max \{0,-y⟨w,x⟩\}$.

Formula

$$M\le \frac{R^2}{{\rho }^2}\text{(mistakes, }\Vert x_i\Vert \le R,\text{margin }\rho >0\text{)},P(\text{test error})\le \frac{1}{n+1}E\left(\frac{R^2}{{\rho }^2}\right)$$

Both bounds are independent of the dimension. The learning rate does not matter when starting at 0 (it only rescales $w$). Without separability the perceptron does not converge; with slack $D$ the number of updates is at most $(R+D{)}^2/{\rho }^2$.

Appears in

• Lecture 2, the algorithm
• Lecture 2, exam-style task by hand
• Lecture 2, perceptron = SGD on the linear loss
• Lecture 2, Theorem 1 and proof
• Lecture 2, Theorem 2
• Lecture 1.1, Rosenblatt 1957 and the XOR limit

Related concepts

• Margin
• Stochastic Gradient Descent
• Leave-One-Out Error