📐 Concept diagram

16-01 — The Perceptron Model

Phase: 16 — Neural Network Mathematics Subject: 16-01 Prerequisites: Phase 1 (linear equations), Phase 2 (vectors), Phase 3 (functions), Phase 4 (derivatives), Phase 10 (probability basics) Next subject: 16-02 — Activation Functions

Learning Objectives

By the end of this subject, you will be able to:

1. Explain the perceptron as a linear binary classifier and write its decision rule mathematically
2. Derive the geometric interpretation of a perceptron as a separating hyperplane
3. Implement the perceptron learning algorithm and explain why it converges for linearly separable data
4. Prove that a single perceptron cannot solve the XOR problem, motivating multi-layer networks
5. Relate the perceptron update rule to gradient descent on a surrogate loss

Core Content

1. What Is a Perceptron?

The perceptron, introduced by Frank Rosenblatt in 1958, is the simplest artificial neural network: a single neuron that makes binary decisions. It takes a vector of inputs, computes a weighted sum, and outputs +1 or −1 (or 1 or 0) based on whether that sum exceeds a threshold.

Formally, let x = [x₁, x₂, ..., xₙ]ᵀ be the input vector (with n features). The perceptron has:

• A weight vector w = [w₁, w₂, ..., wₙ]ᵀ
• A bias term b (sometimes folded into w by appending a constant-1 input)

The perceptron computes:

z = wᵀx + b = Σᵢ wᵢxᵢ + b

And then applies a step function (sign function) to produce the output:

ŷ = sign(z) = { +1 if z ≥ 0 { −1 if z < 0

(Some formulations use 1/0 instead of +1/−1. Both are equivalent up to a shift in the bias; we use +1/−1 because it makes the algebra cleaner.)

Why "perceptron"? Rosenblatt envisioned it as a simplified model of a biological neuron: inputs (dendrites) are weighted (synaptic strengths), summed in the cell body (soma), and if the sum exceeds a threshold, the neuron "fires" (outputs a signal). This is a drastic simplification — real neurons are vastly more complex — but it captures the core idea of thresholded computation.

2. Geometric Interpretation: The Decision Boundary

A perceptron draws a straight line (in 2D), a plane (in 3D), or a hyperplane (in n dimensions) that separates the input space into two halves. The decision boundary is all points where z = 0:

wᵀx + b = 0

This is the equation of a hyperplane. The weight vector w is normal (perpendicular) to this hyperplane. The bias b determines how far the hyperplane is from the origin.

Why is w normal to the hyperplane? Take any two points x₁ and x₂ on the hyperplane. Then:

wᵀx₁ + b = 0 and wᵀx₂ + b = 0 → wᵀ(x₁ − x₂) = 0

So w is orthogonal to every vector lying in the hyperplane — hence w is perpendicular to the hyperplane.

Intuition: The dot product wᵀx measures the projection of x onto w. Points that project further in the direction of w get positive scores; points projecting in the opposite direction get negative scores. The bias shifts the cutoff point.

Example in 2D: Let w = [2, 1]ᵀ, b = −3. The decision boundary is:

2x₁ + x₂ − 3 = 0 → x₂ = 3 − 2x₁

This is a line with slope −2, y-intercept 3. Points above the line get positive outputs; points below get negative.

3. The Perceptron Learning Algorithm

How do we find the right w and b? The perceptron learning algorithm is an online (one example at a time) algorithm:

Algorithm: 1. Initialize w ← 0 (or small random values), b ← 0 2. For each training example (x⁽ⁱ⁾, y⁽ⁱ⁾) where y⁽ⁱ⁾ ∈ {+1, −1}: - Compute prediction: ŷ = sign(wᵀx⁽ⁱ⁾ + b) - If ŷ ≠ y⁽ⁱ⁾ (misclassification): - w ← w + y⁽ⁱ⁾·x⁽ⁱ⁾ - b ← b + y⁽ⁱ⁾ 3. Repeat through the dataset until no misclassifications (or until a maximum number of epochs)

Why does this update make sense? Suppose y⁽ⁱ⁾ = +1 but we predicted −1. Then wᵀx⁽ⁱ⁾ + b < 0 (too negative). The update:

w ← w + x⁽ⁱ⁾, b ← b + 1

This increases wᵀx⁽ⁱ⁾ + b, making it more positive — pushing the prediction toward +1. Conversely, if y⁽ⁱ⁾ = −1 and we predicted +1, the update subtracts x⁽ⁱ⁾, pulling the score negative.

⚠️ THIS IS CRITICAL — The perceptron update is closely related to gradient descent on a specific loss function. Understanding this connection builds intuition for how all neural networks learn through gradient-based optimization.

Connection to gradient descent: Consider the perceptron loss (also called 0-1 loss proxy):

L(w, b) = −y⁽ⁱ⁾ · (wᵀx⁽ⁱ⁾ + b) · 1_{y⁽ⁱ⁾·(wᵀx⁽ⁱ⁾ + b) ≤ 0}

The gradient w.r.t. w is −y⁽ⁱ⁾x⁽ⁱ⁾ when misclassified. The update w ← w − η·∇L = w + η·y⁽ⁱ⁾x⁽ⁱ⁾ is exactly the perceptron update with learning rate η = 1.

4. The Perceptron Convergence Theorem

Theorem (Rosenblatt, 1958): If the training data is linearly separable, the perceptron learning algorithm converges to a separating hyperplane in finitely many steps.

Proof sketch: Let w be any separating weight vector with unit norm (||w|| = 1) and margin γ > 0 (meaning y⁽ⁱ⁾·wᵀ*x⁽ⁱ⁾ ≥ γ for all i). Let R = maxᵢ ||x⁽ⁱ⁾||.

After k updates (mistakes), we can show: 1. wᵀw₍ₖ₎ ≥ kγ (the weight vector aligns with w) 2. ||w**₍ₖ₎||² ≤ kR² (the norm grows slowly)

By Cauchy-Schwarz: wᵀw₍ₖ₎ ≤ ||w||·||w₍ₖ₎|| = ||w**₍ₖ₎||

So: kγ ≤ √(kR²) → k ≤ (R/γ)²

Therefore, at most (R/γ)² mistakes can be made before convergence.

Key takeaway: The number of mistakes is bounded, and the bound depends on the margin (larger margin → fewer mistakes) and the scale of the data.

Important caveat: If the data is NOT linearly separable, the perceptron algorithm never converges — it will keep making mistakes forever. This is the fundamental limitation of the perceptron.

5. The XOR Problem: Why Single Perceptrons Fail

The XOR (exclusive OR) function is:

Theorem: XOR is not linearly separable. No single perceptron can classify XOR correctly.

Proof: Suppose a perceptron with weights w₁, w₂, bias b could separate the four points. Then:

• (0,0) → 0: b < 0
• (0,1) → 1: w₂ + b ≥ 0
• (1,0) → 1: w₁ + b ≥ 0
• (1,1) → 0: w₁ + w₂ + b < 0

Adding inequalities (2) and (3): w₁ + w₂ + 2b ≥ 0. From (4): w₁ + w₂ + b < 0.

Subtract (4) from the sum of (2)+(3): (w₁ + w₂ + 2b) − (w₁ + w₂ + b) ≥ 0 − 0 → b ≥ 0. But from (1): b < 0. Contradiction!

Therefore, no such w₁, w₂, b exist. XOR is not linearly separable.

Geometric intuition: The four points form a square. If a line separates them, the line must put (0,0) and (1,1) on one side, and (0,1) and (1,0) on the other. But no line can do this because the positive points are diagonally opposite from the negative points — any line trying to separate them would need to "split" the square in an impossible way. Visually, try drawing a single straight line that separates the red (1) and blue (0) points on the XOR grid — you can't.

Consequence: This limitation motivated the development of multi-layer perceptrons (MLPs) — neural networks with one or more hidden layers. A two-layer network can solve XOR by composing two linear boundaries: one hidden neuron detects "at least one input is 1" and another detects "both inputs are 1", then the output neuron combines these.

Key Terms

• XOR problem

Worked Examples

Example 1: Geometric Interpretation

Problem: A perceptron has w = [3, −2]ᵀ and b = 1. Plot the decision boundary in 2D and determine which side corresponds to output +1.

Solution:

Step 1 — Write the decision boundary equation:

3x₁ − 2x₂ + 1 = 0 → 2x₂ = 3x₁ + 1 → x₂ = 1.5x₁ + 0.5

Step 2 — Plot: This is a line with slope 1.5 passing through (0, 0.5).

Step 3 — Determine sides: Test a point, say (0,0):

z = 3·0 − 2·0 + 1 = 1 ≥ 0 → output +1

So the half-plane containing the origin gives +1.

Step 4 — The normal vector w = [3, −2]ᵀ points toward the +1 region.

Answer: The line x₂ = 1.5x₁ + 0.5 separates the plane. Points with 3x₁ − 2x₂ + 1 ≥ 0 (including the origin) get +1; the other side gets −1.

Example 2: Perceptron Learning by Hand

Problem: Train a perceptron on this dataset (using +1/−1 labels):

This is an AND-like function (y = +1 only when x₁ = 1). Start with w = [0, 0]ᵀ, b = 0.

Solution:

Epoch 1:

• (0,0,−1): z = 0·0 + 0·0 + 0 = 0 → ŷ = +1. Misclassified (should be −1)! Update: w ← [0,0] + (−1)·[0,0] = [0,0], b ← 0 − 1 = −1
• (0,1,−1): z = 0·0 + 0·1 − 1 = −1 → ŷ = −1. Correct. No update.
• (1,0,+1): z = 0·1 + 0·0 − 1 = −1 → ŷ = −1. Misclassified! Update: w ← [0,0] + (+1)·[1,0] = [1,0], b ← −1 + 1 = 0
• (1,1,+1): z = 1·1 + 0·1 + 0 = 1 → ŷ = +1. Correct. No update.

Epoch 2:

• (0,0,−1): z = 1·0 + 0·0 + 0 = 0 → ŷ = +1. Misclassified! Update: w ← [1,0] + (−1)·[0,0] = [1,0], b ← 0 − 1 = −1
• (0,1,−1): z = 1·0 + 0·1 − 1 = −1 → ŷ = −1. Correct.
• (1,0,+1): z = 1·1 + 0·0 − 1 = 0 → ŷ = +1. Correct! ✓
• (1,1,+1): z = 1·1 + 0·1 − 1 = 0 → ŷ = +1. Correct!

Epoch 3: Check all — all correct!

Final weights: w = [1, 0]ᵀ, b = −1

Verify: Decision boundary: x₁ − 1 = 0 → x₁ = 1. This is a vertical line at x₁ = 1. Points with x₁ ≥ 1 get +1, the rest get −1. This perfectly separates the data.

Example 3: Proving Non-Linear Separability

Problem: Prove that the following 2D dataset is not linearly separable:

(This is the "XNOR" or equality function — y = +1 when x₁ = x₂.)

Solution:

Suppose there exist w₁, w₂, b such that sign(w₁x₁ + w₂x₂ + b) = y for all four points.

From the four points we get: (1) w₁(−1) + w₂(−1) + b ≥ 0 → −w₁ − w₂ + b ≥ 0 (2) w₁(−1) + w₂(+1) + b < 0 → −w₁ + w₂ + b < 0 (3) w₁(+1) + w₂(−1) + b < 0 → w₁ − w₂ + b < 0 (4) w₁(+1) + w₂(+1) + b ≥ 0 → w₁ + w₂ + b ≥ 0

Add (1) and (4): (−w₁ − w₂ + b) + (w₁ + w₂ + b) ≥ 0 → 2b ≥ 0 → b ≥ 0

Add (2) and (3): (−w₁ + w₂ + b) + (w₁ − w₂ + b) < 0 → 2b < 0 → b < 0

Contradiction! b cannot be both ≥ 0 and < 0. Therefore, no such w₁, w₂, b exist.

Geometric intuition: The +1 points are on one diagonal of the square and the −1 points on the other diagonal. No straight line can separate opposite corners from each other.

Practice Problems

(Answers are below. Try each problem before checking.)

Problem 1: A perceptron has weights w = [−1, 2]ᵀ and bias b = −1. Compute the output for input x = [3, 1]ᵀ.

Problem 2: Find the equation of the decision boundary for the perceptron with w = [4, −1, 2]ᵀ and b = 5. What is the geometric shape of this boundary in 3D?

Problem 3: Apply one epoch of the perceptron algorithm to the dataset below with initial w = [0, 0]ᵀ, b = 0. Show all updates.

Problem 4: Show that the 3D dataset below is linearly separable by finding weights and bias manually (inspection is fine).

Problem 5: Prove that for a perceptron with zero bias (b = 0), if x is classified as +1, then any positive scalar multiple cx (c > 0) is also classified as +1. What is the geometric interpretation?

Problem 6: Consider the OR function (y = +1 if either x₁ = 1 OR x₂ = 1, else −1). Write a perceptron that implements OR and verify it classifies all four input combinations correctly.

Problem 7: The perceptron convergence theorem gives a mistake bound of (R/γ)². For the dataset in Example 2, compute R and γ (for w* found by the algorithm) and verify that fewer mistakes were made than this bound.

Summary

1. A perceptron is a linear classifier: ŷ = sign(wᵀx + b), dividing input space with a hyperplane whose normal is w.
2. The perceptron learning algorithm updates weights only on mistakes: w ← w + y·x, moving the boundary toward correct classification.
3. The perceptron convergence theorem guarantees finite convergence when data is linearly separable, with a mistake bound of (R/γ)².
4. The XOR problem demonstrates the fundamental limitation: a single perceptron cannot solve non-linearly separable problems, motivating multi-layer networks.
5. The perceptron update rule is a precursor to gradient descent — it moves weights in the direction that reduces a surrogate loss function.

Pitfalls

• Expecting convergence on non-linearly separable data: The perceptron algorithm cycles indefinitely when the data is not linearly separable. There is no signal that separation is impossible — it just keeps making mistakes forever. Always check linear separability before committing to a perceptron. For non-separable data, use logistic regression, SVM with slack variables, or a multi-layer network. A quick check: if the dataset has XOR-like structure, a single perceptron cannot solve it.
• Confusing the perceptron update with proper gradient descent: The perceptron update $\mathbf{w} \leftarrow \mathbf{w} + y\mathbf{x}$ resembles gradient descent on a surrogate loss, but it is not SGD on a well-defined objective with a learning rate. The effective learning rate is always 1, the loss is not differentiable, and there is no convergence guarantee to a unique minimum (any separating hyperplane works). Don't transplant intuitions from SGD directly to the perceptron algorithm.
• Not normalizing input features before training: The perceptron convergence theorem's mistake bound is $(R/\gamma)^2$ where $R = \max |\mathbf{x}_i|$. If features are on wildly different scales (e.g., $x_1 \in [0, 1]$, $x_2 \in [0, 10^6]$), $R$ is dominated by $x_2$ and the bound becomes enormous. Normalizing features to similar ranges tightens the bound and dramatically speeds up convergence.
• Ignoring the margin when evaluating convergence speed: Two linearly-separable datasets with the same $R$ can have vastly different convergence behavior depending on the margin $\gamma$. A narrow margin (points close to the boundary) means $(R/\gamma)^2$ is large and convergence is slow. If the perceptron seems to be making progress but taking many epochs, check whether a wider-margin separator exists — the data might be nearly non-separable.
• Forgetting the bias term or misapplying the bias trick: The bias $b$ is essential — without it, the decision boundary must pass through the origin, which severely limits the set of learnable functions. When using the bias trick (augmenting $\mathbf{x}$ with a constant 1), remember that the augmented weight's update includes the bias update. Mixing explicit bias with the bias trick (double-counting $b$) is a common implementation bug.

Quiz

Q1: A perceptron has w = [2, −3]ᵀ, b = 4. What is its output for input x = [1, 2]ᵀ?

A) +1 B) −1 C) 0 D) Cannot determine

