What one perceptron costs, and what a bank of them costs

STATEMENT

Count the parameters and the forward FLOPs of a single perceptron over $d$ inputs, then extend to a one-vs-rest bank of $K$ perceptrons. Evaluate at two realistic sizes.

GIVEN

A perceptron $\hat{y} = \mathrm{sign}(\langle\vec{w},\vec{x}\rangle + b)$ with $\vec{w} \in \R^{d}$. Count a multiply and an add as one FLOP each; ignore the sign, which is one comparison.

FIND

Parameters and FLOPs as functions of $d$; then of $d$ and $K$; then numbers at $(d, K) = (784, 10)$ and $(4096, 1000)$.

STRATEGY

Count the arithmetic in the definition literally rather than recalling a rule. The inner product is the only expensive part, and everything else is $O(1)$.

SOLUTION

Step 1 — one perceptron, parameters. The weight vector holds $d$ numbers and the bias holds one:

$N_{\text{params}} = d + 1$

Step 2 — one perceptron, FLOPs. The inner product $\sum_{j=1}^{d} w_j x_j$ needs $d$ multiplications and $d-1$ additions. Adding the bias is one more addition, bringing the additions to $d$. Total:

$N_{\text{FLOPs}} = d + d = 2d$

The convenient way to remember this: one multiply–add per parameter, and there are $d$ weights doing real work. That rule of thumb survives all the way to Chapter II.8, where the $2N$ per token in $C \approx 6ND$ is the same count.

Step 3 — a bank of $K$. One-vs-rest trains $K$ independent perceptrons, one per class, each over the same $d$ inputs. Nothing is shared:

$N_{\text{params}} = K(d+1), \qquad N_{\text{FLOPs}} = 2dK$

Equivalently the bank is one matrix $\mat{W} \in \R^{d\times K}$ and one bias row, so the forward pass is a single $(1\times d)(d\times K)$ product — the same object as a linear layer in Chapter I.5, arrived at from the other direction.

Step 4 — evaluate.

Check — sanity

FLOPs are about twice the parameters. $8{,}192{,}000 / 4{,}097{,}000 = 1.9995$, approaching $2$ as $d$ grows because the bias becomes negligible. If your ratio were near $1$ or near $4$, a multiply or an add went missing.

Both scale linearly in each variable separately. Ten times the classes gives ten times the cost; ten times the input width gives ten times the cost. There is no interaction term, because a one-vs-rest bank shares nothing between classes.

The $d = 784$, $K = 10$ figure is checkable against a known object. That is MNIST with a linear classifier, and $7{,}850$ is the familiar parameter count for exactly that model. Landing on a number that appears in the literature is weak evidence, but it is evidence.