Classical versus deep learning: models, architectures and their cost

Part AA machine-learning primer

If you have trained models before, skim this part and go to Part B. If you have not, read it carefully: it is written for engineers and scientists who know calculus and linear algebra but have not studied machine learning.

3.1Learning from examples

In supervised learning we are given a training set of N examples {(x_i, y_i)}: inputs (feature vectors, windows, spectrograms) and the correct outputs (labels). We choose a model family f(x; θ) and a loss function ℓ(ŷ, y) that measures how bad a prediction ŷ is when the truth is y. Training means solving

The first term is the average loss on the training data (the empirical risk); the second is an optional regulariser that prefers simpler parameter values (for example R(θ) = ‖θ‖², "weight decay"), weighted by a hyper-parameter λ chosen by the engineer, not learned.

Two losses cover most of this course:

• Regression (predict a number): mean squared error, ℓ = (ŷ − y)².
• Classification (predict one of C classes): the model outputs C scores ("logits") z_1…C, turned into probabilities by the softmax p_c = e^z_c / Σ_k e^z_k, and the loss is the cross-entropy ℓ = −log p_y — small when the model puts high probability on the correct class. (The distillation section on page 2 reuses the softmax with a "temperature".)

Unsupervised learning drops the labels and looks for structure — clusters, low-dimensional directions (PCA in Session 2), or a model of "normal" data against which anomalies stand out. Self-supervised learning manufactures labels from the data itself (predict a masked part of the input) and is how large models are pre-trained before being fine-tuned with few labels. Reinforcement learning learns from rewards obtained by acting; it is rare on embedded devices because it needs many, sometimes unsafe, trials.

3.2Generalisation and honest evaluation

Minimising the training loss is easy; the goal is low loss on new data. A model with enough capacity can memorise its training set — including the noise in it — and do badly on anything else. This is overfitting; its opposite, a model too simple to capture the real pattern, is underfitting.

Which model generalises well from limited data depends on its inductive bias: the assumptions built into the model family before it sees any data — that the decision boundary is linear, that nearby inputs have similar outputs, that a pattern means the same thing wherever it occurs in an image. A good inductive bias for the task is worth a great deal of data, which is why a convolutional network learns images from far fewer examples than a fully connected one, and why hand-designed features can let a tiny classical model compete.

Because training error is an optimistic estimate of real-world error, data is divided before any modelling starts. The model's parameters are fitted on the training set; every choice the engineer makes — features, model family, hyper-parameters, when to stop training, which checkpoint to deploy, how far to compress — is made by looking at the validation set; the test set is used once, at the end, to report the number. With small datasets, k-fold cross-validation rotates the validation role across the data so that every example is used for both fitting and validation.

The trade-off between under- and overfitting has a classical formalisation, the bias–variance decomposition, which appears with the tree ensembles in Part B (Fig 3.11). For now the practical rules are: more data reduces overfitting, and so do regularisation, early stopping and data augmentation.

3.3Optimisation: gradient descent

For a model with millions of parameters there is no closed-form solution to the training problem. Instead we start from random parameters and repeatedly move them a small step in the direction that reduces the loss fastest — against the gradient ∇_θL, the vector of partial derivatives of the loss with respect to each parameter:

The step size η is the learning rate, the single most important hyper-parameter in deep learning. In practice the gradient is estimated on a small random mini-batch of examples rather than the whole training set (stochastic gradient descent, SGD), which makes each step cheap and adds a useful amount of noise; adaptive variants such as Adam scale the step per parameter. One pass over the training set is an epoch; training typically takes tens to hundreds of epochs.

The widget makes two points that matter later in the course. First, the learning rate has a hard upper limit set by the steepest direction of the loss surface; beyond it, training diverges. Second, when the surface is much steeper in some directions than others (a large condition number κ), progress in the shallow directions is slow. Unscaled input features are one cause of a large κ — which is why the normalisation of Session 2 makes training faster, not just more accurate. Quantization-aware training (page 2) is gradient descent through a rounding function, with its own complications.

