The Perceptron

Source: Unit 2 §5

A perceptron takes a vector of real-valued inputs, computes a linear combination of them, and outputs +1 if the result exceeds a threshold and −1 (or 0) otherwise. It is the single artificial neuron, and everything later in the course is built from it.

The bias is not special: fixing x0 = 1 turns the threshold θ into an ordinary weight w0 = −θ, so the whole unit is one dot product plus a step.

≡FactsWhere the perceptron came from

• Frank Rosenblatt (1958) proposed the classical perceptron, more general than the McCulloch-Pitts neuron.
• The two key additions were numerical weights on the inputs and a learning mechanism for those weights. Inputs were no longer limited to Boolean values.
• Minsky and Papert (1969) refined and analysed it - and found the limitation in §"The XOR problem" below.

The perceptron equation

With weights $w$, inputs $x$, bias $w_0 = -\theta$ and $x_0 = 1$:

$$y = \begin{cases} 1 & \text{if } \sum_i w_i x_i \ge 0 \\ 0 \text{ (or } -1) & \text{otherwise} \end{cases}$$

Writing the two as vectors $w = [w_0 \ldots w_n]$ and $x = [x_0 \ldots x_n]$ collapses the sum into a dot product:

$$w \cdot x = w^\mathsf{T} x = \sum_i w_i x_i \qquad y = 1 \text{ if } w^\mathsf{T} x \ge 0, \text{ else } 0$$

◎Exam cueWhy is worth the trouble

Setting $x_0 = 1$ and $w_0 = -\theta$ folds the threshold into the weight vector. After that there is no separate threshold to learn: the same update rule trains the bias as trains every other weight.

Geometric interpretation

We are looking for the line (in 2-D) or hyperplane (in general) $w^\mathsf{T} x = 0$ that cuts the input space into two halves. Every point $x$ on that boundary satisfies $w^\mathsf{T} x = 0$, so the angle $\alpha$ between $w$ and any such $x$ is $90°$ - the weight vector is perpendicular to the decision boundary.

Every x on the boundary satisfies wᵀx = 0, and a zero dot product means a 90° angle - which is why w always points straight out of the boundary.

A perceptron represents linear Boolean functions

A single perceptron produces a linear decision surface, so it can represent AND, OR, NAND and NOR.

Function	w₀ (bias)	w₁	w₂
AND	−0.8	0.5	0.5
OR	−0.3	0.5	0.5

Worked example: learning logical OR

Write the perceptron inequality $w_0 + w_1 x_1 + w_2 x_2 \ge 0$ for every row of the truth table that should output 1, and the row that should output 0 for the opposite inequality.

(x₁, x₂)	OR	Constraint
(0,0)	0	w₀ < 0
(1,0)	1	w₁ ≥ −w₀
(0,1)	1	w₂ ≥ −w₀
(1,1)	1	w₁ + w₂ ≥ −w₀

Any weights satisfying all four inequalities implement OR - for instance $w_0 = -0.3$, $w_1 = w_2 = 0.5$, the values in the table above.

One straight line puts the three 1s on one side and the single 0 on the other, so one perceptron is enough.

◎Exam cueThe movie-buff intuition

Take $x_1$ = actor, $x_2$ = genre, $x_3$ = director for the question "should I watch this film?". Past data says the director matters most, so that input gets the high weight - a good director can cross the threshold $\theta$ on its own even when the actor and genre are unremarkable. A true movie buff has $\theta = 0$ and watches anything.

The perceptron training rule

Each weight is nudged by the error $(t - o)$:

$$w_i \leftarrow w_i + \eta (t - o) x_i$$

Symbol	Meaning
xᵢ	the input
wᵢ	the weight for xᵢ
t	target output for the current example
o	actual output the perceptron produced
η	learning rate - small, for example 0.1

The perceptron is learning the linear surface $h(x) = w_0 + w_1 x_1 + w_2 x_2 + \ldots$

→StepsWhat one training example does

1. Present the example and compute the actual output $o$.
2. If $t = o$ the example is already correct, $(t - o) = 0$, and no weight changes.
3. If $t \ne o$, every weight moves by $\eta (t - o) x_i$, nudging the boundary toward the correct answer for this example.
4. Repeat over the training set until nothing changes.

⚠GotchaConvergence is conditional

The perceptron training rule converges only if the data is linearly separable. On data that is not, it never settles - which is exactly the motivation for the delta rule on the next page.

The XOR problem: the perceptron's limitation

XOR sends (0,0) → 0, (0,1) → 1, (1,0) → 1, (1,1) → 0. Plot those four points and the trouble is immediate.

The two 1s sit on one diagonal and the two 0s on the other. No straight line separates them, so no single perceptron can represent XOR.

⚠GotchaThe historical cost of this one picture

If the data is not linearly separable, like XOR, a single perceptron is not enough. Minsky and Papert's demonstration of this is precisely why the field moved to multilayer networks.