Perceptron

Perceptron

1. Rule

Online linear classifier. Predict $y_{pred} = sign(w^{T}x)$. On mistake with true $y ∈ {+1,-1}$:

Only mistakes cause updates. $η=1$ standard.

2. Algorithm

w = 0
repeat until no mistakes (if separable):
  for each (x,y): if y (w^{T}x) ≤ 0: w = w + y x

3. Convergence

If data separable with margin $γ$, perceptron stops after bounded mistakes (mistake bound scales as $1/γ²$). If not separable, it cycles — use averaged / voted version or stop early.

4. Limits

Learns only linear boundaries (fails XOR). No probabilities. Sensitive to order and scale → standardize, shuffle.

5. Exam Points

• Write update rule + trace 2-3 steps — 5-7 marks, very frequent.
• State convergence condition (separable) — 3 marks, frequent.
• XOR failure reason — 2 marks, frequent.