Perceptron

Binary classification problems require partitioning an input feature space into two distinct regions. When two data clusters are linearly separable in two dimensions, there exists at least one separating hyperplane:

$w_1 x_1 + w_2 x_2 + b = 0 \quad \iff \quad \mathbf{w}^T \mathbf{x} + b = 0$

Guessing parameter values arbitrarily risks misclassifying points along the boundary corridor. Instead of manual trial and error, Frank Rosenblatt's perceptron provides an algorithmic mechanism that discovers an exact separating hyperplane directly from labeled training samples by iteratively correcting classification errors.

Weigh Then Threshold

At the core of the perceptron is an affine transformation followed by a Heaviside step activation function. For an input vector $\mathbf{x} = [1.0, 0.5]^T$, synaptic weights $\mathbf{w} = [0.6, -0.4]^T$, and scalar bias $b = +0.1$:

$z = \mathbf{w}^T \mathbf{x} + b = (1.0 \times 0.6) + (0.5 \times -0.4) + 0.1 = 0.60 - 0.20 + 0.10 = +0.50$

The scalar pre-activation $z$ is passed to the step threshold:

$\hat{y} = \Theta(z) = \begin{cases} 1 & \text{if } z \ge 0 \\ 0 & \text{if } z < 0 \end{cases}$

Because $z = +0.50 \ge 0$, the neuron outputs $\hat{y} = 1$ ("YES"). Geometrically, $z$ represents the signed, unnormalized distance from sample point $\mathbf{x}$ to the decision boundary line, with positive values placing the sample in the positive half-space.

Fix One Mistake

When the perceptron predicts correctly ($\hat{y} = y$), no parameters change. When it makes an error, the perceptron learning rule applies an immediate additive vector correction:

$\mathbf{w} \leftarrow \mathbf{w} + \eta (y - \hat{y}) \mathbf{x}, \quad b \leftarrow b + \eta (y - \hat{y})$

Consider an initial state $\mathbf{w} = [0, 0]^T, b = 0$ encountering a positive sample $\mathbf{x} = [1, 1]^T$ with true label $y = 1$. The model evaluates $\hat{y} = 0$, producing an error $y - \hat{y} = +1$. With learning rate $\eta = 1.0$:

$\mathbf{w}_{\text{new}} = [0, 0]^T + 1 \cdot [1, 1]^T = [1, 1]^T, \quad b_{\text{new}} = 0 + 1 = 1$

On the very next forward pass over that sample, the new score evaluates to $z = (1 \times 1) + (1 \times 1) + 1 = 3 \ge 0 \implies \hat{y} = 1$. Adding the input vector directly tilts the normal vector toward the misclassified sample, immediately repairing the prediction.

Tilt The Border

In feature space, the decision boundary line is orthogonal to the weight vector $\mathbf{w}$. When a weight update $\Delta \mathbf{w} = \eta \mathbf{x}^*$ occurs, the normal vector rotates toward the outlier sample point $\mathbf{x}^*$.

This rotation causes the decision boundary line $L_{\text{old}}$ to pivot into $L_{\text{new}}$, sweeping the misclassified sample across the threshold into the correct half-space. As long as the data is linearly separable, well-behaved margin gaps ensure that rotating to encompass an outlier does not displace previously settled points.

Four Fixes Converge

Albert Novikoff proved in 1962 that if a dataset is linearly separable with geometric margin $\gamma > 0$ and maximum sample radius $R = \max_i \|\mathbf{x}_i\|_2$, the perceptron algorithm is guaranteed to converge in a finite number of updates $k$:

$k \le \left( \frac{R}{\gamma} \right)^2$

Tracing four sequential updates on a four-sample problem illustrates this theorem in practice. The classifier begins at 2 of 4 (50%), improves to 3 of 4 on subsequent mistake corrections, and reaches a perfect 4 of 4 (100%) on step 4. Once all samples lie on their correct sides of the hyperplane, zero errors occur, zero updates trigger, and the algorithm halts permanently.

Size Your Steps

The learning rate parameter $\eta$ controls the magnitude of each geometric pivot:

• Clean, Separable Data ($\eta = 1.0$): Full unit steps take bold jumps through weight space. Because Novikoff's finite bound holds, large steps find a valid separating hyperplane in minimal training epochs.
• Noisy or Overlapping Data ($\eta \le 0.1$): When classes overlap or labels contain noise, strict linear separation is impossible. A full step of $1.0$ causes weights to thrash violently as single noisy points repeatedly yank the hyperplane back and forth. Reducing $\eta$ to $0.1$ dampens outlier shocks, stabilizing the boundary around an average consensus. Pairing small steps with the Pocket Algorithm—which archives the best weight vector encountered so far—prevents catastrophic forgetting.

Where It Breaks

In 1969, Marvin Minsky and Seymour Papert proved that a single-layer perceptron cannot solve the exclusive-OR (XOR) function:

$\text{XOR}(0,0) = 0, \quad \text{XOR}(0,1) = 1, \quad \text{XOR}(1,0) = 1, \quad \text{XOR}(1,1) = 0$

Because opposite diagonal corners share identical class labels, any single straight cut can achieve at most 3 out of 4 correct classifications (a 75% accuracy ceiling). The algebraic requirements $w_1 + b > 0$, $w_2 + b > 0$, and $b \le 0$ inevitably force $w_1 + w_2 + b > 0$, misclassifying $(1,1)$ as positive.

Overcoming this limitation requires a Multi-Layer Perceptron (MLP): introducing an intermediate hidden layer with non-linear activation functions bends the coordinate manifold, allowing multiple hyperplanes to combine into convex separating channels.

The Quick Version

• One artificial neuron learns a single straight linear decision boundary.
• Inputs are weighted, summed with bias ($z = \mathbf{w}^T \mathbf{x} + b$), and thresholded at zero.
• Each classification error shifts weights by adding the misclassified input vector.
• In feature space, updates rotate the boundary line to sweep outliers onto the correct side.
• Novikoff's theorem guarantees finite convergence ($k \le (R/\gamma)^2$) for linearly separable data.
• Use full steps ($\eta = 1.0$) for clean separable data and small steps ($\eta \le 0.1$) for noisy labels.
• Single perceptrons cannot solve XOR; non-linear hidden layers are required to bend boundaries.