Perceptrons and the Geometry of Linear Separation

In two dimensions, the equation w·x+b=0 defines a line. In higher dimensions, the same equation defines a hyperplane.

Points near a linear boundary can flip class under a small input change, while points farther away have a larger geometric margin under the chosen scaling.

Distance from the boundary is not confidence. A perceptron does not automatically produce a calibrated uncertainty estimate, and the gap between a confident-looking score and a trustworthy probability has been measured rather than merely warned about. Guo and colleagues opened a 2017 paper with the finding itself: “We discover that modern neural networks, unlike those from a decade ago, are poorly calibrated.” Accuracy had risen. The correspondence between the score and the frequency of being right had fallen. The usual fix is to recalibrate afterwards, and a large-scale 2019 benchmark across classification tasks, from Ovadia and colleagues, tested what happens to that fix under dataset shift. It degrades. The repair does not survive the conditions that make you reach for it.

A raw margin is also not comparable between two networks. Rescaling the weights rescales the margin. No prediction changes. Bartlett, Foster and Telgarsky addressed exactly that in 2017. Their generalization bound “scales with their margin-normalized "spectral complexity": their Lipschitz constant, meaning the product of the spectral norms of the weight matrices, times a certain correction factor”. They tested it on “a standard AlexNet network trained with SGD on the MNIST and CIFAR10 datasets, with both original and random labels”. They found that “the bound, the Lipschitz constants, and the excess risks are all in direct correlation”. A margin starts carrying information once it is measured against a scale. That scale is the model that produced it.

The architecture can succeed only when its available boundaries match the data geometry. How far a single hyperplane gets you is a quantity you can compute before you fit anything.

Cover settled the count in 1965. For N points in general position in d-dimensional space, the number of homogeneously linearly separable dichotomies is exactly C(N,d) = 2·Σ_{k=0}^{d-1} binom(N-1,k). His abstract states the consequence: “It is shown that a family of surfaces having d degrees of freedom has a natural separating capacity of 2d pattern vectors, thus extending and unifying results of Winder and others on the pattern-separating capacity of hyperplanes.” Separating capacity is a budget, not a mood. It is 2d pattern vectors for d degrees of freedom, and the probability of separability collapses sharply once the number of patterns passes twice the number of dimensions. Gardner and Derrida reached the same critical capacity from statistical mechanics in 1988: α_c(0)=2, that is, 2N random patterns for N weights.

So the two cases below are not two temperaments a dataset might have. Below roughly 2d points a linear rule will very likely separate labels even when those labels are random, which is a warning about what separability proves. Above it, the rule runs out of room. No amount of training returns any.

The classic algorithm reacts to a misclassified example rather than differentiating a smooth loss. On separable data the number of reactions is capped before training starts.

Novikoff's 1962 convergence theorem caps the updates on a linearly separable sequence at r²/ρ², the squared ratio of the data radius to the margin. That bound does not depend on the dimension of the inputs. Freund and Schapire restated it in 1999 and opened their paper with the guarantee: “Block (1962), Novikoff (1962) and Minsky and Papert (1969) have shown that if the data are linearly separable, then the perceptron algorithm will make a finite number of mistakes, and therefore, if repeatedly cycled through the training set, will converge to a vector which correctly classifies all of the examples.” Mohri and Rostamizadeh restate the same result in 2013.

Read r²/ρ² backwards and it says what the update buys and what it does not. Double the margin and the mistake budget falls by a factor of four. Add a thousand dimensions and the budget does not move at all. Remove separability and there is no guarantee left to weaken, because ρ no longer exists. XOR is not a slow case. It is a different kind of case.

XOR assigns a positive label when two binary inputs differ, and its four points cannot be separated by one straight line. What repairs this is not depth in itself but the nonlinearity inside the hidden layer. That is an if-and-only-if, not a rule of thumb.

A hidden layer buys universality only because its activation is not a polynomial. Leshno and colleagues proved that in 1992: “We show that most of all the characterizations that were reported thus far in the literature are special cases of the following general result: a standard multilayer feedforward network with a locally bounded piecewise continuous activation function can approximate any continuous function to any degree of accuracy if and only if the network's activation function is not a polynomial.” Cybenko had proved one direction three years earlier, for continuous sigmoidal activations.

The "only if" is the half that matters here. A hidden layer with a linear activation is a polynomial one. It composes back down to a single affine map, and the four XOR points end up exactly where they started. Stacking such layers ten deep changes the parameter count and nothing else.

Before training a deep model, fit a linear baseline on the same representation. Strong performance may reveal that the task is already simple, or that leakage has made it suspiciously easy.

Weak performance does not prove a neural network will succeed. It only establishes one thing. Under the current features, a single linear rule is insufficient.

Whether the deeper model then wins is an empirical question. On one large family of data the answer has stayed stubborn. In 2022 Grinsztajn and colleagues benchmarked standard and recent deep-learning methods against tree-based models such as XGBoost and Random Forests. The test bed was “a standard set of 45 datasets from varied domains with clear characteristics of tabular data”. Their finding: “tree-based models remain state-of-the-art on medium-sized data” — around ten thousand samples — “even without accounting for their superior speed”.

The same result arrives from a literature with no stake in the machine-learning argument. A 2019 systematic review in the Journal of Clinical Epidemiology screened 927 studies and read 71 of them. Across 145 comparisons of logistic regression against machine learning at low risk of bias, the difference in logit(AUC) was 0.00, with a 95% confidence interval running from −0.18 to 0.18. The conclusion is four words longer than it needs to be: “We found no evidence of superior performance of ML over LR.” The next year the same journal published a 6,762-person Asian cohort. Logistic regression was the best model for chronic kidney disease, at an AUC of 0.905, and for diabetes, at 0.768. Every difference from the five machine-learning models was under 1% and not statistically significant.

A simple baseline is not always a step on the way to the real model. Sometimes it is the result — an interval containing zero, twice, in two fields.