3.4Measuring a classifier

A classifier that outputs a score is turned into a decision by a threshold. Moving the threshold trades false alarms against missed events, and how good a trade is available depends on how well the classes are separated and — crucially for embedded detection tasks — on how rare the events are. Precision depends on prevalence; recall does not. A detector evaluated on a balanced test set and deployed where events are a hundred times rarer will see its precision collapse without any change to the model.

Sweeping the threshold over all values traces two standard curves. The ROC curve plots recall (the true-positive rate) against the false-positive rate FP/(FP+TN); the area under it, AUC, is the probability that a random positive scores higher than a random negative, and is 0.5 for guessing and 1 for a perfect ranking. The precision–recall curve plots precision against recall and, unlike the ROC curve, reacts to class imbalance. The widget's d′ ("d-prime") is the distance between the two class means in units of their standard deviation — a one-number summary of how separable the scores are. Finally, a classifier is calibrated if, among all inputs to which it assigns probability 0.8, about 80 % are positive; a reliability diagram plots the predicted against the observed frequency, and the expected calibration error is the average gap between them. The section below develops these ideas.

3.5Calibration and the right metric

A model's score is not a probability unless it was trained or post-processed to be one. SVM decision values certainly are not; boosted ensembles are typically over-confident; random forests are under-confident near the extremes. Two standard remedies: Platt scaling fits a one-dimensional logistic regression p = σ(as + b) to the scores on held-out data; isotonic regression fits a non-decreasing step function, which is more flexible and needs more data. Measure the result with a reliability diagram and the expected calibration error, not with accuracy.

Calibration is not a cosmetic step in this course: the cascade of §1.8 requires a threshold with a known operating point, and thresholds are only transferable across deployments if the scores are calibrated.

