Classification

The Perceptron

The perceptron algorithm applied to a simple linear classification problem

speed
click adds
converged not linearly separable
+1
−1
perceptron θ
averaged θ̄

Click empty space to add a point. Step or Run to train.

Key ideas

  • Decision rule: classify $\hat{y} = \mathrm{sign}(\theta \cdot x + \theta_0)$. The boundary is the hyperplane where $\theta \cdot x + \theta_0 = 0$, with normal vector θ
  • Update rule (on mistake): $\theta \leftarrow \theta + y\, x$ and $\theta_0 \leftarrow \theta_0 + y$. Each misclassified point nudges θ so that point becomes correctly classified next time
  • Novikoff's mistake bound: if data is linearly separable with margin γ and radius R, the perceptron makes at most $(R/\gamma)^2$ mistakes — independent of dataset size
  • Not linearly separable → thrashes forever. No fixed point exists; θ keeps rotating in response to every mistake. Only kernels or a soft-margin loss can rescue this case