Linear Classification

Linear Classification

1. Setup

Map $x → y ∈ \\{0,1\\}$ via linear score + threshold:

Decision boundary $w^{T}x+b=0$ is a hyperplane. Data is linearly separable if some hyperplane splits classes perfectly.

2. Loss Problem

0-1 loss is non-convex (NP-hard to optimize). Use surrogates: logistic loss, hinge (SVM), perceptron loss.

3. Three Linear Classifiers (preview)

Model	Loss	Output
Perceptron	max$(0, -y s)$	hard label
Logistic	$log(1+exp(-y s))$	probability
SVM	max$(0, 1-y s)$ + $λ||w||²$	max-margin label

4. Geometry

w is normal to boundary; ||w|| controls margin width
b shifts boundary; scaling w,b together changes loss but not boundary

5. Exam Points

• Define score + hyperplane — 3-5 marks, very frequent.
• Why surrogate loss needed — 3 marks, frequent.
• Separable vs non-separable sketch — 2 marks.