Q2: What does the weight vector w represent geometrically?

A) The direction of the decision boundary line B) A vector perpendicular (normal) to the decision boundary C) The distance from the origin to the decision boundary D) The slope of the decision boundary

Q3: In the perceptron update rule w ← w + y⁽ⁱ⁾x⁽ⁱ⁾, why do we add y⁽ⁱ⁾x⁽ⁱ⁾ when a positive example is misclassified as negative?

A) To rotate the decision boundary B) To increase the activation for that example, making it more positive C) To decrease the norm of the weight vector D) To add the example to a support vector set

Q4: Why can't a single perceptron solve the XOR problem?

A) XOR requires 3 inputs but perceptrons only accept 2 B) The XOR data points are not linearly separable C) The perceptron algorithm doesn't converge for more than 3 data points D) XOR requires real-valued outputs, not binary

Q5: The perceptron convergence theorem states that the number of mistakes is bounded by (R/γ)², where γ is the margin. What happens to this bound if the data points are very spread out (large R)?

A) The bound decreases — convergence is faster B) The bound increases — convergence may be slower C) The bound stays the same D) The algorithm may never converge regardless of separability

Q6: Suppose we add a bias trick: augment each input with a constant 1, so x̃ = [x; 1] and w̃ = [w; b]. What is the decision boundary in terms of w̃ and x̃?

A) w̃ᵀx̃ = 1 B) w̃ᵀx̃ = b C) w̃ᵀx̃ = 0 D) w̃ᵀx̃ = ||w̃||

Q7: What is the key limitation of the perceptron that multi-layer networks overcome?

A) Perceptrons can only process binary inputs B) Perceptrons can only learn linear decision boundaries C) Perceptrons cannot have a bias term D) Perceptrons require the data to be normalized

Next Steps

Move on to 16-02 — Activation Functions to learn about the non-linear functions (sigmoid, tanh, ReLU) that transform linear perceptrons into powerful multi-layer neural networks.