Metrics for always-on detection. Accuracy is meaningless when the positive class occupies 0.1 % of windows. Use the precision–recall curve rather than the ROC curve (the ROC's false-positive rate is diluted by the enormous negative class), and report the operating point in application terms: false alarms per hour at a stated recall is the standard in keyword spotting and acoustic event detection, because it is the quantity the user experiences.

Part BClassical models under constraints

"Classical" here means everything that is not a deep neural network: linear models, kernel methods, nearest neighbours, decision trees and their ensembles. On microcontrollers they remain widely deployed, and for good reasons.

3.6The regime question

Classical models win when at least one of these holds:

• Little data. With a few hundred labelled windows, a regularised linear model or a small forest generalises better than a network you cannot regularise into submission.
• Extreme memory limits. A depth-6 boosted ensemble of 30 trees fits in a few kilobytes of flash and needs almost no RAM.
• Deterministic, data-independent latency. A tree's latency varies with the path taken; a linear model's does not vary at all. In hard real-time contexts this matters more than mean latency.
• Interpretability or certification. Medical and automotive certification regimes are far more comfortable with a model whose decision can be printed as a rule.
• Good handcrafted features already exist. If domain physics gives you the right 20 features, the representation-learning advantage of a network evaporates.

They lose when the raw input is high-dimensional and the useful features are unknown — images, raw audio, and anything where the relevant structure is compositional.

3.7Inference-time cost models depth

For D features, C classes, N training samples:

Table 3.1 — Inference cost of classical models. Note the structural difference from neural networks: two of these families cost comparisons, not multiplications, and therefore do not benefit from a MAC accelerator at all. A device chosen for its NPU may run a forest no faster than a device without one.

3.8Support vector machines, properly

The embedded catch. Prediction is f(x) = Σ_i∈SV α_i y_i k(x_i, x) + b. Every support vector must be stored and evaluated at inference time. For noisy problems the number of support vectors grows roughly linearly with the training-set size, so a kernel SVM trained on 50 000 windows can end up with thousands of stored D-dimensional vectors — a model larger than the CNN it was supposed to replace. Students who have only used scikit-learn on small data are usually surprised by this.

3.9Trees, forests and boosting

A decision tree recursively partitions the feature space by axis-aligned splits chosen to maximise impurity reduction. With class proportions p_c in a node, the two standard impurities are

and a split's quality is the parent impurity minus the sample-weighted mean of the children's. Gini is cheaper and behaves almost identically; entropy is preferred when you want the information-theoretic interpretation. Trees are high-variance: small data perturbations change the top split and thus everything below it.

Bagging and random forests reduce that variance by averaging trees trained on bootstrap resamples with a random feature subset at each split. The averaging is what reduces variance; the feature subsampling is what decorrelates the trees so the averaging actually helps.

Why this matters on an MCU. A boosted ensemble of shallow trees compiles into straight-line comparison code with the thresholds as immediates. There is no matrix, no accumulator, no arena — inference is tens of comparisons and adds, often under a microsecond, with a completely flat memory profile. For tabular sensor features this is frequently both the most accurate and the cheapest option, and it is the reason libraries that emit C code from a trained ensemble are a staple of industrial embedded ML.

Part CNeural networks, from one neuron

A neural network is a composition of simple parameterised functions. This part builds it up from the smallest unit and counts its cost at every step, because the counting is what the rest of the course is about.

3.10Neurons, layers and backpropagation

A fully connected (dense) layer with n inputs and m outputs computes y = φ(Wx + b), with a weight matrix W of size m×n, a bias vector b and an element-wise activation φ. Its cost is exact and worth memorising:

Without the non-linearity φ, any stack of layers would collapse into a single matrix multiplication and could only represent linear functions. With it, a network with even one hidden layer can approximate any continuous function on a bounded domain given enough units (the universal approximation theorem); depth makes many functions far cheaper to represent than width alone.

How the weights are learned: backpropagation

Training a network is gradient descent on its loss. The gradient with respect to millions of weights is computed efficiently by backpropagation, which is the chain rule of calculus applied layer by layer from the output back to the input. The forward pass computes and stores every layer's activations; the backward pass multiplies by each layer's local derivative and reuses those stored activations to obtain the weight gradients. Two consequences matter for embedded systems. Training costs roughly three times the arithmetic of inference per example; and it needs the activations of every layer at once, so its memory footprint is many times that of inference — the reason on-device training is a research problem (Session 4) rather than a configuration option.

3.11Convolutional networks

For signals with spatial or temporal structure — images, spectrograms, multi-axis IMU windows — a dense layer is wasteful: it learns a separate weight for every input position, although a useful pattern (an edge, an onset, a harmonic) looks the same wherever it occurs. A convolutional layer instead slides a small learned kernel (for example 3×3) across the input and applies the same weights at every position. This weight sharing cuts parameters by orders of magnitude and builds in translation equivariance: a pattern shifted in the input produces the same response, shifted.

A convolutional network stacks such layers, interleaved with non-linearities and with downsampling (stride or pooling) that halves the spatial size while the number of channels grows. Early layers respond to local, simple patterns; later layers combine them into larger, more abstract ones. The network ends with global average pooling and a small dense classifier.

Four more building blocks

• Stride and pooling. A convolution with stride 2 evaluates the kernel at every second position, halving each spatial dimension; a pooling layer does the same with a fixed operation (maximum or average over a 2×2 window). Both cut the activation size by 4× per step. Global average pooling at the end of the network averages each channel over all positions, leaving one number per channel.
• Batch normalisation (BN). During training, BN standardises each channel's activations over the mini-batch and then rescales them with two learned parameters; it makes deep networks much easier to train. At inference it is a fixed per-channel scale and shift, which can be folded into the preceding convolution's weights and bias at no cost (developed below).
• Residual (skip) connections. A block's input is added to its output, y = x + F(x), so the block only has to learn a correction. Residual connections are what made networks of tens to hundreds of layers trainable. Their embedded cost is memory: the input tensor must stay alive until the addition, which raises peak SRAM.
• Depthwise-separable convolution. A factorisation of the standard convolution into a per-channel spatial filter and a 1×1 channel mixer; it is the basis of every efficient architecture and gets its own section below.

The figure is the most important cost fact about CNNs on microcontrollers, already met in Session 1: activations are largest at the front of the network, parameters at the back. Flash is sized by the parameters; SRAM by the largest pair of consecutive activation tensors. The next section makes the arithmetic precise.

3.12The three currencies

Every layer has three costs and they do not correlate:

• Parameters — bytes of flash, and the thing model-size headlines report. Dominated by the final dense layers and by 1×1 convolutions with many channels.
• MACs — arithmetic work, the thing FLOP counts report. Dominated by early convolutions at high spatial resolution.
• Bytes moved — traffic between memory levels, the thing that actually determines latency and energy (Session 1, Fig 1.7). Dominated by whichever layer has poor operand reuse.

A network can be simultaneously parameter-light, MAC-light and slow. Recognising this is the central idea of this part of the chapter.

Table 3.2 — Layer cost formulas. Learn these; the rest of the course assumes them. Note that a dilated convolution costs exactly what an ordinary convolution costs while covering a larger receptive field — which is why it is the standard trick for cheap temporal context.

3.13Depthwise separable convolution depth

3.14Normalisation and activations at inference time

Activations. ReLU is free and quantizes perfectly (it is exactly representable and its output range is bounded below). ReLU6 — min(max(0,x),6) — was adopted in MobileNet precisely to bound the activation range so that low-precision arithmetic has a predictable dynamic range. swish = x·σ(x) improves accuracy but needs a sigmoid; MobileNetV3 replaces it with hard-swish, x·ReLU6(x+3)/6, which is piecewise linear, cheap in integer arithmetic, and nearly as accurate. This is a clean example of a design decision made by the target hardware rather than by the loss curve.

3.15Sequence models on constrained hardware

Sensor data arrive as streams, and three families of model can consume a stream: recurrent networks, which carry a state from step to step; convolutional networks over time (1-D CNNs and temporal convolutional networks), which look at a fixed window; and attention-based transformers, which compare every element of a window with every other. The recurrent idea is the simplest to draw.

Table 3.3 — Sequence models compared on the axes that matter at the edge. The decisive property is not accuracy per parameter but whether inference can be made streaming with bounded state: an always-on device processes an unbounded stream and cannot afford a cache that grows with time.

Streaming inference deserves emphasis. A convolutional model applied to overlapping windows recomputes most of its early layers on every window. A streaming implementation keeps a ring buffer per layer and computes only the new columns, reducing work by roughly the overlap factor. This is standard practice in production keyword spotters and is exactly the kind of systems optimisation that never appears in an accuracy table.

Receptive field. For a stack of convolutions with kernel sizes k_i, strides s_i and dilations d_i, the receptive field grows as R_i = R_i−1 + (k_i−1)·d_i·Π_j<is_j. Check it: a model whose receptive field is shorter than the event it must recognise cannot work, and no amount of training will reveal the reason.

3.16Classical or deep? A decision guide

There is no universal answer, but there is a reliable procedure. Start with the cheapest model that could work — a tree ensemble or logistic regression on a dozen time-domain or spectral features — and measure it on a subject-wise split. Move to a neural network only if that baseline misses the target, and then start with the smallest architecture of the families below. Record, for every candidate, accuracy and flash, peak SRAM, MACs and measured latency: the decision is made on the Pareto front of those, not on accuracy alone.

Table 3.4 — A first decision guide. "Usually" matters: each row is a prior to be tested on the validation set, not a rule.

Part DEfficient architectures and architecture search

Designing the network to be cheap from the start is usually more effective than shrinking a network that was not. This part explains the design principles behind the architecture families used on phones and microcontrollers, and how their design was automated. Presentation topic C covers the primary papers.

3.17Five design principles, each earned

1. Factorise expensive operations. Depthwise separable convolution replaces one joint spatial-and-channel mixing with two cheap ones (§3.13). Everything in this part is a variation on that move.
2. Keep tensors small where they are large. Peak activation memory occurs early (§1.6), so downsample aggressively in the stem. MCU-targeted networks often use a strided stem with very few channels for exactly this reason.
3. Spend parameters where they are cheap and MACs where they are cheap — different places. Late layers are parameter-heavy and compute-light; early layers the reverse.
4. Respect memory access cost. Equal channel widths, few branches, few element-wise operations (§3.19).
5. Choose operators the target can execute. Hard-swish over swish; ReLU6 for bounded ranges; no layer norm without hardware support; only operators the vendor compiler supports (§4.14).

3.18The families and their mechanisms

Table 3.5 — Efficient architecture families. Read the last column as the important one: every family is efficient under an assumption, and deployment failures are usually assumption violations rather than implementation bugs.

Squeeze-and-excitation, in one paragraph

An SE block computes a global average per channel, passes the resulting C-vector through a small two-layer bottleneck MLP with a sigmoid output, and multiplies each channel by its gate. It is channel-wise attention: cheap in MACs, effective in accuracy, and awkward in deployment because it introduces a global reduction (a synchronisation point that breaks streaming and patch-based execution) and a sigmoid on a path that must be quantized. This is why the Lite variants of efficient architectures remove it.

3.19ShuffleNet V2's four guidelines depth

Ma et al. (2018) measured rather than counted, and distilled four rules. They are the most useful practical result in efficient-architecture design and they follow directly from §4.3.

• G2 — excessive group convolution increases memory access cost. Grouping reduces arithmetic for a fixed channel width, which lets you widen the layer, which increases traffic. There is an optimum group count and it is not "as many as possible".
• G3 — network fragmentation reduces parallelism. Many small parallel branches (as produced by some NAS methods) look cheap in FLOPs and run poorly, because each branch has kernel-launch and scheduling overhead and none of them saturates the machine.
• G4 — element-wise operations are not negligible. ReLU, tensor addition, and depthwise convolutions themselves have near-zero FLOPs and substantial memory traffic. In the paper's profiling of ResNet-like blocks, element-wise operations account for a material share of runtime despite being invisible in a FLOP count.

3.20Neural architecture search, decomposed depth

Following Elsken et al.'s survey, every NAS method is three choices.

• Search space. Cell-based spaces search one repeated block; macro spaces search the whole network including widths and resolutions. For MCUs the space itself must be constrained — TinyNAS's contribution is largely that it first chooses a search space whose members fit the device's SRAM and flash, and only then searches within it. Searching a space whose members cannot fit is wasted compute.
• Search strategy. Reinforcement learning (NASNet, MnasNet), evolutionary search, Bayesian optimisation, and differentiable relaxations (DARTS, ProxylessNAS) in which the architecture is a continuous mixture of candidate operations optimised by gradient descent alongside the weights.
• Performance estimation. Training every candidate is infeasible, so: train a single over-parameterised supernet whose sub-networks share weights and evaluate sub-networks directly; or train briefly and extrapolate; or fit a predictor from architecture encoding to accuracy. Each shortcut introduces a ranking bias, and whether supernet rankings correlate with true rankings is an active and unresolved question.

Making hardware cost differentiable

MnasNet uses measured on-device latency inside a multi-objective reward. ProxylessNAS goes further: it builds a latency model as a sum of per-operation measured latencies, which makes expected latency a differentiable function of the architecture-mixing probabilities, so latency enters the loss directly rather than as a reward signal. It also solves the memory problem of differentiable NAS by binarising the paths so only one candidate operation is resident at a time. The result is a network specialised to one hardware target — and the paper's own experiments show that networks specialised for a GPU, a CPU and a mobile phone genuinely differ, which is the empirical justification for this entire part.

Once-for-All attacks the resulting cost problem: if you need a different model per device, do you rerun the search per device? OFA trains one supernet with progressive shrinking — supporting varying depth, width, kernel size and resolution — from which specialised sub-networks are extracted without further training, reported as more than 10¹⁹ sub-networks from a single training run. This decouples the one-off training cost from the per-device deployment cost, which is the right structure for a product line with a dozen hardware variants.