← Appropriate Problems for NN Learning | Next → Multilayer Networks and Backpropagation
A perceptron is a single computational unit that takes a vector of real-valued inputs x₁, x₂, …, xₙ, computes their weighted sum, and outputs +1 if the sum exceeds a threshold, -1 otherwise.
Output o(x₁, ..., xₙ):
= +1 if w₀ + w₁x₁ + w₂x₂ + ... + wₙxₙ > 0
= -1 otherwise
Each wᵢ is a real-valued weight. The quantity −w₀ is the threshold that the weighted sum must exceed.
Using a constant input x₀ = 1 (called the bias input), this simplifies to:
o(x) = sgn( w · x )
= sgn( w₀x₀ + w₁x₁ + w₂x₂ + ... + wₙxₙ )
where sgn returns +1 for positive values and -1 for negative values.
Inputs Weights Aggregation Output
x₁ ─────── w₁ ─────┐
x₂ ─────── w₂ ─────┤──→ Σ wᵢxᵢ ──→ sgn(·) ──→ +1 or -1
x₃ ─────── w₃ ─────┘
x₀=1 ───── w₀ (bias)
Learning a perceptron means choosing the weight vector w = (w₀, w₁, …, wₙ).
A perceptron represents a hyperplane decision surface in n-dimensional space. It outputs:
w · x = 0Sets of examples that can be correctly separated this way are called linearly separable.
| Function | Weights (example) | Notes |
|---|---|---|
| AND | w₀ = −0.8, w₁ = w₂ = 0.5 | Both inputs must be 1 |
| OR | w₀ = −0.3, w₁ = w₂ = 0.5 | At least one input must be 1 |
| NAND | Reverse signs of AND | |
| NOR | Reverse signs of OR | |
| m-of-n | All wᵢ = 0.5, threshold at m − 0.5 | At least m of n inputs true |
XOR outputs 1 if and only if x₁ ≠ x₂:
x₂
1 │ − +
│
0 │ + −
└──────────── x₁
0 1
The four points (0,0), (0,1), (1,0), (1,1) with labels (−1, +1, +1, −1) cannot be separated by any straight line. Therefore no perceptron can correctly classify XOR.
This limitation — shown by Minsky & Papert (1969) — led to the first “AI winter” for neural networks. Multilayer networks were later developed to overcome it.
Every boolean function can be represented by a two-layer network of perceptrons:
Start with random weights; iteratively update on each misclassified example:
Δwᵢ = η × (t − o) × xᵢ
wᵢ ← wᵢ + Δwᵢ
where:
PERCEPTRON-TRAINING(training_examples, η):
Initialize: w ← small random values
Repeat until convergence:
For each (x, t) in training_examples:
o ← sgn(w · x)
For each weight wᵢ:
wᵢ ← wᵢ + η × (t − o) × xᵢ
| Situation | (t − o) | Effect |
|---|---|---|
| Correctly classified | 0 | No weight change |
| Output −1, target +1 | +2 | Weights on active inputs increase → pushes sum positive |
| Output +1, target −1 | −2 | Weights on active inputs decrease → pushes sum negative |
Perceptron Convergence Theorem: If the training examples are linearly separable and the learning rate η is sufficiently small, the perceptron training rule converges to a correct weight vector in finite steps.
If the data are not linearly separable, the rule may cycle indefinitely. This is what motivates the delta rule.
The perceptron training rule fails for non-linearly separable data. The delta rule uses gradient descent to find the best-fit weight vector — even when perfect classification is impossible.
The delta rule is the direct foundation for the Backpropagation algorithm.
Instead of the hard threshold, use a linear unit with output:
o(x) = w · x (just the weighted sum, no threshold)
Define training error over all examples D:
E(w) = (1/2) × Σ (tᵈ − oᵈ)²
d ∈ D
For a linear unit, this error surface is a smooth bowl (paraboloid) with a single global minimum. Gradient descent always finds it.
E(w)
│ ╱
│ ╱ ← error surface (parabola in 2D)
│ ╱
│ ╱
│ ╱ ← global minimum
│╱___________________________ w
The gradient (slope) of E with respect to each weight wᵢ is:
∂E / ∂wᵢ = − Σ (tᵈ − oᵈ) × xᵢᵈ
d ∈ D
Gradient descent moves in the direction of steepest descent (negative gradient):
Δwᵢ = −η × (∂E / ∂wᵢ)
= η × Σ (tᵈ − oᵈ) × xᵢᵈ
d ∈ D
GRADIENT-DESCENT(training_examples, η):
Initialize: w ← small random values
Repeat until convergence:
Δwᵢ ← 0 for all i
For each (x, t) in training_examples:
o ← w · x ← linear unit output
For each wᵢ:
Δwᵢ ← Δwᵢ + η × (t − o) × xᵢ
For each wᵢ:
wᵢ ← wᵢ + Δwᵢ ← update after ALL examples seen
Convergence: Always reaches global minimum for linear units, given η small enough.
Update weights after each individual example instead of summing first:
For each (x, t) in training_examples:
o ← w · x
wᵢ ← wᵢ + η × (t − o) × xᵢ ← immediate update per example
| Property | Batch | Stochastic |
|---|---|---|
| Updates after | All examples | Each example |
| Follows true gradient | ✅ Yes | ✗ Approximation |
| Speed per update | Slower | Faster |
| Can escape local minima | Less likely | More likely |
| Used in practice | Less common | More common |
The per-example update:
Δwᵢ = η × (t − o) × xᵢ
Also called: LMS rule, Adaline rule, Widrow-Hoff rule.
Always converges toward the minimum-error hypothesis, even when data is not linearly separable.
| Property | Perceptron Training Rule | Delta Rule |
|---|---|---|
| Unit output | sgn(w · x) — thresholded | w · x — linear |
| Converges when | Data is linearly separable | Always |
| Converges to | Perfect classifier | Min-error approximation |
| Foundation for | — | Backpropagation |
Both rules use the same update formula Δwᵢ = η(t − o)xᵢ, but o is defined differently:
o = sgn(w · x) → hard thresholdo = w · x → no threshold| Expression | Meaning |
|---|---|
o = sgn(w · x) | Perceptron output |
E(w) = (1/2) Σ (t − o)² | Squared error over training set |
Δwᵢ = η(t − o)xᵢ | Perceptron / Delta rule weight update |
Δw = −η ∇E(w) | Gradient descent general form |
← Appropriate Problems for NN Learning | Next → Multilayer Networks and Backpropagation